遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它最初由美國Michigan大學(xué)J.Holland教授于1975年首先提出來的，并出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個(gè)名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳算法（SGA）。

 

基本概念　　遺傳算法（Genetic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。

　　對于一個(gè)求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同)，一般可以描述為下列數(shù)學(xué)規(guī)劃模型：

 

 

 

式中x為決策變量，式2-1為目標(biāo)函數(shù)式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。

　　遺傳算法的基本運(yùn)算過程如下：

　　a)初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。

　　b)個(gè)體評價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。

　　c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評估基礎(chǔ)上的。

　　d)交叉運(yùn)算；將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。

　　e)變異運(yùn)算：將變異算子作用于群體。即是對群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。

　　群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t 1)。

　　f)終止條件判斷:若t=T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。

 

 

 

　　遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（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)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。

 

遺傳算法特點(diǎn)　　遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為：

　　① 首先組成一組候選解

　　② 依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度

　　③ 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解

　　④ 對保留的候選解進(jìn)行某些操作，生成新的候選解。

　　在遺傳算法中，上述幾個(gè)特征以一種特殊的方式組合在一起：

 

 

 

基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。

　　遺傳算法還具有以下幾方面的特點(diǎn)：

　　(1)遺傳算法從問題解的串集開始搜索，而不是從單個(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è)體，即對搜索空間中的多個(gè)解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。

　　(3)遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。

　　(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。

　　(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時(shí)，適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

 

 

 

　　由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計(jì)算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于許多科學(xué)，下面我們將介紹遺傳算法的一些主要應(yīng)用領(lǐng)域：

　　函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價(jià)的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。

　　隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算上用枚舉法很難求出最優(yōu)解。對這類復(fù)雜的問題，人們已經(jīng)意識到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。

　　此外，GA也在生產(chǎn)調(diào)度問題、自動(dòng)控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等方面獲得了廣泛的運(yùn)用。

 

現(xiàn)狀　　進(jìn)入90年代，遺傳算法迎來了興盛發(fā)展時(shí)期，無論是理論研究還是應(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ā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。 　　隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個(gè)稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會(huì)發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計(jì)算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。 　　1991年D.Whitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子（Adjacency based crossover），這個(gè)算子是特別針對用序號表示基因的個(gè)體的交叉，并將其應(yīng)用到了TSP問題中，通過實(shí)驗(yàn)對其進(jìn)行了驗(yàn)證。 　　D.H.Ackley等提出了隨機(jī)迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由m個(gè)“投票者”來共同決定新個(gè)體的值（m表示群體的大?。?。實(shí)驗(yàn)結(jié)果表明，SIGH與單點(diǎn)交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個(gè)函數(shù)中有四個(gè)表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力。 　　H.Bersini和G.Seront將遺傳算法與單一方法（simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（simplex crossover），該算子在根據(jù)兩個(gè)母體以及一個(gè)額外的個(gè)體產(chǎn)生新個(gè)體，事實(shí)上他的交叉結(jié)果與對三個(gè)個(gè)體用選舉交叉產(chǎn)生的結(jié)果一致。同時(shí)，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個(gè)有更好的性能。 　　國內(nèi)也有不少的專家和學(xué)者對遺傳算法的交叉算子進(jìn)行改進(jìn)。2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題 　　2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。 　　2005年，江雷等針對并行遺傳算法求解TSP問題，探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙，向全局最優(yōu)解方向進(jìn)化。

 

 

一般算法　　遺傳算法是基于生物學(xué)的，理解或編程都不太難。下面是遺傳算法的一般算法：

建初始狀態(tài)

　　初始種群是從解中隨機(jī)選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智能系統(tǒng)的情況不一樣，在那里問題的初始狀態(tài)已經(jīng)給定了。

評估適應(yīng)度

　　對每一個(gè)解(染色體)指定一個(gè)適應(yīng)度的值，根據(jù)問題求解的實(shí)際接近程度來指定(以便逼近求解問題的答案)。不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特性。

繁殖

　　繁殖(包括子代突變) 　　帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代(后代產(chǎn)生后也將發(fā)生突變)。后代是父母的產(chǎn)物，他們由來自父母的基因結(jié)合而成，這個(gè)過程被稱為“雜交”。

下一代

　　如果新的一代包含一個(gè)解，能產(chǎn)生一個(gè)充分接近或等于期望答案的輸出，那么問題就已經(jīng)解決了。如果情況并非如此，新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程，一代一代演化下去，直到達(dá)到期望的解為止。

并行計(jì)算

　　非常容易將遺傳算法用到并行計(jì)算和群集環(huán)境中。一種方法是直接把每個(gè)節(jié)點(diǎn)當(dāng)成一個(gè)并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)。另一種方法是“農(nóng)場主/勞工”體系結(jié)構(gòu)，指定一個(gè)節(jié)點(diǎn)為“農(nóng)場主”節(jié)點(diǎn)，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評估。

 

 

術(shù)語說明　　由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識，下面是我們將會(huì)用來的一些術(shù)語說明：

染色體(Chromosome)

　　染色體又可以叫做基因型個(gè)體(individuals),一定數(shù)量的個(gè)體組成了群體(population),群體中個(gè)體的數(shù)量叫做群體大小。

基因(Gene)

　　基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S=1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alleles)。

基因地點(diǎn)(Locus)

　　基因地點(diǎn)在算法中表示一個(gè)基因在串中的位置稱為基因位置(Gene Position)，有時(shí)也簡稱基因位。基因位置由串的左向右計(jì)算，例如在串 S=1101 中，0的基因位置是3。

特征值( Feature)

　　在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。

適應(yīng)度(Fitness)

　　各個(gè)個(gè)體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。 這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。

 

 

 

　　遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個(gè)體按照它們對環(huán)境適應(yīng)度(適應(yīng)度評估)施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題

 

 

的解，一代又一代地優(yōu)化，并逼進(jìn)最優(yōu)解。

　　遺傳操作包括以下三個(gè)基本遺傳算子(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個(gè)遺傳算子有如下特點(diǎn)：

　　個(gè)體遺傳算子的操作都是在隨機(jī)擾動(dòng)情況下進(jìn)行的。因此，群體中個(gè)體向最優(yōu)解遷移的規(guī)則是隨機(jī)的。需要強(qiáng)調(diào)的是，這種隨機(jī)化操作和傳統(tǒng)的隨機(jī)搜索方法是有區(qū)別的。遺傳操作進(jìn)行的高效有向的搜索而不是如一般隨機(jī)搜索方法所進(jìn)行的無向搜索。

　　遺傳操作的效果和上述三個(gè)遺傳算子所取的操作概率，編碼方法，群體大小，初始群體以及適應(yīng)度函數(shù)的設(shè)定密切相關(guān)。

　　從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫選擇。選擇算子有時(shí)又稱為再生算子(reproduction operator)。選擇的目的是把優(yōu)化的個(gè)體(或解)直接遺傳到下一代或通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有以

 

下幾種：適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。

　　其中輪盤賭選擇法 （roulette wheel selection）是最簡單也是最常用的選擇方法。在該方法中，各個(gè)個(gè)體的選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為n，其中個(gè)體i的適應(yīng)度為，則i 被選擇的概率，為遺傳算法

　　顯然，概率反映了個(gè)體i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。個(gè)體適應(yīng)度越大。其被選擇的概率就越高、反之亦然。計(jì)算出群體中各個(gè)個(gè)體的選擇概率后，為了選擇交配個(gè)體，需要進(jìn)行多輪選擇。每一輪產(chǎn)生一個(gè)[0，1]之間均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來確定被選個(gè)體。個(gè)體被選后，可隨機(jī)地組成交配對，以供后面的交叉操作。

　　在自然界生物進(jìn)化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。

　　交叉算子根據(jù)交叉率將種群中的兩個(gè)個(gè)體隨機(jī)地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法：

　　a)實(shí)值重組（real valued recombination）

　　1)離散重組（discrete recombination）

　　2)中間重組（intermediate recombination）

　　3)線性重組（linear recombination）

　　4)擴(kuò)展線性重組（extended linear recombination）。

　　b)二進(jìn)制交叉（binary valued crossover）

　　1)單點(diǎn)交叉（single-point crossover）

　　2)多點(diǎn)交叉（multiple-point crossover）

　　3)均勻交叉（uniform crossover）

　　4)洗牌交叉（shuffle crossover）

　　5)縮小代理交叉（crossover with reduced surrogate）。

　　最常用的交叉算子為單點(diǎn)交叉(one-point crossover)。具體操作是:在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體。下面給出了單點(diǎn)交叉的一個(gè)例子：

　　個(gè)體A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新個(gè)體

　　個(gè)體B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新個(gè)體

　　變異算子的基本內(nèi)容是對群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。依據(jù)個(gè)體編碼表示方法的不同，可以有以下的算法：

　　a)實(shí)值變異

　　b)二進(jìn)制變異。

　　一般來說，變異算子操作的基本步驟如下：

　　a)對群中所有個(gè)體以事先設(shè)定的編譯概率判斷是否進(jìn)行變異

　　b)對進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異。

　　遺傳算法引入變異的目的有兩個(gè):一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解鄰域時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應(yīng)取較小值，否則接近最優(yōu)解的積木塊會(huì)因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時(shí)收斂概率應(yīng)取較大值。

　　遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當(dāng)群體在進(jìn)化中陷于搜索空間中某個(gè)超平面而僅靠交叉不能擺脫時(shí)，通過變異操作可有助于這種擺脫。所謂相互競爭，是指當(dāng)通過交叉已形成所期望的積木塊時(shí)，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳算法的一個(gè)重要研究內(nèi)容。

　　基本變異算子是指對群體中的個(gè)體碼串隨機(jī)挑選一個(gè)或多個(gè)基因座并對這些基因座的基因值做變動(dòng)(以變異概率P.做變動(dòng))，(0，1)二值碼串中的基本變異操作如下：

　　基因位下方標(biāo)有*號的基因發(fā)生變異。

　　變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小

 

 

 

的值，一般取0.001－0.1。

　　當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閾值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，或者迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)時(shí)，算法終止。預(yù)設(shè)的代數(shù)一般設(shè)置為100-500代。

 

 

　　GA的流程圖如右圖

 

所示

　　遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。這一轉(zhuǎn)換操作就叫做編碼，也可以稱作(問題的)表示(representation)。

　　評估編碼策略常采用以下3個(gè)規(guī)范:

　　a)完備性(completeness):問題空間中的所有點(diǎn)(候選解)都能作為GA空間中的點(diǎn)(染色體)表現(xiàn)。

　　b)健全性(soundness): GA空間中的染色體能對應(yīng)所有問題空間中的候選解。

　　c)非冗余性(nonredundancy):染色體和候選解一一對應(yīng)。

　　目前的幾種常用的編碼技術(shù)有二進(jìn)制編碼，浮點(diǎn)數(shù)編碼，字符編碼，變成編碼等。

　　而二進(jìn)值編碼是目前遺傳算法中最常用的編碼方法。即是由二進(jìn)值字符集{0,1}產(chǎn)生通常的0,1字符串來表示問題空間的候選解。它具有以下特點(diǎn)：

　　a)簡單易行

　　b)符合最小字符集編碼原則

　　c)便于用模式定理進(jìn)行分析，因?yàn)槟Ｊ蕉ɡ砭褪且曰A(chǔ)的。

　　進(jìn)化論中的適應(yīng)度，是表示某一個(gè)體對環(huán)境的適應(yīng)能力，也表示該個(gè)體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評價(jià)函數(shù)，是用來判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的。

　　遺傳算法在搜索進(jìn)化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。由此可見，在不少場合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。

　　適應(yīng)度函數(shù)的設(shè)計(jì)主要滿足以下條件：

　　a）單值、連續(xù)、非負(fù)、最大化

　　b) 合理、一致性

　　c）計(jì)算量小

　　d）通用性強(qiáng)。

　　在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問題本身的要求而定。適應(yīng)度函數(shù)設(shè)計(jì)直接影響到遺傳算法的性能。

　　遺傳算法中初始群體中的個(gè)體是隨機(jī)產(chǎn)生的。一般來講，初始群體的設(shè)定可采取如下的策略:

　　a)根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。

　　b)先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加到初始群體中。這種過程不斷迭代，直到初始群體中個(gè)體數(shù)達(dá)到了預(yù)先確定的規(guī)模。