用免疫算法求解tsp問題

《用免疫算法求解tsp問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、用免疫算法求解TSP問題1．免疫算法的生物學(xué)基礎(chǔ)免疫系統(tǒng)是哺乳動物抵御外來有害物質(zhì)侵害的防御系統(tǒng)，動物一生始終處于復(fù)雜多變的、充滿傷害的自然環(huán)境中，能夠平安無事、進行正常的生命活動，免疫系統(tǒng)在其中起著重要的作用。免疫是生物體的特異性生理反應(yīng),由具有免疫功能的器官、組織、細胞、免疫效應(yīng)分子及基因等組成。免疫系統(tǒng)通過分布在全身的不同種類的淋巴細胞識別和清除侵入生物體的抗原性異物。當(dāng)生物系統(tǒng)受到外界病毒侵害時,便激活自身的免疫系統(tǒng),其目標是盡可能保證整個生物系統(tǒng)的基本生理功能得到正常運轉(zhuǎn)。免疫功能主要是通過分布全身的免疫細胞來實現(xiàn)

2、的，免疫細胞主要有巨噬細胞、抗體及淋巴細胞等。其中淋巴細胞主要有B細胞和T細胞兩種類型，它們是免疫反應(yīng)中的主要作用細胞根據(jù)Burnet的細胞克隆選擇學(xué)說和Jerne免疫網(wǎng)絡(luò)學(xué)說：生物體內(nèi)先天具有針對不同抗原特性的多樣性B細胞克隆，抗原侵入機體后，在T細胞的識別和控制下，選擇并刺激相應(yīng)的B細胞系，使之活化、增殖并產(chǎn)生特異性抗體結(jié)合抗原：同時，抗原與抗體、抗體與抗體之間刺激和抑制關(guān)系形成的網(wǎng)絡(luò)調(diào)節(jié)結(jié)構(gòu)維持著免疫平衡。圖I所示為免疫系統(tǒng)的反應(yīng)過程的一種抽象描述。當(dāng)人工免疫系統(tǒng)受到外界攻擊時,內(nèi)在的免疫機制被激活,其目標是保證整個智

3、能信息系統(tǒng)的基本信息處理功能正常運作。免疫系統(tǒng)以其有限的資源，能夠有效地應(yīng)付數(shù)量龐大得幾近無限的不同種類的病毒的侵害，這一特性無疑引起了人們特別的關(guān)注。在學(xué)科交叉性越來越大的今天，人們在從醫(yī)學(xué)的角度，分析和研究這一特性的同時，也希望能以此作為啟發(fā)，設(shè)計出新的具有突破性的應(yīng)用方法，以解決某些應(yīng)用領(lǐng)域中目前難以解決的難題，免疫算法正是這一思路的產(chǎn)物，是受生物免疫系統(tǒng)的啟示而設(shè)計出來的一種具有對多峰值函數(shù)進行多峰值搜索及全局尋優(yōu)能力的新型算法。2．免疫算法的提出在生命科學(xué)領(lǐng)域中，人們已經(jīng)對遺傳(Heredity)與免疫(Immun

4、ity)等自然現(xiàn)象進行了廣泛深入的研究。六十年代Bagley和Rosenberg等先驅(qū)在對這些研究成果進行分析與理解的基礎(chǔ)上，借鑒其相關(guān)內(nèi)容和知識，特別是遺傳學(xué)方面的理論與概念，并將其成功應(yīng)用于工程科學(xué)的某些領(lǐng)域，收到了良好的效果。時至八十年代中期，美國Michigan大學(xué)的Hollan教授不僅對以前的學(xué)者們提出的遺傳概念進行了總結(jié)與推廣，而且給出了簡明清晰的算法描述，并由此形成目前一般意義上的遺傳算法(GeneticAlgorithm)GA。由于遺傳算法較以往傳統(tǒng)的搜索算法具有使用方便、魯棒性強、便于并行處理等特點，因而廣

5、泛應(yīng)用于組合優(yōu)化、結(jié)構(gòu)設(shè)計、人工智能等領(lǐng)域。另一方面，F(xiàn)armer和Bersini等人也先后在不同時期、不同程度地涉及到了有關(guān)免疫的概念。遺傳算法是一種具有生成+檢測(generateandtest)的迭代過程的搜索算法。從理論上分析，迭代過程中，在保留上一代最佳個體的前提下，遺傳算法是全局收斂的。然而，在對算法的實施過程中不難發(fā)現(xiàn)兩個主要遺傳算子都是在一定發(fā)生概率的條件下，隨機地、沒有指導(dǎo)地迭代搜索，因此它們在為群體中的個體提供了進化機會的同時，也無可避免地產(chǎn)生了退化的可能。在某些情況下，這種退化現(xiàn)象還相當(dāng)明顯。另外，每一

6、個待求的實際問題都會有自身一些基本的、顯而易見的特征信息或知識。然而遺傳算法的交叉和變異算子卻相對固定，在求解問題時，可變的靈活程度較小。這無疑對算法的通用性是有益的，但卻忽視了問題的特征信息對求解問題時的輔助作用，特別是在求解一些復(fù)雜問題時，這種忽視所帶來的損失往往就比較明顯了。實踐也表明，僅僅使用遺傳算法或者以其為代表的進化算法，在模仿人類智能處理事物的能力方面還遠遠不足，還必須更加深層次地挖掘與利用人類的智能資源。從這一點講，學(xué)習(xí)生物智能、開發(fā)、進而利用生物智能是進化算法乃至智能計算的一個永恒的話題。所以，研究者力圖將

7、生命科學(xué)中的免疫概念引入到工程實踐領(lǐng)域，借助其中的有關(guān)知識與理論并將其與已有的一些智能算法有機地結(jié)合起來，以建立新的進化理論與算法，來提高算法的整體性能?；谶@一思想，將免疫概念及其理論應(yīng)用于遺傳算法，在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征信息或知識來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象，這種算法稱為免疫算法(ImmuneAlgorithm)IA。下面將會給出算法的具體步驟，證明其全局收斂性，提出免疫疫苗的選擇策略和免疫算子的構(gòu)造方法，理論分析和對TSP問題的仿真結(jié)果表明免疫算法不僅是有效的而且

8、也是可行的，并較好地解決了遺傳算法中的退化問題。3．免疫算法中涉及的術(shù)語簡介抗原：在生命科學(xué)中，是指能夠刺激和誘導(dǎo)機體的免疫系統(tǒng)使其產(chǎn)生免疫應(yīng)答，并能與相應(yīng)的免疫應(yīng)答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應(yīng)的物質(zhì)。在我們的算法中，是指所有可能錯誤的基因，即非最佳個體的基因。抗體：在生命科學(xué)中，是指免