大學(xué)計算機怎樣研究算法遺傳算法研究示例

大學(xué)計算機-計算思維導(dǎo)論2013-2014ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology戰(zhàn)德臣哈爾濱工業(yè)大學(xué)教授.博士生導(dǎo)師教育部大學(xué)計算機課程教學(xué)指導(dǎo)委員會委員第9講怎樣研究算法：遺傳算法示例2013-2014ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology戰(zhàn)德臣哈爾濱工業(yè)大學(xué)教授.博士生導(dǎo)師教育部大學(xué)計算機課程教學(xué)指導(dǎo)委員會委員第9講怎樣研究算法：遺傳算法示例什么是可求解與難求解問題?難解性問題的基本求解思路是什么?如何類比自然界生物求解問題的思想，設(shè)計計算類問題的求解算法?難解性問題算法計算怎樣研究算法：遺傳算法示例1.可求解與難求解問題可求解與難求解問題----計算復(fù)雜性----P類問題、NP類問題和NPC類問題----NPC類問題的求解思路現(xiàn)實世界中的問題分類1.可求解與難求解問題1.1什么是可求解與難求解問題?計算機在有限時間內(nèi)能夠求解的(可求解問題)計算機在有限時間內(nèi)不能求解的(難求解問題)計算機完全不能求解的(不可計算問題)計算復(fù)雜性是指問題的一種特性，即利用計算機求解問題的難易性或難易程度，其衡量標準：計算所需的步數(shù)或指令條數(shù)(即時間復(fù)雜度)計算所需的存儲空間大小(即空間復(fù)雜度)----通常表達為關(guān)于問題規(guī)模n的一個函數(shù)O(f(n))問題的計算復(fù)雜性1.可求解與難求解問題1.2什么是有限時間內(nèi)不能求解?問題規(guī)模n計算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒41028秒=1015年注：每秒百萬次，n=60，1015年相當于10億臺計算機計算一百萬年O(n3)與O(3n)的差別，O(n!)與O(n3)的差別O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)1.可求解與難求解問題1.3怎樣以復(fù)雜性來劃分問題?P類問題，NP類問題，NPC類問題P類問題：多項式問題(PolynomialProblem)，指計算機可以在有限時間內(nèi)求解的問題，即：P類問題是可以找出一個呈現(xiàn)O(na)復(fù)雜性算法的問題，其中a為常數(shù)。NP類問題：非確定性多項式問題(Non-deterministicPolynomial)。有些問題，其答案是無法直接計算得到的，只能通過間接的猜算或試算來得到結(jié)果，這就是非確定性問題(Non-deterministic)。雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性的問題，即：在多項式時間內(nèi)可以由一個算法驗證一個解是否正確的非確定性問題，就是NP類問題。NPC問題：完全非確定性多項式問題(NP-Complete)。如果NP問題的所有可能答案都可以在多項式時間內(nèi)進行正確與否的驗算的話就叫做完全非確定性多項式問題，即NP-Complete問題。問：加密算法應(yīng)該設(shè)計成一個什么問題呢？1.可求解與難求解問題1.4NPC類問題如何求解?NPC類問題求解窮舉法或稱遍歷法：對解空間中的每一個可能解進行驗證，直到所有的解都被驗證是否正確，便能得到精確的結(jié)果---精確解可能是O(n!)或O(an)近似解求解算法---近似解應(yīng)該是O(na)?=|近似解–精確解|滿意解：?充分小時的近似解TSP問題的遍歷算法TSP問題的貪心算法仿生學(xué)算法進化算法，遺傳算法，蟻群算法，蜂群算法,…怎樣研究算法：遺傳算法示例2.遺傳算法的緣起--生物學(xué)中的遺傳與進化遺傳算法的緣起--生物學(xué)中的遺傳與進化2.遺傳算法的緣起--生物學(xué)中的遺傳與進化2.1生物體中是怎樣遺傳的?生物學(xué)中的遺傳和進化關(guān)于生物遺傳進化的基本觀點(i)生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀；(ii)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進化過程發(fā)生在染色體上；(iii)生物的繁殖過程是由其基因的復(fù)制過程來完成的；(iv)通過同源染色體之間的交叉或染色體的變異會產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(v)對環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機會遺傳到下一代。遺傳與進化優(yōu)勝劣汰2.遺傳算法的緣起--生物學(xué)中的遺傳與進化2.2生物體遺傳與進化的過程是怎樣的?生物學(xué)中的遺傳和進化2.遺傳算法的緣起--生物學(xué)中的遺傳與進化2.3什么是染色體和基因，它們與遺傳有什么關(guān)系?生物學(xué)中的遺傳和進化基本概念種群(Population)

vs.個體(Individual)

vs.染色體(chromosome)染色體(chromosome)vs.基因(gene)基因型(Genotype)vs.表現(xiàn)型(Phenotype)個體的適應(yīng)度(Fitness)選擇(Selection)復(fù)制((Reproduction)交配/雜交(Crossover)突變(Mutation)怎樣研究算法：遺傳算法示例3.計算學(xué)科的遺傳算法計算學(xué)科的遺傳算法3.計算學(xué)科的遺傳算法3.1怎樣用遺傳算法求解問題?一個簡單的遺傳算法應(yīng)用示例求多項式函數(shù)的最小值：

MinF(X)=X2-19X+20,其中X=1,…,64之間的整數(shù)。注：此題不難求出精確解，其精確解為X=9或者X=10。

如何用遺傳算法進行求解?3.計算學(xué)科的遺傳算法3.2生物學(xué)中的概念如何與計算學(xué)科中的概念映射?生物學(xué)中的概念與計算學(xué)科中的概念映射生物學(xué)中的概念計算學(xué)科中的概念解釋種群解集/種群若干可能解的集合個體解/個體一個可能解的表現(xiàn)型，本例中即是十進制的X染色體編碼解/染色體一個可能解的基因型，本例即是X的二進制編碼。X=b6b5b4b3b2b1，其中bi=0或1?；蚧蚪饩幋a中的若干位的bi適應(yīng)度適應(yīng)度一個可能解接近最優(yōu)解的一個度量，本例直接用F(X)作為其適應(yīng)度的度量，其值越小越接近最優(yōu)解選擇選擇指從種群(解集)中依據(jù)適應(yīng)度按某種條件選擇某些個個體(可能解)復(fù)制復(fù)制將一個解從一個解集復(fù)制到另一個解集交配/雜交交叉即交配/雜交，是新可能解的一種形成方法，即是對兩個可能解的編碼通過交換某些編碼位而形成兩個新的可能解的遺傳操作突變變異也是新可能解的一種形成方法，它是通過隨機地改變一個可能解的編碼的某些片段(或基因)而使一個可能解變?yōu)橐恍碌目赡芙獾倪z傳操作3.計算學(xué)科的遺傳算法3.3怎樣模擬遺傳算法進行求解?遺傳算法求解過程的模擬3.計算學(xué)科的遺傳算法3.4如何設(shè)計遺傳算法?遺傳算法基本框架及其設(shè)計要點begin/*遺傳算法*/ t←0；/*進化的種群代數(shù)*/

生成初始種群P(t)；

計算初始種群P(t)中每個個體的適應(yīng)值；

while（不滿足終止條件）do/*利用下述操作生成新個體，并選擇更優(yōu)個體組成新種群*/ (1)通過復(fù)制、交叉或變異操作重組種群P(t)中 的個體，產(chǎn)生新個體，形成候選種群C(t)；/*注意此處C(t)并未包含P(t)中的個體*/

(2)計算C(t)中每個個體的適應(yīng)值；

(3)根據(jù)適應(yīng)值從C(t)和P(t)中選擇更優(yōu)的個體 組成新種群P(t+1)； (4)t←t+1；

endwhile

選擇P(t)中最優(yōu)個體為所求的解；endbegin怎樣研究算法：遺傳算法示例4.遺傳算法為什么可以求解NPC問題遺傳算法為什么可以求解NPC問題4.遺傳算法為什么可以求解NPC問題4.1遺傳算法的本質(zhì)是什么?遺傳算法的基本思想(a)窮舉，遍歷搜索所有,可找到精確解窮舉法或稱遍歷法：對解空間中的每一個可能解進行驗證，直到所有的解都被驗證是否正確，便能得到精確的結(jié)果---精確解可能是O(n!)或O(an)NPC問題理論上可通過枚舉-驗證的遍歷算法來實現(xiàn)4.遺傳算法為什么可以求解NPC問題4.1怎樣用遺傳算法求解問題?遺傳算法的基本思想(b)完全隨機搜索隨機點之間完全沒有聯(lián)系隨機搜索法：在解空間中隨機選擇一些可能解進行驗證，求出所選擇可能解(子解空間)中的最優(yōu)解---近似解基于概率論：隨機選擇子解空間越大，求得滿意解的可能性越大，但耗時也會加長求出的近似解并不能保證是滿意解不求精確解，而求近似解-滿意解，可采取隨機搜索方法(c)導(dǎo)向性隨機搜索隨機點之間形成一路徑4.遺傳算法為什么可以求解NPC問題4.1怎樣用遺傳算法求解問題?遺傳算法的基本思想導(dǎo)向性隨機搜索法：對隨機點的選取進行導(dǎo)向(導(dǎo)向到接近最優(yōu)解的方向或路徑)

基于概率論：隨機選擇隨機選擇的可能解與前一可能解相比，更偏向于滿意解萬一初始解就很差怎么辦?為提高近似解的質(zhì)量，可采取導(dǎo)向性隨機搜索方法4.遺傳算法為什么可以求解NPC問題4.1怎樣用遺傳算法求解問題?遺傳算法的基本思想(d)導(dǎo)向性群(體)隨機搜索多隨機點同步進行導(dǎo)向性搜索導(dǎo)向性群(體)隨機搜索法：通時對多個隨機點的選取進行導(dǎo)向(導(dǎo)向到接近最優(yōu)解的方向或路徑)，多條搜索路徑

基于概率論：隨機選擇多條路徑下的最優(yōu)，總比一條路徑的最優(yōu)要更優(yōu)一些。遺傳算法就是這樣一種導(dǎo)向性群隨機搜索算法。同一時刻多條路徑上的解集合即為一個種群。多次選擇，即多代進化。為進一步提高近似解的質(zhì)量，可采取導(dǎo)向性群(體)隨機搜索方法4.遺傳算法為什么可以求解NPC問題4.2什么情況下可用遺傳算法求解問題?遺傳算法的適用條件對于NP問題，當沒有其他更好的算法可以使用時，可以考慮選擇遺傳算法。遺傳算法的適用條件：(1)已知“解空間”，即可能解的表現(xiàn)型和基因型(2)關(guān)于可能解的“適應(yīng)度”函數(shù)的計算方法(適應(yīng)度用于判斷一個可能解接近精確解的程度或方向)。遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架。怎樣研究算法：遺傳算法示例5.怎樣用遺傳算法求解應(yīng)用問題怎樣用遺傳算法求解具體的應(yīng)用問題(I)----問題理解與分析建模----面向應(yīng)用的遺傳算法設(shè)計要點----可能解編碼方案的多樣性----交叉/變異規(guī)則的多樣性與隨機性----遺傳算法設(shè)計的其他方面----仍需要思考的5.怎樣用遺傳算法求解應(yīng)用問題5.1你能舉出一些需要求解的現(xiàn)實問題嗎?現(xiàn)實世界的幾個具體問題分析例1：“會議室”租用問題例2：“航班機組成員”選擇問題例3：“軟件測試用例”選擇問題

其實它們是同一個問題：一維的集覆蓋問題約束矩陣<x1,x2,…,xn>aij5.怎樣用遺傳算法求解應(yīng)用問題5.2例4和例1,2,3有何不同?例4“課程表”優(yōu)化問題有8門課程需要安排教室，記為Li，i=1,…,8；有6個教室可被使用，記為Rj，j=1,…,6；要求每門課只能安排在一個教室，而每個教室最多只能安排兩門課。教室與課程班之間的約束矩陣A如下表給出，其中aij=1表示該課程班可以安排在該教室，aij=0則不可安排。費用為教室容納人數(shù)/課程班人數(shù)，即Cij=Kj/Li。約束矩陣5.怎樣用遺傳算法求解應(yīng)用問題5.2例4和例1,2,3有何不同?例1，例2，例3例4一維集覆蓋問題二維集覆蓋問題使每一行都被選出的列覆蓋，被哪一列或幾列覆蓋不重要，要滿足約束矩陣使每一行都確定安排在某一列上，使被選中的行-列覆蓋所有的行，要滿足約束矩陣可能解是一維向量可能解是二維矩陣<x1,x2,…,xn>怎樣研究算法：遺傳算法示例5.怎樣用遺傳算法求解應(yīng)用問題怎樣用遺傳算法求解具體的應(yīng)用問題(II)----問題理解與分析建模----面向應(yīng)用的遺傳算法設(shè)計要點----可能解編碼方案的多樣性----交叉/變異規(guī)則的多樣性與隨機性----遺傳算法設(shè)計的其他方面----仍需要思考的5.怎樣用遺傳算法求解應(yīng)用問題5.3遺傳算法的設(shè)計要點是什么?NPC求解:產(chǎn)生一個或一批可能解判斷可能解是否是問題的解可能解的形式是怎樣的?怎樣產(chǎn)生待判定的可能解?產(chǎn)生多少個待判定可能解?怎樣判定一個解是否是所求的解?解的表現(xiàn)型和基因型交叉、變異隨機(概率)解集的規(guī)模進化的代數(shù)隨機(概率)適應(yīng)度選擇(標準)滿意解遺傳算法設(shè)計要點5.怎樣用遺傳算法求解應(yīng)用問題5.3遺傳算法的設(shè)計要點是什么?一組關(guān)于解的概念需要區(qū)分假設(shè)一個問題的解的形式為x，由x的取值空間或定義域給定的任何一個x值被稱為可能解而一個問題通常有很多個關(guān)于可能解的約束，即不是任何一個x值都滿足約束，我們可將滿足問題約束的那些x值稱為可行解而由一個算法在任何一組可行解中求出的最優(yōu)解被稱為是近似解而符合用戶期望的近似解被稱為是滿意解所有可行解中的最優(yōu)解是問題的最優(yōu)解?！翱赡芙饧稀薄翱尚薪饧稀薄敖平饧稀薄皾M意解集合”“最優(yōu)解集合”<x1,x2,…,xn>實際問題分析:解的形式,解的約束,解空間問題解的編碼與解碼規(guī)則設(shè)計:個體(解)的表現(xiàn)型與基因型的變換函數(shù)初始種群的規(guī)模與生成規(guī)則設(shè)計種群個體的適應(yīng)度函數(shù)設(shè)計遺傳規(guī)則的設(shè)計：交叉、變異終止條件及最終解產(chǎn)生繁衍種群的策略設(shè)計解的滿意度評估,算法效率的評估以及算法的改進優(yōu)質(zhì)個體的選擇(汰選)方法設(shè)計5.怎樣用遺傳算法求解應(yīng)用問題5.3遺傳算法的設(shè)計要點是什么?遺傳算法設(shè)計要點5.怎樣用遺傳算法求解應(yīng)用問題5.4為什么要考慮解的形式與解的編碼?x11x12…x1nx21x22…x2n………xm1xm2…xmn可能解的一般形式課程教室Xij=1課程i被安排在教室j;=0課程未被安排在教室j000010010000100000000100010000100000000100000010可行解1100000001000000010000100010000100000000100010000可行解2例4問題的解的形式(表現(xiàn)型)與編碼(基因型)5.怎樣用遺傳算法求解應(yīng)用問題5.4為什么要考慮解的形式與解的編碼?行優(yōu)先編碼:課程分段編碼,一門課程相關(guān)的劃為一段，有多少課程就有多少段列優(yōu)先編碼:教室分段編碼,一個教室相關(guān)的劃為一段，有多少教室就有多少段針對具體問題，可以有不同的編碼方案不同的編碼方案，交叉、變異的規(guī)則也可能不同例4問題的解的形式(表現(xiàn)型)與編碼(基因型)怎樣研究算法：遺傳算法示例5.怎樣用遺傳算法求解應(yīng)用問題怎樣用遺傳算法求解具體的應(yīng)用問題(III)----問題理解與分析建模----面向應(yīng)用的遺傳算法設(shè)計要點----可能解編碼方案的多樣性----交叉/變異規(guī)則的多樣性與隨機性----遺傳算法設(shè)計的其他方面----仍需要思考的5.怎樣用遺傳算法求解應(yīng)用問題5.5為什么要設(shè)計交叉規(guī)則?怎樣交叉?010101101010010101101010交叉010101101010010101101010交叉點010101101010010101101010交叉010101101010010101101010遺傳算法的交叉規(guī)則設(shè)計產(chǎn)生新的待判定的可能解

交叉兩段交叉是否只有這一種交叉方案呢?兩段交叉，一個染色體被分成兩段，兩個染色體的同位置段進行交叉重組010101101010010101101010交叉0101011010100101011010101-2段交叉點2-3段交叉點距離1-2段交叉點2-3段交叉點距離等距離多段交叉5.怎樣用遺傳算法求解應(yīng)用問題5.5為什么要設(shè)計交叉規(guī)則?怎樣交叉?010101101010010101101010交叉010101101010010101101010產(chǎn)生新的待判定的可能解

交叉等距離多段交叉多段交叉，一個染色體被分成多段，兩個染色體的同位置段進行交叉重組遺傳算法的交叉規(guī)則設(shè)計010101101010010101101010交叉0101011010100101011010101-2段交叉點2-3段交叉點距離010101101010010101101010交叉0101011010100101011010101-2段交叉點2-3段交叉點距離不等距離多段交叉5.怎樣用遺傳算法求解應(yīng)用問題5.5為什么要設(shè)計交叉規(guī)則?怎樣交叉?產(chǎn)生新的待判定的可能解

交叉不等距離多段交叉多段交叉，一個染色體被分成多段，兩個染色體的同位置段進行交叉重組遺傳算法的交叉規(guī)則設(shè)計5.怎樣用遺傳算法求解應(yīng)用問題5.5為什么要設(shè)計交叉規(guī)則?怎樣交叉?結(jié)合具體問題的解的編碼方式交叉:點交叉、行交叉、列交叉、塊交叉行交叉是指對兩個染色體同位置的兩個課程段基因進行交叉重組列交叉是指對不同段的相同位置的兩個染色體的基因進行交換塊交叉則是對兩個染色體的任何位置的兩個塊基因進行交換點交叉則是對兩個染色體按某一概率交換其位基因交叉操作本質(zhì)上是一種組合，其組合所形成的可能解空間依然是龐大的，難以確定性的遍歷每個組合。基于概率的隨機處理方法也是遺傳算法的核心處理機制交叉概率：在一個群體中，個體被選擇出進行交叉的概率交叉點的選擇：可通過隨機方式產(chǎn)生子空間中的待判定解的選擇：可通過隨機方式產(chǎn)生5.怎樣用遺傳算法求解應(yīng)用問題5.6你體會到為什么要交叉以及怎樣交叉重組的多樣性了嗎?交叉與隨機010101101010010101101010交叉010101101010010101101010交叉點總計12個,取幾個?種群(1)種群中個體的配對分組問題，即哪兩個個體進行配對交叉；(2)兩段交叉中交叉點位置的選擇；(3)多段交叉中的交叉點距離的變化與不變，即兩個或多個交叉點間等距離和不等距離的多段選擇問題；(4)結(jié)合問題解編碼的交叉與隨機策略；5.怎樣用遺傳算法求解應(yīng)用問題5.6你體會到為什么要交叉以及怎樣交叉重組的多樣性了嗎?交叉與隨機交叉組合產(chǎn)生新可能解的方式是變化多樣的010101101010001000111001010101101010種群(解集)010101101010001000111001001000111001繁衍:交叉交叉交叉交叉操作I：點交叉設(shè)P1和P2表示兩個n位的父代染色體，f(P1)和f(P2)分別表示兩個父代的適應(yīng)值，C表示子代染色體。點交叉操作如下： step1:i=1 step2:如果P1[i]=P2[i]，則C[i]=P1[i]=P2[i] step3:如果P1[i]P2[i]，則 step3.1:以概率p=f(P1)/(f(P1)+f(P2))讓C[i]:=P1[i] step3.2:以概率1-p讓C[i]:=P2[i] step4:如果i=n，停止；否則i=i+1，返回step25.怎樣用遺傳算法求解應(yīng)用問題5.7怎樣將隨機和交叉結(jié)合在一起呢?交叉與隨機交叉策略按前述的各種策略進行，每一種策略都是一子解空間。隨機可依據(jù)問題選擇不同的概率模型，進行處理。概率模型的不同、交叉策略選擇的不同構(gòu)成了豐富多彩的遺傳算法5.怎樣用遺傳算法求解應(yīng)用問題5.7怎樣將隨機和交叉結(jié)合在一起呢?交叉與隨機交叉操作II：行交叉

設(shè)P1和P2表示兩個k*h位的父代染色體，其中k為每一段的位數(shù)，h為染色體的分段數(shù)目，f(P1)和f(P2)分別表示兩個父代的適應(yīng)度值，C表示子代染色體。 step1:產(chǎn)生一個0至h-1的隨機數(shù)x；

step2:如果P1[x*k+i]=P2[x*k+i]foralli=1,…,k，則不產(chǎn)生后代；

step3:如果P1[x*k+i]P2[x*k+i]foranyi=1,…,k，則以概率p=f(P1)/(f(P1)+f(P2))讓P1[x*k+i]與P2[x*k+i]fori=1,…,k交換；//注：兩個染色體的x段如相同,則不交換,否則以概率p進行交換。5.怎樣用遺傳算法求解應(yīng)用問題5.7怎樣將隨機和交叉結(jié)合在一起呢?交叉與隨機交叉操作III：列交叉

設(shè)P1和P2表示兩個k*h位的父代染色體，其中k為每一段的位數(shù)，h為染色體的分段數(shù)目，f(P1)和f(P2)分別表示兩個父代的適應(yīng)度值，C表示子代染色體。 step1:產(chǎn)生一個0至k-1的隨機數(shù)x；

step2:如果P1[i*k+x]=P2[i*k+x]foralli=1,…,h，則不產(chǎn)生后代； step3:如果P1[i*k+x]P2[i*k+x]foranyi=1,…,h，則以概率f(P1)/(f(P1)+f(P2))讓P1[i*k+x]與P2[i*k+x]交換foralli=1,…h(huán)；//注：兩個染色體的各段的x位如都相同，則不交換，否則以概率p進行交換。交叉策略比較：“點交叉”將覆蓋更大的可能解空間，產(chǎn)生更多種新可能解，增加獲得最優(yōu)解的機會；“行交叉”、“列交叉”大大地壓縮了可能解的解空間，產(chǎn)生的可能解都是可行解(編碼方案將約束條件考慮進去了)

；策略的選擇需要折中：選擇搜索更加廣泛的解空間呢，還是選擇壓縮搜索空間呢？需要折中。5.怎樣用遺傳算法求解應(yīng)用問題5.8不同的交叉隨機策略有什么特點?交叉與隨機不同的交叉策略對算法的求解質(zhì)量和收斂速度等方面是有影響的，沒有一種設(shè)計能夠面面俱到，因此如何在算法不同方面性能之間權(quán)衡，也是遺傳算法設(shè)計過程的關(guān)鍵所在，體現(xiàn)了一定程度的技術(shù)性和藝術(shù)性。怎樣研究算法：遺傳算法示例5.怎樣用遺傳算法求解應(yīng)用問題怎樣用遺傳算法求解具體的應(yīng)用問題(IV)----問題理解與分析建模----面向應(yīng)用的遺傳算法設(shè)計要點----可能解編碼方案的多樣性----交叉/變異規(guī)則的多樣性與隨機性----遺傳算法設(shè)計的其他方面----仍需要思考的引入變異操作的目的：一是使遺傳算法具有局部的隨機搜索能力。二是使遺傳算法可維持群體多樣性。變異操作是對群體中的某些個體染色體的某些基因進行突變處理變異概率(PM,probabilityofmutation)，控制算法中變異操作的使用頻率。變異操作的基本步驟：a)對種群中所有個體以事先設(shè)定的變異概率判斷是否進行變異；b)對進行變異的個體隨機選擇變異位置進行變異。遺傳算法設(shè)計的其他問題5.怎樣用遺傳算法求解應(yīng)用問題5.9你能自己分析一下遺傳算法的其他問題嗎?遺傳算法設(shè)計的其他問題5.怎樣用遺傳算法求解應(yīng)用問題5.9你能自己分析一下遺傳算法的其他問題嗎?適應(yīng)度函數(shù)的選擇主要考察其是否能度量一個可能解接近最優(yōu)解的程