《計(jì)算機(jī)智能導(dǎo)論》課件-第2章

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

2.1緒論2.1.1引例

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

例2.1.2

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

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

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

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

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

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

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

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

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

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

拉馬克認(rèn)為:

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

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

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

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

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

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

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

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

2)Darwin進(jìn)化論

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

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

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

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

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

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

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

3)孟德?tīng)栠z傳學(xué)

幾乎在達(dá)爾文提出進(jìn)化論的同時(shí),孟德?tīng)栒谀剡M(jìn)行著豌豆雜交實(shí)驗(yàn),他把實(shí)驗(yàn)結(jié)果總結(jié)為以下兩條定律,德國(guó)植物學(xué)家Correns將這些定律概括為孟德?tīng)柖?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

爬山法求解問(wèn)題示意圖如圖2-5所示。

圖2-5爬山法求解問(wèn)題示意圖

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

3.進(jìn)化計(jì)算

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

1)進(jìn)化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)智能性。

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

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

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

2.2-遺傳算法

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

2.2.2-遺傳的特點(diǎn)

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

(1)遺傳算法必須通過(guò)適當(dāng)?shù)姆椒▽?duì)問(wèn)題的可行解進(jìn)行編碼。

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

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

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

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

2.2.3示例

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

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

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

交叉:編碼的交叉重組,類(lèi)似于染色體的交叉重組。

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

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

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

2.2.4遺傳算法的基本框架

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

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

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

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

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

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

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

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

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

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

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

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

(5)遺傳算法計(jì)算簡(jiǎn)單、功能強(qiáng)。

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

通常情況下,用遺傳算法求解問(wèn)題需要解決以下五個(gè)問(wèn)題:

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

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

(3)根據(jù)潛在解的適應(yīng)性來(lái)評(píng)價(jià)解的好壞,即個(gè)體評(píng)價(jià)問(wèn)題。

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

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

2.3遺傳編碼和種群初始化

2.3.1遺傳編碼定義2.3.1由問(wèn)題空間向GA編碼空間的映射稱(chēng)為編碼,而由編碼空間向問(wèn)題空間的映射稱(chēng)為譯碼。

1.編碼的分類(lèi)

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

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

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

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

2.碼空間與解空間

遺傳算法的一個(gè)特點(diǎn)就是個(gè)體存在碼空間和解空間:遺傳操作在碼空間,而評(píng)價(jià)和選擇在解空間,通過(guò)自然選擇將染色體和解連接起來(lái)。

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

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

3.非字符編碼的三個(gè)問(wèn)題

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

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

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

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

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

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

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

對(duì)于如下約束優(yōu)化問(wèn)題:

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

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

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

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

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

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

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

5.編碼性能評(píng)價(jià)

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

從圖2-14可以看出,1對(duì)1映射是三種映射中最好的;1對(duì)n映射是三種映射中最差的,存在適應(yīng)度評(píng)價(jià)問(wèn)題;n對(duì)1映射則會(huì)存在資源的浪費(fèi)。因此編碼要滿(mǎn)足以下三點(diǎn):

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

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

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

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

2.3.2-種群初始化

1.種群規(guī)模

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

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

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

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

兩者的對(duì)比如下:

2.4交叉和變異

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

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

1.1斷點(diǎn)交叉

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

2.雙斷點(diǎn)交叉

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

例2.4.1針對(duì)TSP問(wèn)題,假定有以下兩條染色體:

具體的交叉方式如下:

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

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

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

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

3.算術(shù)交叉

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

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

(1)凸交叉:滿(mǎn)足λ1

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

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

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

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

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

4.基于方向交叉

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

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

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

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

其中,

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

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

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

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

7.多父輩交叉

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

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

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

2.4.2-變異算子

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

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

1.隨機(jī)變異

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

例2.4.2-針對(duì)TSP問(wèn)題,具體的變異方式如下:

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

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

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

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

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

2.實(shí)數(shù)變異

其具體描述如下:

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

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

],則變異后的解為

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

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

3.基于方向的變異

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

4.高斯變異

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

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

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

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

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

1.選擇壓力

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

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

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

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

2.選擇方式

1)隨機(jī)采樣

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

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

①確定染色體的期望值;

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

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

①輪盤(pán)賭的選擇方式;

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

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

圖2-21選擇方式示意圖

2)確定性采樣

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

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

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

(3)Truncationselection(截?cái)噙x擇);

(4)Blockselection(塊選擇);

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

(6)Thegenerationalreplacement(代替換);

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

3)混合采樣

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

(1)Tournamentselection(競(jìng)賽選擇);

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

(3)Stochastictournamentselection(采用普通的方法計(jì)算選擇概率,然后采用賭盤(pán)選擇個(gè)體,適應(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)對(duì)于最小化問(wèn)題,建立如下適應(yīng)函數(shù)和目標(biāo)函數(shù)的映射關(guān)系:

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

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

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

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

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

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

1.簡(jiǎn)介

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

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

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

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

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

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

其中,xi表示解碼后的一個(gè)解。

2.定義

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

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

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

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

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

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

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

2.編碼和解碼

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

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

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

為變量xj的最大值。

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

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

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

3.種群初始化

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

4.個(gè)體評(píng)價(jià)

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

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

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

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

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

5.選擇(無(wú)偏見(jiàn),平等)

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

例2.6.2-輪盤(pán)賭選擇過(guò)程。

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

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

Step3計(jì)算染色體vk的累積概率qk:

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

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

圖2-24輪盤(pán)賭選擇的輪盤(pán)示意圖

最終選擇的個(gè)體如下:

6.交叉(1斷點(diǎn)交叉)

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

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

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

7.變異

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

例2.6.4對(duì)于個(gè)體v1,隨機(jī)選擇該個(gè)體的第16位進(jìn)行變異,因?yàn)樵摶蛑禐?,所以變異后為0,從而得到子代c1,具體過(guò)程如下:

8.流程和實(shí)驗(yàn)結(jié)果

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

2)實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

【結(jié)論】從這個(gè)例子可以看出,我們?cè)诜治鼍幋a字符串時(shí),常常只關(guān)心某一位或某幾位字符,而對(duì)其他字符不關(guān)心。換句話講,我們只關(guān)心字符的某些特定形式,如1****,

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

2.基本概念

1)模式

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

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

2)模式階(SchemaOrder)

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

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

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

3)模式的定義長(zhǎng)度(SchemaDefiningLength)

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

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

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

δ(s)=b-a(2.22)

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

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

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

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

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

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

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

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

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

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

n2-=2l(2.25)

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

3.模式定理

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

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

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

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

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

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

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

【舉例】

【公式推導(dǎo)】

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

【公式推導(dǎo)】

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

(2)通常pm?1,上式用泰勒級(jí)數(shù)展開(kāi)取一次項(xiàng),可近似表示為

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

4)模式定理

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

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

2.7.2-建筑塊假說(shuō)

1.模式對(duì)搜索空間的劃分

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

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

圖2-27幾個(gè)模式對(duì)搜索空間劃分示意圖

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

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

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

3.建筑塊假說(shuō)

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

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

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

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

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

例2.7.2-建筑塊混合實(shí)例。

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

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

圖2-28建筑塊混合過(guò)程示意圖

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

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

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

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

?x,y,z∈X滿(mǎn)足:

(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)。

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

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

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

(2)對(duì)于?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,使得對(duì)于一切n>N,有d(xn,x)<ε,則稱(chēng)序列{xn}在(X,d)中收斂于x,x稱(chēng)為{xn}的極限,記為xn→x。

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

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

定義2.8.9對(duì)于一個(gè)n×n的方陣A:

2.8.4公理化模型

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

則AEA強(qiáng)收斂。

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

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

2.9.1無(wú)約束優(yōu)化問(wèn)題

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

分別為x的上界和下界。

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

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

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

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

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

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

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

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

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

對(duì)于無(wú)約束優(yōu)化問(wèn)題,理想狀況下目標(biāo)函數(shù)只有唯一的最小值點(diǎn),將其稱(chēng)為全局最小值點(diǎn)。然而在一些情況下,目標(biāo)函數(shù)有數(shù)個(gè)(甚至是無(wú)窮多個(gè))最小值點(diǎn),這時(shí)找到其中一個(gè)最小值點(diǎn)就夠了。在實(shí)際應(yīng)用中,目標(biāo)函數(shù)經(jīng)常具有一個(gè)全局最優(yōu)解,多個(gè)局部最優(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.無(wú)約束優(yōu)化問(wèn)題形式

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

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

Rn

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

時(shí),上述無(wú)約束優(yōu)化問(wèn)題成為完全無(wú)約束優(yōu)化問(wèn)題。

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

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

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

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

例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ù),使用遺傳算法對(duì)其求解,具體設(shè)置如下:

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

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

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

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

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

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

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

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

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

②交叉概率pc=0.8;

③變異概率pm=0.03;

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

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

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

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

其中,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ù)與約束條件分開(kāi)處理法。

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

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

③行為記憶法;

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

(2)混合方式處理法。

①拉格朗日乘子法;

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

③模糊邏輯方法;

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

⑤文化算法。

2.9.3罰函數(shù)

1.罰函數(shù)介紹

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

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

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

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

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

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

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

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

4.罰函數(shù)分類(lèi)

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

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

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

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

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

5.懲罰項(xiàng)的理解

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

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

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

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

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

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

②約束違反的總量;

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

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

6.三種懲罰方式

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

①對(duì)于所有的非可行解采用固定的懲罰項(xiàng);

②對(duì)每個(gè)違反的約束添加一個(gè)懲罰值C。

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

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

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

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

1.GA求解約束優(yōu)化問(wèn)題的過(guò)程

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

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

2.應(yīng)用GA求解約束優(yōu)化問(wèn)題的實(shí)例

例2.9.6約束優(yōu)化實(shí)例1。

采用遺傳算法求解該問(wèn)題時(shí),將遺傳算法的參數(shù)選擇如下:

(1)種群規(guī)模popsize=400;

(2)交叉概率pc=0.85;

(3)變異概率pm=0.02。

GRG與GA方法求解該問(wèn)題的結(jié)果如表2-2所示。

例2.9.7約束優(yōu)化實(shí)例2。

該問(wèn)題由Himmelblau首次提出,之后Homaifar、Qi和Lai提出采用遺傳算法來(lái)求解該問(wèn)題,其中遺傳算法的參數(shù)設(shè)置如下:

(1)種群規(guī)模popsize=400;

(2)交叉概率pc=0.8;

(3)變異概率pm=0.088。

同例2.9.6中的方式,在這里也采用GRG與GA求解該問(wèn)題,得到的結(jié)果如表2-3所示。

2.9.5隨機(jī)優(yōu)化問(wèn)題

隨機(jī)優(yōu)化問(wèn)題是研究約束條件中的系數(shù)和目標(biāo)函數(shù)中的參數(shù)均為隨機(jī)變量時(shí)的規(guī)劃問(wèn)題,用于研究具有不確定性的決策問(wèn)題。隨機(jī)優(yōu)化的中心問(wèn)題是選擇參數(shù),使收益的數(shù)學(xué)

期望達(dá)到最大,或使成本的數(shù)學(xué)期望達(dá)到極小。

例2.9.8隨機(jī)優(yōu)化問(wèn)題

一個(gè)賣(mài)報(bào)人每天早上都會(huì)在報(bào)社以單價(jià)c購(gòu)買(mǎi)x張報(bào)紙,然后他以銷(xiāo)售價(jià)r盡可能地賣(mài)出更多的報(bào)紙,而對(duì)于沒(méi)有賣(mài)出的報(bào)紙也可以以回收價(jià)s退給報(bào)社,其中s<c,那么賣(mài)報(bào)人每天賣(mài)出多少報(bào)紙才能使獲得的利潤(rùn)最大?

為了更好地求解該問(wèn)題,我們先定義如下變量:

c:購(gòu)買(mǎi)價(jià)格,r:銷(xiāo)售價(jià)格,s:回收價(jià)格,x:購(gòu)買(mǎi)數(shù)量,ξ:市場(chǎng)需求;則銷(xiāo)售報(bào)紙獲得的利潤(rùn)可以表述如下:

若假定需求分布為離散分布,且具有如下形式:

從而期望獲得的利潤(rùn)為

相對(duì)地,其相應(yīng)的損失為

1.隨機(jī)優(yōu)化模型

2.蒙特卡羅仿真

3.蒙特卡羅仿真過(guò)程

4.遺傳算法求解隨機(jī)優(yōu)化問(wèn)題

Gen、Liu和Ida為下述問(wèn)題提出了一種遺傳算法的解決方法。

2.9.6非線性目標(biāo)規(guī)劃問(wèn)題

目標(biāo)規(guī)劃是解決多目標(biāo)優(yōu)化問(wèn)題的有力工具之一。目標(biāo)規(guī)劃問(wèn)題的主要思想如下:

(1)為每個(gè)目標(biāo)建立特定數(shù)量的目標(biāo);

(2)為每個(gè)目標(biāo)制定目標(biāo)函數(shù);

(3)尋找一種解,這種解能最大限度地減少這些目標(biāo)函數(shù)與各自目標(biāo)的偏差(加權(quán))之和。

1.非線性目標(biāo)規(guī)劃問(wèn)題一般形式

非線性目標(biāo)規(guī)劃問(wèn)題一般具有如下形式:

目標(biāo)函數(shù)符號(hào)解釋如下:

2.遺傳算法用于求解非線性目標(biāo)規(guī)劃問(wèn)題

遺傳算法解決非線性規(guī)劃問(wèn)題的優(yōu)勢(shì)主要體現(xiàn)在以下兩個(gè)方面:

①遺傳算法是問(wèn)題獨(dú)立的概率算法,可以處理任何類(lèi)型的目標(biāo)函數(shù)和任何約束。

②由于遺傳算法的進(jìn)化性質(zhì),它通過(guò)保持一定數(shù)量的有潛力的解,從而在復(fù)雜空間中執(zhí)行多方向和穩(wěn)健的搜索。

下面介紹應(yīng)用遺傳算法處理非線性目標(biāo)規(guī)劃問(wèn)題的一般步驟。

(1)編碼。

(2)初始化。

(3)評(píng)價(jià)函數(shù)。

評(píng)價(jià)函數(shù)的計(jì)算主要有以下幾個(gè)步驟:

(4)交叉和變異。

2.9.7區(qū)間規(guī)劃問(wèn)題

1.區(qū)間規(guī)劃問(wèn)題介紹

一個(gè)區(qū)間可以定義為一個(gè)有序?qū)崝?shù)對(duì):

其中,aL和aR分別為區(qū)間A的左邊界和右邊界。

區(qū)間也可以定義為如下的形式:

其中,aC

和aW分別為區(qū)間A的中心和半寬度。

它們按照如下的方式來(lái)計(jì)算:

為了有一個(gè)直觀的認(rèn)識(shí),圖2-38給出了區(qū)間的示意圖。圖2-38區(qū)間示意圖

2.區(qū)間不等式

考慮如下具有區(qū)間系數(shù)的約束問(wèn)題:

如何確定約束的可行域是區(qū)間規(guī)劃的一個(gè)基本問(wèn)題。在過(guò)去的幾年,已經(jīng)有人提出了可行域的幾種定義。Ishibuchi和Tanaka基于兩個(gè)區(qū)間不等式保真程度的概念給出了可行域的一種定義,其中不等式保真程度如圖2-39所示。

圖2-39不等式保真程度圖示

定義2.9.3對(duì)于一個(gè)區(qū)間A和一個(gè)實(shí)數(shù)x,不等式A≤x保真程度定義如下:

定義2.9.4對(duì)于區(qū)間A和B,不等式A≤B保真程度由以下公式給出:

理論2.9.1對(duì)于一個(gè)給定的不等式保真程度q,區(qū)間不等式約束可以等價(jià)轉(zhuǎn)換為如下清晰的不等式約束:

3.區(qū)間順序關(guān)系

區(qū)間順序關(guān)系由Okada,S.和M.Gen提出。下面以一個(gè)區(qū)間規(guī)劃問(wèn)題來(lái)對(duì)區(qū)間順序關(guān)系作出解釋,問(wèn)題描述如下:

其中,S是x的可行域,Cj

是一個(gè)表示來(lái)自xj的不確定單位利潤(rùn)的區(qū)間系數(shù)。對(duì)于一個(gè)給定的x,總的利潤(rùn)Z(x)是一個(gè)區(qū)間。我們需要基于此區(qū)間利潤(rùn)做一個(gè)決策。

4.區(qū)間規(guī)劃問(wèn)題的轉(zhuǎn)換

現(xiàn)在考慮如下的非線性區(qū)間規(guī)劃問(wèn)題:

其中,目標(biāo)函數(shù)是一個(gè)乘積的形式。

理論2.9.3對(duì)于給定的順序≤CW和兩個(gè)正的區(qū)間A和B,如下的狀態(tài)保持是真的:

推論2.9.1對(duì)于上述提到的非線性區(qū)間規(guī)劃問(wèn)題,它等價(jià)于如下的線性區(qū)間規(guī)劃問(wèn)題:

讓我們考慮如下的最大化區(qū)間規(guī)劃問(wèn)題:

上述問(wèn)題可以轉(zhuǎn)換為如下問(wèn)題:

5.區(qū)間規(guī)劃問(wèn)題的Pareto解

6.區(qū)間規(guī)劃問(wèn)題實(shí)例圖2-40數(shù)值例子的Pareto解

2.10基于進(jìn)化計(jì)算的組合優(yōu)化問(wèn)題

2.10.1組合優(yōu)化問(wèn)題的基本概念組合優(yōu)化問(wèn)題一般是指在一個(gè)有限的集合中尋找最優(yōu)解的一類(lèi)問(wèn)題。在多數(shù)組合優(yōu)化問(wèn)題中,枚舉與窮舉搜索是不可行的,該問(wèn)題解的集合是離散的或者可以簡(jiǎn)化到離散,目標(biāo)就是尋求問(wèn)題的最優(yōu)解。常見(jiàn)的組合優(yōu)化問(wèn)題有背包問(wèn)題、二次分配問(wèn)題、最小生成樹(shù)問(wèn)題、集合覆蓋問(wèn)題、一維裝箱問(wèn)題和TSP問(wèn)題等。

2.10.2-背包問(wèn)題

背包問(wèn)題歷史悠久,已引起了理論研究人員和實(shí)際工作者的廣泛關(guān)注。由于該問(wèn)題結(jié)構(gòu)簡(jiǎn)單,因此可以深入探索許多組合特性,并通過(guò)解決一系列背包子問(wèn)題來(lái)完成更復(fù)雜優(yōu)

化問(wèn)題的求解。這一問(wèn)題可用于許多工業(yè)建模場(chǎng)合的應(yīng)用,最典型的應(yīng)用包括資本運(yùn)算、貨物裝卸和存儲(chǔ)分配等。

下面介紹背包問(wèn)題中一些常見(jiàn)的符號(hào)。

1.二進(jìn)制表示法求解0－1背包問(wèn)題

二進(jìn)制字符串是0－1背包問(wèn)題解的很自然的表示方式,比如對(duì)于物品總數(shù)為7個(gè)的0－1背包問(wèn)題,決策變量取值如下:

x=[0101000]

它表示選出物品2和4并放入背包。物品的利潤(rùn)和重量如表2-4所示。

對(duì)于最大值問(wèn)題,罰函數(shù)可設(shè)計(jì)為圖2-41的式。圖2-41罰函數(shù)示意圖

其中,

下面給出應(yīng)用解碼方法求解0－1背包問(wèn)題的一個(gè)示例。

假設(shè)輸入數(shù)據(jù)如表2-5所示。

背包容量W=100。下面給出求解該背包問(wèn)題的具體過(guò)程。

假設(shè)給定的染色體如下:

此時(shí)按照下述步驟完成背包問(wèn)題求解。

(1)首先根據(jù)利潤(rùn)重量比將xj=1的物品按降序排列,排序后對(duì)應(yīng)的染色體如下:

其中,7號(hào)、2號(hào)和3號(hào)基因的cj/wj分別為2.0、1.2和0.33。

(2)使用第一擬合啟發(fā)式算法選擇物品,直到背包內(nèi)不能再放入物品。選擇過(guò)程如下:

首先選擇出7號(hào)基因,對(duì)于重量g(x)=30≤W,f(x)=60,符合要求;

其次,選擇出2號(hào)基因,此時(shí)g(x)=80≤W,f(x)=120,符合要求;

最后,再判斷3號(hào)基因,此時(shí)g(x)=110>W,f(x)=130,此時(shí)總重量超出背包最大容量,不再符合要求。

(3)從而符合背包容量要求的物品為7號(hào)和2號(hào)物體,此時(shí)總重量和相應(yīng)的利潤(rùn)為g(x)=80≤W,f(x)=120。

2.序列表示法求解01背包問(wèn)題

Hinterding,R提出采用序列表示法求解01背包問(wèn)題。對(duì)于含有n個(gè)物品的01背包問(wèn)題,一個(gè)染色體包含n個(gè)基因,在每個(gè)基因位上用一個(gè)明確的整數(shù)數(shù)字來(lái)表示相應(yīng)的物品,對(duì)于序列表示中物品的排列順序可以視為它們放入背包中的先后順序。此時(shí),對(duì)應(yīng)的適應(yīng)度函數(shù)為

下面給出應(yīng)用序列表示法求解01背包問(wèn)題的示例。

輸入數(shù)據(jù)如表2-6所示。

3.可變長(zhǎng)度表示法求解0－1背包問(wèn)題

可變長(zhǎng)度表示法屬于直接編碼方法,它不同于序列表示法,在該方法中,染色體中物品的排列順序沒(méi)有任何含義。由于所選物品數(shù)量是不固定的,因此染色體的編碼長(zhǎng)度也是不固定的。

下面仍采用表2-5中的數(shù)據(jù),之后給出三個(gè)可變長(zhǎng)度的染色體,并選出最優(yōu)解。

4.多選擇背包問(wèn)題

多選擇背包問(wèn)題由MMAkbar、EGManning、GCShoja、SKhan及AEMohr提出。該問(wèn)題是帶有互不相關(guān)的多選擇約束的背包問(wèn)題。具體地,多選擇背包問(wèn)題可描述如下:

給定一個(gè)承重有限的背包,并將待放入的物品分為互斥的類(lèi),每個(gè)類(lèi)中有若干不同的物品。問(wèn)題求解目標(biāo)就是從每個(gè)類(lèi)中選擇出一個(gè)物品,在總重量滿(mǎn)足承重約束的前提下,

使得費(fèi)用最小。

(2)交叉和變異。遺傳算子可以選擇均勻交叉算子和隨機(jī)擾動(dòng)變異算子。隨機(jī)擾動(dòng)變異是指,選擇的基因yi可以由集合Ni中的一個(gè)隨機(jī)整數(shù)來(lái)替代,交叉變異的運(yùn)算過(guò)程如圖

2-42所示。圖2-42-均勻交叉和隨機(jī)擾動(dòng)變異示意圖

2.10.3TSP問(wèn)題

旅行商(TSP)問(wèn)題是一類(lèi)受到廣泛研究的組合優(yōu)化問(wèn)題。TSP問(wèn)題描述很簡(jiǎn)單,即旅行商要訪問(wèn)n個(gè)城市,那他要以怎樣的訪問(wèn)順序來(lái)訪問(wèn)這n個(gè)城市才能使得行走路徑最短。

下面介紹TSP問(wèn)題中常用的符號(hào)。

對(duì)于含有4個(gè)城市的TSP問(wèn)題,若按照Z(yǔ)→X→W→Y的順序來(lái)訪問(wèn),我們將4個(gè)城市的訪問(wèn)順序反映在表2-7中。

TSP問(wèn)題一般可以表述為如下形式:

其中,

1.表示方式

(1)直接表示法。直接表示法是TSP問(wèn)題最自然的表示方式,在這種表示方式下城市按照它們被訪問(wèn)的順序列出。我們給出如下的染色體:

(2)隨機(jī)數(shù)表示法。隨機(jī)數(shù)表示法從(0,1)間選取隨機(jī)數(shù)來(lái)編碼一個(gè)解,之后將產(chǎn)生的若干隨機(jī)數(shù)從小到大排序,其排序順序就是相應(yīng)城市的訪問(wèn)順序。

具體地,我們給出如下染色體:

其中,染色體中基因的位置i就代表了城市i,將上述染色體中的隨機(jī)數(shù)按照從小到大排序后,可以得到城市的訪問(wèn)列表為6—1—3—7—8—4—9—2—5。

2.交叉算子

過(guò)去十年已經(jīng)提出了一些交叉算子用于序列表示,常見(jiàn)的交叉算子有部分映射交叉(PMX)、順序交叉(OX)、循環(huán)交叉(CX)、基于位置的交叉(PBX)和啟發(fā)式的交叉。

這些算子可以分為兩類(lèi):規(guī)范方法,其可以看作達(dá)特茅斯二進(jìn)制字符串的兩點(diǎn)或多點(diǎn)交叉到序列表示的擴(kuò)展;啟發(fā)式方法,其在交叉中的應(yīng)用旨在產(chǎn)生性能提升的子代。

PMX交叉算子運(yùn)算時(shí)主要涉及4個(gè)運(yùn)算步驟:

①?gòu)慕o定的染色體中隨機(jī)選取兩個(gè)位置。給定如下的兩個(gè)父代染色體,選取的交叉位置如下：

此時(shí)染色體的長(zhǎng)度為9,交叉位置有8個(gè),上圖選取的交叉位置為2和6。

②交換兩個(gè)子字符串。選取交叉位置后,交換兩個(gè)父代染色體交叉位置之間的子字符串,得到如下子代染色體:

此時(shí),兩個(gè)父代染色體位置2和6之間的子字符串交換后得到上述兩個(gè)子代染色體。

③產(chǎn)生映射關(guān)系。上述交叉操作產(chǎn)生的子代染色體并不是合法的,因此需要產(chǎn)生映射關(guān)系以使子代染色體合法化,具體如下:

我們由此可以得到如下的映射關(guān)系:

其中,基因1和3相互映射,2和5相互映射,9和4相互映射。

④根據(jù)映射關(guān)系使子代合法化。將交叉得到的子代染色體中未涉及交叉操作的基因按照映射關(guān)系進(jìn)行映射,從而得到合法的子代染色體,如下:

(2)順序交叉OX。

OX交叉算子運(yùn)算時(shí)主要涉及3個(gè)運(yùn)算步驟:

①?gòu)母复旧w中選擇一個(gè)子字符串。給定如下的兩個(gè)父代染色體:

選擇父代染色體1位置s和t之間的字符串,也就是選擇了子字符串3456。

(3)循環(huán)交叉CX。

CX交叉算子運(yùn)算時(shí)主要涉及3個(gè)運(yùn)算步驟:

①尋找父代個(gè)體之間的循環(huán)。給定如下的兩個(gè)父代染色體:

根據(jù)上面兩個(gè)染色體可找到如下的循環(huán)關(guān)系:

(4)基于位置的交叉PBX。

PBX交叉算子運(yùn)算時(shí)主要涉及3個(gè)運(yùn)算步驟:

①?gòu)母复旧wparent1中隨機(jī)選擇一些位置如下:

3.變異算子

現(xiàn)階段已經(jīng)提出一些用于序列表示的變異算子,常見(jiàn)的變異算子有相反變異(InversionMutation)、插入變異(InsertionMutation)、交換變異(SwaMutation)和啟發(fā)式變異(HeuristicOperators),下面分別介紹這些變異算子。

(1)相反變異(InversionMutation)。

相反變異主要涉及2個(gè)運(yùn)算步驟:

①隨機(jī)選取一個(gè)子字符串,如下:

(2)插入變異(InsertionMutation)。

(3)交換變異(SwapMutation)。

(4)啟發(fā)式變異(HeuristicMutation)。

②通過(guò)計(jì)算鄰域來(lái)產(chǎn)生子代。

在此例中,由于適應(yīng)值數(shù)值越小,表示當(dāng)前個(gè)體越好,因此選出的染色體為鄰域中第4條染色體。

4.遺傳算法用于求解TSP問(wèn)題

組合優(yōu)化問(wèn)題的特點(diǎn)是存在有限數(shù)量的可行解,并廣泛存在于日常生活中尤其是大量的工業(yè)設(shè)計(jì)中。

組合優(yōu)化最大的挑戰(zhàn)就是如何高效地處理組合爆炸的問(wèn)題,而解決這一問(wèn)題的一種有效方式就是使用遺傳算法。

2.11基于進(jìn)化計(jì)算的多目標(biāo)優(yōu)化問(wèn)題

2.11.1多目標(biāo)優(yōu)化的基本思想1.多目標(biāo)優(yōu)化問(wèn)題(MOP)所謂優(yōu)化就是在某種規(guī)則下,求解個(gè)體性能最優(yōu)的一種解決方案。多目標(biāo)優(yōu)化問(wèn)題(MOP)存在于許多復(fù)雜的實(shí)際系統(tǒng)的設(shè)計(jì)、建模和規(guī)劃中。圖2-43個(gè)體空間、決策空間與目標(biāo)空間關(guān)系示意圖

例2.11.1決策空間與目標(biāo)空間的映射關(guān)系有以下多目標(biāo)優(yōu)化問(wèn)題,根據(jù)決策空間可行域畫(huà)出目標(biāo)空間可行域。

決策空間與目標(biāo)空間可行域如圖2-44所示。圖2-44決策空間可行域與目