計算機(jī)智能導(dǎo)論P(yáng)PT完整全套教學(xué)課件

第1章緒論——從人工智能到計算智能第2章進(jìn)化計算第3章模糊邏輯第4章人工神經(jīng)網(wǎng)絡(luò)目錄第1章緒論

——從人工智能到計算智能1.1人工智能的發(fā)展1.2人工智能預(yù)言、現(xiàn)狀和未來1.3人工智能的新生:計算智能1.4智能的三個層次1.5計算智能領(lǐng)域研究成果

1.1人工智能的發(fā)展

1.1.1

人工智能的萌芽

1.亞里士多德的形而上學(xué)和邏輯學(xué)

亞里士多德的主要成就包括主謂命題及關(guān)于此類命題的邏輯推理方法,特別是三段論。

例1.1.1

(i)凡孔子的后代是人,(ii)凡人皆會死,因此凡孔子的后代會死。若寫成普遍的形式,則是:(i)凡S是M;(ii)凡M是P;因此凡S是P。這里(i)及(ii)是兩個前提,若這兩個前提為真,則以上推出的結(jié)論(凡S是P)亦必然是真,因此這個三段論是正確的。

2.歸納法

Bacon(培根,1561—1626年)在《新工具》中提出歸納法,提出“知識就是力量”。他十分重視科學(xué)實驗,認(rèn)為只有經(jīng)過實驗才能獲得真正的知識。

3.圖靈與人工智能

艾倫·麥席森·圖靈(Turing,1912年—1954年,見圖1-1,

英國數(shù)學(xué)家),以“紙上下棋機(jī)”率先探討了下棋與機(jī)器智能的聯(lián)系,是舉世公認(rèn)的“人工智能之父”。

圖1-1

圖靈

4.人工智能的物質(zhì)基礎(chǔ)———計算機(jī)

二戰(zhàn)期間,美國軍方為了解決計算大量軍用數(shù)據(jù)的難題,成立了由賓夕法尼亞大學(xué)莫奇利和?？颂仡I(lǐng)導(dǎo)的研究小組,開始研制世界上第一臺計算機(jī)。經(jīng)過三年緊張的工作,第一臺電子計算機(jī)終于在1946年2月14日問世了,它由17468個電子管、6萬個電阻器、1萬個電容器和6千個開關(guān)組成,重達(dá)30噸,占地160平方米,耗電174千瓦,耗資45萬美元。這臺計算

機(jī)每秒只能運(yùn)行5千次加法運(yùn)算,稱為“埃尼阿克”即ENIAC(電子數(shù)字積分計算機(jī),見圖1-2),為人工智能研究奠定了物質(zhì)基礎(chǔ)。

圖1-2ENIAC計算機(jī)

5.數(shù)學(xué)奇才、計算機(jī)之父———馮·諾依曼

馮·諾依曼計算機(jī)結(jié)構(gòu)如圖1-3所示。圖1-3馮·諾依曼計算機(jī)結(jié)構(gòu)

6.MP模型

1943年,McCulloch和Pitts建立了神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)模型,如圖1-4所示,通過模擬人腦實現(xiàn)智能,開創(chuàng)了人工神經(jīng)網(wǎng)絡(luò)的研究。圖1-4神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)模型與人體神經(jīng)元

7.Wiener控制論

Wiener曾研究計算機(jī)如何能像大腦一樣工作,并發(fā)現(xiàn)了二者的相似性。

8.英國數(shù)學(xué)家、邏輯學(xué)家Boole

Boole實現(xiàn)了萊布尼茨的思維符號化和數(shù)學(xué)化的思想,提出了一種嶄新的代數(shù)系統(tǒng)———布爾代數(shù)。

1.1.2人工智能的誕生

1.導(dǎo)因

現(xiàn)實世界中相當(dāng)多問題的求解都是復(fù)雜的,常無算法可循,即使有計算方法,也是NP(Non-deterministicPolynomial,即多項式復(fù)雜程度的非確定性)問題。

2.達(dá)特茅斯會議

1956年夏天,美國達(dá)特茅斯大學(xué)召開了一次影響深遠(yuǎn)的歷史性會議。

3.現(xiàn)代電腦的智能與人類智能

一方面,電腦能計算出10億位的π值,能快速處理全國人口普查的海量數(shù)據(jù),能精確地控制宇宙飛船登上月球的每一個步驟,任何聰明絕頂?shù)娜嗽谒媲岸枷嘈我娊I;另一方面,電腦的智力水平連普通3歲孩童都不如。

4.生物智能

對于低級動物來說,它的生存、繁衍是一種智能。

5.人類智能

具體地講,包括以下幾方面能力:

(1)感知與認(rèn)識事物、客觀世界與自我的能力;

(2)通過學(xué)習(xí)取得經(jīng)驗、積累知識的能力;

(3)理解知識、運(yùn)用知識及運(yùn)用經(jīng)驗分析問題和解決問題的能力;

(4)聯(lián)想、推理、判斷、決策的能力;

(5)運(yùn)用語言進(jìn)行抽象、概括的能力;

(6)發(fā)現(xiàn)、發(fā)明、創(chuàng)造、創(chuàng)新的能力;

(7)實時地、迅速地、合理地應(yīng)付復(fù)雜環(huán)境的能力;

(8)預(yù)測、洞察事物發(fā)展變化的能力。

6.智能定義

下面幾種定義是目前使用較多的定義:

(1)從生物學(xué)角度定義為“中樞神經(jīng)系統(tǒng)的功能”。

(2)從心理學(xué)角度定義為“進(jìn)行抽象思維的能力”。

(3)有人同義反復(fù)地把它定義為“獲得能力的能力”。

(4)智能是個體或群體在不確定的動態(tài)環(huán)境中作出適當(dāng)反應(yīng)的能力,這種反應(yīng)必須有助于它(它們)實現(xiàn)其最終的行為目標(biāo)。

(5)智能是個體有目的的行為、合理的思維,以及有效地適應(yīng)環(huán)境的綜合能力。

7.人工智能

人工智能是相對人的自然智能而言的,即用人工的方法和技術(shù),研制智能機(jī)器或智能系統(tǒng)來模仿、延伸和擴(kuò)展人的智能,實現(xiàn)智能行為和“機(jī)器思維”,解決需要人類專家才能

處理的問題。

8.人工智能的特點與分支

1)特點

人工智能具備推理、學(xué)習(xí)和聯(lián)想的特點。

2)分支

人工智能從一開始就形成了兩種重要的研究范式,即符號主義和聯(lián)接主義。

(1)符號主義:它認(rèn)為人工智能源于數(shù)理邏輯。

(2)聯(lián)接主義:它認(rèn)為人工智能源于仿生學(xué),特別是人腦模型的研究。

例1.1.2感知器學(xué)習(xí)模型。

感知器學(xué)習(xí)模型如圖1-5所示。圖1-5感知器學(xué)習(xí)模型

1986年,魯梅爾哈特(Rumelhart)等人提出了多層網(wǎng)絡(luò)中的反向傳播(BP)算法。此后,聯(lián)接主義勢頭大振,從模型到算法,從理論分析到工程實現(xiàn),為神經(jīng)網(wǎng)絡(luò)計算機(jī)走向市場打下了基礎(chǔ)?，F(xiàn)在,對人工神經(jīng)網(wǎng)絡(luò)(ArtificialNearalNetwork,ANN)的研究熱情依然不減。

9.人工智能的目標(biāo)

人工智能科學(xué)想要解決的問題,是讓電腦也具有人類的聽、說、讀、寫、思考、學(xué)習(xí)、適應(yīng)環(huán)境變化、解決各種實際問題等能力。

1.1.3人工智能的發(fā)展

1.機(jī)器證明

2.專家系統(tǒng)

專家系統(tǒng)的一般結(jié)構(gòu)如圖1-6所示

3.第五代計算機(jī)

4.模式識別

5.人腦與電腦

圖1-6專家系統(tǒng)的一般結(jié)構(gòu)

1.2人工智能預(yù)言、現(xiàn)狀和未來

1.人工智能的現(xiàn)狀人工智能先驅(qū)這些充滿樂觀的預(yù)言,除了40年后電腦戰(zhàn)勝了卡斯帕洛夫之外,其余的直到現(xiàn)在依然遠(yuǎn)沒有被實現(xiàn),甚至引發(fā)了長時期無休無止的爭論和哲學(xué)意義上的思辨。人工智能雖然做出了許多令人鼓舞的工作,但在前進(jìn)的道路上,還面臨著相當(dāng)難以克服的障礙。

2.人工智能的未來

現(xiàn)有的計算機(jī)技術(shù)已充分實現(xiàn)了人類左腦的邏輯推理功能,人工智能的下一步是模仿人類右腦的模糊處理能力,以及模擬整個大腦并行處理大量信息的功能,將人類從那些繁瑣的重復(fù)性的腦力勞動中解放出來,去從事那些具有高創(chuàng)造性的腦力勞動,如科學(xué)發(fā)明和藝術(shù)創(chuàng)作等,生產(chǎn)效率也將得到大幅度提高。

1.3人工智能的新生:計算智能

1.3人工智能的新生:計算智能

1.3.1-人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)的特點如下:

(1)信息的分布表示記憶在大量神經(jīng)元中。

(2)神經(jīng)網(wǎng)絡(luò)運(yùn)算的全局并行和局部操作。

(3)處理的非線性。

(4)較強(qiáng)的學(xué)習(xí)能力。

1.3.2模糊邏輯

經(jīng)典集合與模糊集合如圖1-7所示。

圖1-7經(jīng)典集合與模糊集合

1.3.3進(jìn)化計算

進(jìn)化計算是一種模擬自然界生物進(jìn)化過程與機(jī)制,并進(jìn)行問題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。

這些方法的共同點如下:

(1)它們是依靠生產(chǎn)者提供的數(shù)字、數(shù)據(jù)材料進(jìn)行加工處理,而不是依賴于知識,具有較強(qiáng)的魯棒性。

(2)這些研究方法各自可以在某些特定方面起到特殊的作用,但是也存在一些固有的局限,將這些智能方法有機(jī)地融合起來進(jìn)行研究,就能為建立一種統(tǒng)一的智能系統(tǒng)和優(yōu)化方法提供基礎(chǔ)。

1.3.4計算智能

計算智能系統(tǒng)是在神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)、進(jìn)化計算三個分支發(fā)展相對成熟的基礎(chǔ)上,通過相互之間的有機(jī)融合而形成的新的科學(xué)方法,也是智能理論和技術(shù)發(fā)展的嶄新階段。

計算智能的特點如下:

(1)具有計算的適應(yīng)性;

(2)具有計算誤差的容忍度;

(3)接近人處理問題的速度;

(4)具有近似人的誤差率。

1.4智能的三個層次

1.智能的三個層次(1)生物智能(BiologicalIntelligence,BI),由腦的物理化學(xué)過程反映出來,是腦智能的基礎(chǔ)。(2)人工智能(ArtificialIntelligence,AI),是非生物的、人造的,常用符號來表示。AI的來源是人類知識的精華。(3)計算智能(ComputationalIntelligence,CI),是由數(shù)學(xué)方法和計算機(jī)實現(xiàn)的,其來源于數(shù)值計算的傳感器。

2.層次間關(guān)系

(1)從復(fù)雜性來看:BI>AI>CI。

(2)從隸屬關(guān)系來看:BI包含AI包含CI。

(3)AI是CI到BI的過渡,因為AI中除計算算法之外,還包括符號表示及數(shù)值信息處理,模糊集合和模糊邏輯是AI到CI的過渡。

1.5計算智能領(lǐng)域研究成果

1.5.1-進(jìn)化計算研究成果1.進(jìn)化多目標(biāo)優(yōu)化的研究進(jìn)展應(yīng)用進(jìn)化算法求解多目標(biāo)優(yōu)化問題,已成為進(jìn)化計算的研究熱點之一,并形成一個新的研究方向———進(jìn)化多目標(biāo)優(yōu)化。

2.免疫克隆算法的研究進(jìn)展

人工免疫系統(tǒng)的研究起源于對生物免疫的研究,免疫學(xué)是一門相對年輕的學(xué)科,人類對自然免疫的認(rèn)識可以追溯到300年以前。經(jīng)過300多年的發(fā)展,免疫學(xué)已經(jīng)從微生物學(xué)發(fā)展成一門獨立的學(xué)科,并派生出若干分支,例如細(xì)胞免疫學(xué)、分子免疫學(xué)、神經(jīng)與內(nèi)分泌免疫學(xué)、生殖免疫學(xué)和行為免疫學(xué)等。

人工免疫系統(tǒng)的研究主要集中在以下幾個方面:

(1)對人工免疫系統(tǒng)模型的研究。

(2)關(guān)于免疫機(jī)理的研究。

(3)多樣性遺傳機(jī)理的研究。

(4)克隆選擇機(jī)理。

3.群智能方法的研究進(jìn)展

20世紀(jì)50年代出現(xiàn)了仿生學(xué),因此從生物進(jìn)化機(jī)理出發(fā)尋找解決復(fù)雜優(yōu)化問題的方法受到研究者越來越多的關(guān)注,比如出現(xiàn)了遺傳算法、進(jìn)化策略、進(jìn)化規(guī)劃等進(jìn)化算法,而

生物群體行為對現(xiàn)實生活中復(fù)雜問題的求解也具有重要的指導(dǎo)作用。

1.5.2模糊理論研究成果

1.模糊聚類

1)模糊聚類算法的發(fā)展

模糊理論的出現(xiàn)將傳統(tǒng)的聚類分析推廣成了模糊聚類分析。

2)模糊聚類算法在圖像分割領(lǐng)域的應(yīng)用

圖像分割是圖像理解中十分關(guān)鍵的一步,因此近些年來許多學(xué)者提出了很多高效的圖像分割方法。

2.模糊控制

1974年,英國的E.H.Mamdani成功地將模糊控制應(yīng)用于鍋爐和蒸汽機(jī)控制以來,模糊控制得以廣泛發(fā)展并在現(xiàn)實中得以成功應(yīng)用。

1.5.3人工神經(jīng)網(wǎng)絡(luò)研究成果

1.神經(jīng)網(wǎng)絡(luò)的發(fā)展

隨著計算機(jī)的問世,開發(fā)出一款人工智能(使計算機(jī)能夠具有人的意識)的計算機(jī)程序成為計算機(jī)領(lǐng)域研究者的一個前進(jìn)方向,自從1950年圖靈測試提出的半個多世紀(jì)以來,人工智能的進(jìn)展遠(yuǎn)遠(yuǎn)沒能完全達(dá)到圖靈測試的標(biāo)準(zhǔn),但這些年的發(fā)展特別是神經(jīng)網(wǎng)絡(luò)的出現(xiàn)為強(qiáng)人工智能的出現(xiàn)奠定了強(qiáng)有力的基礎(chǔ)。

2.多層感知機(jī)的缺點

多隱層感知機(jī)(或稱深度前饋神經(jīng)網(wǎng)絡(luò))的缺點有:

一是有類標(biāo)數(shù)據(jù)少,訓(xùn)練不充分,易出現(xiàn)過擬合現(xiàn)象。

二是構(gòu)建的優(yōu)化目標(biāo)函數(shù)為高度非凸的,參數(shù)初始化影響網(wǎng)絡(luò)模型的性能(因為可行域內(nèi)出現(xiàn)大量鞍點和局部最小值點),極易陷入局部最優(yōu)。

三是利用反向傳播算法,當(dāng)隱層較多時,由誤差反饋其靠近輸出端的權(quán)值調(diào)整較大,但靠近輸入端的權(quán)值調(diào)整較小,出現(xiàn)所謂的梯度彌散現(xiàn)象。

針對這三個缺點,提出的改進(jìn)策略有:

一是增加數(shù)據(jù)量,改進(jìn)統(tǒng)計方法,如裁剪、取塊等;或減少層與層之間的權(quán)值連接,間接增加數(shù)據(jù)量;再或者利用生成式對抗網(wǎng)絡(luò)學(xué)習(xí)少量數(shù)據(jù)的內(nèi)在分布特性,然后根據(jù)采樣來擴(kuò)充數(shù)據(jù)等。

二是逐層學(xué)習(xí)加精調(diào)策略,利用自編碼或傳統(tǒng)的機(jī)器學(xué)習(xí)方法和稀疏表示/編碼方法在無監(jiān)督學(xué)習(xí)方式下實現(xiàn)逐層的權(quán)值預(yù)訓(xùn)練(逐層權(quán)值初始化),通過保持層與層之間的拓

撲結(jié)構(gòu)特性來避免過早地陷入局部最優(yōu)。

三是為了弱化梯度彌散現(xiàn)象,在初始化的參數(shù)上引入隨機(jī)梯度下降來實現(xiàn)精調(diào),以克服輸入端的權(quán)值未充分訓(xùn)練的問題,這也正是深度神經(jīng)網(wǎng)絡(luò)優(yōu)化的方式。

3.深度神經(jīng)網(wǎng)絡(luò)簡介

在深度學(xué)習(xí)、計算與認(rèn)知的范式中,關(guān)于“深度”的定義,有時間上(如深度遞歸神經(jīng)網(wǎng)絡(luò))和空間結(jié)構(gòu)上(如深度卷積神經(jīng)網(wǎng)絡(luò))的區(qū)別,其對應(yīng)的輸入分別為序列向量和圖像(或

視頻),并且計算與認(rèn)知的形式也有所不同,時間上的深度遞歸神經(jīng)網(wǎng)絡(luò)旨在挖掘序列數(shù)據(jù)中的上下文邏輯特性,空間結(jié)構(gòu)上的深度神經(jīng)網(wǎng)絡(luò)主要挖掘數(shù)據(jù)中的高層語義特性(層級特征提取)。

4.深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方式

深度學(xué)習(xí)的學(xué)習(xí)方式包括監(jiān)督、半監(jiān)督和無監(jiān)督,其中半監(jiān)督方式下的逐層學(xué)習(xí)(大量無類標(biāo)數(shù)據(jù))加精調(diào)(少量有類標(biāo)數(shù)據(jù))的模式最為成熟,無監(jiān)督方式下的深度學(xué)習(xí)最為新穎,如基于生成式對抗網(wǎng)絡(luò)的深度生成神經(jīng)網(wǎng)絡(luò)(該網(wǎng)絡(luò)的性能取決于數(shù)據(jù)量,以及迭代更新判別網(wǎng)絡(luò)和生成網(wǎng)絡(luò)的策略),或特征學(xué)習(xí)加機(jī)器學(xué)習(xí)中的無監(jiān)督方法(如K-means聚類算法)形成的層級聚類特性的深度網(wǎng)絡(luò)等。

5.深度神經(jīng)網(wǎng)絡(luò)主要研究的問題

一是在很多領(lǐng)域,很難獲取大量的監(jiān)督數(shù)據(jù),或者數(shù)據(jù)的標(biāo)注成本過高;

二是訓(xùn)練數(shù)據(jù)規(guī)模再大,也有難以覆蓋的情況。例如聊天機(jī)器人,我們不可能窮盡所有可能的答案,而且很多答案也是隨時間變化的,因此僅僅依靠大規(guī)模的訓(xùn)練語料,并不能解決這些問題;

三是通用深度學(xué)習(xí)模型直接應(yīng)用到具體問題,其表現(xiàn)(效果、性能、占用資源等)可能不盡如人意,這就要求根據(jù)特定的問題和數(shù)據(jù)來定制和優(yōu)化深度學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu),這是當(dāng)前

研究最多、最熱的地方;

四是訓(xùn)練的問題,包括網(wǎng)絡(luò)層數(shù)增加帶來的梯度衰減,及如何更有效地進(jìn)行大規(guī)模并行訓(xùn)練等。

為了解決這些問題,當(dāng)前的研究前沿主要包括以下幾個方向:

一是引入外部知識,例如知識圖譜等;

二是深度學(xué)習(xí)與傳統(tǒng)方法的結(jié)合,包括人工規(guī)則與深度神經(jīng)網(wǎng)絡(luò)的結(jié)合、貝葉斯與深度神經(jīng)網(wǎng)絡(luò)的結(jié)合、遷移學(xué)習(xí)與深度神經(jīng)網(wǎng)絡(luò)的結(jié)合、強(qiáng)化學(xué)習(xí)與深度神經(jīng)網(wǎng)絡(luò)的結(jié)合和

圖模型與深度神經(jīng)網(wǎng)絡(luò)的結(jié)合等;

三是無監(jiān)督的深度生成模型;

四是新的網(wǎng)絡(luò)結(jié)構(gòu)、新的訓(xùn)練方法等。第2章進(jìn)化計算2.1緒論2.2遺傳算法2.3遺傳編碼和種群初始化2.4交叉和變異2.5選擇和適應(yīng)度函數(shù)2.6遺傳算法用于求解數(shù)值優(yōu)化問題第2章進(jìn)化計算2.7遺傳算法的理論基礎(chǔ)2.8進(jìn)化算法的收斂性分析2.9基于進(jìn)化計算的約束優(yōu)化問題2.10基于進(jìn)化計算的組合優(yōu)化問題2.11基于進(jìn)化計算的多目標(biāo)優(yōu)化問題2.12-群智能算法2.13免疫克隆算法

2.1緒論2.1.1引例

例2.1.1對于一個求函數(shù)最大值的優(yōu)化問題,一般可描述為下述數(shù)學(xué)規(guī)劃模型:當(dāng)n=1時,為單目標(biāo)優(yōu)化;當(dāng)n>1時,為多目標(biāo)優(yōu)化;當(dāng)m=k=0時,為無約束優(yōu)化,否則為約束優(yōu)化;若x取值離散則為離散優(yōu)化,若x∈D?R則為連續(xù)優(yōu)化。

例2.1.2

無約束多峰單目標(biāo)優(yōu)化函數(shù)如圖2-1所示。圖2-1無約束多峰單目標(biāo)優(yōu)化函數(shù)

例2.1.3約束單目標(biāo)優(yōu)化問題。

例2.1.4約束多目標(biāo)優(yōu)化問題。

Pareto最優(yōu)區(qū)域和最優(yōu)解如圖2-2所示。圖2-2-Pareto最優(yōu)區(qū)域和Pareto最優(yōu)解

傳統(tǒng)最優(yōu)化方法在處理以下問題時面臨新挑戰(zhàn):

離散性問題———主要指組合優(yōu)化;不確定性問題———隨機(jī)性數(shù)學(xué)模型;半結(jié)構(gòu)或非結(jié)構(gòu)化的問題;大規(guī)模問題和超高維問題,以及動態(tài)優(yōu)化問題等。

2.1.2-從進(jìn)化論到進(jìn)化計算

1.現(xiàn)代進(jìn)化論

現(xiàn)代進(jìn)化論的理論來源至少包括三方面的內(nèi)容:拉馬克(Lamarck)進(jìn)化學(xué)說、達(dá)爾文(Darwin)進(jìn)化論和孟德爾遺傳學(xué),其主干是達(dá)爾文進(jìn)化論。

1)Lamarck進(jìn)化學(xué)說

拉馬克認(rèn)為:

(1)一切物種都是由其他物種演變和進(jìn)化而來的,而生物的演變和進(jìn)化是一個緩慢而連續(xù)的過程。

(2)環(huán)境的變化能夠引起生物的變異,環(huán)境的變化迫使生物發(fā)生適應(yīng)性的進(jìn)化。生物對環(huán)境的適應(yīng)是發(fā)生變異的結(jié)果:環(huán)境變了,生物會發(fā)生相應(yīng)的變異,以適應(yīng)新的環(huán)境。對于植物和無神經(jīng)系統(tǒng)的低等動物來說,環(huán)境引起變異的過程是:環(huán)境→機(jī)能→形態(tài)構(gòu)造。對于有神經(jīng)系統(tǒng)的動物來說,環(huán)境引起變異的過程是:環(huán)境→需要→習(xí)性→機(jī)能→形態(tài)構(gòu)造。

(3)有神經(jīng)系統(tǒng)的動物發(fā)生變異的原因,除了環(huán)境變化和雜交外,更重要的是用進(jìn)廢退和獲得性狀遺傳。

(4)生物進(jìn)化的方向是從簡單到復(fù)雜,從低等到高等。

(5)最原始的生物起源于自然發(fā)生。

拉馬克建立了比較完整的生物體系,但他的關(guān)于獲得性

遺傳的法則始終得不到現(xiàn)代科學(xué)的支持。拉馬克曾以長頸鹿

的進(jìn)化為例,說明他的“用進(jìn)廢退”觀點(圖2-3)。圖2-3環(huán)境變化迫使生物適應(yīng)性進(jìn)化示意圖

2)Darwin進(jìn)化論

1831年,達(dá)爾文開始了為期5年的環(huán)球科學(xué)旅行。沿途,

他仔細(xì)考察了各地的生物類型、地理分布、古生物化石和現(xiàn)存生物的相互關(guān)系、地質(zhì)層次序。返英后,他又研究了人工育種的經(jīng)驗,總結(jié)了生物學(xué)和人類學(xué)的最新成果,并于1859年完成了《物種起源》一書。與此同時,Wallace發(fā)表了題為《論變種無限地離開其原始模式的傾向》的論文。

他們提出的觀點被統(tǒng)稱為達(dá)爾文進(jìn)化學(xué)說,其基本要點是:

(1)生物不是靜止的,而是進(jìn)化的。物種不斷變異,舊物種消失,新物種產(chǎn)生。

(2)生物進(jìn)化是逐漸和連續(xù)的,不會發(fā)生突變。

(3)生物之間都有一定的親緣關(guān)系,它們具有共同的祖先。

(4)自然選擇是變異最重要的途徑。

3)孟德爾遺傳學(xué)

幾乎在達(dá)爾文提出進(jìn)化論的同時,孟德爾正在默默地進(jìn)行著豌豆雜交實驗,他把實驗結(jié)果總結(jié)為以下兩條定律,德國植物學(xué)家Correns將這些定律概括為孟德爾定律:

(1)分離定律:純質(zhì)親本雜交時,子一代所有個體都表現(xiàn)出顯性性狀,子二代表現(xiàn)出分離現(xiàn)象,顯性性狀與隱性性狀之比為3∶1。

(2)自由組合定律(又稱獨立分配定律):兩對性狀分離后又隨機(jī)組合,在子二代中出現(xiàn)自由組合現(xiàn)象,出現(xiàn)的全顯性、一隱一顯、一顯一隱、全隱性之比為9∶3∶3∶1。

在生物細(xì)胞中,控制并決定生物遺傳特性的物質(zhì)是脫氧核糖核酸,簡稱DNA,染色體是其載體。DNA是由四種堿基按一定規(guī)則排列組成的長鏈。四種堿基不同的排列決定了生

物不同的表現(xiàn)性狀。細(xì)胞在分裂時,DNA通過復(fù)制轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中,新的細(xì)胞就繼承了上一代細(xì)胞的基因。有性生殖生物在繁殖下一代時,兩個同元染色體之間通過交叉而

重組,即在兩個染色體的某一相同位置處DNA被切斷,其前后兩串分別交叉形成兩個新的染色體,如圖2-4所示。細(xì)胞進(jìn)行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯,從而使

DNA發(fā)生某種變異,產(chǎn)生新的染色體,這些新的染色體將決定新個體(后代)的新性狀。

圖2-4兩個同元染色體交叉重組示意圖

2.生物進(jìn)化與優(yōu)化

現(xiàn)代進(jìn)化論認(rèn)為,只用種群上和物種內(nèi)的少量統(tǒng)計過程就可以充分解釋大多數(shù)生命歷史,這些過程就是繁殖、變異、競爭和選擇,它們構(gòu)成了生物進(jìn)化的四個要素。

(1)繁殖。生命的持續(xù)是通過繁殖作用實現(xiàn)的。

(2)變異。變異是指同種生物世代之間或同代不同個體之間的差異。

(3)競爭。生存競爭是指生物與環(huán)境所發(fā)生的關(guān)系,這種關(guān)系包括種內(nèi)斗爭、種間斗爭、生物與自然環(huán)境斗爭三個方面。

(4)選擇。自然選擇學(xué)說是達(dá)爾文進(jìn)化論的核心。自然選擇是指,適合于環(huán)境的生物被保留下來,而不適合的則被淘汰。

總而言之,繁殖是所有生命的共同特征;變異保證了任何生命系統(tǒng)能在正熵世界中連續(xù)繁殖自己;對于限制在有限區(qū)域中不斷膨脹的種群來說,競爭和選擇是不可避免的。于是進(jìn)化就是這四個相互作用的隨機(jī)過程一代一代地作用在種群上的結(jié)果。

個體和物種一般被認(rèn)為是對應(yīng)于它們的遺傳編碼所表現(xiàn)出來的行為特性。個體的遺傳編碼通常被稱為基因型(genotype),而表現(xiàn)出來的行為被稱為表現(xiàn)型(phenotype)?；蛐蜑檫M(jìn)化過程中所獲信息的存儲提供了一種機(jī)制。由于多效性(pleiotropy)和多基因性(polygeny)這兩種機(jī)制的存在和廣泛應(yīng)用,一般來說遺傳上的變化所導(dǎo)致的結(jié)果是不可預(yù)料的。所謂多效性,是指一個單一基因可以同時對多個表現(xiàn)型特征產(chǎn)生作用,而多基因性,是指單一的表現(xiàn)型特征可能由多個基因共同的相互作用所確定。

根據(jù)上述觀點,生物進(jìn)化顯然是一種求解優(yōu)化問題的過程。給定了初始條件和環(huán)境約束,通過選擇可以得到與最優(yōu)解盡可能接近的表現(xiàn)型,但是環(huán)境又持續(xù)不斷地變化著,物種跟在環(huán)境變化的后面,不斷地向一個新的最優(yōu)解進(jìn)化,這就是進(jìn)化計算這類模擬自然進(jìn)化的計算方法的思想源泉。以生物進(jìn)化過程為基礎(chǔ),計算科學(xué)學(xué)者提出了各種模擬形式的計算方法。

舉例隨機(jī)算法———爬山法。

(0)初始化:隨機(jī)產(chǎn)生一個當(dāng)前解c,評價其適應(yīng)度f(c)。

(1)對c進(jìn)行復(fù)制,并對復(fù)制后的解進(jìn)行變異,得到m,評價其適應(yīng)度f(m)。

(2)如果f(m)不比f(c)差,則用m取代c,否則丟棄m。

(3)如果滿足停止條件,停止;否則,轉(zhuǎn)(1)。

爬山法求解問題示意圖如圖2-5所示。

圖2-5爬山法求解問題示意圖

盡管爬山法可用于問題的求解,但也存在一定的缺點,從圖2-6中可看到:爬山法圖2-6爬山法陷入局部最優(yōu)示意圖

3.進(jìn)化計算

進(jìn)化計算(EvolutionaryComputation,EC)是一類通過模擬生物進(jìn)化過程與機(jī)制來求解問題的自適應(yīng)人工智能技術(shù)。它的核心思想源于這樣的基本認(rèn)識:從簡單到復(fù)雜、從低級到高級的生物進(jìn)化過程本身是一個自然的、并行發(fā)生的、穩(wěn)健的優(yōu)化過程,這一過程的目標(biāo)是對環(huán)境的適應(yīng)性,生物種群通過“優(yōu)勝劣汰”及遺傳變異來達(dá)到進(jìn)化的目的。

1)進(jìn)化算法

進(jìn)化算法(EvolutionaryAlgorithms,EAs)是基于進(jìn)化計算思想發(fā)展起來的一類隨機(jī)搜索技術(shù)。

采用進(jìn)化算法求解優(yōu)化問題的一般步驟如下:

(1)隨機(jī)給定一組初始解;

(2)評價當(dāng)前這組解的性能;

(3)若當(dāng)前解滿足要求或進(jìn)化過程達(dá)到一定代數(shù),計算結(jié)束;

(4)根據(jù)(2)的評價結(jié)果,從當(dāng)前解中選擇一定數(shù)量的解作為基因操作對象;

(5)對所選擇的解進(jìn)行基因操作(如交叉、變異等),得到一組新解,轉(zhuǎn)到(2)。

與傳統(tǒng)搜索算法相比,進(jìn)化算法具有以下不同點:

(1)進(jìn)化算法不直接作用在解空間上,而是利用解的某種編碼表示;

(2)進(jìn)化算法從一個群體即多個點而不是一個點開始搜索,這是它能以較大概率找到整體最優(yōu)解的主要原因之一;

(3)進(jìn)化算法只使用解的適應(yīng)性信息(即目標(biāo)函數(shù)值),并在增加收益和減少開銷之間進(jìn)行權(quán)衡,而傳統(tǒng)搜索算法一般要使用導(dǎo)數(shù)等其他輔助信息;

(4)進(jìn)化算法使用隨機(jī)轉(zhuǎn)移規(guī)則而不是確定性的轉(zhuǎn)移規(guī)則。

2)進(jìn)化算法的特點

(1)智能性。

(2)本質(zhì)并行性。

3)進(jìn)化計算的主要分支

目前研究的進(jìn)化算法主要有四種:遺傳算法(GeneticAlgorithms,GAs)、進(jìn)化規(guī)劃(EvolutionaryProgramming,EP)、進(jìn)化策略(EvolutionStrategy,ES)和遺傳編程(GeneticProgramming,GP)。前三種算法是彼此獨立發(fā)展起來的,最后一種是在遺傳算法的基礎(chǔ)上發(fā)展起來的一個分支,雖然這幾個分支在算法的實現(xiàn)方面具有一些細(xì)微差別,但它們具有一個共同的特點,即都是借助生物進(jìn)化的思想和原理來解決實際問題。

2.2-遺傳算法

2.2.1遺傳算法簡介遺傳算法的創(chuàng)始人是美國密西根大學(xué)的Holland教授。Holland教授在20世紀(jì)50年代末期開始研究自然界的自適應(yīng)現(xiàn)象,并希望能夠?qū)⒆匀唤绲倪M(jìn)化方法用于實現(xiàn)求解復(fù)雜問題的自動程序設(shè)計。Holland教授認(rèn)為:可以用一組二進(jìn)制串來模擬一組計算機(jī)程序,并且定義了一個衡量每個“程序”正確性的度量———適應(yīng)值。他模擬自然選擇機(jī)制對這組“程序”進(jìn)行“進(jìn)化”,直到最終得到一個正確的“程序”。

2.2.2-遺傳的特點

標(biāo)準(zhǔn)遺傳算法的特點如下:

(1)遺傳算法必須通過適當(dāng)?shù)姆椒▽栴}的可行解進(jìn)行編碼。

(2)遺傳算法基于個體的適應(yīng)度來進(jìn)行概率選擇操作。

(3)在遺傳算法中,個體的重組使用交叉算子。

(4)在遺傳算法中,變異操作使用隨機(jī)變異技術(shù)。

(5)遺傳算法擅長對離散空間的搜索,它較多地應(yīng)用于組合優(yōu)化問題。

2.2.3示例

遺傳算法首先實現(xiàn)從性狀到基因的映射,即編碼工作,然后從代表問題可能潛在解集的一個種群開始進(jìn)化求解。

選擇:通過適應(yīng)度的計算,淘汰不合理的個體。類似于自然界的物競天擇。

復(fù)制:編碼的拷貝,類似于細(xì)胞分裂中染色體的復(fù)制。

交叉:編碼的交叉重組,類似于染色體的交叉重組。

變異:編碼按小概率擾動產(chǎn)生的變化,類似于基因的突變。

圖2-7展示了遺傳算法的尋優(yōu)過程。

圖2-7遺傳算法尋優(yōu)過程示意圖

2.2.4遺傳算法的基本框架

在一系列相關(guān)研究工作的基礎(chǔ)上,20世紀(jì)80年代由Goldberg進(jìn)行歸納總結(jié),形成了遺傳算法的基本框架,如圖2-8所示。

圖2-8遺傳算法基本框架示意圖

2.2.5遺傳算法的優(yōu)點

經(jīng)典的優(yōu)化方法包括共軛梯度法、擬牛頓法、單純形方法等。

經(jīng)典優(yōu)化算法的特點:算法往往是基于梯度的,靠梯度方向來提高個體性能;漸進(jìn)收斂;單點搜索;局部最優(yōu)。

圖2-9給出了遺傳算法與經(jīng)典算法求解問題的流程圖。

圖2-9遺傳算法和經(jīng)典方法求解問題流程圖

遺傳算法具有如下優(yōu)點:

(1)遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。

(2)遺傳算法同時進(jìn)行解空間的多點搜索。

(3)遺傳算法使用概率搜索技術(shù)。

(4)遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索,而非盲目地窮舉或完全隨機(jī)搜索。

(5)遺傳算法計算簡單、功能強(qiáng)。

2.2.6遺傳算法的五個關(guān)鍵問題

通常情況下,用遺傳算法求解問題需要解決以下五個問題:

(1)對問題的潛在解進(jìn)行基因的表示,即編碼問題。

(2)構(gòu)建一組潛在的解決方案,即種群初始化問題。

(3)根據(jù)潛在解的適應(yīng)性來評價解的好壞,即個體評價問題。

(4)改變后代基因組成的遺傳算子(選擇、交叉、變異等),即遺傳算子問題。

(5)設(shè)置遺傳算法使用的參數(shù)值(種群大小、應(yīng)用遺傳算子的概率等),即參數(shù)選擇問題。

2.3遺傳編碼和種群初始化

2.3.1遺傳編碼定義2.3.1由問題空間向GA編碼空間的映射稱為編碼,而由編碼空間向問題空間的映射稱為譯碼。

1.編碼的分類

(1)根據(jù)采用的符號,編碼可以分為二進(jìn)制編碼、實數(shù)編碼和整數(shù)排列編碼等。

(2)根據(jù)編碼采用的結(jié)構(gòu),編碼可以分為一維編碼和多維編碼。

(3)根據(jù)編碼采用的長度,編碼可以分為固定長度的編碼和可變長度的編碼。

(4)根據(jù)編碼的內(nèi)容,編碼可以分為僅對解進(jìn)行編碼的方法和對解+參數(shù)進(jìn)行編碼的方法。

2.碼空間與解空間

遺傳算法的一個特點就是個體存在碼空間和解空間:遺傳操作在碼空間,而評價和選擇在解空間,通過自然選擇將染色體和解連接起來。

解空間與碼空間相互關(guān)系如圖2-10所示。

圖2-10解空間與碼空間相互關(guān)系示意圖

3.非字符編碼的三個問題

(1)染色體的可行性,是指對染色體經(jīng)過解碼之后,是否存在于給定問題的可行域。

(2)染色體的合法性,編碼空間中的染色體必須對應(yīng)問題空間中的某一潛在解,即每個編碼必須有意義。

(3)映射的唯一性,染色體和潛在解必須一一對應(yīng)。編碼的可行性和合法性如圖2-11所示。圖2-11編碼可行性與合法性示意圖

4.不可行解產(chǎn)生的原因及求解方法

在實際問題中,約束是普遍的,可分為等式和不等約束,一般最優(yōu)解往往處于可行域與非可行域的交界處。罰函數(shù)是經(jīng)典的處理方法,它的作用在于強(qiáng)制可行解從可行解域和非可行解域到達(dá)最優(yōu)解?？尚杏蚺c非可行域示意圖如圖2-12所示。

求解約束優(yōu)化問題的常規(guī)解法可分為兩種:一種是把有約束問題轉(zhuǎn)化為無約束問題,再用無約束問題的方法求解;另一種是改進(jìn)無約束問題的求解方法,使之能用于有約束問題的情況。

圖2-12-可行域與非可行域示意圖

對于如下約束優(yōu)化問題:

通常,外罰函數(shù)法的一般表達(dá)式為

這里β、γ常取2,經(jīng)過大量的研究,Richiardsonetal得出以下結(jié)論:

依賴不可行解到可行域距離的罰函數(shù)的性能要優(yōu)于僅依靠違反約束的數(shù)目的罰函數(shù)的性能;當(dāng)所給問題的可行解和約束較少時,如果僅以違反約束的數(shù)目來構(gòu)造罰函數(shù),很難使得不可行解轉(zhuǎn)變?yōu)榭尚薪狻?/p>

罰函數(shù)法是遺傳算法用于約束優(yōu)化問題最常用的方法。從本質(zhì)上講,這種方法通過對不可行解的懲罰來將約束問題轉(zhuǎn)換為無約束問題。任何對約束的違反都要在目標(biāo)函數(shù)中添

加懲罰項。罰方法的基本思想從傳統(tǒng)優(yōu)化中借鑒而來。

從圖2-13中可以看出,此時的非可行解是不可拋棄的,它在進(jìn)化過程中比可行解更容易獲得全局最優(yōu)解。

圖2-13非可行解向全局最優(yōu)解進(jìn)化示意圖

5.編碼性能評價

碼空間到解空間的映射有以下三種情況:1對1映射、n對1映射和1對n映射,具體如圖2-14所示。

從圖2-14可以看出,1對1映射是三種映射中最好的;1對n映射是三種映射中最差的,存在適應(yīng)度評價問題;n對1映射則會存在資源的浪費。因此編碼要滿足以下三點:

(1)不冗余:碼空間到解空間是1對1映射;

(2)合法性:對編碼的任意排列對應(yīng)一個解;

(3)完備性:任意一個解都對應(yīng)一個排列。

圖2-14碼空間與解空間映射關(guān)系示意圖

2.3.2-種群初始化

1.種群規(guī)模

2.產(chǎn)生初始種群的方法

產(chǎn)生初始種群的方法通常有兩種。一種是完全隨機(jī)的方法,它適合于對問題的解無任何先驗知識的情況;另一種是根據(jù)某些先驗知識將其轉(zhuǎn)變?yōu)楸仨殱M足的一組要求,然后在滿足這些要求的解中再隨機(jī)地選取樣本。

采用隨機(jī)法產(chǎn)生初始種群時,若產(chǎn)生的隨機(jī)數(shù)大于0,則將種群中相應(yīng)染色體的相應(yīng)基因位置1,否則置0。

根據(jù)先驗知識產(chǎn)生初始種群時,對于給定的含有n個變量的個體,若第j個變量的取值范圍是(a[j],b[j]),則可以根據(jù)在(0,1)間產(chǎn)生的隨機(jī)正數(shù)r,按照公式a[j]+r*(b[j]-a[j])來計算個體第j位變量的取值。

兩者的對比如下:

2.4交叉和變異

2.4.1交叉算子定義2.4.1(交叉算子)所謂交叉,是指把兩個父代個體的部分結(jié)構(gòu)加以替換生成新個體的操作,這可以提高搜索能力。在交叉運(yùn)算之前還必須對群體中的個體進(jìn)行配對。

交叉算子主要有1斷點交叉(不易破壞好的模型)、雙斷點交叉、多斷點交叉(又稱廣義交叉,一般不使用,隨著交叉點的增多,個體結(jié)構(gòu)被破壞的可能性逐漸增大,影響算法的性能),算術(shù)交叉、模擬二進(jìn)制交叉、單峰正態(tài)交叉等。

1.1斷點交叉

實數(shù)編碼的1斷點交叉運(yùn)算示意圖如圖2-15所示。圖2-15實數(shù)編碼的1斷點交叉運(yùn)算示意圖

2.雙斷點交叉

雙斷點交叉運(yùn)算的示意圖如圖2-16所示。圖2-16雙斷點交叉運(yùn)算示意圖

例2.4.1針對TSP問題,假定有以下兩條染色體:

具體的交叉方式如下:

(1)選擇兩個斷點位置:第一個斷點位于第三和第四個基因之間;第二個斷點位于第七和第八個基因之間;

(2)移走p2中已在p1中的4、5、6和7后,得到路徑2—3—1—8—9;

(3)該序列順序放在o1中:o1=(231|4567|89);

(4)類似地,可以得到另一個后代:o2=(234|1867|59)。

3.算術(shù)交叉

假定有兩個父代x1和x2,其子代可以通過如下交叉方式得到

根據(jù)λ1和λ2-取值的不同,可以分為以下三類:

(1)凸交叉:滿足λ1

+λ2=1,λ1>0,λ2->0。

(2)仿射交叉:滿足λ1+λ2=1。

(3)線性交叉:滿足λ1+λ2≤2,λ1>0,λ2->0。

三種交叉示意圖如圖2-17所示。

圖2-17凸交叉、仿射交叉、線性交叉示意圖

4.基于方向交叉

基于方向交叉方式通過目標(biāo)函數(shù)值來決定搜索的方向。父代x1和x2通過以下方式交叉得到子代x':

其中,0<r≤1,x2不差于x1。

5.模擬二進(jìn)制交叉

模擬二進(jìn)制交叉(SBXcross-over)如下所示:

其中,

其中,aik、ajk(i≠j,k=1,…,n)是個體i、j的第k個決策變量。r、u是分布在[0,1]之間的隨機(jī)數(shù)。

6.單峰正態(tài)交叉

單峰正態(tài)交叉通過三個父代個體來產(chǎn)生兩個后代,第一個子代的方向取決于p1和p2,標(biāo)準(zhǔn)差正比于p1和p2之間的距離;第二個子代的方向與第一個子代的方向正交,標(biāo)準(zhǔn)方差取決于p3到第一個方向的距離。具體示意圖如圖2-18所示。

圖2-18單峰正太交叉示意圖

7.多父輩交叉

將多父輩交叉引入到遺傳算法中,可降低超級個體將自身復(fù)制到子代中的可能性,這就意味著帶來了更為多樣的解空間搜索結(jié)果,從而減少了遺傳算法早熟的危險。

多父輩交叉操作示意圖如圖2-19所示。

圖2-19多父輩交叉操作示意圖

2.4.2-變異算子

定義2.4.2(變異算子)變異就是將染色體編碼串中的某些基因用其他的基因來替換,它是遺傳算法中不可缺少的部分。其目的就是改善遺傳算法的局部搜索能力,維持群體的多樣性,防止出現(xiàn)早熟現(xiàn)象。

設(shè)計變異算子需要確定變異點的位置和基因值的替換,最常用的是基本位變異,它只改變編碼串中個別位的基因值,變異發(fā)生的概率也小,發(fā)揮作用比較慢,效果不明顯。變異算子主要有:均勻變異,它特別適用于算法的初期階段,增加了群體的多樣性;非均勻變異,隨著算法的運(yùn)行,它使得搜索過程更加集中在某一個重點區(qū)域中;邊界變異,適用于最優(yōu)點位于或接近于可行解邊界的問題;高斯變異,改進(jìn)了算法對重點搜索區(qū)域的局部搜索性能。隨著研究的不斷深入,變異算子的改進(jìn)和新算子不斷涌現(xiàn)。

1.隨機(jī)變異

隨機(jī)選擇一位進(jìn)行變異,具體如下所示:

例2.4.2-針對TSP問題,具體的變異方式如下:

(1)選擇兩個等位基因;

(2)將第二個等位基因插入到第一個等位基因之后,具體如下所示:

該變異方式的優(yōu)點是保護(hù)了大部分基因位信息的臨近關(guān)系。也可采用如下的變異方式:

(1)選擇兩個等位基因;

(2)將第二個等位基因和第一個等位基因位置互換,具體如下所示:

2.實數(shù)變異

其具體描述如下:

設(shè)s=(v1,v2,…,vn)是一個父解,分量vk

被選作進(jìn)行變異的分量,其定義區(qū)間是[ak,bk

],則變異后的解為

函數(shù)Δ(i,y)的具體表達(dá)式為

這里,r是[0,1]上的一個隨機(jī)數(shù),T表示最大代數(shù),λ是一個決定非一致性程度的參數(shù),它起著調(diào)整局部搜索區(qū)域的作用,其取值一般為2~5。

3.基于方向的變異

基于方向的變異方式通過目標(biāo)函數(shù)值來決定搜索的方向。父代x1和x2通過交叉得到子代x':

4.高斯變異

高斯變異的方法就是,產(chǎn)生一個服從高斯分布的隨機(jī)數(shù),取代先前基因中的實數(shù)數(shù)值。這個算法產(chǎn)生的隨機(jī)數(shù),其數(shù)學(xué)期望為當(dāng)前基因的實數(shù)數(shù)值。假定一個染色體由兩部分組

成(x,σ),其中,第一個分量x表示搜索空間中的一個點,第二個分量σ表示方差,則其子代個體按如下方式產(chǎn)生:

其中,N(0,Δσ')是一個均值為0,方差為σ'的高斯函數(shù)。

2.5選擇和適應(yīng)度函數(shù)

2.5.1選擇定義2.5.1選擇(selection)算子從群體中選擇優(yōu)勝個體,淘汰劣質(zhì)個體的操作稱為選擇,即從當(dāng)前群體中選擇適應(yīng)度值高的個體以生成配對池(matingpool)的過程。選擇算子有時又稱為再生算子(reproductionopenitor)。

1.選擇壓力

定義2.5.2選擇壓力選擇壓力是最佳個體選中的概率與平均選中概率的比值。

選擇的基礎(chǔ)是達(dá)爾文的適者生存理論,遺傳算法本質(zhì)上是一種隨機(jī)搜索,選擇算子則將遺傳搜索的方向引向最優(yōu)解所在區(qū)域,選擇的作用使得群體向最優(yōu)解所在區(qū)域移動。因

此,合適的選擇壓力很重要,選擇壓力太大容易早熟,選擇壓力太小,則進(jìn)化緩慢,如圖2-20所示。

圖2-20不同選擇壓力群體進(jìn)化方向示意圖

2.選擇方式

1)隨機(jī)采樣

(1)選擇幅度決定了每個個體被復(fù)制的次數(shù)。

(2)選擇幅度由以下兩部分組成:

①確定染色體的期望值;

②將期望值轉(zhuǎn)換為實際值,即該染色體后代個體的數(shù)目。

(3)經(jīng)過選擇將期望轉(zhuǎn)化為實際值,即后代個數(shù)常用的選擇方式:

①輪盤賭的選擇方式;

②一次隨機(jī)采樣。

這兩種采樣方式如圖2-21所示。

圖2-21選擇方式示意圖

2)確定性采樣

確定性采樣就是從父代和子代個體中選擇最優(yōu)的個體。具體舉例如下:

(1)(μ+λ)-selection(μ個父代,λ個子代,從μ+λ中選擇最好的μ個個體);

(2)(μ,λ)-selection(μ個父代,λ個子代,從λ中選擇最好的μ個個體);

(3)Truncationselection(截斷選擇);

(4)Blockselection(塊選擇);

(5)Elitistselection(貪婪選擇,在比例選擇最優(yōu)個體時沒有被選擇,進(jìn)行強(qiáng)制選擇);

(6)Thegenerationalreplacement(代替換);

(7)Steady-statereproduction(穩(wěn)態(tài)再生,n個最差的父代個體被子代替換)。

3)混合采樣

混合采樣同時具有隨機(jī)性和確定性,具體舉例如下:

(1)Tournamentselection(競賽選擇);

(2)Binarytournamentselection(規(guī)模為2的競賽選擇);

(3)Stochastictournamentselection(采用普通的方法計算選擇概率,然后采用賭盤選擇個體,適應(yīng)度高的進(jìn)入群體,否則被拋棄);

(4)Remainderstochasticsampling(隨機(jī)保留采樣,期望選擇次數(shù)的整數(shù)部分確定,小數(shù)部分隨機(jī))。

2.5.2-適應(yīng)度函數(shù)

1.目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)

(1)對于最小化問題,建立如下適應(yīng)函數(shù)和目標(biāo)函數(shù)的映射關(guān)系:

其中,cmax可以是一個輸入值或是理論上的最大值,也可以是當(dāng)前所有代或最近K代中g(shù)(x)的最大值,此時cmax隨著代數(shù)會有變化。

(2)對于最大化問題,一般采用以下映射:

其中,g(x)為目標(biāo)函數(shù)值,cmin可以是一個輸入值,也可以是當(dāng)前所有代或最近K代中g(shù)(x)的最小值。

2.適應(yīng)度變換

對于未成熟收斂現(xiàn)象,應(yīng)設(shè)法降低某些異常個體的競爭力,這可以通過縮小相應(yīng)的適應(yīng)度值來實現(xiàn)。對于隨機(jī)漫游現(xiàn)象,應(yīng)設(shè)法提高個體間的競爭力差距,這可以通過放大相應(yīng)的適應(yīng)度值來實現(xiàn)。這種適應(yīng)度的縮放調(diào)整稱為適應(yīng)度變換,即假定第k個染色體的原始適應(yīng)度為fk,變換后的適應(yīng)度fk'為

2.5.3適應(yīng)度共享和群體多樣性

1.簡介

共享函數(shù)法根據(jù)個體在某個距離內(nèi)與其他個體的臨近程度來確定該個體的適應(yīng)度應(yīng)改變多少。在擁擠的峰周圍的個體的復(fù)制概率受到抑制,利于其他個體產(chǎn)生后代,如圖2-22所示。

圖2-22-共享函數(shù)法示意圖

根據(jù)兩個染色體之間采用的距離測度的不同,適應(yīng)度共享可以分為以下兩類:

(1)Genotypicsharing(基因型共享)。個體之間的距離在碼空間進(jìn)行計算,具體如下:

其中,si表示編碼形式的一個字符串或者一條染色體。

(2)Phenotypicsharing(表現(xiàn)型共享)。個體之間的距離在解空間進(jìn)行計算,具體如下:

其中,xi表示解碼后的一個解。

2.定義

共享函數(shù)Sh(dij)定義如下:

其中,α是一個常數(shù),σshare是用戶定義的小生境半徑。

在給定了適應(yīng)度函數(shù)的定義之后,一個染色體的共享適應(yīng)度fi'定義如下:

式中,mi為給定染色體i的小生境計數(shù)(thenichecount),即染色體i與群體中所有染色體之間共享函數(shù)之和,具體定義如下:

2.6遺傳算法用于求解數(shù)值優(yōu)化問題

1.優(yōu)化問題例2.6.1無約束單目標(biāo)優(yōu)化問題。圖2-23給出了例2.6.1中問題解的分布情況。

圖2-23無約束單目標(biāo)優(yōu)化問題

2.編碼和解碼

1)二進(jìn)制編碼

要求采用二進(jìn)制編碼,精確到小數(shù)點后面五位。編碼長度的求解過程如下:

(1)根據(jù)精度要求,要將區(qū)間至少分成(bj-aj)×105份,其中aj為變量xj的最小值,bj

為變量xj的最大值。

(2)變量xj需要的比特位mj要滿足下式:

2)二進(jìn)制解碼

以vj為例,二進(jìn)制串的解碼過程如下:

3.種群初始化

隨機(jī)產(chǎn)生一個初始種群,以產(chǎn)生10個個體為例:

4.個體評價

在遺傳算法中,適應(yīng)度函數(shù)起到環(huán)境的作用。在該無約束、單目標(biāo)優(yōu)化問題中,將適應(yīng)度eval定義為目標(biāo)函數(shù)值,具體計算如下:

由于目標(biāo)函數(shù)表達(dá)式為

若給定x1=-2.59210,x2=5.31320,可得

因此,可以求得上述10個個體的適應(yīng)度函數(shù)如下:

很明顯,在10個個體中,最好的個體是v10,最差的個體是v9。

5.選擇(無偏見,平等)

輪盤賭選擇又稱比例選擇算子,其基本思想是:個體被選中的概率與其適應(yīng)度函數(shù)值成正比。具體步驟如下:

例2.6.2-輪盤賭選擇過程。

輸入:群體P(t-1),C(t-1)

輸出:群體P(t),C(t)

Step3計算染色體vk的累積概率qk:

Step4隨機(jī)產(chǎn)成10個[0,1]區(qū)間內(nèi)的數(shù):

隨后,將產(chǎn)生的10個隨機(jī)數(shù)依次與累積概率作比較,應(yīng)用輪盤選擇的方法依次選擇出10個個體,選擇過程采用的輪盤如圖2-24所示。

圖2-24輪盤賭選擇的輪盤示意圖

最終選擇的個體如下:

6.交叉(1斷點交叉)

采用1斷點交叉,即隨機(jī)選擇一個斷點,交換兩個父代個體的右側(cè)部分,從而產(chǎn)生子代。

例2.6.3考慮如下兩個個體,隨機(jī)選擇第17個基因位作為斷點。

其中,c1、c2是交叉操作后產(chǎn)生的子代。

7.變異

定義2.6.1變異操作是指根據(jù)變異概率改變一個或多個基因。

例2.6.4對于個體v1,隨機(jī)選擇該個體的第16位進(jìn)行變異,因為該基因值為1,所以變異后為0,從而得到子代c1,具體過程如下:

8.流程和實驗結(jié)果

1)GA(遺傳算法)用于求解無約束優(yōu)化問題的流程

2)實驗結(jié)果

GA求解無約束單目標(biāo)優(yōu)化問題結(jié)果如圖2-25所示。圖2-25GA求解無約束單目標(biāo)優(yōu)化問題結(jié)果示意圖

GA在本例函數(shù)中的尋優(yōu)過程如圖2-26所示。圖2-26GA在例2.3.1函數(shù)中的尋優(yōu)過程示意圖

2.7遺傳算法的理論基礎(chǔ)

2.7.1模式理論1.問題引出例2.7.1求maxf(x)=x2,x∈{0,1,2,…,31}。

【分析】當(dāng)編碼的最左邊字符為“1”時,其個體適應(yīng)度較大,如2號個體和4號個體,將其記為“1****”;其中2-號個體適應(yīng)度最大,其編碼的左邊兩位都是1,記為

“11***”;當(dāng)編碼的最左邊字符為“0”時,其個體適應(yīng)度較小,如1號和3號個體,記為“0****”。

【結(jié)論】從這個例子可以看出,我們在分析編碼字符串時,常常只關(guān)心某一位或某幾位字符,而對其他字符不關(guān)心。換句話講,我們只關(guān)心字符的某些特定形式,如1****,

11***,0****,這種特定的形式就叫模式。

2.基本概念

1)模式

模式集(Schema)是指編碼的字符串中具有類似特征的子集。以五位二進(jìn)制字符串為例,模式*111*可代表4個個體:01110、01111、11110、11111;模式*0000則代表2個個體:10000、00000。

個體是由二值字符集V={0,1}中的元素組成的一個編碼串;而模式卻是由三值字符集V={0,1,*}中的元素組成的一個編碼串,其中“*”表示通配符,它既可被當(dāng)作“1”也可被當(dāng)作“0”。

2)模式階(SchemaOrder)

定義2.7.1模式階是指模式中已有明確含義(二進(jìn)制字符時指0或1)的字符個數(shù),記作o(s),式中s代表模式。

舉例:模式(011*1**)含有4個明確含義的字符,其階次是4,記作o(011*1**)=4;模式(0******)的階次是1,記作o(0******)=1。

階次越低,模式的概括性越強(qiáng),其所代表的編碼串個體數(shù)也越多,反之亦然;當(dāng)模式階次為零時,它沒有明確含義的字符,其概括性最強(qiáng)。

3)模式的定義長度(SchemaDefiningLength)

定義2.7.2-模式的定義長度是指模式中第一個和最后一個具有明確含義的字符之間的距離,記作δ(s)。

舉例:模式(011*l**)的第一個字符為0,最后一個字符為l,中間有3個字符,其定義長度為4,記作δ(011*l**)=4。

模式(0******)的長度是0,記作δ(0******)=0。一般地,有如下式子:

δ(s)=b-a(2.22)

式中,b為模式s中最后一個明確字符的位置;a為模式s中第一個明確字符的位置。

模式的長度代表該模式在今后遺傳操作(交叉、變異)中被破壞的可能性:模式長度越短,被破壞的可能性越小,長度為0的模式最難被破壞。

4)編碼字符串的模式數(shù)目

(1)模式總數(shù)。假設(shè)二進(jìn)制字符串的長度為l,字符串中每一個字符可取(0,1,*)三個符號中的任意一個,可能組成的模式數(shù)目最多為

3×3×3×…×3=(2+1)l(2.23)

一般情況下,假設(shè)字符串長度為l,字符的取值為k種,字符串組成的模式數(shù)目nl最多為nl=(k+1)l。

(2)編碼字符串(一個個體編碼串)所含模式總數(shù)。對于長度為l的某二進(jìn)制字符串,它含有的模式總數(shù)最多為

2×2×2×…×2=2l(2.24)

【注意】這個數(shù)目是指字符串已確定為0或1,每個字符只能在已定值(0/1)中選取;前面所述的n1指字符串未確定,每個字符可在{0,1,*}三者中選取。

一般情況下,長度為l、取值有k種的某一字符串,它可能含有的模式數(shù)目最多為

n2-=2l(2.25)

(3)群體所含模式數(shù)。在長度為l、規(guī)模為M的二進(jìn)制編碼字符串群體中,一般包含2l~M·2l個模式。

3.模式定理

1)復(fù)制時的模式數(shù)目

這里以比例選擇算子為例研究。

公式推導(dǎo)如下:

(1)假設(shè)在第t次迭代時,群體P(t)中有M個個體,其中m個個體屬于模式s,記作(s,t)。

(2)個體ai按其適應(yīng)度fi的大小進(jìn)行復(fù)制。從統(tǒng)計意義來講,ai被復(fù)制的概率pi為

進(jìn)一步推導(dǎo)如下:

2)交叉時的模式數(shù)目

【舉例】

【公式推導(dǎo)】

3)變異時的模式數(shù)目

【公式推導(dǎo)】

(1)變異時個體的每一位發(fā)生變化的概率是變異概率pm,即每一位存活的概率是1-pm。根據(jù)模式的階o(s),可知模式中有明確含義的字符有o(s)個,于是模式s存活的概率是

(2)通常pm?1,上式用泰勒級數(shù)展開取一次項,可近似表示為

【結(jié)論】式(2.37)說明,模式的階次o(s)越低,模式s存活的可能性越大,反之亦然。

4)模式定理

綜合上述1)、2)、3)的內(nèi)容可以得出,遺傳算法經(jīng)復(fù)制、交叉、變異操作后,模式s在下一代群體中所擁有的個體數(shù)目如下:

【模式定理】適應(yīng)度高于群體平均適應(yīng)度的,長度較短,低階的模式在遺傳算法的迭代過程中將按指數(shù)規(guī)律增長。

2.7.2-建筑塊假說

1.模式對搜索空間的劃分

以求maxf(x)=x2,x∈{0,1,2,…,31}為例,圖2-27中:橫坐標(biāo)表示x,縱坐標(biāo)代表適應(yīng)度f(x)=x2,用千分?jǐn)?shù)表示,弧線表示適應(yīng)度曲線,網(wǎng)點區(qū)代表所有符合此模式的個體集合,則幾個模式對搜索空間的劃分分別如圖2-27(a)~(c)所示。

【結(jié)論】模式能夠劃分搜索空間,且模式的階(已確定個數(shù))越高,對搜索空間的劃分越細(xì)致。

圖2-27幾個模式對搜索空間劃分示意圖

2.分配搜索次數(shù)

模式定理告訴我們:GA根據(jù)模式的適應(yīng)度、長度和階次為模式分配搜索次數(shù)。為那些適應(yīng)度較高、長度較短、階次較低的模式分配的搜索次數(shù)按指數(shù)率增長;為那些適應(yīng)度較

低、長度較長、階次較高的模式分配的搜索次數(shù)按指數(shù)率衰減。

3.建筑塊假說

前面我們已經(jīng)介紹了GA如何劃分搜索空間及在各個子空間中分配搜索次數(shù),那么GA如何利用搜索過程中的積累信息加快搜索速度呢?Holland和Goldberg在模式定理的基礎(chǔ)上提出了“建筑塊假說”。

定義2.7.3建筑塊(或稱積木塊)(BulidingBlock)為短定義長度、低階、高適應(yīng)度模式。

之所以稱之為建筑塊(積木塊),是由于遺傳算法的求解過程并不是在搜索空間中逐一測試各個基因的枚舉組合,而是通過一些較好的模式,像搭積木一樣,將它們拼接在一起,從而逐漸構(gòu)造出適應(yīng)度越來越高的個體編碼串。

【建筑塊假說】GA在搜索過程中將不同的“建筑塊”通過遺傳算子(如交叉算子)的作用將其結(jié)合在一起,形成適應(yīng)度更高的新模式,這樣可大大縮小GA的搜索范圍。

【建筑塊混合】建筑塊通過遺傳算子的作用集合在一起的過程稱為“建筑塊混合”。當(dāng)那些構(gòu)成最優(yōu)點(或近似最優(yōu)點)的“建筑塊”結(jié)合在一起時,就得到了最優(yōu)點。

例2.7.2-建筑塊混合實例。

假如,問題的最優(yōu)解用三個建筑塊BB1、BB2、BB3表示,群體中有8個個體,初始群體中個體1、個體2包含建筑塊BB1,個體3包含建筑塊BB3,個體5包含建筑塊BB2,在群體進(jìn)化過程中,建筑塊的組合過程如圖2-28所示。

由于第三代群體中出現(xiàn)了一個包含3個“建筑塊”的個體P3,此時個體P3就代表這個問題的最優(yōu)解。

圖2-28建筑塊混合過程示意圖

2.8進(jìn)化算法的收斂性分析

2.8.1收斂性的定義定義2.8.1設(shè)Zt為t時刻種群中所包含個體的適應(yīng)值的最大值,f*為適應(yīng)值函數(shù)f(x)在所有可能的個體所組成的集合X中所取得的最大值,若Zt滿足則稱算法收斂到最優(yōu)解。

2.8.2-基于壓縮映射原理的收斂性分析

定義2.8.2-設(shè)X是一個非空集合。若d是一個X×X到R的映射,并且對于

?x,y,z∈X滿足:

(1)d(x,y)≥0,并且d(x,y)=0,當(dāng)且僅當(dāng)x=y;

(2)d(x,y)=d(y,x);

(3)d(x,y)≤d(x,z)+d(z,y)。

則稱d為X上的度量(或稱為距離函數(shù)),稱(X,d)為度量空間。

定理2.8.1在度量空間(X,d)中,

(1)對于?x,y,z∈X,有|d(x,z)-d(y,z)|≤d(x,y);

(2)對于?x,y,x1,y1∈X,有|d(x,y)-d(x1,y1)|≤d(x,x1)+d(y,y1)。

定義2.8.3設(shè)(X,d)為度量空間,{xn}是(X,d)中的序列。若存在正整數(shù)N,使得對于一切n>N,有d(xn,x)<ε,則稱序列{xn}在(X,d)中收斂于x,x稱為{xn}的極限,記為xn→x。

定義2.8.4設(shè)(X,d)為度量空間,{xn}是(X,d)中的序列。若對于?ε>0,存在正整數(shù)N,使得對于一切m,n>N,有d(xm,xn)<ε,則稱序列{xn}是(X,d)中的Cauchy序列。若(X,d)中的每一個Cauchy序列都收斂,則稱(X,d)為完備度量空間。

2.8.3基于有限Markov鏈的收斂性分析

定義2.8.9對于一個n×n的方陣A:

2.8.4公理化模型

定理2.8.7在下述條件下,任何抽象演化算法AEA次收斂:

則AEA強(qiáng)收斂。

以上所述的公理化模型也可用于其他進(jìn)化算法(如進(jìn)化策略)的收斂性分析。

2.9基于進(jìn)化計算的約束優(yōu)化問題

2.9.1無約束優(yōu)化問題

1.認(rèn)識無約束優(yōu)化問題對于一個具有n個實變量的實函數(shù)f(x),我們想要找到一個對應(yīng)于最小函數(shù)值的n元向量x*,這個n元向量x*就是該實函數(shù)的最優(yōu)解。最優(yōu)解在于找到如下的n元向量x*:其中,函數(shù)f(x)稱為目標(biāo)函數(shù),x*為目標(biāo)函數(shù)的最小值點,xL和xR

分別為x的上界和下界。

例2.9.1單變量函數(shù)優(yōu)化問題。

此例中我們考慮一個變量的函數(shù),如圖2-29所示,函數(shù)f(x)=(x-x*)2-有一個唯一的最小值解x*。圖2-29函數(shù)f(x)=(x-x*)2-曲線

例2.9.2-周期函數(shù)優(yōu)化問題。

函數(shù)f(x)=-2cos(2x-2x*)有無窮多個最小值點,如圖2-30所示,最小值點x=x*+pπ,p為整數(shù)。

圖2-30函數(shù)f(x)=-2cos(2x-2x*)曲線

例2.9.3多模態(tài)函數(shù)優(yōu)化問題。

對于函數(shù)f(x)=0.015(x-x*)2-2cos(2x-2x*),如圖2-31所示,它有一個全局最優(yōu)解x*,而且有一些局部最小值點,比如x1、x2,它們分別是特定區(qū)域內(nèi)的函數(shù)最小值點。圖2-31函數(shù)f(x)=0.015(x-x*)2-2cos(2x-2x*)曲線

例2.9.4多峰函數(shù)優(yōu)化問題。

圖2-32、圖2-33和圖2-34給出了幾個多峰函數(shù)。

對于無約束優(yōu)化問題,理想狀況下目標(biāo)函數(shù)只有唯一的最小值點,將其稱為全局最小值點。然而在一些情況下,目標(biāo)函數(shù)有數(shù)個(甚至是無窮多個)最小值點,這時找到其中一個最小值點就夠了。在實際應(yīng)用中,目標(biāo)函數(shù)經(jīng)常具有一個全局最優(yōu)解,多個局部最優(yōu)解,因此尋找全局最優(yōu)解有一定困難。

圖2-33函數(shù)G(x,y)=20+x2-10cos2πx+y2-10cos2πy曲線

圖2-34函數(shù)F(x,y)=xsin(4πx)-ysin(4πy)+1曲線

2.無約束優(yōu)化問題形式

通常,一個無約束優(yōu)化問題的數(shù)學(xué)表達(dá)形式如下:

其中,f為一實值函數(shù),Ω為可行域,它是

Rn

的一個子集。當(dāng)Ω=Rn

時,上述無約束優(yōu)化問題成為完全無約束優(yōu)化問題。

定義2.9.1若ε>0,使得對于x*的ε距離范圍內(nèi)的x均有f(x)≥f(x*),那么點x*∈Ω就稱為f在可行域Ω內(nèi)的一個局部極小值點。

定義2.9.2-若對于?x∈Ω,均有f(x)≥f(x*),那么點x*∈Ω就稱為f在可行域Ω內(nèi)的全局極小值點。

3.無約束優(yōu)化問題求解

為了對無約束優(yōu)化問題有更清晰的認(rèn)識,下面以經(jīng)典的Ackley’s函數(shù)遺傳算法求解過程來進(jìn)一步認(rèn)識無約束優(yōu)化問題。

例2.9.5Ackley’s函數(shù)求解。

已知c1=20,c2=0.2,c3=2π,e=2.71282,其函數(shù)圖像形式如圖2-35所示。圖2-35Ackley’s函數(shù)圖像

為最小化Ackley’s函數(shù),使用遺傳算法對其求解,具體設(shè)置如下:

①采用實數(shù)編碼方式;

②采用算數(shù)交叉算子;

③采用非一致性變異算子;

④采用最好種群選擇法(to

(4)最好種群選擇。最好種群選擇是從父代和子代中選擇出最好的popsize(種群規(guī)模)數(shù)量的個體以產(chǎn)生下一代。對于要求解的函數(shù),因為目標(biāo)函數(shù)值均為正值,但考慮到其求

解的是最小化問題,所以應(yīng)將目標(biāo)函數(shù)值取反并加上一個合適的正常數(shù)c以產(chǎn)生適應(yīng)度函數(shù),所以適應(yīng)度函數(shù)具有如下形式:

eval(v)=-f(x)+c(2.53)

求解該函數(shù)最優(yōu)化問題時,遺傳算法的參數(shù)設(shè)置如下:

①種群規(guī)模popsize=10;

②交叉概率pc=0.8;

③變異概率pm=0.03;

④最大迭代次數(shù)maxGen=1000。

2.9.2-約束優(yōu)化問題的形式及處理方法

1.約束優(yōu)化問題一般形式

約束優(yōu)化處理帶有等式或不等式約束的目標(biāo)函數(shù)優(yōu)化問題,現(xiàn)實中的許多問題可以成功地建模為約束優(yōu)化問題。通常約束優(yōu)化問題具有如下形式:

其中,f是目標(biāo)函數(shù),gi(x)≤0為不等式約束,hi(x)=0為等式約束,X為可行域,它包含了變量x的上界和下界。

如圖2-36所示。

圖2-36可行域與非可行域示意圖

2.約束處理方法

(1)修理策略。

(2)拋棄策略。

(3)懲罰策略。

(4)修改遺傳算子策略。

3.其他約束處理方法

(1)目標(biāo)函數(shù)與約束條件分開處理法。

①協(xié)同進(jìn)化法;

②可行解劃分優(yōu)先級法;

③行為記憶法;

④多目標(biāo)優(yōu)化方法。

(2)混合方式處理法。

①拉格朗日乘子法;

②隨機(jī)進(jìn)化的約束優(yōu)化方法;

③模糊邏輯方法;

④免疫系統(tǒng)方法;

⑤文化算法。

2.9.3罰函數(shù)

1.罰函數(shù)介紹

罰函數(shù)方法是在目標(biāo)函數(shù)中加上一個懲罰項P(g,h),對于最大化問題它滿足:當(dāng)約束滿足時,P(g,h)=0;否則P(g,h)<0,其作用在于反映該點是否位于可行域內(nèi)。罰函數(shù)由Courant提出,Carroll、Fiacco及McCormick對它進(jìn)行了深入研究和推廣。

若給定的初始點在可行域內(nèi)部,則利用內(nèi)罰函數(shù)法所產(chǎn)生的點列都是內(nèi)點。從幾何上看,內(nèi)罰函數(shù)法在可行域的邊界上形成一堵無窮高的“障礙墻”,所以內(nèi)罰函數(shù)法也稱障礙函數(shù)法。目前,用進(jìn)化算法求解約束優(yōu)化問題時應(yīng)用較多的是外罰函數(shù)法,其優(yōu)點是不一定要求初始群體都是可行的。這是因為在許多實際應(yīng)用問題中,尋找可行解本身就是NP難問題。通常,外罰函數(shù)法的一般表達(dá)式為

2.傳統(tǒng)罰方法與進(jìn)化算法罰方法的比較

罰方法可能是遺傳算法中用于約束優(yōu)化問題最常用的方法。從本質(zhì)上講,這種方法通過對不可行解的懲罰來將約束問題轉(zhuǎn)換為無約束問題,任何對約束的違反都要在目標(biāo)函數(shù)中添加懲罰項,罰方法的基本思想從傳統(tǒng)優(yōu)化中借鑒而來。

圖2-37對于不可行解的信息保留給出了直觀的解釋。不可行解b遠(yuǎn)比不可行解d和可行解c離最優(yōu)解a要近,因此我們希望對b的懲罰比對d的懲罰要小,盡管b是不可行解,但它帶有最優(yōu)解的信息要比c多。

圖2-37不可行解b保留遺傳信息示意圖

3.罰函數(shù)的構(gòu)造

(2)采用目標(biāo)函數(shù)乘懲罰項的方式,得到的表達(dá)式如下:

4.罰函數(shù)分類

在遺傳算法中,已經(jīng)提出了一些方法用于處理非可行解。通常,這些方法可以分為變懲罰和靜懲罰方法。

(1)變懲罰方法:包含兩部分,分別是懲罰數(shù)目和懲罰強(qiáng)度。

①懲罰數(shù)目,即可變懲罰比率,它可根據(jù)違反約束的程度和遺傳算法的迭代次數(shù)來調(diào)節(jié)。

②懲罰強(qiáng)度,它取決于違反約束的強(qiáng)度。

(2)靜懲罰方法:它對于一些復(fù)雜的問題并不高效,現(xiàn)階段大多數(shù)的研究工作主要聚焦在變懲罰方法的研究上。

5.懲罰項的理解

本質(zhì)上,懲罰項是非可行解到可行域距離的函數(shù),它通?？梢杂上旅嫒N方式給出:

(1)一個非可行解到可行域的絕對距離;

(2)在當(dāng)前種群中,所有的非可行解到可行域的相對距離;

(3)采用自適應(yīng)的方式給出懲罰項。

在上述的距離度量中,考慮的因素可能包含:

①違反約束的數(shù)目;

②約束違反的總量;

③非可行解到可行域的距離;

④非可行解到全局最優(yōu)解的距離。

6.三種懲罰方式

(1)靜懲罰函數(shù)。靜懲罰函數(shù)的特點是:

①對于所有的非可行解采用固定的懲罰項;

②對每個違反的約束添加一個懲罰值C。

這兩種方式通常不如使用一些到可行域距離的度量方式。

(2)變懲罰函數(shù)。變懲罰函數(shù)是為了避免手動設(shè)置Ci的值而設(shè)立的,而且可根據(jù)進(jìn)化時間來自動決定Ci以完成對非可行解的懲罰。

(3)自適應(yīng)懲罰函數(shù)。對于自適應(yīng)懲罰,Bean和Hadj-Alouane提出根據(jù)最近幾代最好的性能來修正懲罰函數(shù);Smith和Tate和Coit等提出,懲罰應(yīng)該隨著時間的推移,能夠估計“接近可行的閾值”;Eiben等提出,在約束滿足的時候應(yīng)該改變偏置。

2.9.4應(yīng)用GA求解約束優(yōu)化問題

1.GA求解約束優(yōu)化問題的過程

遺傳算法在求解問題時,首先實現(xiàn)從性狀到基因型的映

射,得到初始種群后,就會按照優(yōu)勝劣汰的原則,選擇出適應(yīng)度高的個體,通過復(fù)制、交叉、變異產(chǎn)生新的種群,并在不斷地選擇過程中產(chǎn)生越來越好的解。同時,遺傳算子在求解問題時也是至關(guān)重要的,主要涉及交叉和變異算子,常見的交叉算子有斷點交叉、算術(shù)交叉、基于方向的交叉、模擬二進(jìn)交叉、單峰正態(tài)交叉和多父輩交叉等;常見的變異算子有隨機(jī)變異、實數(shù)變