遺傳算法的實驗問題

1、遺傳算法的實驗問題實驗問題對函數(shù)求解全局最大值。實驗?zāi)康谋緦嶒灥闹饕康氖峭ㄟ^MATLAB編程，使學(xué)生熟悉并掌握常用的MATLAB函數(shù)，同時對 遺傳算法有個初步的了解。相關(guān)知識遺傳算法是進化算法中產(chǎn)生最早、影響最大、應(yīng)用也比較廣泛的一個研究方向和領(lǐng)域， 其基本思想是由美國密執(zhí)安大學(xué)的John H. Holland教授于1962年率先提出的。1975年， 他出版了專著自然與人工系統(tǒng)中的適應(yīng)性行為（Adaptation in Natural and Artificial Systems）19，該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，確立了遺傳算法的基本數(shù)學(xué) 框架。此后，從事遺傳算法研究的學(xué)者越來

2、越多，使之成為一種通用于多領(lǐng)域中的優(yōu)化算法。遺傳算法是一種基于生物的自然選擇和群體遺傳機理的搜索算法。它模擬了自然選擇和 自然遺傳過程中發(fā)生的繁殖、交配和突變現(xiàn)象。它將每個可能的解看做是群體（所有可能解） 中的一個個體，并將每個個體編碼成字符串的形式，根據(jù)預(yù)定的目標(biāo)函數(shù)對每個個體進行評 價，給出一個適應(yīng)度值。開始時總是隨機地產(chǎn)生一些個體（即候選解），根據(jù)這些個體的適應(yīng) 度利用遺傳算子對這些個體進行操作，得到一群新個體，這群新個體由于繼承了上一代的一 些優(yōu)良性狀，因而明顯優(yōu)于上一代，這樣逐步朝著更優(yōu)解的方向進化。遺傳算法在每一代同 時搜索參數(shù)空間的不同區(qū)域，然后把注意力集中到解空間中期望值最高的

3、部分，從而使找到 全局最優(yōu)解的可能性大大增加。作為進化算法的一個重要組成部分，遺傳算法不僅包含了進化算法的基本形式和全部優(yōu) 點，同時還具備若干獨特的性能：1）在求解問題時，遺傳算法首先要選擇編碼方式，它直接處理的對象是參數(shù)的編碼集而 不是問題參數(shù)本身，搜索過程既不受優(yōu)化函數(shù)連續(xù)性的約束，也沒有函數(shù)導(dǎo)數(shù)必須存在的要 求。通過優(yōu)良染色體基因的重組，遺傳算法可以有效地處理傳統(tǒng)上非常復(fù)雜的優(yōu)化函數(shù)求解 問題。2）若遺傳算法在每一代對群體規(guī)模為n的個體進行操作，實際上處理了大約O（n3）個 模式，具有很高的并行性，因而具有明顯的搜索效率。3）在所求解問題為非連續(xù)、多峰以及有噪聲的情況下，能夠以很大的概率

4、收斂到最優(yōu)解 或滿意解，因而具有較好的全局最優(yōu)解求解能力。4）對函數(shù)的性態(tài)無要求，針對某一問題的遺傳算法經(jīng)簡單修改即可適應(yīng)于其他問題，或 者加入特定問題的領(lǐng)域知識，或者與已有算法相結(jié)合，能夠較好地解決一類復(fù)雜問題，因而 具有較好的普適性和易擴充性。5）遺傳算法的基本思想簡單，運行方式和實現(xiàn)步驟規(guī)范，便于具體使用。遺傳算法對問題的描述對于一個求函數(shù)最大值的優(yōu)化問題（求函數(shù)最小值也雷同），一般可描述為下述數(shù)學(xué)規(guī)劃 模型：（1）式中，X=x1,x2,.,xnT為決策變量，f（X）為目標(biāo)函數(shù)，和為約束條件，U是基本空間，R 是U的一個子集。集合R表示由所有滿足約束條件的解所組成的一個集合，叫做可行解集

5、合。 它們的關(guān)系如圖1所示。圖1最優(yōu)化問題的可行解及可行解集合在遺傳算法中，將n維決策向量X=x1,x2,.,xnT用n個記號Xi（i=1，2，.，n）所組成的符號串X來表示：X = X1X2.Xn X=x1 , x2 ,.,xnT把每個Xi看作一個遺傳基因，它的所有可能取值稱為等位基因，這樣，X就可看做是由n個 遺傳基因所組成的一個染色體。一般情況下，染色體的長度n是固定的，但對一些問題n也 可以是變化的。根據(jù)不同的情況，這里的等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的 實數(shù)值，或者是純粹的一個符號。最簡單的等位基因是由0和1這兩個整數(shù)組成的，相應(yīng)的 染色體就可表示為一個二進制符號串。這種

6、編碼所形成的排列形式X是個體的基因型，與它 對應(yīng)的X值是個體的表現(xiàn)型。通常個體的表現(xiàn)型和基因型是一一對應(yīng)的，但有時也允許基因 型和表現(xiàn)型是多對一的關(guān)系。染色體X也稱為個體X，對于每個個體X，要按照一定的規(guī)則確 定出其適應(yīng)度。個體的適應(yīng)度與其對應(yīng)的個體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目 標(biāo)函數(shù)的最優(yōu)點，其適應(yīng)度越大；反之，其適應(yīng)度越小。在遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體 X的搜索過程來進行的，從而由所有的染色體X就組成了問題的搜索空間。生物的進化是以集團為主體的。與此相對應(yīng)，遺傳算法的運算對象是由M個個體所組成 的集合，稱為群體(或種群)。與生物一

7、代一代的自然進化過程相類似，遺傳算法的運算過程 也是一個反復(fù)迭代的過程，第t代群體記做P(t)，經(jīng)過一代遺傳和進化后，得到第t+1代群 體，它們也是由多個個體組成的集合，記做P(t+1)。這個群體不斷地經(jīng)過遺傳和進化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度高的個體更 多地遺傳到下一代，這樣最終在群體中將會得到一個優(yōu)良的個體X，它所對應(yīng)的表現(xiàn)型X將 達(dá)到或接近于問題的最優(yōu)解X*。生物的進化過程主要是通過染色體之間的交叉和染色體的變異來完成的。與此相對應(yīng)， 遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個進化過程，使用所謂的遺傳算子作用于群體 P(t)中，進行下述遺傳操作，從而得到新一代群體P(t+1

8、)。選擇(selectin)：根據(jù)各個個體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體 P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。交叉(crossover)：將群體P(t)內(nèi)的各個個體隨機搭配成對，對每一對個體，以某個 概率(稱為交叉概率，crossoverrate)交換它們之間的部分染色體。變異(mutation)：對群體P(t)中的每一個個體，以某一概率(稱為變異概率， mutationrate)改變某一個或某一些基因座上的基因值為其他的等位基因。遺傳算法的運算流程遺傳算法的主要運算流程如下：步驟一：初始化。設(shè)置進化代數(shù)計數(shù)器t=0；設(shè)置最大進化代數(shù)T；隨機生成M個個體

9、作 為初始群體P(0)。步驟二：個體評價。計算群體P(t )中各個個體的適應(yīng)度。步驟三：選擇運算。將選擇算子作用于群體。步驟四：交叉運算。將交叉算子作用于群體。步驟五：變異運算。將變異算子作用于群體。群體P(t )經(jīng)過選擇、交叉、變異運算之后 得到下一代群體P(t+1)。步驟六：終止條件判斷。若tWT，則：t=t+1，轉(zhuǎn)到步驟二；若tT，則以進化過程中所 得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出，終止計算。具體的流程示意圖見圖2所示。圖2遺傳算法的運算過程示意2.3基本遺傳算法基于對自然界中生物遺傳與進化機理的模仿，針對不同的問題，很多學(xué)者設(shè)計了許多不 同的編碼方法來表示問題的可行解，開發(fā)了許

10、多種不同的遺傳算子來模仿不同環(huán)境下的生物 遺傳特性。這樣，由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這 些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿， 來完成對問題最優(yōu)解的自適應(yīng)搜索過程?；谶@個共同特點，Goldberg總結(jié)出了一種統(tǒng)一的 最基本的遺傳算法一基本遺傳算法(simple genetic algorithms，簡稱SGA) 20?；具z 傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡 單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本 框架，同時也具有一定的應(yīng)用

11、價值。下面給出基本遺傳算法的構(gòu)成要素：染色體編碼方法?；具z傳算法使用固定長度的二進制符號串來表示群體中的個 體，其等位基因是由二值符號集0，1所組成的。初始群體中各個個體的基因值可用均勻分 布的隨機數(shù)來生成。如：X=100111001000101101就可表示一個個體，該個體的染色體長度是n=18。個體適應(yīng)度評價?；具z傳算法按與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中每 個個體遺傳到下一代群體中的機會多少。為正確計算這個概率，這里要求所有個體的適應(yīng)度 必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個體適應(yīng)度 之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時的處理方法。遺傳算子。基本遺傳算法使用下述三種遺傳算子：選擇運算使用比例選擇算子；交叉運算使用單點交叉算子；變異運算使用基本位變異算子或均勻變異算子。基本遺傳算法的運行參數(shù)。基本遺傳算法有下述4個運行參數(shù)需要提前設(shè)定：N :群體大小，即群體中所含染色體的數(shù)量，一般取為20100。maxgen :遺傳運算的終止進化代數(shù)，一般取為100500。-pc :交叉概率，一般取為0.40.99。pm :變異概率，一般取為0.00010.1。需要說明的是，這里給出的4個運行參數(shù)的取值范圍是在經(jīng)