一種改進的遺傳算法分析

李 可

（吉林電子信息職業技術學院，吉林 吉林 132012）

一種改進的遺傳算法分析

李 可

（吉林電子信息職業技術學院，吉林 吉林 132012）

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

遺傳算法；個體最優；加快收斂

1 遺傳算法使用背景

遺傳算法生根于達爾文的自然選擇學說，其核心思想是模擬自然界中生物的進化，是以“優勝劣汰，適者生存”為基礎的。1975年美國密歇根大學J·Holland教授在自然界遺傳進化理論的啟發下研究出了遺傳算法，它是一種并行的，靠隨機尋優的計算機算法。但是并不能將算法直接投入到各個實際問題中，必須對單一的遺傳算法進行適當的加工，才能將其投入生產生活的使用中。

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

2 遺傳算法的特點

（1）在搜索過程，不需要優化函數導數的存在，也不需要優化函數保持連續。

（2）因為遺傳算法的搜索信息是目標的函數值，因此對函數的性質沒有任何要求，在實際應用中具有較好的普適性，并且可以非常方便地和其他算法進行融合，即易擴充性。

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

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

（5）遺傳算法在對大規模問題的處理方面表現良好，而對于較小規模較簡單的問題效果則不是特別好。

3 遺傳算法基本原理

遺傳算法是一種使用計算機模擬大自然生物的遺傳的自適應性算法。遺傳算法首先效仿生物的遺傳進化過程，從而構造出獨特的計算模型。因為遺傳算法有機地結合了計算機和自然遺傳兩個學科、因此遺傳算法是一種嶄新的高效的算法。遺傳算法所擁有的最大優點是對于任何問題的求解都與初始條件無關，因此該算法搜索最優解的能力極強。

作為計算機學科，遺傳算法的完成需要以下兩種數據轉換，分別是算法開始前的，從表現型到基因型的轉換和算法完成之后的，從基因型到表現型的轉換。前者指的是編碼操作，即搜索空間中的參數或遺傳空間中的染色體，對其進行轉換；后者指的是譯碼操作，即將染色體或個體通過轉換得到最優解。基礎遺傳算法流程圖如圖1所示。

圖1 基礎遺傳算法流程

傳算法過程分為以下5個階段：

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

4 算法改進

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

本文給出一個智能交叉算子，把傳統的交叉操作分解成智能交叉算子與變異算子兩個部分。對智能交叉算子操作得到新的最優個體，這個最優個體優于待交叉最優個體。這樣更有利于個體生存，更能適應環境變化。如圖2所示，通過改進算法，找到最優解，可以加快收斂速度，使收斂性更強。

5 結語

本文提出了一種基于交叉算子的改進算法，通過算法改進，找到最優個體，加快收斂速度，克服了過早收斂的缺點。

圖2 改進算法流程

[1]陳國良，王煦法，莊鎮泉，等.遺傳算法及其應用[M].北京：人民郵電出版社，1996.

[2]江建，郭耀煌.模擬退火混合遺傳算法及其實現[J].重慶文理學院學報，2009（5）：65-67.

[3]朱亨榮，劉偉銘，宋丹.改進遺傳算法求解TSP問題[J].湖南工業大學學報，2004（2）：38-40.

[4]周松儒.遺傳算法的混合改進研究及其應用[D].南寧：廣西大學，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

項目名稱：遺傳算法在水污染控制系統中的運用；項目編號：2016012。

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