交叉熵方法(Cross-Entropy Method )邂逅組合優化

從《The Cross-Entropy Method A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning 》一書總結和COP、ML相關的精華+對其他相關paper的解讀~

大綱

Motivation of CEM指數族Generating Random VariablesCEM公式推導及在item placement上的應用、The TLR MethodCEM for Max-Cut Problem CEM for TSP、Speeding up Trajectory Generation of CEM for TSP使用最佳樣本的CEM的收斂性CEM for Sequence Alignment ProblemThe Markov Decision Process and Reinforcement Learning CEM代碼實戰CEM+constraints技巧、理論分析對CEM的細微改進，持續更新CEM文獻整理、資料安利Future Work

Motivation of CEM

運籌學中的許多日常任務涉及解決複雜的優化問題。旅行商問題（TSP），二次分配問題（QAP）和最大割問題是組合優化問題（COP）的代表性示例，這些問題的結構是完全已知的且是靜態的。相比之下，緩衝區分配問題（BAP）是一個嘈雜的估計問題，需要對未知目標函數進行估計。 離散事件模擬是一種估計未知目標函數的方法，近年來隨機算法特別是交叉熵（CE）越來越流行。CE方法的名稱來KL散度，這是現代資訊理論的基本概念。該方法是由自適應算法驅動的，用於估計複雜隨機網絡中稀有事件的概率（涉及方差最小化）。很快The cross-entropy method for combinatorial and continuous optimization、Combinatorial optimization, cross-entropy, ants and rare events意識到，對Optimization of computer simulation models with rare events的簡單修改，涉及到CE最小化，它不僅可以用於估計稀有事件的概率，還可以用於解決困難的組合優化和連續的多極值問題（ 通過將原始的「確定性」優化問題轉換為相關的「隨機」估計問題，然後應用類似於Optimization of computer simulation models with rare events的罕見事件模擬機制）。簡言之，CE方法涉及一個兩階段迭代過程：

1.根據指定的機制生成隨機數據樣本（軌跡，向量等）。

2.根據數據更新隨機機制的參數，以在下一次迭代中生成「更好」的樣本。

這種新方法的強大功能和普遍性在於，更新規則通常是簡單明了的（因此速度很快），並且"optimal" in some well-defined mathematical sense。另外，CE方法為仿真和優化提供了統一方法，且在新領域的開拓上有著巨大的力。

CE方法的應用越來越多。有關CE方法應用的最新出版物包括：緩衝區分配[9]；靜態仿真模型[85]；電信系統的排隊模型[43、46]；神經計算[50]；控制和導航[83]；DNA序列比對[98]；信號處理[110]；調度[113]；車輛路線[36]；強化學習[117]；項目管理[37]；重尾分布[15，103];  CE融合[114]；網絡可靠性[87]；可修復系統[137]；最大割和分割問題[147]。

注意：

1.CE方法可以成功處理確定/嘈雜（eg:目標函數被加性「噪聲」「破壞」，這種情況通常發生在基於仿真的問題如緩衝區分配問題中）的問題。

2.CE主頁包含許多連結，文章，參考，教程和電腦程式，可在以下網站找到：http://www.cemethod.org/

指數族

Generating Random Variables

本節我們簡要描述幾種從指定分布中生成隨機變量的方法。

1.The Inverse-Transform Method  

通常，逆變換方法要求cdf F的逆函數可以比較容易被推算出來。適用的分布是指數分布，均勻分布，威布爾分布，對數分布和柯西分布……

對於離散的m點隨機變量，可以將逆變換方法編寫如下：

離散分布的逆變換方法--算法1.7.2

算法1.7.2中的大部分執行時間都花在了步驟2的比較上。我們可通過有效的搜索技術減少時間。參見Non-Uniform Random Variate generation。

逆變換方法可以輕鬆擴展到來自給定聯合cdf F（x）的獨立隨機變量的隨機向量X =（Xb ...，Xn）。在這種情況下，我們僅將方法分別應用於每個組件。

對於dependent變量，由於它需要了解Xi的邊際和條件分布，因此其適用性非常有限。

2.Alias Method

Alias Method 方法不需要像算法1 7.2的步驟2那樣費時地搜索。它基於以下事實：

Alias Method 方法相當通用且有效，但是需要為n-1個pdf g（k）進行初始setting和額外的存儲。可以在Non-Uniform Random Variate generationcon中找到計算two-point pdf g（k），k = 1，...，n-1的過程。一旦建立了（1.45），generation from f 就很簡單，並且 可以寫成：

3.The Composition Method

The Composition Method 假設cdf F可以表示為不同cdf H_i的組合

因此，為了根據F生成X，我們必須首先生成上面給出的離散隨機變量Y，然後給定Y = i，從Hi生成Xi：

4 The Acceptance-Rejection Method

從直接處理要生成的隨機變量的cdf的意義上來說，逆變換和合成方法是直接方法。不幸的是，對於許多概率分布，逆變換很難或不可能找到。即使逆變換F-1以顯式形式存在，逆變換方法也不一定是最有效的變量生成方法。當上述直接方法失敗或被證明計算效率低下時，可以使用由約翰·馮·諾伊曼（John von Neumann）提出的一種間接方法，即接受拒絕方法（ARM）。

要執行ARM，我們需要指定（1）容易根據h生成隨機變量的pdf h，以及（2）常數C>=1，使得對所有x都有C h（x）>=f（x）  。因此，我們將f（x）表示為

根據ARM，我們獨立生成兩個隨機變量，服從U（O，1）的U和服從h（y）的Y，並測試不等式U<=g（Y）。如果不等式成立，那麼我們接受Y作為來自f（x）的必需隨機變量；否則，我們拒絕pair (U, Y)，然後重試直到獲得成功的pair (U, Y)：

證明

接受拒絕方法的效率由接受概率p = P（U<=g（Y））= 1 / C決定（。請注意，在成功配對（U，Y）出現之前，試驗次數服從幾何分布，

為了使該方法具有實際意義，在選擇h（x）時必須使用以下標準：

1.從h（x）生成隨機變量應該很容易。

2.1 / C不應太小，即h（x）應該與f（x）「接近」。

使用相同的推理，算法1. 7.5直接適用於多維情況。我們只需記住，此時Y（參閱算法1.7.5的步驟2）變成n維（而不是一維）隨機向量。因此，我們需要一種從多維pdf h（y）生成Y的便捷方法。注意，如果h（x）≠ f（x），則ARM的效率會隨著n急劇降低。實際上，它只能用於n <10（ 參見Modern Simulation and Modeling）。

CEM公式推導及在item placement上的應用

進化策略優化算法CEM(Cross Entropy Method)介紹！https://blog.csdn.net/ppp8300885/article/details/80567682

其中的黑箱猜數代碼：

from scipy.stats import binom 
import numpy as np
import copy
n=10
N=50
y=np.array([1, 1, 1, 1, 1, 0, 0, 0, 0, 0])#np.random.choice([0,1],size=n)
p=np.array([0.5]*n)
def S(x):
  return n-np.linalg.norm(x-y,ord=1)
rho=1
eps=1e-6
jitter=1e-1
x=[]
score=[]
for _ in range(N):
  tmp=[np.random.choice([0,1],size=1,p=[1-p[i],p[i]])[0] for i in range(n)]
  x.append(tmp)
  score.append(S(tmp))
x=np.array(x)
elite=np.argwhere(np.array(score)>=np.percentile(sorted(score),100-rho))
p_old=p.copy()
tmp=x[elite].reshape([len(elite),n]).T
for i in range(n):
  p[i]=np.sum(tmp[i])/len(elite)
t=1

while t<30:#sum([min(1-p[i],p[i]) for i in range(n)])>eps:
  x=[]
  score=[]
  for _ in range(N):
    tmp=[np.random.choice([0,1],size=1,p=[1-p[i],p[i]])[0] for i in range(n)]
    x.append(tmp)
    score.append(S(tmp))
  x=np.array(x)
  elite=np.argwhere(np.array(score)>=np.percentile(sorted(score),100-rho))
  tmp=x[elite].reshape([len(elite),n]).T
  for i in range(n):
    p[i]=max(min(np.sum(tmp[i])/len(elite),1-jitter),jitter)
  print(p)
  t+=1
  if t%20==0:
    print(t)
交叉熵進化算法+PPO求解設備放置問題 nips論文簡讀 - 微塵-黃含馳的文章 - 知乎 https://zhuanlan.zhihu.com/p/182578237
The TLR Method
變換似然比transform likelihood ratio （TLR）方法是一種構建適用於輕/重尾分布的有效IS估計量
的簡單、便捷和統一的方法。詳情見《The Cross-Entropy Method A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning 》P91~
CEM for Max-Cut Problem
最大割問題可以表示如下：
給定具有節點集V = {1，...，n}和邊集E的加權圖G（V，E），將圖的節點劃分為兩個子集v1和v2，以最大化使從一個子集到另一個子集的邊權重之和。（NP難！）
假設權重非負，且不失一般性+簡單起見，假設圖G是完全且無向的。令非負對稱成本矩陣C =（Cij）表示邊權重。
形式上，一個 cut就是指V的一個分割{V1，V2}。例如，如果V = {1，...，6}，則{{1，3，4}，{2，5，6}}是一個可能的 cut。cut的成本是整個cut的權重之和。例如，請考慮以下6 x 6成本矩陣
通過割矢量x =（x1，...，xn）表示cut將很方便，如果節點i與1屬於同一分區，則Xi = 1，否則為0。（根據定義x1 =1）例如，cut {{1，3，4}，{2，5，6}}可以通過割矢量（1、0、1、1、0、0）表示。
令花體X為所有割矢量x =（1，x2，,••，Xn）的集合，令S（x）為割的相應成本。我們希望通過CE方法最大化S。
因此，（a）我們需要指定隨機切割矢量的生成方式，（b）計算相應的更新公式。生成剪切向量的最自然最簡單的方法是，使X2，...，Xn為獨立的伯努利隨機變量，其成功概率為p2，...，pn：
A Synthetic Max-Cut Problem
由於最大割問題NP難，因此不存在解決最大割問題的有效方法。天真的總枚舉例程僅適用於小圖（如n<=30的圖）。儘管分支定界啟發式方法可以精確地解決中等大小的問題，但是當n變大時，它也會遇到問題。
為了驗證CE方法的準確性，我們構建了一個人工圖以便可以提前獲得解。特別地，對於m  {1，...，n}，考慮以下對稱成本矩陣：
Z11是mxm對稱矩陣，所有上對角元素均由U（a，b）分布生成（所有下對角元素均遵循對稱性），Z22是（n-m）x（n-  m）對稱矩陣，元素生成方式與Z11類似，除對角元素（0）之外，C的所有其他元素均為c。
當然，如果Z11和Z22中的元素是通過任意有界支撐分布生成的，且支撐的最大值小於c，我們也可以找到相似的最佳解和最佳值。
 表2.3列出了對於有n = 400個節點的網絡，CEM算法的典型輸出：
注-partition的另一種生成方式
書中給出的代碼P275，也許有點舊
% A Matlab demonstration of the CE method for
% solving the synthetic MAXCUT problem
clear
% Setting parameters
m = 200; % (2m nodes total)
N = 1000; % sample size
rho= 0.1;
maxiters=23; % Number of iterations
% set random seed
rand('state',1234);
% first construct a random cost matrix
Z11 = rand(m);
for i = 1:m,
for j =i:m,
Z11(j,i) Z11(i,j);
end;
Z11(i,i) 0;
end
Z22 = rand(m);
for i = 1:m,
for j =i:m,
Z22(j,i) Z22(i,j);
end;
Z22(i,i) O· '
end
B12 ones(m); 
B21 = ones(m);
C = [Z11 B12; B21 Z22]; %cost matrix
% Calculating optimal score
optp = [ones(1,m),zeros(1,m)]
y rand(1,2*m);
A.2 The Max-Cut Problem 275
x = (y <optp); %generate cut vector, according top
s = scut(C,x);
fprintf('Best score %f\n',s)
%Initializing
p = 1/2 *ones (1,2*m);
p(1) = 1;
gammas= zeros(1,max!ters);
curbests = zeros(1,max!ters);
ps = zeros(max!ters,2*m);
pdist = zeros(1,max!ters);
tic
curbest=O.O;
for j=(1:max!ters) %main CE loop
j % output interation number
% generate matrix X of cutvectors
Y = rand(N,2*m);
X= (Y < ones(N,1)*p);
g = zeros(N,1);
for i=1:N
g(i,:) = scut(C,X(i,:));
end
[sortcut,sortidx] = sort(g);
% update gamma
% sortidx(1) contains index of the smallest
% cutvector
eidx = ceil((1-rho)*N); %smallest index of best
gamma= sortcut(eidx);
curbest = max(curbest,sortcut(end)) %keep track of best result
gammas(j)=gamma;
curbests(j) = curbest;
pdist(j) = min(norm(p -optp),norm(p- -optp));
% update p on basis of elite vectors, that is, the vectors
% X(sortidx(eidx),:) to X(sortidx(N),:)
for i=1:2*m
p(i)= sum(X(sortidx(eidx:N),i))/(N-eidx+1);
end
ps(j':) = p; 
end
toe %end timing
% gammas is the calculated gamma
% pdist is the distance from the optimal p
finalp = p
fprintf('Calculated best score %f\n',curbest);
figure(1);
plot(1:max!ters,gammas);
xlabel('t');ylabel('\gamma_t');
figure(4);
plot(1:max!ters,pdist);
xlabel('Number of iteration');ylabel('l lp-p_o_p_t I 1_2');
figure(2);
subplot(10,1,1); bar(1/2*ones(1,2*m));
for j=1:9
subplot(10,1,j+1); bar(ps(j,:));
end
figure(3);
for j=1:10
subplot(10,1,j); bar(ps(j+9,:));
end
for i = 1:max!ters
fprintf('%d %f %f %f\n',i,gammas(i),curbests(i), pdist(i));
end
function [perf] = scut(C,x)
Vi= find(x);% {V1,V2} is the partition
V2 = find(-x);
perf = sum(sum(C(V1,V2))); %the size of the cut
CEM for TSP
粗糙翻譯--假定該圖是完整的，即每個節點都相互連接是很方便的。請注意，這不會導致通用性下降，因為對於不完整的圖，我們總是可以以無限的成本添加其他邊而不會影響最小行程。如圖4.5所示，並帶有相應的成本矩陣
x = ( x1 , ... , Xn)
粗糙翻譯--備註4.10（向前和向後循環） 對於具有對稱成本矩陣C的TSP，始終至少存在兩個最優行程。例如，如果在圖4.5中成本矩陣是對稱的，並且（1、2、3、5、4、6）是最佳行程，則（1、6、4、5、3、2）也是 最佳遊覽。我們可以將一個巡視稱為前進巡視，將另一個巡視稱為後退巡視。為了區分前進和後退，可以使用以下簡單規則：對於前向巡視X2 <Xn，對於後退巡視X2> Xn·
路徑長表達示例
粗糙翻譯--我們的目標是使用CE方法在集合X上最小化（4.32）中的S。為了使S最小，我們需要指定一種用於生成隨機遊覽x的機制，並且像往常一樣，採用基本的交叉熵算法4.2.1來更新與此機制關聯的分布的參數。考慮到旅行商問題提出了SEN-Stochastic Edge Network 型優化問題，我們現在提出第一個隨機軌跡生成算法，該算法基於通過網絡節點的過渡。更具體地，為了生成隨機遊程X =（XI。...，Xn），我們使用n x n轉移概率矩陣P，然後根據算法2.5.1進行處理，為便於參考，下面將其重複用作算法4.7.1。回想一下，像往常一樣，我們在軌跡生成算法中包括了目標函數計算的額外步驟。
①generate trajectories either via node transitions
詳細版本
②generate trajectories either via node placements
對應於以下事件：節點i站在置換的第j位。
(區別主要在step 4、step 5的if條件上)
我們可以使用alias方法來加速軌跡生成。在這種情況下，需要考慮初始設置和額外的存儲，但由於別名方法非常快，因此對大的n，相比逆變換和接受/拒絕方法，我們優先考慮alias方法。對於TSP和生成類似解的問題，我們使用了alias、接受-拒絕和逆變換方法的組合，如下所述。
請注意，我們的目標是使用概率矩陣P生成n個數字的排列。為簡單起見，請考慮算法4.11.2，即，使用P中的第i行生成排列中的第i個數字。使用alias方法和接受拒絕方法的組合生成數字的前x％。使用逆變換方法生成其餘數字。令Alias（i，P）表示通過別名方法使用P中的第i行生成的隨機數。
其中的黑箱猜數代碼：
from scipy.stats import binom 
import numpy as np
import copy
n=10
N=50
y=np.array([1, 1, 1, 1, 1, 0, 0, 0, 0, 0])#np.random.choice([0,1],size=n)
p=np.array([0.5]*n)
def S(x):
  return n-np.linalg.norm(x-y,ord=1)
rho=1
eps=1e-6
jitter=1e-1
x=[]
score=[]
for _ in range(N):
  tmp=[np.random.choice([0,1],size=1,p=[1-p[i],p[i]])[0] for i in range(n)]
  x.append(tmp)
  score.append(S(tmp))
x=np.array(x)
elite=np.argwhere(np.array(score)>=np.percentile(sorted(score),100-rho))
p_old=p.copy()
tmp=x[elite].reshape([len(elite),n]).T
for i in range(n):
  p[i]=np.sum(tmp[i])/len(elite)
t=1

while t<30:#sum([min(1-p[i],p[i]) for i in range(n)])>eps:
  x=[]
  score=[]
  for _ in range(N):
    tmp=[np.random.choice([0,1],size=1,p=[1-p[i],p[i]])[0] for i in range(n)]
    x.append(tmp)
    score.append(S(tmp))
  x=np.array(x)
  elite=np.argwhere(np.array(score)>=np.percentile(sorted(score),100-rho))
  tmp=x[elite].reshape([len(elite),n]).T
  for i in range(n):
    p[i]=max(min(np.sum(tmp[i])/len(elite),1-jitter),jitter)
  print(p)
  t+=1
  if t%20==0:
    print(t)
交叉熵進化算法+PPO求解設備放置問題 nips論文簡讀 - 微塵-黃含馳的文章 - 知乎 https://zhuanlan.zhihu.com/p/182578237
The TLR Method
變換似然比transform likelihood ratio （TLR）方法是一種構建適用於輕/重尾分布的有效IS估計量
的簡單、便捷和統一的方法。詳情見《The Cross-Entropy Method A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning 》P91~
CEM for Max-Cut Problem
最大割問題可以表示如下：
給定具有節點集V = {1，...，n}和邊集E的加權圖G（V，E），將圖的節點劃分為兩個子集v1和v2，以最大化使從一個子集到另一個子集的邊權重之和。（NP難！）
假設權重非負，且不失一般性+簡單起見，假設圖G是完全且無向的。令非負對稱成本矩陣C =（Cij）表示邊權重。
形式上，一個 cut就是指V的一個分割{V1，V2}。例如，如果V = {1，...，6}，則{{1，3，4}，{2，5，6}}是一個可能的 cut。cut的成本是整個cut的權重之和。例如，請考慮以下6 x 6成本矩陣
通過割矢量x =（x1，...，xn）表示cut將很方便，如果節點i與1屬於同一分區，則Xi = 1，否則為0。（根據定義x1 =1）例如，cut {{1，3，4}，{2，5，6}}可以通過割矢量（1、0、1、1、0、0）表示。
令花體X為所有割矢量x =（1，x2，,••，Xn）的集合，令S（x）為割的相應成本。我們希望通過CE方法最大化S。
因此，（a）我們需要指定隨機切割矢量的生成方式，（b）計算相應的更新公式。生成剪切向量的最自然最簡單的方法是，使X2，...，Xn為獨立的伯努利隨機變量，其成功概率為p2，...，pn：
A Synthetic Max-Cut Problem
由於最大割問題NP難，因此不存在解決最大割問題的有效方法。天真的總枚舉例程僅適用於小圖（如n<=30的圖）。儘管分支定界啟發式方法可以精確地解決中等大小的問題，但是當n變大時，它也會遇到問題。
為了驗證CE方法的準確性，我們構建了一個人工圖以便可以提前獲得解。特別地，對於m  {1，...，n}，考慮以下對稱成本矩陣：
Z11是mxm對稱矩陣，所有上對角元素均由U（a，b）分布生成（所有下對角元素均遵循對稱性），Z22是（n-m）x（n-  m）對稱矩陣，元素生成方式與Z11類似，除對角元素（0）之外，C的所有其他元素均為c。
當然，如果Z11和Z22中的元素是通過任意有界支撐分布生成的，且支撐的最大值小於c，我們也可以找到相似的最佳解和最佳值。
 表2.3列出了對於有n = 400個節點的網絡，CEM算法的典型輸出：
注-partition的另一種生成方式
書中給出的代碼P275，也許有點舊
% A Matlab demonstration of the CE method for
% solving the synthetic MAXCUT problem
clear
% Setting parameters
m = 200; % (2m nodes total)
N = 1000; % sample size
rho= 0.1;
maxiters=23; % Number of iterations
% set random seed
rand('state',1234);
% first construct a random cost matrix
Z11 = rand(m);
for i = 1:m,
for j =i:m,
Z11(j,i) Z11(i,j);
end;
Z11(i,i) 0;
end
Z22 = rand(m);
for i = 1:m,
for j =i:m,
Z22(j,i) Z22(i,j);
end;
Z22(i,i) O· '
end
B12 ones(m); 
B21 = ones(m);
C = [Z11 B12; B21 Z22]; %cost matrix
% Calculating optimal score
optp = [ones(1,m),zeros(1,m)]
y rand(1,2*m);
A.2 The Max-Cut Problem 275
x = (y <optp); %generate cut vector, according top
s = scut(C,x);
fprintf('Best score %f\n',s)
%Initializing
p = 1/2 *ones (1,2*m);
p(1) = 1;
gammas= zeros(1,max!ters);
curbests = zeros(1,max!ters);
ps = zeros(max!ters,2*m);
pdist = zeros(1,max!ters);
tic
curbest=O.O;
for j=(1:max!ters) %main CE loop
j % output interation number
% generate matrix X of cutvectors
Y = rand(N,2*m);
X= (Y < ones(N,1)*p);
g = zeros(N,1);
for i=1:N
g(i,:) = scut(C,X(i,:));
end
[sortcut,sortidx] = sort(g);
% update gamma
% sortidx(1) contains index of the smallest
% cutvector
eidx = ceil((1-rho)*N); %smallest index of best
gamma= sortcut(eidx);
curbest = max(curbest,sortcut(end)) %keep track of best result
gammas(j)=gamma;
curbests(j) = curbest;
pdist(j) = min(norm(p -optp),norm(p- -optp));
% update p on basis of elite vectors, that is, the vectors
% X(sortidx(eidx),:) to X(sortidx(N),:)
for i=1:2*m
p(i)= sum(X(sortidx(eidx:N),i))/(N-eidx+1);
end
ps(j':) = p; 
end
toe %end timing
% gammas is the calculated gamma
% pdist is the distance from the optimal p
finalp = p
fprintf('Calculated best score %f\n',curbest);
figure(1);
plot(1:max!ters,gammas);
xlabel('t');ylabel('\gamma_t');
figure(4);
plot(1:max!ters,pdist);
xlabel('Number of iteration');ylabel('l lp-p_o_p_t I 1_2');
figure(2);
subplot(10,1,1); bar(1/2*ones(1,2*m));
for j=1:9
subplot(10,1,j+1); bar(ps(j,:));
end
figure(3);
for j=1:10
subplot(10,1,j); bar(ps(j+9,:));
end
for i = 1:max!ters
fprintf('%d %f %f %f\n',i,gammas(i),curbests(i), pdist(i));
end
function [perf] = scut(C,x)
Vi= find(x);% {V1,V2} is the partition
V2 = find(-x);
perf = sum(sum(C(V1,V2))); %the size of the cut
CEM for TSP
粗糙翻譯--假定該圖是完整的，即每個節點都相互連接是很方便的。請注意，這不會導致通用性下降，因為對於不完整的圖，我們總是可以以無限的成本添加其他邊而不會影響最小行程。如圖4.5所示，並帶有相應的成本矩陣
x = ( x1 , ... , Xn)
粗糙翻譯--備註4.10（向前和向後循環） 對於具有對稱成本矩陣C的TSP，始終至少存在兩個最優行程。例如，如果在圖4.5中成本矩陣是對稱的，並且（1、2、3、5、4、6）是最佳行程，則（1、6、4、5、3、2）也是 最佳遊覽。我們可以將一個巡視稱為前進巡視，將另一個巡視稱為後退巡視。為了區分前進和後退，可以使用以下簡單規則：對於前向巡視X2 <Xn，對於後退巡視X2> Xn·
路徑長表達示例
粗糙翻譯--我們的目標是使用CE方法在集合X上最小化（4.32）中的S。為了使S最小，我們需要指定一種用於生成隨機遊覽x的機制，並且像往常一樣，採用基本的交叉熵算法4.2.1來更新與此機制關聯的分布的參數。考慮到旅行商問題提出了SEN-Stochastic Edge Network 型優化問題，我們現在提出第一個隨機軌跡生成算法，該算法基於通過網絡節點的過渡。更具體地，為了生成隨機遊程X =（XI。...，Xn），我們使用n x n轉移概率矩陣P，然後根據算法2.5.1進行處理，為便於參考，下面將其重複用作算法4.7.1。回想一下，像往常一樣，我們在軌跡生成算法中包括了目標函數計算的額外步驟。
①generate trajectories either via node transitions
詳細版本
②generate trajectories either via node placements
對應於以下事件：節點i站在置換的第j位。
(區別主要在step 4、step 5的if條件上)
我們可以使用alias方法來加速軌跡生成。在這種情況下，需要考慮初始設置和額外的存儲，但由於別名方法非常快，因此對大的n，相比逆變換和接受/拒絕方法，我們優先考慮alias方法。對於TSP和生成類似解的問題，我們使用了alias、接受-拒絕和逆變換方法的組合，如下所述。
請注意，我們的目標是使用概率矩陣P生成n個數字的排列。為簡單起見，請考慮算法4.11.2，即，使用P中的第i行生成排列中的第i個數字。使用alias方法和接受拒絕方法的組合生成數字的前x％。使用逆變換方法生成其餘數字。令Alias（i，P）表示通過別名方法使用P中的第i行生成的隨機數。