遺傳算法原理

關于遺傳算法原理報告提綱一、遺傳算法概述二、遺傳算法原理三、遺傳算法的應用第2頁,共97頁，星期六，2024年，5月一、遺傳算法概述1、智能優(yōu)化算法

2、基本遺傳算法

3、遺傳算法的特點

第3頁,共97頁，星期六，2024年，5月1、智能優(yōu)化算法智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。第4頁,共97頁，星期六，2024年，5月常用的智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡稱GA）（2）模擬退火算法（SimulatedAnnealing，簡稱SA）（3）禁忌搜索算法（TabuSearch，簡稱TS）

……第5頁,共97頁，星期六，2024年，5月智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空間，因而具有全局優(yōu)化性能。返回第6頁,共97頁，星期六，2024年，5月遺傳算法起源遺傳算法是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。第7頁,共97頁，星期六，2024年，5月遺傳算法的搜索機制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和突變)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。

返回第8頁,共97頁，星期六，2024年，5月2、基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎。第9頁,共97頁，星期六，2024年，5月基本遺傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應度函數(shù)（3）遺傳算子（選擇、交叉、突變）（4）運行參數(shù)第10頁,共97頁，星期六，2024年，5月編碼GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。第11頁,共97頁，星期六，2024年，5月函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：

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

表現(xiàn)型：0.637197編碼解碼個體（染色體）基因第14頁,共97頁，星期六，2024年，5月初始種群SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。第15頁,共97頁，星期六，2024年，5月適應度函數(shù)

遺傳算法對一個個體（解）的好壞用適應度函數(shù)值來評價，適應度函數(shù)值越大，解的質量越好。適應度函數(shù)是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。第16頁,共97頁，星期六，2024年，5月選擇算子遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。第17頁,共97頁，星期六，2024年，5月輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應度函數(shù)值大小成正比。設群體大小為n，個體i的適應度為Fi，則個體i被選中遺傳到下一代群體的概率為：第18頁,共97頁，星期六，2024年，5月輪盤賭選擇方法的實現(xiàn)步驟（1）計算群體中所有個體的適應度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。第19頁,共97頁，星期六，2024年，5月交叉算子所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產(chǎn)生新個體的主要方法。SGA中交叉算子采用單點交叉算子。第20頁,共97頁，星期六，2024年，5月單點交叉運算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點第21頁,共97頁，星期六，2024年，5月突變算子所謂突變運算，是指依據(jù)突變概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的突變運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和突變運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。SGA中突變算子采用基本位突變算子。第22頁,共97頁，星期六，2024年，5月基本位突變算子基本位突變算子是指對個體編碼串隨機指定的某一位或某幾位基因作突變運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行突變操作的某一基因座上的原有基因值為0，則突變操作將其變?yōu)?；反之，若原有基因值為1，則突變操作將其變?yōu)?。第23頁,共97頁，星期六，2024年，5月基本位突變算子的執(zhí)行過程突變前：000001110000000010000突變后：000001110001000010000突變點第24頁,共97頁，星期六，2024年，5月運行參數(shù)（1）M：種群規(guī)模（2）T：遺傳運算的終止進化代數(shù)（3）Pc：交叉概率（4）Pm：突變概率第25頁,共97頁，星期六，2024年，5月SGA的框圖產(chǎn)生初始群體是否滿足停止準則是輸出結果并結束計算個體適應度值比例選擇運算單點交叉運算基本位突變運算否產(chǎn)生新一代群體執(zhí)行M/2次返回第26頁,共97頁，星期六，2024年，5月3、遺傳算法的特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。返回第27頁,共97頁，星期六，2024年，5月二、遺傳算法原理1、遺傳算法的數(shù)學基礎

2、遺傳算法的收斂性分析

3、遺傳算法的改進

返回第28頁,共97頁，星期六，2024年，5月1、遺傳算法的數(shù)學基礎（1）模式定理（2）積木塊假設返回第29頁,共97頁，星期六，2024年，5月模式模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結構。在二進制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即0或者1。

模式示例：10**1第30頁,共97頁，星期六，2024年，5月兩個定義定義1：模式H中確定位置的個數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1)=4。第31頁,共97頁，星期六，2024年，5月模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質，而模式的定義距就反映了這種性質的差異。

第32頁,共97頁，星期六，2024年，5月模式定理模式定理：具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學基礎。第33頁,共97頁，星期六，2024年，5月模式定理從模式定理可看出，有高平均適應度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串數(shù)目，這主要是因為選擇使最好的模式有更多的復制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。返回第34頁,共97頁，星期六，2024年，5月積木塊假設積木塊假設：遺傳算法通過短定義距、低階以及高平均適應度的模式（積木塊），在遺傳操作下相互結合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。返回第35頁,共97頁，星期六，2024年，5月2、遺傳算法的收斂性分析遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關的因素主要包括種群規(guī)模、選擇操作、交叉概率和突變概率。第36頁,共97頁，星期六，2024年，5月種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。第37頁,共97頁，星期六，2024年，5月選擇操作對收斂性的影響選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和突變操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。第38頁,共97頁，星期六，2024年，5月交叉概率對收斂性的影響交叉操作用于個體對，產(chǎn)生新的個體，實質上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應度值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。第39頁,共97頁，星期六，2024年，5月突變概率對收斂性的影響突變操作是對種群模式的擾動，有利于增加種群的多樣性。但是，突變概率太小則很難產(chǎn)生新模式，突變概率太大則會使遺傳算法成為隨機搜索算法。第40頁,共97頁，星期六，2024年，5月遺傳算法的本質遺傳算法本質上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用突變算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。返回第41頁,共97頁，星期六，2024年，5月3、遺傳算法的改進遺傳欺騙問題：在遺傳算法進化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導致算法獲得某個局部最優(yōu)解。第42頁,共97頁，星期六，2024年，5月遺傳算法的改進途徑（1）對編碼方式的改進（2）對遺傳算子的改進（3）對控制參數(shù)的改進（4）對執(zhí)行策略的改進第43頁,共97頁，星期六，2024年，5月對編碼方式的改進二進制編碼優(yōu)點在于編碼、解碼操作簡單，交叉、突變等操作便于實現(xiàn)，缺點在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴大，遺傳算法的性能降低。格雷編碼克服了二進制編碼的不連續(xù)問題，浮點數(shù)編碼改善了遺傳算法的計算復雜性。第44頁,共97頁，星期六，2024年，5月對遺傳算子的改進排序選擇均勻交叉逆序突變（1）對群體中的所有個體按其適應度大小進行降序排序；（2）根據(jù)具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3）以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。第45頁,共97頁，星期六，2024年，5月對遺傳算子的改進排序選擇均勻交叉逆序突變（1）隨機產(chǎn)生一個與個體編碼長度相同的二進制屏蔽字P=W1W2…Wn

；（2）按下列規(guī)則從A、B兩個父代個體中產(chǎn)生兩個新個體X、Y：若Wi=0，則X的第i個基因繼承A的對應基因，Y的第i個基因繼承B的對應基因；若Wi=1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。

第46頁,共97頁，星期六，2024年，5月對遺傳算子的改進排序選擇均勻交叉逆序突變突變前：348|7965|21突變后：348|5697|21第47頁,共97頁，星期六，2024年，5月對控制參數(shù)的改進Schaffer建議的最優(yōu)參數(shù)范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

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

2、遺傳算法的應用示例

3、我的研究第51頁,共97頁，星期六，2024年，5月1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）智能控制（4）圖像處理（5）機器學習（6）人工生命返回第52頁,共97頁，星期六，2024年，5月遺傳算法應用于組合優(yōu)化組合優(yōu)化是指在給定約束條件下,求解目標函數(shù)的最優(yōu)值。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在計算機上用枚舉法很難甚至不可能求出其最優(yōu)解。實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡路由等具有NP難度的組合優(yōu)化問題上取得了成功的應用。如旅行商問題，我們給定一組n個城市和他們兩兩之間的直達距離，通過遺傳算法我們可以尋找一條閉合的旅程，使得每個城市剛好經(jīng)過一次且總的履行距離最短。再如車間作業(yè)調度問題，車間作業(yè)是指利用車間資源對某一對象進行生產(chǎn)的過程，作業(yè)調度實際上就是對車間作業(yè)進行有效排序，使某個目標函數(shù)最小。比方一臺機床有多個工具，加工多種工件，各工件有確定的加工期限約束，需要制定一個月的加工計劃保證完成所有的加工任務。由于JSP具有離散、動態(tài)、多變量耦合等屬性，應用遺傳算法具有一定難度，主要體現(xiàn)在遺傳編碼方法上。返回第53頁,共97頁，星期六，2024年，5月函數(shù)優(yōu)化工程上經(jīng)常會遇到在多準則或多設計目標下設計和決策的問題，如果這些目標是相背的，需要找到滿足這些目標的最佳設計方案。通常的做法是根據(jù)某有效函數(shù)將多目標合成單一目標來進行優(yōu)化。但大多數(shù)情況下，在優(yōu)化之前這種效用函數(shù)是難以確切知道的。法國經(jīng)濟學V.Pareto(1848-1923)最早研究經(jīng)濟領域內(nèi)的多目標優(yōu)化問題，他的理論稱為Pareto最優(yōu)化理論。J.Horn和N.Nafpliotis提出了關于用遺傳算法解決多目標問題的基本算法思想，遺傳算法界稱為NPGA。返回第54頁,共97頁，星期六，2024年，5月智能控制許多控制領域問題，當考慮到系統(tǒng)優(yōu)化、自適應、自組織和自學習等方面的要求時，一般存在許多常規(guī)方法難以湊效的困難。例如，當有非連續(xù)評價函數(shù)、缺少初始信息、模型參數(shù)和結構或控制過程中的隨機性、不確定性等復雜因素出現(xiàn)時，現(xiàn)有的控制理論和方法往往因需要求導信息、對初始條件的敏感性、對高品質的領域知識依賴性而難以得到很好的應用。1971年K.S.Fu從研究自學習控制系統(tǒng)入手，將智能控制概括為自動控制與人工智能的交集；1977年，Saridis以智能機器人的控制為主要研究背景，從研究機器智能的角度提出了智能控制是自動控制、人工智能及運籌學的交集，并提出了分級遞階智能控制的結構和方法；Astrom提出的專家智能則是將專家對被控對象和控制過程的知識、經(jīng)驗等融入控制器的設計與控制決策中。早期的智能控制研究受到傳統(tǒng)控制理論的影響，大部分著眼點仍然基于系統(tǒng)已有的先驗知識來解決問題，而不是自動獲取知識。模糊控制基于模糊集理論，模擬人的近似推理和決策過程。1974年Mamdani成功地將它應用于高爐和蒸汽機的控第55頁,共97頁，星期六，2024年，5月智能控制制，隨后獲得了迅猛的發(fā)展。模糊控制的主要困難在于控制規(guī)則的獲取以及控制系統(tǒng)的穩(wěn)定性問題。20世紀80年代中期以來，神經(jīng)網(wǎng)絡得到重新重視和發(fā)展。它主要模擬人腦的形象思維以及學習獲取知識的能力。神經(jīng)網(wǎng)絡應用于控制問題，由于其高度依賴于生產(chǎn)現(xiàn)場所提供的大量訓練樣本，且訓練算法的可實現(xiàn)性、實時性要求等因素，影響了其實用性。此外，對復雜問題的神經(jīng)網(wǎng)絡結構最優(yōu)設計一直缺乏有效的方法。90年代以來，模糊理論、神經(jīng)網(wǎng)絡、專家系統(tǒng)、遺傳算法和混沌方法等在許多控制領域得到了應用和發(fā)展，并且更重視這些方法相互融合，形成所謂的混合軟計算。遺傳算法借助搜索機制的隨機性，能夠搜索問題域的全局最優(yōu)解，并且對噪聲和變化表現(xiàn)出很好的魯棒性和自適應能力。遺傳算法在控制領域的應用大致分為兩大類：一類是離線設計和分析；另一類是在線自適應性調整。前者遺傳算法作為優(yōu)化器，對于已知的控制對象尋求合適的控制規(guī)則以滿足控制品質方面的要求，或者對于特定的控制器結構搜索最優(yōu)參數(shù)。后者遺傳算法作為一種學習機制來確定未知的或非穩(wěn)定系統(tǒng)的特征，或者對控制器進行自適應性調整。返回第56頁,共97頁，星期六，2024年，5月圖像處理圖像處理和模式識別是計算機視覺中的一個重要領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會產(chǎn)生一些誤差，這些誤差會影響到圖像處理和識別的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法在圖像處理中的優(yōu)化計算方面是完全可以勝任的，目前已在圖像校準、圖像分割、幾何形狀識別、圖像壓縮、三維重建優(yōu)化以及圖像檢索等方面得到了應用。返回第57頁,共97頁，星期六，2024年，5月機器學習機器學習以復雜系統(tǒng)為對象，研究機器如何獲取新知識或改善已有知識的問題，屬于人工智能研究中較年輕的分支。由于20世紀40年代計算機的產(chǎn)生，使機器學習的實現(xiàn)有了可能，并且在50年代中期到60年代中期成了機器學習的熱烈時期，這一時期主要研究各類自適應系統(tǒng)，并已開始研究神經(jīng)網(wǎng)絡模型和人工進化系統(tǒng)。60年代中期到70年代中期轉入低潮，主要研究側重于基于概念的學習和基于歸納的學習；70年代中期到80年代中期又得到了迅速地發(fā)展，特別是專家系統(tǒng)的成功應用。不同的學習策略和各種學習方法相繼問世，示例歸約學習成為研究主流，如出現(xiàn)了影響很大的示例學習方法:ID系列和AQ系列。此外，自動知識獲取成為機器學習的應用研究目標，遺傳算法應用于機器學習的思想已經(jīng)被提出。最近10多年機器學習的研究和發(fā)展又進入了一個暫新時期。1986年，神經(jīng)網(wǎng)絡重新興起，基于連接機制的學習開始向傳統(tǒng)的符號學習挑戰(zhàn)。神經(jīng)網(wǎng)絡將知識的表達蘊涵于網(wǎng)絡連接中，處理隱層和反向傳播算法的發(fā)展，顯示出很強的學習能力，因而，廣泛應用于模式識別、自動控制、信號處理、語音識別等許多領域。隨著各種改進型學習算法不斷地被提出，顯著地改善了機器學習系統(tǒng)的性能。而此前的符號學習試圖將知識由一個知識庫包含和解釋，其學習能力非常局限，只能適用于知識表達相對簡單的系統(tǒng)。第58頁,共97頁，星期六，2024年，5月機器學習迄今，自然界只有人類才真正具有完善的學習能力，機器學習系統(tǒng)實際上是對人的學習機制的一種抽象和模擬，是一種理想的學習模型?；诜枌W習和學習系統(tǒng)如監(jiān)督型學習系統(tǒng)、條件反射型學習系統(tǒng)、類比式學習系統(tǒng)、推理學習系統(tǒng)等，只具備一些較初級的學習能力。近年來，由于遺傳算法的發(fā)展，基于進化機制的遺傳學習成為一種新機器學習方法，它將知識表達為另一種符號形式-----遺傳基因，通過模擬生物的進化過程，實現(xiàn)專門領域知識的合理增長型學習，所以有的學者將之稱為次符號學習方法。機器學習成為遺傳算法的經(jīng)典領域之一，歸功于密歇根大學Holland等早期的工作。他們將基于遺傳的機器學習方法發(fā)展成為CSI的分類系統(tǒng)學習方法，奠定了遺傳算法重要的思想基礎，后來被歸納為“密歇根方法”。1991年，DeJong等提出了“匹茨堡方法”。1994年，日本名古屋大學的市橋等結合兩種方法的優(yōu)點提出了“名古屋方法”，這些方法都分別在復雜機器學習系統(tǒng)獲得了成功的應用。此外，遺傳程序設計方法應用于機器發(fā)現(xiàn)系統(tǒng)的研究及結合不同學習方法交互作用的混合學習方法也開始受到重視。返回第59頁,共97頁，星期六，2024年，5月人工生命生物的多種特性與功能已經(jīng)給科學研究者很多啟示，人工神經(jīng)網(wǎng)絡可以說是受到人的神經(jīng)元的啟發(fā)，而遺傳算法、進化計算更是根據(jù)生物的遺傳、進化機制演變而成的。近年來，一些學者對人工生成具有生命特征的產(chǎn)物進行了多方面的研究。在早期，馮.諾依曼根據(jù)許多小單元均只與附近小單元相互作用的原則構造了元胞自動機，這種自動機可以“自繁殖”。他又指出計算機程序可以在內(nèi)存中進行自復制?，F(xiàn)在出現(xiàn)的各種計算機病毒，它們在一定的條件下可以自繁殖，甚至“進化”。各種電子寵物如“電子雞”、“電子魚”等具有類似生物的特性，例如需要按時進食，對環(huán)境可以趨利避害，有發(fā)育、生長、會生病、死亡等生物特征。這些“人工生命”可以看成一種具有生命特性的信息系統(tǒng)，相當一部分的人工生命是在計算機上實現(xiàn)的。可以認為自然界產(chǎn)生的生物是以核酸分子作為信息載體的，而生命的特征是由生物體中的信息系統(tǒng)決定的，如果把表征生命特性的信息系統(tǒng)在其它媒體上實現(xiàn)，同樣也會產(chǎn)生相應的特征。這就是人工生命的內(nèi)涵。返回第60頁,共97頁，星期六，2024年，5月2、遺傳算法的應用示例彈藥裝載問題（AmmunitionLoadingProblem，簡稱ALP），就是在滿足各類通用彈藥運輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運輸工具，使得通用彈藥的裝載效率達到最大值的問題。第61頁,共97頁，星期六，2024年，5月AGSAA的基本原理

在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應用改進型遺傳算法和模擬退火算法相結合，構建自適應遺傳模擬退火算法（AGSAA），從而綜合了全局優(yōu)化和局部搜索的特點，為解決彈藥裝載這一組合優(yōu)化問題提供了新的思路。第62頁,共97頁，星期六，2024年，5月AGSAA的編碼方式

AGSAA采用二進制編碼方式，每一個二進制位對應一個待裝彈藥箱，若為１，表示該彈藥箱裝入運輸工具，為０則不裝。第63頁,共97頁，星期六，2024年，5月AGSAA的解碼和適應度函數(shù)

AGSAA采用彈藥裝載的啟發(fā)式算法來解碼，解碼后最終確定裝入運輸工具的彈藥箱。適應度函數(shù)主要考慮兩個方面，即載重率和積載率，對這兩個因素加權，來計算適應度函數(shù)值。第64頁,共97頁，星期六，2024年，5月彈藥裝載的啟發(fā)式算法

（1）定位規(guī)則（Locatingrule）定位規(guī)則是指用來確定當前待裝彈藥箱在運輸工具剩余裝載空間中擺放位置的規(guī)則。（2）定序規(guī)則（Orderingrule）定序規(guī)則是指用來確定彈藥箱放入運輸工具裝載空間先后順序的規(guī)則。第65頁,共97頁，星期六，2024年，5月遺傳算子的選擇AGSAA的選擇算子采用輪盤賭選擇算子，并結合最優(yōu)保存策略；突變算子采用基本位突變算子；同時，在突變運算之后，增加退火算子，以增強算法的局部搜索能力；交叉概率和突變概率為自適應概率，以提高種群的進化效率。第66頁,共97頁，星期六，2024年，5月交叉算子的選擇由于AGSAA是采用將彈藥箱的編號排列成串來進行編碼的，如果個體交叉采用傳統(tǒng)方式進行，就有可能使個體的編碼產(chǎn)生重復基因（即一個彈藥箱編號在一個個體中出現(xiàn)兩次以上），從而產(chǎn)生不符合條件的個體，因此，AGSAA采用的是部分映射交叉算子。

第67頁,共97頁，星期六，2024年，5月部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345返回第68頁,共97頁，星期六，2024年，5月關于遺傳算法應用方面我的研究1、基于遺傳算法的提高排課滿意度的研究（計算機應用研究中國計算機學會會刊2007年增刊電腦知識與技術.學術交流2007/09）2、基于遺傳算法的虛擬物體的變形研究(計算機應用與軟件中國計算機學會會刊錄用待發(fā))3、計算機遺傳病毒染毒機理分析(計算機應用與軟件中國計算機學會會刊2008/08)4、倒立擺的混合控制（審稿階段）5、基于GA和滑?？刂频墓β士刂破鞯脑O計與仿真（審稿階段）6、基于遺傳算法的智能化動態(tài)分組的研究（2008年山西省教育廳研究課題）返回第69頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

染色體結構染色體結構如右圖上所示。該染色體含有m個基因，m的個數(shù)即是參與授課教師的總人數(shù)，每一個基因代表每位教師的課表，每一染色體即表示一種可能的排課結果。每位教師課表可用一維字符陣列表示。如右圖下所示。例如：某一教師星期2第3大節(jié)要配置“微機原理”課程，字符陣列即可表示為：demo(23)=”微機原理”結合所有的染色體及所有的教師人數(shù)和上述的一維字符陣列，可成為一個三維陣列，即（染色體編號、教師編號、教師課表）。例如：第５染色體的第８位教師，于星期二第３大節(jié)課要配置“微機原理”課程，字符陣列可表示為demo(5,8,23)=”微機原理”以教師的課表為基因單位，兩染色體經(jīng)交叉操作后基因互換，不會影響到每位教師所教授的課程，也不會造成教師課表內(nèi)含有其他教師的教授課程，不會出現(xiàn)每代演化后課表染色體結構不合理的問題。第70頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

適應性函數(shù)適應性函數(shù)是計算出每條染色體的適應值。在本研究中，染色體若其適應值較大者，表示該排課結果擁有較多較佳授課時段，將會被給予較大的生存概率于下一代演化中。首先建立每位教師的授課時段優(yōu)先度，如表1所示，可由教師填入自己較喜歡的時段及其喜好程度，該表格將提供做適應性使用，其中3代表最喜歡的授課時段，2代表較喜歡的授課時段，1代表喜歡的授課時段，空白代表可以接受的授課時段，-1代表不喜歡的授課時段。在演化過程中，應盡量避免-1所代表的時段，以避免教師不愿授課。將染色體中每個基因（教師課表）與教師時段喜好表比較，取相對應位置的值相加，如此累計計算出整條染色體的值。染色體函數(shù)計算所得的適應值也越大。第71頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

選擇選擇就是將較大適應值的染色體復制到交叉池中。本文采用隨機競爭法，即由上一代隨機選取兩條染色體來競爭，適應值較大的即可生存下來。此方法的優(yōu)點是不影響競爭概率。第72頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

交叉交叉是以每位教師課程表為基因單位，進行隨機交換。方法是隨機自交叉池里選取一對染色體作為進行交叉的雙親，并再取一亂數(shù)值（設為r），與系統(tǒng)預設的交叉率值（設為t）比較，若r<t即進行交換基因。第73頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

突變突變是隨機改變?nèi)我唤處煹囊皇谡n時段，將教師課表的時段以亂數(shù)方式?jīng)Q定是否要搬移與搬移到何處。當取出的亂數(shù)值小于系統(tǒng)預設的突變率時，即進行交叉，并隨機決定新的位置，如圖6所示。例如：將第5條染色體的第8位教師的星期2第3大節(jié)課的“微機原理”搬到星期3的第一大節(jié)課，可表示為：demo(5,8,31)=demo(5,8,23)demo(5,8,23)=””。第74頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

演化流程圖

第75頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

實驗結果在研究中，以數(shù)種不同交叉率及突變率來進行演化模型。我們設交叉率為0.5，突變率分別為0.01、0.03、0.05為例，每項各執(zhí)行10次，再求取平均數(shù)，如下表所示。其次，以突變率為0.01，交叉率分別為0.6、0.7、0.8為例，每項各執(zhí)行10次，再求取其平均數(shù)，如下表所示。第76頁,共97頁，星期六，2024年，5月基于遺傳算法的提高排課滿意度的研究

實驗結果圖是適應函數(shù)值在演化過程中的變化，演化100代，染色體50條，突變率0.5，交叉率為0.01。圖中綠色代表可行染色體中的最佳值，紅色代表世代最佳值，藍色代表世代平均值，黑色代表世代最佳值。返回第77頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

虛擬物體的初始建構

為使虛擬物體能利用虛擬物體變形，首先需要進行初始建構。本系統(tǒng)初始建構的方法是：將虛擬物體依一定之次序切割成9個不同的截面?？紤]到繪圖面的彈性與控制點的密度，將控制每個截面外形的控制點數(shù)目設定為12點，并應用曲線配合方式使控制點位于截面線上。如圖1。調整各截面的大小，再調整各截面的位置，如圖2所示。再將各截面連接，完成演變前的初始狀態(tài)。如圖3：第78頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

虛擬物體形變的規(guī)則

本系統(tǒng)以各截面為形變的基礎，采用數(shù)列這種數(shù)學模型進行形變。2．1等差數(shù)列以其項數(shù)為橫軸，各項的值為縱軸。2．2等差級數(shù)以其項數(shù)為橫軸，各項的和為縱軸。本系統(tǒng)是對欲形變的截面做縮放或空間位置的變化，而各截面的縮放或位移，則透過等差數(shù)列或等差級數(shù)來進行造型變化。開始形變截面的大小與空間位置為“首項”，而開始形變到終止形變之間n個截面的縮放比例與位移距離為數(shù)列中的各項值，形變方式即透過等差數(shù)列或等差級數(shù)的計算，將第n個截面（即數(shù)列中的第n項）的縮放值與位移距離計算出，得到該截面在空間上的大小與應位移的距離，以此類推，將其他各截面的大小與空間位置推出，建構變形后的造型。2．3數(shù)列計算運用于造型形變分別對造型中的主截面進行x、y軸項的比例縮放或x、y軸向的位置變化，再進行主截面與主截面間的形體漸變，分大小與位移漸變，大小漸變，是指兩個主要截面之間有大小的差異，漸變時，會由一個主截面的大小漸變到另一個主截面的大小。而位移漸變，是指兩個主要截面與z軸距離值的差異，漸變時，會由一個主截面與z軸的x、y距離值增減到另一個主截面與z軸的x、y距離。第79頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

遺傳算法的應用染色體本系統(tǒng)采用實數(shù)型方式，各截面的位移和縮放采用等差數(shù)列或等差級數(shù)。以（ABCDEFGH）代表染色體的各個基因。編碼如表1：第80頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

遺傳算法的應用適應函數(shù)本系統(tǒng)采用符合虛擬物體功能需求為評判機制，以虛擬物體變形后空間大小接近原虛擬物體內(nèi)部體積為選擇方式，建立適應函數(shù)，以使虛擬物體變形后有足夠體積容納內(nèi)部物質。適應函數(shù)為：F1=|(AP+AQ)×h/2-S|（１）其中F1：適應函數(shù)AP：虛擬物體前端的面積AQ：虛擬物體后端的面積h：P、Q截面的距離3．3選擇隨機的從空間座標中挑選2條染色體，然后各計算兩條染色體的適應函數(shù)值，比較計算結果若都比前一代演算結果佳(適應值高)，就進行下一個步驟，若有一條染色體沒有前一代佳就再選取，直到兩條染色體的適應值都比前一代高就進行下一個步驟。第81頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

遺傳算法的應用3．4交叉交叉是將選取出的兩條染色體依交叉點做基因交換，若比系統(tǒng)所定的交叉率低的可進行交叉。本系統(tǒng)采用成功率較高的交叉率80%來進行。而交叉方式，則采用單一交叉的方式進行。若染色體之交叉率低于80%，且隨機選取基因1與基因2之間作為交叉點，交叉方式如圖4。第82頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

遺傳算法的應用突變突變是隨機選擇出染色體基因，做基因數(shù)值上的增減，突變的發(fā)生根據(jù)染色體的突變率而定。本系統(tǒng)設定為20%，只要染色體所產(chǎn)生的突變率小于20%就會突變。而突變方式，采用單點突變的方式進行，先隨機選取基因3為突變點，并隨機產(chǎn)生增減值1。原則上，增減后不超過基因規(guī)定的范圍，超過后以最接近的基因規(guī)定范圍內(nèi)的值代替。如圖5。第83頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

遺傳算法的應用3．6適應度比較選擇、交叉或突變完后，計算各子代的適應函數(shù)值，將適應函數(shù)值較優(yōu)且比前一代適應值優(yōu)良的子代留下，作為下一次運算選取步驟中，染色體選擇的比較基準。3．7替換、再循環(huán)留下子代中適應值最大且前一代適應值優(yōu)良的子代，并進行下一次的選擇、交叉、突變。3．8演變完成的條件當前一代的適應值與本代的適應值的差距很小，幾乎不改變時，表示前一代與本代相差不大，演變完成。演變完成的條件：E=|fl-1-fl|/fl<ε（２）E：適應函數(shù)的最終判斷函數(shù)

S：虛擬物體體積大小fl：第l代適應函數(shù)的值fl-1：第l-1代適應函數(shù)的值第84頁,共97頁，星期六，2024年，5月基于遺傳算法的虛擬物體的變形研究

結論返回第85頁,共97頁，星期六，2024年，5月算機遺傳病毒染毒機理分析第86頁,共97頁，星期六，2024年，5月防毒與解毒方法2.1防毒（1）掃描對比法掃描對比法是依據(jù)先前建立好的病毒特征碼去判斷病毒,依照病毒某些固定不變的特征,制作成病毒特征碼。這種方法的優(yōu)點是可以準確判斷出已知的病毒,準確率很高。缺點是需要時刻更新病毒特征碼,否則無法對抗新病毒。（2）加總查核法加總查核法是根據(jù)檔案本身的特征屬性（如檔名、檔案大小、存檔日期時間,或檔案內(nèi)容依照特定演算法產(chǎn)生識別）,利用這些特征屬性來產(chǎn)生檢查碼。此種方法的優(yōu)點是可以確保此檔案不遭到病毒的更改,保持其完整性。缺點是檔案只要一經(jīng)正常使用修改后,都需重新制作檢查碼,不利于經(jīng)常更新的檔案，且制作檢查碼前須確定檔案未遭受病毒感染。（3）行為模式偵測法行為模式偵測法是依照程式的行為模式,來辨別該程式是否為病毒。從而分析計算機系統(tǒng)中一些不正常的行為指令,來防治一些危險性的行為,此種方法常用來對付多形病毒和會自我編碼的病毒。此種方法的優(yōu)點是可預防行為模式類似的變種病毒或未知病毒。缺點是很難定義出絕對危險或絕對安全的行為模式,也有可能攔截下具特殊功能的正常程式。第87頁,共97頁，星期六，2024年，5月防毒與解毒方法（4）虛擬機器模擬法除了上述的行為模式偵測法可以用于對付多形病毒和會自我編碼的病毒外,另一種方法就是使用虛擬機器模擬法。此種方法主要通過虛擬機器來模擬產(chǎn)生執(zhí)行環(huán)境,再使用假執(zhí)行將已加密過的病毒解密后,配合使用掃描對比病毒特征碼等其他方法來發(fā)現(xiàn)病毒。此方法的優(yōu)點是可以完全解開多形和會編碼的病毒保護功能,使其無所遁形。缺點是會嚴重地耗用系統(tǒng)資源,將許多時間花費在虛擬執(zhí)行上。2.2解毒工作原理解毒最主要的功能就是清除病毒,將磁道或檔案恢復成未受病毒感染的狀態(tài)。以引導區(qū)病毒為例,原始引導區(qū)的信息被搬移至別處,而病毒寫入該引導區(qū)。此種病毒的解毒原理即是將被搬移的原始引導區(qū)信息,重新搬回引導區(qū)內(nèi)并覆蓋病毒。檔案型病毒是在原始文件中加入有毒宏指令,從而感染文件,而此種病毒的解毒原理則為將有毒宏從中毒文件中移除,回復原始文件。第88頁,共97頁，星期六，2024年，5月研究方法和研究模型從過去計算機病毒與防毒軟件的發(fā)展史來說,早期傳統(tǒng)的防毒軟件要正確地找出病毒,都是通過掃描對比固定的病毒特征碼,從病毒特征去判斷程式是否已被感染。但是傳統(tǒng)的防毒方法對于多形病毒和病毒產(chǎn)生器則無所適從。因為多形病毒有賦予病毒改變外貌的能力,以躲避防毒軟件的掃描對比,通過不同的編碼技術或參數(shù),讓被感染的檔案里找不到相同的病毒特征碼。病毒產(chǎn)生器則是根據(jù)病毒作者的需求,在功能選單上以勾選的方式選擇,依亂數(shù)選取模組來產(chǎn)生病毒。這種產(chǎn)生病毒的方式,可造就出與眾不同的病毒,并且能很容易產(chǎn)生出許多不同功能類型的新病毒。因此我們試圖探討是否存在一種方式,能夠結合前述的多形病毒與病毒產(chǎn)生器的優(yōu)點,讓病毒在數(shù)字世界里,提高其生存機率,而遺傳算法似乎正好具備有此種能力,在未來病毒的演進中,若結合遺傳算法來遂行其永續(xù)存活的理想,將可能造成防毒或是消毒的工作負擔。第89頁,共97頁，星期六，2024年，5月遺傳算法根據(jù)遺傳算法的原理我們讓原本一成不變的病毒能夠改變自己。這種改變不是某種外貌或編碼方式的改變,而是進行病毒本體的實質更新。本文試圖建立一組新的病毒核心,讓這個核心采用遺傳算法的原則,實現(xiàn)演變工程。當然要特別強調的是,本文是對這個核心提出設計概念,并非要將固定的指令碼一陳不變式地寫入核心內(nèi)。在遺傳算法的選擇、交叉、變異的操作步驟下,病毒的演變將會很類似自然界的行為法則。病毒的最主要目的,就是希望“存