遺傳算法的原理及組成淺析

金天坤 高 揚(yáng)

（大慶師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，黑龍江 大慶 163712）

遺傳算法(GA)是一種宏觀意義下的仿生算法，它模擬的機(jī)制是一切生命智能的產(chǎn)生與進(jìn)化過程。作為一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化方法，它對模型的表達(dá)式?jīng)]有特定的要求，如目標(biāo)函數(shù)用約束函數(shù)的連續(xù)性、可微性等函數(shù)解析性質(zhì)的限制，還具有全局優(yōu)化性、穩(wěn)健性與可操作的簡單性等優(yōu)點(diǎn)。

1 遺傳算法的主要步驟及

遺傳算法操作的是一群編碼化的可行解，稱作種群p（t）。它通過種群的更新與迭代來搜索全局最優(yōu)解。種群的迭代是通過選擇、雜交和變異等具有生物意義的遺傳算子來實(shí)現(xiàn)的。在算法中，進(jìn)化過程是通過一代群體p（t）向下一代群體p（t+1）的演化完成的,每一代群體由若干個(gè)個(gè)體組成，每個(gè)個(gè)體稱為一個(gè)染色體，而每個(gè)染色體是一系基因組成的基因串。每個(gè)染色體由于其中所含基因排列方式的不同而表現(xiàn)出不同的性能[1]。

算法在整個(gè)優(yōu)化過程中的遺傳操作是隨機(jī)的，但它所呈現(xiàn)出的特性并不是完全隨機(jī)的搜索，它能有效的利用歷史信息來推測下一代的期望性能有所提高的尋優(yōu)點(diǎn)集,這樣反復(fù)進(jìn)行,最后收斂到一個(gè)最優(yōu)解。

2 遺傳算法的組成

遺傳算法主要由幾個(gè)部分組成:編碼方式、適應(yīng)度函數(shù)、遺傳操作、算法終止條件。要利用遺傳算法成功的解決優(yōu)化問題,每個(gè)部分的設(shè)計(jì)都非常關(guān)鍵。

2.1 編碼

編碼原理遺傳算法不是對所求問題的實(shí)際優(yōu)化變量直接操作，而是對表示可行解的遺傳編碼（即個(gè)體)作遺傳操作。因此遺傳算法中在進(jìn)行搜索之前需要把解空間的可行解轉(zhuǎn)換為搜索空間的基因型結(jié)構(gòu)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點(diǎn)。編碼問題實(shí)際上是問題空間到表示空間的映射問題。

一個(gè)好的編碼方法，有可能會(huì)使得交叉運(yùn)算、變異運(yùn)算等遺傳操作可以簡單地實(shí)現(xiàn)和執(zhí)行[2]。

通常的編碼方法包括:①二進(jìn)制編碼方法；②格雷碼編碼方法；③浮點(diǎn)數(shù)編碼方法。

符號編碼方法:①多參數(shù)級聯(lián)編碼方法；②多參數(shù)交叉編碼方法。

2.2 適應(yīng)度函數(shù)的設(shè)計(jì)

從數(shù)學(xué)角度看,遺傳算法實(shí)質(zhì)上是一種溉率性捜索算法。但它也具有一定的智能特怔。遺傳算法是在適應(yīng)度函數(shù)的指導(dǎo)下進(jìn)行搜索。而不是窮舉式的全面搜索。適應(yīng)度函數(shù)評估是選擇操作的依據(jù)。各個(gè)體適應(yīng)度函數(shù)值的大小決定了它們是繼續(xù)繁衍還是消亡。相當(dāng)于是自然界中各生物對環(huán)境的適應(yīng)能力的大小。通常，適應(yīng)度大的個(gè)體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)。再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。改變種群內(nèi)部結(jié)構(gòu)的操怍皆通過適應(yīng)度加以控制。適應(yīng)度函數(shù)的選取直接影響到遺傳的收斂性及收斂速度。

2.2 遺傳操作

基本遺傳搡作包括:選擇、交叉、變異。

1）選擇。選擇操作決定如何從當(dāng)前種群中選取個(gè)體作為產(chǎn)生下一代種群的父代個(gè)體。不同的選擇策略將導(dǎo)致不同的選擇壓力，即最佳個(gè)體選中的概率與平均中概率的比值。但也較容易出現(xiàn)過早收斂現(xiàn)象；較小的選擇壓力能使種群保持足夠的多樣性。從而增大算法收斂到全局最優(yōu)的概率,但算法收斂速度一般較慢。

常用的選擇方法有:

①基于比例的適應(yīng)度分配(proportional fitness assignment)方法

在現(xiàn)代社會(huì)的新形勢下，森林保護(hù)工作的重要性不言而喻。面對森林保護(hù)所帶來的巨大利益，我們更應(yīng)該堅(jiān)定信心，努力做好森林保護(hù)工作，讓森林發(fā)揮出巨大的作用。并且我們還要隨時(shí)關(guān)注森林保護(hù)過程中存在的問題，并且要對這些問題提出相應(yīng)的解決措施，還要注意讓森林保護(hù)工作落到實(shí)處，真正的為我國的環(huán)境保護(hù)做出相應(yīng)的貢獻(xiàn)。

基干適應(yīng)度比例的選擇方法利用比例于各個(gè)體適應(yīng)的概率決定其子孫的遺留可能性。包括繁殖池選擇（breeding pool selection）、輪盤賭選擇（roulette wheel selection）等方法。

②基于排名的適應(yīng)度分配(rank-based fitness assignment)方法

基于排名的選擇方法包括線性排名選擇和非線性排名選擇等方法，是將種群中的個(gè)體按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個(gè)體在種群中的序位,而不是實(shí)際的目標(biāo)值。

常用選擇方法還包括局部選擇、截?cái)噙x擇、錦標(biāo)賽選擇、穩(wěn)態(tài)繁殖等。

2）交叉

在生物的自然進(jìn)化過程中，兩個(gè)同源染色體通過交叉而重組形成新的染色體，從而產(chǎn)生出新的個(gè)體或物種。交配重組是生物遺傳和進(jìn)化過程中的一個(gè)主要壞節(jié)。模仿這個(gè)環(huán)節(jié),在遺傳算法中也使用交叉算子來產(chǎn)生新的個(gè)體。

常用的幾種交叉算子有：

②二進(jìn)制交叉；單點(diǎn)交叉；多點(diǎn)交叉；均勻交叉；洗牌交叉；縮小代理交叉。

3）變異

變異是遺傳算法中保持生物多樣性的一個(gè)重要途徑。它以一定概率選擇某一基因座,通過改變該基因座的基因值來獲取新個(gè)體。

算法中的適應(yīng)值函數(shù)要求是非負(fù)的，而一般優(yōu)化問題的目標(biāo)函數(shù)并不滿足這個(gè)條件。常用的實(shí)現(xiàn)變異的適應(yīng)度變換有以下三種[3]：

（1）線性尺度變換。假定J是原適應(yīng)度度量。J′是變換后新的適應(yīng)度置。 則線性尺度變換的變換公式是 J′（A)=aJ（A）+β，?A∈H

這里α是縮放因子，β是平移參數(shù)，H為所有個(gè)體構(gòu)成的個(gè)體空間。其變換效果取決于對參數(shù)α，β的選取。這兩個(gè)參數(shù)的選取必須滿足兩個(gè)條件:第一、平均適應(yīng)值等于原平均適應(yīng)值Jmg；第二,新適應(yīng)度度置的最大值是頃平均值的指定倍數(shù),即Ji-mg=cJmg,其中C一般取為2。

（2）乘幕尺度變換。 變換公式為：J′=aJ（A）+β，?A∈HL

即新的適應(yīng)度是原適應(yīng)度的某個(gè)指定乘幕。幕指數(shù)K與變換目的及所求解的問題有關(guān)。

（3）指數(shù)尺度變換換公式為：J′=aJ（A）+β，?A∈HL

指數(shù)比例既可以讓非常好的個(gè)體保持較多的復(fù)制機(jī)會(huì)，同時(shí)又限制了其復(fù)制數(shù)目以免它很快的控制整個(gè)群體。

3遺傳算法的不足及改進(jìn)

通過分析，可以看出在用遺傳算法進(jìn)行路徑規(guī)劃時(shí)，隨機(jī)產(chǎn)生初始種群，為了避免陷人局部極值點(diǎn)，種群數(shù)量要達(dá)到 一定的規(guī)模。但種群規(guī)模大會(huì)導(dǎo)致搜索空間較大，刪除冗余個(gè)體的能力較差，大大影響路徑規(guī)劃的速度。特別在環(huán)境較為復(fù) 雜的情形下，這種缺點(diǎn)就更加明顯。

為了更好地發(fā)揮遺傳算法的作用，眾多學(xué)者從各方面對算法進(jìn)行深人研究和討論，目前的改進(jìn)策略大致可以分為以下兩方面[4]：

（1）改進(jìn)遺傳算法的各組成部分。如:設(shè)計(jì)新的編碼方式、動(dòng)態(tài)的、自適應(yīng)的參數(shù)操作、新奇的遺傳操作等，來進(jìn)一步改 善算法的性能(如:收斂速度慢、早熟、易陷入局部最優(yōu)解等)。

（2）由于遺傳算法的操作簡單，較容易與其他方法結(jié)合,實(shí)驗(yàn)研究表明這種改進(jìn)相對是比較有效的。如:為克服早熟等缺陷，提出與禁搜索（Tabu search)結(jié)合，poths提出基于遷移和人工選擇的遺傳算法；為解決局部優(yōu)的問題，遺傳算法分別與模糊集（Fuzzy set)、與混沌（Chaos)結(jié)合、與單純形、與爬出法、神經(jīng)網(wǎng)絡(luò)、正交設(shè)計(jì)、免疫等結(jié)合來不斷優(yōu)化算法。

在問題越來越復(fù)雜化的今天，遺傳算法也應(yīng)與時(shí)倶進(jìn)，只有通過不同的方式來對算法的結(jié)構(gòu)、參數(shù)、操作不斷改進(jìn)和 提高，才能設(shè)計(jì)高效的遺傳算法，滿足現(xiàn)代社會(huì)的需要。

［1］張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安：西安交通大學(xué)出版社，2000.

［2］張曉績，方浩，戴冠中.遺傳算法的編碼機(jī)制研究[J].信息與控制 ，1997，26（2)：134-139.

［3］周浦城，洪炳鎮(zhèn)，楊敬輝.基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2004，36(7)：880-883.

［4］林銼云，董家禮.多目標(biāo)優(yōu)化的方法與理論[M].吉林：吉林教育出版社，1992.