【正文】 這樣，一些不可行解也有可能進(jìn)入群體，以保證群體中染色體的數(shù)目，使遺傳算法得以繼續(xù)。 采用懲罰的方法來(lái)處理約束。一般有下面幾種方法： 問(wèn)題的約束在染色體中表現(xiàn)出來(lái)，設(shè)計(jì)專(zhuān)門(mén)的遺傳算子，使染色體所表示的解在遺傳算法的求解過(guò)程中始終保持為可行解。如染色體 021304605870表示的行車(chē)線(xiàn)路為： 子路徑 1: 配送中心 0 → 需求點(diǎn) 2 → 需求點(diǎn) 1→ 需求點(diǎn) 3→ 配送中心 0 子路徑 2: 配送中心 0 → 需求點(diǎn) 4 → 需求點(diǎn) 6→ 配送中心 0 子路徑 3: 配送中心 0 → 需求點(diǎn) 5→ 需求點(diǎn) 8→ 需求點(diǎn) 7→ 配送中心 0 29 圖 41 遺傳算法解決 VSPTW算法流程圖 這種染色體結(jié)構(gòu)子路徑內(nèi)部是有序的，若子路徑 1中點(diǎn) 1， 3相互交換位置，會(huì)使目標(biāo)函數(shù)值改變；而子路徑之間是無(wú)序的，若子路徑 1和 2相互交換位置，卻不會(huì)改變目標(biāo)函數(shù)的值；若子路徑倒轉(zhuǎn)，如 0460倒轉(zhuǎn)為 0640，也不會(huì)改變目標(biāo)函數(shù)的值。 單車(chē)場(chǎng)車(chē)輛優(yōu)化調(diào)度問(wèn)題的一條可行線(xiàn)路可編成長(zhǎng)度為 mn? 的染色體? ?mwmts iiiiiiii ???? ,0,0,0 12222111211 ，其中 kji 用自然數(shù)表示，代表編號(hào)為 kj 的需求點(diǎn)。 算法設(shè)計(jì) 算法流程圖 算法流 程圖如圖 41示。若車(chē)輛在 ia 之前到達(dá)點(diǎn) i，則車(chē)輛在此等待，發(fā)生了機(jī)會(huì)成本損失。 軟時(shí)間窗 VSP指如果每項(xiàng)任務(wù)不能在要求的時(shí)間范圍內(nèi)完成，則給予一定的懲罰。 以 is 表示車(chē)輛到達(dá)點(diǎn) i的時(shí)間，一般應(yīng)有以下關(guān)系式： 00?s iii bsa ?? ni ,2,1 ?? (47) 硬時(shí)間窗 VSP指每項(xiàng)任務(wù)必須在要求的時(shí)間范圍內(nèi)完成，即必須滿(mǎn)足式 (47)。求滿(mǎn)足貨運(yùn)要求的費(fèi)用最少的車(chē)輛行使線(xiàn)路。 得到車(chē)輛優(yōu)化調(diào)度數(shù)學(xué)模型如下： ? ?? ?? ?? mk ni ppk kiikdz 1 11 )1(m in (42) qgk kini p???1 nnk ??1 ， mk ,2,1 ?? (43) nnmk k ???1 (44) ? ?? ?kkikik ninppP ,2,1,2,1| ?? ??? mk ,2,1 ?? (45) ??21 kk PP ? 21 kk ?? ； mk ,2,11 ?? ； mk ,2,12 ?? (46) 27 有時(shí)間窗 VSP 模型 設(shè)完成任務(wù) i 需要的時(shí)間 (裝貨或卸貨 )表示為 iT ，又設(shè)任務(wù) i 的開(kāi)始時(shí)間需在一定的時(shí)間范圍 ? ?ii ba, 內(nèi)，其中 ia 為任務(wù) i的允許最早開(kāi)始時(shí)間，為任務(wù) i的允許最遲開(kāi)始時(shí)間。 為構(gòu)造數(shù)學(xué)模型方便，將物流配送中心編號(hào)為 0，需求點(diǎn)編號(hào)為 n,1? ，則物流配送中心及需求點(diǎn)均以點(diǎn) ? ?nii ,1,0 ?? 來(lái)表示， 完成配送任務(wù)共需要車(chē)輛 數(shù)目為 m ，每輛車(chē)的載重量為 q ，每個(gè)需求點(diǎn)的需求量為 ? ?nigi ,2,1 ?? ，配送中心及各需求點(diǎn)中任意兩點(diǎn)間的距離為 ? ?njnid ij ,1,0。為了使線(xiàn)路安排具有一定的彈性，可預(yù)先估計(jì)一個(gè)完成任務(wù)所需要的車(chē)輛數(shù) m： 11 ????????????????aqgmnii (41) 其中， [ ]表示不大于括號(hào)內(nèi)數(shù)字的 最大整數(shù)， ? ?10 ??aa 是對(duì)裝車(chē)或卸車(chē)的復(fù)雜性程度及約束多少的估計(jì)，一般來(lái)講，裝 (卸 )車(chē)越復(fù)雜，約束越多， a 應(yīng)越小，表示一輛車(chē)所能承載的貨物量越小。 數(shù)學(xué)模型 一般 VSP 模型 物流配送中心擁有足夠的載重量為 q 的車(chē)輛，現(xiàn)有 n 個(gè)需求點(diǎn)任務(wù)需要貨物運(yùn)輸，以n,1? 表示，已知第 i個(gè)需求點(diǎn)的需要的貨物量為 ? ?nigi ,1?? ，且 qgi ? 。 有時(shí)間窗的 VSP 則是在一般車(chē)輛優(yōu)化調(diào)度問(wèn)題的基礎(chǔ)上要求每項(xiàng)任務(wù) i 在時(shí)間范圍? ?ii ba, 內(nèi)完成，并可根據(jù)時(shí)間約束的嚴(yán)格與否，分為軟時(shí)間窗和硬時(shí)間窗的 VSP。如一個(gè)中心貨場(chǎng)需向幾個(gè)顧客有運(yùn)送貨物，每個(gè)顧客對(duì)貨物有一定的要求，運(yùn)送貨物的車(chē)輛在貨場(chǎng)裝滿(mǎn)貨后發(fā)出，把貨送到各顧客處，完成任務(wù)后，返回貨場(chǎng)，如何確定滿(mǎn)足用戶(hù)需求的費(fèi)用最小的車(chē)輛行使路線(xiàn)，即送貨車(chē)輛優(yōu)化調(diào)度。求滿(mǎn)足貨運(yùn)需求和車(chē)輛載重量的費(fèi)用最小的車(chē)輛行使線(xiàn)路。 問(wèn)題描述 一般車(chē)輛優(yōu)化調(diào)度問(wèn)題可描述為：一個(gè)物流配送中心使用載重量相同的多輛汽車(chē)完成多個(gè)貨物需求點(diǎn)的配送任務(wù)。該問(wèn)題屬于組合優(yōu)化領(lǐng)域的 NP 難題 ［１１］ ，本小組嘗試使用遺傳算法求得該類(lèi)問(wèn)題的最優(yōu)解或近似最優(yōu)解。 時(shí)間窗約束下的物流配送運(yùn)輸在實(shí)際中是存在的，如某些特定的用戶(hù)在斷貨時(shí)提出的緊急配送到貨的時(shí)間要求、為飯店配送鮮活水產(chǎn)品、為有固定時(shí)刻表的火車(chē)、飛機(jī)等轉(zhuǎn)運(yùn)點(diǎn)送貨以及超市配送用戶(hù)要求送貨不能太早于開(kāi)門(mén)營(yíng)業(yè)時(shí)間、也不能太晚于銷(xiāo)售缺貨時(shí)間等。目前許多學(xué)者認(rèn)識(shí)到這些參數(shù)需要隨著遺傳進(jìn)程而自適應(yīng)變化，這種有自組織性能的遺傳算法具有更強(qiáng)的魯棒性、全局收斂性和計(jì)算效率 ［９］［１０］ 。目前常用的參數(shù)范圍是 200~20?n , ~?cp ， ~0?mp 。建議的最優(yōu)參數(shù)范圍是30~20?n , ~?cp , ~?mp 。這主要是種群規(guī)模過(guò)小，導(dǎo)致種群內(nèi)個(gè)體多樣性減小，從而可能丟失一些有意義的搜索點(diǎn)或最優(yōu)點(diǎn)，然而種群過(guò)大，每次迭代所需要的計(jì)算量就會(huì)很大，這又可能導(dǎo)致一個(gè)無(wú)法接 受的慢收斂率。為了選擇合適的群體規(guī)模 n、交叉率 cp 、變異率 mp ，許多學(xué)者進(jìn)行了研究。 2— 交換和 3— 交換說(shuō)明分別示于圖 39和圖 310中。這里說(shuō)明一下2— 交換和 3— 交換。 圖 37 插入變異的說(shuō)明 易位變異 隨機(jī)地選擇一個(gè)子巡回，并將其插入到一個(gè)隨機(jī)的位置中，如圖 38中所示。 雙親 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 反轉(zhuǎn)變異的說(shuō)明 插入變異 隨機(jī)地選擇一個(gè)城市，并將它插入到一個(gè)隨機(jī)的位置中 。主要有以下四種： 反轉(zhuǎn)變異 在染色體上隨機(jī)地選擇兩點(diǎn)，將兩點(diǎn)間的子串反轉(zhuǎn)。目前發(fā)展的主要變異算子如表 32所示。 雙親 1： 5 7 4 9 8 2 6 3 1 原始后代 ： * * 4 9 * * * 3 1 雙親 2： 1 2 3 4 9 8 7 6 5 后代 ： 2 5 4 9 8 2 6 3 1 雙親 1： 5 4 6 3 8 7 2 9 1 原始后代 ： * 4 * * 8 * * 9 1 雙親 2： 1 2 3 4 9 8 7 6 5 后代 ： 2 4 3 5 8 7 6 9 1 選擇位置 21 圖 35 基于順序交叉運(yùn)算的說(shuō)明 變異算子 當(dāng)交叉算子產(chǎn)生的后代的適應(yīng)度不在比前輩好又未達(dá)到最優(yōu)解，就會(huì)產(chǎn)生 不成熟收斂，不成熟收斂的根源是發(fā)生了有效基因缺失，這時(shí)，為克服這種情況，只有依賴(lài)于變異。說(shuō)明見(jiàn)圖 35。 圖 34 說(shuō)明了交叉過(guò)程，同樣步驟可產(chǎn)生另一個(gè)后代 [4 2 3 1 5 6 7 8 9]。 過(guò)程說(shuō)明見(jiàn)圖 33，同樣步驟可用同一對(duì)雙親產(chǎn)生另一個(gè)后代 [7 9 3 4 5 6 1 2 8]。 過(guò)程說(shuō)明見(jiàn)圖 32。采用二進(jìn)制編碼、實(shí)數(shù)編碼和自然數(shù)編碼時(shí)所采用的交叉策略不一樣，其中自然數(shù)編碼所采用的交叉策略有如下幾種： 部分映射交叉 (PMX ) PMX可看作二進(jìn)制串的兩點(diǎn)或多點(diǎn)交叉在自然數(shù)編碼中的擴(kuò)展，并應(yīng)用修復(fù)程序來(lái)解決簡(jiǎn)單兩點(diǎn)交叉引起的非法性。交叉算子是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征 [5]。 由于染色體復(fù)制后，當(dāng)前群體中最佳染色體可能喪失繁殖能力，為了提高遺傳算法的性能，可在使用輪盤(pán)賭的基礎(chǔ)上采用最佳保留策略。復(fù)制算子策略與編碼方式無(wú) 關(guān)，復(fù)制的主要思想是染色體的復(fù)制概率正比于其適應(yīng)度。此方法在計(jì)算上的步驟上比較簡(jiǎn)易，但 k的設(shè)定與問(wèn)題的類(lèi)型具有相關(guān)性。 標(biāo)準(zhǔn)差祛除法 此方法是利用平均適應(yīng)度函數(shù)與其標(biāo)準(zhǔn)差間的差異來(lái)修正原個(gè)體的適應(yīng)度，以解決線(xiàn)性定標(biāo)會(huì)產(chǎn)生負(fù)值的問(wèn)題，是線(xiàn)性定標(biāo)前的一個(gè)預(yù)處理方法，但計(jì)算上比較復(fù)雜。目前，主要的定標(biāo)技術(shù)歸納成表 31。在這種情況下，應(yīng)該放大個(gè)體的適應(yīng)度，以提高個(gè)體之間的競(jìng)爭(zhēng)力。在另一方面，在搜索過(guò)程的后期，雖然群體中存在足夠的多樣性，但群體的平均適應(yīng) 度可能會(huì)接近群體的最優(yōu)適應(yīng)度。這種現(xiàn)象稱(chēng)為過(guò)早收斂。因此，個(gè)體繁殖數(shù)量的調(diào)節(jié)在遺傳操作中就顯得比較重要。 適應(yīng)度函數(shù)一般要求非負(fù)，上述適應(yīng)度函數(shù)的轉(zhuǎn)換方法并不能保證后代的適應(yīng)度函數(shù)值為正數(shù)，一旦在遺傳過(guò)程中出現(xiàn)了比 MAX更大的適應(yīng)度函數(shù)值，就可能出現(xiàn)負(fù)的適應(yīng)度，使復(fù)制算子失效。 目前操作的群體中，最大的目標(biāo)函數(shù)值。一般可采用以下的方法進(jìn)行轉(zhuǎn)換： ? ? ? ?轉(zhuǎn)換前轉(zhuǎn)換后 kk fM A Xf ?? 其中 MAX為一常數(shù)，最好與群體無(wú)關(guān)，一般可以由下列四種方式?jīng)Q定 : 任意足夠大的正數(shù)。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問(wèn)題本身的要求而定。 ??3 適應(yīng)度函數(shù)是用來(lái)區(qū)分群體中個(gè)體好壞的 工具，是算法演化過(guò)程的驅(qū)動(dòng)力，是進(jìn)行自然選擇的唯一依據(jù)。 適應(yīng)度函數(shù) 在遺傳算法中，適應(yīng)度是用來(lái)區(qū)分群體中個(gè)體（問(wèn)題的解）的好壞，適應(yīng)度越大的個(gè)體越好，反之，適應(yīng)度越小的個(gè)體越差。設(shè)共有 n 個(gè)城市，分別用 n,3,2,1 ? 來(lái)表示，每?jī)蓚€(gè)城市 i 和 j 之間的距離用 ijd 表示，則商人的一次遍歷路線(xiàn)可以用一個(gè) n,3,2,1 ? 的全排列 ? ?n??? , 21 ? 表示，該排列表示遍歷路線(xiàn)121 ???? ???? n?。 排列編碼 對(duì)于某些問(wèn)題，排列是其解的一種自然的表示。因此當(dāng)問(wèn)題的解是實(shí)數(shù)向量時(shí)，可以直接采用實(shí)數(shù)向量編碼。 Gray 編碼可以有效的解決二進(jìn)制編碼的 Hamming 懸崖缺陷，但由于長(zhǎng)度與二進(jìn)制編碼相同，因此同樣存在二進(jìn)制編碼中（ 2）、（ 3）兩項(xiàng)缺點(diǎn)。 一個(gè) n 階 Gray碼是一個(gè)由所有 n位二進(jìn)制位串組成的有序循環(huán)序列，使得相鄰的位串之間恰有一位不同。 （ 3）在求解多維高精度優(yōu)化問(wèn)題時(shí)，二進(jìn)制編碼將會(huì)非常長(zhǎng)，從而降低算法效率。 （ 2）在求解連續(xù)優(yōu)化問(wèn)題時(shí)，采用 二進(jìn)制編碼，一般要預(yù)先給出解的精度以確定串長(zhǎng)，而精度確定后難以在算法中調(diào)整。但也存在以下缺點(diǎn)： （ 1）相鄰整數(shù)的二進(jìn)制編碼可能具有較大的 Hamming 距離。 二進(jìn)制編碼是將原問(wèn)題的解空間映射到位串空間 ??L1,0 上，其中 L 為某個(gè)固定常數(shù)。下面是幾種常用的編碼方法。它實(shí)際上確定了對(duì)問(wèn)題的描述方式，直接影響到選擇、交叉、變異這一系列基因操作，最終影響到整個(gè)遺傳算法的性能。 編碼 將問(wèn)題的解編碼為染色體是用遺傳算法解決各類(lèi)問(wèn)題的第一步，也是關(guān)鍵一步。Ochi 和 Luiz 1998 )，但僅僅是開(kāi)始嘗試階段，還有待于進(jìn)一步的研究。但在 VSP中的應(yīng)用才剛剛開(kāi)始，已有文獻(xiàn)利用遺傳算法對(duì) VSP 進(jìn)行求解 (Berthold,1995。遺傳算法與神經(jīng)網(wǎng)絡(luò)的相結(jié)合應(yīng)用于機(jī)械設(shè)計(jì)、結(jié)構(gòu)優(yōu)化、決策分析。分類(lèi)器 CS1是 Halland與 Keitman實(shí)現(xiàn)的第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)。機(jī)器學(xué)習(xí)是為解決專(zhuān)家系統(tǒng)設(shè)計(jì)中的知識(shí)獲取瓶頸問(wèn)題而設(shè)計(jì)的。目前在運(yùn)籌學(xué)、機(jī)械優(yōu)化設(shè)計(jì)、電網(wǎng)設(shè)計(jì)、生產(chǎn)管理等應(yīng)用學(xué)科中都嘗試著用遺傳算法解決現(xiàn)實(shí)優(yōu)化計(jì)算問(wèn)題。 遺傳算法的應(yīng)用總的來(lái)說(shuō)可以分為如下三大類(lèi)： 優(yōu)化計(jì)算 優(yōu)化計(jì)算是遺傳算法最直接的應(yīng)用，應(yīng)用面也最廣。 13 遺傳算法的基本流程如圖 31所示。父代的遺傳基因的結(jié)合是通過(guò)父代染色體之間的交叉并到達(dá)下一代個(gè)體的。當(dāng)適應(yīng)度函數(shù)確定以后，復(fù)制是以適應(yīng)度函數(shù)值的大小決定的概率分布來(lái)確定哪些染色體適應(yīng)生存，哪些被淘汰。第三是是適應(yīng)度函數(shù)的構(gòu)造和應(yīng)用，計(jì)算每個(gè)染色體適應(yīng)度。第二是隨機(jī)產(chǎn)生初始群體。編碼的目的主要是使優(yōu)化問(wèn)題解的表現(xiàn)形式適合于遺傳算法中的遺傳運(yùn)算。 與傳統(tǒng)方法相比，遺傳算法的優(yōu)越性主要表現(xiàn)在：首先，在遺傳算子的作用下，遺傳算法具有很強(qiáng)的搜索能力，能以很大的概率找到 問(wèn)題的全局最優(yōu)解：其次，由于它固有的并行性，能有效地處理大規(guī)模的優(yōu)化問(wèn)題。 遺傳算法中的選擇、交叉、和變異都是隨機(jī)操作，