遺傳算法的產(chǎn)生

遺傳算法的產(chǎn)生

早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；

1963年，德國(guó)柏林技術(shù)大學(xué)的I.Rechenberg和H.P.Schwefel，做風(fēng)洞實(shí)驗(yàn)時(shí)，產(chǎn)生了進(jìn)化策略的初步思想；

60年代，L.J.Fogel在設(shè)計(jì)有限態(tài)自動(dòng)機(jī)時(shí)提出進(jìn)化規(guī)劃的思想。1966年Fogel等出版了《基于模擬進(jìn)化的人工智能》，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。

60年代中期，美國(guó)Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；

1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(GeneticAlgorithms)”一詞；

1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。遺傳算法的發(fā)展

70年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；

1985年，在美國(guó)召開了第一屆遺傳算法國(guó)際會(huì)議，并且成立了國(guó)際遺傳算法學(xué)會(huì)(ISGA，InternationalSocietyofGeneticAlgorithms)；

1989年，Holland的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；

1991年，L.Davis編輯出版了《遺傳算法手冊(cè)》，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中大量的應(yīng)用實(shí)例。遺傳算法——進(jìn)化計(jì)算——計(jì)算智能——人工智能遺傳學(xué)基本概念與術(shù)語

染色體（chromosome）：遺傳物質(zhì)的載體；

脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)；

核糖核酸（RNA）：核酸的一類。由核苷酸通過3′，5′-磷酸二酯鍵連接而成的多聚體。不同種類的RNA鏈長(zhǎng)不同，行使各式各樣的生物功能。

遺傳因子（gene）：DNA或RNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；

基因型（genotype）：遺傳因子組合的模型；

表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)；

個(gè)體（individual）：指染色體帶有特征的實(shí)體；

種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大??；

進(jìn)化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；

適應(yīng)度（fitness）：度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕；

選擇（selection）：指決定以一定的概率從種群中選擇若干個(gè)體的操作（實(shí)現(xiàn)優(yōu)勝劣汰）；

復(fù)制（reproduction）：細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因；

交叉（crossover）：在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。又稱基因重組，俗稱“雜交”；

變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀；

編碼（coding）：表現(xiàn)型到基因型的映射；

解碼（decoding）：從基因型到表現(xiàn)型的映射。遺傳算法的原理遺傳算法(GA)是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法。其采納了自然進(jìn)化模型，從代表問題可能潛在解集的一個(gè)種群開始，種群由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成，每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體，初始種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的解：

在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小挑選個(gè)體，并借助遺傳算子進(jìn)行組合交叉和主客觀變異，產(chǎn)生出代表新的解集的種群。

這一過程循環(huán)執(zhí)行，直到滿足優(yōu)化準(zhǔn)則為止。最后，末代個(gè)體經(jīng)解碼，生成近似最優(yōu)解。

基于種群進(jìn)化機(jī)制的遺傳算法如同自然界進(jìn)化一樣，后生代種群比前生代更加適應(yīng)于環(huán)境，通過逐代進(jìn)化，逼近最優(yōu)解。遺傳算法的基本流程遺傳算法的特點(diǎn)

遺傳算法的本質(zhì)并行性。

首先，遺傳算法以并行的方式從問題解的串集開始搜索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。

其次，算法內(nèi)含并行性。遺傳算法采用種群方式組織搜索，因而可同時(shí)搜索解空間的多個(gè)區(qū)域，并相互交流信息，能以較小的計(jì)算獲得較大的收益。

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

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

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

遺傳算法可更直接地應(yīng)用，對(duì)給定的問題，可以產(chǎn)生許多潛在解，最終選擇可以由使用者指定，通用性高，應(yīng)用范圍廣。遺傳算法的基本操作

遺傳基因型(編碼)

編碼方式

二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、格雷碼編碼、符號(hào)編碼、復(fù)數(shù)編碼、DNA編碼等。

以大象灰色皮膚為例：二進(jìn)制編碼：，浮點(diǎn)編碼：127.0

編碼原則

完備性（completeness）：?jiǎn)栴}空間的所有解都能表示為所設(shè)計(jì)的基因型；

健全性（soundness）：任何一個(gè)基因型都對(duì)應(yīng)于一個(gè)可能解；

非冗余性（non-redundancy）：?jiǎn)栴}空間和表達(dá)空間一一對(duì)應(yīng)。

二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較

在交叉操作時(shí)，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個(gè)體的可能性多，而且產(chǎn)生的新個(gè)體不受父?jìng)€(gè)體所構(gòu)成的超體的限制；

在變異操作時(shí)，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。

選擇

適應(yīng)度計(jì)算：

按比例的適應(yīng)度函數(shù)（proportionalfitnessassignment）：

基于排序的適應(yīng)度計(jì)算（Rank-basedfitnessassignment）：

選擇算法：

輪盤賭選擇（roulettewheelselection）：

隨機(jī)遍歷抽樣（stochasticuniversalselection）：

局部選擇（localselection）：

截?cái)噙x擇（truncationselection）：

錦標(biāo)賽選擇（tournamentselection）：

交叉或基因重組

二進(jìn)制交叉（binaryvaluedcrossover）：

單點(diǎn)交叉（single-pointcrossover）

多點(diǎn)交叉（multiple-pointcrossover）

均勻交叉（uniformcrossover）

洗牌交叉（shufflecrossover）

縮小代理交叉（crossoverwithreducedsurrogate）

實(shí)值重組（realvaluedrecombination）：

離散重組（discreterecombination）

中間重組（intermediaterecombination）

線性重組（linearrecombination）（均勻、非均勻）

擴(kuò)展線性重組（extendedlinearrecombination

交叉方式

半種群交叉(N/2)：對(duì)群體中的要交叉的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則最多共有[M/2]對(duì)相互配對(duì)的個(gè)體組參與交叉。(若種群數(shù)為奇數(shù)，則其中任一個(gè)個(gè)體多選一次配對(duì))

全種群交叉(N)：對(duì)群體中要交叉的個(gè)體，從種群中隨機(jī)挑選一個(gè)個(gè)體與其完成交叉操作，最多共有M對(duì)相互配對(duì)的個(gè)體參與變異。

變異方法

二進(jìn)制變異

單點(diǎn)變異

逆序變異

均勻變異

實(shí)值變異

隨機(jī)變異

邊界變異

非一致變異

自適應(yīng)變異

高斯變異

變異方式

基于個(gè)體的變異：即對(duì)任意一個(gè)個(gè)體，判斷其是否進(jìn)行變異操作，如果是，則隨機(jī)生成一個(gè)變異基因發(fā)生變異操作。

基于基因座的變異：即對(duì)種群中的個(gè)體，判斷每一個(gè)個(gè)體的每一位基因是否進(jìn)行變異操作，如果是，則發(fā)生變異操作。遺傳算法的應(yīng)用

函數(shù)優(yōu)化：是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域；

組合優(yōu)化：實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效；

自動(dòng)控制：如基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等；

機(jī)器人智能控制：遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動(dòng)協(xié)調(diào)等方面廣泛得到了應(yīng)用；

組合圖像處理和模式識(shí)別：目前已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識(shí)別等方面得到了應(yīng)用；

人工生命：基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；

遺傳程序設(shè)計(jì)：Koza發(fā)展了遺傳程序設(shè)計(jì)的概念，他使用了以LISP語言所表示的編碼方法，基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動(dòng)生成計(jì)算機(jī)程序；

機(jī)器學(xué)習(xí)：機(jī)器學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一?；谶z傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù)，從而更好地改進(jìn)了模糊系統(tǒng)的性能；基于遺傳算法的機(jī)器學(xué)習(xí)可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)；分類器系統(tǒng)也在學(xué)習(xí)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用?；具z傳算法遺傳算法在自然與社會(huì)現(xiàn)象的模擬、工程計(jì)算等方面得到了廣泛的應(yīng)用。在各個(gè)不同的應(yīng)用領(lǐng)域，為了取得更好的結(jié)果，人們對(duì)GA進(jìn)行了大量的改進(jìn)。為不至于混淆，把Holland提出的算法稱為基本遺傳算法，簡(jiǎn)稱為SGA（SimpleGeneticAlgorithm)，也有稱其為(GA、CGA)。以SGA為例，闡述遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)方法。

SGA的構(gòu)成要素：

染色體編碼方法：基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因由二值符號(hào)集{0，1}組成。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。如：x：就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是l＝18。

個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。

遺傳算子：基本遺傳算法使用下述三種遺傳算子：

選擇運(yùn)算：使用比例選擇算子；

交叉運(yùn)算：使用單點(diǎn)交叉算子；

變異運(yùn)算：使用基本位變異算子。

基本遺傳算法的運(yùn)行參數(shù)：基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：

M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20∽100。

T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100∽500

pc：交叉概率，一般取為0.4∽0.99

pm：變異概率，一般取為0.0001∽0.1說明：這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。

基本遺傳算法的描述基本遺傳算法可定義為一個(gè)7元組：GA＝(M,F,s,c,m,pc,pm)M——群體大??；F——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算子；c——交叉操作算子：m——變異操作算子；pc——交叉概率；pm——變異概率。

編碼與解碼

編碼假設(shè)某一參數(shù)的取值范圍是[umin,umax]，我們用長(zhǎng)度為len的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，則它總共能夠產(chǎn)生2len種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：…＝0umin…＝1umin+d………=2len–1umax其中，d為二進(jìn)制編碼的編碼精度，其公式為：

解碼假設(shè)某一個(gè)體的編碼是：x：blenblen-1blen-2……b2b1，則對(duì)應(yīng)的解碼公式為：

[例]設(shè)-3.0≤x≤12.1，精度要求＆=1/10000，由公式：得到：即：217<<218x需要18位{0/1}符號(hào)表示。如：解碼：

個(gè)體適應(yīng)度評(píng)價(jià)如前所述，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。(1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(X)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)(2)對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即：minf(X)＝max(-f(X))但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求，需要進(jìn)行適應(yīng)度函數(shù)尺度轉(zhuǎn)換，將目標(biāo)函數(shù)值f(x)變換為個(gè)體的適應(yīng)度F(x)。(3)SGA適應(yīng)度函數(shù)變換常用方法：方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：其中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可用下面方法之一來選取：?預(yù)先指定的一個(gè)較小的數(shù)。?進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。?當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：其中，Cmax是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法求得：?預(yù)先指定的一個(gè)較大的數(shù)。?進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。?當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。

比例選擇算子指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。pi=fi/∑fi(i=1,2,…,M)式中pi——個(gè)體i被選中的概率；fi——個(gè)體i的適應(yīng)度；∑fi——群體的累加適應(yīng)度。顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個(gè)體也有可能被選中，以便增加下一代群體的多樣性。執(zhí)行比例選擇的手段是輪盤選擇。個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度：從統(tǒng)計(jì)意義講，適應(yīng)度大的個(gè)體，其刻度長(zhǎng)，被選中的可能性大；反之，適應(yīng)度小的個(gè)體被選中的可能性小，但有時(shí)也會(huì)被“破格”選中。

單點(diǎn)交叉算子Ⅰ.對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則共有[M/2]對(duì)相互配對(duì)的個(gè)體組。Ⅱ.每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長(zhǎng)度為len，則共有(len-1)個(gè)可能的交叉點(diǎn)位置。Ⅲ.對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。單點(diǎn)交叉運(yùn)算的示例如下所示：

基本位變異算子對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?，反之，若原有基因值為1，則變異操作將其變?yōu)??；疚蛔儺愐蜃拥木唧w執(zhí)行過程是：Ⅰ.對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。Ⅱ.對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體?；疚蛔儺愡\(yùn)算的示例如下所示：

變異概率變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率pm也是針對(duì)基因而言，即：式中：B——每代中變異的基因數(shù)目；M——每代中群體擁有的個(gè)體數(shù)目len——個(gè)體中基因串長(zhǎng)度。GA算法流程圖簡(jiǎn)單函數(shù)優(yōu)化實(shí)例

問題的提出：一元函數(shù)求最大值：

編碼表現(xiàn)型：x基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度）按編碼原理：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)＝3，即需將區(qū)間分為3/0.=3×106等份。所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。

產(chǎn)生初始種群產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，………

計(jì)算適應(yīng)度直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)①解碼：將個(gè)體s轉(zhuǎn)化為[-1,2]區(qū)間的實(shí)數(shù)：s=<>→x=0.②計(jì)算x的函數(shù)值（適應(yīng)度）：f(x)=xsin(10πx)+2.0=2.

遺傳操作選擇：比例選擇法；交叉：?jiǎn)吸c(diǎn)交叉；變異：小概率變異

模擬結(jié)果設(shè)置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。得到的最佳個(gè)體：smax=<>;xmax=1.8506;f(xmax)=3.8503;遺傳算法的改進(jìn)

傳統(tǒng)的GA在解決時(shí)就存在如下問題：首先，模型復(fù)雜，參數(shù)太多難以達(dá)到優(yōu)化目的，優(yōu)化速度慢且達(dá)不到最優(yōu)解。其次，約束條件復(fù)雜、繁多，算法收斂的時(shí)候很難滿足約束條件。因此，在處理交通控制問題上揚(yáng)長(zhǎng)避短，需要改進(jìn)遺傳算法，使其達(dá)到智能控制的效果。

改進(jìn)措施改變遺傳算法的組成成分；采用混合遺傳算法；采用動(dòng)態(tài)自適應(yīng)技術(shù)；采用非標(biāo)準(zhǔn)的遺傳操作算子；采用并行遺傳算法等。

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過大會(huì)使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個(gè)體結(jié)構(gòu)，Pm過大，變成純粹的隨機(jī)搜索。

自適應(yīng)策略Srinvivas等提出一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動(dòng)改變：當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使Pc和Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使Pc和Pm減少；對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)于較低的Pc和Pm；而較低適應(yīng)度的個(gè)體，對(duì)應(yīng)于較高的Pc和Pm。

自適應(yīng)方法fmax——群體中最大的適應(yīng)度值；favg——每代群體的平均適應(yīng)度值；f’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f——要交叉或變異的個(gè)體適應(yīng)度值。k1、k2、k3、k4取(0,1)的值。

自適應(yīng)方法進(jìn)一步改進(jìn)適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個(gè)體有可能是局部最優(yōu)點(diǎn)；使最大適應(yīng)度個(gè)體的交叉概率和變異概率由0提高到Pc2和Pm2；采用精英選擇策略；CHC算法

改進(jìn)思路1991年Eshelman提出的一種改進(jìn)遺傳算法；C：跨世代精英選擇（Crossgenerationalelitistselection）策略；H：異物種重組（Heterogeneousrecombination）；C：大變異（Cataclysmicmutation）。

選擇上一代種群與通過新的交叉方法產(chǎn)生的個(gè)體群混合起來，從中按一定概率選擇較優(yōu)的個(gè)體；即使交叉操作產(chǎn)生較劣個(gè)體偏多，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計(jì)算的尺度問題。

交叉均勻交叉的改進(jìn)：當(dāng)兩個(gè)父?jìng)€(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位值的交換；確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。

變異在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(jìn)行初始化；初始化：選擇一定比例（擴(kuò)散率，一般0.35）的基因座，隨機(jī)地決定它們的位值?；谛∩臣夹g(shù)的遺傳算法

小生境概念小生境（niche）：生物學(xué)中，特定環(huán)境中的一種組織功能；在SGA中，容易“近親繁殖”；NGA（NicheGenericAlgorithm），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群；優(yōu)勢(shì)：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。

選擇策略預(yù)選擇（preselection,1970）機(jī)制：當(dāng)子個(gè)體的適應(yīng)度超過其父?jìng)€(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父?jìng)€(gè)體，否則父?jìng)€(gè)體仍保留，從而有效維持種群多樣性，造就小生境進(jìn)化環(huán)境。排擠（crowding,1975）機(jī)制：設(shè)置排擠因子CF（CF=2或3），隨機(jī)選取1/CF個(gè)個(gè)體組成排擠成員，排擠與其相似（用距離來度量）的個(gè)體，使個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來度量。共享（sharing,1987）機(jī)制：通過個(gè)體之間的相似性程度的共享函數(shù)來調(diào)整各個(gè)體的適應(yīng)度。共享函數(shù)的目的是將搜索空間的多個(gè)峰值在地理上區(qū)分開來，每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體，比例數(shù)目與峰值高度有關(guān)。共享函數(shù)的值越大，表明個(gè)體之間越相似，記為Sh(dij)，dij為兩個(gè)個(gè)體i和j之間的距離。σshare是niche的半徑，由使用者給定。共享法將個(gè)體的適應(yīng)度降低，即適應(yīng)度值fi除以一個(gè)niche計(jì)數(shù)mi：在距離為σshare的范圍內(nèi)的個(gè)體彼此削減適應(yīng)度，這些個(gè)體將收斂在一個(gè)niche內(nèi)，避免了整個(gè)種群的收斂。退火進(jìn)化算法退火進(jìn)化算法(annealingevolutionalgorithm,AEA）遺傳算法（GA)模擬退火算法（SA）是人工智能中用于解決組合優(yōu)化問題的經(jīng)典。但是，SA在全局搜索能力方面不足，GA在局部搜索能力方面不足。而退火進(jìn)化算法（annealingevolutionalgorithm,AEA)綜合了SA和GA算法，優(yōu)勢(shì)互補(bǔ)，發(fā)揮SA局部搜索能力和GA全局搜索能力,克服SA全局搜索能力差及效率不高的問題和GA局部搜索能力差及其早熟現(xiàn)象。AEA把SA算法與GA結(jié)合在一起，通過變異與選擇不斷改善解群體，并行搜索解空間，從而有可能更迅速地找到全局最優(yōu)解。由于在選擇中采用Metropolis準(zhǔn)則，因而保留了SA算法易跳出某局部極值“陷阱”的優(yōu)點(diǎn)，易于向全局極小值快速收斂。算法求解過程如下：(1)初始化進(jìn)化代數(shù)計(jì)數(shù)器k←0，隨機(jī)給出種群P(k)初值，給定初試退火溫度T0。(2)評(píng)價(jià)當(dāng)前群體