❶ 用遺傳演算法求解配送路線優化問題時，交叉率和變異率怎麼設定
以下是問題的詳細回答，文字有些長，請你耐心看希望對你有幫助。
傳演算法可以很好的解決物流配送路徑優化問題。但是由於遺傳演算法交配運算元操作可能會使最好解遺失，所以將遺傳演算法和模擬退火演算法結合來解決這一問題。實驗結果表明：用這種有記憶功能的遺傳模擬退火演算法求解物流配送路徑優化問題，可以在一定程度上解決上述問題，從而得到較高質量的解。
一 物流系統簡介
物流系統是以客戶滿意為目標，根據顧客的要求條件，從生產地到銷售地，在倉儲、包裝、配送、運輸、裝卸等環節有機整合所形成的實物、服務以及信息的流通過程所組成的一個復雜的系統。
物流配送是現代化物流管理中的一個重要環節。它是指按用戶的定貨要求，在配送中心進行分貨、配貨，並將配好的貨物及時送交收貨人的活動。本文討論物流配送中的路徑優化問題，並且通過結合模擬退火演算法來解決遺傳演算法在解決此類問題時的不足。
二 系統模型設計
物流配送路徑優化問題可以按這樣的情況進行描述：從某物流配送中心用多輛配送車輛向多個客戶送貨。每個客戶的位置和貨物需求量一定，每輛車的載重量一定，配送時間一定，其一次配送的最大行駛距離一定。要求合理安排車輛配送路線，使目標函數得到最優。並滿足以下條件：（1）每條配送路徑上各客戶需求量之和不超過配送車輛的載重量；（2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；（3）每次配送的貨物不能超過客 戶要求的時間； （4）每個客戶的需求必須滿足，且只能由一輛配送車送貨。設配送中心需要向k個客戶送貨，每個客戶的貨物需求量是g （i＝1，2，…..k），每輛配送車的載重量是q，且g 下面建立此問題的數學模型：c 表示點i到點j的運輸成本，t 表示從i到s所允許的最大時間。配送中心編號為0，各客戶編號為i（i＝1，2，….，k），定義變數如下：
x = 1 或 0（其中，當x 等於1時表示車s由i駛向j；0表示沒有該路徑。）。
y = 1 或 0（其中，當y 等於1時表示點i的貨運任務由s車完成；0表示沒有。）。
根據上述變數定義可得到的數學模型如下所示：
min Z ＝ ； （1） ；（2）
＝ 1或 m（其中，當 i = 1，2，……，k時為1，否則為0。）；（3）
＝ y ，j = 1，2，……，k；s = 1，2，……，m； （4）
＝ y ，i = 0，1，……，k；s = 1，2，……，m； （5）
t > 0；且t t ， j = 1，2……，s-1； （6）
上述模型中，式（2）為汽車容量約束；式（3）保證了每個客戶的運輸任務僅由一輛車完成，而所有運輸任務則由m輛車協同完成；式（4）和式（5）限制了到達和離開某一客戶的汽車有且僅有一輛。式（6）對配送時間做了約束，即物品到達指定地點的時間不能大於其最大允許時間。
上述模型中還要考慮時間問題，即每個客戶對所送物品的時間要求各不相同，故需加入一個時間參數t 。對每個運輸路徑都加上時間參數t （t 的值可由客戶需求中得知，並記錄到資料庫。），在每個規定的時間內（如一個月），優先配送t 值小的物品，每次在用遺傳演算法求解前，遍歷規定時間內的所有t ，按照t 值由小到大排列染色體，然後再求出最優解，根據最優解制定配送方案。
三 引入退火演算法改進求解過程
針對遺傳演算法的一些不足，將模擬退火演算法與之結合，並加入記憶裝置，從而構造了物流配送路徑優化問題的一種有記憶功能的遺傳模擬退火演算法。該演算法的特點是擴大了原有遺傳演算法的搜索鄰域，在一定概率控制下暫時接受一些惡化解。同時利用記憶裝置保證了在一定終止條件下所得的最終解至少是搜索過程中曾得到所有解中的最優解。該演算法通過在常規的遺傳演算法基礎上加入模擬退火運算元和記憶裝置而得到。下面首先介紹此有記憶功能的遺傳模擬演算法的步驟。根據參考文獻[3],給出下面的演算法實現步驟：
STEP1 給定群體規模maxpop，將初始群體按照t 所指定的值進行分塊， k=0;初始溫度t ＝t ，產生初始群體pop(k)，並且初始群體的每個分塊中都具有t 滿足某一屬性的特徵值；對初始群體計算目標值f(i), 找出使函數f (t )最小的染色體i和這個函數值f，記i =i，f =f；其中，f (t )為狀態i在溫度為t 時的目標值。i∈ pop( k)，即當代群體中的一個染色體；
STEP2 若滿足結束條件則停止計算，輸出最優染色體i 和最優解f ；否則，在群體pop(k)的每一個染色體i∈ pop(k)的鄰域中隨機選一狀態j∈N( i )，且t 滿足條件要求, 按模擬退火中的接受概率
接受或拒絕j，其中f (t )， f (t )分別為狀態i，j的目標值。這一階段共需maxpop次迭代以選出新群體newpop1；
STEP3 在newpop1(k+1)中計算適應度函數
其中，f 是newpop1(k+1)中的最小值。由適應度函數決定的概率分布從newpop1中隨機選maxpop個染色體形成種群newpop2；
STEP4 按遺傳演算法的常規方法對newpop2進行交叉得到crosspop，再變異得到mutpop；
STEP5 染色體中的每個元素在滿足t 的情況下，且具有較大t 值的元素完成時沒有破壞具有較小t 值進行計算所需條件的情況下，不必按照由小到大的順序進行排列，
STEP6 令pop(k+1)=mutpop,對pop(k+1)計算f (t ),找出使函數f (t )最小的染色體i和這個函數值f，如果f < f ,則令i = i， f =f， t ＝ d(t )，k = k+1, 返回 STEP2。
出於表示簡單，計算機處理方便的目的，對於VRP問題的遺傳演算法編碼通常都採用自然數編碼。上述數學模型的解向量可編成一條長度為k＋m＋1的染色體（0，i ，i ，…,i ，0，i ,…i ，0，…0，i ,…,i ，0）。在整條染色體中，自然數 i 表示第 j 個客戶。0的數目為m＋1個，代表配送中心，並把自然數編碼分為m段，形成m個子路徑，表示由m輛車完成所有運輸任務。這樣的染色體編碼可以解釋為：第一輛車從配送中心出發，經過i ，i ，…,i 客戶後回到配送中心，形成了子路徑1；第2輛車也從配送中心出發，途徑i ,…i 客戶後回到配送中心，形成子路徑2。m輛車依次出發，完成所有運輸任務，構成m條子路徑。
如染色體0123045067890表示由三輛車完成9個客戶的運輸任務的路徑安排：
子路徑1：配送中心→客戶1→客戶2→客戶3→配送中心
子路徑2：配送中心→客戶4→客戶5→配送中心
子路徑3：配送中心→客戶6→客戶7→客戶8→客戶9→配送中心。
為了使演算法收斂到全局最優，遺傳群體應具有一定的規模。但為了保證計算效率，群體規模也不能太大。一般取群體規模取值在10到100之間。
在初始化染色體時，先生成 k 個客戶的一個全排列，再將 m＋1 個 0 隨機插入排列中，其中所選的 k 個客戶所要求的時間必須在某一個特定的時間段內，且完成任何一個客戶配送任務時不能破壞完成其他客戶配送任務的條件。需要注意的是必須有兩個 0 被安排在排列的頭和尾，並且在排列中不能有連續的兩個0。這樣構成一條滿足問題需要的染色體。針對此染色體，隨機選擇兩個位置上的元素進行交換，並用演算法對其調整，使其成為新的滿足要求的染色體。交換若干次，直至生成滿足群體規模數的染色體。
在這里，將容量約束式（2）轉為運輸成本的一部分，運輸成本變為：
其中M為一很大的正數，表示當一輛車的貨運量超過其最大載重量時的懲罰系數。M應趨向於無窮大。考慮到計算機處理的問題，參考文獻[6]，取M為1000000為宜。將此運輸成本函數作為我們的目標函數。適應度函數採用一種加速適應度函數：
這種適應度函數加速性能比較好，可以迅速改進適應度的值，縮短演算法運行時間。
將每代種群的染色體中適應度最大的染色體直接復制，進入下一代。種群中其他染色體按其適應度的概率分布，採用輪盤賭的方法，產生子代。這樣既保證了最優者可生存至下一代，又保證了其餘染色體可按生存競爭的方法生成子代，使得演算法可收斂到全局最優。選中的染色體按一定的概率—交叉率，產生子代。交叉率在0.6～0.8之間，演算法進化效果較好。
四 試驗數據與比較
實驗數據取自參考文獻[6]。
實驗1，隨機生成1個有8個門店的VRP問題，初始數據如下：
圖1八個門店的需求量及其位置
根據各倉庫的需求量，計算出需要的汽車數：m=[17.82/(0.85*8)]+1=3。採用傳統的遺傳演算法的各運算元，並對其中的交叉運算元進行了改造，取群體規模為20，進化代數為50，應用此程序他費時3s得到的結果為：
而我們的演算法在上面的演算法中加入了一個模擬退火運算元，取初始退火溫度為10，衰減系數取0.85使用第三節所述演算法步驟，在奔騰四的計算機上計算，耗時2s，得結果如下：
實驗2，隨機生成1個有20個門店的VRP問題，初始數據如下：
圖2 20個門店的需求量及其位置
計算得：需6輛車。用參考文獻[6]中的演算法取群體規模100，進化代數分別設為20，50，100，得到的結果不同：
圖3 普通遺傳演算法的實驗結果
而採用本文的演算法，初始退火溫度取10，衰減系數取0.85，在奔騰四的計算機上計算，則結果如下：
圖4 新型演算法的實驗結果
從以上兩個實驗可以看出：採用本文中所述的演算法，要得到相同的結果可以縮短進化代數，從而節約運算時間。而要增加進化代數必然得到更好的結果。
五 結論
用模擬退火演算法與傳統的遺傳演算法相結合來求解物流系統中車輛路徑問題，可以使演算法所需的進化代數明顯減少，問題解可在最短時間內求出。因此在時間特性上有了比較好的改善，耗時較短，獲得了較好的結果。根據參考資料所記載的數據表明，此演算法在解決諸如車輛路徑問題問題確實可行，並有較好的性能。而且隨著問題規模的增大，這種對時間性能的改善效果將更加明顯。這就非常有助於物流企業根據自己的實際情況科學、有效的指定物流決策，降低風險，降低成本，提高經濟效益和自身的競爭力。
參考文獻
[1] 郭耀煌 李軍著，車輛優化調度，成都：成都科技大學，1994
[2] 邢文訓 謝金星編著，現代優化計算方法，北京：清華大學出版社，1999
[3] 郎茂祥，物流配送車輛調度問題的模型和演算法研究，北京：北方交通大學，2002
[4] 郎茂祥 胡思繼，用混和遺傳演算法求解物流配送路徑優化問題的研究，中國管理科學，2002
[5] 李軍 謝秉磊 郭耀煌，非滿載車輛調度問題的遺傳演算法，系統工程理論與實踐，2000
[6] 唐坤，車輛路徑問題中的遺傳演算法設計，東北大學學報（自然科學版），2002
[7] 姜大立 楊西龍 杜文等，車輛路徑問題的遺傳演算法研究，系統工程理論與實踐，1999
[8] 閻慶 鮑遠律，新型遺傳模擬退火演算法求解物流配送路徑問題，計算機科學與發展，2002