遺傳算法原理與應用課件

遺傳算法原理與應用組員：余靜芝許冰孫純軼楊美艷厲云丹

遺傳算法原理與應用組員：提綱一、遺傳算法概述二、遺傳算法原理三、遺傳算法的應用提綱一、遺傳算法概述

生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的自適應能力。受其啟發(fā)，人們致力于對生物各種生存特性的機理研究和行為模擬，為人工自適應系統(tǒng)的設計和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithms，簡稱GAs)就是這種生物行為的計算機模擬中令人矚目的重要成果?；趯ι镞z傳和進化過程的計算機模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應能力和優(yōu)化能力。

遺傳算法所借鑒的生物學基礎就是生物的遺傳和進化。遺傳與變異

遺傳(Heredity)——世間的生物從其父代繼承特性或性狀，這種生命現象就稱為遺傳(Heredity)，由于遺傳的作用，使得人們可以種瓜得瓜、種豆得豆，也使得鳥仍然是在天空中飛翔，魚仍然是在水中游。變異（variation）——雖然說子代遺傳了父代的各種特性，但是總會出現與父代不一樣的性狀，這就可以說是變異。由于變異的存在，沒有兩個同種生物是完全一樣的，或者說，沒有兩片葉子是一樣的。生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的自遺傳算法與生物進化之間的對應關系遺傳算法生物進化適應函數環(huán)境適應值函數適應性適應性函數值最大的解被保留的概率最大選擇問題的一個解個體解的編碼染色體編碼的元素基因被選定的一組解群體根據適應函數選擇的一組解（以編碼形式表示）種群以一定的方式由雙親產生后代的過程交配編碼的某些分量發(fā)生變化的過程變異遺傳算法與生物進化之間的對應關系遺傳算法生物進化適應函數環(huán)境

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

遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。遺傳算法的定義遺傳算法（GeneticAlgorithm）染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經過解碼（decoding），可以作為問題近似最優(yōu)解。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（遺傳算法計算優(yōu)化的過程就如同生物學上生物遺傳進化的過程，主要有三個基本操作（或算子）：選擇（Selection）交叉（Crossover）變異（Mutation）選擇(復制)：

根據各個個體的適應度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中；交叉：

將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率(稱為交叉概率）交換它們之間的部分染色體；

變異：

對群體P(t)中的每一個個體，以某一概率(稱為變異概率)改變某一個或某一些基因座上的基因值為其他基因值。

遺傳算法計算優(yōu)化的過程就如同生物學上生物遺傳進化的過程，主要

依據適應函數值的大小，選擇操作從規(guī)模為N的群體中隨機地選擇若干染色體構成種群，種群的規(guī)?？梢耘c原來群體的規(guī)模一致，也可以不一致。若假設二者規(guī)模一致，但二者并不完全相同，因為適應函數值大的染色體可能會多次被從群體選出，而適應值小的染色體可能會失去被選中的機會。因此，一些適應函數值大的染色體可能會重復出現在種群中，而一些適應函數值小的染色體則可能被淘汰。依據適應函數值的大小，選擇操作從規(guī)模為N的群體中隨一、遺傳算法概述1、智能優(yōu)化算法2、基本遺傳算法3、遺傳算法的特點一、遺傳算法概述1、智能優(yōu)化算法1、智能優(yōu)化算法智能優(yōu)化算法又稱為現代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據，而不是單純憑借專家經驗，理論上可以在一定的時間內找到最優(yōu)解或近似最優(yōu)解。1、智能優(yōu)化算法智能優(yōu)化算法又稱為現代啟發(fā)式算法常用的智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡稱GA）（2）模擬退火算法（SimulatedAnnealing，簡稱SA）（3）禁忌搜索算法（TabuSearch，簡稱TS）……常用的智能優(yōu)化算法（1）遺傳算法智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空間，因而具有全局優(yōu)化性能。智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)遺傳算法的搜索機制

遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。遺傳算法的搜索機制遺傳算法模擬自然遺傳算法的具體步驟選擇編碼策略，把參數集合（可行解集合）轉換染色體結構空間；定義適應函數，便于計算適應值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數；隨機產生初始化群體；計算群體中的個體或染色體解碼后的適應值；按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標，或者已完成預定的迭代次數，不滿足則返回第五步，或者修改遺傳策略再返回第六步．遺傳算法的具體步驟選擇編碼策略，把參數集合（可行解集合）轉換遺傳算法原理與應用課件2、基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎。2、基本遺傳算法基本遺傳算法（SimpleGen基本遺傳算法的組成（1）編碼（產生初始種群）（2）適應度函數（3）遺傳算子（選擇、交叉、變異）（4）運行參數基本遺傳算法的組成（1）編碼（產生初始種群）編碼GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。編碼GA是通過某種編碼機制把對象抽象為由特定基本遺傳算法的算法描述基本遺傳算法的算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileendProcedureGA函數優(yōu)化示例求下列一元函數的最大值：

x∈[-1,2]，求解結果精確到6位小數。函數優(yōu)化示例求下列一元函數的最大值：x∈[-1,2]，SGA對于本例的編碼

由于區(qū)間長度為3，求解結果精確到6位小數，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例的二進制編碼長度至少需要22位，本例的編碼過程實質上是將區(qū)間[-1，2]內對應的實數值轉化為一個二進制串（b21b20…b0）。SGA對于本例的編碼由于區(qū)間長度為3，求解結果幾個術語基因型：1000101110110101000111

表現型：0.637197

編碼解碼個體（染色體）基因幾個術語基因型：100010111011010100011初始種群SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數量稱為種群規(guī)模。初始種群SGA采用隨機方法生成若干個個體的集合，適應度函數遺傳算法對一個個體（解）的好壞用適應度函數值來評價，適應度函數值越大，解的質量越好。適應度函數是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。適應度函數遺傳算法對一個個體（解）的好壞用適選擇算子遺傳算法使用選擇運算來實現對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。選擇算子遺傳算法使用選擇運算來實現對群體中的個體輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應度函數值大小成正比。設群體大小為n，個體i的適應度為Fi，則個體i被選中遺傳到下一代群體的概率為：輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它輪盤賭選擇方法的實現步驟（1）計算群體中所有個體的適應度函數值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。輪盤賭選擇方法的實現步驟（1）計算群體中所有個體的適應度函

以賭輪盤的方式來看，把一個輪盤分成若干扇形，面積越大的編號，越容易中獎，因此獎金會比較低。以適應性函數來看，其值越大者所占的面積就越大，其選中的機率就越大。以賭輪盤的方式來看，把一個輪盤分成若干扇形，面積越大的交叉算子所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。SGA中交叉算子采用單點交叉算子。交叉算子所謂交叉運算，是指對兩個相互配對的染色單點交叉運算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點

在基因組中的隨機選擇一個位置，然后交換兩父代個體中該位置后面的所以基因來產生后代個體。單點交叉運算交叉前：交叉點在基因組中的隨機選擇一個位多點交叉運算交叉前：00000|01110|00000001000011100|00000|111111000101交叉后：00000|01110|00000001000011100|00000|111111000101交叉點交叉點

在基因組中隨機選擇兩個位置，然后交換兩個父代個體中處于兩個位置之間的基因來產生后代個體。多點交叉運算交叉前：交叉點交叉點在基因組中隨機選擇兩均點交叉運算交叉前：00000|01110|00000|00100|0011100|00000|11111|10001|01交叉后：00000|00000|00000|10001|0011100|01110|11111|00100|01

均勻交叉又稱“駐點交叉”，在交叉前先進行基因的變異檢測，通過后再行交叉。交叉點均點交叉運算交叉前：均勻交叉又稱“駐點交叉”，在交叉變異算子所謂變異運算，是指依據變異概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子。變異算子所謂變異運算，是指依據變異概率Pm基本位變異算子基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)??；疚蛔儺愃阕踊疚蛔儺愃阕邮侵笇€體編碼串隨機基本位變異算子的執(zhí)行過程

變異前：000001110000000010000變異后：000001110001000010000變異點基本位變異算子的執(zhí)行過程變異前：變異點運行參數（1）M：種群規(guī)模（2）T：遺傳運算的終止進化代數（3）Pc：交叉概率（4）Pm：變異概率運行參數（1）M：種群規(guī)模SGA的框圖產生初始群體是否滿足停止準則是輸出結果并結束計算個體適應度值比例選擇運算單點交叉運算基本位變異運算否產生新一代群體執(zhí)行M/2次SGA的框圖產生初始群體是否滿足停止準則是輸出結果并結束計3、遺傳算法的特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應度函數不受連續(xù)、可微等條件的約束，適用范圍很廣。3、遺傳算法的特點（1）群體搜索，易于并行化處理；二、遺傳算法原理1、遺傳算法的數學基礎2、遺傳算法的收斂性分析3、遺傳算法的改進二、遺傳算法原理1、遺傳算法的數學基礎1、遺傳算法的數學基礎（1）模式定理（2）積木塊假設

1、遺傳算法的數學基礎（1）模式定理模式模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結構。在二進制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即0或者1。

模式示例：10**1模式模式是指種群個體基因串中的相似樣板，它用來描述兩個定義定義1：模式H中確定位置的個數稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1)=4。

兩個定義定義1：模式H中確定位置的個數稱為模式模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式階數越高，模式的確定性就越高，所匹配的樣本數就越少。在遺傳操作中，即使階數相同的模式，也會有不同的性質，而模式的定義距就反映了這種性質的差異。模式的階和定義距的含義模式階用來反映不同模式間確定模式定理

模式定理：具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數目呈指數增長，為解釋遺傳算法機理提供了數學基礎。

模式定理模式定理：具有低階、短定義距模式定理從模式定理可看出，有高平均適應度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數增長的串數目，這主要是因為選擇使最好的模式有更多的復制，交叉算子不容易破壞高頻率出現的、短定義長的模式，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。模式定理從模式定理可看出，有高平均適應度、短定義距積木塊假設

積木塊假設：遺傳算法通過短定義距、低階以及高平均適應度的模式（積木塊），在遺傳操作下相互結合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數呈指數增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。積木塊假設積木塊假設：遺傳算法通過2、遺傳算法的收斂性分析遺傳算法要實現全局收斂，首先要求任意初始種群經有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。2、遺傳算法的收斂性分析遺傳算法要實現全局收斂，首種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現為收斂速度緩慢。種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠選擇操作對收斂性的影響選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。選擇操作對收斂性的影響選擇操作使高適應度個體能夠以交叉概率對收斂性的影響交叉操作用于個體對，產生新的個體，實質上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應度值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。交叉概率對收斂性的影響交叉操作用于個體對，產生新的變異概率對收斂性的影響

變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。變異概率對收斂性的影響變異操作是對種遺傳算法的本質

遺傳算法本質上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。

遺傳算法的本質遺傳算法本質上是對染3、遺傳算法的改進遺傳欺騙問題：在遺傳算法進化過程中，有時會產生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導致算法獲得某個局部最優(yōu)解。3、遺傳算法的改進遺傳欺騙問題：在遺傳遺傳算法的改進途徑（1）對編碼方式的改進（2）對遺傳算子的改進（3）對控制參數的改進（4）對執(zhí)行策略的改進遺傳算法的改進途徑（1）對編碼方式的改進對編碼方式的改進二進制編碼優(yōu)點在于編碼、解碼操作簡單，交叉、變異等操作便于實現，缺點在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴大，遺傳算法的性能降低。格雷編碼克服了二進制編碼的不連續(xù)問題，浮點數編碼改善了遺傳算法的計算復雜性。對編碼方式的改進二進制編碼優(yōu)點在于編對遺傳算子的改進排序選擇均勻交叉逆序變異（1）對群體中的所有個體按其適應度大小進行降序排序；（2）根據具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3）以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產生下一代群體。

對遺傳算子的改進排序選擇（1）對群體中的所有個體按其適對遺傳算子的改進排序選擇均勻交叉逆序變異（1）隨機產生一個與個體編碼長度相同的二進制屏蔽字P=W1W2…Wn；（2）按下列規(guī)則從A、B兩個父代個體中產生兩個新個體X、Y：若Wi=0，則X的第i個基因繼承A的對應基因，Y的第i個基因繼承B的對應基因；若Wi=1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。

對遺傳算子的改進排序選擇（1）隨機產生一個與個體編碼長對遺傳算子的改進排序選擇均勻交叉逆序變異變異前：348|7965|21變異前：348|5697|21對遺傳算子的改進排序選擇變異前：對控制參數的改進

Schaffer建議的最優(yōu)參數范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

對控制參數的改進Schaffer建議對控制參數的改進

Srinvivas等人提出自適應遺傳算法，即PC和Pm能夠隨適應度自動改變，當種群的各個個體適應度趨于一致或趨于局部最優(yōu)時，使二者增加，而當種群適應度比較分散時，使二者減小，同時對適應值高于群體平均適應值的個體，采用較低的PC和Pm，使性能優(yōu)良的個體進入下一代，而低于平均適應值的個體，采用較高的PC和Pm，使性能較差的個體被淘汰。對控制參數的改進Srinvivas對執(zhí)行策略的改進混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法對執(zhí)行策略的改進混合遺傳算法三、遺傳算法的應用1、遺傳算法的應用領域2、遺傳算法的應用示例

三、遺傳算法的應用1、遺傳算法的應用領域1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數優(yōu)化（3）自動控制（4）生產調度（5）圖像處理（6）機器學習（7）人工生命（8）數據挖掘

1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數優(yōu)化遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化間題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面是遺傳算法的一些主要應用領域：(1)組合優(yōu)化

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

函數優(yōu)化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數優(yōu)化問題，用其他優(yōu)化方法較難求解，用遺傳算法可以方便地得到較好的結果。

遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化間題的通用框架，它(3)自動控制

在自動控制領域中很多與優(yōu)化相關的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出了良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經網絡的結構優(yōu)化設計和權值學習等，都顯示出了遺傳算法在這些領域中應用的可能性。（4）生產調度問題

生產調度問題在很多情況下所建立起來的數學模型難以精確求解，即使經過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠。而目前在現實生產中也主要是靠一些經驗來進行調度?，F在遺傳算法已成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用。

(3)自動控制（5）機器學習

學習能力是高級自適應系統(tǒng)所應具備的能力之一?；谶z傳算法的機器學習，特別是分類器系統(tǒng)，在很多領域中都得到了應用。例如，遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數，從而更好地改進了模糊系統(tǒng)的性能；基于遺傳算法的機器學習可用來調整人工神經網絡的連接權，也可用于人工神經網絡的網絡結構優(yōu)化設計；分類器系統(tǒng)也在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。

（5）機器學習(6)圖像處理

圖像處理是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地，日前已在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。(7)人工生命

人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現象的重要基礎理論。(6)圖像處理（8）數據挖掘數據挖掘是近幾年出現的數據庫技術，它能夠從大型數據庫中提取隱含的、先前未知的、有潛在應用價值的知識和規(guī)則。許多數據挖掘問題可看成是搜索問題，數據庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應用遺傳算法在數據庫中進行搜索，對隨機產生的一組規(guī)則進行進化.直到數據庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數據庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數據挖掘下具。利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。對遺傳算法的改進很多，其中有馬爾科夫鏈模型，有編碼方式的改進，選擇算子、變異算子和交換算子的改進，有種群規(guī)模動態(tài)性上的改動，最有特點的改進就是并行化改進。并行化改進利用的遺傳算法的固有并行性。（8）數據挖掘數據挖掘是近幾年出現的數據庫技術，它能夠從大2、遺傳算法的應用示例彈藥裝載問題（AmmunitionLoadingProblem，簡稱ALP），就是在滿足各類通用彈藥運輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運輸工具，使得通用彈藥的裝載效率達到最大值的問題。2、遺傳算法的應用示例彈藥裝載問題（AAGSAA的基本原理在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應用改進型遺傳算法和模擬退火算法相結合，構建自適應遺傳模擬退火算法（AGSAA），從而綜合了全局優(yōu)化和局部搜索的特點，為解決彈藥裝載這一組合優(yōu)化問題提供了新的思路。AGSAA的基本原理在彈藥裝載中，考慮到模擬退火AGSAA的編碼方式AGSAA采用二進制編碼方式，每一個二進制位對應一個待裝彈藥箱，若為１，表示該彈藥箱裝入運輸工具，為０則不裝。AGSAA的編碼方式AGSAA采用二進制編碼方式AGSAA的解碼和適應度函數AGSAA采用彈藥裝載的啟發(fā)式算法來解碼，解碼后最終確定裝入運輸工具的彈藥箱。適應度函數主要考慮兩個方面，即載重率和積載率，對這兩個因素加權，來計算適應度函數值。AGSAA的解碼和適應度函數AGSAA采用彈藥裝彈藥裝載的啟發(fā)式算法

（1）定位規(guī)則（Locatingrule）定位規(guī)則是指用來確定當前待裝彈藥箱在運輸工具剩余裝載空間中擺放位置的規(guī)則。（2）定序規(guī)則（Orderingrule）定序規(guī)則是指用來確定彈藥箱放入運輸工具裝載空間先后順序的規(guī)則。彈藥裝載的啟發(fā)式算法（1）定位規(guī)則（Locating遺傳算子的選擇AGSAA的選擇算子采用輪盤賭選擇算子，并結合最優(yōu)保存策略；變異算子采用基本位變異算子；同時，在變異運算之后，增加退火算子，以增強算法的局部搜索能力；交叉概率和變異概率為自適應概率，以提高種群的進化效率。遺傳算子的選擇AGSAA的選擇算子采用輪盤賭選擇算子，交叉算子的選擇由于AGSAA是采用將彈藥箱的編號排列成串來進行編碼的，如果個體交叉采用傳統(tǒng)方式進行，就有可能使個體的編碼產生重復基因（即一個彈藥箱編號在一個個體中出現兩次以上），從而產生不符合條件的個體，因此，AGSAA采用的是部分映射交叉算子。交叉算子的選擇由于AGSAA是采用將彈藥箱的編號排列部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345部分映射交叉算子交叉前：遺傳算法的應用實例遺傳算法旅行商問題旅行商問題：一個旅行者要去很多城市，每個城市只去一次，問：該怎么走路線最短？這個問題可以轉化為：隨機給n個點，如何連線這n個點，使得連線最短？這個問題是遺傳算法的經典問題~哈哈~~我試著寫了一個程序來解決。采用的策略是：1.精英主義：每次有2個最優(yōu)解直接進入下一代。2.輪盤賭選擇生育：每次對每一代的個體進行一次輪詢，如果不適應度<某個隨機數，那么選擇這個個體進行生育。遺傳算法的應用實例遺傳算法旅行商問題旅行商問題：一個旅行者要3.單性繁殖：因為基因組的基因是互斥的且有序的，所以不適合兩性繁殖。4.交換變異：變異的方式為——隨機選擇兩個不同位置的基因，交換位置。遺傳算法的目的，就是找到一個可能最優(yōu)的解！為了達到這個目的，他先對解進行隨機搜索，然后選中幾個解中較優(yōu)的解，進行一些變換，然后再次從這些變換后的解中搜尋較優(yōu)解，變換n次之后，有可能得到非常優(yōu)秀的解。所以說，遺傳算法是建立在最優(yōu)解與較優(yōu)解的差別小的基礎上的，也可以說，是建立在父母漂亮，小孩很有可能也漂亮的理論基礎上的。另外，遺傳算法也是拼人品的算法，他得出的很有可能是局部最優(yōu)解，而不是全局最優(yōu)解。3.單性繁殖：因為基因組的基因是互斥的且有序的，所以不適合兩運行結果運行結果主要程序：voidcGAMachine::SetupNextGeneration()//進化到下一代{vector<cGenome>offspring;//保存下一代基因m_maxNotFitness=m_genomes[m_population-1].m_notfitness;//所有基因組最大不適應度while(offspring.size()<(unsignedint)m_population-2)//選擇（最大人口數-2）數量的基因組進行變異和遺傳{cGenomeparent=SelectRouletteWheel();//進行輪盤賭隨機選擇一個基因組出來進行生育cGenomeoffspring1;//保存變異后的基因組MutateInsert(parent.m_genes,offspring1.m_genes);//進行變異主要程序：voidcGAMachine::SetupNexoffspring.push_back(offspring1);//將變異后的基因組壓入第二代vector<基因組>里}sort(m_genomes.begin(),m_genomes.end());//對vector<基因組>進行排序，以便下一行代碼選出最優(yōu)秀的2個基因組CopyEliteInto(offspring);//直接將最優(yōu)秀的2個基因組復制到下一代m_genomes=offspring;m_curGener++;//代數計數器+1}offspring.push_back(offspring1voidcGAMachine::MutateInsert(constvector<cGene>&parent,vector<cGene>&offspring)//插入變異，似乎比交換變異更好{/*if(rand()/(double)(RAND_MAX)>m_mutationRate){offspring=parent;return;}*/intnRandscr=rand()%(parent.size()-1);intnRanddes=rand()%(parent.size()-1);if(nRanddes==nRandscr){offspring=parent;return;}voidcGAMachine::MutateInsert(cGenegeneInsert=parent[nRandscr];offspring=parent;offspring.erase(offspring.begin()+nRandscr);if(nRandscr<nRanddes){offspring.insert(offspring.begin()+nRanddes-1,geneInsert);}else{offspring.insert(offspring.begin()+nRanddes,geneInsert);}}cGenegeneInsert=parent[nRan謝謝！謝謝！遺傳算法原理與應用組員：余靜芝許冰孫純軼楊美艷厲云丹

遺傳算法原理與應用組員：提綱一、遺傳算法概述二、遺傳算法原理三、遺傳算法的應用提綱一、遺傳算法概述

生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的自適應能力。受其啟發(fā)，人們致力于對生物各種生存特性的機理研究和行為模擬，為人工自適應系統(tǒng)的設計和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithms，簡稱GAs)就是這種生物行為的計算機模擬中令人矚目的重要成果?；趯ι镞z傳和進化過程的計算機模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應能力和優(yōu)化能力。

遺傳算法所借鑒的生物學基礎就是生物的遺傳和進化。遺傳與變異

遺傳(Heredity)——世間的生物從其父代繼承特性或性狀，這種生命現象就稱為遺傳(Heredity)，由于遺傳的作用，使得人們可以種瓜得瓜、種豆得豆，也使得鳥仍然是在天空中飛翔，魚仍然是在水中游。變異（variation）——雖然說子代遺傳了父代的各種特性，但是總會出現與父代不一樣的性狀，這就可以說是變異。由于變異的存在，沒有兩個同種生物是完全一樣的，或者說，沒有兩片葉子是一樣的。生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的自遺傳算法與生物進化之間的對應關系遺傳算法生物進化適應函數環(huán)境適應值函數適應性適應性函數值最大的解被保留的概率最大選擇問題的一個解個體解的編碼染色體編碼的元素基因被選定的一組解群體根據適應函數選擇的一組解（以編碼形式表示）種群以一定的方式由雙親產生后代的過程交配編碼的某些分量發(fā)生變化的過程變異遺傳算法與生物進化之間的對應關系遺傳算法生物進化適應函數環(huán)境

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

遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。遺傳算法的定義遺傳算法（GeneticAlgorithm）染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經過解碼（decoding），可以作為問題近似最優(yōu)解。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（遺傳算法計算優(yōu)化的過程就如同生物學上生物遺傳進化的過程，主要有三個基本操作（或算子）：選擇（Selection）交叉（Crossover）變異（Mutation）選擇(復制)：

根據各個個體的適應度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中；交叉：

將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率(稱為交叉概率）交換它們之間的部分染色體；

變異：

對群體P(t)中的每一個個體，以某一概率(稱為變異概率)改變某一個或某一些基因座上的基因值為其他基因值。

遺傳算法計算優(yōu)化的過程就如同生物學上生物遺傳進化的過程，主要

依據適應函數值的大小，選擇操作從規(guī)模為N的群體中隨機地選擇若干染色體構成種群，種群的規(guī)?？梢耘c原來群體的規(guī)模一致，也可以不一致。若假設二者規(guī)模一致，但二者并不完全相同，因為適應函數值大的染色體可能會多次被從群體選出，而適應值小的染色體可能會失去被選中的機會。因此，一些適應函數值大的染色體可能會重復出現在種群中，而一些適應函數值小的染色體則可能被淘汰。依據適應函數值的大小，選擇操作從規(guī)模為N的群體中隨一、遺傳算法概述1、智能優(yōu)化算法2、基本遺傳算法3、遺傳算法的特點一、遺傳算法概述1、智能優(yōu)化算法1、智能優(yōu)化算法智能優(yōu)化算法又稱為現代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據，而不是單純憑借專家經驗，理論上可以在一定的時間內找到最優(yōu)解或近似最優(yōu)解。1、智能優(yōu)化算法智能優(yōu)化算法又稱為現代啟發(fā)式算法常用的智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡稱GA）（2）模擬退火算法（SimulatedAnnealing，簡稱SA）（3）禁忌搜索算法（TabuSearch，簡稱TS）……常用的智能優(yōu)化算法（1）遺傳算法智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空間，因而具有全局優(yōu)化性能。智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)遺傳算法的搜索機制

遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。遺傳算法的搜索機制遺傳算法模擬自然遺傳算法的具體步驟選擇編碼策略，把參數集合（可行解集合）轉換染色體結構空間；定義適應函數，便于計算適應值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數；隨機產生初始化群體；計算群體中的個體或染色體解碼后的適應值；按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標，或者已完成預定的迭代次數，不滿足則返回第五步，或者修改遺傳策略再返回第六步．遺傳算法的具體步驟選擇編碼策略，把參數集合（可行解集合）轉換遺傳算法原理與應用課件2、基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎。2、基本遺傳算法基本遺傳算法（SimpleGen基本遺傳算法的組成（1）編碼（產生初始種群）（2）適應度函數（3）遺傳算子（選擇、交叉、變異）（4）運行參數基本遺傳算法的組成（1）編碼（產生初始種群）編碼GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。編碼GA是通過某種編碼機制把對象抽象為由特定基本遺傳算法的算法描述基本遺傳算法的算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileendProcedureGA函數優(yōu)化示例求下列一元函數的最大值：

x∈[-1,2]，求解結果精確到6位小數。函數優(yōu)化示例求下列一元函數的最大值：x∈[-1,2]，SGA對于本例的編碼

由于區(qū)間長度為3，求解結果精確到6位小數，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例的二進制編碼長度至少需要22位，本例的編碼過程實質上是將區(qū)間[-1，2]內對應的實數值轉化為一個二進制串（b21b20…b0）。SGA對于本例的編碼由于區(qū)間長度為3，求解結果幾個術語基因型：1000101110110101000111

表現型：0.637197

編碼解碼個體（染色體）基因幾個術語基因型：100010111011010100011初始種群SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數量稱為種群規(guī)模。初始種群SGA采用隨機方法生成若干個個體的集合，適應度函數遺傳算法對一個個體（解）的好壞用適應度函數值來評價，適應度函數值越大，解的質量越好。適應度函數是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。適應度函數遺傳算法對一個個體（解）的好壞用適選擇算子遺傳算法使用選擇運算來實現對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。選擇算子遺傳算法使用選擇運算來實現對群體中的個體輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應度函數值大小成正比。設群體大小為n，個體i的適應度為Fi，則個體i被選中遺傳到下一代群體的概率為：輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它輪盤賭選擇方法的實現步驟（1）計算群體中所有個體的適應度函數值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。輪盤賭選擇方法的實現步驟（1）計算群體中所有個體的適應度函

以賭輪盤的方式來看，把一個輪盤分成若干扇形，面積越大的編號，越容易中獎，因此獎金會比較低。以適應性函數來看，其值越大者所占的面積就越大，其選中的機率就越大。以賭輪盤的方式來看，把一個輪盤分成若干扇形，面積越大的交叉算子所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。SGA中交叉算子采用單點交叉算子。交叉算子所謂交叉運算，是指對兩個相互配對的染色單點交叉運算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點

在基因組中的隨機選擇一個位置，然后交換兩父代個體中該位置后面的所以基因來產生后代個體。單點交叉運算交叉前：交叉點在基因組中的隨機選擇一個位多點交叉運算交叉前：00000|01110|00000001000011100|00000|111111000101交叉后：00000|01110|00000001000011100|00000|111111000101交叉點交叉點

在基因組中隨機選擇兩個位置，然后交換兩個父代個體中處于兩個位置之間的基因來產生后代個體。多點交叉運算交叉前：交叉點交叉點在基因組中隨機選擇兩均點交叉運算交叉前：00000|01110|00000|00100|0011100|00000|11111|10001|01交叉后：00000|00000|00000|10001|0011100|01110|11111|00100|01

均勻交叉又稱“駐點交叉”，在交叉前先進行基因的變異檢測，通過后再行交叉。交叉點均點交叉運算交叉前：均勻交叉又稱“駐點交叉”，在交叉變異算子所謂變異運算，是指依據變異概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子。變異算子所謂變異運算，是指依據變異概率Pm基本位變異算子基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)??；疚蛔儺愃阕踊疚蛔儺愃阕邮侵笇€體編碼串隨機基本位變異算子的執(zhí)行過程

變異前：000001110000000010000變異后：000001110001000010000變異點基本位變異算子的執(zhí)行過程變異前：變異點運行參數（1）M：種群規(guī)模（2）T：遺傳運算的終止進化代數（3）Pc：交叉概率（4）Pm：變異概率運行參數（1）M：種群規(guī)模SGA的框圖產生初始群體是否滿足停止準則是輸出結果并結束計算個體適應度值比例選擇運算單點交叉運算基本位變異運算否產生新一代群體執(zhí)行M/2次SGA的框圖產生初始群體是否滿足停止準則是輸出結果并結束計3、遺傳算法的特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應度函數不受連續(xù)、可微等條件的約束，適用范圍很廣。3、遺傳算法的特點（1）群體搜索，易于并行化處理；二、遺傳算法原理1、遺傳算法的數學基礎2、遺傳算法的收斂性分析3、遺傳算法的改進二、遺傳算法原理1、遺傳算法的數學基礎1、遺傳算法的數學基礎（1）模式定理（2）積木塊假設

1、遺傳算法的數學基礎（1）模式定理模式模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結構。在二進制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即0或者1。

模式示例：10**1模式模式是指種群個體基因串中的相似樣板，它用來描述兩個定義定義1：模式H中確定位置的個數稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1)=4。

兩個定義定義1：模式H中確定位置的個數稱為模式模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式階數越高，模式的確定性就越高，所匹配的樣本數就越少。在遺傳操作中，即使階數相同的模式，也會有不同的性質，而模式的定義距就反映了這種性質的差異。模式的階和定義距的含義模式階用來反映不同模式間確定模式定理

模式定理：具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數目呈指數增長，為解釋遺傳算法機理提供了數學基礎。

模式定理模式定理：具有低階、短定義距模式定理從模式定理可看出，有高平均適應度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數增長的串數目，這主要是因為選擇使最好的模式有更多的復制，交叉算子不容易破壞高頻率出現的、短定義長的模式，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。模式定理從模式定理可看出，有高平均適應度、短定義距積木塊假設

積木塊假設：遺傳算法通過短定義距、低階以及高平均適應度的模式（積木塊），在遺傳操作下相互結合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數呈指數增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。積木塊假設積木塊假設：遺傳算法通過2、遺傳算法的收斂性分析遺傳算法要實現全局收斂，首先要求任意初始種群經有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。2、遺傳算法的收斂性分析遺傳算法要實現全局收斂，首種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現為收斂速度緩慢。種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠選擇操作對收斂性的影響選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。選擇操作對收斂性的影響選擇操作使高適應度個體能夠以交叉概率對收斂性的影響交叉操作用于個體對，產生新的個體，實質上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應度值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。交叉概率對收斂性的影響交叉操作用于個體對，產生新的變異概率對收斂性的影響

變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。變異概率對收斂性的影響變異操作是對種遺傳算法的本質

遺傳算法本質上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。

遺傳算法的本質遺傳算法本質上是對染3、遺傳算法的改進遺傳欺騙問題：在遺傳算法進化過程中，有時會產生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導致算法獲得某個局部最優(yōu)解。3、遺傳算法的改進遺傳欺騙問題：在遺傳遺傳算法的改進途徑（1）對編碼方式的改進（2）對遺傳算子的改進（3）對控制參數的改進（4）對執(zhí)行策略的改進遺傳算法的改進途徑（1）對編碼方式的改進對編碼方式的改進二進制編碼優(yōu)點在于編碼、解碼操作簡單，交叉、變異等操作便于實現，缺點在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴大，遺傳算法的性能降低。格雷編碼克服了二進制編碼的不連續(xù)問題，浮點數編碼改善了遺傳算法的計算復雜性。對編碼方式的改進二進制編碼優(yōu)點在于編對遺傳算子的改進排序選擇均勻交叉逆序變異（1）對群體中的所有個體按其適應度大小進行降序排序；（2）根據具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3）以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產生下一代群體。

對遺傳算子的改進排序選擇（1）對群體中的所有個體按其適對遺傳算子的改進排序選擇均勻交叉逆序變異（1）隨機產生一個與個體編碼長度相同的二進制屏蔽字P=W1W2…Wn；（2）按下列規(guī)則從A、B兩個父代個體中產生兩個新個體X、Y：若Wi=0，則X的第i個基因繼承A的對應基因，Y的第i個基因繼承B的對應基因；若Wi=1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。

對遺傳算子的改進排序選擇（1）隨機產生一個與個體編碼長對遺傳算子的改進排序選擇均勻交叉逆序變異變異前：348|7965|21變異前：348|5697|21對遺傳算子的改進排序選擇變異前：對控制參數的改進

Schaffer建議的最優(yōu)參數范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

對控制參數的改進Schaffer建議對控制參數的改進

Srinvivas等人提出自適應遺傳算法，即PC和Pm能夠隨適應度自動改變，當種群的各個個體適應度趨于一致或趨于局部最優(yōu)時，使二者增加，而當種群適應度比較分散時，使二者減小，同時對適應值高于群體平均適應值的個體，采用較低的PC和Pm，使性能優(yōu)良的個體進入下一代，而低于平均適應值的個體，采用較高的PC和Pm，使性能較差的個體被淘汰。對控制參數的改進Srinvivas對執(zhí)行策略的改進混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法對執(zhí)行策略的改進混合遺傳算法三、遺傳算法的應用1、遺傳算法的應用領域2、遺傳算法的應用示例

三、遺傳算法的應用1、遺傳算法的應用領域1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數優(yōu)化（3）自動控制（4）生產調度（5）圖像處理（6）機器學習（7）人工生命（8）數據挖掘

1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數優(yōu)化遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化間題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面是遺傳算法的一些主要應用領域：(1)組合優(yōu)化

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

函數優(yōu)化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數優(yōu)化問題，用其他優(yōu)化方法較難求解，用遺傳算法可以方便地得到較好的結果。

遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化間題的通用框架，它(3)自動控制

在自動控制領域中很多與優(yōu)化相關的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出了良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經網絡的結構優(yōu)化設計和權值學習等，都顯示出了遺傳算法在這些領域中應用的可能性。（4）生產調度問題

生產調度問題在很多情況下所建立起來的數學模型難以精確求解，即使經過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠。而目前在現實生產中也主要是靠一些經驗來進行調度?，F在遺傳算法已成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用。

(3)自動控制（5）機器學習

學習能力是高級自適應系統(tǒng)所應具備的能力之一?；谶z傳算法的機器學習，特別是分類器系統(tǒng)，在很多領域中都得到了應用。例如，遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數，從而更好地改進了模糊系統(tǒng)的性能；基于遺傳算法的機器學習可用來調整人工神經網絡的連接權，也可用于人工神經網絡的網絡結構優(yōu)化設計；分類器系統(tǒng)也在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。

（5）機器學習(6)圖像處理

圖像處理是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地，日前已在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。(7)人工生命

人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有