遺傳規(guī)律及伴性遺傳經(jīng)典整理(教師版-含答案)

遺傳算法編碼及算子簡(jiǎn)介遺傳算法主要是通過(guò)遺傳操作對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加結(jié)構(gòu)重組處理，從而不斷地搜索出群體中個(gè)體間的結(jié)構(gòu)相似性，形成并優(yōu)化積木塊以逐漸逼近最優(yōu)解。由此可見，必須把群體中的個(gè)體轉(zhuǎn)化成按一定基因結(jié)構(gòu)組成的染色體或個(gè)體，即編碼。編碼原則包括兩條：1.有積極積木塊編碼規(guī)則，即所定編碼應(yīng)當(dāng)易于生成所求問(wèn)題相關(guān)的短距和低階的積木塊。 2.最小字符集編碼規(guī)則，即所定編碼應(yīng)用最小字符集以使問(wèn)題得到自然的表示或描述。規(guī)則一是基于模式定理和積木塊假設(shè)；規(guī)則二提供了一種更為實(shí)用的編碼規(guī)則。評(píng)估編碼策略常采用的規(guī)范有： 1.完備性：?jiǎn)栴}空間中的所有點(diǎn)都能作為GA空間的點(diǎn)表現(xiàn)。 2.健全性：GA空間中的染色體能對(duì)應(yīng)所有問(wèn)題空間中的候選解。 3.非冗余性：染色體和候選解一一對(duì)應(yīng)。這些評(píng)估規(guī)范是獨(dú)立于問(wèn)題領(lǐng)域的普遍準(zhǔn)則。對(duì)某個(gè)具體的應(yīng)用領(lǐng)域而言，應(yīng)該客觀化地比較和評(píng)估該問(wèn)題領(lǐng)域中所用的編碼方法。應(yīng)用遺傳算法進(jìn)行優(yōu)化，首先將問(wèn)題描述成串的形式，以模擬染色體。選擇何種編碼方式對(duì)算法的運(yùn)行有很大的影響。現(xiàn)在，流行的觀點(diǎn)認(rèn)為二進(jìn)制編碼能在相同的范圍內(nèi)表示最多的模式，能充分地體現(xiàn)所謂的隱含并行性。但是，二進(jìn)制編碼方式的精度依賴于染色體的基因位數(shù)及設(shè)計(jì)變量的范圍。因而對(duì)于高精度、多變量問(wèn)題，n值需很大，降低遺傳算法的收斂速度。另外，二進(jìn)制編碼不直接反映真實(shí)的設(shè)計(jì)空間。其它的編碼方式還有：格雷碼編碼、浮點(diǎn)編碼、樹結(jié)構(gòu)編碼 、參數(shù)動(dòng)態(tài)編碼和多維編碼等。 遺傳算法主要有選擇、交叉和突變算子 選擇算子 遺傳算法使用選擇算子或稱復(fù)制算子來(lái)對(duì)種群中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：選擇算子使適 應(yīng)性高的個(gè)體在后代中生存的概率較大，而適應(yīng)度低的個(gè)體生存的概率很小甚至被淘汰。遺傳算法中的選擇操作就是來(lái)確定如何從父代群體中按某種方法選取那些個(gè)體以傳到下一 代群體的一種遺傳算法。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)價(jià)基礎(chǔ)上的。選擇操作的主要目的是為了避免基 因缺失、提高全局收斂性和計(jì)算效率。在遺傳算法中級(jí)很重要的作用。 選擇操作有多種方法，最常用的是輪盤賭法。在具體使用中，應(yīng)根據(jù)問(wèn)題求解的特點(diǎn)采用合適的方法或者混合使用。下面簡(jiǎn)單介紹各種選擇算法：(1) 比例選擇算法 基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比，即適應(yīng)度越高的個(gè)體被選中的概率也越大，反之則小。 (2) 最優(yōu)選擇算法 在遺傳算法的運(yùn)行過(guò)程中，通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷地產(chǎn)出新的個(gè)體 。雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)出越來(lái)越多的優(yōu)良個(gè)體，但由于選擇、交叉、變異等遺傳 操作的隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個(gè)體。由于隨機(jī)操作的原因 ，這種選擇方法的誤差比較大，有時(shí)甚至連適應(yīng)度較高的個(gè)體也選擇不上，由此會(huì)降低群體的平均適應(yīng)度，對(duì)算法的運(yùn)行效率、收斂性都有不利的影響。一般說(shuō)來(lái)，適應(yīng)度最好的個(gè)體要盡可能地保留到下一代群體中。為此可以使用最優(yōu)保留策略進(jìn)化模型，即當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換掉本代群體中經(jīng)過(guò)交叉、變異等操作后所產(chǎn)生的是硬度最低的個(gè)體。最有選擇算法的具體步驟是： 1.找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。 2.若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的迄今為止最好的個(gè)體的適應(yīng)度還高，則以當(dāng) 前群體中的最佳個(gè)體為新的迄今為止的最好個(gè)體。 3.用迄今為止的最好個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。 該方法可確保迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作所破壞，它是遺傳算法收斂性的一個(gè)重要條件。但另一方面，它也容易使得某個(gè)局部最優(yōu)個(gè)體不易被淘汰掉反而快速擴(kuò)散，導(dǎo)致算法的全局搜索能力下降。當(dāng)然，該算法可以推廣到在每一代的進(jìn)化過(guò)程中保留多個(gè)最優(yōu)個(gè)體不參加交叉、變異等遺傳運(yùn)算，而直接講它們選擇到下一代群體中。 (3) 確定式選擇算法 它是按照一種確定的方式來(lái)進(jìn)行選擇操作。 (4)期望值選擇算法 根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望值來(lái)進(jìn)行隨機(jī)選擇運(yùn)算。 (5)無(wú)回放余數(shù)隨機(jī)選擇算法 (6)排序選擇算法 主要思想是：對(duì)群體中的所有個(gè)體按期適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。算法步驟為： 1. 對(duì)群體中的所有個(gè)體按其適應(yīng)度的大小進(jìn)行降序排序。 2. 根據(jù)具體求解問(wèn)題設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè) 個(gè)體。 3. 以各個(gè)個(gè)體所分配到的概率值作為其能夠遺傳到下一代的概率，基于這些概率值用比例選擇的方法來(lái)產(chǎn)生下一代群體。該方法的實(shí)施必須根據(jù)對(duì)所研究問(wèn)題的分析和理解情況預(yù)先設(shè)計(jì)一個(gè)概率分配表，這個(gè)設(shè)計(jì)過(guò)午一定規(guī)律可言。而且，雖然依據(jù)個(gè)體適應(yīng)度之間的大小次序給各個(gè)個(gè)體分配了一個(gè)選擇概率，但由于具體選擇方法，所以排序選擇方法仍具有較大的選擇誤差。 (7)隨機(jī)聯(lián)賽選擇算法 它是一種基于個(gè)體適應(yīng)度之間大小關(guān)系的選擇算法。其基本思路是每次選取集各個(gè)體重適 應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。在聯(lián)賽選擇操作中，只有個(gè)體適應(yīng)度之間的大小比較運(yùn)算，而無(wú)個(gè)體適應(yīng)度之間的算術(shù)運(yùn)算。聯(lián)賽選擇中，每次進(jìn)行適應(yīng)度大小比較的個(gè)體數(shù)目稱為聯(lián)賽規(guī)模。 交叉算子 所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換生成新個(gè)體的操作。這可以提高搜索力。 在交叉運(yùn)算之前還必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。目前常用的配對(duì)策略是隨機(jī)配對(duì)，即將群體中的個(gè)體以隨機(jī)方式兩兩配對(duì)，交叉操作是在配對(duì)個(gè)體之間進(jìn)行的。 交叉算子主要有：一點(diǎn)交叉（不易破壞好的模型），雙點(diǎn)交叉，多點(diǎn)交叉（又稱廣義交叉 ，一般不使用，隨著交叉點(diǎn)的增多，個(gè)體結(jié)構(gòu)被破壞的可能性逐漸增大，影響算法的性能），均勻交叉，算術(shù)交叉等。目前各種交叉操作形式上的區(qū)別是交叉位置的選取方式。下面簡(jiǎn)單介紹幾種交叉方法。 （1）單點(diǎn)交叉 隨機(jī)選取個(gè)體中的某基因位，從此位開始交換兩親本的后面部分序列，以產(chǎn)生兩個(gè)子代。 （2）兩點(diǎn)交叉 隨機(jī)選取個(gè)體中的兩個(gè)基因位，交換兩親本間部分。 （3）OX交叉 隨機(jī)選擇兩個(gè)點(diǎn)，親本在兩個(gè)點(diǎn)間的部分被復(fù)制下來(lái)作為子代的一部分。子代的余下部分從對(duì)應(yīng)親本染色體的其余部分中，先選出第二個(gè)交叉點(diǎn)開始到它的最后一個(gè)基因位的基因按先后次序添入，然后再繼續(xù)按次序取該染色體的第一基因位到第二交叉點(diǎn)的基因依次添入，其中跳過(guò)子代染色體中已含有的基因。此種方法能充分保留親本代基因的相對(duì)次序。 (4)PX交叉 隨機(jī)地選取幾個(gè)位置，子代染色體的這些位置繼承第一親本的相應(yīng)位置，子代染色體的其余位置按第二親本中出現(xiàn)的次序添入，并跳過(guò)已含有的基因。此種方法保留有親本的絕對(duì)位置信息。變異算子在生物的遺傳和自然進(jìn)化過(guò)程中，因?yàn)槟承┡既坏囊蛩囟鴮?dǎo)致生物的某些基因發(fā)生變異，從而產(chǎn)生出新的染色體，表現(xiàn)出新的生物性狀。模仿生物遺傳和進(jìn)化過(guò)程中的變異環(huán)節(jié)，在遺傳算法中也引入了變異算子來(lái)產(chǎn)生新的個(gè)體。變異運(yùn)算就是將個(gè)體染色體編碼串中的某些基因用其它的基因來(lái)替換。它是遺傳算法中不可缺少的部分。目的就是改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。設(shè)計(jì)變異算子需要確定變異點(diǎn)的位置和基因值的替換，最常用的是基本位變異，它只改變編碼串中個(gè)別位的基因值，變異發(fā)生的概率也小，發(fā)揮作用比較慢，效果不明顯。變異算子主要有：均勻變異，它特別適于算法的初期階段，增加群體的多樣性；非均勻變異，隨著算法的運(yùn)行，它使得搜索過(guò)程更加集中在某一個(gè)重點(diǎn)區(qū)域中；邊界變異，適用于最優(yōu)點(diǎn)位于或接近于可行解邊界的問(wèn)題；高斯變異，改進(jìn)了算法對(duì)重點(diǎn)搜索區(qū)域的局部搜索性能。 算子的改進(jìn)和新算子不斷涌現(xiàn)。倒位操作，在染色體中選擇兩個(gè)倒位點(diǎn)，兩點(diǎn)間的基因倒換位置。利用倒位作用的遺傳算法能發(fā)現(xiàn)并助長(zhǎng)有用基因的緊密形式。二倍體與顯性操作，二倍體具有記憶能力，能解決動(dòng)態(tài)環(huán)境下的復(fù)雜系統(tǒng)優(yōu)化問(wèn)題。顯性操作具有魯棒性，有利于提高算子的運(yùn)算效率，維護(hù)好的搜索群體。針對(duì)不同的問(wèn)題，人們研究出各種算子，不斷的進(jìn)行推廣。遺傳算法以個(gè)體的集合為運(yùn)算對(duì)象，對(duì)個(gè)體所進(jìn)行的各種操作都有一定的相互獨(dú)立性，所以它具有一種天然的并行結(jié)構(gòu)。對(duì)基本遺傳算法的運(yùn)行過(guò)程，為實(shí)現(xiàn)并行化，可以從個(gè)體適應(yīng)度評(píng)價(jià)、整個(gè)群體中各個(gè)個(gè)體適應(yīng)度評(píng)價(jià)、子代群體產(chǎn)生過(guò)程、群體分組幾方面考慮。實(shí)現(xiàn)的方法可分為兩類：標(biāo)準(zhǔn)型并行方法