【正文】 為了避免陷入局部最優(yōu)解，禁忌搜索中采用了一種靈活的記憶技術(shù)，對已經(jīng)進(jìn)行的優(yōu)化過程進(jìn)行記錄和選擇，以此指導(dǎo)下一步的搜索方向的選擇。 禁忌搜索的基本原理： 禁忌搜索算法是記住以往已搜索過的局部最優(yōu)解，并在進(jìn)一步迭代搜索中盡量避開這些局部最優(yōu)解，進(jìn)而使得搜索途徑多樣化，以此跳出局部最優(yōu)解，在禁忌搜索算法中涉及鄰域，候選解禁忌表，禁忌表規(guī)模，以及破禁水平等內(nèi)容。 交叉算子的選擇 由于 AGSAA是采用將彈藥箱的編號排列成串來進(jìn)行編碼的，如果個體交叉采用傳統(tǒng)方式進(jìn)行，就有可能使個體的編碼產(chǎn)生重復(fù)基因（即一個彈藥箱編號在一個個體中出現(xiàn)兩次以上），從而產(chǎn)生不符合條件的個體，因此，AGSAA采用的是部分映射交叉算子。 （ 2）定序規(guī)則（ Ordering rule） 定序規(guī)則是指用來確定彈藥箱放入運(yùn)輸工具裝載空間先后順序的規(guī)則。 適應(yīng)度函數(shù)主要考慮兩個方面 ， 即載重率和積載率 ， 對這兩個因素加權(quán) ， 來計算適應(yīng)度函數(shù)值 。 AGSAA的編碼方式 AGSAA采用二進(jìn)制編碼方式 ， 每一個二進(jìn)制位對應(yīng)一個待裝彈藥箱 ， 若為１ ， 表示該彈藥箱裝入運(yùn)輸工具 ， 為０則不裝 。 遺傳算法的應(yīng)用示例 彈藥裝載問題（ Ammunition Loading Problem，簡稱 ALP），就是在滿足各類通用彈藥運(yùn)輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運(yùn)輸工具，使得通用彈藥的裝載效率達(dá)到最大值的問題。 SA算法的收斂性理論中要求溫度終值趨于零，這顯然不合實際。 ⑹ 外循環(huán)終止準(zhǔn)則 外循環(huán)終止準(zhǔn)則，即算法終止準(zhǔn)則，用于決定算法何時結(jié)束。 而在時齊 SA算法理論中 ， 收斂條件要求在每個溫度下產(chǎn)生候選解的數(shù)目趨于無窮大 ，以使相應(yīng)的馬氏鏈達(dá)到平穩(wěn)概率分布 ， 顯然在實際應(yīng)用算法時這是無法實現(xiàn)的 。 ⑸ 內(nèi)循環(huán)終止準(zhǔn)則 內(nèi)循環(huán)終止準(zhǔn)則，或稱 Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。 || m ax?rpt ln/0 ??? rp⑷ 溫度更新函數(shù) 溫度更新函數(shù) ， 即溫度的下降方式 ， 用于在外循環(huán)中修改溫度值 。 ② 隨機(jī)產(chǎn)生一組狀態(tài) ， 確定兩兩狀態(tài)間的最大目標(biāo)值差 ， 然后依據(jù)差值 ， 利用一定的函數(shù)確定初溫 。實驗表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計算時間將增加。 狀態(tài)接受函數(shù)的引入是 SA算法實現(xiàn)全局搜索的最關(guān)鍵的因素， SA算法中通常采用min[1,exp(△ C/t)]作為狀態(tài)接受函數(shù)。 ⑵ 狀態(tài)接受函數(shù) 狀態(tài)接受函數(shù)一般以概率的方式給出 ， 不同接受函數(shù)的差別主要在于接受概率的形式不同 。 ⑴ 狀態(tài)產(chǎn)生函數(shù) 設(shè)計狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點(diǎn)應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。 )(1 kk tu p d a t et ?? 1?? kk模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)定 從算法流程上看，模擬退火算法包括三函數(shù)兩準(zhǔn)則，即狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則，這些環(huán)節(jié)的設(shè)計將決定 SA算法的優(yōu)化性能。模擬退火算法是基于 Monte Carlo 迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理退火過程與組合優(yōu)化之間的相似性， SA由某一較高初溫開始，利用具有概率突跳特性的 Metropolis抽樣策略在解空間中進(jìn)行隨機(jī)搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解。這種接受準(zhǔn)則通常稱為 Metropolis準(zhǔn)則。具體而言，在溫度 t,由當(dāng)前狀態(tài) i產(chǎn)生新狀態(tài) j，兩者的能量分別為 ，若 則接受新狀態(tài) j為當(dāng)前狀態(tài)；否則，若概率 大于 區(qū)間內(nèi)的隨機(jī)數(shù)則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留 i為當(dāng)前狀態(tài)，其中 k為 Boltzmann常數(shù)。目的是使粒子的熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 物理學(xué)的知識告訴我們 ， 對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng) ， 系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行 ， 當(dāng)自由能達(dá)到最小時 ， 系統(tǒng)達(dá)到平衡態(tài) 。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。其目的是增強(qiáng)粒子的熱運(yùn)動，使其偏離平衡位置。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。SA算法是基于 Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡(luò)路由等具有 NP難度的組合優(yōu)化問題上取得了成功的應(yīng)用。 對控制參數(shù)的改進(jìn) Srinvivas等人提出自適應(yīng)遺傳算法，即 PC和Pm能夠隨適應(yīng)度自動改變，當(dāng)種群的各個個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使二者增加，而當(dāng)種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)值高于群體平均適應(yīng)值的個體，采用較低的 PC和 Pm，使性能優(yōu)良的個體進(jìn)入下一代，而低于平均適應(yīng)值的個體，采用較高的 PC和 Pm，使性能較差的個體被淘汰 。 對遺傳算子 的改進(jìn) 排序選擇 均勻交叉 逆序變異 （ 1） 隨機(jī)產(chǎn)生一個與個體編碼長度相同的二進(jìn)制屏蔽字 P = W1W2… Wn ； （ 2） 按下列規(guī)則從 A、 B兩個父代個體中產(chǎn)生兩個新個