- 相關(guān)推薦
研究人工免疫算法中旅行商問(wèn)題
0.引言
早在18世紀，愛(ài)爾蘭的數學(xué)家哈密爾頓和英國的數學(xué)家托馬斯就已經(jīng)對旅行商問(wèn)題（TSP）進(jìn)行數學(xué)研究，而旅行商問(wèn)題一般形式的研究則是由數學(xué)家卡爾·門(mén)格爾于19世紀三十年代在維也納和哈佛大學(xué)首次進(jìn)行研究的。對旅行商問(wèn)題的研究往往是出于把它作為一個(gè)可應用于解決大規模的組合最優(yōu)化問(wèn)題的一般方法的一個(gè)平臺，然而這并不是說(shuō)在很多領(lǐng)域中旅行商問(wèn)題找不到其具體的應用。事實(shí)上，旅行商問(wèn)題有許許多多的應用，它可以看成是許多領(lǐng)域內復雜工程優(yōu)化問(wèn)題的抽象形式，諸如郵路問(wèn)題、網(wǎng)絡(luò )布線(xiàn)問(wèn)題、物流配送問(wèn)題、電路板鉆孔問(wèn)題等等，這些應用給旅行商問(wèn)題的研究帶來(lái)了活力，并且幫助指導今后的研究工作。旅行商問(wèn)題本身的應用范圍正在不斷擴張，它的研究方法也正迎來(lái)越來(lái)越廣闊的發(fā)展前景�？梢钥闯�，不論從理論還是實(shí)際應用來(lái)講，研究TSP問(wèn)題取得的每一步進(jìn)展都將會(huì )有非常重大的意義。
多年來(lái)人們一直尋求求解TSP問(wèn)題的算法，其中有傳統的算法如動(dòng)態(tài)規劃法、分支極限法等，但由于其僅能用于求解規模較小的TSP問(wèn)題，在實(shí)際應用中的局限性使其無(wú)法適用于求解大規模的TSP問(wèn)題。近年來(lái)，現代流行的智能算法也越來(lái)越受到研究人員們的廣泛關(guān)注，當然人們也正在努力的探索，試圖用其求解TSP問(wèn)題。這些算法包括神經(jīng)網(wǎng)絡(luò )、遺傳算法、蟻群算法等。本文欲用另外一種人工智能算法--人工免疫算法,來(lái)求解TSP問(wèn)題。中國碩士論文網(wǎng)提供大量免費碩士畢業(yè)論文,如有業(yè)務(wù)需求請咨詢(xún)網(wǎng)站客服人員！
1.旅行商問(wèn)題的概述
1.1 旅行商問(wèn)題的描述：
旅行商問(wèn)題，簡(jiǎn)單地說(shuō)，就是某一旅行商要去n 個(gè)城市去旅行，他要把這n 個(gè)城市都逛一次而且不重復，最后回到原出發(fā)城市,問(wèn)給定所有城市之間的旅行成本，哪一種旅行路徑成本最��？為了簡(jiǎn)化，成本可理解為旅行商走過(guò)的最短距離。即已知n 個(gè)城市以及各城市間的距離，某一旅行商從某個(gè)城市出發(fā)訪(fǎng)問(wèn)每個(gè)城市有且僅一次，最終返回原出發(fā)城市，怎樣走才能使其所走的線(xiàn)路最短？
用圖論來(lái)描述，那就是已知帶權圖 G=(C，L)，尋找出總權值最小的一條路徑。其中C={c1，c2，…，cn}表示n 個(gè)城市的集合，L={ lij | ci，cj∈C}是集合C 中元素（城市）兩兩連接的集合，每條邊lij，都存在與之對應的權值dij，實(shí)際應用中dij 可以表示距離、費用、時(shí)間、油量等。
從旅行商問(wèn)題的描述來(lái)看，似乎其并不是很復雜，理解起來(lái)也是很簡(jiǎn)單，但其的確是一個(gè)非常復雜的問(wèn)題。對于n 個(gè)城市的旅行商問(wèn)題，可供選擇的路徑數目我們可以這樣計算：
起始城市訪(fǎng)問(wèn)其他城市有n-1 個(gè)選擇，第二個(gè)城市有n-2 個(gè)選擇，依此類(lèi)推，倒數第2 個(gè)城市只有1 個(gè)選擇，總的可選擇的路徑數為?n ?1?! ? (n ?1)(n ? 2)(n ? 3). . . 3 2 1。另外，我們所研究的標準的旅行商問(wèn)題其旅行成本是對稱(chēng)的，即城市i 到城市j 的旅行成本和城市j 到城市i 的旅行成本是一樣的，故對于一個(gè)包含n 個(gè)城市的旅行商問(wèn)題，可供選擇的路徑有(n ?1)!/ 2種。當n 較小時(shí)，我們可通過(guò)羅列各種路徑并從中找出最短路徑，但隨著(zhù)值n的變大，可供選擇的路徑數迅速增加，用羅列的辦法已經(jīng)無(wú)能為力了，這時(shí)必須尋求其他解法來(lái)搜索最短的路徑。
1.2 旅行商問(wèn)題的數學(xué)建模：
旅行商問(wèn)題( TSP)在數學(xué)上可以描述為以下優(yōu)化問(wèn)題。
2.人工免疫算法的基本原理2.1 生物免疫系統及其運行機制生物免疫系統是自然界生物所必備的防御系統, 它是一種由眾多細胞、分子和組織等子系統構成的復雜系統，這些子系統之間存在著(zhù)復雜的相互聯(lián)系，具有識別“自己”和“非己”，消除和消滅異物的功能。生物免疫系統又分為先天免疫系統和自適應免疫系統。先天免疫系統是一種與生俱來(lái)的天然防御系統，具有識別一定微生物并消滅這種微生物的能力，但對于絕大數外來(lái)侵入病毒的殺傷力較弱，這時(shí)候自適應免疫系統就開(kāi)始發(fā)揮它的重要作用了，它能夠自適應的學(xué)習外來(lái)侵入病毒物質(zhì)或分子的模式結構，中立或消除該種物質(zhì)。
自適應免疫系統的運行機制可以簡(jiǎn)單的概括為：在抗原的激勵下，巨噬細胞分化抗原為顆粒狀物質(zhì)，抗原呈遞細胞將這些物質(zhì)呈遞到巨噬細胞的表面；通過(guò)識別的途徑，被激活T細胞分化和分泌淋巴因子，并使B細胞應答；B細胞對來(lái)自激活的T細胞的信號做出反應——被激活并進(jìn)行分化和繁殖，分泌出抗體蛋白；抗體纏住、中立并毀滅這些抗原，其他多余的T細胞和B細胞變?yōu)橛洃浖毎�。這樣反復循環(huán)若干代數將最終產(chǎn)生能夠消滅抗原的有效抗體。
免疫系統中B細胞的功能主要是產(chǎn)生抗體,抗體由氨基酸排列組成, 氨基酸的不同排列方式形成不同的抗體;而T細胞則主要實(shí)現免疫調節功能。
2.2人工免疫系統及人工免疫算法的基本步驟
人工免疫系統即根據生物免疫系統的運行機制構造的一種仿生系統。在構造人工免疫系統時(shí), 首先要構造的就是人工抗原和抗體,在人工免疫系統中, 一個(gè)抗體或抗原可以用一個(gè)字符串表示，生物抗體由氨基酸的不同排列組成，因此, 人工抗體（字符串）中的字符應相當于生物抗體中的氨基酸。為使人工免疫系統具有與生物免疫系統類(lèi)似的自我調節機制,可以用親和力來(lái)描述抗體和抗原之間的匹配程度，用濃度來(lái)描述每種抗體在整個(gè)抗體群中所占份額�？贵w和抗原之間的親和力反映了候選解和最優(yōu)解的接近程度, 也即反映候選解對約束條件和目標函數的滿(mǎn)足程度。對于親和力較大的抗體作為記憶細胞加以重點(diǎn)保留，又通過(guò)濃度調節來(lái)保持抗體的多樣性；再對經(jīng)過(guò)選擇的抗體群（通過(guò)親和力和濃度進(jìn)行促進(jìn)抑制得到的抗體群）進(jìn)行繁殖變異產(chǎn)生新的抗體群。不斷地循環(huán)，最終也將會(huì )找到滿(mǎn)足要求的最優(yōu)解。
步驟1：抗原識別——對實(shí)際問(wèn)題進(jìn)行抽象，產(chǎn)生目標函數和約束條件作為抗原。
步驟2：產(chǎn)生初始抗體——若抗原為新抗原，則隨機產(chǎn)生N個(gè)抗體構成初始抗體群，記憶庫為空集；若抗原為已經(jīng)出現的抗原，則從記憶庫中隨機選擇部分記憶細胞，以及隨機產(chǎn)生部分抗體構成規模為N的初始抗體群。
步驟3：親和力、濃度計算——親和力反映了候選解和最優(yōu)解的接近程度，濃度反應了候選解之間的相似性。
步驟4：記憶細胞更新——與抗原有最大親和力的抗體加給記憶細胞。 由于記憶細胞數目有限，新產(chǎn)生的具有更高親和力的抗體替換較低親和力的抗體。
步驟5：終止條件——當達到給定代數或已經(jīng)連續幾代都沒(méi)能找到更好的解則終止，否則轉到步驟（6）重復執行。
步驟6：抗體的促進(jìn)和抑制——高親和力抗體受到促進(jìn)，高濃度抗體受到抑制。通常通過(guò)計算抗體成活的期望值來(lái)實(shí)施。
步驟7：產(chǎn)生新抗體群——通過(guò)人工免疫算子產(chǎn)生多種抗體，再加上記憶細胞中的抗體代替原抗體群，形成下一代抗體群。
3.旅行商問(wèn)題的人工免疫算法
3.1 旅行商問(wèn)題的人工免疫算法的基本步驟:
人工免疫算法的映射關(guān)系:抗原對應為遍歷各城市的最短路徑；抗體對應為一條遍歷路徑；親和力對應為抗體所決定的路徑與抗原的最短路徑的匹配程度。算法的基本步驟:
步驟1:隨機生成一個(gè)規模為N的初始抗體群path。
步驟2:計算抗體群path中的每個(gè)抗體的親和力Affi和濃度density。
步驟3:選擇親和力較高的抗體生成記憶細胞群體MemoryLab，其規模為N1。
步驟4:依據親和力和濃度對路徑path中各個(gè)抗體的進(jìn)行選擇并繁殖,得新抗體群path2。親和力越高、濃度越低則繁殖越多;反之, 則繁殖越少。
步驟5:通過(guò)人工免疫算子對抗體群path2進(jìn)行變異等操作,得到抗體群path3。親和力越低則變異率越高;親和力越高則變異率越低。
步驟6: 將path3 并入path, 計算抗體群path中的每個(gè)抗體對抗原的親和力。刪除親和力低的和重復的抗體,使群體總規模保持為N。
步驟7: 重復執行步驟2到步驟7,直到循環(huán)次數達到設定值或經(jīng)過(guò)若干次循環(huán)仍沒(méi)有找到更優(yōu)解。
3.2 抗體的編碼以及初始抗體群體的產(chǎn)生：
抗體的編碼方式模擬了生物抗體的蛋白質(zhì)結構, 把每個(gè)城市看成是一個(gè)氨基酸分子, 將城市之間的邊看作是連接氨基酸分子的肽鍵。一條遍歷n個(gè)城市的路徑則相當于一條包含n個(gè)不同氨基酸分子的肽鏈。
抗體按所走城市的順序進(jìn)行編碼, 每一個(gè)抗體編碼字符串形如: (C1, C2 ,…,Ci ,…,Cn )其中Ci 表示遍歷城市的編號。一個(gè)字符串抗體只能代表一個(gè)候選解,但一個(gè)候選解允許有一個(gè)以上的字符串抗體相對應。在確定抗體的編碼方式時(shí), 應盡量使字符串抗體和候選解之間形成一一對應的關(guān)系, 以縮小抗體空間、提高搜索效率�？筛鶕⺄SP問(wèn)題有每個(gè)城市有且只能訪(fǎng)問(wèn)一次和任意的Ci不等于Cj的約束條件。另外對于有n 個(gè)城市的旅行商問(wèn)題,從其中的一個(gè)城市出發(fā),遍歷其余(n-1)個(gè)城市且每個(gè)城市只去一次的路徑有(n-1) ! /2條。 對這n個(gè)城市編號,其號碼分別為1, 2, 3,…, n；并且把商人出發(fā)城市編為第1號,其它城市可以隨意編號,把這n個(gè)城市的編號任意排列成一個(gè)長(cháng)度為n的字符串都可以形成一個(gè)抗體。 因此抗體空間含有n! 個(gè)抗體,而解空間含有(n-1) ! /2個(gè)可行解。這n ! 個(gè)抗體只代表(n-1)! /2個(gè)可行解。 因此免疫算法要在抗體空間中搜索到與抗原匹配的抗體,比在解空間中搜索到最優(yōu)解更難。
基于抗體的編碼，初始抗體群的產(chǎn)生一般都是隨機的產(chǎn)生，這樣是為了能夠增加整個(gè)抗體群體的多樣性。
3.3 親和力計算免疫系統通過(guò)識別在抗原和抗體之間的獨特型或者抗體和抗體之間的獨特型產(chǎn)生多種抗體，抗原和抗體之間結合強度一般用親和力來(lái)估計——抗原與抗體之間親和力越大，抗原與抗體之間的匹配越好。
免疫算法中的難點(diǎn)之一就是親和力計算。親和力函數的設計往往在很大程度上決定算法的優(yōu)劣性。對TSP問(wèn)題來(lái)說(shuō),常見(jiàn)的親和力定義方法是取抗體所對應的路徑長(cháng)度的倒數。
對應的路徑長(cháng)度通常為較大的正數, 致使親和力通常變得很小,且密集分布于一個(gè)狹窄區間內, 不利于體現抗體的優(yōu)劣。另一方面,該方法沒(méi)有體現抗體與抗原之間的聯(lián)系。為此可進(jìn)一步對其進(jìn)行改進(jìn)，得親和力得定義為:
A（k）= L /L(k)其中L為抗原對應的旅行商路線(xiàn)的總長(cháng)度,即TSP問(wèn)題的最短路徑。但我們往往不知道最短路徑是多長(cháng)，否則也沒(méi)必要進(jìn)行搜索。為此可以把L設為當前抗體群中的抗體的最短路徑，但這往往使親和力保持較高，并且也聚集在一個(gè)較短的空間范圍內（但較簡(jiǎn)簡(jiǎn)單單的取路徑的倒數有較大的改進(jìn)）這為如何實(shí)現抗體的促進(jìn)和抑制帶來(lái)一定的難度，為此必須為抗體被擴增數進(jìn)行相應的設計，見(jiàn)3.4。
3.4 抗體濃度抗體的濃度用于調節抗體的規模，基于濃度的選擇機制，既促進(jìn)親和力高的抗體，又可抑制濃度高的抗體，從而保證了算法的收斂性及抗體群體的多樣性。濃度函數的定義和定義抗體親和力的定義一樣，對算法的優(yōu)劣性也同樣具有非常的地位�？蓪⒖贵w濃度函數定義如下式:其中, n 為抗體數量，s (abi , abj )表示抗體間的相似性�？贵w的濃度表示與其相似的抗體占整個(gè)群體的比例。判斷抗體間的相似性有多種方法。
一種是基于信息熵的判斷方法，通過(guò)這種方法能夠較容易地與生物免疫系統中的抗體對應，更能夠客觀(guān)地反應其含義。根據抗體群平均信息熵的概念計算抗體濃度的方法可知，抗體群的所有抗體在同一基因座上的等位基因各不相同時(shí)，抗體群的平均信息熵最大，抗體的相似性最��；反之，相似性較大。但是，在優(yōu)化計算中，這種利用信息熵的概念計算抗體濃度的方法存在一定得問(wèn)題，例如抗體A=（1，2，3，4，5）與抗體B=(2，3，4，5，1)之間的信息熵較大，但其卻對應同一條路徑。
其中D( abi , abj )表示抗體abi和abj的歐基里德距離, T為預設的指定閾值。這種算法也同樣具有基于信息熵的判斷方法的缺點(diǎn)，但該判斷方法相對簡(jiǎn)單。
在此提出一種求解濃度的方法：首先，對某一個(gè)具體的抗體ab先從抗體群中尋找和其親和力相近的抗體abk（可以將兩親和力作差，求絕對值，絕對值小于某一閾值暫且將其認為是相似抗體，以待作進(jìn)一步篩選）。其次，拿這個(gè)具體抗體ab和從第一步搜尋到的其他抗體abk作比較——先從抗體ab（字符串）的第一個(gè)字符char1到抗體abk中尋找相同的字符char1，將抗體abk中的字符char1左兩個(gè)右兩個(gè)字符存入一個(gè)數組a中，同時(shí)也將抗體ab（字符串）的第一個(gè)字符char1左兩個(gè)右兩個(gè)字符存入另一個(gè)數組b中（字符串第一個(gè)字母的左兩個(gè)字符為該字符串的的最后兩個(gè)字符，同時(shí)最后一個(gè)字符的右兩個(gè)字符為該字符串的前兩個(gè)，字符串第二個(gè)字母的選擇同理），判斷兩數組a和b中有幾個(gè)相同的字符；再從第一個(gè)抗體ab中的第二個(gè)字符char2到第二個(gè)抗體abk中去找，得相同數，依次類(lèi)推，將總的相同數相加作為該抗體的相似性數k。最后基于前兩步對所有抗體求得相似性數ki，定義第i個(gè)抗體abi的抗體濃度為： ? =ki / sum?ki ?。
3.5 抗體促進(jìn)和抑制
將抗體群中的抗體根據其親和力大小按升序排列, 得到: {ab1 ,ab2 , …, abn }, 且A(i)<A(i+1), i = 1, 2, …,n-1。從抗體群中選擇親和力較大的m個(gè)抗體進(jìn)行擴增。但擴增的數量受親和力刺激的同時(shí)還要受濃度的調節。高親和力、低濃度的抗體擴增數多；低親和力、高濃度的抗體擴增數少。
3.6 人工免疫
算子為了能對未知抗原產(chǎn)生免疫應答,可通過(guò)免疫算子來(lái)產(chǎn)生新的抗體。在生物免疫系統中新抗體一般是通過(guò)變異得到的，但為了進(jìn)一步提高免疫算子的多樣性我們可引入遺傳算法中的交叉操作算子�，F對部分人工免疫算子作一些簡(jiǎn)要的介紹：
�。�1） 字符換位算子：字符換位操作即是對抗體A，隨機取兩個(gè)正整數i,j，以一定的概率交換抗體A中一對字符ci,cj的位置。
�。�2） 字符串移位算子：字符串移位操作是從抗體A中隨機取出一個(gè)字符子串A1, 以一定的概率依次往左（或往右）移動(dòng)字符串A1中的各個(gè)字符, 最左（或最右）邊的一個(gè)字符則移動(dòng)到最右(或最左)邊的位置。
�。�3） 字符串逆轉算子：字符串逆轉操作是對抗體A中隨機取出一個(gè)子字符串，以一定的概率將其首尾倒置。
�。�4） 字符串重組算子：字符串重組操作是在抗體A中隨機取一個(gè)子字符串A1，以一定的概率使字符串A1中字符重新排列。重新排列的目的是提高抗體的親和力，具體方法與所求解的問(wèn)題有關(guān)。
�。�5） 優(yōu)質(zhì)串保留算子：如果若干個(gè)抗體與抗原之間的親和力都很大, 且這些抗體包含了一個(gè)相同的子字符串, 則稱(chēng)這個(gè)子字符串為優(yōu)質(zhì)字符串, 簡(jiǎn)稱(chēng)優(yōu)質(zhì)串。如果抗體中存在優(yōu)質(zhì)串, 則在抗體產(chǎn)生過(guò)程中以一定概率使該優(yōu)質(zhì)串不受破壞。
�。�6） 新抗體引人算子：若抗體群中的抗體失去了多樣性, 則可以產(chǎn)生新的抗體替換掉其中的一部分,以保持抗體群中抗體的多樣性。新抗體引人操作是當抗體群中有k個(gè)抗體相同時(shí), 對其中的（k-1）個(gè)抗體以一定概率用新產(chǎn)生的抗體替換。
�。�7） 有序交叉算子：隨機取兩個(gè)正整數i,j，兩后代現分別按對應位置復制雙親X1、X2匹配段中的兩個(gè)子串A1、A2，在對應位置交換雙親匹配段以外的城市，如果交換后，后代X1中的某一城市a與子串A1中的城市重復，則將該城市取代子串A2中的城市a具有相同位置的城市，直到與子串A1中的城市均不重復為止，對后代X2也采用相同的方法。
4. 應用實(shí)驗研究
為了驗證人工免疫算法的的有效性，本文針對從TSPLIB中摘取的Swiss42的TSP數據運用人工免疫算法對其用MATLAB進(jìn)行多次應用實(shí)驗。對抗體群規模N=50，記憶細胞的規模N1=20，交叉概率Pc=0.9，變異概率Pm=0.05，參數因子? =5，? =5，? =0.1，總的循環(huán)代數Tc=1000，進(jìn)行了多次計算，每次計算隨機產(chǎn)生不同的初始抗體。計算結果如表1所示，搜索到最優(yōu)路徑的情況。
實(shí)驗結果表明本文提出的旅行商問(wèn)題的人工免疫算法能夠有效地搜索到最優(yōu)值，其中的一些參數調節也能夠較有效的改變搜索能力和收斂速度，但從上面的一些數據可知本文提出的算法仍有一些不足之處，如怎樣選擇最佳參數等。
5.結語(yǔ)
本文提出了一種基于人工免疫理論的基本算法來(lái)求解旅行商問(wèn)題。免疫算法通過(guò)抗體與抗原間的親和力以及抗體與抗體之間的濃度來(lái)保留優(yōu)質(zhì)抗體和保持抗體群種的多樣性。
對高親和力、低濃度的抗體進(jìn)行促進(jìn)；對低親和力、高濃度的抗體進(jìn)行抑制，并加大變異程度。由其獨特的特征，在優(yōu)化問(wèn)題規模不大、搜索空間較小的情況下防止算法陷入局部最優(yōu)，具有更強的全局搜索能力，但對更大規模的優(yōu)化問(wèn)題時(shí)有收斂速度較慢等不足，由此產(chǎn)生了各種各樣的改進(jìn)版的人工免疫算法，如結合遺傳算法等其他算法的混合式算法，這些都為對人工免疫算法的研究帶來(lái)了廣闊的前景。
本碩士論文來(lái)源于中國碩士論文網(wǎng)，參考文獻：http://www.lunwenad.com/wzlb-6.html，轉載敬請保留鏈接，謝謝。
【研究人工免疫算法中旅行商問(wèn)題】相關(guān)文章：
大學(xué)課程表問(wèn)題中的算法研究與應用03-01
基于Memetic算法的客運站到發(fā)線(xiàn)分配問(wèn)題研究03-07
計數查找算法的研究11-22
LDPC碼譯碼算法研究03-07
紅外圖像增強算法研究03-07
指紋識別算法研究03-08
FFT算法的研究與DSP實(shí)現03-07
iLBC語(yǔ)音算法的初步研究03-07