《智能設(shè)計(jì)方法》課件 5 遺傳算法基礎(chǔ)

第五章遺傳算法基礎(chǔ)演講人目錄01.應(yīng)用意義和挑戰(zhàn)07.returnpopulation03.挑戰(zhàn)與問(wèn)題05.#計(jì)算城市之間的距離矩陣02.應(yīng)用意義04.解決方法與技術(shù)06.population=[]08.#復(fù)制交叉段1遺傳算法基本概念1.1遺傳算法的生物學(xué)基礎(chǔ)根據(jù)化石和分子學(xué)證據(jù)，地球上現(xiàn)存的所有生物都可以追溯到35到38億年前的共同祖先。而驅(qū)動(dòng)從同一祖先演化到如今遍布全球的不勝枚舉物種的過(guò)程則是自然選擇。達(dá)爾文在1859年出版的《物種起源》一書(shū)中首次系統(tǒng)性的闡述了自然選擇的生物進(jìn)化觀(guān)點(diǎn)（如圖5-1）。生物的遺傳特征在生存競(jìng)爭(zhēng)中，由于具有某種優(yōu)勢(shì)或某種劣勢(shì)，因而在生存能力上產(chǎn)生差異，并進(jìn)而導(dǎo)致繁殖能力的差異，使得這些特征被保存或是淘汰。因此，凡是在生存斗爭(zhēng)中獲勝的個(gè)體都是對(duì)環(huán)境適應(yīng)性比較強(qiáng)的個(gè)體。達(dá)爾文把這種在生存斗爭(zhēng)中適者生存、不適者淘汰的過(guò)程叫作自然選擇。自然選擇則是演化的主要機(jī)制，經(jīng)過(guò)自然選擇而能夠成功生存，稱(chēng)為“適應(yīng)”。如此，生物種群從低級(jí)、簡(jiǎn)單到高級(jí)、復(fù)雜不斷演化。1遺傳算法基本概念1.1遺傳算法的生物學(xué)基礎(chǔ)圖5-1達(dá)爾文與《物種起源》[17]達(dá)爾文的自然選擇學(xué)說(shuō)表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。遺傳是指父代與子代之間，在性狀上存在的相似現(xiàn)象；變異是指父代與子代之間，以及子代的個(gè)體之間，在性狀上存在的差異現(xiàn)象。在生物體內(nèi)，遺傳和變異的關(guān)系十分密切。一個(gè)生物體的遺傳性狀往往會(huì)發(fā)生變異，而變異的性狀有的可以遺傳。遺傳能使生物的性狀不斷地傳送給后代，因此保持了物種的特性；變異能夠使生物的性狀發(fā)生改變，從而適應(yīng)新的環(huán)境而不斷地向前發(fā)展。1遺傳算法基本概念1.1遺傳算法的生物學(xué)基礎(chǔ)生物的各項(xiàng)生命活動(dòng)都有它的物質(zhì)基礎(chǔ)，生物的遺傳與變異也是這樣。根據(jù)現(xiàn)代細(xì)胞學(xué)和遺傳學(xué)的研究可知：遺傳物質(zhì)的主要載體是染色體，而染色體由基因組成；基因是有遺傳效應(yīng)的片段，它儲(chǔ)存著遺傳信息，可以被準(zhǔn)確地復(fù)制，也能夠發(fā)生突變。生物體自身通過(guò)對(duì)基因的復(fù)制和交叉，使其性狀的遺傳得到選擇和控制。同時(shí)，通過(guò)基因重組、基因變異和染色體在結(jié)構(gòu)和數(shù)目上的變異產(chǎn)生豐富多彩的變異現(xiàn)象。生物的遺傳特性，使生物界的物種能夠保持相對(duì)的穩(wěn)定；生物的變異特性，使生物個(gè)體產(chǎn)生新的性狀，以至形成了新的物種，推動(dòng)了生物的進(jìn)化和發(fā)展。[18]由于生物在繁殖中可能發(fā)生基因交叉和變異，引起了生物性狀的連續(xù)微弱改變，為外界環(huán)境的定向選擇提供了物質(zhì)條件和基礎(chǔ)，使生物的進(jìn)化成為可能。人們正是通過(guò)對(duì)環(huán)境的選擇?；虻慕徊婧妥儺愡@一生物演化的選代過(guò)程的模仿，才提出了能夠用于求解最優(yōu)化問(wèn)題的強(qiáng)魯棒性和自適應(yīng)性的遺傳算法。[19]生物遺傳和進(jìn)化的規(guī)律有：1遺傳算法基本概念1.1遺傳算法的生物學(xué)基礎(chǔ)（1）生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀，染色體是由基因及其有規(guī)律的排列所構(gòu)成的。01（2）生物的繁殖過(guò)程是由其基因的復(fù)制過(guò)程來(lái)完成的。同源染色體的交叉或變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。02（3）對(duì)環(huán)境適應(yīng)能力強(qiáng)的基因或染色休，比適應(yīng)能力差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。031遺傳算法基本概念模式定理模式定義：模式是描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板。不失一般性，考慮二值字符集{0，1}，由此可以產(chǎn)生通常的0、1字符串。增加一個(gè)符號(hào)“*”，稱(chēng)作“通配符”，即“*”既可以當(dāng)作“0”，也可以當(dāng)作“1”。這樣，二值字符集{0,1}就擴(kuò)展為三值字符集{0，1，*}，由此可以產(chǎn)生諸如0110，0*11**，**01*0之類(lèi)的字符串?；谌底址瘂0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串，稱(chēng)作模式。這里需要強(qiáng)調(diào)的是，“*”只是一個(gè)描述符，而并非遺傳算法中實(shí)際的運(yùn)算符號(hào)，它僅僅是為了描述上的方便而引入的符號(hào)。1遺傳算法基本概念模式定理模式的概念可以簡(jiǎn)明地描述為具有相似結(jié)構(gòu)特點(diǎn)的個(gè)體編碼字符串。在引入了模式概念之后，遺傳算法的本質(zhì)是對(duì)模式所進(jìn)行的一系列運(yùn)算，即通過(guò)選擇操作將當(dāng)前群體中的優(yōu)良模式遺傳到下一代群體中，通過(guò)交叉操作進(jìn)行模式的重組，通過(guò)變異操作進(jìn)行模式的突變。通過(guò)這些遺傳運(yùn)算，一些較差的模式逐步被淘汰，而一些較好的模式逐步被遺傳和進(jìn)化，最終就可以得到問(wèn)題的最優(yōu)解。多個(gè)字符串中隱含著多個(gè)不同的模式。確切地說(shuō)，長(zhǎng)度為L(zhǎng)的字符串，隱含著2L個(gè)不同的模式，而不同的模式所匹配的字符串的個(gè)數(shù)是不同的。為了反映這種確定性的差異，引入模式階概念。模式階定義：模式H中確定位置的個(gè)數(shù)稱(chēng)作該模式的模式階，記作O(H)。1遺傳算法基本概念模式定理比如，模式011*1*的階數(shù)為4，而模式0*****的階數(shù)為1。顯然，一個(gè)模式的階數(shù)越高，其樣本數(shù)就越少，因而其確定性就越高。但是，模式階并不能反映模式的所有性質(zhì)；即使具有同階的模式，在遺傳操作下，也會(huì)有不同的性質(zhì)。為此，引入定義距的概念。定義距定義：在模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱(chēng)作該模式的定義距，記作D(H)。模式定理：在遺傳算法選擇、交叉和變異算子的作用下，具有低階、短定義距，并且其平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將呈指數(shù)級(jí)增長(zhǎng)。模式定理又稱(chēng)為遺傳算法的基本定理。模式定理闡述了遺傳算法的理論基礎(chǔ)，說(shuō)明了模式的增加規(guī)律，同時(shí)也對(duì)遺傳算法的應(yīng)用提供了指導(dǎo)。根據(jù)模式定理，隨著遺傳算法的一代一代地進(jìn)行，那些定義距短的、位數(shù)少的、高適應(yīng)度的模式將越來(lái)越多，因而可期望最后得到的位串的性能越來(lái)越得到改善，并最終趨向全局的最優(yōu)點(diǎn)。[20]1遺傳算法基本概念模式定理模式的思路提供了一種簡(jiǎn)單而有效的方法，使得能夠在有限字符表的基礎(chǔ)上討論有限長(zhǎng)位串的嚴(yán)謹(jǐn)定義的相似性；而模式定理從理論上保證了遺傳算法是一個(gè)可以用來(lái)尋求最優(yōu)可行解的優(yōu)化過(guò)程。1遺傳算法基本概念積木塊假設(shè)模式定理說(shuō)明了具有某種結(jié)構(gòu)特征的模式在遺傳進(jìn)化過(guò)程中其樣本數(shù)目將呈指數(shù)級(jí)增長(zhǎng)。這種模式定義為積木塊，它在遺傳算法中非常重要。積木塊定義：具有低階、短定義距以及高平均適應(yīng)度的模式稱(chēng)作積木塊。之所以稱(chēng)之為積木塊，是由于遺傳算法的求解過(guò)程并不是在搜索空間中逐一地測(cè)試各個(gè)基因的枚舉組合，而是通過(guò)一些較好的模式，像搭積木一樣，將它們拼接在一起，從而逐漸地構(gòu)造出適應(yīng)度越來(lái)越高的個(gè)體編碼串。模式定理說(shuō)明了積木塊的樣本數(shù)呈指數(shù)級(jí)增長(zhǎng)，亦即說(shuō)明了用遺傳算法尋求最優(yōu)樣本的可能性，但它并未指明遺傳算法一定能夠?qū)で蟮阶顑?yōu)樣本;而積木塊假設(shè)說(shuō)明了遺傳算法的這種能力。1遺傳算法基本概念積木塊假設(shè)積木塊假設(shè)：個(gè)體的積木塊通過(guò)選擇、交叉、變異等遺傳算子的作用，能夠相互結(jié)合在一起，形成高階、長(zhǎng)距、高平均適應(yīng)度的個(gè)體編碼串。積木塊假設(shè)說(shuō)明了用遺傳算法求解各類(lèi)問(wèn)題的基本思想，即通過(guò)基因塊之間的相互拼接能夠產(chǎn)生出問(wèn)題的更好的解，最終生成全局最優(yōu)解。從遺傳算法的模式定理得到：具有高適應(yīng)度、低階、短定義矩的模式的數(shù)量會(huì)在種群的進(jìn)化中呈指數(shù)級(jí)增長(zhǎng)，從而保證了算法獲得最優(yōu)解的一個(gè)必要條件。而另一方面，積木塊假設(shè)則指出：遺傳算法有能力使優(yōu)秀的模式向著更優(yōu)的方向進(jìn)化，即遺傳算法有能力搜索到全局最優(yōu)解。[21]1遺傳算法基本概念遺傳算法流程基本遺傳算法(也稱(chēng)標(biāo)準(zhǔn)遺傳算法、經(jīng)典遺傳算法或簡(jiǎn)單遺傳算法，SimpleGeneticAlgorithm，簡(jiǎn)稱(chēng)SGA)，是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象，只使用基本遺傳算子(GeneticOperator)：選擇算子(SelectionOperator)、交叉算子(CrossoverOperator)和變異算子(MutationOperator)，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其它一些遺傳算法的基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。[22]選擇、交叉和變異是遺傳算法的3個(gè)主要操作算子，它們構(gòu)成了遺傳操作，使遺傳算法具有了其它優(yōu)化算法沒(méi)有的特點(diǎn)。遺傳算法使用群體搜索技術(shù)，通過(guò)對(duì)當(dāng)前群體施加選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，并逐步使群體進(jìn)化到包含或接近最優(yōu)解的狀態(tài)。1遺傳算法基本概念遺傳算法流程在遺傳算法中，將n維決策向量X=[x1,x≥,…,xn]用n個(gè)記號(hào)X(i=1,2,..,n)所組成的符號(hào)串X來(lái)表示：X=[x1,x2,…,xn]T(5-1)把每一個(gè)Xi，看作一個(gè)遺傳基因，它的所有可能取值就稱(chēng)為等位基因，這樣，X就可看作由n個(gè)遺傳基因所組成的一個(gè)染色體。一般情況下，染色體的長(zhǎng)度是固定的，但對(duì)一些問(wèn)題來(lái)說(shuō)它也可以是變化的。根據(jù)不同的情況，這里的等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)，或者是一個(gè)純粹的記號(hào)。最簡(jiǎn)單的等位基因是由0或1的符號(hào)串組成的，相應(yīng)的染色體就可以表示為一個(gè)二進(jìn)制符號(hào)串。這種編碼所形成的排列形式是個(gè)體的基因型，與它對(duì)應(yīng)的X值是個(gè)體的表現(xiàn)型。染色體X也稱(chēng)為個(gè)體X，對(duì)于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定其適應(yīng)度。個(gè)體的適應(yīng)度與其對(duì)應(yīng)的個(gè)體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，適應(yīng)度越小。1遺傳算法基本概念遺傳算法流程在遺傳算法中，決策向量X組成了問(wèn)題的解空間。對(duì)問(wèn)題最優(yōu)解的搜索是通過(guò)對(duì)染色體X的搜索過(guò)程來(lái)完成的，因而所有的染色體X就組成了問(wèn)題的搜索空間。生物的進(jìn)化過(guò)程主要是通過(guò)染色體之間的交叉和染色體基因的變異來(lái)完成的。與此相對(duì)應(yīng)，遺傳算法中最優(yōu)解的搜索過(guò)程正是模仿生物的這個(gè)進(jìn)化過(guò)程，進(jìn)行反復(fù)迭代，從第t代群體P(t)，經(jīng)過(guò)一代遺傳和進(jìn)化后，得到第t+1代群體P(t+1)。這個(gè)群體不斷地經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體X，達(dá)到或接近于問(wèn)題的最優(yōu)解。[23]遺傳算法的運(yùn)算流程如圖5-2所示。具體步驟如下：1遺傳算法基本概念遺傳算法流程(3)選擇運(yùn)算。將選擇算子作用于群體，根據(jù)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，選擇一些優(yōu)良個(gè)體進(jìn)傳到下一代群體。C(2)個(gè)體評(píng)價(jià)。計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。B(4)交叉運(yùn)算。將交叉算子作用于群體，對(duì)選中的成對(duì)個(gè)體，以某一概率交換它們之間的部分染色體，產(chǎn)生新的個(gè)體。D(1)初始化。設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器g=0，設(shè)置最大進(jìn)化代數(shù)G，隨機(jī)生成Np個(gè)個(gè)體作為初始群體P(0)。A(5)變異運(yùn)算。將變異算子作用于群體，對(duì)選中的個(gè)體，以某一概率改變某一個(gè)或某一些基因值為其他的等位基因。E1遺傳算法基本概念遺傳算法流程(6)循環(huán)操作。群體P(t)經(jīng)過(guò)選擇、交叉和變異運(yùn)算之后得到下一代群體P(t+1)。計(jì)算其適應(yīng)度值，并根據(jù)適應(yīng)度值進(jìn)行排序，準(zhǔn)備進(jìn)行下一次遺傳操作。(7)終止條件判斷：若g≤G，則g=g+1，轉(zhuǎn)到步驟(2)；若g>G，則此進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度的個(gè)體作為最優(yōu)解輸出，終止計(jì)算。圖5-2遺傳算法基本流程圖遺傳算法流程中涉及的部分基本概念如表5-1所示。部分遺傳算法術(shù)語(yǔ)在表5-1中列出。表5-1遺傳學(xué)與遺傳算法術(shù)語(yǔ)對(duì)應(yīng)關(guān)系1遺傳算法基本概念適應(yīng)函數(shù)遺傳算法將問(wèn)題空間表示為染色體位串空間，為了執(zhí)行適者生存的原則，必須對(duì)個(gè)體位串的適應(yīng)性進(jìn)行評(píng)價(jià)。因此，適應(yīng)函數(shù)(fitnessfunction)就構(gòu)成了個(gè)體的生存環(huán)境。根據(jù)個(gè)體的適應(yīng)值，就可決定它在此環(huán)境下的生存能力。一般來(lái)說(shuō)，好的染色體位串結(jié)構(gòu)具有比較高的適應(yīng)函數(shù)值，即可以獲得較高的評(píng)價(jià)，具有較強(qiáng)的生存能力。由于適應(yīng)值是群體中個(gè)體生存機(jī)會(huì)選擇的惟一確定性指標(biāo)，所以適應(yīng)函數(shù)的形式直接決定著群體的進(jìn)化行為。根據(jù)實(shí)際問(wèn)題的經(jīng)濟(jì)含義，適應(yīng)值可以是銷(xiāo)售收入、利潤(rùn)、市場(chǎng)占有率、商品流通量或機(jī)器可靠性等。為了能夠直接將適應(yīng)函數(shù)與群體中的個(gè)體優(yōu)劣度量相聯(lián)系，在遺傳算法中適應(yīng)值規(guī)定為非負(fù)，并且在任何情況下總是希望越大越好。[24]若用SL表示位串空間，SL上的適應(yīng)值函數(shù)可表示為f()：SL→R+函數(shù)，為實(shí)值，其中R+表示非負(fù)實(shí)數(shù)集合。1遺傳算法基本概念適應(yīng)函數(shù)對(duì)于給定的優(yōu)化問(wèn)題optg(x)(x∈[u,v])，目標(biāo)函數(shù)有正有負(fù)，甚至可能是復(fù)數(shù)值，所以有必要通過(guò)建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值是非負(fù)的，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大方向。針對(duì)進(jìn)化過(guò)程中關(guān)于遺傳操作的控制的需要，選擇函數(shù)變換T：g→f，使得對(duì)于最優(yōu)解x*，maxf(x*)=opt(x*)(x*∈[u,v])。[25]1)對(duì)最小化問(wèn)題，建立如下適應(yīng)函數(shù)f(x)和目標(biāo)函數(shù)g(x)的映射關(guān)系：????=?????????????,若????<????????0,否則(5-2)其中，cmax可以是一個(gè)輸入值或是理論上的最大值?；蛘呤堑疆?dāng)前所有代或最近K代中g(shù)(x)的最大值，此時(shí)cmax隨著代數(shù)會(huì)有變化。1遺傳算法基本概念適應(yīng)函數(shù)2)對(duì)于最大化問(wèn)題，一般采用下述方法：????=?????????????,若?????????????>00,否則（5-3）式中cmax既可以是特定的輸入值，也可以是當(dāng)前所有代或最近K代中g(shù)(x)的最小值。若optg(x)(x∈[u,v])為最大化問(wèn)題，且min(g(x))≥0(x∈[u,v])，仍然需要針對(duì)進(jìn)化過(guò)程的控制目標(biāo)選擇某種函數(shù)變換，以便于制定合適的選擇策略，使得遺傳算法獲得最大的進(jìn)化能力和最佳的搜索效果。[26]遺傳操作1遺傳算法基本概念適應(yīng)函數(shù)遺傳操作是優(yōu)選強(qiáng)勢(shì)個(gè)體的“選擇”、個(gè)體間交換基因產(chǎn)生新個(gè)體的“交叉”、個(gè)體基因信息突變而產(chǎn)生新個(gè)體的“變異”這三種變換的統(tǒng)稱(chēng)。在生物進(jìn)化過(guò)程中，一個(gè)群體中生物特性的保持是通過(guò)遺傳來(lái)繼承的。生物的遺傳主要是通過(guò)選擇、交叉、變異三個(gè)過(guò)程把當(dāng)前父代群體的遺傳信息遺傳到下一代(子代）成員。與此對(duì)應(yīng)，遺傳算法中最優(yōu)解的搜索過(guò)程也模仿生物的這個(gè)進(jìn)化過(guò)程，使用所謂的遺傳算子來(lái)實(shí)現(xiàn)，即選擇算子、交叉算子、變異算子。[27](1)選擇算子：根據(jù)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。典型的選擇算子有以下幾類(lèi)：1遺傳算法基本概念適應(yīng)函數(shù)1)輪盤(pán)賭選擇（roulettewheelselection）“輪盤(pán)賭”選擇法是遺傳算法中最早提出的一種選擇方法，由Holland提出，因?yàn)樗?jiǎn)單實(shí)用，所以被廣泛采用。它是一種基于比例的選擇，利用各個(gè)個(gè)體適應(yīng)度所占比例的大小來(lái)決定其子代保留的可能性。若某個(gè)個(gè)體i的適應(yīng)度為fi，種群大小為NP，則它被選取的概率表示為????=??????=1??????????=1,2,…,????(5-4)個(gè)體適應(yīng)度越大，則其被選擇的機(jī)會(huì)也越大；反之亦然。為了選擇交叉?zhèn)€體，需要進(jìn)行多輪選擇。每一輪產(chǎn)生一個(gè)[0，1]內(nèi)的均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來(lái)確定被選個(gè)體。1遺傳算法基本概念適應(yīng)函數(shù)圖5-3輪盤(pán)賭選擇算子范例1遺傳算法基本概念錦標(biāo)賽選擇（tournamentselection）由于算法執(zhí)行的效率以及易實(shí)現(xiàn)的的特點(diǎn)，錦標(biāo)賽選擇算法是遺傳算法中最流行的選擇策略。在本人的實(shí)際應(yīng)用中的確此策略比基本的輪盤(pán)賭效果要好些。他的策略也很直觀(guān)，就是我們?cè)購(gòu)恼麄€(gè)種群中抽取n個(gè)個(gè)體，讓他們進(jìn)行競(jìng)爭(zhēng)(錦標(biāo)賽)，抽取其中的最優(yōu)的個(gè)體。參加錦標(biāo)賽的個(gè)體個(gè)數(shù)稱(chēng)為錦標(biāo)賽選擇規(guī)模。通常n=2便是最常使用的大小，也稱(chēng)作二值錦標(biāo)賽選擇。錦標(biāo)賽選擇的優(yōu)勢(shì)：更小的復(fù)雜度易并行化處理不易陷入局部最優(yōu)點(diǎn)不需要對(duì)所有的適應(yīng)度值進(jìn)行排序處理下圖（圖5-4）顯示了n=3的錦標(biāo)賽選擇的過(guò)程：1遺傳算法基本概念錦標(biāo)賽選擇（tournamentselection）圖5-4錦標(biāo)賽選擇算子范例3)隨機(jī)遍歷抽樣（stochasticuniversalselection）隨機(jī)遍歷抽樣是上述輪盤(pán)賭選擇的修改版，其使用相同的輪盤(pán)，比例相同，但采用多個(gè)選擇點(diǎn)，只旋轉(zhuǎn)一次轉(zhuǎn)盤(pán)就可以同時(shí)選擇所有個(gè)體。該選擇方法可以防止個(gè)體被過(guò)分反復(fù)選擇，從而避免了具有特別高適應(yīng)度的個(gè)體壟斷下一代。因此，其為較低適應(yīng)度的個(gè)體提供了被選擇的機(jī)會(huì)；進(jìn)而降低了原始輪盤(pán)選擇方法的不公平問(wèn)題。1遺傳算法基本概念無(wú)回放隨機(jī)選擇（localselection）無(wú)回放隨機(jī)選擇（也叫期望值選擇ExceptedValueSelection）：根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望來(lái)進(jìn)行隨機(jī)選擇運(yùn)算。方法如下：計(jì)算群體中每個(gè)個(gè)體在下一代群體中的生存期望數(shù)目N。若某一個(gè)體被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去0.5，若某一個(gè)體未被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去1.0。隨著選擇過(guò)程的進(jìn)行，若某一個(gè)體的生存期望數(shù)目小于0時(shí)，則該個(gè)體就不再有機(jī)會(huì)被選中。1遺傳算法基本概念截?cái)噙x擇（truncationselection）截?cái)噙x擇是一種簡(jiǎn)單的選擇策略，它將種群中的個(gè)體按照適應(yīng)度數(shù)值排序，然后選擇適應(yīng)度最高的個(gè)體作為下一代。這種策略簡(jiǎn)單易行，但它可能會(huì)導(dǎo)致種群多樣性的喪失，因?yàn)檫m應(yīng)度較低的個(gè)體完全沒(méi)有機(jī)會(huì)遺傳給下一代。(2)交叉算子：將群體P(t)中選中的各個(gè)個(gè)體隨機(jī)搭配，對(duì)每一對(duì)個(gè)體，以某一概率（交叉概率PC）交換它們之間的部分染色體。通過(guò)交叉，遺傳算法的搜索能力得以飛躍提高。交叉操作一般分為以下幾個(gè)步驟：首先，從交配池中隨機(jī)取出要交配的一對(duì)個(gè)體;然后，根據(jù)位串長(zhǎng)度L，對(duì)要交配的一對(duì)個(gè)體，隨機(jī)選取[1，L-1]中的一個(gè)或多個(gè)整數(shù)k作為交叉位置;最后，根據(jù)交叉概率PC。實(shí)施交叉操作，配對(duì)個(gè)體在交叉位置處，相互交換各自的部分基因，從而形成新的一對(duì)個(gè)體。交叉算子可以分為以下幾類(lèi)：1遺傳算法基本概念截?cái)噙x擇（truncationselection）1)單點(diǎn)交叉，該算子在配對(duì)的染色體中隨機(jī)的選擇一個(gè)交叉位置，然后在該交叉位置對(duì)配對(duì)的染色體進(jìn)行基因位變換。在實(shí)際應(yīng)用中，使用率最高的是單點(diǎn)交叉算子。2)雙點(diǎn)交叉或多點(diǎn)交叉，即對(duì)配對(duì)的染色體隨機(jī)設(shè)置兩個(gè)或者多個(gè)交叉點(diǎn)，然后進(jìn)行交叉運(yùn)算，改變?nèi)旧w基因序列。3)均勻交叉，即配對(duì)的染色體基因序列上的每個(gè)位置都以等概率進(jìn)行交叉，以此組成新的1遺傳算法基本概念截?cái)噙x擇（truncationselection）基因序列。圖5-5幾種交叉算子操作實(shí)例4)算術(shù)交叉，是指兩個(gè)個(gè)體的線(xiàn)性組合產(chǎn)生出兩個(gè)新的個(gè)體，為了能夠進(jìn)行線(xiàn)性組合運(yùn)算，算數(shù)交叉的操作對(duì)象一般是由浮點(diǎn)數(shù)編碼所表示的個(gè)體。設(shè)??????和??????之間做算術(shù)交叉，則交叉后的新個(gè)體為：??????+1=????????+1???????????????+1=????????+1?????????（5-5）其中，α為常數(shù)時(shí)，此時(shí)進(jìn)行的算術(shù)交叉叫做均勻算術(shù)交叉；當(dāng)α為由進(jìn)化代數(shù)所決定的變量時(shí)，此時(shí)稱(chēng)為非均勻算術(shù)交叉。操作過(guò)程：1遺傳算法基本概念截?cái)噙x擇（truncationselection）(1)確定兩個(gè)個(gè)體進(jìn)行線(xiàn)性組合時(shí)的系數(shù)α。(2)依據(jù)上式進(jìn)行交叉操作產(chǎn)生新個(gè)體。(3)變異算子：對(duì)群體中的每個(gè)個(gè)體，以某一概率(變異概率PM)將某一個(gè)或某一些基因座上的基因值改變?yōu)槠渌牡任换蛑?。根?jù)個(gè)體編碼方式的不同，變異方式有：實(shí)值變異、二進(jìn)制變異。對(duì)于二進(jìn)制的變異，對(duì)相應(yīng)的基因值取反；對(duì)于實(shí)值的變異，對(duì)相應(yīng)的基因值用取值范圍內(nèi)的其他隨機(jī)值替代。變異操作的一般步驟為：首先，對(duì)種群中所有個(gè)體按事先設(shè)定的變異概率判斷是否進(jìn)行變異；然后，對(duì)進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異。1遺傳算法基本概念群體規(guī)模群體規(guī)模將影響遺傳優(yōu)化的最終結(jié)果以及遺傳算法的執(zhí)行效率。當(dāng)群體規(guī)模Np太小時(shí)，遺傳優(yōu)化性能一般不會(huì)太好。采用較大的群體規(guī)?？梢詼p小遺傳算法陷入局部最優(yōu)解的機(jī)會(huì)，但較大的群體規(guī)模意味著計(jì)算復(fù)雜度較高。一般N取10~200。交叉概率交叉概率P控制著交叉操作被使用的頻度。較大的交叉概率可以增強(qiáng)遺傳算法開(kāi)辟新的搜索區(qū)域的能力，但高性能的模式遭到破壞的可能性增大；若交叉概率太低，遺傳算法搜索可能陷入遲鈍狀態(tài)。一般P取0.25~1.00。變異概率變異在遺傳算法中屬于輔助性的搜索操作，它的主要目的是保持群體的多樣性。一般低頻度的變異可防止群體中重要基因的可能丟失，高頻度的變異將使遺傳算法趨于純粹的隨機(jī)搜索。通常Pm取0.001~0.1。1遺傳算法基本概念群體規(guī)模遺傳運(yùn)算的終止進(jìn)化代數(shù)終止進(jìn)化代數(shù)G是表示遺傳算法運(yùn)行結(jié)束條件的一個(gè)參數(shù)，它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。一般視具體問(wèn)題而定，G的取值可在100~1000之間。[28]1遺傳算法基本概念1.4遺傳算法的特點(diǎn)遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化的過(guò)程而形成的一種并行、高效、全局搜索的方法，它主要有以下特點(diǎn)：(1)遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。這種對(duì)決策變量的編碼處理方式，使得在優(yōu)化計(jì)算過(guò)程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化等的機(jī)理，方便地應(yīng)用遺傳操作算子。特別是對(duì)一些只有代碼概念而無(wú)數(shù)值概念或很難有數(shù)值概念的優(yōu)化問(wèn)題，編碼處理方式更顯示出了其獨(dú)特的優(yōu)越性。(2)遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。它僅使用由目標(biāo)函數(shù)值變換來(lái)的適應(yīng)度函數(shù)值，就可確定進(jìn)一步的搜索方向和搜索范圍，而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。實(shí)際應(yīng)用中很多函數(shù)無(wú)法或很難求導(dǎo)，甚至根本不存在導(dǎo)數(shù)，對(duì)于這類(lèi)目標(biāo)函數(shù)的優(yōu)化和組合優(yōu)化問(wèn)題，遺傳算法就顯示了其高度的優(yōu)越性，因?yàn)樗荛_(kāi)了函數(shù)求導(dǎo)這個(gè)障礙。1遺傳算法基本概念1.4遺傳算法的特點(diǎn)(3)遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。遺傳算法對(duì)最優(yōu)解的搜索過(guò)程，是從一個(gè)由很多個(gè)體所組成的初始群體開(kāi)始的，而不是從單一的個(gè)體開(kāi)始的。對(duì)這個(gè)群體所進(jìn)行的選擇、交叉、變異等運(yùn)算，產(chǎn)生出新一代的群體，其中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點(diǎn)，相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱含并行性。(4)遺傳算法是一種基于概率的搜索技術(shù)。遺傳算法屬于自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，從而增加了其搜索過(guò)程的靈活性。雖然這種概率特性也會(huì)使群體中產(chǎn)生一些適應(yīng)度不高的個(gè)體，但隨著進(jìn)化過(guò)程的進(jìn)行，新的群體中總會(huì)更多地產(chǎn)生出優(yōu)良的個(gè)體。與其他一些算法相比，遺傳算法的魯棒性使得參數(shù)對(duì)其搜索效果的影響盡可能小。1遺傳算法基本概念1.4遺傳算法的特點(diǎn)(5)遺傳算法具有自組織、自適應(yīng)和自學(xué)習(xí)等特性。當(dāng)遺傳算法利用進(jìn)化過(guò)程獲得信息自行組織搜索時(shí)，適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。同時(shí)，遺傳算法具有可擴(kuò)展性，易于同別的算法相結(jié)合，生成綜合雙方優(yōu)勢(shì)的混合算法。1遺傳算法基本概念1.5遺傳算法的優(yōu)缺點(diǎn)遺傳算法的優(yōu)點(diǎn)：適用范圍廣：遺傳算法可以用于許多優(yōu)化問(wèn)題，包括函數(shù)優(yōu)化、組合優(yōu)化、圖形優(yōu)化、機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域。并行處理能力強(qiáng)：由于遺傳算法的各個(gè)個(gè)體之間可以獨(dú)立演化，因此可以很容易地并行處理，加快算法的收斂速度。全局搜索能力強(qiáng)：遺傳算法能夠在解空間中搜索全局最優(yōu)解，即使搜索空間非常大、非線(xiàn)性或存在多個(gè)局部最優(yōu)解，也可以在一定程度上避免陷入局部最優(yōu)解的情況。靈活性高：遺傳算法具有良好的可擴(kuò)展性，可以通過(guò)引入新的操作符、調(diào)整參數(shù)等方式來(lái)提高算法性能。1遺傳算法基本概念1.5遺傳算法的優(yōu)缺點(diǎn)對(duì)約束條件適應(yīng)性強(qiáng)：遺傳算法能夠通過(guò)適當(dāng)?shù)木幋a方式和適應(yīng)度函數(shù)來(lái)處理約束條件，從而使優(yōu)化問(wèn)題具有更好的可行性。遺傳算法的缺點(diǎn)：參數(shù)設(shè)置比較困難：遺傳算法需要設(shè)置許多參數(shù)，例如種群大小、交叉概率、變異概率等，這些參數(shù)的選擇對(duì)算法的性能影響較大，因此需要花費(fèi)一定的時(shí)間和精力進(jìn)行調(diào)參。需要計(jì)算適應(yīng)度函數(shù)：遺傳算法的效果直接取決于適應(yīng)度函數(shù)的質(zhì)量，而計(jì)算適應(yīng)度函數(shù)的成本較高，這也是算法效率較低的原因之一?？赡芟萑刖植孔顑?yōu)解：盡管遺傳算法能夠全局搜索最優(yōu)解，但在搜索空間比較復(fù)雜的情況下，遺傳算法也有可能陷入局部最優(yōu)解，這時(shí)需要一些優(yōu)化措施，例如引入更多的交叉和變異操作，來(lái)提高算法的多樣性和搜索能力。1遺傳算法基本概念1.5遺傳算法的優(yōu)缺點(diǎn)總的來(lái)說(shuō)，遺傳算法具有全局搜索能力強(qiáng)、適用范圍廣、靈活性高等優(yōu)點(diǎn)，但需要花費(fèi)一定的時(shí)間和精力進(jìn)行參數(shù)調(diào)優(yōu)，并且在某些情況下容易陷入局部最優(yōu)解。因此，在具體應(yīng)用時(shí)需要根據(jù)具體情況選擇合適的優(yōu)化算法。2遺傳算法的發(fā)展歷程2.1遺傳算法的興起Holland的早期工作主要集中于生物學(xué)、社會(huì)學(xué)、控制工程、人工智能等領(lǐng)域中的一類(lèi)動(dòng)態(tài)系統(tǒng)的適應(yīng)性問(wèn)題(adaptation)，其中適應(yīng)性概念描述了在環(huán)境中表現(xiàn)出較好行為和性能的系統(tǒng)結(jié)構(gòu)的漸進(jìn)改變過(guò)程，簡(jiǎn)稱(chēng)系統(tǒng)的適應(yīng)過(guò)程。[18]Holland認(rèn)為，通過(guò)簡(jiǎn)單的模擬機(jī)制可以描述復(fù)雜的適應(yīng)性現(xiàn)象。因此，Holland試圖建立適應(yīng)過(guò)程的一般描述模型，并在計(jì)算機(jī)上開(kāi)展模擬試驗(yàn)研究，分析自然系統(tǒng)或者人工系統(tǒng)對(duì)環(huán)境變化的適應(yīng)性現(xiàn)象，其中遺傳算法僅僅是一種具體的算法形式。Bremermann,DeJong等人則注重將遺傳算法應(yīng)用于參數(shù)優(yōu)化問(wèn)題，極大地促進(jìn)了遺傳算法的應(yīng)用。所以，遺傳算法既是一種自然進(jìn)化系統(tǒng)的計(jì)算模型，也是一種通用的(generalpurpose)求解優(yōu)化問(wèn)題的適應(yīng)性搜索方法。目前，人們最關(guān)注和普遍使用的遺傳算法是其后一種性質(zhì)。2遺傳算法的發(fā)展歷程2.1遺傳算法的興起從整體上來(lái)講，遺傳算法是進(jìn)化算法中產(chǎn)生最早、影響最大、應(yīng)用也比較廣泛的一個(gè)研究方向和領(lǐng)域，它不僅包含了進(jìn)化算法的基本形式和全部?jī)?yōu)點(diǎn)，同時(shí)還具備若干獨(dú)特的性能。1)在求解問(wèn)題時(shí)，遺傳算法首先要選擇編碼方式，它直接處理的對(duì)象是參數(shù)的編碼集而不是問(wèn)題參數(shù)本身，搜索過(guò)程既不受優(yōu)化函數(shù)連續(xù)性的約束，也沒(méi)有優(yōu)化函數(shù)導(dǎo)數(shù)必須存在的要求。通過(guò)優(yōu)良染色體基因的重組，遺傳算法可以有效地處理傳統(tǒng)上非常復(fù)雜的優(yōu)化函數(shù)求解問(wèn)題。2)若遺傳算法在每一代對(duì)群體規(guī)模為n的個(gè)體進(jìn)行操作，實(shí)際上處理了大約0(n3)個(gè)模式，具有很高的并行性，因而具有顯著的搜索效率。3)在所求解問(wèn)題為非連續(xù)、多峰以及有噪聲的情況下，能夠以很大的概率收斂到最優(yōu)解或滿(mǎn)意解，因而具有較好的全局最優(yōu)解求解能力。2遺傳算法的發(fā)展歷程2.1遺傳算法的興起4)對(duì)函數(shù)的性態(tài)無(wú)要求，針對(duì)某一問(wèn)題的遺傳算法經(jīng)簡(jiǎn)單修改即可適應(yīng)于其他問(wèn)題，或者加入特定問(wèn)題的領(lǐng)域知識(shí)，或者與已有算法相結(jié)合，能夠較好地解決一類(lèi)復(fù)雜問(wèn)題，因而具有較好的普適性和易擴(kuò)充性。5)遺傳算法的基本思想簡(jiǎn)單，運(yùn)行方式和實(shí)現(xiàn)步驟規(guī)范，便于具體使用。鑒于遺傳算法具有上述特征，一經(jīng)提出即在理論上引起了高度重視，并在實(shí)際工程技術(shù)和經(jīng)濟(jì)管理領(lǐng)域得到了廣泛地應(yīng)用，產(chǎn)生了大量的成功案例。1962年，JohnHolland在OutlineforaLogicTheoryofAdaptiveSystems一文中，提出了所謂監(jiān)控程序(supervisoryprograms)的概念，即利用群體進(jìn)化模擬適應(yīng)性系統(tǒng)的思想。2遺傳算法的發(fā)展歷程2.1遺傳算法的興起他注意到在建立智能機(jī)器的研究中，不僅可以完成單個(gè)生物體的適應(yīng)性改進(jìn)，而且通過(guò)一個(gè)種群的許多代的進(jìn)化也可以取得非常好的適應(yīng)性效果。為了獲得一個(gè)好的學(xué)習(xí)方法，僅靠單個(gè)策略的改進(jìn)是不夠的，采用多策略的群體繁殖往往能產(chǎn)生顯著的學(xué)習(xí)效果。盡管他當(dāng)時(shí)沒(méi)有給出實(shí)現(xiàn)這些思想的具體技術(shù)，但卻引進(jìn)了群體、適應(yīng)值、選擇、變異、交叉等基本概念。1966年，F(xiàn)ogel等人也提出了類(lèi)似的思想，但其重點(diǎn)是放在變異算子而不是采用交叉算子。1967年，Holland的學(xué)生J.D.Bagley通過(guò)對(duì)跳棋游戲參數(shù)的研究，在其博士論文中首次提出“遺傳算法”一詞。[26]2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展Holland以二進(jìn)制字符集{0,1}構(gòu)成的代碼串表示實(shí)際問(wèn)題的描述結(jié)構(gòu)或參數(shù)，稱(chēng)為“染色體”（chromosome）。對(duì)這些“染色體”進(jìn)行變換，利用“染色體”中所包含的信息決定新一代“染色體”，并最終得到問(wèn)題的解。這種方法對(duì)所要解決的問(wèn)題類(lèi)型幾乎沒(méi)有任何限制，所需要的信息只是每個(gè)染色體的評(píng)價(jià)值。這種使用簡(jiǎn)單編碼和選擇機(jī)制的算法能夠解決相當(dāng)復(fù)雜的問(wèn)題，并且解決實(shí)際問(wèn)題時(shí)不需要該領(lǐng)域的專(zhuān)門(mén)知識(shí)。通過(guò)對(duì)這些簡(jiǎn)單的染色體進(jìn)行迭代處理，從這些染色體中發(fā)現(xiàn)并保存好的染色體，進(jìn)而逐步發(fā)現(xiàn)問(wèn)題的最優(yōu)解，這些思想就是遺傳算法理論的雛形。同時(shí)，F(xiàn)raser采用計(jì)算機(jī)模擬自然遺傳系統(tǒng)，1962年提出了和現(xiàn)在的遺傳算法十分相似的概念與思想。但是，F(xiàn)raser和其他一些學(xué)者并未認(rèn)識(shí)到自然遺傳方法可以轉(zhuǎn)化為人工遺傳算法。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展在20世紀(jì)60年代中期至70年代末期，基于自然進(jìn)化的思想遭到懷疑和后對(duì)。Holland及其數(shù)位博士堅(jiān)持了這一方向的研究。在Holland發(fā)表論文后的十余年中，從事遺傳算法研究的論文開(kāi)始慢慢出現(xiàn)。大多數(shù)研究都集中在美國(guó)Michigan大學(xué)的Holland及其學(xué)生當(dāng)中。因此，進(jìn)傳算法大多數(shù)著名學(xué)者都曾經(jīng)是Michigan大學(xué)的學(xué)生，如：DavidE.Goldberg、KennethA.DeJong、JohnR.Koza、StepanieForrest等。1975年，Holland出版了專(zhuān)著《自然與人工系統(tǒng)中的話(huà)應(yīng)性行為》(AdaptationinNaturalandArtificialSystems)[18]，該書(shū)系統(tǒng)地闡述了傳算法的基本理論和方法，提出了對(duì)遺傳算法的理論發(fā)展極為重要的模式理論(schematheory)，其中首次確認(rèn)了選擇、交叉和變異等遺傳算子，以及遺傳算法的隱并行性，并將遺傳算法應(yīng)用于適應(yīng)性系統(tǒng)模擬、函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、自動(dòng)控制等領(lǐng)域。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展另外，DanielJ.Cavicchio的博士論文中探討了一組實(shí)驗(yàn)，將基于整數(shù)編碼的遺傳算法應(yīng)用于模式識(shí)別問(wèn)題，研究了保持群體差異性的選擇策略。DeJong在其博士論文研究中首次把遺傳算法用于函數(shù)優(yōu)化問(wèn)題，并對(duì)遺傳算法的機(jī)理與參數(shù)設(shè)計(jì)問(wèn)題進(jìn)行了較為系統(tǒng)地研究。DeJong深入全面地研究了模式定理和遺傳算子的行為，將其與自己大量實(shí)驗(yàn)工作相結(jié)合，建立了著名的五函數(shù)測(cè)試平臺(tái)。通過(guò)實(shí)驗(yàn)，他給出如下結(jié)論：1.初始群體容量越大，離線(xiàn)性能越好，但在線(xiàn)性能的初始值較差。2.變異可以降低某些基因的丟失機(jī)會(huì)，提高變異概率能避免成熟前收斂，但卻降低在線(xiàn)性能。3交叉概率越大，群體中新結(jié)構(gòu)的產(chǎn)生越快，當(dāng)交叉概率等于0.6時(shí)，在線(xiàn)性能與離線(xiàn)性能都較好。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展1975年之后，遺傳算法作為函數(shù)優(yōu)化器(functionoptimizers)不但在各個(gè)領(lǐng)域得到廣泛應(yīng)用，而且還豐富和發(fā)展了若干遺傳算法的基本理論。1980年，Bethke對(duì)函數(shù)優(yōu)化GA進(jìn)行了研究，包括應(yīng)用研究和數(shù)學(xué)分析。Smith在1980年首次提出使用變長(zhǎng)位串的概念，這在某種程度上為以后的遺傳規(guī)劃莫定了基礎(chǔ)。Goldberg、Davis、Grefenstette、Bauer、Srinivas和Patnaik等大批研究人員對(duì)遺傳算法理論的基本框架和遺傳算子進(jìn)行了構(gòu)建和改進(jìn)，并將遺傳算法分別應(yīng)用于工程設(shè)計(jì)、自動(dòng)控制、經(jīng)濟(jì)金融、博奕問(wèn)題、機(jī)器學(xué)習(xí)等2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展諸多領(lǐng)域之中。1989年，DavidGoldberg出版了GeneticAlgorithmsinSearch，OptimizationandMachineLearning一書(shū)，這是第一本傳算法教科書(shū)，它是對(duì)當(dāng)時(shí)關(guān)于遺傳算法領(lǐng)域研究工作的全面而系統(tǒng)的總結(jié)，因而也成為引用最多的參考書(shū)之一。與Holland的著作側(cè)重于適應(yīng)性系統(tǒng)的進(jìn)化數(shù)學(xué)分析不同，本書(shū)將遺傳算法的基本原理與范圍廣泛的應(yīng)用實(shí)例相結(jié)合，并給出了大量可以使用的應(yīng)用程序。1991年Davis編輯出版了HandbookofGeneticAlgorithms[21]，其中包括了GA在工程技術(shù)和社會(huì)生活中的大量應(yīng)用實(shí)例。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展JohnR.Koza將遺傳算法用于處理不定長(zhǎng)樹(shù)形字符串或一組程序，提出了遺傳規(guī)（geneticprogramming，簡(jiǎn)稱(chēng)GP）的概念。樹(shù)狀表示方法是Koza教授于1989年首次提出的，這種表示方法的主要特點(diǎn)之一就是染色體結(jié)構(gòu)是動(dòng)態(tài)變化的層次結(jié)構(gòu)，它受環(huán)境影響而改變，因而對(duì)問(wèn)題的表示更加自然。該方法是一種與領(lǐng)域無(wú)關(guān)的自適應(yīng)搜索解空間的有效算法。通過(guò)增加染色體結(jié)構(gòu)的復(fù)雜性，它拓廣了傳統(tǒng)遺傳算法的應(yīng)用范圍。Koza教授認(rèn)為不同領(lǐng)域中許多看起來(lái)不相同的問(wèn)題都可看成是尋找一定的計(jì)算機(jī)程序問(wèn)題，即許多不同領(lǐng)域的問(wèn)題都可形式化為程序歸納問(wèn)題，而遺傳規(guī)劃提供了實(shí)現(xiàn)程序歸納的方法，如公式、規(guī)劃（plan）、控制策略、計(jì)算程序模型（Model）、決策樹(shù)、對(duì)策策略（game-playingstrategy）、轉(zhuǎn)換函數(shù)、數(shù)學(xué)表達(dá)式等都稱(chēng)之為計(jì)算機(jī)程序。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展1992年，Koza教授出版了第一本遺傳規(guī)劃專(zhuān)著GeneticProgramming1，兩年之后又出版了第二本關(guān)于遺傳規(guī)劃的專(zhuān)著。Koza教授雖然尚未建立遺傳規(guī)劃的完整理論體系，但他通過(guò)大量的實(shí)驗(yàn)說(shuō)明了遺傳規(guī)劃能夠成功地解決一類(lèi)復(fù)雜問(wèn)題，為基于符號(hào)表示的函數(shù)學(xué)習(xí)問(wèn)題增添了一個(gè)強(qiáng)有力的工具。隨著遺傳算法研究和應(yīng)用的不斷深人與擴(kuò)展，1985年，在美國(guó)召開(kāi)了第一屆遺傳算法國(guó)際會(huì)議，即ICGA(InternationalConferenceonGeneticAlgorithm)。這次會(huì)議是遺傳算法發(fā)展的重要里程碑，此會(huì)以后每隔一年舉行一次。從1999年起，ICGA和GP（GeneticProgrammingSociety）的系列會(huì)議合并為每年一次的遺傳和進(jìn)化國(guó)際會(huì)議（GeneticandEvolutionaryComputationConference，GECCO）。2遺傳算法的發(fā)展歷程2.2遺傳算法的發(fā)展在歐洲，從1990年開(kāi)始也每隔一年舉辦一次類(lèi)似的會(huì)議，即PPSN（ParallelProblemSolvingfromNature）會(huì)議。以遺傳算法理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議FOGA（FoundationofGeneticAlgorithm）也從1990年起每隔一年舉辦一次。2遺傳算法的發(fā)展歷程2.3遺傳算法的改進(jìn)標(biāo)準(zhǔn)遺傳算法的主要本質(zhì)特征，在于群體搜索策略和簡(jiǎn)單的遺傳算子，這使得遺傳算法獲得了強(qiáng)大的全局最優(yōu)解搜索能力、問(wèn)題域的獨(dú)立性、信息處理的并行性、應(yīng)用的魯棒性和操作的簡(jiǎn)明性，從而成為一種具有良好適應(yīng)性和可規(guī)?；那蠼夥椒?。但大量的實(shí)踐和研究表明，標(biāo)準(zhǔn)遺傳算法存在局部搜索能力差和“早熟”等缺陷，不能保證算法收斂。在現(xiàn)有的許多文獻(xiàn)中出現(xiàn)了針對(duì)標(biāo)準(zhǔn)遺傳算法的各種改進(jìn)算法，并取得了一定的成效。它們主要集中在對(duì)遺傳算法的性能有重大影響的6個(gè)方面：編碼機(jī)制、選擇策略、交叉算子、變異算子、特殊算子和參數(shù)設(shè)計(jì)（包括群體規(guī)模、交叉概率、變異概率）等。此外，遺傳算法與差分進(jìn)化算法、免疫算法、蟻群算法、粒子群算法、模擬退火算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)算法和量子計(jì)算等結(jié)合起來(lái)所構(gòu)成的各種混合遺傳算法，可以綜合遺傳算法和其他算法的優(yōu)點(diǎn)，提高運(yùn)行效率和求解質(zhì)量。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例旅行商問(wèn)題是一種典型的組合優(yōu)化問(wèn)題，在實(shí)際生活和工程中具有廣泛的應(yīng)用。它要求尋找一條路徑，使得旅行商從起點(diǎn)出發(fā)，經(jīng)過(guò)每個(gè)城市僅一次，最終回到起點(diǎn)，并且總路徑長(zhǎng)度最短。然而，隨著城市數(shù)量的增加，問(wèn)題的復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，傳統(tǒng)的精確求解方法在實(shí)際中往往不夠高效。而遺傳算法作為一種啟發(fā)式搜索算法，通過(guò)模擬自然進(jìn)化過(guò)程，可以有效地解決TSP這類(lèi)問(wèn)題。遺傳算法在TSP中的應(yīng)用具有廣泛的場(chǎng)景，包括但不限于以下幾個(gè)方面：物流規(guī)劃：在物流領(lǐng)域，企業(yè)需要規(guī)劃貨物的最優(yōu)配送路線(xiàn)，使得貨物能夠在最短的時(shí)間內(nèi)被送達(dá)客戶(hù)手中。TSP提供了一個(gè)合適的數(shù)學(xué)模型，遺傳算法可以用于求解這類(lèi)問(wèn)題，優(yōu)化配送路徑，降低成本。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例巡回銷(xiāo)售員問(wèn)題：銷(xiāo)售員需要在多個(gè)客戶(hù)之間進(jìn)行拜訪(fǎng)，以盡量減少行程時(shí)間和成本，同時(shí)提高工作效率。遺傳算法可以幫助銷(xiāo)售員規(guī)劃最佳的拜訪(fǎng)路線(xiàn)，使得銷(xiāo)售員的工作更加高效。電路板布線(xiàn)：在電路板布線(xiàn)中，需要設(shè)計(jì)一個(gè)最佳的線(xiàn)路，以減少電路板上的連接距離，從而降低電路板的成本和復(fù)雜度。TSP可以被用來(lái)建模這類(lèi)問(wèn)題，并且遺傳算法能夠找到較優(yōu)的布線(xiàn)方案。DNA測(cè)序：在生物信息學(xué)中，遺傳算法可用于優(yōu)化DNA測(cè)序的順序，以盡量減少讀取DNA片段的成本和時(shí)間。通過(guò)將DNA測(cè)序問(wèn)題轉(zhuǎn)化為T(mén)SP問(wèn)題，并應(yīng)用遺傳算法進(jìn)行求解，可以提高測(cè)序的效率。應(yīng)用方法：3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例01遺傳算法是一種啟發(fā)式優(yōu)化算法，通常包括以下關(guān)鍵步驟：02初始化種群：隨機(jī)生成初始的候選解（路徑），構(gòu)成初始種群。03評(píng)估適應(yīng)度：對(duì)種群中的每個(gè)個(gè)體（路徑）計(jì)算適應(yīng)度，即路徑長(zhǎng)度。04選擇：根據(jù)適應(yīng)度選擇一定數(shù)量的個(gè)體作為父代，用于繁殖下一代。05交叉：對(duì)選出的父代個(gè)體進(jìn)行交叉操作，產(chǎn)生新的個(gè)體（子代）。06變異：對(duì)新生成的個(gè)體進(jìn)行變異操作，增加種群的多樣性。07替換：用新生成的個(gè)體替換原種群中的一部分個(gè)體，形成新一代種群。08重復(fù)迭代：重復(fù)進(jìn)行選擇、交叉、變異和替換操作，直到達(dá)到停止條件。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例具體應(yīng)用步驟遺傳算法在解決旅行商問(wèn)題（TSP）時(shí)，具體的應(yīng)用步驟不僅僅包括基本的初始化種群、評(píng)估適應(yīng)度、遺傳操作和迭代優(yōu)化，還涉及到一系列細(xì)致的步驟和技巧。下面將對(duì)這些步驟進(jìn)行拓展，以便更全面地理解遺傳算法在TSP中的應(yīng)用。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例問(wèn)題建模與數(shù)據(jù)準(zhǔn)備在開(kāi)始應(yīng)用遺傳算法解決TSP之前，首先需要對(duì)問(wèn)題進(jìn)行建模，并準(zhǔn)備好相關(guān)的數(shù)據(jù)。建模的過(guò)程包括確定城市之間的距離或成本，通常使用城市之間的歐氏距離或其他距離度量。數(shù)據(jù)準(zhǔn)備的過(guò)程包括收集城市坐標(biāo)、距離矩陣等相關(guān)信息，并將其轉(zhuǎn)化為算法可以處理的格式。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例初始種群的生成生成初始種群是遺傳算法的第一步，初始種群的好壞直接影響了算法的收斂速度和解的質(zhì)量。除了隨機(jī)生成初始路徑外，還可以采用啟發(fā)式算法（如最近鄰法、最小生成樹(shù)法）生成初始路徑，以提高種群的質(zhì)量。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例適應(yīng)度函數(shù)的設(shè)計(jì)適應(yīng)度函數(shù)用于評(píng)估每個(gè)個(gè)體（路徑）的優(yōu)劣程度，通常是路徑長(zhǎng)度越短，適應(yīng)度越高。除了簡(jiǎn)單地將路徑長(zhǎng)度作為適應(yīng)度外，還可以引入懲罰項(xiàng)（如違反約束的懲罰）或其他啟發(fā)式評(píng)價(jià)指標(biāo)（如路徑的連續(xù)性、平滑性等），以提高算法的搜索效率。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例選擇操作的改進(jìn)選擇操作決定了哪些個(gè)體將被選為父代，直接影響了種群的多樣性和收斂速度。除了常見(jiàn)的輪盤(pán)賭選擇方法外，還可以采用其他選擇策略（如錦標(biāo)賽選擇、隨機(jī)選擇等）來(lái)提高算法的魯棒性和全局搜索能力。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例交叉和變異操作的優(yōu)化交叉和變異是遺傳算法的核心操作，通過(guò)交叉和變異可以產(chǎn)生新的個(gè)體，增加種群的多樣性。在TSP中，可以采用不同的交叉和變異策略（如部分映射交叉、順序交叉、交換變異等），并根據(jù)問(wèn)題的特點(diǎn)和約束條件進(jìn)行相應(yīng)的優(yōu)化和改進(jìn)。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例精英保留策略精英保留策略是指在遺傳算法的迭代過(guò)程中保留一定數(shù)量的最優(yōu)個(gè)體，防止優(yōu)秀解的丟失，從而加速算法的收斂過(guò)程。在TSP中，可以定期更新種群，并保留一定數(shù)量的最優(yōu)個(gè)體，以保證算法朝著更優(yōu)解的方向發(fā)展。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例參數(shù)調(diào)優(yōu)與收斂判斷遺傳算法中有許多參數(shù)需要調(diào)優(yōu)，如種群大小、交叉概率、變異概率等。通過(guò)對(duì)這些參數(shù)進(jìn)行調(diào)優(yōu)，可以提高算法的性能和收斂速度。同時(shí)，還需要設(shè)計(jì)有效的收斂判斷標(biāo)準(zhǔn)，以判斷算法是否達(dá)到停止條件，如最大迭代次數(shù)、種群適應(yīng)度的變化情況等。3遺傳算法在旅行商問(wèn)題中的應(yīng)用舉例并行化與優(yōu)化加速為了提高算法的計(jì)算效率和處理能力，可以采用并行化和優(yōu)化加速的技術(shù)。通過(guò)將算法的不同部分進(jìn)行并行化處理，可以加速算法的運(yùn)行速度，降低求解時(shí)間。同時(shí)，還可以利用硬件加速（如GPU加速、分布式計(jì)算等）來(lái)進(jìn)一步提高算法的效率和性能。01應(yīng)用意義和挑戰(zhàn)應(yīng)用意義和挑戰(zhàn)遺傳算法在解決旅行商問(wèn)題（TSP）中的應(yīng)用具有重要的意義，同時(shí)也面臨著一系列挑戰(zhàn)。下面將對(duì)其應(yīng)用意義和挑戰(zhàn)進(jìn)行進(jìn)一步的拓展和深入探討。02應(yīng)用意義應(yīng)用意義高效求解復(fù)雜問(wèn)題：TSP屬于NP難題，傳統(tǒng)的精確求解方法往往難以應(yīng)對(duì)大規(guī)模問(wèn)題。遺傳算法作為一種啟發(fā)式優(yōu)化算法，具有較強(qiáng)的全局搜索能力和適應(yīng)性，能夠在合理的時(shí)間內(nèi)找到近似最優(yōu)解，有效應(yīng)對(duì)復(fù)雜問(wèn)題的求解。廣泛應(yīng)用于實(shí)際場(chǎng)景：TSP問(wèn)題在現(xiàn)實(shí)生活和工程中有著廣泛的應(yīng)用，如物流規(guī)劃、交通路線(xiàn)優(yōu)化、生產(chǎn)排程、網(wǎng)絡(luò)設(shè)計(jì)等。遺傳算法能夠幫助優(yōu)化這些問(wèn)題的解決方案，提高資源利用率、降低成本開(kāi)銷(xiāo)、提升效率和服務(wù)質(zhì)量。靈活性和可擴(kuò)展性：遺傳算法具有較高的靈活性和可擴(kuò)展性，可以根據(jù)問(wèn)題的特點(diǎn)和需求進(jìn)行定制和優(yōu)化。通過(guò)調(diào)整算法的參數(shù)和策略，可以適應(yīng)不同規(guī)模和復(fù)雜度的問(wèn)題求解，具有較強(qiáng)的適應(yīng)性和通用性。應(yīng)用意義探索解空間：遺傳算法不僅能夠找到最優(yōu)解，還能夠探索解空間中的多個(gè)局部最優(yōu)解，為決策提供多樣化的選擇。這對(duì)于多目標(biāo)優(yōu)化和決策支持具有重要意義，有助于找到更全面和多樣化的解決方案。03挑戰(zhàn)與問(wèn)題挑戰(zhàn)與問(wèn)題局部最優(yōu)解：遺傳算法容易陷入局部最優(yōu)解，特別是在復(fù)雜的問(wèn)題中，存在多個(gè)局部最優(yōu)解時(shí)更為明顯。解決方法包括增加種群的多樣性、引入隨機(jī)因素等。參數(shù)調(diào)優(yōu)：遺傳算法有許多參數(shù)需要調(diào)優(yōu)，如種群大小、交叉概率、變異概率等，不同參數(shù)設(shè)置會(huì)影響算法的性能和收斂速度。需要通過(guò)實(shí)驗(yàn)和經(jīng)驗(yàn)來(lái)確定最佳參數(shù)組合。收斂速度：遺傳算法在求解復(fù)雜問(wèn)題時(shí)往往需要大量的迭代次數(shù)，收斂速度較慢。優(yōu)化方法包括改進(jìn)交叉和變異操作、引入局部搜索等技術(shù)來(lái)加速收斂過(guò)程。問(wèn)題約束和實(shí)時(shí)性：實(shí)際問(wèn)題往往存在各種約束條件，如時(shí)間窗口、容量限制等，這增加了問(wèn)題的復(fù)雜度。同時(shí)，一些問(wèn)題需要實(shí)時(shí)求解，要求算法具有較高的實(shí)時(shí)性和響應(yīng)速度。規(guī)模擴(kuò)展性：隨著問(wèn)題規(guī)模的增加，遺傳算法的求解時(shí)間和內(nèi)存消耗也會(huì)增加，限制了其在大規(guī)模問(wèn)題上的應(yīng)用。因此，需要研究并行化和分布式算法等技術(shù)，提高算法的規(guī)模擴(kuò)展性和計(jì)算效率。挑戰(zhàn)與問(wèn)題多樣性保持：種群的多樣性對(duì)于算法的搜索性能至關(guān)重要，但過(guò)早的收斂和種群過(guò)度聚集會(huì)導(dǎo)致多樣性喪失。需要設(shè)計(jì)合適的操作來(lái)保持種群的多樣性，如多樣性保持策略和種群調(diào)節(jié)機(jī)制等。04解決方法與技術(shù)解決方法與技術(shù)1多樣性保持策略：引入精英保留策略、多樣性保持機(jī)制等，避免種群陷入局部最優(yōu)解，保持種群的多樣性和魯棒性。2算法優(yōu)化與改進(jìn)：不斷改進(jìn)和優(yōu)化遺傳算法的交叉、變異、選擇等操作，提高算法的搜索效率和收斂速度。3參數(shù)自適應(yīng)調(diào)整：引入?yún)?shù)自適應(yīng)調(diào)整機(jī)制，根據(jù)算法的運(yùn)行狀態(tài)和問(wèn)題的特點(diǎn)動(dòng)態(tài)調(diào)整參數(shù)，提高算法的魯棒性和適應(yīng)性。4并行化與分布式計(jì)算：利用并行化和分布式計(jì)算技術(shù)，加速算法的運(yùn)行速度，提高處理能力和規(guī)模擴(kuò)展性。5混合算法與元啟發(fā)式方法：將遺傳算法與其他優(yōu)化算法結(jié)合，形成混合算法或采用元啟發(fā)式方法，利用各種算法的優(yōu)勢(shì)互補(bǔ)，提高問(wèn)題求解的效率和質(zhì)量。解決方法與技術(shù)問(wèn)題約束的處理：設(shè)計(jì)有效的約束處理機(jī)制，如罰函數(shù)法、修復(fù)操作等，保證算法在滿(mǎn)足約束條件的前提下進(jìn)行優(yōu)化。遺傳算法求解旅行商問(wèn)題的Python實(shí)現(xiàn)：首先，我們需要導(dǎo)入必要的庫(kù)：importnumpyasnpimportrandom然后，定義TSP問(wèn)題的一些參數(shù)和函數(shù)。假設(shè)有一些城市的坐標(biāo)，我們將通過(guò)歐氏距離來(lái)計(jì)算城市之間的距離。還需要定義一些遺傳算法的參數(shù)，如種群大小、交叉率、變異率等。#城市坐標(biāo)解決方法與技術(shù)cities=np.array([[0,0],[1,2],[3,1