馮智莉 易國洪,2 李普山 黎慧源 代 瑜

1(武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 湖北 武漢 430205)2(武漢工程大學(xué)智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430205)

0 引 言

人工智能領(lǐng)域中，一個(gè)非常關(guān)鍵的問題是需要在非常龐大并且十分復(fù)雜的解空間中找到最優(yōu)解或者是近似最優(yōu)解。對(duì)這種NP-hard問題[1]，不恰當(dāng)?shù)乃阉鞣椒赡軙?huì)出現(xiàn)組合爆炸的問題[2]，因此找到一個(gè)通用的搜索算法一直都受到相關(guān)領(lǐng)域研究人員的關(guān)注。

最優(yōu)化問題一般可以分成兩類：組合優(yōu)化問題和函數(shù)優(yōu)化問題[3]。其中：函數(shù)優(yōu)化問題即連續(xù)變量的優(yōu)化問題，目標(biāo)對(duì)象是指定區(qū)間的所有變量；而組合優(yōu)化的目標(biāo)對(duì)象則是在無限集中某一個(gè)符合要求的目標(biāo)答案，如旅行商問題[4]TSP 。目前對(duì)于函數(shù)優(yōu)化問題常見的解決策略是精確算法和智能優(yōu)化算法。精確算法包括:整數(shù)規(guī)劃[6]、動(dòng)態(tài)規(guī)劃[7]、線性規(guī)劃算法[5]和分支定界[8-9]等，這些時(shí)間復(fù)雜性較大，適合用于小規(guī)模問題。智能優(yōu)化算法主要包括文獻(xiàn)[10]在1953年提出的模擬退火算法、文獻(xiàn)[11]于1973年提出的遺傳算法GA、文獻(xiàn)[12-14]于1986年提出的禁忌算法、文獻(xiàn)[15]于1992年提出的蟻群算法和文獻(xiàn)[16]以革新的方式使用神經(jīng)網(wǎng)絡(luò)方法。其中，以遺傳算法、模擬退火算法等為代表的指導(dǎo)性搜索法，以貪心算法[17]等算法為代表的局部搜索法，均借鑒了一些自然現(xiàn)象，以及人的思維活動(dòng)來指導(dǎo)搜索活動(dòng)的展開。遺傳算法優(yōu)勢(shì)在于：可以快速地將解空間中的全體解搜索出，全局搜索能力優(yōu)秀[18]，克服了其他算法的快速下降陷阱問題；適合分布式計(jì)算，天然并行性加快了收斂速度。但是相對(duì)的，遺傳算法局部搜索能力不足，簡(jiǎn)單遺傳算法耗時(shí)長(zhǎng)，在進(jìn)化后期搜索效率較低[19]，所以存在一定的早熟收斂的風(fēng)險(xiǎn)。遺傳算法的難點(diǎn)是采用何種選擇方法，在充分保留好的個(gè)體的同時(shí)，又要維持群體的多樣性。

1 基本概念和主要環(huán)節(jié)討論

遺傳算法是諸多進(jìn)化算法中的一種。模擬了自然界中生物自然淘汰的進(jìn)化過程，學(xué)習(xí)不僅可以通過單個(gè)生物個(gè)體的適應(yīng)來完成，還可以通過種群的進(jìn)化來實(shí)現(xiàn)，并將其運(yùn)用到計(jì)算機(jī)模型之中[20]。Darwin 進(jìn)化論中適者生存的原理認(rèn)為，每一代種群最終都會(huì)越來越適應(yīng)環(huán)境。每一個(gè)個(gè)體都會(huì)繼承但不完全繼承父輩的特性，自身會(huì)隨機(jī)的產(chǎn)生一些新特性，只有高度適應(yīng)環(huán)境的個(gè)體才能被保留下來。遺傳算法從代表問題中生成一個(gè)或多個(gè)初代解集(種群)，解集中的解又被稱之為個(gè)體，個(gè)體本質(zhì)上是帶有特征的實(shí)體，經(jīng)過基因編碼來實(shí)現(xiàn)。經(jīng)過適應(yīng)函數(shù)篩選的個(gè)體形成的新的種群，遺傳算法不斷地評(píng)價(jià)每一個(gè)個(gè)體，保證更適應(yīng)環(huán)境的個(gè)體擁有更多的繁殖機(jī)會(huì)。遺傳算法放棄了梯度信息，重視的是種群之間的搜索策略，以及個(gè)體信息在種群內(nèi)的交換，克服了傳統(tǒng)搜索算法難以解決非線性復(fù)雜問題的缺點(diǎn)，具有適合并行處理、魯棒性強(qiáng)、簡(jiǎn)單通用、搜索能力強(qiáng)和運(yùn)用范圍廣的特點(diǎn)[20]。目前已經(jīng)廣泛地運(yùn)用在自適應(yīng)控制、機(jī)器學(xué)習(xí)、組合優(yōu)化、人工生命等領(lǐng)域。

在遺傳算法中，問題的解(表現(xiàn)型)所組成的群體(種群)會(huì)朝著更加適應(yīng)環(huán)境的方向變化。每個(gè)候選解都有一組屬性(個(gè)體染色的編碼信息)，屬性會(huì)根據(jù)一定的比例或者規(guī)則被突變和切割連接。完整的進(jìn)化通常從隨機(jī)生成的個(gè)體群體開始，是一個(gè)迭代過程，每個(gè)迭代中的群體稱為一代。每一代都要用適應(yīng)度函數(shù)(通常是目標(biāo)函數(shù))來衡量篩選更適應(yīng)環(huán)境的個(gè)體；從經(jīng)過選擇的個(gè)體中對(duì)其基因組進(jìn)行修飾(重組并且可能隨機(jī)突變)，將獲得的新的個(gè)體組成新的一代；在種群成熟之前，算法會(huì)不斷地迭代，并可能使用不同的候選解決方案。通常情況下，經(jīng)過數(shù)代進(jìn)化工作，該算法終止時(shí)，基本可以得到令人滿意水平的個(gè)體。

基本遺傳算法的形式描述如算法1所示。

算法1遺傳算法

1: 初始化一個(gè)解集，并評(píng)估每個(gè)個(gè)體的適應(yīng)度

2: Repeat

3: 通過適應(yīng)度函數(shù)篩選出部分個(gè)體

4: 按照“適應(yīng)度越高，被選中的可能性越高”的原則，以一定的比例選擇部分個(gè)體進(jìn)行雜交，產(chǎn)生子代

5: 按照一定比例選擇部分個(gè)體進(jìn)行變異操作

6: until 新種群產(chǎn)生

2 遺傳算法并行化策略

當(dāng)問題的規(guī)模和復(fù)雜程度不斷增加以后，遺傳算法收斂到全局最優(yōu)所花費(fèi)的時(shí)間也更長(zhǎng)。遺傳算法具備天然的并行性，并且并行機(jī)目前也比較普及，為遺傳算法的并行化奠定了基礎(chǔ)。常見的并行化策略主要有以下幾點(diǎn)：

(1) 適應(yīng)度評(píng)價(jià)函數(shù) 個(gè)體適應(yīng)度評(píng)價(jià)需要占用一定的時(shí)間，提升計(jì)算個(gè)體適應(yīng)度的效率，可以通過研究并行化遺傳算法的適應(yīng)函數(shù)，找到并行計(jì)算個(gè)體適應(yīng)度函數(shù)的恰當(dāng)表達(dá)方式，可以有效地提升遺傳算法的選擇效率。該方法依賴于數(shù)值的開發(fā)成果和并行化研究。

(2) 產(chǎn)生新種群 前文已經(jīng)提到遺傳算法中個(gè)體的選擇是同時(shí)完成的，不同個(gè)體的適應(yīng)度相互獨(dú)立的，彼此之間互不影響。在適應(yīng)度函數(shù)評(píng)價(jià)個(gè)體的時(shí)候可以采用并行化策略，因此，計(jì)算個(gè)體適應(yīng)度可以分發(fā)給不同的機(jī)器上完成。同理，簡(jiǎn)單遺傳算法的交叉、變異過程都可以實(shí)現(xiàn)并行化。

(3) 種群分組 前面的方法主要還是根據(jù)遺傳算法本身的特點(diǎn)進(jìn)行改進(jìn)。需要注意的是：可以將一個(gè)遺傳算法用在多個(gè)種群上，例如可以將遺傳算法放在集群環(huán)境中，同時(shí)處理多個(gè)種群。將種群分組則對(duì)簡(jiǎn)單遺傳算法的結(jié)構(gòu)進(jìn)行改進(jìn)，在并行機(jī)上實(shí)現(xiàn)起來相對(duì)來說也更加簡(jiǎn)單。

2.1 四種基本模型

運(yùn)用分而治之的思想，文獻(xiàn)[21]最早在大型的并行計(jì)算機(jī)上應(yīng)用并行遺傳算法PGAs(Parallel Ge-netic Algorithms)。同時(shí)分而治之的思想有多種實(shí)現(xiàn)途徑，目前并行化遺傳算法主要有4類模型：主從模型、孤島模型、鄰域模型、混合模型。

(1) 主從模型 主從模型易于實(shí)現(xiàn)，是遺傳算法的直接并行化方案之一。僅有一個(gè)種群，種群的選擇交叉變異等操作都在主節(jié)點(diǎn)機(jī)上完成，適應(yīng)度的評(píng)價(jià)在從節(jié)點(diǎn)機(jī)完成。從節(jié)點(diǎn)接收主節(jié)點(diǎn)發(fā)送過來的個(gè)體，主節(jié)點(diǎn)獲得從節(jié)點(diǎn)計(jì)算的個(gè)體適應(yīng)度值。文獻(xiàn)[22]設(shè)計(jì)了基于MPI的可重用的主從式PGAs框架；文獻(xiàn)[23]將主從PGAs運(yùn)用到模糊關(guān)聯(lián)規(guī)則的挖掘算法，加速性能比提升了19.1%。

當(dāng)模型需要大量的計(jì)算適應(yīng)度的工作的時(shí)候就可以采用這種并行化方案，但是也存在著主節(jié)點(diǎn)和從節(jié)點(diǎn)之間通信延遲或者瓶頸問題，負(fù)荷不均勻的問題等，導(dǎo)致并行失效。

(2) 孤島模型 孤島模型又被稱為分布式模型或者粗粒度模型，這種模型適合如Transputer的多處理機(jī)系統(tǒng)的MMD機(jī)器或者是集群環(huán)境。先依照節(jié)點(diǎn)機(jī)的個(gè)數(shù)分布成多個(gè)種群(或者是子群體)，子群體在自己所在的節(jié)點(diǎn)機(jī)上運(yùn)行GA，在經(jīng)歷一定的進(jìn)化代數(shù)(進(jìn)化時(shí)間)以后，子群體交換部分個(gè)體，豐富了子群體的多樣性，降低了未成熟就收斂的可能。目前孤島模型的研究熱點(diǎn)主要是確定遷移規(guī)模、遷移拓?fù)湟约斑w移策略問題。文獻(xiàn)[24]將粗粒度并行遺傳算法與動(dòng)態(tài)規(guī)劃相結(jié)合，孤島模型的加速比提升，且通信開銷較小。文獻(xiàn)[25]將遺傳規(guī)劃算法與粗粒度并行遺傳算法結(jié)合，并用語言數(shù)據(jù)實(shí)驗(yàn)證明新算法的預(yù)測(cè)誤差更低。

(3) 鄰域模型 鄰域模型，或稱細(xì)粒度模型，常用于連接機(jī)或者是多處理器系統(tǒng)陣列式SIMD系統(tǒng)的機(jī)器。該模型對(duì)于每個(gè)個(gè)體都在所在的處理機(jī)或者是鄰域處理機(jī)上完成，幾乎沒有全局操作，充分展現(xiàn)了遺傳算法的特性。鄰域模型中的每一個(gè)處理機(jī)都只分配一個(gè)個(gè)體，將一個(gè)個(gè)體視為一個(gè)子群體，子群體只和鄰接子群體交換信息。在文獻(xiàn)[26]中提出了基于GPU的細(xì)粒度并行化遺傳算法，提升了算法的運(yùn)行速度。文獻(xiàn)[27]提出了細(xì)粒度模型在Hadoop的MapReduce上并行編程求解最短路徑，取得了優(yōu)于經(jīng)典遺傳算法的效果。

鄰域模型的關(guān)鍵是采用什么樣的鄰域結(jié)構(gòu)，因?yàn)猷徲蚪Y(jié)構(gòu)極大地影響了個(gè)體在種群當(dāng)中的傳播路徑以及個(gè)體的空間位置。目前采用什么樣的鄰域拓?fù)渥顑?yōu)尚無權(quán)威說法。根據(jù)Shapiro B的理論，在海明距離r>2的時(shí)候，效果較差，并且通過對(duì)r內(nèi)所有鄰域?qū)嶒?yàn)后發(fā)現(xiàn)4鄰域模型比8鄰域模型效果更好。

(4) 混合模型 近幾年來出現(xiàn)了較多的混合模型，主要是將前三種基本模型進(jìn)行整合形成新的層次結(jié)構(gòu)。例如混合模型中有：細(xì)粒度-粗粒度模型、粗粒度粗粒度模型以及粗粒度-主從式模型，上層模型將下層并行結(jié)構(gòu)模型視為一個(gè)種群，下層模型中的子群體則是真實(shí)的子群體(種群)。一般來說下層模型中內(nèi)部信息交換量比較大。文獻(xiàn)[28]提出了一種分層遺傳算法解決了作業(yè)車間調(diào)度問題。

以上的模型根據(jù)其自身的特點(diǎn)來說，各有優(yōu)劣。主從模型適合計(jì)算時(shí)間主要在評(píng)估適應(yīng)度環(huán)節(jié)的問題，使用范圍有限。細(xì)粒度模型對(duì)處理機(jī)的要求比較高，目前就適用于小范圍直徑還是大規(guī)模鄰域尚有爭(zhēng)議。粗粒度模型的通信開銷小，加速比呈線性，因此使用范圍比較廣，適合在通信帶寬低的集群環(huán)境上運(yùn)行，不過，目前對(duì)采用什么樣的遷移策略和遷移規(guī)模來說仍然有待進(jìn)一步的研究?；旌夏Ｐ鸵?yàn)槠渚哂休^好的并行性，是當(dāng)前研究的主流模型，在混合模型當(dāng)中，粗粒度-主從式模型運(yùn)用效果較好[29]。

常見的實(shí)現(xiàn)并行化遺傳算法的并行機(jī)主要有多數(shù)據(jù)流、多指令流的MIMD機(jī)器，粗粒度的并行計(jì)算機(jī)，多數(shù)據(jù)流、單指令流的SIMD機(jī)器，細(xì)粒度的并行計(jì)算機(jī)等，還可以在局域網(wǎng)環(huán)境或者是集群環(huán)境下實(shí)現(xiàn)并行算法。需要根據(jù)具體的實(shí)現(xiàn)方法來選用不同的硬件環(huán)境。

2.2 并行化性能評(píng)估標(biāo)準(zhǔn)

加速比是評(píng)級(jí)多核架構(gòu)性能的主要參數(shù)。加速比是串行和并行時(shí)間的耗時(shí)比。例如并行耗時(shí)5.9單位，串行耗時(shí)95.1單位，那么加速比即為16.12。依據(jù)多核處理器加速比已有的研究，現(xiàn)在對(duì)并行化遺傳算法的評(píng)價(jià)模型進(jìn)行介紹。

2.2.1 固定任務(wù)模型

評(píng)價(jià)并行化遺傳算法的性能的指標(biāo)有很多，其中最常見的就是Amdahl定律中的加速比。

原始的加速比的原理如下：假設(shè)有p個(gè)并行機(jī)，可以組成一個(gè)性能更高的并行化運(yùn)行平臺(tái)。單個(gè)計(jì)算節(jié)點(diǎn)的運(yùn)算速度(即性能)為1，p個(gè)計(jì)算節(jié)點(diǎn)所創(chuàng)建的結(jié)構(gòu)的串行性能為pref(p)。已知加速比為串行運(yùn)行時(shí)間與并行運(yùn)行時(shí)間之比，即：

(1)

式中：T1是串行計(jì)算所需的時(shí)間；Tp是該算法在p個(gè)處理機(jī)組成的并行機(jī)上的運(yùn)行時(shí)間；Sp即為加速比。

假設(shè)問題為w，單個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行任務(wù)的時(shí)間即為：

并行化運(yùn)行平臺(tái)的基本執(zhí)行時(shí)間為：

(2)

(3)

令perf(p)=c,c為常數(shù)，則有：

(4)

式(4)在c=1的時(shí)候就是大型機(jī)之父的理論解析式，系統(tǒng)功效提高的程度和總執(zhí)行時(shí)間以及執(zhí)行方式有關(guān)：

(5)

f是并行處理部分在整個(gè)系統(tǒng)中的占比；對(duì)應(yīng)的，(1-f)就是串行處理的部分在整個(gè)系統(tǒng)中的占比。m是并行處理機(jī)的數(shù)量，Speedup即為加速比。固定模型的三維圖解變化趨勢(shì)如圖1所示。

圖1 固定任務(wù)模型加速比變化趨勢(shì)圖

該定律主要適用于負(fù)載固定的情況，例如在主從式模型中可以得到幾乎呈線性的加速比；而在孤島模型當(dāng)中，當(dāng)群體規(guī)模恒定，子群體的規(guī)模與數(shù)量不成正比的時(shí)候，其加速與主從式模型加速比相同。目前該定律在鄰域模型中運(yùn)用的較少[29]。

2.2.2 固定時(shí)間模型

文獻(xiàn)[30]于1988年提出了Gustafson定律。

假設(shè)原始任務(wù)為w,比例擴(kuò)增任務(wù)為w′，在同等的時(shí)間內(nèi)，p核并行和串行完成的任務(wù)相同，則有：

w′=(1-f)w+fmw

(6)

那么：

(7)

固定時(shí)間的三維模型圖解變化趨勢(shì)如圖2所示。

圖2 固定時(shí)間模型加速比變化趨勢(shì)圖

2.2.3 其他模型

文獻(xiàn)[31-32]結(jié)合實(shí)際問題給出了其他兩種評(píng)價(jià)指標(biāo)：(1) 改進(jìn)了Amadahl定律的加速比，先確定一個(gè)適應(yīng)度指標(biāo)，當(dāng)個(gè)體適應(yīng)度高于此指標(biāo)的時(shí)候，穿行計(jì)算的時(shí)間與并行計(jì)算的時(shí)間之比為加速比。(2) 計(jì)算并行運(yùn)算和串行運(yùn)算獲得個(gè)體的最高適應(yīng)度的差值大小。

另外還可以設(shè)計(jì)多個(gè)指標(biāo)，例如增加平均進(jìn)化代數(shù)、平均計(jì)算時(shí)間等因素，設(shè)計(jì)成具有不同集合特點(diǎn)的測(cè)試函數(shù)來比較不同模型之間的優(yōu)劣。

3 遺傳算法的研究和未來發(fā)展方向

本文重點(diǎn)考察了近五年國內(nèi)外工程技術(shù)人員以及相關(guān)領(lǐng)域研究者在遺傳算法方面的研究情況，數(shù)據(jù)來自2013年-2017年已發(fā)表在核心期刊上的“工業(yè)技術(shù)類”有關(guān)遺傳算法的研究。圖3是遺傳算法在包含函數(shù)優(yōu)化、生產(chǎn)調(diào)度、自動(dòng)控制、圖像處理、人工智能、遺傳編程、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)以及遺傳算法綜述以內(nèi)10個(gè)方向的應(yīng)用，圖4是遺傳算法在編碼策略、遺傳算子、物種多樣性、測(cè)試函數(shù)、收斂性、欺騙問題和綜述等7個(gè)方面文獻(xiàn)的統(tǒng)計(jì)結(jié)構(gòu)。

圖3 2013年-2017年遺傳算法應(yīng)用領(lǐng)域分布柱形圖

圖4 2013年-2017年遺傳算法研究領(lǐng)域分布柱形圖

根據(jù)圖3、圖4可以得到如下結(jié)論：

就應(yīng)用領(lǐng)域而言，遺傳算法的主要應(yīng)用方向集中在機(jī)器人學(xué)、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)方面。在生產(chǎn)調(diào)度中的應(yīng)用基本呈現(xiàn)出逐年增加的趨勢(shì)。

就研究方向而言，遺傳算法研究的熱門在遺傳算子、測(cè)試函數(shù)、收斂性和編碼策略上。相比而言，在物種多樣性和欺騙問題上研究成果不多，有待更深層次的研究。

整體而言，2016年以前遺傳算法領(lǐng)域的研究持平，說明遺傳算法仍然是機(jī)器學(xué)習(xí)領(lǐng)域和數(shù)據(jù)挖掘領(lǐng)域的研究關(guān)鍵點(diǎn)。加上真正有效的成果在總體的研究成果中占比較少，因此遺傳算法仍然是一個(gè)值得進(jìn)行深入研究的領(lǐng)域。

遺傳算法具有魯棒性強(qiáng)的特點(diǎn)，即可以用一個(gè)通用的框架來系統(tǒng)的解決優(yōu)化問題，目前已經(jīng)取得了較多的成果。在研究應(yīng)用方向?qū)用?，函?shù)優(yōu)化是評(píng)價(jià)遺傳算法的基本算例，多樣化的測(cè)試函數(shù)有助于體現(xiàn)算法的性能和效果。文獻(xiàn)[33]提出了一些多極值并具有最優(yōu)點(diǎn)的函數(shù)。對(duì)于如背包問題、布局優(yōu)化、旅行商問題、圖形劃分等NP-hard問題，解空間急劇上升，已經(jīng)不能用枚舉法或是暴力求解法解決問題。文獻(xiàn)[34-36]成功地將遺傳算法運(yùn)用到求解TSP問題上，文獻(xiàn)[37-39]分別將遺傳算法運(yùn)用到了排課問題、車間作業(yè)調(diào)度問題上。在自動(dòng)控制方面，文獻(xiàn)[40]用遺傳算法優(yōu)化了航空控制系統(tǒng)，文獻(xiàn)[41]利用遺傳算法對(duì)模糊控制器進(jìn)行了優(yōu)化。在機(jī)器人方面，遺傳算法也被廣泛的運(yùn)用，例如文獻(xiàn)[42]將遺傳算法運(yùn)用到機(jī)器人移動(dòng)的路徑規(guī)劃。圖像處理對(duì)降低圖像分割、掃描等操作的誤差有一定的要求，因此可以用遺傳算法進(jìn)行優(yōu)化計(jì)算。文獻(xiàn)[43-45]分別將遺傳算法運(yùn)用到漢字識(shí)別、圖像恢復(fù)和圖像邊緣特征提取上。在機(jī)器學(xué)習(xí)領(lǐng)域，遺傳算法可以通過學(xué)習(xí)模糊控制規(guī)則來改進(jìn)模糊系統(tǒng)的功能，文獻(xiàn)[46-47]已經(jīng)將遺傳算法用來調(diào)整CNN的連接權(quán)，以達(dá)到優(yōu)化CNN結(jié)構(gòu)的效果。另外數(shù)據(jù)挖掘問題也可以轉(zhuǎn)換成最優(yōu)解的搜索問題，數(shù)據(jù)庫就是搜索空間，遺傳算法隨機(jī)產(chǎn)生一組規(guī)則，當(dāng)不斷進(jìn)化的規(guī)則可以全面覆蓋數(shù)據(jù)庫的時(shí)候則進(jìn)化完成[46]。文獻(xiàn)[48]中已經(jīng)開發(fā)出相應(yīng)的數(shù)據(jù)挖掘工具，主要是基于遺傳算法的思想，對(duì)失事飛機(jī)的數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，結(jié)果證明這種方法十分有效。

在研究領(lǐng)域，編碼方式是遺傳算法的關(guān)鍵之一，遺傳算法之父Holland建議用二進(jìn)制。文獻(xiàn)[49]提出了多目的進(jìn)程調(diào)度二進(jìn)制編碼方式，強(qiáng)調(diào)識(shí)別關(guān)鍵產(chǎn)品、單位、任務(wù)，僅將少部分變量進(jìn)行二進(jìn)制編碼。文獻(xiàn)[50]提出混沌gary編碼方式，對(duì)于多參數(shù)的優(yōu)化問題來說實(shí)數(shù)編碼的效果更好。文獻(xiàn)[51]針對(duì)實(shí)數(shù)編碼僅適用于連續(xù)變量問題，提出了將混沌變異與映射到量子位的實(shí)數(shù)染色體交叉的編碼方式。文獻(xiàn)[52]為了減低早熟的概率，將復(fù)數(shù)的思想運(yùn)用到遺傳算法的編碼方式中。文獻(xiàn)[53]提出了基于動(dòng)態(tài)相似度的零件族編碼，優(yōu)化了遺傳算法的收斂時(shí)間和編碼長(zhǎng)度。

遺傳算法的關(guān)鍵主要在于交叉、選擇、變異算子的設(shè)計(jì)。文獻(xiàn)[54]提出了局部搜索能力納入選擇算子，提升了算法在不可能解的領(lǐng)域找到可行解的幾率。文獻(xiàn)[55]設(shè)計(jì)了一種局部競(jìng)爭(zhēng)選擇算子，為避免陷于局部最優(yōu)的問題，通過強(qiáng)調(diào)個(gè)體差異保證了種群的多樣性。文獻(xiàn)[56]將模擬退火算法運(yùn)用到選擇算子中，提升了算法的穩(wěn)定性。文獻(xiàn)[57]提出了拉普拉斯交叉算子，達(dá)到實(shí)現(xiàn)遺傳算法穩(wěn)定高效的搜索的效果。文獻(xiàn)[58]通過高斯分布概率調(diào)整了實(shí)數(shù)編碼的交叉算子。文獻(xiàn)[59]提出了單親遺傳算子，確保最終一定找到可行解。文獻(xiàn)[60]提出了功率變異算子。文獻(xiàn)[61]設(shè)計(jì)了定向編譯算子，提升了交互遺傳算法的性能。文獻(xiàn)[62]提出了貪婪子循環(huán)算子，提升了遺傳算法在TSP問題中的性能。

遺傳算法中涉及到位串、交叉概率、變異概率和群體規(guī)模等參數(shù)的設(shè)計(jì)。文獻(xiàn)[63]設(shè)計(jì)了一套模糊規(guī)則，在線動(dòng)態(tài)地改變交叉概率和變異概率。文獻(xiàn)[64]則用條件發(fā)生器來產(chǎn)生交叉和變異概率，具備一定的穩(wěn)定傾向性和隨機(jī)性。文獻(xiàn)[65]通過大量實(shí)驗(yàn)提出了針對(duì)調(diào)度問題的最佳遺傳算法參數(shù)。文獻(xiàn)[66]針對(duì)遺傳算法存在的早熟問題，提出了遺傳優(yōu)勢(shì)原則，讓交叉概率和編譯概率自適應(yīng)的改變。

收斂性是優(yōu)化問題的重要考核指標(biāo)，目前主要是運(yùn)用Markov鏈來證明遺傳算法的全局收斂性。文獻(xiàn)[67]闡明了遺傳算法收斂性的定義，并提出了新算法解決多峰值優(yōu)化過早收斂問題。文獻(xiàn)[68]運(yùn)用齊次Markov鏈證明了當(dāng)保留了上一代最優(yōu)個(gè)體的經(jīng)典遺傳算法可以收斂到全局最優(yōu)。文獻(xiàn)[69]闡明了遺傳算法出現(xiàn)早熟問題的原因，提出了新的遺傳算法收斂理論。

建筑塊理論認(rèn)為在遺傳過程中低階短距、適應(yīng)度高的模式將會(huì)以指數(shù)級(jí)別增長(zhǎng)，并轉(zhuǎn)變成高階長(zhǎng)距、適應(yīng)值高的模式。但受到“欺騙條件”的影響，最終可能會(huì)形成非最優(yōu)模式，導(dǎo)致問題最終無法收斂到全局最優(yōu)解，這就是欺騙問題。文獻(xiàn)[70]給出了模式欺騙和遺傳算法欺騙問題的定義，并討論了欺騙問題和收斂性和并行性的問題。文獻(xiàn)[67]提出了解決連續(xù)性欺騙問題的定向變異算子。文獻(xiàn)[71]計(jì)算了部分領(lǐng)域的遺傳算法解決完全欺騙問題的所需的平均值時(shí)間。

4 結(jié) 語

遺傳算法為解決復(fù)雜優(yōu)化問題提供了通用模板，是近些年進(jìn)化算法研究的熱點(diǎn)之一。同時(shí)統(tǒng)計(jì)數(shù)據(jù)還表明遺傳算法已經(jīng)漸漸走向了應(yīng)用，目前已經(jīng)較為廣泛地運(yùn)用在數(shù)據(jù)挖掘的技術(shù)中，改進(jìn)也是當(dāng)前遺傳算法的研究熱點(diǎn)?？v觀遺傳算法的研究方向可以發(fā)現(xiàn)，主要仍集中于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等方面，并呈現(xiàn)出逐年增加的趨勢(shì)，但是在機(jī)器學(xué)習(xí)領(lǐng)域?qū)嶋H應(yīng)用成果方面并不豐富。因此還存在進(jìn)一步的發(fā)展空間，在欺騙問題等理論問題研究方面尚有欠缺。整體來看遺傳算法還有相當(dāng)?shù)陌l(fā)展空間，未來發(fā)展主要集中在以下幾個(gè)方面：

1) 遺傳算法未來會(huì)在并行化方面進(jìn)一步發(fā)展。目前數(shù)據(jù)挖掘的運(yùn)用較多，并行化遺傳算法能夠顯著地提升運(yùn)算速度，有較高的應(yīng)用價(jià)值。

2) 遺傳算法目前在欺騙問題、參數(shù)設(shè)定等理論性研究方面尚顯不足。這限制了遺傳算法更深層次的發(fā)展，因此未來遺傳算法的研究重點(diǎn)可能會(huì)更多的出現(xiàn)在理論方面，建立起相應(yīng)的數(shù)學(xué)基礎(chǔ)。

3) 遺傳算法會(huì)與其他技術(shù)進(jìn)一步融合。因?yàn)檫z傳算法的局部搜索能力較弱，存在著早熟收斂的風(fēng)險(xiǎn)，需要和其他能夠快速局部收斂算法相結(jié)合才能實(shí)現(xiàn)更有效的收斂策略，這需要大量的實(shí)驗(yàn)和理論研究來實(shí)現(xiàn)。

4) 算法的早熟機(jī)理、參數(shù)設(shè)置的理論指導(dǎo)、收斂速度等理論研究可能會(huì)成為后進(jìn)的研究熱點(diǎn)。這些理論將指導(dǎo)算法發(fā)展的方向，目前還有很多不足，因此仍然有發(fā)展的空間。

5) 并行化理論研究方面未來會(huì)更加深入。遺傳算子之間相互獨(dú)立，個(gè)體與個(gè)體之間的適應(yīng)度選擇過程也都相互獨(dú)立，具備并行化的天然優(yōu)勢(shì)。設(shè)計(jì)對(duì)應(yīng)的并行策略和并行遺傳算子，建立相應(yīng)的數(shù)學(xué)基礎(chǔ)，尤其是在數(shù)據(jù)挖掘領(lǐng)域，顯得十分必要。