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

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

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

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

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

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

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