【正文】 問題時，二進制編碼會占用大量的存儲空間，而且使得搜索空間極其龐大，從而影響遺傳算法的性能。這樣，可以直接在解的表現(xiàn)型上操作，從而便于引入與問題領域相關的啟發(fā)式信息，增加遺傳算法的搜索能力。 例如旅行商問題（ TSP）：選擇一條商人遍歷若干城市的最短路徑。因此 n,3,2,1 ? 的全排列 ? ?n??? , 21 ? 就可以作為 TSP 的染色體。遺傳算法正是基于適應度對個體進行選擇，以保證適應性好的個體有機會在下一代中產(chǎn)生更多的子個體。改變群體內部結構的操作都是通過適應度加以控制。 16 目標函數(shù)映射成適應度函數(shù) 遺傳算法適應度函數(shù)值作為染色體的性能指標，以及利用繁殖概率的大小來評估各染色體的優(yōu)劣程度，多半以最大化為目標 (亦即越大越好 )；但是許多優(yōu)化問題 (比如物流配送 VSP問題 )是求取費用函數(shù)的最小值，必須將目標函數(shù)轉化為求最大值形式己得到適應度函數(shù)，而且保證適應度函數(shù)非負。 目前所出現(xiàn)最大的目標函數(shù)值。 目前遺傳世代中，最后 n代出現(xiàn)的最大的目標函數(shù)值。為了保證適應度函數(shù)為非負，可以采用如下的轉化形式： ? ? ? ?轉換前轉換后 kkk fff /?? 適應度定標 在設計遺傳算法時，群體的規(guī)模一般在幾十至幾百，與實際物種的規(guī)模相差很遠。如果群體中出現(xiàn)了超級個體，即該個體的適應度大大超過了群體的平均適應度，則按照適應度比例選擇時，該個體很快在群體中占有絕對優(yōu)勢，從而導致算法較早的收斂到一個局部最優(yōu)點。在這種情況下，應該縮小這個個體的適應度，以降低這些超級個體的競爭力，防止過早收斂。在這種情況下，群體中實際上已不存在競爭，從而搜索目標難以得到改善，出現(xiàn)了停滯現(xiàn)象。 這種對適應度的縮放調整稱為適應度函數(shù)的定標。 表 31 遺傳算法中適應度常用的定標方法 定標方法 方法描述 17 線性定標 將群體中各個體的適應度以線性關系縮放，這種方法控制每一代中表現(xiàn)最佳的個體復制數(shù)目，但當群體中個體適應度差異在定標前就己經(jīng)有顯著差異時，經(jīng)由此法轉換的新適應度可能會有負值產(chǎn)生， 違背了概率不得為負數(shù)的限制，必須輔以其他方法處理。 級數(shù)定標 將原來適應度函數(shù)值以接近 1的次方來擴大各個個體間的差異。 遺傳算法的基因操作 選擇算子 發(fā)展各種復制算子的目的是為了避免基因缺失，提高全局收斂性和效率。適應度比例方法是目前遺傳算法中最基本也是最常用的復制方法，它也叫輪盤賭復制法或蒙特卡羅復制，其具體步驟如下： Step l：對各個染色體 kv 計算適應度 kf ； Step 2：計算種群中 n個染色體適應度的和 ???nk kfF 1； Step 3：對各染色體 kv ，計算選擇概率 Ffp kk /? nk ,2,1 ?? ； Step 4：對各染色體 kv 計算累計概率 ???nj jk pq 1nk ,2,1 ?? 復制過程類似旋轉轉輪 n次，每次按如下方式選出一個染色體來構造新的種群，具體過程為：在 ? ?1,0 區(qū)間內產(chǎn)生一個均勻分布的偽隨機數(shù) r，若： 1qr? ，則選擇第一個染色體 1v ；否則選擇第 k個染色體 ? ?nkvk ?,2? ，使得 kk qrq ???1 成立。 18 交叉算子 交叉算子的作用是組合出新的個體，在串空間進行有效搜索，同時需降低對有效模式的破壞概率。在 交叉算子之前需首先配對，目前采用的是隨機配對。步驟如下： Step l：在字串上均勻的選擇兩點，由這兩點定義的子串稱為映射段； Step 2：交換雙親的兩個子串，產(chǎn)生原始后代； Step 3：確定兩映射段之間的關系； Step 4： 根據(jù)映射關系將后代合法化。 順序交叉 (ox ) Step l：從第一雙親中隨機選擇一個子串； Step 2：將子串復制到一個空子串的相應位置，產(chǎn)生一個原始后代； Step 3：刪去第二雙親子串已有的城市，得到原始后代需要的其他城市的順序； Step 4：按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。 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：將這些位置復制到一個空子串的相應位置，產(chǎn)生一個原始后代； Step 3：刪去第二雙親上該組中已有的城市，剩下的城市構成了原始后代需要的順序； Step 4：按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。 圖 34 基于位置交叉運算的說明 基于順序的交叉 是基于位置交叉的變型，其中一個雙親選定位置上的城市的順序強制被另一雙親相應城市所代替。用同樣的步驟可產(chǎn)生另一個后代 [2 4 5 3 1 6 9 7 8]。變異在遺傳算法中的作用是第二位的 ［３］［５］ 。 表 32 變異算子類型 名稱 特點 研究者 適用編碼 常規(guī)位變異 標準遺傳算法成員 DeJong 二進制 有效基因變異 避免有效基因缺失 Yun 二進制 自適應有效基因變異 最低有效基因個數(shù)自適應變化 Yun 二進制 概率自調整變異 由兩個串的相似性確定變異概率 Whitley 二進制 均勻變異 由一個實數(shù)元素以相同的概率在域 內變動 Michalewicz 十進制 非均勻變異 使整個矢量在解空間輕微變動 Michalewicz 十進制 三次高斯近似變異 Bosworth, Foo,Zeigler 十進制 零變異 同上 十進制 目前較常用的高級遺傳算子，來源于群體遺傳學。說明如圖 36所示。過程示于圖 37中。 隨機選擇子巡回 5 4 3 9 8 1 7 6 2 插入子巡回 5 4 3 7 8 1 9 2 6 隨機選擇一個城市 5 4 3 9 8 1 7 6 2 插入到一個隨機位置 5 4 3 9 8 2 1 7 6 23 圖 38 易位變異的說明 k— 交換變異 k— 交換變異是解決 VSP 的一種局域尋優(yōu)技術，即對初始可行路線的 k 條邊（或弧）進行交換，在初始可行解的鄰域內逐步改進方案，直到在鄰域內不能改進為止。將 2— 交換和 3— 交換作為遺傳算法的變異算子，即在每代群體中以概率 P，隨機選取染色體上的兩點或 3點，進行 2— 交換或 3— 交換。 圖 39 2— 交換變異的說明 隨機選擇一個子巡回 5 4 3 9 8 1 7 6 2 插入到一個隨機位置 5 4 3 7 8 6 2 9 1 隨機選擇兩個位置 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 性能影響很大。通常認為：若種群過小，算法就有可能收斂于局部最優(yōu)解，而不能收斂到最優(yōu)結果或最優(yōu)結果附近。一般，當種群規(guī)模增大時，將有利于改善種群的多樣性，從而可能有利于使算法收斂到最優(yōu)解或最優(yōu)解附近。但在某些情況下，當種群達到一定規(guī)模時，再增大種群規(guī)模，對搜索結果的改善并無多大幫助，甚至有可能變差。由于控制參數(shù)會相互影響，所以無法確定獨立的最佳參數(shù)值，但當種群規(guī)模小時可選擇較大的交叉及變異率以防止過早收斂；當群體規(guī)模大時可選擇較小交叉及變異率以節(jié)省運算時間。 隨機選擇三個位置 5 4 3 9 8 1 7 6 2 交換相應的城市 5 4 3 9 8 6 7 1 2 5 4 6 9 8 1 7 3 2 5 4 6 9 8 3 7 1 2 5 4 1 9 8 6 7 3 2 5 4 1 9 8 3 7 6 2 25 第 4 章 遺傳算法求解有時間窗非滿載 VSP 由于現(xiàn)在各任務需求點，如零售商店、連鎖店等都盡可能的銷售暢銷商品，庫存數(shù)量最好不要太多，且不能缺貨，因此現(xiàn)在的物流配送一般是小范圍、近距離 、多品種、小批量、多批次、為多用戶服務的經(jīng)濟活動，這時每個任務點的貨物量小于車輛容量，用一輛車執(zhí)行單一任務，屬于非滿載運行情況，在一輛車上同時裝載有不同任務點的貨物，所以物流配送車輛優(yōu)化調度大部分是非滿載車輛優(yōu)化調度問題。 有時間窗約束的車輛優(yōu)化調度問題歸結為車輛優(yōu)化調度問題 中的單車場、單車型、非滿載、多約束（含時間窗約束）、多目標、車輛封閉的對點服務問題。根據(jù)小組成員的分工，本文就適應度函數(shù)的選定和變異算子進行主要闡述。每個需求點 (供貨點 )的需求量 (供貨量 )已知，且都小于配送車輛的載重量；配送中心和各需求點中任意兩點間的運距已知或可以推算出來；一個需求點的任務 只能由一輛車一次運送完成；每個配送車輛從配送中心出發(fā)，完成運送任務后返回配送中心。在日常生活中和生產(chǎn)實際中，許多類似的問題都可以歸結為這類問題。又如，若干廠家生產(chǎn)一些產(chǎn)品，需要運到配送中心，車輛從配送中心出發(fā)，到各廠家去裝貨，裝滿貨后返回配送中心，在滿足 廠家發(fā)貨要求的情況下，按什么線路行駛，可使總費用最小，即集貨車輛優(yōu)化調度。由于有時間窗的 VSP是典型的 NP難題，會隨著節(jié)點的增加出現(xiàn)組合爆炸的現(xiàn)象 ［５］ 。 26 一般來講，當問題的約束越多，組織線路就越難，一輛車所完成的滿足所有約束的任務就越少，這時，一輛車實際所能容納的任務量要小，而所用的車輛數(shù)可能要多。本算法采用人機對話來調整 a 的大小。,1,0 ?? ?? ，第 k 輛車的行車路徑稱為第 k條子路徑，其中經(jīng)過的需求點數(shù)目為 kn ， kp 表示第 k 條子路徑中包含的 kn 個需求點組成的集合 ，其中的元素? ?nipki ,2,1 ?? 代表第 k 條子路徑中順序為 i 的需求點； )1(0, ?knkk pp 均表示配送中心，且有 0)1(0 ?? ?knkk pp。如果車輛到達 i的時間早于 ia ，則車輛需在 i處等待，如果車輛到達時間晚于 ib ，則任務 i要延遲執(zhí)行。此問題稱之為有時間窗的車輛優(yōu)化調度問題。若超出這個時間范圍， 則得到的解為不可行解 ［２］［４］ 。懲罰成本函數(shù)的設定一般以配送中心與顧客在商議之后所簽定的合同為主，但因實際上所簽定合同是為維護買賣雙方共同的利益，故考慮的因素相當多。若車輛在 ib 之后到達點 i，則服務被延遲，須支付一定的罰金。 染色體結構 為提高效率，對 VSP采用自然數(shù)編碼方式，即序數(shù)編碼。這樣的染色體結構可通俗地理解為第一輛車從配送中心 0 出發(fā)，經(jīng)過需求點siii 11211 , ? 后，回到配送中心 0， 形成子路徑 1；第二輛車也從配送中心 0 出發(fā)，經(jīng)過以 28 前未訪問的需求點 tiii 22221 , ? 后，返回配送中心 0，形成子路徑 2；依次類推，直到所有的 n個需求點全部被遍歷，形成子路徑 m。 開始 輸入配送中心及需求點數(shù)據(jù) 輸入系統(tǒng)控制參數(shù) 輸出配送中心及需求點數(shù)據(jù)和系統(tǒng)控制參數(shù) 初始化運距數(shù)組 dd 遺傳代數(shù) GEN=0 初始化染色體種 群 計算染色體適應度 輸出中間結果 輸出結果 滿足終止條件？ GEN=GEN+1 進行遺傳操作 結束 Y N 30 約束處理 對于 VSP這類約束較復雜的優(yōu)化問題，用遺傳算法求解時，需要對約束進行處理。 在編 碼的過程中不考慮約束，而在遺傳算法的計算過程中檢測得到的染色體相應的解是否可行，若可行，則放入下一代群體中，否則將其舍棄。如果一個染色體對應的解違反了某個約束，試其違反程度給予一定懲罰，使其具有較小的適應度