一種改進(jìn)的遺傳算法分析

李 可

（吉林電子信息職業(yè)技術(shù)學(xué)院，吉林 吉林 132012）

一種改進(jìn)的遺傳算法分析

李 可

（吉林電子信息職業(yè)技術(shù)學(xué)院，吉林 吉林 132012）

遺傳算法是復(fù)雜的非線性科學(xué)和人工智能科學(xué)的前沿，遺傳算法具有不受搜索空間限制性假設(shè)的約束，也不受模型參數(shù)數(shù)目與約束條件的束縛等特點(diǎn)，它的優(yōu)點(diǎn)在于全局尋優(yōu)。文章通過算法改進(jìn)，找到最優(yōu)個(gè)體，加快收斂速度，克服過早收斂的缺點(diǎn)。

遺傳算法；個(gè)體最優(yōu)；加快收斂

1 遺傳算法使用背景

遺傳算法生根于達(dá)爾文的自然選擇學(xué)說，其核心思想是模擬自然界中生物的進(jìn)化，是以“優(yōu)勝劣汰，適者生存”為基礎(chǔ)的。1975年美國(guó)密歇根大學(xué)J·Holland教授在自然界遺傳進(jìn)化理論的啟發(fā)下研究出了遺傳算法，它是一種并行的，靠隨機(jī)尋優(yōu)的計(jì)算機(jī)算法。但是并不能將算法直接投入到各個(gè)實(shí)際問題中，必須對(duì)單一的遺傳算法進(jìn)行適當(dāng)?shù)募庸ぃ拍軐⑵渫度肷a(chǎn)生活的使用中。

遺傳算法包含了很多數(shù)學(xué)概念，如適應(yīng)度函數(shù)，復(fù)制交叉等。在實(shí)際問題中尋找該問題的最優(yōu)解是遺傳問題的主要工作。遺傳算法是對(duì)求解空間沒有很高的要求，對(duì)解集函數(shù)無需求導(dǎo)，因此該算法的優(yōu)點(diǎn)是計(jì)算間接，收斂速度快[1]。所以遺傳算法更加適合求解復(fù)雜的多項(xiàng)式非確定性問題。遺傳算法直接將搜索信息定為目標(biāo)函數(shù)，首先給出一個(gè)確定的范圍，然后并行地對(duì)多個(gè)值同時(shí)進(jìn)行搜索，因此和其他的優(yōu)化算法相比遺傳算法的求解速度更快，更能夠有效地處理多值多變的實(shí)際問題，例如生產(chǎn)調(diào)度問題、旅行商問題、自動(dòng)控制問題、復(fù)雜布局問題以及神經(jīng)網(wǎng)絡(luò)問題。

2 遺傳算法的特點(diǎn)

（1）在搜索過程，不需要優(yōu)化函數(shù)導(dǎo)數(shù)的存在，也不需要優(yōu)化函數(shù)保持連續(xù)。

（2）因?yàn)檫z傳算法的搜索信息是目標(biāo)的函數(shù)值，因此對(duì)函數(shù)的性質(zhì)沒有任何要求，在實(shí)際應(yīng)用中具有較好的普適性，并且可以非常方便地和其他算法進(jìn)行融合，即易擴(kuò)充性。

（3）遺傳算法是一種群體搜索，它可以同時(shí)搜索多個(gè)點(diǎn)，因此具有很高的隱含并行性，通過并行性可以極大地提高計(jì)算速度。

（4）遺傳算法的所有算子，包括選擇、交叉、變異算子都可以使用概率的方式來進(jìn)行，因此該算法具有自適應(yīng)性從而提高了遺傳算法的靈活性和適應(yīng)性，具有良好的全局尋優(yōu)能力。

（5）遺傳算法在對(duì)大規(guī)模問題的處理方面表現(xiàn)良好，而對(duì)于較小規(guī)模較簡(jiǎn)單的問題效果則不是特別好。

3 遺傳算法基本原理

遺傳算法是一種使用計(jì)算機(jī)模擬大自然生物的遺傳的自適應(yīng)性算法。遺傳算法首先效仿生物的遺傳進(jìn)化過程，從而構(gòu)造出獨(dú)特的計(jì)算模型。因?yàn)檫z傳算法有機(jī)地結(jié)合了計(jì)算機(jī)和自然遺傳兩個(gè)學(xué)科、因此遺傳算法是一種嶄新的高效的算法。遺傳算法所擁有的最大優(yōu)點(diǎn)是對(duì)于任何問題的求解都與初始條件無關(guān)，因此該算法搜索最優(yōu)解的能力極強(qiáng)。

作為計(jì)算機(jī)學(xué)科，遺傳算法的完成需要以下兩種數(shù)據(jù)轉(zhuǎn)換，分別是算法開始前的，從表現(xiàn)型到基因型的轉(zhuǎn)換和算法完成之后的，從基因型到表現(xiàn)型的轉(zhuǎn)換。前者指的是編碼操作，即搜索空間中的參數(shù)或遺傳空間中的染色體，對(duì)其進(jìn)行轉(zhuǎn)換；后者指的是譯碼操作，即將染色體或個(gè)體通過轉(zhuǎn)換得到最優(yōu)解?；A(chǔ)遺傳算法流程圖如圖1所示。

圖1 基礎(chǔ)遺傳算法流程

傳算法過程分為以下5個(gè)階段：

（1）編碼并生成初始群體；（2）計(jì)算每個(gè)個(gè)體的適應(yīng)度。若得到最優(yōu)解，則停止運(yùn)算，運(yùn)算結(jié)束，否則繼續(xù)進(jìn)行下一次運(yùn)算；（3）按照事先設(shè)定好的選擇策略，選出一些適應(yīng)度較高的個(gè)體，拋棄其余適應(yīng)度較低的個(gè)體；（4）通過交叉算子生成新的個(gè)體；（5）對(duì)新個(gè)體進(jìn)行變異操作，返回（2）。

4 算法改進(jìn)

作為遺傳算法中三大基本算法之一的交叉算法，在遺傳算法中起著非常重要的作用，是最關(guān)鍵的算法。交叉算子的好壞直接影響著遺傳算法的收斂性，決定著收斂速度。設(shè)計(jì)優(yōu)良的交叉算法能加快收斂速度，提高性能。

本文給出一個(gè)智能交叉算子，把傳統(tǒng)的交叉操作分解成智能交叉算子與變異算子兩個(gè)部分。對(duì)智能交叉算子操作得到新的最優(yōu)個(gè)體，這個(gè)最優(yōu)個(gè)體優(yōu)于待交叉最優(yōu)個(gè)體。這樣更有利于個(gè)體生存，更能適應(yīng)環(huán)境變化。如圖2所示，通過改進(jìn)算法，找到最優(yōu)解，可以加快收斂速度，使收斂性更強(qiáng)。

5 結(jié)語

本文提出了一種基于交叉算子的改進(jìn)算法，通過算法改進(jìn)，找到最優(yōu)個(gè)體，加快收斂速度，克服了過早收斂的缺點(diǎn)。

圖2 改進(jìn)算法流程

[1]陳國(guó)良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

[2]江建，郭耀煌.模擬退火混合遺傳算法及其實(shí)現(xiàn)[J].重慶文理學(xué)院學(xué)報(bào)，2009（5）：65-67.

[3]朱亨榮，劉偉銘，宋丹.改進(jìn)遺傳算法求解TSP問題[J].湖南工業(yè)大學(xué)學(xué)報(bào)，2004（2）：38-40.

[4]周松儒.遺傳算法的混合改進(jìn)研究及其應(yīng)用[D].南寧：廣西大學(xué)，2014.

Analysis of an improved genetic algorithm

Li Ke
（Jilin College of Electronic Information, Jilin 132012, China）

Genetic algorithm is a complex nonlinear science and artificial intelligence science frontier, the genetic algorithm has characteristic of not restrained by the search space restriction hypothesis and not restrained by number and constraint conditions of model parameters, it has the advantages of global optimization. The article finds the optimal individual, speeding up the convergence rate and overcoming the premature convergence through algorithm improvement.

genetic algorithm; individual optimization; accelerating convergence

項(xiàng)目名稱：遺傳算法在水污染控制系統(tǒng)中的運(yùn)用；項(xiàng)目編號(hào)：2016012。

李可（1989— ），女，吉林吉林。