計(jì)算機(jī)應(yīng)用研究ApplicationResearchofComputers

Vol.27No.7

Jul.2010

遺傳算法理論及其應(yīng)用研究進(jìn)展

邊　霞,米　良

a

b

(四川大學(xué)a.計(jì)算機(jī)學(xué)院;b.制造科學(xué)與工程學(xué)院,成都610065)

摘　要:首先闡述遺傳算法的原理和求解問題的一般過程;然后討論了近年來從遺傳算子、控制參數(shù)等方面對(duì)

遺傳算法的改進(jìn),并對(duì)遺傳算法在計(jì)算機(jī)科學(xué)與人工智能、自動(dòng)控制以及組合優(yōu)化等領(lǐng)域的應(yīng)用進(jìn)行陳述;最后評(píng)述了遺傳算法未來的研究方向和主要研究內(nèi)容。關(guān)鍵詞:遺傳算法;遺傳算子;控制參數(shù);組合優(yōu)化中圖分類號(hào):TP301.6　　　文獻(xiàn)標(biāo)志碼:A　　　文章編號(hào):1001-3695(2010)07-2425-05doi:10.3969/j.issn.1001-3695.2010.07.006

Developmentongeneticalgorithmtheoryanditsapplications

ab

BIANXia,MILiang

(a.CollegeofComputerScience,b.CollegeofManufacturingScience＆Engineering,SichuanUniversity,Chengdu610065,China)

Abstract:Thispaperfirstsetouttheprincipleandprocessesofthegeneticalgorithms,andthenintroducedanumberof

schemesonimprovingthegeneticalgorithmssuchasthegeneticoperatorsandcontrolparameters,aswellastheapplicationofgeneticalgorithmsincomputerscienceandartificialintelligence,automaticcontrol,combinatorialoptimizationandsoon.Finally,presentedsomeremarksonthefurtherresearchanddirections.Keywords:geneticalgorithms(GA);geneticoperators;controlparameters;combinatorialoptimization　　遺傳算法[1](GA)是由美國Michigan大學(xué)的Holland教授于1975年首先提出的。它源于達(dá)爾文的進(jìn)化論、孟德爾的群體遺傳學(xué)說和魏茨曼的物種選擇學(xué)說;其基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過程搜索最優(yōu)解的算法。從公開發(fā)表的論文看,我國首先開始研究應(yīng)用遺傳算法的有趙改善[2]和華中理工大學(xué)的師漢民等人[3]。遺傳算法最早應(yīng)用于一維地震波形反演中

[4]

存的遺傳和進(jìn)化過程而形成的一種具有自適應(yīng)能力的、全局性的概率搜索算法。它是從代表問題可能潛在解集的一個(gè)種群開始,首先將表現(xiàn)型映射到基因型即編碼,從而將解空間映射到編碼空間,每個(gè)編碼對(duì)應(yīng)問題的一個(gè)解,稱為染色體或個(gè)體。初始種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來越好的近似解。在每一代,根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體,并借助自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異,產(chǎn)生出代表新的解集的種群。這個(gè)過程使種群像自然進(jìn)化一樣,后代種群比前代更加適應(yīng)于環(huán)境,末代種群中的最優(yōu)個(gè)體經(jīng)過解碼可以作為問題近似最優(yōu)解。利用遺傳算法求解問題的流程[6]如圖1所示。

,其特點(diǎn)是處理的對(duì)象是參數(shù)

的編碼集而不是問題參數(shù)本身,搜索過程既不受優(yōu)化函數(shù)聯(lián)系性的約束,也不要求優(yōu)化函數(shù)可導(dǎo),具有較好的全局搜索能力;算法的基本思想簡單,運(yùn)行方式和實(shí)現(xiàn)步驟規(guī)范,具有全局并行搜索、簡單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),但其局部搜索能力差,容易出現(xiàn)早熟現(xiàn)象

[5]

。

自1985年起,國際遺傳算法會(huì)議每兩年召開一次,在歐洲,從1990年開始每隔一年也舉辦一次類似的會(huì)議。1993年,國際上第一本以遺傳算法和進(jìn)化計(jì)算為核心內(nèi)容的學(xué)術(shù)期刊《EvolutionaryComputation》(進(jìn)化計(jì)算)在MIT創(chuàng)刊;1994年,在美國奧蘭多召開的IEEEWorldCongressonComputationIntelligence(IEEE全球計(jì)算智能大會(huì))上,進(jìn)化計(jì)算與模糊邏輯、神經(jīng)網(wǎng)絡(luò)一起統(tǒng)稱為計(jì)算智能;1997年,《IEEETransac-tionsonEvolutionaryComputation》創(chuàng)刊。這些刊物及時(shí)全面地報(bào)道了近年來遺傳算法的最新研究成果。目前,與遺傳算法有關(guān)的學(xué)術(shù)會(huì)議包括ICGA、PPSN、ICEC、ANN＆GA、EP、FOGA、COGANN、EC、GP、SEAL等。

a)建立數(shù)學(xué)模型。

b)編碼,即用設(shè)計(jì)好的算法將表現(xiàn)型映射到個(gè)體基因型。c)解碼,遺傳算子只對(duì)編碼后的染色體起作用,由個(gè)體表

　遺傳算法原理

遺傳算法[1]是模擬生物在自然環(huán)境中優(yōu)勝劣汰、適者生

收稿日期:2010-01-01;修回日期:2010-02-27

作者簡介:邊霞(1985-),女,碩士研究生,主要研究方向?yàn)榫W(wǎng)絡(luò)安全(593470285@qq.com);米良(1985-),男,博士研究生,主要研究方向?yàn)橛?jì)算機(jī)集成制造.·2426·

現(xiàn)型計(jì)算目標(biāo)函數(shù)值后就可以判斷染色體的優(yōu)劣。

計(jì)算機(jī)應(yīng)用研究第27卷

法的性能影響,他對(duì)五個(gè)函數(shù)進(jìn)行測試后,提出了一組參數(shù)選擇范圍:N50,P6,P001,這一組參數(shù)值后來被pop=c=0.m=0.作為標(biāo)準(zhǔn)參數(shù)廣泛使用。丁承明等人[17]提出了利用正交試驗(yàn)法去優(yōu)化選取控制參數(shù),這種方法利用正交試驗(yàn)的均衡分散性,使得通過較少的試驗(yàn)次數(shù)就能搜索大部分參數(shù)組合空間,而且還可以確定哪個(gè)參數(shù)對(duì)結(jié)果影響最顯著,然后有針對(duì)性地進(jìn)行精確的搜索,從而使得參數(shù)問題得到解決。李康順等人[18]提出的改進(jìn)遺傳算法能夠根據(jù)個(gè)體適應(yīng)度大小和群體的分散程度自動(dòng)調(diào)整遺傳控制參數(shù),從而能夠在保持群體多樣性的同時(shí)加快收斂速度,克服了傳統(tǒng)遺傳算法的收斂性差、易早熟等問題。

.　基于常識(shí)啟發(fā)的改進(jìn)

很多學(xué)者受常識(shí)的啟發(fā)對(duì)遺傳算法進(jìn)行了改進(jìn)。Reynolds等人[19～21]提出的文化算法是一種模擬人類文化進(jìn)化機(jī)制的算法,它模擬了種群空間和信賴空間兩級(jí)的進(jìn)化。在信賴空間級(jí)存儲(chǔ)和提煉由種群進(jìn)化中獲取的解決問題的知識(shí)及經(jīng)驗(yàn);而種群級(jí)在信賴空間級(jí)的指導(dǎo)下不斷進(jìn)化,最后收斂。王磊等人[22,23]研究的免疫遺傳算法根據(jù)生物的免疫原理,將免疫算法中抗體多樣性的維持機(jī)制、記憶機(jī)制、促進(jìn)抑制機(jī)制引入到遺傳算法中,在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上提出了加速實(shí)數(shù)編碼的免疫遺傳算法。該算法改進(jìn)了基本遺傳算法群體多樣性差、搜索區(qū)間大和免疫算法容易陷入局部最優(yōu)以及進(jìn)化后期搜索停滯不前的性能,使其快速成熟收斂的同時(shí)又提高了局部尋優(yōu)和全局尋優(yōu)的能力。朱燦等人[24]將物種的概念引入遺傳算法,提出了一種基于物種選擇的遺傳算法,根據(jù)種子到當(dāng)前最優(yōu)點(diǎn)的距離將種群分為當(dāng)前最優(yōu)物種和物種倉庫,對(duì)這兩個(gè)物種分別以不同的交叉概率和變異概率進(jìn)行遺傳運(yùn)算,以平衡種群的選擇壓力和種群多樣性,在提高算法效率和穩(wěn)定性方面取得了很好的效果。周蘭鳳等人[25]提出了一種基于知識(shí)的遺傳算法,該算法采用特定的遺傳算子,將領(lǐng)域知識(shí)納入初始種群及自適應(yīng)調(diào)整控制參數(shù),克服了傳統(tǒng)遺傳算法的早熟收斂問題,提高了遺傳算法的效率。Giráldez等人[26]對(duì)進(jìn)化算法中加入知識(shí)的各種技術(shù)進(jìn)行了分類和歸納,設(shè)計(jì)了一種基于知識(shí)的快速進(jìn)化算法并將其用于機(jī)器學(xué)習(xí)問題,實(shí)驗(yàn)結(jié)果表明,該算法不但能保證解的質(zhì)量而且大大縮短了計(jì)算時(shí)間。.　與其他智能算法結(jié)合

遺傳算法的全局搜索能力較強(qiáng),能較快地確定全局最優(yōu)點(diǎn),但局部搜索能力較弱,進(jìn)一步精確求解要耗費(fèi)很長時(shí)間。因此,將局部搜索能力強(qiáng)的算法與遺傳算法結(jié)合可以相互取長補(bǔ)短。Hageman等人[27]提出了遺傳算法與禁忌搜索相結(jié)合的策略;魏明等人[28]將遺傳算法與混沌優(yōu)化相結(jié)合,在遺傳進(jìn)化過程中,根據(jù)種群相對(duì)多樣性對(duì)每代個(gè)體引入混沌領(lǐng)域方法搜索有效基因,并有效地結(jié)合遺傳算法善于全局優(yōu)化和混沌局部搜索能力強(qiáng)等特點(diǎn),顯著提高了計(jì)算效率,具有較大的實(shí)用價(jià)值。任子武等人[29]將遺傳算法與粒子群優(yōu)化方法相結(jié)合,采用混沌序列產(chǎn)生初始種群、非線性排序選擇、多個(gè)交叉后代競爭擇優(yōu)和變異尺度自適應(yīng)變化等改進(jìn)遺傳操作,并通過精英個(gè)體保留、粒子群優(yōu)化及改進(jìn)遺傳算法(IGA)三種策略共同作用產(chǎn)生種群新個(gè)體,以克服常規(guī)算法中收斂速度慢、早熟及局部收斂等缺陷。此外,還有遺傳算法與模擬退火算法相結(jié)合[30]、遺傳算法與單純形法相結(jié)合[31]、遺傳算法與神經(jīng)網(wǎng)絡(luò)

d)確定適應(yīng)度轉(zhuǎn)換規(guī)則,染色體所對(duì)應(yīng)的解空間的值可能相差很大,需要一定的轉(zhuǎn)換使其適合定量評(píng)估個(gè)體的優(yōu)劣。

e)設(shè)計(jì)遺傳算子,即設(shè)計(jì)交叉、變異和選擇算子等。遺傳算子與待優(yōu)化問題、染色體的編碼方案有很大的關(guān)系。

f)確定運(yùn)行參數(shù),運(yùn)行參數(shù)包括交叉概率、變異概率和種群數(shù)目等。遺傳算法本身的參數(shù)還缺乏定量的標(biāo)準(zhǔn),目前采用的多是經(jīng)驗(yàn)數(shù)值,并且遺傳參數(shù)的選取與編碼和遺傳算子的設(shè)計(jì)有很大關(guān)系。

　遺傳算法的改進(jìn)

目前在遺傳算法的應(yīng)用中,最突出的問題是局部搜索能力差和容易出現(xiàn)早熟現(xiàn)象。近年來,眾多學(xué)者圍繞這兩個(gè)核心問題發(fā)表了大量有價(jià)值的學(xué)術(shù)論文法進(jìn)行了改進(jìn)。.　遺傳算子的改進(jìn)

在遺傳算子方面,Pan等人[7]提出自適應(yīng)變異算子,使得變異能夠根據(jù)解的質(zhì)量自適應(yīng)地調(diào)整搜索區(qū)域,較明顯地提高了搜索能力。Louis等人[8]根據(jù)個(gè)體之間的海明距離進(jìn)行非均勻的交叉和變異,在保持群體多樣性的同時(shí)還防止了早熟。夏虎等人[9]提出了一種考慮環(huán)境作用的協(xié)同免疫遺傳算法,在該算法中,設(shè)計(jì)了克隆環(huán)境演化算子和自適應(yīng)探索算子,并構(gòu)造了三個(gè)子種群協(xié)同進(jìn)化來發(fā)揮克隆環(huán)境演化算子的作用,從而提高了算法的全局搜索能力。蔡良偉等人[10]提出一種改進(jìn)的交叉操作,根據(jù)種群的多樣性和個(gè)體的相關(guān)性選擇不同的交叉策略以減少無效的交叉操作,從而提高了交叉操作的效率并改善了算法的收斂性能。江雷等人[11]提出的基于并行遺傳算法求解TSP,對(duì)遺傳算法的雜交算子進(jìn)行改進(jìn),探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。Whitley等人[12]提出了自適應(yīng)和有指導(dǎo)的變異,這種方法對(duì)改進(jìn)遺傳算法的性能起了一定的作用。.　多種群遺傳算法

一些學(xué)者提出了基于多種群的遺傳算法,將一個(gè)大的種群分成多個(gè)小的種群,每個(gè)小種群地進(jìn)行進(jìn)化,進(jìn)化一定代數(shù)后進(jìn)行種群間的通信。由于這種方式可以采用并行計(jì)算的模式,取得了較好的效果。賀新等人[13]介紹了一種基于新的變異算子多種群的新遺傳算法,該算法引入一種基于主群、附屬子群的結(jié)構(gòu),可避免傳統(tǒng)遺傳算法難以克服的早熟收斂問題。葉在福等人[14]引入多種群,對(duì)不同種群賦予不同的控制參數(shù),實(shí)現(xiàn)不同的搜索目的,通過移民算子聯(lián)系各種群,通過人工選擇算子保存各種群每個(gè)進(jìn)化代中的最優(yōu)個(gè)體,對(duì)遺傳算法的早熟現(xiàn)象有了很大的改進(jìn)。朱燦等人[15]提出了一種考慮性別特征的遺傳算法,該方法模擬生物系統(tǒng)多物種同時(shí)進(jìn)化,指出最優(yōu)種子的獲得不但需要一個(gè)好的個(gè)體(父體),而且需要一個(gè)好的進(jìn)化方向(母體),通過增加母體的方法加速最優(yōu)物種的進(jìn)化,從而提高了算法的效率。.　優(yōu)化控制參數(shù)

遺傳算法的控制參數(shù)主要有種群數(shù)目N、交叉概率Ppopc

和變異概率Pm,不同的參數(shù)組合對(duì)遺傳算法的運(yùn)行性能影響

[16]

很大。DeJong首先系統(tǒng)地研究了不同的參數(shù)組合對(duì)遺傳算[7～31]

,從各方面對(duì)遺傳算

第7期邊　霞,等:遺傳算法理論及其應(yīng)用研究進(jìn)展·2427　　　·

相結(jié)合[32]、遺傳算法與模糊集相結(jié)合[33]、遺傳算法與爬山法和梯度法等局部搜索算法相結(jié)合

[33]

和空間擴(kuò)展的平衡,因此可以有效地避免陷入局部極值點(diǎn),具備全局最優(yōu)搜索性,不會(huì)受到如Pareto曲面形狀、目標(biāo)個(gè)數(shù)等條件的,還可處理帶隨機(jī)的、不確定的離散搜索空間問題,這正是數(shù)學(xué)規(guī)劃法所難以克服的。Hajela等人[86]把多目標(biāo)問題通過效用函數(shù)轉(zhuǎn)換為單目標(biāo)問題,再用GA來求解。目前,怎樣利用GA的智能性來求解多目標(biāo)函數(shù)優(yōu)化問題,仍然是一個(gè)值得研究的新課題[87,88]。.　遺傳學(xué)習(xí)

將遺傳算法用于知識(shí)獲取,構(gòu)成以遺傳算法為核心的機(jī)器學(xué)習(xí)系統(tǒng)。比較經(jīng)典的是Holland設(shè)計(jì)的用于序列決策學(xué)習(xí)的桶鏈算法(bucketbrigade)反饋機(jī)制(該系統(tǒng)被稱為分類器系統(tǒng)),以及機(jī)器人規(guī)則、概念學(xué)習(xí)、模式識(shí)別等。

、遺傳算法與小生境技術(shù)

[36]

結(jié)合[34]、將量子計(jì)算與遺傳算法相結(jié)合形成量子遺傳算法[35]、在遺傳算法中加入免疫算子構(gòu)成免疫進(jìn)化算法

等。這些混

合策略不但提高了算法的性能,還擴(kuò)展了算法的應(yīng)用領(lǐng)域。

還有許多學(xué)者從其他方面對(duì)遺傳算法進(jìn)行了改進(jìn),如設(shè)計(jì)交互式遺傳算法、引入量子理論等。這些改進(jìn)都在某種程度上提高了遺傳算法的性能,然而這些改進(jìn)都具有一定的局限性。因此,提高遺傳算法的收斂速度、克服早熟現(xiàn)象將是一個(gè)永恒的目標(biāo)。

　遺傳算法的應(yīng)用進(jìn)展

由于遺傳算法具有全局并行搜索、簡單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),使得遺傳算法廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)[37,38]、自動(dòng)控制[39～42]、人工智能[43～50]、工程設(shè)計(jì)[51,52]、制造業(yè)[37,53]、生物工程[]和社會(huì)科學(xué)[53,55,56]等領(lǐng)域。.　在計(jì)算機(jī)科學(xué)與人工智能方面

遺傳算法在計(jì)算機(jī)科學(xué)與人工智能領(lǐng)域中的應(yīng)用包括數(shù)據(jù)庫查詢優(yōu)化[57]、數(shù)據(jù)挖掘與知識(shí)獲取[58,59]、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與參數(shù)優(yōu)化

[60～63]

.　社會(huì)與經(jīng)濟(jì)領(lǐng)域

早期的經(jīng)濟(jì)學(xué)研究采用遺傳算法來求解數(shù)學(xué)公式,取得了

[]

不錯(cuò)的效果,但離機(jī)器學(xué)習(xí)還差得很遠(yuǎn)。例如,Lettau在

1997年建立的一個(gè)簡單的主體模型中就使用了這種方法;Bau-[90]er對(duì)遺傳算法在經(jīng)濟(jì)與投資中的應(yīng)用進(jìn)行了全面分析。近

年來,商業(yè)、金融領(lǐng)域已經(jīng)成為遺傳算法應(yīng)用熱點(diǎn),目前已經(jīng)有許多基于遺傳算法的軟件包應(yīng)用于金融系統(tǒng)和股票投資分析。

、模式識(shí)別

[68]

[,65]

、專家系統(tǒng)

[66,67]

等。另外,遺

傳算法在軟件測試用例.　自動(dòng)控制領(lǐng)域

自動(dòng)生成方面也作出了很大的貢獻(xiàn)。

　結(jié)束語

遺傳算法的研究歸納起來可分為理論與技術(shù)研究和應(yīng)用

遺傳算法可用于求解系統(tǒng)參數(shù)辨識(shí)問題。Karr采用遺傳算法設(shè)計(jì)自適應(yīng)模糊邏輯控制器,取得了顯著的效果;Es-posito等人

[69]

[39]

研究兩個(gè)方面?？梢哉f,遺傳算法的應(yīng)用已經(jīng)滲透到了各個(gè)領(lǐng)域。但目前遺傳算法的算法分析和理論分析還沒有跟上,還有很多富有挑戰(zhàn)性的課題亟待完善與解決,主要有:

a)算法規(guī)模小。雖然遺傳算法模擬了生物的進(jìn)化過程,但目前遺傳算法的運(yùn)行規(guī)模還遠(yuǎn)小于生物的進(jìn)化規(guī)模。隨著計(jì)算機(jī)系統(tǒng)性能的不斷提高,人們將有可能實(shí)現(xiàn)模擬更接近于自然的進(jìn)化系統(tǒng),從而充分利用遺傳算法的并行性解決更復(fù)雜更有價(jià)值的問題。

b)遺傳算法的編碼問題。編碼是遺傳算法求解問題的前提,最基本的是二進(jìn)制編碼。其他的編碼方法有格雷碼、實(shí)數(shù)編碼、符號(hào)編碼、多參數(shù)編碼和DNA編碼等。不同的應(yīng)用應(yīng)該采用不同的編碼方式,因此基于不同的應(yīng)用,遺傳算法的編碼還有待改進(jìn)與完善。

c)遺傳算法控制參數(shù)的選擇問題。遺傳算法中控制參數(shù)的不同選取會(huì)對(duì)遺傳算法的性能產(chǎn)生較大的影響,將影響到整個(gè)算法的收斂性。這些參數(shù)包括交叉概率(p)、變異概率c(p和種群數(shù)目(Np)等。m)op

d)早熟收斂和局部搜索能力差問題。早熟收斂和局部搜索能力差是遺傳算法最突出的兩個(gè)問題。有很多學(xué)者針對(duì)這兩個(gè)問題發(fā)表了大量的學(xué)術(shù)文章,但從根本上解決這兩個(gè)問題還有待研究發(fā)現(xiàn)。

e)遺傳算子的無方向性問題?；具z傳算子包括選擇算子、交叉算子和變異算子。設(shè)計(jì)性能優(yōu)良的遺傳算子一直是遺傳算法的重要問題,如果能從遺傳算子的方向性著手改進(jìn)遺傳算法,有可能會(huì)得到意想不到的結(jié)果。

對(duì)上述問題的深入研究必將大大促進(jìn)遺傳算法理論和應(yīng)用的發(fā)展,遺傳算法也必將在智能計(jì)算領(lǐng)域中展現(xiàn)出更加光明的前景。

將基于GA的優(yōu)化技術(shù)應(yīng)用于RBF神經(jīng)網(wǎng)絡(luò)輸

[70]

出層權(quán)值的優(yōu)化;Vesin等人將GA用于解決網(wǎng)絡(luò)結(jié)構(gòu)和權(quán)

值的完全優(yōu)化問題。遺傳算法也可用于控制器參數(shù)優(yōu)化整定;Fonesca等人[71]將MOGA(多目標(biāo)遺傳算法)用于控制器的優(yōu)化設(shè)計(jì)以解決磁懸浮列車的控制器設(shè)計(jì)問題;顏文俊等人[72]則提出了一類新型的多目標(biāo)魯棒優(yōu)化控制器設(shè)計(jì)方法,通過有效算法求解滿足系統(tǒng)魯棒穩(wěn)定性和魯棒性能的優(yōu)化解。此外,GA在故障診斷[73]和機(jī)器人行走路徑規(guī)劃[74]中的應(yīng)用也取得了成功。

.　在組合最優(yōu)化問題方面

組合優(yōu)化(combinatorialoptimization)研究那些含有有限個(gè)可行解的、日常生活中大量存在的問題。這其中一個(gè)重要并且普遍的應(yīng)用領(lǐng)域就是考慮如何有效利用稀缺資源來提高生產(chǎn)力箱衡

[75]

。GA在組合優(yōu)化問題中的應(yīng)用包括路徑覆蓋、背包

[79]

[76]

、裝

[84]

[77,78][81]

、確定最小生成樹

[80]

、機(jī)器調(diào)度排序與平、旅行推銷員分配

、車輛路徑

[82]

、網(wǎng)絡(luò)設(shè)計(jì)與路徑

[83]

等。

.　在多目標(biāo)函數(shù)優(yōu)化問題方面

多目標(biāo)問題最早由意大利經(jīng)濟(jì)學(xué)家Pareto在16年從政治經(jīng)濟(jì)學(xué)的角度提出的。多目標(biāo)群體決策是當(dāng)前管理科學(xué)、決策理論、系統(tǒng)工程、運(yùn)籌學(xué)、福利經(jīng)濟(jì)學(xué)等學(xué)科研究中十分重要的內(nèi)容[85]。GA很適合求解多目標(biāo)優(yōu)化問題,因?yàn)镚A可以并行地處理各個(gè)目標(biāo),避免了目標(biāo)間的優(yōu)先排序處理。GA通過保持一個(gè)潛在解的種群進(jìn)行多方向搜索,這種種群對(duì)種群的搜索可以跳出局部最優(yōu)解,從而突破了數(shù)學(xué)規(guī)劃法的點(diǎn)對(duì)點(diǎn)的搜索方法。GA在整個(gè)解空間同時(shí)開始尋優(yōu)搜索,注重區(qū)域搜索·2428·

參考文獻(xiàn):

[1]

計(jì)算機(jī)應(yīng)用研究第27卷

munity[J].IEEETransonSystems,Man,andCybernetics,PartA:SystemsandHumans,2000,30(5):552-561.[24]朱燦,梁昔明,周書仁.基于物種選擇的遺傳算法[J].小型微型

計(jì)算機(jī)系統(tǒng),2009,30(3):534-536.

[25]周蘭鳳,洪炳熔.用基于知識(shí)的遺傳算法實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)

劃[J].電子學(xué)報(bào),2006,34(5):911-914.

[26]GIR LDEZR,AGUILAR-RUIZJS,RIQUELMEJC.Knowledge-basedfastevaluationforevolutionarylearning[J].IEEETransonSystems,Man,andCybernetics,PartC:ApplicationsandRe-views,2005,35(I):1-7.

[27]HAGEMANJA,WEHRENSR,SPRANGHAvan,etal.Hybridge-neticalgorithm-tabusearchapproachforoptimisingmultilayeropticalcoatings[J].AnalyticaChimicaActa,2003,490(1-2):211-222.[28]魏明,蔡延光.一種基于混沌領(lǐng)域搜索的自適應(yīng)遺傳算法[J].計(jì)

算機(jī)應(yīng)用研究,2009,26(2):4-465.

[29]任子武,傘冶.實(shí)數(shù)遺傳算法的改進(jìn)及性能研究[J].電子學(xué)報(bào),

2007,35(2):269-274.

[30]YOGESWARANM,PONNAMBALAMSG,TIWARIMK.Aneffi-cienthybridevolutionaryheuristicusinggeneticalgorithmandsimula-tedannealingalgorithmtosolvemachineloadingprobleminFMS[J].InternationalJournalofProductionResearch,2009,47(19):21-48.

[31]OHSK,PEDRYCZW,PARKHS.Geneticallyoptimizedfuzzypoly-nomialneuralnetworks[J].IEEETransonFuzzySystems,2006,14(1):125-144.

[32]KUMARP,CHANDNAVK,THOMASMS.Fuzzy-geneticalgorithm

forpre-processingdataattheRTU[J].IEEETransonPowerSys-tems,2004,19(2):718-723.

[33]MURATAT,MIYATAS.Genelinkageidentificationinpermutation

problemsforlocalsearchandgeneticlocalsearch[C]//ProcofIEEEInternationalConferenceonSystems,ManandCybernetics.2005:1920-1924.

[34]ZHANGJun,HUANGDe-shuang,LOKTM,etal.Anoveladaptive

sequentialnichetechniqueformultimodalfunctionoptimization[J].Neurocomputing,2006,69(16-18):2396-2401.

[35]WANGLing,TANGFang,WUHao.Hybridgeneticalgorithmbased

onquantumcomputingfornumericaloptimizationandparameteresti-mation[J].AppliedMathematicsandComputation,2005,171(2):1141-1156.

[36]LUOXiao-ping,WEIWei.Discussionontheconvergencerateofim-munegeneticalgorithm[C]//Procofthe5thWorldCongressonIntel-ligentControlandAutomation.2004:2275-2278.

[37]CHANDRASEKHARAMR.Geneticalgorithmforembeddingacom-pletegraphinahypercubewithaVLSIapplication[J].Micropro-cessingandMicroprogramming,1994,40(8):537-552.[38]BOMMWLPvan.Geneticalgorithmforoptimallogicaldatabasede-sign[J].InternationalSoftwareTechnology,1994,36(2):725-732.

[39]KARRCL.Designofanadaptivefuzzylogiccontrollerusinggenetic

algorithm[C]//Procofthe4thInternationalConferenceonGeneticAlgorithms.SanFrancisco:MorganKaufmann,1991:450-457.[40]景興建,土越超,談大龍.理性遺傳算法及其在多機(jī)器人運(yùn)動(dòng)防調(diào)

中的應(yīng)用[J].自動(dòng)化學(xué)報(bào),2002,28(6):955-961.

[41]FREDG,KELLYJP,LAGUNAM.Geneticalgorithmsandtabu

search:hybridsforoptimization[J].ComputerandOperationRe-search,1995,122(1):111-134.

HOLLANDJH.Adaptationinnaturalandartificialsystems[M].Cambridge:MITPress,1975.

[2]趙改善.求解非線性最優(yōu)化問題的遺傳算法[J].地球物理學(xué)進(jìn)

展,1992,7(1):90-97.

[3]師漢民,陳吉紅.基因遺傳算法的原理及在機(jī)械工程中的應(yīng)用

[J].中國機(jī)械工程,1992,3(3):18-21.[4]

STOFFAPL,SENMK.Nonlinearmultiparameteroptimizationusinggeneticalgorithms:inversionofplane-waveseismogram[J].Geo-physics,1991,56(11):1794-1810.

[5]周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,

2001.

[6]姜昌華.遺傳算法在物流系統(tǒng)優(yōu)化中的應(yīng)用研究[D].上海:華東

師范大學(xué),2007.[7]

PANZheng-jun,KANGLi-shan,NIESi-xiang.Evolvingboththeto-pologyandweightsofneuralnetwork[J].ParallelAlgorithmsandApplications,1996,9(3＆4):299-307.[8]

LOUISSJ,RAWLINSGJE.Syntacticanalysisofconvergenceinge-neticalgorithms[M]//FoundationsofGeneticAlgorithm.SanMateo:MorganKaufmann,1993:141-151.

[9]夏虎,莊健,王立忠,等.一種考慮環(huán)境作用的協(xié)同免疫遺傳算法

[J].西安交通大學(xué)學(xué)報(bào),2009,43(11):80-84.

[10]蔡良偉,李霞.遺傳算法交叉操作的改進(jìn)[J].系統(tǒng)工程與電子技

術(shù),2006,28(6):925-928.

[11]江雷.基于并行遺傳算法的彈性TSP研究[J].微電子學(xué)與計(jì)算

機(jī),2005,22(8):130-134.

[12]WHITLEYD,STRAKWEATHERT,BOGARTC.Geneticalgorithms

andneuralnetworks:optimizingconnectionandconnectivity[J].ParallelComputing,1990,14(3):347-361.

[13]賀新,劉智明,周激流.基于主附種群結(jié)構(gòu)的遺傳算法[J].四川

大學(xué)學(xué)報(bào):自然科學(xué)版,2003,40(2):278-282.

[14]葉在福,單淵達(dá).基于多種群遺傳算法的輸電系統(tǒng)擴(kuò)展規(guī)劃[J].

電力系統(tǒng)自動(dòng)化,2000,24(5):24-27.

[15]朱燦,梁昔明,顏東煌.一種考慮性別特征的遺傳算法[J].武漢

理工大學(xué)學(xué)報(bào),2008,30(12):110-113,128.

[16]DeJONGKA.Ananalysisofthebehaviorofaclassofgeneticadap-tivesystems[D].Michigan:UniversityofMichigan,1975.

[17]丁承民,張傳生,劉貴忠.利用正交試驗(yàn)法優(yōu)化配置遺傳算法控制

參數(shù)[R].西安:西安交通大學(xué)電子與信息工程學(xué)院信息工程研究所,1996.

[18]李康順,李茂民,張文生.一種基于改進(jìn)遺傳算法的圖像分割方法

[J].計(jì)算機(jī)應(yīng)用研究,2009,26(11):43-4367.

[19]REYNOLDSRG,SVERDLIKW.Problemsolvingusingculturalalgo-rithms[C]//ProcofInternationalConferenceonEvolutionaryCompu-tation.1994:5-650.

[20]REYNOLDSRG,ZHUS.Knowledge-basedfunctionoptimization

usingfuzzyculturalalgorithmswithevolutionaryprogramming[J].IEEETransonSystems,Man,andCybernetics,PartB,2001,31(1):1-18.

[21]REYNOLDSRG,PENGB.Culturalalgorithms:modelingofhowcul-tureslearntosolveproblems[C]//Procofthe16thIEEEInternatio-nalConferenceonToolswithArtificialIntelligence.WashingtonDC:IEEEComputerSociety,2004:166-172.

[22]王磊,潘進(jìn),焦李成.免疫算法[J].電子學(xué)報(bào),2000,28(7):552-561.

[23]JIAOLi-cheng,WANGLei.ANovelgeneticalgorithmbasedonim-第7期邊　霞,等:遺傳算法理論及其應(yīng)用研究進(jìn)展·2429　　　·

[42]MICHALEWICZZ,JANIKOWC,KJRAWCZYKJ.Amodifiedgenetic

algorithmforoptimalcontrolproblems[J].ComputersandMathe-maticalApplications,1992,23(12):83-94.

[43]DAVISJJ.Trainingproductunitneuralnetworkwithgeneticalgo-rithms[J].IEEEExpert,1993,8(5):26-33.

[44]DeJONGKA.Learningwithgeneticalgorithms:anoverview[J].Ma-chineLearning,1988,3(2-3):121-138.

[45]DORIGOM,SCHNEPHU.Genetic-basedmachinelearningandbe-havior-basedrobotics:anewsynthesis[J].IEEETransonSys-tems,ManandCybernetics,1993,23(1):141-1.

[46]BOOKERLB,GOLDBERGDE,HOLLANDJH.Classifiersystems

andgeneticalgorithms[J].ArtificialIntelligence,19,40(1):235-282.

[47]LIEPINSGE,WANGLA.ClassifiersystemlearningofBooleancon-cepts[C]//Procofthe4thInternationalConferenceonGeneticAlgo-rithms.SanFrancisco:MorganKaufmann,1991:318-323.

[48]MCAULAYAD,OHJC.Improvinglearningofgeneticrule-based

classifiersystems[J].IEEETransonSystem,Man,andCyber-netics,1994,24(1):152-159.

[49]MATWINS,SZAPIROT,HAIGHK.Geneticalgorithmsapproachtoa

negotiationsupportsystem[J].IEEETransonSystems,Man,andCybernetics,1991,21(1):102-114.

[50]NIKOLOPOULOSC,FELLRATHP.Ahybridexpertsystemforin-vestmentadvising[J].ExpertSystems,1994,11(4):245-250.[51]JENKINSWM.Structuraloptimizationwiththegeneticalgorithm[J].

StructuralEngineer,1991,69(24):408-422.

[52]GOLDBERGDE.Computer-aidedgaspipelineoperationusing

geneticalgorithmandrulelearning[D].Michigan:UniversityofMichigan,1983.

[53]DAVISL.Handbookofgeneticalgorithms[M].[S.l.]:VanNos-trandReinholdCompany,1991.

[]FORRESTS.Geneticalgorithm:principlesofnaturalselectionappli-cationtocomputation[J].Science,1993,261(5123):872-878.[55]BAUERRJ.Geneticalgorithmsandinvestmentstrategies[R].New

York:Wiley,1994.

[56]MICHALEWICZZ.Geneticalgorithms+datastructures=evolution

programs[M].3rded.NewYork:Springer-Verlag,1996.

[57]MAHFOUDSW.FiniteMarkovchainmodelsofanalternativeselec-tionstrategyforthegeneticalgorithm[J].ComplexSystems,1993,7(2):155-170.

[58]McCALLUMRA,SPACKMANKA.Usinggeneticalgorithmtolearn

disjunctiverulesfromexamples[C]//ProcofInternationalConferenceonMachineLearning.SanMateo:MorganKaufmann,1990.

[59]LAVINEBK.Patternrecognitionanalysisviageneticalgorithmsandmul-tivariatestatisticalmethods[M].BocaRaton,Fla:CRCPress,2000.[60]WHITLEYLD.Foundationsofgeneticalgorithms2[M].SanMateo:

MorganKaufmann,1993.

[61]WHITLEYLD,VOSEMD.Foundationsofgeneticalgorithms3

[M].SanFrancisco:MorganKaufmann,1995.

[62]HAASR,HUNTKJ.Geneticalgorithms-basedoptimizationofa

fuzzy-neuralvehiclecontroller[C]//ProcofInternationalConferenceonFuzzySystems.1994.

[63]SCHAFFERJD,WHITLEYLD,ESHELMANLJ.Combinationsof

geneticalgorithmsandneuralnetworks:asurveyofthestateoftheart[C]//ProcofInternationalWorkshoponCombinationsofGeneticAl-gorithmsandNeuralNetworks.1992:1-37.

[]BALAJ,DeJONGKA,HAUNGJ,etal.Hybridlearningusing

geneticalgorithmsanddecisiontreesforpatternclassification[C]//Procofthe14thInternationalJointConferenceonArtificialIntelli-gence.1995:19-25.

[65]PALSK.Geneticalgorithmsforpatternrecognition[M].BocaRaton,

Fla:CRCPress,1996.

[66]KADABAN,NYGARDKE,JUELLPJ.Integrationofadaptivema-chinelearningandknowledge-basedsystemsforroutingandschedu-lingapplications[J].ExpertSystemswithApplications,1991,2(1):15-27.

[67]金菊良,丁晶.遺傳算法及其在水科學(xué)中的應(yīng)用[M].成都:四川

大學(xué)出版社,2000.

[68]BEMDTDJ,WATKINSA.Investigatingtheperformanceofgenetic

algorithm-basedsoftwaretestcasegeneration[C]//Procofthe7thIEEEInternationalSymposiumonHighAssuranceSystemsEnginee-ring.2004:261-262.

[69]ESPOSITOA,MARINAROM,ORICCHIOD,etal.Approximationof

continuousanddiscontinuousmappingsbyagrowingneuralRBF-basedalgorithm[J].NeuralNetworks,2000,13(6):651-665.[70]VESINJM,GRATERR.Modelselectionusingasimplexreproduc-tiongeneticalgorithm[J].SignalProcessing,1999,78(3):321-327.

[71]FONESCACM,FLEMMINGPJ.Multiobjectiveoptimisationand

multipleconstrainthandlingwithevolutionaryalgorithms-partⅠ:aunifiedformulationandpartⅡ:applicationexample[J].IEEETransonSystems,ManandCybernetics,PartA:SystemsandHu-mans,1998,28(1):26-37,38-47.

[72]顏文俊,張森林.新型多目標(biāo)優(yōu)化控制策略及其應(yīng)用研究[J].浙

江大學(xué)學(xué)報(bào):工學(xué)版,2004,38(6):691-696.

[73]ZHONGBing-lin,YANTing-hu,HUANGRen,etal.Ageneticalgo-rithmfordiagnosisproblemsolving[C]//ProcofIEEEInternationalConferenceonSystems,ManandCybernetics.Piscataway:IEEEServiceCenter,1992.

[74]DAVIDORY.Geneticalgorithmandrobotics:aheuristicstrategyfor

optimization[M].[S.l.]:WorldScientificPublishingCo.,1991.[75]LINJin-cherng,YEHPu-lin.Automatictestdatagenerationforpath

testingusingGAs[J].InformationSciences,2001,131(1-4):47-.

[76]BERNDTDJ,WATKINSA.Investigatingtheperformanceofgenetic

algorithm-basedsoftwaretestcasegeneration[C]//Procofthe8thIEEEInternationalSymposiumonHighAssuranceSystemsEnginee-ring.2004:261-262.

[77]許光濘,肖志勇,愈金壽.應(yīng)用自適應(yīng)遺傳算法解決集裝箱裝載問

題[J].控制與決策,2007,22(11):1280-1283.

[78]KARABULUTK,INCEOGLUMM.Ahybridgeneticalgorithmfor

packingin3Dwithdeepestbottomleftwithfillmethod[C]//Procofthe3rdInternationalConferenceonAdvancesinInformationSystems.2004:441-450.

[79]SINGHA,BAGHELAS.Anewgroupinggeneticalgorithmforthe

quadraticmultipleknapsackproblem[C]//Procofthe7thEuropeanConferenceonEvolutionaryComputationinCombinatorialOptimiza-tion.Berlin:Springer,2007:210-218.

[80]ZHOUG,GENM.Approachtodegree-constrainedminimumspanning

treeproblemusinggeneticalgorithm[J].EngineeringDesignandAutomation,1997,3(2):157-165.

(下轉(zhuǎn)第2434頁)

·2434·計(jì)算機(jī)應(yīng)用研究第27卷

[13]SARKARN,CHAUDHURIBB.Anefficientapproachtoestimate

fractaldimensionoftextureimages[J].PatternRecognition,1992,25(9):1035-1041.

[14]PELEGJ,NATOR,HARLEYR,etal.Multipleresolutiontextures

analysisandclassification[J].IEEETransonPatternAnalysisandMachineIntelligence,1985,6(4):518-523.

[15]何四華,楊紹清,石愛國.紋理高階分形特征在海面艦船目標(biāo)檢測

中的應(yīng)用[J].光學(xué)與光電技術(shù),2008,6(4):79-82.

[16]杜干,張守宏.高階分形特征在雷達(dá)信號(hào)檢測中的應(yīng)用[J].電子

學(xué)報(bào),2000,28(3):90-92.

[17]TOLLECR,McJUNKINTR,ROHRBAUGHDT,etal.Lacunarity

definitionforramifieddatasetsbasedonopticalcover[J].PhysicaD:NonlinearPhenomena,2003,179(3-4):129-152.

[18]張坤華,楊煊.基于分形特征的復(fù)雜背景下擴(kuò)展目標(biāo)檢測[J].強(qiáng)

激光與粒子束,2009,21(2):217-220.

[19]章毓晉.圖像分割[M].北京:科學(xué)出版社,2001.

[20]PENGZhen-ming,HUANGBin.Detectingtheman-madetargetbased

onenhancedfractalfeatureusingPRIA[C]//Procofthe1stInterna-tionalSymposiumonSystemsandControlinAerospaceandAstronau-tics.2006:208-211.

[21]CHENGHui,BOUMANCA.MultiscaleBayesiansegmentationusing

atrainablecontextmodel[J].IEEETransonImageProcessing,2001,10(4):511-525.

[22]ANDREYP,TAROXP.UnsupervisedsegmentationofMarkovmodel-basedtextureimageinselectionistrelaxation[J].IEEETransonPatternAnalysisandMachineIntelligence,1998,20(3):252-262.

[23]KUMARS,HEBERTM.Man-madestructuredetectioninnatural

imagesusingacausalmultiscalerandomfield[C]//ProcofIEEEIn-ternationalConferenceonComputerVisionandPatternRecognition.2003:119-126.

[24]BOUMANCA,SHAPIROM.Amultiscalerandomfieldmodelfor

Bayesianimagesegmentation[J].IEEETransonImageProces-sing,1994,3(2):162-177.

[25]LISZ.Markovrandomfieldmodelinginimageanalysis[M].Lon-don:Springer-Verlag,2001.

[26]WONCS,DERINH.Unsupervisedsegmentationofnoisyandtex-turedimagesusingMarkovrandomfields[J].GraphicalModelsandImageProcessing,1992,(4):308-328.

[27]KUMARS,HEBERTM.Discriminativefieldsformodelingspatial

dependenciesinnaturalimages[C]//AdvancesinNeuralInformation(上接第2429頁)

[81]黃德才,郭海東.基于JIT的非等同并行多機(jī)調(diào)度問題的混合遺

傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2004,10(3):298-302.[82]GENM,LIYin-zhen.Spanningtree-basedgeneticalgorithmforbicri-teriafixedchargetransportationproblem[C]//ProcofIEEECongressonEvolutionaryComputation.WashingtonDC:IEEEComputerSocie-ty,1999:2265-2271.

[83]MUNETOMOM,TALAIY,SATOY.Anadaptivenetworkroutingal-gorithmemployingpathgeneticoperators[C]//Procofthe7thCon-gressonGeneticAlgorithms.1997:3-9.

[84]樂艷麗,魯漢榕,李加慶.基于改進(jìn)遺傳算法求解旅行商問題

[J].空軍雷達(dá)學(xué)院學(xué)報(bào),2007,21(4):298-300.

[85]周文坤,武振業(yè),鞠廷英.多目標(biāo)群體決策的一種綜合集成方法

[J].西南交通大學(xué)學(xué)報(bào),2001,36(1):100-103.ProcessingSystems.Cambridge:MITPress,2003:87-97.

[28]RUBINSTEINYD,HASTIET.Discriminativevsinformativelearning

[C]//Procofthe3rdInternationalConferenceonKnowledgeDisco-veryandDataMining.1997:49-53.

[29]MALLADIR,SETHIANJA,VEMURIBC.Shapemodelingwith

frontpropagation:alevelsetapproach[J].IEEETransonPatternAnalysisandMachineIntelligence,1995,7(2):158-175.[30]李俊,楊新,施鵬飛.基于Mumford-Shah模型的快速水平集圖像

分割方法[J].計(jì)算機(jī)學(xué)報(bào),2002,25(11):1175-1183.

[31]王怡,周明全,耿國華.基于簡化Mumford-Shah模型的水平集圖

像分割算法[J].計(jì)算機(jī)應(yīng)用,2006,26(8):1848-1850.

[32]CAOGuo,YANGXin,MAOZhi-hong.Atwo-stagelevelsetevolution

schemeforman-madeobjectsdetectioninaerialimages[C]//ProcofIEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.2005:474-476.

[33]OSHERS,SETHIANJA.Frontspropagatingwithcurvaturedepen-dentspeed:algorithmsbasedonHamihon-Jacobiformulation[J].JournalofComputerPhysics,1988,79(1):12-49.

[34]GUBAS,RASTOGIR,SHIMK.ROCK:arobustclusteringalgorithm

forcategoricalattributes[J].InformationSystems,2000,25(5):345-366.

[35]WUNing-ning,ZHANGJing.Factoranalysisbasedanomalydetection

andclustering[J].DecisionSupportSystems,2006,42(1):375-3.

[36]PIRESA,SANTOSPC.Usingclusteringandrobustestimatorsto

detectoutliersinmultivariatedata[C]//ProcofInternationalConferenceonRobustStatistics.2005.

[37]CARLOTTOMJ.Acluster-basedapproachfordetectingman-made

objectsandchangesinimagery[J].IEEETransonGeoscienceandRemoteSensing,2005,43(2):374-387.

[38]STEIND,BEAVENS,STOCKERA,etal.Anomalydetectionfrom

hyperspectralimagery[J].IEEESignalProcess,2002,19(1):58-69.

[39]KANUNGOT,MOUNTDM,NETHANS,etal.Alocalsearchap-proximationalgorithmforK-meansclustering[J].ComputationalGeometry,2004,28(2-3):-112.

[40]DEMPSTERAP,LAIRDNM,RDINDB.Maximumlikelihoodfrom

incompletedataviatheEMalgorithm[J].JournaloftheRoyalSta-tisticalSociety,1977,39(1):1-38.

[41]TOUJT,GONZALEZRC.Patternrecognitionprinciples[M].[S.

l.]:Addison-Wesley,1974.

[86]HAJELAP,LINCY.Geneticsearchstrategiesinmulticriterionopti-maldesign[J].StructuralandMultidisciplinaryOptimization,1992,5(4):99-107.

[87]DEVK.Optimizationforengineeringdesign:algorithmsandexamples

[M].[S.l.]:Prentice-Hall,1995.

[88]STEUERRE.Multipleoptimizationcriteria:theory,computation,and

application[M].NewYork:Wiley,1986.

[]LETTAUM.Explainingthefactswithadaptiveagents:thecaseofmu-tualfundflows[J].JournalofEconomicDynamicsandControl,1997,21(7):1117-1147.

[90]CHIPPERFIELDA,FLEMINGPJ,POHLHEIMH,etal.Genetical-gorithmtoolboxforusewithMATLAB[R].Sheffield:DepartmentofAutomaticControlandSystemEngineering,UniversityofSheffield,1994.