遺傳算法原理

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

2、基本遺傳算法

3、遺傳算法的特點(diǎn)

第3頁,共97頁，星期六，2024年，5月1、智能優(yōu)化算法智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(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)化算法的特點(diǎn)它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。返回第6頁,共97頁，星期六，2024年，5月遺傳算法起源遺傳算法是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。第7頁,共97頁，星期六，2024年，5月遺傳算法的搜索機(jī)制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和突變)對這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。

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

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

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

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

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

3、遺傳算法的改進(jìn)

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

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

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

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

第46頁,共97頁，星期六，2024年，5月對遺傳算子的改進(jìn)排序選擇均勻交叉逆序突變突變前：348|7965|21突變后：348|5697|21第47頁,共97頁，星期六，2024年，5月對控制參數(shù)的改進(jìn)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ù)的改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動(dòng)改變，當(dāng)種群的各個(gè)個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使二者增加，而當(dāng)種群適應(yīng)度比較分散時(shí)，使二者減小，同時(shí)對適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，采用較低的PC和Pm，使性能優(yōu)良的個(gè)體進(jìn)入下一代，而低于平均適應(yīng)值的個(gè)體，采用較高的PC和Pm，使性能較差的個(gè)體被淘汰。第49頁,共97頁，星期六，2024年，5月對執(zhí)行策略的改進(jìn)混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法返回第50頁,共97頁，星期六，2024年，5月三、遺傳算法的應(yīng)用1、遺傳算法的應(yīng)用領(lǐng)域

2、遺傳算法的應(yīng)用示例

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

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

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

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

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

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

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

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

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

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

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

演化流程圖

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

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

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

虛擬物體的初始建構(gòu)

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

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

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

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

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

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

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

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

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

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