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