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