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

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

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

vs.個(gè)體(Individual)

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

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

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

生成初始種群P(t)；

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

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

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

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

endwhile

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

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

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

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

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

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

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

設(shè)P1和P2表示兩個(gè)k*h位的父代染色體，其中k為每一段的位數(shù)，h為染色體的分段數(shù)目，f(P1)和f(P2)分別表示兩個(gè)父代的適應(yīng)度值，C表示子代染色體。 step1:產(chǎn)生一個(gè)0至h-1的隨機(jī)數(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交換；//注：兩個(gè)染色體的x段如相同,則不交換,否則以概率p進(jìn)行交換。5.怎樣用遺傳算法求解應(yīng)用問(wèn)題5.7怎樣將隨機(jī)和交叉結(jié)合在一起呢?交叉與隨機(jī)交叉操作III：列交叉

設(shè)P1和P2表示兩個(gè)k*h位的父代染色體，其中k為每一段的位數(shù)，h為染色體的分段數(shù)目，f(P1)和f(P2)分別表示兩個(gè)父代的適應(yīng)度值，C表示子代染色體。 step1:產(chǎn)生一個(gè)0至k-1的隨機(jī)數(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)；//注：兩個(gè)染色體的各段的x位如都相同，則不交換，否則以概率p進(jìn)行交換。交叉策略比較：“點(diǎn)交叉”將覆蓋更大的可能解空間，產(chǎn)生更多種新可能解，增加獲得最優(yōu)解的機(jī)會(huì)；“行交叉”、“列交叉”大大地壓縮了可能解的解空間，產(chǎn)生的可能解都是可行解(編碼方案將約束條件考慮進(jìn)去了)

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