【文章內(nèi)容簡介】 群體內(nèi)部染色體的隨機信息交換機制相結(jié)合的全局搜索算法。經(jīng)過幾十年的發(fā)展，GA算法的研究日漸成熟。與傳統(tǒng)的優(yōu)化算法相比，GA具有如下優(yōu)點：①不是從單點，而是從多點開始搜索；②在搜索最優(yōu)解時，不受問題性質(zhì)(連續(xù)性、可微性)的限制只需由目標函數(shù)值轉(zhuǎn)換成適應(yīng)度即可；③搜索過程不易陷入局部最優(yōu)值。其基本思想是把GA待優(yōu)化的參數(shù)編碼成二進制位串形式，然后由若干個位串形成一個初始種群作為待求問題的候選解，使用選擇(select)、交叉(crossover)、變異(mutation)進行操作，不斷迭代優(yōu)化，直到找到最優(yōu)解。遺傳算法是模仿自然界生物進化論思想而得出的一種全局優(yōu)化算法。它對所優(yōu)化目標的經(jīng)驗知識要求甚少，一般只需要知道其數(shù)值關(guān)系即可。同時由于遺傳算法群體的多樣性，使其盡可能在全方向上搜索，達到全局最優(yōu)。 遺傳算法的歷史和發(fā)展Holland的早期工作主要集中于生物學，控制工程，人工智能等領(lǐng)域中的中一類動態(tài)系統(tǒng)的適應(yīng)性問題，其中適應(yīng)性概念在環(huán)境表現(xiàn)出較好行為和性能的系統(tǒng)結(jié)構(gòu)的漸進改變過程，簡稱系統(tǒng)的適應(yīng)過程。Holland認為：通過簡單的模擬機制可以描述復(fù)雜的適應(yīng)性現(xiàn)象。因此，Holland試圖建立適應(yīng)過程的一般描述模型，并在計算機上進行模擬試驗研究，分析自然系統(tǒng)或者人工系統(tǒng)對環(huán)境變化的適應(yīng)性現(xiàn)象，其中遺傳算法僅僅是一種具體的算法形式。Bremermann，De Jong等人則注重遺傳算法應(yīng)用于參數(shù)優(yōu)化問題，極大的促進了遺傳算法的應(yīng)用。所以，遺傳算法既是一種自然進化系統(tǒng)的計算模型，也是一種通用的求解優(yōu)化問題的適應(yīng)性搜索方法。1962年，John Holland在“Outline for a Logic Theory Adaptive Systems”一文中，提出了所謂的監(jiān)控程序的概念，即利用群體進化模擬適應(yīng)性系統(tǒng)的思想。在這篇文章中盡管它沒有給出實現(xiàn)這些思想的具體技術(shù)，但卻引進了群體，適應(yīng)值，選擇，交叉等基本概念。1966年，F(xiàn)ogel等人也提出了類似的思想，但是其重點是放在變異算子而不是采用交叉算子。1967年，其博士論文中首次提出了“遺傳算法”一詞。在20世紀60年代中期至70年代末期，基于自然進化的思想遭到了懷疑和反對。Holland及其數(shù)位博士堅持了這一方向的研究。1975年，Holland出版了專著《自然與人工系統(tǒng)中的適應(yīng)性行為》（Adaptation in Natural and Artificial Systems），該書系統(tǒng)的闡述了遺傳算法的基本理論和方法，提出了對遺傳算法和理論發(fā)展極為重要的模式理論，其中首次確認了選擇，交叉，變異等遺傳算子，以及遺傳算法的隱并行性，并將遺傳算法應(yīng)用于適應(yīng)性系統(tǒng)模擬，函數(shù)優(yōu)化，機器學習，自動控制等領(lǐng)域。1975年以后，遺傳算法作為函數(shù)優(yōu)化器不但在各個領(lǐng)域的得到了廣泛應(yīng)用，而且還豐富和發(fā)展了若干遺傳算法的基本理論。1980年，Bethke對函數(shù)優(yōu)化GA進行了研究，包括應(yīng)用研究和數(shù)學分析。Smith在1980年首次提出使用變長位串的概念。這在某種程度上為以后的遺傳規(guī)劃奠定了基礎(chǔ)。1989年，David Goldberg出版了《Genetic Algorithms in Search Optimization and Machine Learning》一書，這是第一本遺傳算法的教科書，它是對當時關(guān)于遺傳算法領(lǐng)域研究工作的全面而系統(tǒng)的總結(jié)，因而也成為引用最多的參考書之一。隨著遺傳算法研究和應(yīng)用的不斷深入與擴展，1985年，在美國召開了第一屆遺傳算法國際會議，即ICGA(International Conference on Genetic Algorithm)這次會議是遺傳算法發(fā)展的重要里程碑，此會以后每隔一年舉行一次。隨著Internet技術(shù)的發(fā)展和普及應(yīng)用，遺傳算法的有關(guān)研究單位建立了大量的專題網(wǎng)站，其中最為著名的是由美國海軍人工智能應(yīng)用研究中心建立的GA_Archives檢索網(wǎng)站，歷年來的公開發(fā)表的論文和報告，有關(guān)國際會議消息，典型應(yīng)用案例和程序的源代碼等。這些眾多的研究單位和頻繁的國際學術(shù)活動集中反映了遺傳算法的學術(shù)意義的應(yīng)用價值。目前，遺傳算法已經(jīng)成為一個多學科、多領(lǐng)域的重要研究方向。 遺傳算法的應(yīng)用領(lǐng)域遺傳算法作為一種有效的全局搜索方法，從產(chǎn)生至今不斷應(yīng)用領(lǐng)域，比如工程設(shè)計，制造業(yè)，人工智能，計算機科學，生物工程，自動控制，社會科學，商業(yè)和金融等，同時應(yīng)用實踐又促進了遺傳算法的發(fā)展和完善。比較成功的案例如下：（1）遺傳學習將遺傳算法用于知識獲取，構(gòu)成以遺傳算法為核心的機器學習系統(tǒng)，其中群體由一組產(chǎn)生規(guī)則組成。比較典型的適Holland設(shè)計的用于序列決策學習的分類器系統(tǒng)，以及機器人規(guī)劃，模式識別，概念學習。（2）自動控制領(lǐng)域遺傳算法適用于求解復(fù)雜的參數(shù)辨識問題。Maclay等人用遺傳算法求解電車模型參數(shù)辨識問題，取得了很好的效果；Karr采用遺傳算法設(shè)計自適應(yīng)模糊邏輯控制器，取得了顯著的效果；Freeman等人提出了應(yīng)用遺傳算法精調(diào)控制中的由人定義的模糊邏輯集合概念。另外，GA在故障診斷和機器人行走路徑中的應(yīng)用也取得了成功。（3）人工智能與計算機科學GA 在人工智能與計算機科學領(lǐng)域中的應(yīng)用包括：數(shù)據(jù)挖掘和知識獲取，數(shù)據(jù)庫優(yōu)化查詢，人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與參數(shù)優(yōu)化，模式識別，專家系統(tǒng)等。另外，很多專家學者將GA應(yīng)用于各自所從事的工程領(lǐng)域，比如VLSI設(shè)計，運輸規(guī)劃，設(shè)備布局，土木工程，生物工程等，對解決具體實踐問題起到了極大的促進作用。 遺傳學的概念串（string）：它是個體的形式，在算法中為二進制，并且對應(yīng)遺傳學中的染色體。群體（population）：個體的集合稱為群體，串是群體的元素。群體大?。╬opulation size）：在群體中個體的數(shù)量稱為群體的大小。基因（gene）：基因是串中的元素，基因用于表示個體的特征。例如有一個s=1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因?；蛭恢茫╣ene position）：一個基因在串中的位置稱為基因位置，有時也稱為基因位?；蛭恢糜纱淖笙蛴矣嬎?，例如在串s=1101中，0的基因位置是3?；蛭恢脤?yīng)于遺傳學中的地點?；蛱卣髦担╣ene feature）：在用串表示整數(shù)時，基因的特征值與二進制的權(quán)一致；例如在串s=1011中，基因位置3中的1，它的基因特征值是2?；蛭恢?中的1，它的基因特征值是8。串結(jié)構(gòu)空間ss：在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進行的。串結(jié)構(gòu)空間對應(yīng)于遺傳學中的基因型的集合。參數(shù)空間sp：這是串空間在物理系統(tǒng)中的映射，它對應(yīng)于遺傳學中的表現(xiàn)型的集合。非線性：它對應(yīng)遺傳學中的異位顯性。適應(yīng)度（fitness）：表示某一個體對于環(huán)境的適應(yīng)程度。遺傳算法(Genetic Algorithms GA)是以自然選擇和基因遺傳理論為基礎(chǔ)，將生物進化過程中的適者生存規(guī)則與群體內(nèi)部染色體的隨機信息交換機制相結(jié)合，在問題解空間內(nèi)進行全局并行、隨機的搜索，其結(jié)果是向全局最優(yōu)方向收斂。遺傳算法模仿生物進化的步驟，引入選擇，交叉，變異等算子[9]。繁殖是在父母代種群中將適應(yīng)度較高的個體選擇出來，根據(jù)適者生存原理，淘汰適應(yīng)度較低的個體，以優(yōu)化種群；交叉是從種群中隨機地抽取一對個體，并隨機地選擇一位交叉位進行交叉，生成新樣本，達到增大搜索空間的目的；變異是模仿生物的基因突變，為了防止繁殖和交叉丟失重要的遺傳信息；它對個體按位進行操作，以提高遺傳算法的搜索效率和全局搜索能力[10]。步驟一：參數(shù)編碼和解碼在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。一般把問題的各種參數(shù)用編碼構(gòu)成子串，然后把子串并接成染色體串。二進制編碼方法是遺傳算法中最常用的一種編碼方法。本文中采用的編碼方式就是二進制編碼。步驟二：適應(yīng)度函數(shù)的選擇適應(yīng)度函數(shù)表明個體對環(huán)境適應(yīng)能力的強弱，它與所選取的目標函數(shù)有關(guān)。本文采用了絕對誤差積分模型：J= () 定義適應(yīng)度函數(shù)f為:f== () 本文中應(yīng)用Simulink完成適應(yīng)度函數(shù)的選擇。步驟三：遺傳算法① 選擇(selection operator)遺傳算法使用選擇算子來對群體中的個體進行優(yōu)勝劣汰操作。在選擇時，以適應(yīng)度為選擇原則。適應(yīng)度準則體現(xiàn)了適者生存，不適應(yīng)者被淘汰的自然法則。適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大，適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小。最常用的選擇算子是基本遺傳算法中的比例選擇算子，本文采用的就是這種方法。其基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比例關(guān)系。設(shè)群體大小為，個體的適應(yīng)度為， （）從上式就可以看出：適應(yīng)度高的個體，繁殖下一代的數(shù)目比較多。適應(yīng)度低的個體，繁殖下一代的數(shù)目比較少，甚至被淘汰。這樣，就產(chǎn)生了對環(huán)境適應(yīng)能力比較強的后代。對于問題求解角度來講，就是選擇出和最優(yōu)解比較接近的中間解。② 交叉(crossover operator)對于選中用于繁殖下一代的個體，隨機的選擇兩個個體的相同位置，按交叉概率p。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。交叉時，可以執(zhí)行單點交叉和多點交叉。交叉算子是指對2個相互配對的染色體按某種方式相互交換其部分基因，從而形成2個新的個體。本文采用中間重組雙點交叉法，即在群體中隨機選取2個個體，并在個體編碼串中只隨機設(shè)置2個交叉點，然后在該點以一定的概率Pc相互交換2個配對個體的部分染色體。③ 變異(mutation operator)根據(jù)生物遺傳中的基因變異的原理，以變異概率pm對某些個體的某些位執(zhí)行變異。在變異時，對要執(zhí)行變異的位求反，就是把1變成0，把0變成1。變異概率pm與生物變異極小的情況一致，變異運算是指將個體染色體編碼串中某些基因座上的基因值用該基因座的其它等位基因來替換，形成一個新的個體。本文采用的變異操作是高位變異。，又可維持群體的多樣性，避免出現(xiàn)初期收斂問題，也就是說變異增加了全局優(yōu)化的可能性。④ 初始種群的產(chǎn)生為保證在整個解空間進行搜索，采用隨機產(chǎn)生初始種群。⑤ 遺傳操作迭代終止的條件遺傳算法在應(yīng)用中最關(guān)鍵的問題有如下3個：① 串的編碼方式：一般把問題的各種參數(shù)用二進制編碼構(gòu)成子串，然后把子串拼接成染色體串(串的長度及編碼形式對算法收斂影響很大)。② 適應(yīng)函數(shù)的確定：適應(yīng)函數(shù)也稱為對象函數(shù)，這是問題求解品質(zhì)的測量函數(shù)，往往也稱為問題的“環(huán)境” 。一般可以把問題的模型函數(shù)作為對象函數(shù)，但有時也需要另行構(gòu)造。③ 遺傳算法自身參數(shù)設(shè)定：遺傳算法自身參數(shù)有3個，即群體大小、交叉概率和變異概率。群體大小太小時難以求