顧　瑋

（徐州高等師范學(xué)?！⌒熘荨?21116）

?

遺傳算法概述

顧瑋

（徐州高等師范學(xué)校徐州221116）

摘要基于遺傳算法，介紹了算法的相關(guān)概念，列出了算法的操作步驟，分析了算法實(shí)現(xiàn)的關(guān)鍵技術(shù)，為以后遺傳算法的應(yīng)用提供了理論支持。

關(guān)鍵詞遺傳算法關(guān)鍵技術(shù)操作步驟

一、遺傳算法簡(jiǎn)介

遺傳算法［1］（Genetic Algorithms，簡(jiǎn)稱GA）是生命科學(xué)與工程科學(xué)互相交叉、互相滲透的產(chǎn)物，其本質(zhì)是一種求解問(wèn)題的高度并行的全局隨機(jī)化搜索算法，它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。

經(jīng)過(guò)中外學(xué)者近20年的研究，遺傳算法不論是在應(yīng)用上、算法設(shè)計(jì)上，還是在基礎(chǔ)理論上，都取得了很大的發(fā)展，已成為信息科學(xué)、計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)和應(yīng)用數(shù)學(xué)等諸多學(xué)科所共同關(guān)注的熱點(diǎn)研究領(lǐng)域。

二、遺傳算法的有關(guān)概念

下面列出了遺傳算法相關(guān)的基本概念。

編碼：染色體中遺傳信息在一個(gè)長(zhǎng)鏈上按一定的模式排列，即進(jìn)行了遺傳編碼。在優(yōu)化問(wèn)題中染色體編碼表現(xiàn)為具體參數(shù)到染色體基因表現(xiàn)形式的映射。

選擇：指決定以一定的概率從種群中選擇若干個(gè)體的操作。選擇過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。

交叉：父代個(gè)體繁殖下一代個(gè)體時(shí)，兩個(gè)父?jìng)€(gè)體的染色體之間通過(guò)交叉重組，即在兩個(gè)染色體的某一位置處被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。這個(gè)過(guò)程又稱為基因重組。

變異：染色體復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使染色體基因發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀。

三、遺傳算法的基本操作

1、遺傳算法的基本操作步驟

遺傳算法所涉及的五大要素為：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定。遺傳算法的運(yùn)行過(guò)程為一個(gè)典型的迭代過(guò)程，其必須完成的工作內(nèi)容和基本步驟如下：

（6）按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；

（7）判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定迭代次數(shù)，不滿足則返回步驟6。

2、實(shí)現(xiàn)遺傳算法的關(guān)鍵技術(shù)

（1）染色體編碼［2］

遺傳算法不能直接處理實(shí)際問(wèn)題的參數(shù)，而只能處理以基因串的形式表達(dá)的染色體。因此要使用遺傳算法就必須把優(yōu)化問(wèn)題解的參數(shù)轉(zhuǎn)換成染色體形式，這一轉(zhuǎn)換操作就叫編碼。

（2）個(gè)體適應(yīng)度評(píng)價(jià)

遺傳算法在搜索過(guò)程中僅以適應(yīng)度函數(shù)［3］作為尋優(yōu)的依據(jù)。遺傳算法的適應(yīng)度函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合，對(duì)適應(yīng)度函數(shù)的唯一要求就是函數(shù)值不能為負(fù)數(shù)。

（3）遺傳算子

在遺傳算法中，通過(guò)編碼組成初始群體后，遺傳操作的任務(wù)就是對(duì)群體的個(gè)體按照它們對(duì)環(huán)境的適應(yīng)程度施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過(guò)程。遺傳算法的遺傳操作包括選擇、交叉和變異三個(gè)基本算子［4］。

①選擇算子

從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫選擇。常用的選擇策略主要有：適應(yīng)度比例法、最佳個(gè)體保留法、期望值方法、排序選擇法和聯(lián)賽選擇法。

②交叉算子

遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉把兩個(gè)父?jìng)€(gè)體的部分基因相互交換而生成新個(gè)體的操作。常用的交叉算子為：?jiǎn)吸c(diǎn)交叉、兩點(diǎn)交叉和均勻交叉。

③變異算子

變異算子就是對(duì)群體中個(gè)體的染色體某些位置的基因發(fā)生變動(dòng)。變異能保證后代群體中個(gè)體的多樣性。常見(jiàn)的變異算子主要有：基本變異算子、均勻變異算子和自適應(yīng)變異。

（4）遺傳算法的運(yùn)行參數(shù)

在遺傳算法的運(yùn)行過(guò)程中，存在著對(duì)其性能產(chǎn)生重大影響的一組參數(shù)。這組參數(shù)在初始化階段或群體進(jìn)化過(guò)程中需要合理的選擇和控制，以使遺傳算法以最佳的搜索軌跡達(dá)到最優(yōu)解。主要的參數(shù)有：

交叉概率一般應(yīng)取較大值。但若取值過(guò)大的話，它又會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算反而產(chǎn)生不利影響；若取值過(guò)小的話，產(chǎn)生新個(gè)體的速度又較慢。

若變異概率取值較大的話，雖然能產(chǎn)生出較多的新個(gè)體，但也有可能破壞掉很多較好的模式；若變異概率取值太小的話，則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟現(xiàn)象的能力就會(huì)較差。

終止代數(shù)是表示遺傳算法運(yùn)行結(jié)束條件的一個(gè)參數(shù)，它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。

⑤遺傳算法的終止條件

遺傳算法迭代過(guò)程的終止，一般采用設(shè)定最大代數(shù)的方法。該方法簡(jiǎn)單易行但不準(zhǔn)確。其次，可以根據(jù)群體的收斂程度來(lái)判斷。最后，在采用精英保留選擇策略的情況下，按每代最佳個(gè)體的適應(yīng)值的變化情況確定。

四、結(jié)束語(yǔ)

本文主要從遺傳算法的相關(guān)概念、基本操作、操作步驟和關(guān)鍵實(shí)現(xiàn)技術(shù)等方面研究了遺傳算法，為遺傳算法的深入研究和應(yīng)用奠定了理論基礎(chǔ)。

參考文獻(xiàn)

［1］陳國(guó)良，王煦法，莊鎮(zhèn)泉，王東生.遺傳算法及其應(yīng)用［M］.北京：人民郵電出版社，2012：51-53.

［2］董敏，霍劍青，王曉蒲.基于自適應(yīng)遺傳算法的智能組卷研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2004，25（1）：82-85.

［3］梁艷春，周春光，李壽范.基于遺傳算法的函數(shù)優(yōu)化問(wèn)題的研究［J］.軟件學(xué)報(bào)，2005，8（9）：701-708.

［4］戴亞非，李曉明.計(jì)算機(jī)自動(dòng)組卷算法分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，16（9）：51-55.

［5］魏平，熊偉潔.用遺傳算法解組卷問(wèn)題的設(shè)計(jì)與實(shí)現(xiàn)［J］.微電子學(xué)與計(jì)算機(jī)，2002（4）：48-50.

［6］丁建立，陳增強(qiáng)，袁著社.遺傳算法與蟻群算法的融合［J］.計(jì)算機(jī)研究與發(fā)展，2003，40（9）：1351-1356.

Overview of Genetic Algorithms

Gu Wei
（Xuzhou Higher Normal School Xuzhou 221116）

AbstractBased on genetic algorithm，introduces the related concepts of the algorithm，lists the steps of the algorithm，and analyzed the key technologies to implement the algorithm，for the application of genetic algorithms to provide theoretical support.

KeywordsGenetic algorithm Key technology Operation steps

中圖分類號(hào)TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)160223-7211

作者簡(jiǎn)介

顧瑋，女，1981年生，漢族，徐州高等師范學(xué)校教師，碩士研究生，研究數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘，系統(tǒng)開(kāi)發(fā)。