遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，它最初由美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出來(lái)的，并出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個(gè)名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡(jiǎn)單遺傳算法（SGA）。
遺傳算法定義
遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過(guò)基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼（decoding），可以作為問(wèn)題近似最優(yōu)解。
遺傳算法特點(diǎn)
遺傳算法是解決搜索問(wèn)題的一種通用算法，對(duì)于各種通用問(wèn)題都可以使用。搜索算法的共同特征為：
① 首先組成一組候選解；
② 依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度；
③ 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；
④ 對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。
在遺傳算法中，上述幾個(gè)特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測(cè)性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來(lái)。
遺傳算法還具有以下幾方面的特點(diǎn)：
(1)遺傳算法從問(wèn)題解的串集開始嫂索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。
(2)許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。
(3)遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。
(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。
(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，硬度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。
遺傳算法的應(yīng)用
由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計(jì)算是不依賴于梯度信息或其它輔助知識(shí)，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于許多科學(xué)，下面我們將介紹遺傳算法的一些主要應(yīng)用領(lǐng)域：
1、 函數(shù)優(yōu)化。
函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測(cè)試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。
2、 組合優(yōu)化
隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算上用枚舉法很難求出最優(yōu)解。對(duì)這類復(fù)雜的問(wèn)題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP問(wèn)題非常有效。例如遺傳算法已經(jīng)在求解旅行商問(wèn)題、 背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等方面得到成功的應(yīng)用。
此外，GA也在生產(chǎn)調(diào)度問(wèn)題、自動(dòng)控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等方面獲得了廣泛的運(yùn)用。
遺傳算法的現(xiàn)狀
進(jìn)入90年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時(shí)產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無(wú)疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。
隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來(lái)離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對(duì)于解決人工智能中知識(shí)獲取和知識(shí)優(yōu)化精煉的瓶頸難題帶來(lái)了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開拓21世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個(gè)稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對(duì)象，而遺傳算法在這方面將會(huì)發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計(jì)算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來(lái)的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。
1991年D.Whitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子（Adjacency based crossover），這個(gè)算子是特別針對(duì)用序號(hào)表示基因的個(gè)體的交叉，并將其應(yīng)用到了TSP問(wèn)題中，通過(guò)實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證。
D.H.Ackley等提出了隨即迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由m個(gè)“投票者”來(lái)共同決定新個(gè)體的值（m表示群體的大小）。實(shí)驗(yàn)結(jié)果表明，SIGH與單點(diǎn)交叉、均勻交叉的神經(jīng)遺傳算法相比，所測(cè)試的六個(gè)函數(shù)中有四個(gè)表現(xiàn)出更好的性能，而且總體來(lái)講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競(jìng)爭(zhēng)力。
H.Bersini和G.Seront將遺傳算法與單一方法（simplex method）結(jié)合起來(lái)，形成了一種叫單一操作的多親交叉算子（simplex crossover），該算子在根據(jù)兩個(gè)母體以及一個(gè)額外的個(gè)體產(chǎn)生新個(gè)體，事實(shí)上他的交叉結(jié)果與對(duì)三個(gè)個(gè)體用選舉交叉產(chǎn)生的結(jié)果一致。同時(shí)，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個(gè)有更好的性能。
國(guó)內(nèi)也有不少的專家和學(xué)者對(duì)遺傳算法的交叉算子進(jìn)行改進(jìn)。2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對(duì)不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來(lái)搜索變量空間，并利用種群間遷移算子來(lái)進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問(wèn)題
2004年，趙宏立等針對(duì)簡(jiǎn)單遺傳算法在較大規(guī)模組合優(yōu)化問(wèn)題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識(shí)別出可能的基因塊，然后用基因塊作為新的基因單位對(duì)染色體重新編碼，產(chǎn)生長(zhǎng)度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
2005年，江雷等針對(duì)并行遺傳算法求解TSP問(wèn)題,探討了使用彈性策略來(lái)維持群體的多樣性,使得算法跨過(guò)局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。
遺傳算法的一般算法
遺傳算法是基于生物學(xué)的，理解或編程都不太難。下面是遺傳算法的一般算法：
創(chuàng)建一個(gè)隨機(jī)的初始狀態(tài)
初始種群是從解中隨機(jī)選擇出來(lái)的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號(hào)人工智能系統(tǒng)的情況不一樣，在那里問(wèn)題的初始狀態(tài)已經(jīng)給定了。
評(píng)估適應(yīng)度
對(duì)每一個(gè)解(染色體)指定一個(gè)適應(yīng)度的值，根據(jù)問(wèn)題求解的實(shí)際接近程度來(lái)指定(以便逼近求解問(wèn)題的答案)。不要把這些“解”與問(wèn)題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特性。
繁殖(包括子代突變)
帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代(后代產(chǎn)生后也將發(fā)生突變)。后代是父母的產(chǎn)物，他們由來(lái)自父母的基因結(jié)合而成，這個(gè)過(guò)程被稱為“雜交”。
下一代
如果新的一代包含一個(gè)解，能產(chǎn)生一個(gè)充分接近或等于期望答案的輸出，那么問(wèn)題就已經(jīng)解決了。如果情況并非如此，新的一代將重復(fù)他們父母所進(jìn)行的繁衍過(guò)程，一代一代演化下去，直到達(dá)到期望的解為止。
并行計(jì)算
非常容易將遺傳算法用到并行計(jì)算和群集環(huán)境中。一種方法是直接把每個(gè)節(jié)點(diǎn)當(dāng)成一個(gè)并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)。另一種方法是“農(nóng)場(chǎng)主/勞工”體系結(jié)構(gòu)，指定一個(gè)節(jié)點(diǎn)為“農(nóng)場(chǎng)主”節(jié)點(diǎn)，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評(píng)估。
術(shù)語(yǔ)說(shuō)明
由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識(shí)，下面是我們將會(huì)用來(lái)的一些術(shù)語(yǔ)說(shuō)明：
一、染色體(Chronmosome)
染色體又可以叫做基因型個(gè)體(individuals),一定數(shù)量的個(gè)體組成了群體(population),群體中個(gè)體的數(shù)量叫做群體大小。
二、基因(Gene)
基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alletes)。
三、基因地點(diǎn)(Locus)
基因地點(diǎn)在算法中表示一個(gè)基因在串中的位置稱為基因位置(Gene Position)，有時(shí)也簡(jiǎn)稱基因位?；蛭恢糜纱淖笙蛴矣?jì)算，例如在串 S＝1101 中，0的基因位置是3。
四、基因特征值(Gene Feature)
在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。
五、適應(yīng)度(Fitness)
各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù). 這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。
遺傳算法的運(yùn)算過(guò)程
選擇(復(fù)制)：
根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下 一代群體P(t+1)中；
交叉：
將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一對(duì)個(gè)體，以某個(gè)概率(稱為交叉概率）交換它們之間的部分染色體；
變異：
對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率)改變某一個(gè)或某一些基因座上的基因值為其他基因值。
1.2 遺傳算法的原理
遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解。
一、遺傳算法的目的
典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題：
考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
給定目標(biāo)函數(shù)f，有f(bi)，并且
0<f(bi)<∞
同時(shí)
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明顯，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串bi處，即求出最優(yōu)解。
二、遺傳算法的基本原理
長(zhǎng)度為L(zhǎng)的n個(gè)二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語(yǔ)，對(duì)群體執(zhí)行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential reproduction)。
2．交叉(Crossover)
這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。
3．變異(Mutation)
這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。
遺傳算法的原理可以簡(jiǎn)要給出如下：
choose an intial population
determine the fitness of each individual
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each individual
perform selection
until some stopping criterion applies
這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。
三、遺傳算法的步驟和意義
1．初始化
選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合bi，i=1，2，...n。這個(gè)初始的群體也就是問(wèn)題假設(shè)解的集合。一般取n＝30-160。
通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合bi,i＝1，2，...n。問(wèn)題的最優(yōu)解將通過(guò)這些初始假設(shè)解進(jìn)化而求出。
2．選擇
根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。
給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度。以
(3-86)
為選中bi為下一代個(gè)體的次數(shù)。
顯然．從式(3—86)可知：
(1)適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。
(2)適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。
這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。
3．交叉
對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。
例如有個(gè)體
S1=100101
S2=010111
選擇它們的左邊3位進(jìn)行交叉操作，則有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值為0.25—0.75。
4．變異
根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。
例如有個(gè)體S＝101011。
對(duì)其的第1，4位置的基因進(jìn)行變異，則有
S'=001111
單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。
5．全局最優(yōu)收斂(Convergence to the global optimum)
當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過(guò)程收斂、算法結(jié)束。否則，用經(jīng)過(guò)選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。
圖3—7中表示了遺傳算法的執(zhí)行過(guò)程。
圖3-7 遺傳算法原理
1.3 遺傳算法的應(yīng)用
遺傳算法在很多領(lǐng)域都得到應(yīng)用；從神經(jīng)網(wǎng)絡(luò)研究的角度上考慮，最關(guān)心的是遺傳算法在神經(jīng)網(wǎng)絡(luò)的應(yīng)用。在遺傳算法應(yīng)用中，應(yīng)先明確其特點(diǎn)和關(guān)鍵問(wèn)題，才能對(duì)這種算法深入了解，靈活應(yīng)用，以及進(jìn)一步研究開發(fā)。
一、遺傳算法的特點(diǎn)
1．遺傳算法從問(wèn)題解的中集開始嫂索，而不是從單個(gè)解開始。
這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，復(fù)蓋面大，利于全局擇優(yōu)。
2．遺傳算法求解時(shí)使用特定問(wèn)題的信息極少，容易形成通用算法程序。
由于遺傳算法使用適應(yīng)值這一信息進(jìn)行搜索，并不需要問(wèn)題導(dǎo)數(shù)等與問(wèn)題直接相關(guān)的信息。遺傳算法只需適應(yīng)值和串編碼等通用信息，故幾乎可處理任何問(wèn)題。
3．遺傳算法有極強(qiáng)的容錯(cuò)能力
遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息；通過(guò)選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串；這是一個(gè)強(qiáng)烈的濾波過(guò)程；并且是一個(gè)并行濾波機(jī)制。故而，遺傳算法有很高的容錯(cuò)能力。
4．遺傳算法中的選擇、交叉和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。
這說(shuō)明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的復(fù)蓋。
5．遺傳算法具有隱含的并行性
遺傳算法的基礎(chǔ)理論是圖式定理。它的有關(guān)內(nèi)容如下：
(1)圖式(Schema)概念
一個(gè)基因串用符號(hào)集{0，1，*}表示，則稱為一個(gè)因式；其中*可以是0或1。例如：H=1x x 0 x x是一個(gè)圖式。
(2)圖式的階和長(zhǎng)度
圖式中0和1的個(gè)數(shù)稱為圖式的階，并用0(H)表示。圖式中第1位數(shù)字和最后位數(shù)字間的距離稱為圖式的長(zhǎng)度，并用δ(H)表示。對(duì)于圖式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
(3)Holland圖式定理
低階，短長(zhǎng)度的圖式在群體遺傳過(guò)程中將會(huì)按指數(shù)規(guī)律增加。當(dāng)群體的大小為n時(shí)，每代處理的圖式數(shù)目為0(n3)。
遺傳算法這種處理能力稱為隱含并行性(Implicit Parallelism)。它說(shuō)明遺傳算法其內(nèi)在具有并行處理的特質(zhì)。
二、遺傳算法的應(yīng)用關(guān)鍵
遺傳算法在應(yīng)用中最關(guān)鍵的問(wèn)題有如下3個(gè)
1．串的編碼方式
這本質(zhì)是問(wèn)題編碼。一般把問(wèn)題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長(zhǎng)度及編碼形式對(duì)算法收斂影響極大。
2．適應(yīng)函數(shù)的確定
適應(yīng)函數(shù)(fitness function)也稱對(duì)象函數(shù)(object function)，這是問(wèn)題求解品質(zhì)的測(cè)量函數(shù)；往往也稱為問(wèn)題的“環(huán)境”。一般可以把問(wèn)題的模型函數(shù)作為對(duì)象函數(shù)；但有時(shí)需要另行構(gòu)造。
3．遺傳算法自身參數(shù)設(shè)定
遺傳算法自身參數(shù)有3個(gè)，即群體大小n、交叉概率Pc和變異概率Pm。
群體大小n太小時(shí)難以求出最優(yōu)解，太大則增長(zhǎng)收斂時(shí)間。一般n＝30-160。交叉概率Pc太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)。一般取Pc=0.25-0.75。變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。一般取Pm＝0．01—0．2。
三、遺傳算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用
遺傳算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用主要反映在3個(gè)方面：網(wǎng)絡(luò)的學(xué)習(xí)，網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)，網(wǎng)絡(luò)的分析。
1．遺傳算法在網(wǎng)絡(luò)學(xué)習(xí)中的應(yīng)用
在神經(jīng)網(wǎng)絡(luò)中，遺傳算法可用于網(wǎng)絡(luò)的學(xué)習(xí)。這時(shí)，它在兩個(gè)方面起作用
(1)學(xué)習(xí)規(guī)則的優(yōu)化
用遺傳算法對(duì)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)規(guī)則實(shí)現(xiàn)自動(dòng)優(yōu)化，從而提高學(xué)習(xí)速率。
(2)網(wǎng)絡(luò)權(quán)系數(shù)的優(yōu)化
用遺傳算法的全局優(yōu)化及隱含并行性的特點(diǎn)提高權(quán)系數(shù)優(yōu)化速度。
2．遺傳算法在網(wǎng)絡(luò)設(shè)計(jì)中的應(yīng)用
用遺傳算法設(shè)計(jì)一個(gè)優(yōu)秀的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，首先是要解決網(wǎng)絡(luò)結(jié)構(gòu)的編碼問(wèn)題；然后才能以選擇、交叉、變異操作得出最優(yōu)結(jié)構(gòu)。編碼方法主要有下列3種：
(1)直接編碼法
這是把神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)直接用二進(jìn)制串表示，在遺傳算法中，“染色體”實(shí)質(zhì)上和神經(jīng)網(wǎng)絡(luò)是一種映射關(guān)系。通過(guò)對(duì)“染色體”的優(yōu)化就實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)的優(yōu)化。
(2)參數(shù)化編碼法
參數(shù)化編碼采用的編碼較為抽象，編碼包括網(wǎng)絡(luò)層數(shù)、每層神經(jīng)元數(shù)、各層互連方式等信息。一般對(duì)進(jìn)化后的優(yōu)化“染色體”進(jìn)行分析，然后產(chǎn)生網(wǎng)絡(luò)的結(jié)構(gòu)。
(3)繁衍生長(zhǎng)法
這種方法不是在“染色體”中直接編碼神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，而是把一些簡(jiǎn)單的生長(zhǎng)語(yǔ)法規(guī)則編碼入“染色體”中；然后，由遺傳算法對(duì)這些生長(zhǎng)語(yǔ)法規(guī)則不斷進(jìn)行改變，最后生成適合所解的問(wèn)題的神經(jīng)網(wǎng)絡(luò)。這種方法與自然界生物地生長(zhǎng)進(jìn)化相一致。
3．遺傳算法在網(wǎng)絡(luò)分析中的應(yīng)用
遺傳算法可用于分析神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)由于有分布存儲(chǔ)等特點(diǎn)，一般難以從其拓?fù)浣Y(jié)構(gòu)直接理解其功能。遺傳算法可對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行功能分析，性質(zhì)分析，狀態(tài)分析。
遺傳算法雖然可以在多種領(lǐng)域都有實(shí)際應(yīng)用，并且也展示了它潛力和寬廣前景；但是，遺傳算法還有大量的問(wèn)題需要研究，目前也還有各種不足。首先，在變量多，取值范圍大或無(wú)給定范圍時(shí)，收斂速度下降；其次，可找到最優(yōu)解附近，但無(wú)法精確確定最擾解位置；最后，遺傳算法的參數(shù)選擇尚未有定量方法。對(duì)遺傳算法，還需要進(jìn)一步研究其數(shù)學(xué)基礎(chǔ)理論；還需要在理論上證明它與其它優(yōu)化技術(shù)的優(yōu)劣及原因；還需研究硬件化的遺傳算法；以及遺傳算法的通用編程和形式等
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
