用免疫算法求解TSP問(wèn)題-Read

用免疫算法求解TSP問(wèn)題1．免疫算法的生物學(xué)基礎(chǔ)免疫系統(tǒng)是哺乳動(dòng)物抵御外來(lái)有害物質(zhì)侵害的防御系統(tǒng)，動(dòng)物一生始終處于復(fù)雜多變的、充滿傷害的自然環(huán)境中，能夠平安無(wú)事、進(jìn)行正常的生命活動(dòng)，免疫系統(tǒng)在其中起著重要的作用。免疫是生物體的特異性生理反應(yīng),由具有免疫功能的器官、組織、細(xì)胞、免疫效應(yīng)分子及基因等組成。免疫系統(tǒng)通過(guò)分布在全身的不同種類(lèi)的淋巴細(xì)胞識(shí)別和清除侵入生物體的抗原性異物。當(dāng)生物系統(tǒng)受到外界病毒侵害時(shí),便激活自身的免疫系統(tǒng),其目標(biāo)是盡可能保證整個(gè)生物系統(tǒng)的基本生理功能得到正常運(yùn)轉(zhuǎn)。免疫功能主要是通過(guò)分布全身的免疫細(xì)胞來(lái)實(shí)現(xiàn)的，免疫細(xì)胞主要有巨噬細(xì)胞、抗體及淋巴細(xì)胞等。其中淋巴細(xì)胞主要有B細(xì)胞和T細(xì)胞兩種類(lèi)型，它們是免疫反應(yīng)中的主要作用細(xì)胞根據(jù)Burnet的細(xì)胞克隆選擇學(xué)說(shuō)和Jerne免疫網(wǎng)絡(luò)學(xué)說(shuō)：生物體內(nèi)先天具有針對(duì)不同抗原特性的多樣性B細(xì)胞克隆，抗原侵入機(jī)體后，在T細(xì)胞的識(shí)別和控制下，選擇并刺激相應(yīng)的B細(xì)胞系，使之活化、增殖并產(chǎn)生特異性抗體結(jié)合抗原：同時(shí)，抗原與抗體、抗體與抗體之間刺激和抑制關(guān)系形成的網(wǎng)絡(luò)調(diào)節(jié)結(jié)構(gòu)維持著免疫平衡。圖I所示為免疫系統(tǒng)的反應(yīng)過(guò)程的一種抽象描述。當(dāng)人工免疫系統(tǒng)受到外界攻擊時(shí),內(nèi)在的免疫機(jī)制被激活,其目標(biāo)是保證整個(gè)智能信息系統(tǒng)的基本信息處理功能正常運(yùn)作。免疫系統(tǒng)以其有限的資源，能夠有效地應(yīng)付數(shù)量龐大得幾近無(wú)限的不同種類(lèi)的病毒的侵害，這一特性無(wú)疑引起了人們特別的關(guān)注。在學(xué)科交叉性越來(lái)越大的今天，人們?cè)趶尼t(yī)學(xué)的角度，分析和研究這一特性的同時(shí)，也希望能以此作為啟發(fā)，設(shè)計(jì)出新的具有突破性的應(yīng)用方法，以解決某些應(yīng)用領(lǐng)域中目前難以解決的難題，免疫算法正是這一思路的產(chǎn)物，是受生物免疫系統(tǒng)的啟示而設(shè)計(jì)出來(lái)的一種具有對(duì)多峰值函數(shù)進(jìn)行多峰值搜索及全局尋優(yōu)能力的新型算法。2．免疫算法的提出在生命科學(xué)領(lǐng)域中，人們已經(jīng)對(duì)遺傳(Heredity)與免疫(Immunity)等自然現(xiàn)象進(jìn)行了廣泛深入的研究。六十年代Bagley和Rosenberg等先驅(qū)在對(duì)這些研究成果進(jìn)行分析與理解的基礎(chǔ)上，借鑒其相關(guān)內(nèi)容和知識(shí)，特別是遺傳學(xué)方面的理論與概念，并將其成功應(yīng)用于工程科學(xué)的某些領(lǐng)域，收到了良好的效果。時(shí)至八十年代中期，美國(guó)Michigan大學(xué)的Hollan教授不僅對(duì)以前的學(xué)者們提出的遺傳概念進(jìn)行了總結(jié)與推廣，而且給出了簡(jiǎn)明清晰的算法描述，并由此形成目前一般意義上的遺傳算法(GeneticAlgorithm)GA。由于遺傳算法較以往傳統(tǒng)的搜索算法具有使用方便、魯棒性強(qiáng)、便于并行處理等特點(diǎn)，因而廣泛應(yīng)用于組合優(yōu)化、結(jié)構(gòu)設(shè)計(jì)、人工智能等領(lǐng)域。另一方面，F(xiàn)armer和Bersini等人也先后在不同時(shí)期、不同程度地涉及到了有關(guān)免疫的概念。遺傳算法是一種具有生成+檢測(cè)(generateandtest)的迭代過(guò)程的搜索算法。從理論上分析，迭代過(guò)程中，在保留上一代最佳個(gè)體的前提下，遺傳算法是全局收斂的。然而，在對(duì)算法的實(shí)施過(guò)程中不難發(fā)現(xiàn)兩個(gè)主要遺傳算子都是在一定發(fā)生概率的條件下，隨機(jī)地、沒(méi)有指導(dǎo)地迭代搜索，因此它們?cè)跒槿后w中的個(gè)體提供了進(jìn)化機(jī)會(huì)的同時(shí)，也無(wú)可避免地產(chǎn)生了退化的可能。在某些情況下，這種退化現(xiàn)象還相當(dāng)明顯。另外，每一個(gè)待求的實(shí)際問(wèn)題都會(huì)有自身一些基本的、顯而易見(jiàn)的特征信息或知識(shí)。然而遺傳算法的交叉和變異算子卻相對(duì)固定，在求解問(wèn)題時(shí)，可變的靈活程度較小。這無(wú)疑對(duì)算法的通用性是有益的，但卻忽視了問(wèn)題的特征信息對(duì)求解問(wèn)題時(shí)的輔助作用，特別是在求解一些復(fù)雜問(wèn)題時(shí)，這種忽視所帶來(lái)的損失往往就比較明顯了。實(shí)踐也表明，僅僅使用遺傳算法或者以其為代表的進(jìn)化算法，在模仿人類(lèi)智能處理事物的能力方面還遠(yuǎn)遠(yuǎn)不足，還必須更加深層次地挖掘與利用人類(lèi)的智能資源。從這一點(diǎn)講，學(xué)習(xí)生物智能、開(kāi)發(fā)、進(jìn)而利用生物智能是進(jìn)化算法乃至智能計(jì)算的一個(gè)永恒的話題。所以，研究者力圖將生命科學(xué)中的免疫概念引入到工程實(shí)踐領(lǐng)域，借助其中的有關(guān)知識(shí)與理論并將其與已有的一些智能算法有機(jī)地結(jié)合起來(lái)，以建立新的進(jìn)化理論與算法，來(lái)提高算法的整體性能?；谶@一思想，將免疫概念及其理論應(yīng)用于遺傳算法，在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問(wèn)題中的一些特征信息或知識(shí)來(lái)抑制其優(yōu)化過(guò)程中出現(xiàn)的退化現(xiàn)象，這種算法稱(chēng)為免疫算法(ImmuneAlgorithm)IA。下面將會(huì)給出算法的具體步驟，證明其全局收斂性，提出免疫疫苗的選擇策略和免疫算子的構(gòu)造方法，理論分析和對(duì)TSP問(wèn)題的仿真結(jié)果表明免疫算法不僅是有效的而且也是可行的，并較好地解決了遺傳算法中的退化問(wèn)題。3．免疫算法中涉及的術(shù)語(yǔ)簡(jiǎn)介抗原：在生命科學(xué)中，是指能夠刺激和誘導(dǎo)機(jī)體的免疫系統(tǒng)使其產(chǎn)生免疫應(yīng)答，并能與相應(yīng)的免疫應(yīng)答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應(yīng)的物質(zhì)。在我們的算法中，是指所有可能錯(cuò)誤的基因，即非最佳個(gè)體的基因?？贵w：在生命科學(xué)中，是指免疫系統(tǒng)受抗原刺激后，免疫細(xì)胞轉(zhuǎn)化為漿細(xì)胞并產(chǎn)生能與抗原發(fā)生特異性結(jié)合的免疫球蛋白，該免疫球蛋白即為抗體。在本文中是指根據(jù)疫苗修正某個(gè)個(gè)體的基因所得到的新個(gè)體。其中，根據(jù)疫苗修正某個(gè)個(gè)體基因的過(guò)程即為接種疫苗，其目的是消除抗原在新個(gè)體產(chǎn)生時(shí)所帶來(lái)的負(fù)面影響。免疫疫苗：根據(jù)進(jìn)化環(huán)境或帶球問(wèn)題，所得到的對(duì)最佳個(gè)體基因的估計(jì)。免疫算子：同生命科學(xué)中的免疫理論類(lèi)似，免疫算子也分兩種類(lèi)型：全免疫和目標(biāo)免疫，二者分別對(duì)應(yīng)于生命科學(xué)中的非特異性免疫和特異性免疫。其中，全免疫是指群體中每個(gè)個(gè)體在變異操作后，對(duì)其每一環(huán)節(jié)都進(jìn)行一次免疫操作的免疫類(lèi)型；目標(biāo)免疫則指?jìng)€(gè)體在進(jìn)行變異操作后，經(jīng)過(guò)一定判斷，個(gè)體僅在作用點(diǎn)處發(fā)生免疫反應(yīng)的一種類(lèi)型。前者主要應(yīng)用于個(gè)體進(jìn)化的初始階段，而在進(jìn)化過(guò)程中基本上不發(fā)生作用，否則將很有可能產(chǎn)生通常意義上所說(shuō)的“同化現(xiàn)象”；后者一般而言將伴隨群體進(jìn)化的全部過(guò)程,也是免疫操作的一個(gè)常用算子。免疫調(diào)節(jié)：在免疫反應(yīng)過(guò)程中，大量的抗體的產(chǎn)生降低了抗原對(duì)免疫細(xì)胞的刺激，從而抑制抗體的分化和增殖，同時(shí)產(chǎn)生的抗體之間也存在著相互刺激和抑制的關(guān)系，這種抗原與抗體、抗體與抗體之間的相互制約關(guān)系使抗體免疫反應(yīng)維持一定的強(qiáng)度，保證機(jī)體的免疫平衡。免疫記憶：指免疫系統(tǒng)將能與抗原發(fā)生反應(yīng)的抗體作為記憶細(xì)胞保存記憶下來(lái)，當(dāng)同類(lèi)抗原再次侵入時(shí)，相應(yīng)的記憶細(xì)胞被激活而產(chǎn)生大量的抗體，縮短免疫反應(yīng)時(shí)間?？乖R(shí)別：通過(guò)表達(dá)在抗原表面的表位和抗體分子表面的對(duì)位的化學(xué)基進(jìn)行相互匹配選擇完成識(shí)別，這種匹配過(guò)程也是一個(gè)不斷對(duì)抗原學(xué)習(xí)的過(guò)程，最終能選擇產(chǎn)生最適當(dāng)?shù)目贵w與抗原結(jié)合而排除抗原。 4．免疫算法的算法思想、具體步驟免疫算法主要包括如下幾個(gè)關(guān)鍵步驟：(1)產(chǎn)生初始群體：對(duì)初次應(yīng)答，初始抗體隨機(jī)產(chǎn)生;而對(duì)再次應(yīng)答，則借助免疫機(jī)制的記憶功能，部分初始抗體由記憶單元獲取。由于記憶單元中抗體具有較高的適應(yīng)度和較好的解群分布，因此可提高收斂速度。(2)根據(jù)先驗(yàn)知識(shí)抽取疫苗(3)計(jì)算抗體適應(yīng)度(4)收斂判斷若當(dāng)前種群中包含了最佳個(gè)體或達(dá)到最大進(jìn)化代數(shù)，則結(jié)束算法;否則進(jìn)行以下步驟。(5)產(chǎn)生新抗體每一代新抗體主要通過(guò)兩條途徑產(chǎn)生：(a)基于遺傳操作生成新抗體:采用賭輪盤(pán)選擇機(jī)制，當(dāng)群體相似度小于閥值A(chǔ)0時(shí)，多樣性滿足要求，則抗體被選中的概率正比于適應(yīng)度;反之，按下述(b)的方式產(chǎn)生新抗體，交叉和變異操作均采用單點(diǎn)方式。(b)隨機(jī)產(chǎn)生P個(gè)新抗體：為保證抗體多樣性，模仿免疫系統(tǒng)細(xì)胞的新陳代謝功能，隨機(jī)產(chǎn)生P個(gè)新抗體，使抗體總數(shù)為N+P，再根據(jù)群體更新，產(chǎn)生規(guī)模為N的下一代群體。(6)群體更新：對(duì)種群進(jìn)行接種疫苗和免疫選擇操作，得到新一代規(guī)模為N的父代種群，返回步驟3免疫算法的流程圖如下：根據(jù)流程圖具體過(guò)程為：①隨機(jī)產(chǎn)生初始父代種群A1；②根據(jù)先驗(yàn)知識(shí)抽取疫苗；③若當(dāng)前群體中包含最佳個(gè)體,則算法停止運(yùn)行并輸出結(jié)果;否則繼續(xù)；④對(duì)于目前的第k代父本種群Ak進(jìn)行交叉操作，得到種群Bk；⑤對(duì)Bk進(jìn)行變異操作，得到種群Ck；⑥對(duì)Ck進(jìn)行接種疫苗操作，得到種群Dk；⑦對(duì)Dk進(jìn)行免疫選擇操作，得到新一代父本Ak+1,轉(zhuǎn)至③。5．免疫算法的收斂性一代種群的規(guī)模為n0，則所有種群的規(guī)模均為n0，種群中的所有個(gè)體均為l位的q進(jìn)制編碼。算法中的交叉操作選擇一點(diǎn)或多點(diǎn)均可。變異操作是對(duì)每個(gè)基因位以概率PM相互獨(dú)立地進(jìn)行變異，變異后處于其它任一狀態(tài)的概率均為1/q-1。算法的狀態(tài)轉(zhuǎn)移情況可用如下的隨機(jī)過(guò)程來(lái)表述：其中從Ak到Dk的狀態(tài)轉(zhuǎn)換構(gòu)成了馬爾可夫鏈，而Ak+1的狀態(tài)與前面各變量的狀態(tài)均有關(guān)。但是隨機(jī)過(guò)程{Ak|k=1,2,…,}顯然仍是一個(gè)馬爾可夫過(guò)程。設(shè)X為搜索空間,即所有個(gè)體的空間，將規(guī)模為n0的群體認(rèn)為是狀態(tài)空間S=Xn0中的一個(gè)點(diǎn)，其每個(gè)坐標(biāo)分別是X中的個(gè)體。用|S|表示S中狀態(tài)的數(shù)量，用，i=1，2，…，|S|，表示si是S中的某一狀態(tài)，用表示si，sj作為X的子集時(shí)的包含關(guān)系。用表示隨機(jī)變量V在第k代時(shí)處于狀態(tài)si。設(shè)f是X上的適應(yīng)度函數(shù)，令則可如下定義算法的收斂性。定義1如果對(duì)于任意的初始分布均有，則稱(chēng)算法收斂。該定義表明：算法收斂是指當(dāng)算法迭代到足夠多的次數(shù)以后，群體中包含全局最佳個(gè)體的概率接近于1。這種定義即為通常所說(shuō)的概率1收斂。定理免疫算法是概率1收斂的。定理的證明過(guò)程略。不過(guò)，這里需要說(shuō)明的一點(diǎn)是，如果把免疫算子從免疫算法中略去，可以證明該算法將不再保證收斂到全局最優(yōu)值，或者說(shuō)它是強(qiáng)不收斂的。6．TSP問(wèn)題描述TSP問(wèn)題是優(yōu)化搜索算法嘗試求解的經(jīng)典問(wèn)題之一，屬于NP完全問(wèn)題。TSP問(wèn)題是旅行商問(wèn)題的簡(jiǎn)稱(chēng)，即一個(gè)商人從某一城市出發(fā)，要遍歷所有目標(biāo)城市，其中每個(gè)城市必須而且只須訪問(wèn)一次。TSP問(wèn)題是尋找一條最短的遍歷n個(gè)城市的路徑，或者說(shuō)搜索整數(shù)子集X={1，2，…，n}(X的元素表示對(duì)n個(gè)城市的編號(hào))的一個(gè)排列{V1，V2，..…Vn)，使取最小值，式中的表示城市到城市的距離。由于它是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式，所以成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)。該問(wèn)題是一個(gè)典型的NP問(wèn)題，即隨著規(guī)模的增加，可行解的數(shù)目將做指數(shù)級(jí)增長(zhǎng)。6.免疫算子的構(gòu)造方法免疫算子包括全免疫和目標(biāo)免疫兩種。對(duì)于TSP問(wèn)題，要找到適用于整個(gè)抗原(即全局問(wèn)題求解)的疫苗極為困難，所以不妨采用目標(biāo)免疫。具體而言，在求解問(wèn)題之前先從每個(gè)城市點(diǎn)的周?chē)鼽c(diǎn)中選取一個(gè)路徑最近的點(diǎn)，以此作為算法執(zhí)行過(guò)程中對(duì)該城市點(diǎn)進(jìn)行目標(biāo)免疫操作時(shí)所注人的疫苗。每次遺傳操作后，隨機(jī)抽取一些個(gè)體注射疫苗，然后進(jìn)行免疫檢測(cè)，即對(duì)接種了疫苗的個(gè)體進(jìn)行檢測(cè)：若適應(yīng)度提高，則繼續(xù)；反之，若其適應(yīng)度仍不如父代，說(shuō)明在交叉、變異的過(guò)程中出現(xiàn)了嚴(yán)重的退化現(xiàn)象，這時(shí)該個(gè)體將被父代中所對(duì)應(yīng)的個(gè)體所取代。在選擇階段，先計(jì)算其被選中的概率，后進(jìn)行相應(yīng)的條件判斷。7．免疫疫苗的選取具體步驟如下：(1)分析待求問(wèn)題,搜集特征信息假設(shè)在某一時(shí)刻,某人從一城市出發(fā),欲前往下一個(gè)目標(biāo)城市.一般而言,他首先考慮的選擇目標(biāo)是距離當(dāng)?shù)芈烦套罱某鞘?如果目標(biāo)城市恰恰就是前面走過(guò)的某一城市時(shí),則下一個(gè)要到達(dá)的目標(biāo)更替為除該城市之外的距離最小的城市,并以此類(lèi)推.這種方法雖然不能作為全局問(wèn)題的解決方案,但在一個(gè)很小范圍內(nèi),比如只有三四個(gè)城市的情況(相對(duì)于全局問(wèn)題而言,這屬于一種局部問(wèn)題),這種考慮往往不失為一個(gè)較好的策略.當(dāng)然,能否作為最終的解決方案,還需要進(jìn)一步的判斷.(2)根據(jù)特征信息制作免疫疫苗基于上述認(rèn)識(shí)，就TSP問(wèn)題的特點(diǎn)而言,在最終的解決方案中,即最佳路徑的選取里，必然包括而且在很大程度上包括相鄰城市間距離最短的路徑。TSP問(wèn)題的這種特點(diǎn)即可作為求解問(wèn)題時(shí)以供參考的一種特征信息或知識(shí)，故能夠視為從問(wèn)題中抽取疫苗的一種途徑。所以在具體實(shí)施過(guò)程中，只需使用一般的循環(huán)迭代方法找出所有城市的鄰近城市即可(當(dāng)然，某一城市既可能是兩個(gè)或多個(gè)城市的鄰近城市，也可能都不是)；疫苗不是一個(gè)個(gè)體，故不能作為問(wèn)題的解。它僅僅具備個(gè)體在某些基因位上的特征。(3)接種疫苗設(shè)TSP問(wèn)題中所有與城市Ai距離最近的城市為Aj，并且二者非直接連接而是處于某一路徑的兩段：Ai-1----Ai----Ai+1和Aj-1----Aj-----Aj+1，則當(dāng)前的遍歷路徑為：P={A0,…,Ai-1,Ai,Ai+1,…,Aj-1,Aj,Aj+1,…,AN}，其對(duì)應(yīng)的路徑長(zhǎng)度為：(1)在免疫概率Pi發(fā)生條件下，對(duì)城市Ai而言,免疫算子將把其鄰近城市Aj排列為它的下一個(gè)目標(biāo)城市，而使原先的遍歷路徑調(diào)整為：πc={A0,…,Ai-1,Ai,Aj,Ai+1,…,Aj-1,Aj+1,…,AN}，則相應(yīng)的路徑長(zhǎng)度變化為：(2)比較式(1)和式(2)，因?yàn)锳j是所有城市中(即全局中)與城市Ai距離最近的點(diǎn)，在由Ai----Aj-----Ai+1所構(gòu)成的三角形中l(wèi)1一定為最短邊或次短邊(此時(shí)l2一定為最短邊.因?yàn)槿鬭i<l1，則與Ai最近的城市為Ai+1而非Aj)，而在Aj-1，Aj和Aj+1之間卻不一定具有這個(gè)性質(zhì)。所以在多數(shù)情況下，l3較aj-1+aj的減少量要大于l1+l2較ai的增加量。而且更加重要的是在這一個(gè)局部環(huán)境內(nèi)，算子對(duì)路徑做了一次最佳調(diào)整。當(dāng)然，這次調(diào)整究其能否對(duì)整個(gè)路徑有所貢獻(xiàn)，還有待于選擇機(jī)制的進(jìn)一步判斷。但是，從分析過(guò)程中，不難得出下列關(guān)系：，式中,P(A)表示事件A發(fā)生的概率。上述所謂的“調(diào)整”過(guò)程，即為是TSP問(wèn)題求解時(shí)基于某一特定疫苗的免疫注射過(guò)程。8．免疫算法的程序求解框圖如圖所示。具體過(guò)程如下：(1)個(gè)體編碼和適應(yīng)度函數(shù)算法實(shí)現(xiàn)中，將TSP問(wèn)題的目標(biāo)函數(shù)對(duì)應(yīng)于抗原，問(wèn)題的解對(duì)應(yīng)于抗體。抗體采用以遍歷城市的次序排列進(jìn)行編碼，每一抗體碼串形如:V1，V2，…，Vn，其中，Vi表示遍歷城市的序號(hào)。適應(yīng)度函數(shù)取路徑長(zhǎng)度Td倒數(shù)，即：表示第i個(gè)抗體所表示的遍歷城市的路徑長(zhǎng)度。(2)交叉與變異算子采用單點(diǎn)交叉，其中交叉點(diǎn)的位置隨機(jī)確定。對(duì)于免疫操作，算法中加人了對(duì)遺傳個(gè)體基因型特征的繼承性和對(duì)進(jìn)一步優(yōu)化所需個(gè)體特征的多樣性進(jìn)行評(píng)測(cè)的環(huán)節(jié)，在此基礎(chǔ)上設(shè)計(jì)了一種部分路徑變異法。該方法每次