【正文】 隨機選擇兩個位置 5 4 3 9 8 1 7 6 2 交換相應的城市 5 4 6 9 8 1 7 3 2 24 圖 310 3— 交換變異的說明 遺傳算法控制參數(shù)設定 遺傳算法中需要選擇的參數(shù)主要有染色體長度 l 、群體規(guī)模 n、交叉率 cp 、變異率 mp等，這些參數(shù)對 GA 性能影響很大。 圖 34 基于位置交叉運算的說明 基于順序的交叉 是基于位置交叉的變型，其中一個雙親選定位置上的城市的順序強制被另一雙親相應城市所代替。 級數(shù)定標 將原來適應度函數(shù)值以接近 1的次方來擴大各個個體間的差異。 目前所出現(xiàn)最大的目標函數(shù)值。 Gray 編碼的方法是首先對問題的解進行二進制編碼，再將二進制編碼轉換為相應的Gray編碼，然后進行遺 傳操作，當進行適應度計算時，再將 Gray編碼轉換為相應的二進制編碼。有專家斷言遺傳算法是用來解決NP完全問題和 NP難題的趨勢 ［８］ 。子代的產生是一個生殖過程，它產生了一個新解；最后是變異，新解產生過程中可能產生基因變異，變異使某些解的編碼發(fā)生變化，使解具有更大的遍歷性。遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠的信息，通過選擇、交叉、變異操作能迅速 排除與最優(yōu)解相差極大的染色體。在實際的物流配送中，配送車輛如果能在最佳時段 (如圖 23 中的 ? ?le, 內將貨物送到顧客處，則不處罰；若在圖 23 中的（ ? ?ea, 或 ? ?bl, ）時段內才送達，則顧客的滿意度降低 (轉化為懲罰函數(shù) )，而且顧客不接受上述兩個時段以外的時間 （ ? ?a,?? 或 ? ??,b ）收貨。根據(jù)任務特征可分為以下兩類： （ 1）集貨或送貨的車輛優(yōu)化調度 載貨車輛由車場出發(fā)到幾個集貨點裝貨后返回車場（僅有裝貨），或是車輛出發(fā)到幾個送貨點卸貨（僅有卸貨）后返回車場。目前已提 6 出的啟發(fā)式算法很多，按 Cesar Rego 的分類法有以下四類： （ 1）算法 (Constructive Algorithm) 根據(jù)一些準則，每一次將一個不在線路上的點增加進線路，直到所有的點都被安排進線路為止。 按任務性質分，有對弧服務問題 (如中國郵遞員問題 )和對點服務問題 (如旅行商問題 )以及混合服務問題 (如交通車線路安排問題 )。 3B 2B 1B 用戶 工廠 1A 2A 3A 進貨 送貨 集貨 存儲 配貨 車輛 配裝 3 圖 12 傳統(tǒng)的物流配送模式 物流中心配送作業(yè)的重點是如何將車輛有效的使用并決定其最經濟的行駛路線圖，使商品能在最短的時間內送到顧客的手中。 目前國內采用遺傳算法解決物流配送的車輛優(yōu)化調度問題的研究還處在起步階段。并對所采用的遺傳算法的基本理論做了論述。配送的流程一般如下圖所示。李大為等 (1998)以 TSP的最近距離啟發(fā)式為基礎，通過設置評價函數(shù)來處理時間窗約束，求解了簡單的 VSP。 常用的基本理論和方法有：分枝界定法、割平面法、線性規(guī)劃法、動態(tài)規(guī)劃法、匹配理論、對偶理論、組合理論、線搜索技術、列生成技術、概率分析、統(tǒng)計分析、最差情況分析、經驗分析等?；趩l(fā)式的并行算法和一些稱為亞啟發(fā)式算法 (Metaheuristics、 Laporte 和 Osman， 1996)的方法都屬于此類 (Cesar Rego， 1998； Gendrea、 Laporte 和 Potvin， 1994)［８ ］ 。 9 第 2 章 有時間窗的車輛優(yōu)化調度問題 (VSPTW) 時間窗的定義 VSPTW問題是傳統(tǒng)的車輛優(yōu)化調度問題加上時間窗約束，時間窗約束可分為硬時間窗、軟時間窗與混合型時間窗。許多傳統(tǒng)優(yōu)化方法都是從搜索空間的單點出發(fā)，通過某些轉換 規(guī)則確定下一點。第二是隨機產生初始群體。分類器 CS1是 Halland與 Keitman實現(xiàn)的第一個基于遺傳算法的機器學習系統(tǒng)。但也存在以下缺點： （ 1）相鄰整數(shù)的二進制編碼可能具有較大的 Hamming 距離。 適應度函數(shù) 在遺傳算法中，適應度是用來區(qū)分群體中個體（問題的解）的好壞，適應度越大的個體越好，反之，適應度越小的個體越差。在另一方面，在搜索過程的后期，雖然群體中存在足夠的多樣性，但群體的平均適應 度可能會接近群體的最優(yōu)適應度。采用二進制編碼、實數(shù)編碼和自然數(shù)編碼時所采用的交叉策略不一樣，其中自然數(shù)編碼所采用的交叉策略有如下幾種： 部分映射交叉 (PMX ) PMX可看作二進制串的兩點或多點交叉在自然數(shù)編碼中的擴展，并應用修復程序來解決簡單兩點交叉引起的非法性。 雙親 1： 5 4 6 3 8 7 2 9 1 原始后代： 4 * * 1 8 9 * * * 雙親 2： 1 2 3 4 9 8 7 6 5 后代： 4 2 3 1 8 9 7 6 5 選擇位置 22 圖 36 反轉變異的說明 插入變異 隨機地選擇一個城市，并將它插入到一個隨機的位置中 。目前許多學者認識到這些參數(shù)需要隨著遺傳進程而自適應變化，這種有自組織性能的遺傳算法具有更強的魯棒性、全局收斂性和計算效率 ［９］［１０］ 。為了使線路安排具有一定的彈性，可預先估計一個完成任務所需要的車輛數(shù) m： 11 ????????????????aqgmnii (41) 其中， [ ]表示不大于括號內數(shù)字的 最大整數(shù)， ? ?10 ??aa 是對裝車或卸車的復雜性程度及約束多少的估計，一般來講，裝 (卸 )車越復雜，約束越多， a 應越小，表示一輛車所能承載的貨物量越小。 單車場車輛優(yōu)化調度問題的一條可行線路可編成長度為 mn? 的染色體? ?mwmts iiiiiiii ???? ,0,0,0 12222111211 ，其中 kji 用自然數(shù)表示，代表編號為 kj 的需求點。如染色體 021304605870表示的行車線路為： 子路徑 1: 配送中心 0 → 需求點 2 → 需求點 1→ 需求點 3→ 配送中心 0 子路徑 2: 配送中心 0 → 需求點 4 → 需求點 6→ 配送中心 0 子路徑 3: 配送中心 0 → 需求點 5→ 需求點 8→ 需求點 7→ 配送中心 0 29 圖 41 遺傳算法解決 VSPTW算法流程圖 這種染色體結構子路徑內部是有序的，若子路徑 1中點 1， 3相互交換位置，會使目標函數(shù)值改變；而子路徑之間是無序的，若子路徑 1和 2相互交換位置，卻不會改變目標函數(shù)的值；若子路徑倒轉，如 0460倒轉為 0640，也不會改變目標函數(shù)的值。 為構造數(shù)學模型方便，將物流配送中心編號為 0，需求點編號為 n,1? ，則物流配送中心及需求點均以點 ? ?nii ,1,0 ?? 來表示， 完成配送任務共需要車輛 數(shù)目為 m ，每輛車的載重量為 q ，每個需求點的需求量為 ? ?nigi ,2,1 ?? ，配送中心及各需求點中任意兩點間的距離為 ? ?njnid ij ,1,0。 時間窗約束下的物流配送運輸在實際中是存在的，如某些特定的用戶在斷貨時提出的緊急配送到貨的時間要求、為飯店配送鮮活水產品、為有固定時刻表的火車、飛機等轉運點送貨以及超市配送用戶要求送貨不能太早于開門營業(yè)時間、也不能太晚于銷售缺貨時間等。 圖 37 插入變異的說明 易位變異 隨機地選擇一個子巡回，并將其插入到一個隨機的位置中，如圖 38中所示。 過程說明見圖 32。在這種情況下，應該放大個體的適應度，以提高個體之間的競爭力。 ??3 適應度函數(shù)是用來區(qū)分群體中個體好壞的 工具，是算法演化過程的驅動力，是進行自然選擇的唯一依據(jù)。 （ 2）在求解連續(xù)優(yōu)化問題時，采用 二進制編碼，一般要預先給出解的精度以確定串長，而精度確定后難以在算法中調整。遺傳算法與神經網(wǎng)絡的相結合應用于機械設計、結構優(yōu)化、決策分析。第三是是適應度函數(shù)的構造和應用，計算每個染色體適應度。遺傳算法是以點集開始的尋優(yōu)過程，初始群體是隨機地在搜索空間中選取的，覆蓋面大，利于全局尋優(yōu)。圖 21為一懲罰函數(shù) (Penalty Function)當貨品送達時間超出 ? ?le, 時，其懲罰值 ??tP 等于一個非常大的正值， 表示硬時間窗的限制。 貨運車輛優(yōu)化調度問題的分類 根據(jù)任務的性質將貨物運輸分成以下幾類： 非滿載車輛優(yōu)化調度問題 當貨物量小于車輛容量時，用一輛車執(zhí)行任務，存在不滿載運行情況，調度時可安排一 7 輛車執(zhí)行多項任務，即在一輛車上同時載有不同貨主的貨物。 人機互動法 此方法結合人類決策與計算機計算能力，在求解的過程中，通過高度的人機交互模式，結合專家的決策信息，并據(jù)以計算出結果；優(yōu)點是尋優(yōu)的過程中，決策者可以很清楚地看到各約束條件之間的替代關系，以及 參數(shù)變化可能導致的成本變化。遺傳算法和神經網(wǎng)絡方法對簡單 TSP的求解取得了一定成果。但是在現(xiàn)代的配送系統(tǒng)中，零售商為了減少資金積壓及提供多樣化的商品，勢必要減少各種商品的存貨數(shù)量，而同時又必須考慮到提供最好的服務品質 (不允許缺 貨 )。經實驗分析，取得了較好的結果。此外，我國具有強大物流配送資源優(yōu)勢的郵政業(yè)更是在遞送包裹的基礎上為企業(yè)、商家和電子商務網(wǎng)站積極開展配送業(yè)務。 在 物流配送系統(tǒng)中，物流配送中心的成立可有效的簡化配送程序與減少配送的頻率，以i個供應商和 j 個零售商為例，傳統(tǒng)的配送模式是假設 j個零售 商的需求都是由 i個供應商自行配送，則一共有 ij 次的運送，如圖 12 所示。 分類 VSP 被 提 出 后 ， Linus (1981),Bodin 和 Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和 Savelsbergh(1990)等許多學 者對 VSP從不同角度，按不同的標準進行了分類。 啟發(fā)式解法 (Heuristics) 由于上述三種方法的求解效率 較差，所以大部分的學者都致力于啟發(fā)式解法的發(fā)展。 （ 2）集貨和送貨一體化的車輛優(yōu)化調度 每一項貨運任務都有自己的集貨點和送貨點，車輛從車場出發(fā)，去某一任務的集貨地點裝貨后運至其送貨地點卸貨（即裝卸混合），完成所有任務后返回車場。圖 22就是一種可能的懲罰函數(shù)。遺傳算法在優(yōu)化過程中，放棄使用這些輔助信息，具有廣泛適應性。第四是染色體的交叉。Malmb,1996。 15 Gray 編碼 Gray編碼的目的是為了克服二進制編碼的 Hamming懸崖缺陷。 16 目標函數(shù)映射成適應度函數(shù) 遺傳算法適應度函數(shù)值作為染色體的性能指標，以及利用繁殖概率的大小來評估各染色體的優(yōu)劣程度，多半以最大化為目標 (亦即越大越好 )；但是許多優(yōu)化問題 (比如物流配送 VSP問題 )是求取費用函數(shù)的最小值，必須將目標函數(shù)轉化為求最大值形式己得到適應度函數(shù)，而且保證適應度函數(shù)非負。 表 31 遺傳算法中適應度常用的定標方法 定標方法 方法描述 17 線性定標 將群體中各個體的適應度以線性關系縮放，這種方法控制每一代中表現(xiàn)最佳的個體復制數(shù)目，但當群體中個體適應度差異在定標前就己經有顯著差異時，經由此法轉換的新適應度可能會有負值產生， 違背了概率不得為負數(shù)的限制，必須輔以其他方法處理。 19 圖 32 PMX運算的說明 隨機選擇子巡回 1 2 3 4 9 8 7 6 5 5 4 6 9 3 8 7 1 2 雙親 1： 雙親 2： 交換雙親中的子串 1 2 6 9 9 8 7 1 2 5 4 3 4 3 8 7 6 5 原始后代 1： 原始后代 2： 用映射關系將后代合法化 后代 1： 后代 2： 3 5 6 9 4 8 7 1 2 2 9 3 4 6 8 7 6 5 確定映射關系 6 9 1 2 3 4 6 5 1 6 3 2 5 9 4 20 圖 33 OX 運算的說明 基于位置的交叉 Step l：從第一雙親上隨機地選擇一組位置； Step 2：將這些位置復制到一個空子串的相應位置，產生一個原始后代； Step 3：刪去第二雙親上該組中已有的城市，剩下的城市構成了原始后代需要的順序； Step 4：按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。將 2— 交換和 3— 交換作為遺傳算法的變異算子，即在每代群體中以概率 P，隨機選取染色體上的兩點或 3點，進行 2— 交換或 3— 交換。根據(jù)小組成員的