【正文】 到了初步的應(yīng)用，并顯示出了良好的效果。 生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠(yuǎn)。對這類復(fù)雜問題，人們已意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。 用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能，更能反映算法的本質(zhì)效果。 Koza成功地把他提出的遺傳編程的方法應(yīng)用于人工智能、機器學(xué)習(xí)、符號處理等方面。 2021/6/15 25 L． Davis 1991年， Davis編輯出版了 《 遺傳算法手冊 (Handbook of Geic Algorithms)》 — 書，書中包括了遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟中的大量應(yīng)用實例。他推薦了在大多數(shù)優(yōu)化問題中都較適用的遺傳算法的參數(shù)，還建立了著名的 De Jong五函數(shù)測試平臺，定義了評價遺傳算法性能的在線指標(biāo)和離線指標(biāo)。這些都與目前遺傳算法中所使用的算子和方法相類似。 1975年， Ho11and出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著 《 自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性 (Adaptation in natural and artificial system)》 。 下面是在遺傳算法的發(fā)展進(jìn)程中一些關(guān)鍵人物所做出的一些主要貢獻(xiàn)。 而另一方面 ， 與其他一些算法相比遺傳算法的魯棒性又會使得參數(shù)對其搜索效果的影響會盡可能地低 。 傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個搜索點到另一個搜索點的轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系，這種確定性往往也有可能使得搜索永遠(yuǎn)達(dá)不到最優(yōu)點，因而也限制了算法的應(yīng)用范圍。 遺傳算法從很多個體所組成的一個初始群體開始最優(yōu)解的搜索過程，而不是從 — 個單一的個體開始搜索。 這個特性對很多目標(biāo)函數(shù)無法或是很難求導(dǎo)數(shù)的函數(shù)，或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等，應(yīng)用遺傳算法時就顯得比較方便，因為它避開了函數(shù)求導(dǎo)這個障礙。特別是對一些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨持的優(yōu)越性。 若 t＞ T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出，終止計算。 將變異算于作用于群體。 將選擇算子作用于群體。 設(shè)置進(jìn)化代數(shù)計數(shù)器 t?0；設(shè)置最大進(jìn)化代數(shù) T；隨機生成 M個個體作為初始群體 P(0)。 2021/6/15 14 選擇 (selection)：根據(jù)各個個體的適應(yīng)度 ， 按照一定的規(guī)則或方法 ，從第 t代群體 P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體 P(t+1)中 。 與此相對應(yīng) ， 遺傳算法的運算對象是由 M個個體所組成的集合 ， 稱為群體 。 對于每一個個體 X， 要按照一定的規(guī)則確定出其適應(yīng)度；個體的適應(yīng)度與其對應(yīng)的個體表現(xiàn)型 X的目標(biāo)函數(shù)值相關(guān)聯(lián) ， X越接近于目標(biāo)函數(shù)的最優(yōu)點 ， 其適應(yīng)度越大；反之 ， 其適應(yīng)度越小 。 相應(yīng)的染色體就可表示為一個二進(jìn)制符號串 。 2021/6/15 11 遺傳算法中，將 n維決策向量 用 n個記號 Xi (n＝l， 2， ?， n)所組成的符號串 X來表示： ? ?Tnxxx ?21?X? ? Tnn xxxXXXX ?? 2121 ??? X把每一個 Xi看作一個遺傳基因 ， 它的所有可能取值稱為等位基因 ，這樣 ， X就可看做是由 n個遺傳基因所組成的一個染色體 。 2021/6/15 10 (3)搜索算法。另外，當(dāng)枚舉空間比較大時，該方法的求解效率比較低，有時甚至在目前最先進(jìn)的計算工具上都無法求解。 隨著研究的深入，人們逐漸認(rèn)識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實，因而求出其近似最優(yōu)解或滿意解是人們的主要著眼點之 — 。 2021/6/15 6 一、遺傳算法概要 ???????URRXX..)(m a xtsf式中， 為決策變量， f(X)為目標(biāo)函數(shù)，后兩個式子為約束條件， U是基本空間， R是 U的一個子集。 2021/6/15 5 遺傳算法是模擬生物在自然環(huán)境力的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。 2021/6/15 4 雖然人們還未完全揭開遺傳與進(jìn)化的奧秘，既沒有完全掌握其機制，也不完全清楚染色體編碼和譯碼過程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個特點卻為人們所共識： (1)生物的所有遺傳信息都包含在其染色休中，染色體決定了生物的性狀。受其啟發(fā)，人們致力于對生物各種生存特性的機理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計和開發(fā)提供了廣闊的前景。 遺傳算法 (Geic Algorithm，簡稱 GA)就是這種生物行為的計算機模擬中令人矚目的重要成果。 (2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過程發(fā)生在染色體上。 它最早由美國密執(zhí)安大學(xué)的 Holland教授提出，起源于 60年代對自然和人工自適應(yīng)系統(tǒng)的研究。 ? ?Tnxxx ?21?X對于一個求函數(shù)最大值的優(yōu)化問題 (求函數(shù)最小值也類同 )， —般可描述為下述數(shù)學(xué)規(guī)劃模型： 滿足約束條件的解 X稱為可行解，集合 R表示由所有滿足約束條件的解所組成的一個集合，叫做可行解集合。 2021/6/15 9 求最優(yōu)解或近似最優(yōu)解的方法 (1)枚舉法。 (2)啟發(fā)式算法。尋求一種搜索算法，該算法在可行解集合的一個子集內(nèi)進(jìn)行搜索操作，以找到問題的最優(yōu)解或近似最優(yōu)解。 — 般情況下 ， 染色體的長度 n是固定的 ， 但對一些問題 n也可以是變化的 。 2021/6/15 12 這種編碼所形成的排列形式 X是個體的基因型，與它對應(yīng)的 x值是個體的表現(xiàn)型。 遺傳算法中，決策變量 X組成了問題的解空間。 與生物一代一代的自然進(jìn)化過程相類似 ， 遺傳算法的運算過程也是一個反復(fù)迭代的過程 ， 第 t代群體記做 P(t)， 經(jīng)過一代遺傳和進(jìn)化后 ， 得到第 t+l代群體 ， 它們也是由多個個體組成的集合 ， 記做P(t+1)。 交叉 (crossover)：將群體 P(t)內(nèi)的各個個體隨機搭配成對 ， 對每對個體 ， 以某個概率 (稱為交叉概率 ， crossover rate)交換它們之間的部分染色體 。 步驟二：個體評價。 2021/6/15 16 步驟四：交叉運算。 群體 P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體 P(t+1)。 2021/6/15 17 三、遺傳算法的特點 (1)遺傳算法以決策變量的編碼作為運算對象。 2021/6/15 18 (2)遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。 再者，直接利用目標(biāo)函數(shù)值或個體適應(yīng)度，也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高了搜索效率。對這個群體所進(jìn)行的選擇、交叉、變異等運算，產(chǎn)生出的乃是新一代的群體，在這之中包括了很多群體信息。 遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。 2021/6/15 21 四、遺傳算法的發(fā)展 遺傳算法起源于對生物系統(tǒng)所進(jìn)行的計算機模擬研究。 2021/6/15 22 J． H． Holland 60年代， Ho11and提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒生物遺傳的機制，以群體的方法進(jìn)行自適應(yīng)搜索，并且充分認(rèn)識到了交叉、變異等運算策略在自適應(yīng)系統(tǒng)中的重要性。 80年代， Holland教授實現(xiàn)了第一個基于遺傳算法的機器學(xué)習(xí)系統(tǒng) —— 分類器系統(tǒng) (C1assifier system，簡稱 CS)，開創(chuàng)了基于遺傳算法的機器學(xué)習(xí)的新概念，為分類器系統(tǒng)構(gòu)造出了一個完整的框架。他還敏銳地意識到在遺傳算法執(zhí)行的不向階段可以使用不同的選擇率，這將有利于防止遺傳算法的早熟現(xiàn)象，從而創(chuàng)立了自適應(yīng)遺傳算法的概念。 D． J． De Jong 1989年， De Jong出版了專著 《 搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳沖法 (Geic Algorithms in Search， Optimization and Machine Learning)》 。這本書為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。 2021/6/15 26 五、遺傳算法的應(yīng)用 (1)函數(shù)優(yōu)化。 而對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。 實踐證明，遺傳算法對于組合優(yōu)化中的 NP完全問題非常有效。目前在現(xiàn)實生產(chǎn)中也主要是靠一些經(jīng)驗來進(jìn)行調(diào)度。 例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工種經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。 2021/6/15 31 (6)圖像處理。 遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展。 2021/6/15 33 (8)遺傳編程。 學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一。這樣 ， 由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法 。 2021/6/15 38 染色體編碼方法 基本遺傳算法使用固定長度的二進(jìn)制符號串來表示群體中的個體，其等位基因是由二值符號集 {0， 1}所組成的。 這樣 ， 根據(jù)不同種類的問題 ， 必須預(yù)先確定好由目標(biāo)函數(shù)值到個體適應(yīng)度之間的轉(zhuǎn)換規(guī)則 ， 特別是要領(lǐng)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時的處理方法 。 2021/6/15 42 在遺傳算法的實際應(yīng)用中 ， 往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍 。 變異概率通常只取較小的數(shù)值 。 t=0。 end for for i=1 to M do Mutation operation of P(t)。 個體的適應(yīng)度越大 ， 該個體被遺傳到下一代的概率也越大；反之 ， 個體的適應(yīng)度越小 ， 該個體被遺傳到下一代的概率也越小 。 上面兩式保證不了所有情況下個體的適應(yīng)度都是非負(fù)數(shù)這個要求。 ? 進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。 ? 前代或最近幾代群體中的最大目標(biāo)函數(shù)值。 所謂比例選擇算了，是指個體被選中并遺傳到下一代群體中的概率與該個體的適應(yīng)度大小成正比。 雖然賭盤的指針具體停止在哪一個扇面是無法預(yù)測的 ， 但指針指向各個扇面的概率卻是可以估計的 ， 它與各個扇面的圓心角大小成正比：圓心角越大 ， 停在該扇面的可能性也越大；圓心角越小 ，停在該扇面的可能性也越小 。 (3)最后再使用模擬賭盤操作 (即 0到 1之間的隨機數(shù) )來確定各個個體被選中的次數(shù) 。其中 [x]表示不大于 x的最大整數(shù)。 2021/6/15 55 單點交叉示意如下所示： A： 1 0 1 1 0 1 1 1 0 0 A’： 1 0 1 1 0 1 1 1 1 1 B： 0 0 0 1 1 1 0 0 1 1 B’； 0 0 0 1 1 1 0 0 0 0 單點交叉 交叉點 2021/6/15 56 基本位變異算子 對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個體 ， 若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0， 則變異操作將該基因值變?yōu)?1；反之 ， 若原有基因值為 l， 則變異操作將其變?yōu)?0。 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型 (是求目標(biāo)函數(shù)的最大值還是求目標(biāo)函數(shù)的最小值 )及其數(shù)學(xué)描述形式或量化方法。 第六步：設(shè)計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。 例如 ， 基因型 X=10l110所對應(yīng)的表現(xiàn)型是： X＝ [5， 6]T。 一個隨機產(chǎn)生的初始群體如表中第 1欄所示 。 表中第 3欄所示為初始群體中各個個體的解碼結(jié)果 ， 第 4欄所示為各個個體所對應(yīng)的目標(biāo)函數(shù)值 ， 它也是個體的適應(yīng)度 ，第 4欄中還給出了群體中適應(yīng)度的最大值和平均值 。 其具體操作過程是： 先計算出群體中所有個體的適應(yīng)度的總和； 其次計算出每個個體的相對適應(yīng)度的大小 ， 如表中第 5欄所示 ，它即為每個個體被遺傳到下一代群體中的概率 ， 每個概率值組成一個區(qū)域 ， 全部概率值之代為 l。 本例采用單點交叉的方法 ， 其具體操作過程是： 先對群體進(jìn)行隨機配對 ， 表中第 8欄所示為一種隨機配對情況； 其次隨機設(shè)置交叉點位置 ， 如表第 9欄所示為一隨機產(chǎn)生的交叉點位置 ， 其中的數(shù)字表示交叉點設(shè)置在該基因座之后； 最后再相互交換配對染色體之間的部分基因 。 本例中 ， 我們采用基本位變異的方法來進(jìn)行變異運算 ， 其具體操作過程是： 首先確定出各個個體的基因變異位置 ， 如表中第 11欄所示為隨機產(chǎn)生的變異點位置 ， 其中的數(shù)字表示變異點設(shè)置在該基因座處； 然