優(yōu)化算法之遺傳算法-pyy

遺傳算法GeneticAlgorithm(GA)主要內(nèi)容遺傳算法簡(jiǎn)介基本原理研究進(jìn)展遺傳算法的流程流程結(jié)構(gòu)應(yīng)用舉例遺傳算法的改進(jìn)算子選擇參數(shù)設(shè)置混合遺傳算法并行遺傳算法遺傳算法的應(yīng)用遺傳算法在生物信息學(xué)中的應(yīng)用遺傳算法是什么？遺傳算法（GeneticAlgorithm，GA）是進(jìn)化計(jì)算的一個(gè)分支，是一種模擬自然界生物進(jìn)化過程的隨機(jī)搜索算法。

遺傳算法的思想來源是怎樣的？它由誰提出的？GA思想源于自然界“自然選擇”和“優(yōu)勝劣汰”的進(jìn)化規(guī)律，通過模擬生物進(jìn)化中的自然選擇和交配變異尋找問題的全局最優(yōu)解。它最早由美國(guó)密歇根大學(xué)教授JohnH.Holland提出，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中。遺傳算法簡(jiǎn)介產(chǎn)生60年代中期，美國(guó)Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(Genetic

Algorithms)”一詞；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。70年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國(guó)召開了第一屆遺傳算法國(guó)際會(huì)議，并且成立了國(guó)際遺傳算法學(xué)會(huì)(ISGA，InternationalSocietyofGeneticAlgorithms)；發(fā)展1989年，Holland的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；1991年，L.Davis編輯出版了《遺傳算法手冊(cè)》，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中大量的應(yīng)用實(shí)例。達(dá)爾文(Darwin)的進(jìn)化論進(jìn)化論是生物學(xué)最基本的理論之一。生物學(xué)上的所謂進(jìn)化或者演化（Evolution），舊稱“天演”，是指生物在變異、遺傳與自然選擇作用下的演變發(fā)展，物種淘汰和物種產(chǎn)生過程。地球上原來無生命，大約在30多億年前，在一定的條件下，形成了原始生命，其后，生物不斷的進(jìn)化，直至今天世界上存在著170多萬個(gè)物種。達(dá)爾文用自然選擇來解釋生物進(jìn)化。自然選擇就是指生物由于環(huán)境中某些因素的影響而使得有利于一些個(gè)體的生存，而不利于另外一些個(gè)體生存的演化過程。簡(jiǎn)而言之——物競(jìng)天擇，適者生存達(dá)爾文的自然選擇說遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個(gè)體之間總有差異，是生命多樣性的根源；生存斗爭(zhēng)和適者生存：具有適應(yīng)性變異的個(gè)體被保留，不具適應(yīng)性變異的個(gè)體被淘汰。自然選擇過程是長(zhǎng)期的、緩慢的、連續(xù)的過程。孟德爾(Mendel)的遺傳學(xué)遺傳學(xué)是研究基因及它們?cè)谏镞z傳中的作用的科學(xué)分支。遺傳學(xué)最早的應(yīng)用在有歷史記載之初就已經(jīng)出現(xiàn)了，即馴養(yǎng)動(dòng)物及植物的選擇育種。遺傳信息以化學(xué)方法被編碼在DNA（脫氧核糖核酸）中。1865年，孟德爾首先記錄了豌豆某些特性的遺傳模式，表明它們遵守簡(jiǎn)單的統(tǒng)計(jì)學(xué)規(guī)律。由他的統(tǒng)計(jì)分析中，孟德爾定義了一個(gè)概念：遺傳的基本單位——等位基因。他描述的等位基因類于現(xiàn)在的基因。直到孟德爾死后，20世紀(jì)初另外的科學(xué)家重新發(fā)現(xiàn)這個(gè)定律之后，孟德爾的工作的重要性才被大家了解。改變一個(gè)生物的DNA從而達(dá)到某種目的被稱為基因工程。生物進(jìn)化過程遺傳基因重組過程群體競(jìng)爭(zhēng)淘汰的群體變異子群種群婚配生物遺傳學(xué)基礎(chǔ)遺傳學(xué)基本概念與術(shù)語染色體（chromosome）：遺傳物質(zhì)的載體；脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)；遺傳因子（gene）：DNA或RNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；遺傳學(xué)基本概念與術(shù)語基因型（genotype）：遺傳因子組合的模型，染色體的內(nèi)部表現(xiàn)；表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)，基因型形成的個(gè)體；ATCGTAATCATA遺傳學(xué)基本概念與術(shù)語個(gè)體（individual）：指染色體帶有特征的實(shí)體；種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大??；種群大?。悍N群中個(gè)體的數(shù)量，也叫群體規(guī)模。遺傳學(xué)基本概念與術(shù)語進(jìn)化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；適應(yīng)度（fitness）：個(gè)體性能的數(shù)量值，度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕;遺傳學(xué)基本概念與術(shù)語選擇（selection）：指決定以一定的概率從種群中選擇若干個(gè)體的操作；復(fù)制（reproduction）：細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因;交叉（crossover）：在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。又稱基因重組，俗稱“雜交”;遺傳學(xué)基本概念與術(shù)語變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。進(jìn)化論與遺傳學(xué)的融合

1930～1947年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，Th.Dobzhansky1937年發(fā)表的《遺傳學(xué)與物種起源》是融合進(jìn)化論與遺傳學(xué)的代表作。生物進(jìn)化與智能學(xué)的關(guān)系

生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、自組織和自優(yōu)化能力，這是一種生物在進(jìn)化過程中體現(xiàn)的智能，也是人工系統(tǒng)夢(mèng)寐以求的功能。如何借鑒？對(duì)于一個(gè)優(yōu)化問題，一定數(shù)量的候選解（生命個(gè)體）被表示為抽象的數(shù)字串（染色體），通過進(jìn)化向更好的解發(fā)展。選解一般為二進(jìn)制數(shù)字串（即0和1），但也可能有其他表示。一開始，生命個(gè)體完全隨機(jī)產(chǎn)生，之后一代一代的進(jìn)化，在進(jìn)化過程中的每一代，每一個(gè)個(gè)體的適應(yīng)程度被評(píng)價(jià)，通過自然選擇和變異產(chǎn)生新的生命群體，該群體就是下一代的個(gè)體。選擇運(yùn)算群體p(t)交叉運(yùn)算變異運(yùn)算解碼群體p(t+1)解集合個(gè)體評(píng)價(jià)遺傳空間解空間編碼遺傳算法原理在遺傳算法中，問題的每個(gè)有效解被稱為一個(gè)“染色體

(chromosome)”，也稱為“串”，對(duì)應(yīng)于群體中的每個(gè)生物個(gè)體(individual）。染色體的具體形式是一個(gè)使用特定編碼方式生成的編碼串，編碼串中的每一個(gè)編碼單元稱為"基因(gene)"遺傳算法通過比較適應(yīng)值(fitnessvalue)區(qū)分染色體的優(yōu)劣，適應(yīng)值越大的染色體越優(yōu)秀。評(píng)估函數(shù)(evaluationfunction)用來計(jì)算并確定染色體對(duì)應(yīng)的適應(yīng)值。遺傳算法原理選擇算子(selection)按照一定的規(guī)則對(duì)群體的染色體進(jìn)行選擇，得到父代種群。一般情況下，越優(yōu)秀的染色體被選中的次數(shù)越多。交叉算子(crossover)作用于每?jī)蓚€(gè)成功交配的父代染色體，染色體交換各自的部分基因，產(chǎn)生兩個(gè)子代染色體。子代染色體取代父代染色體進(jìn)入新種群，而沒有交配的染色體則直接進(jìn)入新種群。變異算子(mutation)使新種群進(jìn)行小概率的變異。染色體發(fā)生變異的基因改變數(shù)值，得到新的染色體。經(jīng)過變異的新種群替代原有群體進(jìn)入下一次進(jìn)化。遺傳算法類似于自然進(jìn)化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。遺傳算法對(duì)求解問題的本身一無所知，它所需要的僅僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群。再對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。這就是遺傳算法的基本原理。遺傳算法原理遺傳算法原理Holland給出了著名的模式定理(SchemaTheory)

，為遺傳算法提供了理論支持。模式(schema)

是指群體中編碼的某些位置具有相似結(jié)構(gòu)的染色體集合。

假設(shè)染色體的編碼是由0或1組成的二進(jìn)制符號(hào)序列，

模式01***0

則表示以01開頭且以0結(jié)尾的編碼串對(duì)應(yīng)的染色體的集合，即{010000，010010，010100，010110，011000，011010，011100，011110}。遺傳算法原理模式的階(schemaorder):模式中具有確定取值的基因個(gè)數(shù)。

如模式01***0的階為3模式的定義長(zhǎng)度(schemaddefininglength)

是指模式中第一個(gè)具有確定取值的基因到最后一個(gè)具有確定取值的基因的距離，例如模式01***0的定義長(zhǎng)度為5

而模式*1****的定義長(zhǎng)度為0遺傳算法原理Holland的模式定理提出，遺傳算法的實(shí)質(zhì)是通過選擇、交叉、變異的遺傳算子對(duì)模式進(jìn)行搜索。低階、定義長(zhǎng)度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式在群體中的比例將呈指數(shù)級(jí)增長(zhǎng)。隨著進(jìn)化的不斷進(jìn)行，較優(yōu)染色體的個(gè)數(shù)將快速增加。模式定理證明了遺傳算法尋求全局最優(yōu)解的可能性，但不能保證算法一定能找到全局最優(yōu)解。遺傳算法原理積木塊假設(shè)(BuildingBlockHypothesis)

，對(duì)模式定理做了補(bǔ)充，說明遺傳算法具有能夠找到全局最優(yōu)解的能力。積木塊(buildingblock)

是指低階、定義長(zhǎng)度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式。積木塊假設(shè)認(rèn)為在遺傳算法運(yùn)行過程中，積木塊在遺傳算子的影響下能夠相互結(jié)合，產(chǎn)生新的更加優(yōu)秀的積木塊，最終接近全局最優(yōu)解。研究?jī)?nèi)容和方向遺傳算法的流程七個(gè)重要問題:染色體的編碼群體的初始化適應(yīng)值評(píng)價(jià)選擇群體種群交配種群變異算法流程選擇運(yùn)算群體p(t)交叉運(yùn)算變異運(yùn)算解碼群體p(t+1)解集合個(gè)體評(píng)價(jià)遺傳空間解空間編碼染色體的編碼原因：遺傳算法只能處理染色體，不能直接在問題解集上進(jìn)行相應(yīng)操作。應(yīng)用遺傳算法,需要解決問題解的表示,即染色體的編碼編碼:將問題結(jié)構(gòu)變換為位串形式編碼表示的過程；解碼或譯碼:將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程。解空間一個(gè)解的編碼染色體(chromosome)編碼解碼編碼方法二進(jìn)制編碼方法浮點(diǎn)數(shù)編碼方法格雷碼(Gray)符號(hào)編碼

二進(jìn)制編碼方法產(chǎn)生的染色體是一個(gè)二進(jìn)制符號(hào)序列，染色體的每一個(gè)基因只能取值0或1。

假定問題定義的有效解取值空間為[Umin，Umax],其中D為有效解的變量維數(shù)，使用L位二進(jìn)制符號(hào)串表示解的一維變量，則我們可以得到如表4.2所示的編碼方式:二進(jìn)制編碼方法

假設(shè)[Umin，Umax]為[1,64]，采用6位二進(jìn)制符號(hào)串進(jìn)行編碼，則某個(gè)二進(jìn)制符號(hào)串010101代表了數(shù)值22

L位二進(jìn)制編碼的精度為:

二進(jìn)制編碼的最大缺點(diǎn)是長(zhǎng)度較大，當(dāng)要求采用較高的精度或表示較大范圍的數(shù)時(shí)，必須通過增加L來達(dá)到要求?！褚痪S染色體編碼指問題空間映射到染色體空間后，其相應(yīng)的基因呈一維排列構(gòu)成染色體。一維染色體常用的符號(hào)集是二值符號(hào)集{0，1}●如果問題解空間是整數(shù)，其編碼需要兩步確定確定編碼長(zhǎng)度。如果問題解空間范圍為x，那么編碼長(zhǎng)度為

2.確定編碼

●確定編碼，將整數(shù)轉(zhuǎn)換為二進(jìn)制表示形式。方法：除2取余法。例如：9=(1001)2910014210●如果所求解空間包含負(fù)值。如果解空間為整數(shù)，可使用添加符號(hào)位的方法解決，即正數(shù)符號(hào)位為0，負(fù)數(shù)為1+9=(01001)2

-9=(11001)2

如果所求解空間為實(shí)數(shù)空間？確定編碼長(zhǎng)度假設(shè)范圍：[a,b]精度：小數(shù)點(diǎn)后4位至少需要的空間存儲(chǔ)碼長(zhǎng):2.編碼(1)轉(zhuǎn)換為整數(shù)(2)轉(zhuǎn)換為二進(jìn)制

例1

問題的解空間為[-3.0,12.1],求1.02編碼后的結(jié)果，精度為小數(shù)點(diǎn)后4位。1.根據(jù)精度和解空間大小，確定編碼長(zhǎng)度

(1)轉(zhuǎn)化為整數(shù)(2)轉(zhuǎn)化為二進(jìn)制2.編碼(1)轉(zhuǎn)化為整數(shù)

假設(shè)轉(zhuǎn)換公式：

將1100100解碼是多少呢？(2)轉(zhuǎn)化為實(shí)數(shù)依據(jù)上例編寫程序，給定任意N位的染色體，將其轉(zhuǎn)換為解空間為[a,b]的實(shí)數(shù)。(1)轉(zhuǎn)化為整數(shù)doubledecoding(intchrom[]){inti;doublex=0;

returnx;}

(2)轉(zhuǎn)化為實(shí)數(shù)for(i=0;i<L;i++){x=x+pow(2,N-i-1)*chrom[i];}x=a+(x/(pow(2,N)-1)*(b-a);●2.多參數(shù)映射編碼優(yōu)化問題經(jīng)常碰到帶優(yōu)化的參數(shù)不止一個(gè)的情況，因此需要采用多參數(shù)映射編碼。

思想：現(xiàn)將每個(gè)參數(shù)進(jìn)行二進(jìn)制串編碼，然后將這個(gè)子串生成一個(gè)完整的染色體。例如：（2，5，6）----010101110

注：每個(gè)子串的碼長(zhǎng)可以不同。

(2,5,100)----0101011100100

背包問題編碼每個(gè)染色體用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示染色體的編碼長(zhǎng)度等于問題定義的解的變量個(gè)數(shù)染色體的每一個(gè)基因等于解的每一維變量。待求解問題的一個(gè)有效解為則該解對(duì)應(yīng)的染色體編碼為因?yàn)檫@種編碼方法使用的是變量的真實(shí)值，所以浮點(diǎn)數(shù)編碼方法也叫做真值編碼方法。對(duì)于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，用浮點(diǎn)數(shù)編碼來表示個(gè)體時(shí)將會(huì)有一些益處。浮點(diǎn)數(shù)編碼方法格雷碼(Gray)是將二進(jìn)制編碼通過一下變換得到的碼：設(shè)二進(jìn)碼(B1B2…Bn)對(duì)應(yīng)的格雷碼為(G1G2…Gn),則從二進(jìn)碼到格雷碼的轉(zhuǎn)換為：從格雷碼到二進(jìn)碼的轉(zhuǎn)換為:

符號(hào)編碼方法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集可以是一個(gè)字母表，如{A,B,C,D,…}；也可以是一個(gè)數(shù)字序號(hào)表，如{1,2,3,4,5,…}；還可以是一個(gè)代碼表，如{x1,x2,x3,x4,x5,…}，等等。如:旅行商問題群體的初始化群體的初始化遺傳算法在給定的初始進(jìn)化群體中進(jìn)行迭代搜索采用生成隨機(jī)數(shù)的方法，對(duì)染色體的每一維變量進(jìn)行初始化賦值初始化染色體時(shí)必須滿足優(yōu)化問題對(duì)有效解的定義。在算法的開始得到一個(gè)平均適應(yīng)值相對(duì)較高的初始群體再進(jìn)行進(jìn)化來提高算法的求解性能適應(yīng)值評(píng)價(jià)用于評(píng)估各個(gè)染色體的適應(yīng)值，區(qū)分優(yōu)劣為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫做適應(yīng)度函數(shù)(fitnessfunction)。通過計(jì)算適應(yīng)度函數(shù)值來決定染色體的優(yōu)劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)勝劣汰原則。在遺傳算法中，規(guī)定適應(yīng)值越大的染色體越優(yōu)。適應(yīng)度函數(shù)要求能有效地反映每一個(gè)染色體的適應(yīng)能力。若一個(gè)染色體與問題的最優(yōu)解染色體之間的差距較小，則對(duì)應(yīng)的適應(yīng)度函數(shù)值就會(huì)較大。評(píng)估函數(shù)常常根據(jù)問題的優(yōu)化目標(biāo)

來確定，例如求解函數(shù)優(yōu)化問題時(shí)，問題定義的目標(biāo)函數(shù)可以作為評(píng)估函數(shù)的原型。對(duì)于一些求解最大值的數(shù)值優(yōu)化問題，我們可以直接套用問題定義的函數(shù)表達(dá)式。但是對(duì)于其他優(yōu)化問題，問題定義的目標(biāo)函數(shù)表達(dá)式必須經(jīng)過一定的變換。例如TSP的目標(biāo)是路徑總長(zhǎng)度為最短，路徑總長(zhǎng)度變換后就可作為TSP問題的適應(yīng)度函數(shù)：

ωn+1=ω1,d(ωj,ωj+1)表示兩城市間的距離(路徑長(zhǎng)度)。選擇運(yùn)算群體p(t)交叉運(yùn)算變異運(yùn)算解碼群體p(t+1)解集合個(gè)體評(píng)價(jià)遺傳空間解空間編碼遺傳操作遺傳算法的遺傳操作主要有三種：選擇算子(selection)交叉算子(crossover)變異算子(mutation)選擇算子選擇操作也叫做復(fù)制(reproduction)操作，根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。一般地，適應(yīng)度較大(優(yōu)良)的個(gè)體有較大的存在機(jī)會(huì)，而適應(yīng)度較小(低劣)的個(gè)體繼續(xù)存在的機(jī)會(huì)也較小。簡(jiǎn)單遺傳算法采用賭輪選擇機(jī)制.根據(jù)每個(gè)染色體的適應(yīng)值得到群體中所有染色體的適應(yīng)值總和。計(jì)算每個(gè)染色體適應(yīng)值與群體適應(yīng)值總和的比Pi

假設(shè)一個(gè)具有N

個(gè)扇區(qū)的輪盤，每個(gè)扇區(qū)對(duì)應(yīng)群體中的一個(gè)染色體，扇區(qū)的大小與對(duì)應(yīng)染色體的Pi值成正比。交叉算子交叉操作的簡(jiǎn)單方式是:按交叉概率Pc選擇出兩個(gè)父代個(gè)體P1和P2，將兩者的部分碼值進(jìn)行交換。交叉概率的Pc

一般取值為：0.4~0.99之間。隨機(jī)數(shù)

Random(0,1)

小于Pc

，則表示該染色體可進(jìn)行交叉操作隨機(jī)產(chǎn)生一個(gè)有效的交配位置，父代染色體交換位于該交配位置后的所有基因編碼長(zhǎng)度為8，產(chǎn)生一個(gè)在1~7之間的隨機(jī)數(shù)k，假如現(xiàn)在產(chǎn)生的是5,將P1和P2的后3位基因交換：P1的高5位與P2的低三位組成數(shù)串10001001,這就是P1和P2的一個(gè)子代個(gè)體Q1

；P2的高5位與P1的低3位組成數(shù)串11011110,這就是P1和P2的另一個(gè)子代Q2個(gè)體。交換過程如圖所示69單點(diǎn)交叉運(yùn)算的偽代碼:procedure:

One-cutPointCrossoverinput:pC,parentPk,k=1,2,...,popSizeoutput:offspringCkBegin

pos

c()for

k=1topopSize

//popSize:populationsize ifpcrandom[0,1]

//pC:theprobabilityofcrossover

pos=c(pos,k)

else

CkPkend

endwhile(length(pos)>1)

i

random[1,pos];

j

random[1,pos];

if

(i≠j)

p

random[1,L-1];//p:thecutposition,L:thelengthofchromosome

CiPi

[1:p-1]//Pj

[p:L];

CjPj

[1:p-1]//Pi

[p:L

];pospos\{i,j}

endend

outputoffspringCk;end變異操作的簡(jiǎn)單方式就是改變碼串中某個(gè)位置上的數(shù)碼變異概率的Pm一般取值為：0.001~0.1之間。隨機(jī)數(shù)

Random(0,1)小于Pm

，則表示該染色體上的基因可進(jìn)行變異操作隨機(jī)產(chǎn)生一個(gè)有效的變異位置，染色體上位于該位置的基因發(fā)生改變變異算子二進(jìn)制編碼表示的每個(gè)位置的數(shù)碼只有0和1兩種可能，二進(jìn)制編碼的簡(jiǎn)單變異操作是將0與1互換：0變異為1，1變異為0。設(shè)有如下二進(jìn)制編碼：碼長(zhǎng)為8，隨機(jī)產(chǎn)生一個(gè)1~8之間的數(shù)k，假如現(xiàn)在k=5，對(duì)第5位(從右到左)進(jìn)行變異操作，將原來的0變?yōu)?，得到如下數(shù)碼串：浮點(diǎn)數(shù)編碼形式的染色體若某基因發(fā)生變異，則可采用隨機(jī)數(shù)方法隨機(jī)產(chǎn)生一個(gè)滿足問題定義的數(shù)值取代該基因現(xiàn)有的值。procedure:Mutationinput:pM,parentPk,k=1,2,...,popSizeoutput:offspringCkbeginfor

k=1topopSize

//popSize:populationsize forj=1to

L

//L:thelengthofchromosome

ifpMrandom[0,1]

//pM:theprobabilityofmutation

Pk[j]

=1-Pk[j]

; //p:thecutposition

CkPk

[1:j-1]//Pk

[j]//Pk[j+1:L]; end endendoutputoffspringCk;end變異運(yùn)算的偽代碼:算法流程：一般遺傳算法的主要步驟如下Step1初始化規(guī)模為N的群體，其中染色體每個(gè)基因的值采用隨機(jī)數(shù)產(chǎn)生器生成并滿足問題定義的范圍。當(dāng)前進(jìn)化代數(shù)Generation=0。Step2用評(píng)估函數(shù)對(duì)群體中所有染色體進(jìn)行評(píng)價(jià)，分別計(jì)算每個(gè)染色體的適應(yīng)值,保存適應(yīng)值最大的染色體BestStep3采用輪盤賭選擇運(yùn)算對(duì)群體的染色體進(jìn)行選擇操作，產(chǎn)生規(guī)模同樣為N的種群。Step4按照概率Pc從種群中選擇染色體進(jìn)行交叉運(yùn)算。兩兩父代染色體交換部分基因，產(chǎn)生兩個(gè)新的子代染色體，子代染色體取代父代染色體進(jìn)入新種群。沒有進(jìn)行交配的染色體直接復(fù)制進(jìn)入新種群。Step5按照概率Pm對(duì)新種群中染色體的基因進(jìn)行變異操作。發(fā)生變異的基因數(shù)值發(fā)生改變。變異后的染色體取代原有染色體進(jìn)入新群體，未發(fā)生變異的染色體直接進(jìn)入新群體。Step6變異后的新群體取代原有群體，重新計(jì)算群體中各個(gè)染色體的適應(yīng)值。倘若群體的最大適應(yīng)值大于Best的適應(yīng)值，則以該最大適應(yīng)值對(duì)應(yīng)的染色體替代Best，即更新最大適應(yīng)值大于Best。Step7當(dāng)前進(jìn)化代數(shù)Generation加l。如果Generation超過規(guī)定的最大進(jìn)化代數(shù)或Best達(dá)到規(guī)定的誤差要求，算法結(jié)束，Best可表示問題的一個(gè)解;否則返回Step3輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。算法的停止條件最簡(jiǎn)單的有如下兩種：①完成了預(yù)先給定的進(jìn)化代數(shù)則停止；②種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。用遺傳算法求解優(yōu)化問題其中為整數(shù)。用遺傳算法求解優(yōu)化問題其中為整數(shù)。解:(1)確定初始種群①參數(shù)編碼將整數(shù)

x*{0,1,…,31}作為參數(shù)，采用二進(jìn)制進(jìn)行編碼：X=0—>00000，……x=31—>11111②隨機(jī)生成例如:①01001；②11001；

③01000；④10011。③隨機(jī)選擇適者個(gè)體

采用輪盤法，對(duì)初始種群進(jìn)行選擇，使得最優(yōu)秀的個(gè)體獲得最多的生存繁殖機(jī)會(huì)。(3)交叉將選擇出的個(gè)體存入交配池中，用隨機(jī)方法配對(duì)交叉，以產(chǎn)生新一代的個(gè)體①隨機(jī)選擇配對(duì)；②隨機(jī)選擇交叉點(diǎn)；③采用單點(diǎn)交叉，產(chǎn)生新的種群(4)變異在交叉過程中，可能丟失一些重要的遺傳信息(特定位置的1與0)，因而產(chǎn)生變異。為了獲得新的遺傳信息，則需引入適度的變異。遺傳算法的特點(diǎn)遺傳算法是一種基于空間搜索的算法，它通過自然選擇、遺傳、變異等操作以及達(dá)爾文的適者生存的理論，模擬自然進(jìn)化過程來尋找所求問題的答案。因此，遺傳算法的求解過程也可看做是最優(yōu)化過程。遺傳算法并不能保證所得到的是最佳答案，但通過一定的方法，可以將誤差控制在容許的范圍內(nèi)。遺傳算法具有以下特點(diǎn)：

(1)遺傳算法是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)行進(jìn)化；

(2)遺傳算法是從問題解的編碼組開始而非從單個(gè)解開始搜索；(3)遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度值這一信息而非利用導(dǎo)數(shù)或其他輔助信息來指導(dǎo)搜索；

(4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。遺傳算法利用簡(jiǎn)單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，從而解決非常困難的問題。它不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性，導(dǎo)數(shù)存在和單峰等假設(shè)，能從離散的、多極值的、含有噪音的高維問題中以很大的概率找到全局最優(yōu)褲。確定性采樣(DeterministicSampling)排擠模型（CrowdingModel）最佳個(gè)體保存模型（ElitistModel）適應(yīng)值比例模型（fitnessproportionmodel）

排序模型(rank-basedmodel)隨機(jī)錦標(biāo)賽模型(StochastictournamentModel)無回放余數(shù)隨機(jī)采樣(Remainderstochasticsamplingandreplacement)期望值模型(expectedvaluemodel)選擇算子遺傳算法的改進(jìn)遺傳算法的改進(jìn)交配算子單性孢子交配算子邊重組交配算子循環(huán)交配算子順序交配算子部分匹配交配算子多點(diǎn)交配算子算術(shù)交配算子均勻交配算子兩點(diǎn)交配算子邊集合交配算子遺傳算法的改進(jìn)非均勻變異算子高斯變異算子邊界變異算子變異算子

群體規(guī)模N√影響算法的搜索能力和運(yùn)行效率。若N設(shè)置較大，一次進(jìn)化所覆蓋的模式較多，可以保證群體的多樣性，從而提高算法的搜索能力，但是由于群體中染色體的個(gè)數(shù)較多，勢(shì)必增加算法的計(jì)算量,降低了算法的運(yùn)行效率。若N設(shè)置較小，雖然降低了計(jì)算量，但是同時(shí)降低了每次進(jìn)化中群體包含更多較好染色體的能力問。N的設(shè)置一般為20~100。參數(shù)設(shè)置

染色體的長(zhǎng)度L√影響算法的計(jì)算量和交叉變異操作的效果。L的設(shè)置跟優(yōu)化問題密切相關(guān)，一般由問題定義的解的形式和選擇的編碼方法決定。對(duì)于二進(jìn)制編碼方法，染色體的長(zhǎng)度L根據(jù)解的取值范圍和規(guī)定精度要求選擇大小。對(duì)于浮點(diǎn)數(shù)編碼方法，染色體的長(zhǎng)度L跟問題定義的解空間維數(shù)D相同。除了染色體長(zhǎng)度一定的編碼方法，Goldberg等人還提出了一種變長(zhǎng)度染色體遺傳算法MessyGA，其染色體的長(zhǎng)度并不是固定的。參數(shù)設(shè)置

基因的取值范圍R√R視采用的染色體編碼方案而定。對(duì)于二進(jìn)制編碼方法，R={0，1}對(duì)于浮點(diǎn)數(shù)編碼方法，R與優(yōu)化問題定義的解每一維變量的取值范圍相同。參數(shù)設(shè)置交叉概率Pc√決定了進(jìn)化過程中，種群參加交叉運(yùn)算的染色體的平均數(shù)目Pc×N。Pc的取值范圍一般為0.4~0.99也可采用自適應(yīng)的方法調(diào)整算法運(yùn)行過程中的Pc

值參數(shù)設(shè)置變異概率Pm√增加群體進(jìn)化的多樣性，決定了進(jìn)化過程中群體發(fā)生變異的基因平均個(gè)數(shù)。Pm的值不宜過大。因?yàn)樽儺悓?duì)己找到的較優(yōu)解具有一定的破壞作用，如果Pm的值太大，可能會(huì)導(dǎo)致算法目前所處的較好的搜索狀態(tài)倒退回原來較差的情況。Pm的取值一般為0.001~0.1也可采用自適應(yīng)的方法調(diào)整算法運(yùn)行過程中的Pm值參數(shù)設(shè)置適應(yīng)值評(píng)價(jià)√影響算法對(duì)種群的選擇，恰當(dāng)?shù)脑u(píng)估函數(shù)應(yīng)該能夠?qū)θ旧w的優(yōu)劣做出合適的區(qū)分，保證選擇機(jī)制的有效性，從而提高群體的進(jìn)化能力。評(píng)估函數(shù)的設(shè)置同優(yōu)化問題的求解目標(biāo)有關(guān)。評(píng)估函數(shù)應(yīng)滿足較優(yōu)染色體的適應(yīng)值較大的規(guī)定。為了更好地提高選擇的效能，可以對(duì)評(píng)估函數(shù)做出一定的修正。目前主要的評(píng)估函數(shù)修正方法有:令線性變換令乘客變換令指數(shù)變換等參數(shù)設(shè)置終止條件√決定算法何時(shí)停止運(yùn)行，輸出找到的最優(yōu)解。采用何種終止條件，跟具體問題的應(yīng)用有關(guān)。可以使算法在達(dá)到最大進(jìn)化代數(shù)時(shí)停止，最大進(jìn)化代數(shù)一般可設(shè)置為100~1000，根據(jù)具體問題可對(duì)該建議值作相應(yīng)的修改。也可以通過考察找到的當(dāng)前最優(yōu)解的情況來控制算法的停止。例如，當(dāng)目前進(jìn)化過程算法找到的最優(yōu)解達(dá)到一定的誤差要求，則算法可以停止。誤差范圍的設(shè)置同樣跟具體的優(yōu)化問題相關(guān)?；蛘呤撬惴ㄔ诔掷m(xù)很長(zhǎng)的一段進(jìn)化時(shí)間內(nèi)所找到的最優(yōu)解沒有得到改善時(shí)，算法可以停止。參數(shù)設(shè)置混合遺傳算法√提高遺傳算法求解問題的能力。并行組合模擬退火算法(ParallelRecombinationSimulatedAnneali噸，PRSA)并行模擬退火遺傳算法(ParallelSimulatedAnnealingandGeneticAlgorithms,PSAGA)貪婪遺傳算法(GreedyGenetic<Algorithm,GGA)遺傳比率切割算法(GeneticRatio-CutAlgorithm,GRCA)遺傳爬山法(GeneticHillclimbi噸Algorithm，GHA)引人局部改善操作的混合遺傳算法免疫遺傳算法(lmmuneGeneticAlgorithm,IGA)

并行遺傳算法√算法從整體的流程上看仍然是串行的，但是算法運(yùn)行過程中對(duì)每個(gè)染色體的處理卻是具有潛在的并行性。標(biāo)準(zhǔn)型并行方法(StandardParallelApproach)

沒有根本改變遺傳算法整體上的串行計(jì)算結(jié)構(gòu)，只是在算法的某些操作中引入并行計(jì)算技術(shù)，這些操作包括適應(yīng)值計(jì)算、選擇操作、交配操作、變異操作等分解型并行方法(DecompositionParallelApproach)

將整個(gè)群體分解成幾個(gè)子群體，各個(gè)子群體分配到不同的計(jì)算資源上分別獨(dú)立地使用原有的遺傳