生物啟發(fā)式算法及其改進研究.pdf

1、自然界一直是人類創(chuàng)造力的豐富源泉，人類認識事物的能力大部分都來源于與自然界的相互作用之中。自然界中的許多自適應優(yōu)化現(xiàn)象不斷給人以啟示:生物體和自然生態(tài)系統(tǒng)可以通過自身的演化就使許多在人類看起來極其復雜的優(yōu)化問題得到完美的解決。近些年來，一些與經典的數(shù)學規(guī)劃原理截然不同的、試圖通過模擬自然生態(tài)系統(tǒng)機制以求解復雜優(yōu)化問題的生物啟發(fā)式算法相繼出現(xiàn)(如進化算法、粒子群優(yōu)化算法、人工免疫算法、蟻群優(yōu)化算法等)，大大豐富了現(xiàn)代優(yōu)化技術，也為那些傳統(tǒng)

2、最優(yōu)化技術難以處理的NP難問題提供了切實可行的解決方案。因其高效的優(yōu)化性能，無需問題特殊信息等優(yōu)點，已廣泛應用于工程優(yōu)化設計、計算機科學、組合優(yōu)化、優(yōu)化調度等領域。因此生物啟發(fā)式算法也越來越受到眾多學者們的關注。本文主要研究了其中的進化算法、蟻群算法、粒子群算法和人工免疫算法。
　　 全文共分六章，第一章為緒論，主要介紹了生物啟發(fā)式算法的發(fā)展歷史，以及目前的一些發(fā)展現(xiàn)狀，并分別介紹了進化算法、蟻群算法、粒子群算法和免疫算法的產生

3、背景和發(fā)展現(xiàn)狀。并對本論文研究的主要內容和研究方法進行了簡單的介紹。
　　 第二章在介紹了進化算法的基本原理的基礎上，分別對遺傳算法、進化規(guī)劃、進化策略、遺傳編程的不同方面的特點進行了研究，然后從編碼策略，選擇方式，遺傳算子等在不同算法的操作過程中所具有的不同點與側重點，以及對性能可能帶來的影響進行了對比分析；最后討論了進化算法中兩種最主要的操作算子：變異操作算子和交叉操作算子各自的優(yōu)缺點。
　　 第三章首先介紹了蟻群算

4、法的基本原理，并介紹了旅行商問題——這一典型的組合優(yōu)化問題的特點。針對進化策略收斂速度快但容易陷入早熟收斂以及最大最小螞蟻系統(tǒng)求解能力強但收斂速度較慢的特點，將進化策略與最大最小螞蟻系統(tǒng)融合，利用最大最小螞蟻系統(tǒng)求出每一步迭代的最優(yōu)解，再對迭代出最優(yōu)解進行進化策略中的變異操作來加快解的收斂速度。最后將所提出的改進算法應用到中國旅行商問題(CTSP)的實際應用中，來驗證算法的優(yōu)越性。
　　 第四章介紹了粒子群算法的基本原理以及解決

5、旅行商問題的基本步驟，并針對基本粒子群算法易陷入局部極小值的缺點，分別將進化算法中的變異因子和模擬退火算法引入粒子群算法中，結合粒子群算法全局搜索能力強和模擬退火算法局部搜索能力強的優(yōu)點，提出了一種混合算法。最后將混合算法應用于解決中國旅行商問題中，并將實驗結果與基本的模擬退火算法、基本的粒子群算法以及帶有變異因子的粒子群算法進行了對比研究。
　　 第五章首先對人工免疫算法的起源，基本原理，以及解決實際優(yōu)化問題的基本步驟進行了介

6、紹，并著重介紹了基于信息熵和基于歐式距離的免疫算法。針對上述兩種免疫算法存在的不足，提出了一種基于新的濃度計算方法的改進人工免疫算法，最后將該算法應用在中國旅行商問題的求解中，并針對旅行商問題的實際特點提出了一種新的免疫疫苗的提取和注射的方法，通過對比實驗驗證了改進算法有著更高的求解效率。
　　 第六章對本論文的一些研究成果進行了歸納總結，并指出了目前生物啟發(fā)式算法的研究中還存在一些問題，最后對下一步研究的內容和方向進行了展望。