.⑵稱＞0〔為上的一維概率分布。從選擇算子的執(zhí)行過(guò)程,適應(yīng)值大的個(gè)體易被選擇,適應(yīng)值小的個(gè)體易被淘汰,這樣經(jīng)過(guò)不斷地選擇使適應(yīng)值大的個(gè)體不斷重復(fù)出現(xiàn),使一個(gè)種群可能變?yōu)辇R次種群。但是選擇算子只是在一個(gè)固定的種群中進(jìn)行選擇；選擇的結(jié)果不可能跑到種群之外。對(duì)于種群之外更好的個(gè)體是不可能被選擇得到的,選擇的結(jié)果依賴于初始種群。母體和母體空間:所謂母體即是一對(duì)個(gè)體〔X1,X2,其中Xi∈S<i=1,2>所有母體的全體稱為母體空間,即S2={<X1,X2>；X1,X2∈S}〔2.7雜交算子：雜交算子是母體空間到個(gè)體空間的映射,記作Ts:S2→S〔2.8<l>單點(diǎn)雜交算子：等概率的隨機(jī)確定一個(gè)基因位置作為雜交點(diǎn),再把一對(duì)母體兩個(gè)個(gè)體從雜交點(diǎn)分成前后兩個(gè)部分,交換兩個(gè)個(gè)體的后半部分得到兩個(gè)新個(gè)體,取第一個(gè)個(gè)體為雜交結(jié)果。<2>單點(diǎn)隨機(jī)雜交算子：等概率的隨機(jī)確定一個(gè)基因位置作為雜交點(diǎn),再把一對(duì)母體兩個(gè)個(gè)體從雜交點(diǎn)分為前后兩個(gè)部分,以概率Pc交換兩個(gè)個(gè)體的后半部分,得到兩個(gè)新個(gè)體,取第一個(gè)個(gè)體為雜交結(jié)果。稱Pc為雜交概率。如果確定兩個(gè)基因位置將一對(duì)母體兩個(gè)個(gè)體分成三部分,交換中間部分,稱為雙點(diǎn)雜交算子。同樣有雙點(diǎn)雜交與雙點(diǎn)隨機(jī)雜交之分。<3>均勻隨機(jī)雜交算子：獨(dú)立地以概率Pc把母體的第一個(gè)個(gè)體的相應(yīng)的分量交換為第二母體的相應(yīng)分量,從而得到雜交結(jié)果。變異算子：變異算子是個(gè)體空間到個(gè)體空間的隨機(jī)映射,其作用方式為獨(dú)立地以概率Pm改變個(gè)體分量取值。Pm稱作變異概率?；谏飳W(xué)上的考慮,一般認(rèn)為雜交是自然演化的主要機(jī)制,變異為自然演化的背景,它們分別承擔(dān)遺傳與變異兩種功能。因此在具體應(yīng)用過(guò)程中,雜交概率一般取值較大,在0.6與0.9之間。而變異概率取值較小、一般在0.001與0.01之間。遺傳算法的基本概念構(gòu)成了遺傳算法的基本模型。對(duì)于一個(gè)實(shí)際問(wèn)題,首先是將問(wèn)題轉(zhuǎn)化為遺傳算法的基本概念。一旦用遺傳算法的基本概念來(lái)表達(dá)實(shí)際問(wèn)題,問(wèn)題的求解過(guò)程就不再依賴于實(shí)際問(wèn)題本身。2.2遺傳算法的基本原理遺傳算法類似于自然進(jìn)化,通過(guò)作用于染色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題。與自然界相似,遺傳算法對(duì)求解問(wèn)題的本身一無(wú)所知,它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià),并基于適應(yīng)值來(lái)選擇染色體,使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中,通過(guò)隨機(jī)方式產(chǎn)生若干個(gè)所求解問(wèn)題的數(shù)字編碼,即染色體,形成初始群體；通過(guò)適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià),淘汰低適應(yīng)度的個(gè)體,選擇高適應(yīng)度的個(gè)體參加遺傳操作,經(jīng)過(guò)遺傳操作后的個(gè)體集合形成下一代新的種群,從而對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。這就是遺傳算法的基本原理。下面是遺傳算法的基本思想：初始化群體；<2>計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值；<3>按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則,選擇將進(jìn)入下一代的個(gè)體；<4>按概率Pc進(jìn)行交叉操作；<5>按概率Pc進(jìn)行突變操作；<6>沒(méi)有滿足某種停止條件,則轉(zhuǎn)第<2>步,否則進(jìn)入<7>；<7>輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。程序的停止條件最簡(jiǎn)單的有如下二種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒(méi)有改進(jìn)時(shí)停止。應(yīng)用遺傳算法求解應(yīng)用問(wèn)題時(shí),需要根據(jù)應(yīng)用問(wèn)題構(gòu)造遺傳算法,遺傳算法中的各種選擇算子、交叉算子、變異算子,遺傳算法的構(gòu)造過(guò)程如圖2.1所示。實(shí)際應(yīng)用中的優(yōu)化問(wèn)題都含有一定的約束條件,在遺傳算法中處理約束條件常用的方法有搜索空間限定法、可行解變換法、罰函數(shù)法。搜索空間限定法的思想是在搜索空間中將個(gè)體與解空間中可行解之間建立一一對(duì)應(yīng)的關(guān)系；可行解變換法的思想是在由個(gè)體基因型到個(gè)體表現(xiàn)型的變換中增加滿足約束條件的處理過(guò)程；罰函數(shù)法的思想是對(duì)解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體計(jì)算其適應(yīng)度時(shí)處以一個(gè)罰函數(shù)降低適應(yīng)度,減少此個(gè)體遺傳到下一代的機(jī)會(huì)。另外,在遺傳算法的研究和應(yīng)用中,開(kāi)發(fā)出了多種高級(jí)實(shí)現(xiàn)技術(shù),利用這些技術(shù)可以有效的利用遺傳算法解決廣泛的應(yīng)用問(wèn)題。最優(yōu)化問(wèn)題描述最優(yōu)化問(wèn)題描述解空間確定決策變量、優(yōu)化條件建立優(yōu)化模型第一步第二步確定決策變量、優(yōu)化條件建立優(yōu)化模型目標(biāo)函數(shù)f〔X目標(biāo)函數(shù)f〔X個(gè)體表現(xiàn)型X個(gè)體表現(xiàn)型X確定適應(yīng)度轉(zhuǎn)換規(guī)則解碼方法編碼方法確定適應(yīng)度轉(zhuǎn)換規(guī)則解碼方法編碼方法適應(yīng)度F〔X個(gè)體基因型X第三步第四步第五步適應(yīng)度F〔X個(gè)體基因型X設(shè)計(jì)遺傳算子第六步設(shè)計(jì)遺傳算子確定運(yùn)行參數(shù)確定運(yùn)行參數(shù)第七步遺傳算法遺傳算法遺傳空間圖2.1遺傳算法的構(gòu)造過(guò)程2.3遺傳算法的特征為解決各種優(yōu)化計(jì)算問(wèn)題,人們提出了各種各樣的優(yōu)化算法,如單純形法、梯度法、動(dòng)態(tài)規(guī)劃法、分枝定界法等。這些優(yōu)化算法各有各的長(zhǎng)處,各有各的適用范圍,也各有各的限制。搜索算法的共同特征為：〔1首先組成一組候選解；〔2依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度；〔3根據(jù)適應(yīng)度保留某些候選解,放棄其他候選解；〔4對(duì)保留的候選解進(jìn)行某些操作,生成新的候選解。在遺傳算法中,上述幾個(gè)特征以一種特殊的方式組合在一起：基于染色體群的并行搜索,帶有猜測(cè)性質(zhì)的選擇操作、交叉操作和變異操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開(kāi)來(lái)。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的搜索算法,與其他一些優(yōu)化算法相比,它主要有下述幾個(gè)特點(diǎn)：遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來(lái)進(jìn)行優(yōu)化計(jì)算,但遺傳算法不是直接以決策變量的值而是以決策變量的某種形式的編碼為運(yùn)算對(duì)象。這種對(duì)決策變量的編碼處理方式,使得我們?cè)趦?yōu)化計(jì)算過(guò)程中可以借鑒生物學(xué)中染色體和基因等概念,可以模仿自然界中生物的遺傳和進(jìn)化等機(jī)理,也使得我們可以方便地應(yīng)用遺傳操作算子。特別是對(duì)一些無(wú)數(shù)值概念或很難有數(shù)值概念,而只有代碼概念的優(yōu)化間題,編碼處理方式更顯示出了其獨(dú)持的優(yōu)越性。遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值,而且往往需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)位變換來(lái)的適應(yīng)度函數(shù)值,就可確定進(jìn)一步的搜索方向和搜索范圍,無(wú)商月標(biāo)函數(shù)的導(dǎo)數(shù)伍等其他一些輔助信．這個(gè)特性對(duì)很多目標(biāo)函數(shù)是無(wú)法或很難求導(dǎo)數(shù)的函數(shù),或?qū)?shù)不存在的函數(shù)的優(yōu)化阿題,以及組合優(yōu)化問(wèn)題等,應(yīng)用遺傳算法時(shí)就顯得比較方便,它避開(kāi)函數(shù)求導(dǎo)這個(gè)障礙。再者,直接利月目標(biāo)函數(shù)值或個(gè)體適應(yīng)度,也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中,從而提高搜索效率。遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化算法往往是從解中的一個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的迭代搜索過(guò)程。單個(gè)搜索點(diǎn)所提供的搜索信息畢竟不多,所以搜索效率不高,有時(shí)甚至使搜索過(guò)程陷于局部最優(yōu)解而停滯不前。遺傳算法從由很多個(gè)體所組成的一個(gè)初始群體開(kāi)始最優(yōu)解的搜索過(guò)程．而不是從一個(gè)單一的個(gè)體開(kāi)始搜索。對(duì)這個(gè)群體所進(jìn)行的選擇、雜交、變異等運(yùn)算,產(chǎn)生出的仍是新一代的群體,在這之中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點(diǎn),所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn),這是遺傳算法所特有的一種隱含特性。遺傳算法使用概率搜索技術(shù)。很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法,一個(gè)搜索點(diǎn)到另一個(gè)搜索點(diǎn)的轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系,這種確定性往往也有可能使得搜索遠(yuǎn)達(dá)不到最優(yōu)點(diǎn),從而也限制了算法的應(yīng)用范圍。而遺傳算法屬于一種自適應(yīng)概率搜索技術(shù),其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的,從而增加了其搜索過(guò)程的靈活性。雖然這概率特性也會(huì)使群體中產(chǎn)生一些適應(yīng)度不高的個(gè)體,但隨著進(jìn)化過(guò)程的進(jìn)行,新的群體中總更多地產(chǎn)生出許多優(yōu)良的個(gè)體,實(shí)踐和理論都已證明了在一定條件下遺傳算法總是以概率收斂問(wèn)題為最優(yōu)解。當(dāng)然,交叉概率和變異概率等參數(shù)也會(huì)影響算法的搜索效果和搜索效率,所以如何選擇遺傳算法的參數(shù)在其應(yīng)用中是一個(gè)比較重要的問(wèn)題。另一方面,與其他一些算法相比,遺傳算法的魯棒性又會(huì)使得參數(shù)對(duì)其搜索效果的影響會(huì)盡可能地低。遺傳算法作為一種快捷、簡(jiǎn)便、容錯(cuò)性強(qiáng)的算法,在各類結(jié)構(gòu)對(duì)象的優(yōu)化過(guò)程中顯示出明顯的優(yōu)勢(shì)。搜索過(guò)程是從一組解迭代到另一組解,采用同時(shí)處理群體中多個(gè)個(gè)體的方法,降低了陷入局部最優(yōu)解的可能性,并易于并行化。采用概率的變遷規(guī)則來(lái)指導(dǎo)搜索方向,而不采用確定性搜索規(guī)則。對(duì)搜索空間沒(méi)有任何特殊要求〔如連通性、凸性等,只利用適應(yīng)性信息,不需要導(dǎo)數(shù)等其它輔助信息,適應(yīng)范圍更廣。第三章遺傳算法的基本實(shí)現(xiàn)技術(shù)3.1編碼編碼方法遺傳算法主要是通過(guò)遺傳操作對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加結(jié)構(gòu)重組處理,從而不斷地搜索出群體中個(gè)體間的結(jié)構(gòu)相似性,形成并優(yōu)化積木塊以逐漸逼近最優(yōu)解,因此,遺傳算法不能直接處理問(wèn)題空間的參數(shù),必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。該轉(zhuǎn)換操作就稱為編碼。編碼過(guò)程是問(wèn)題空間向遺傳算法空間的映射過(guò)程,所謂問(wèn)題空間是指由遺傳算法表現(xiàn)個(gè)體<有效的候選解>集合所組成的空間；而遺傳算法空間是指由基因型個(gè)體所組成的空間。編碼過(guò)程是遺傳算法的基石,編碼方法除了決定了個(gè)體的染色體排列形式之外,它還決定了個(gè)體從遺傳算法空間的基因型變換到問(wèn)題空間的表現(xiàn)型時(shí)的解碼方法；編碼方法也影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法。由此可見(jiàn),編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化運(yùn)算的效率。一個(gè)好的編碼方法,有可能會(huì)使得交叉運(yùn)算、變異運(yùn)算等遺傳操作可以簡(jiǎn)單地實(shí)現(xiàn)和執(zhí)行。而一個(gè)差的編碼方法,卻有可能會(huì)使得交叉運(yùn)算、變異運(yùn)算等遺傳操作難以實(shí)現(xiàn),也有可能會(huì)產(chǎn)生很多在可行解集合內(nèi)無(wú)對(duì)應(yīng)可行解的個(gè)體,這些個(gè)體經(jīng)解碼處理后所表示的解稱為無(wú)效解。因此Goldberg提出了三條編碼評(píng)估規(guī)范：〔1完備性<Completeness>：?jiǎn)栴}空間中的所有點(diǎn)都能作為GA空間中的點(diǎn)<染色體>表現(xiàn)?！?健全性<Soundness>：GA空間中的染色體能對(duì)應(yīng)所有問(wèn)題空間中的候選解?！?非冗余性<Nonredundancy>：染色體和候選解一一對(duì)應(yīng)。大多數(shù)的應(yīng)用中,二進(jìn)制編碼用得最多,其次是十進(jìn)制編碼。SGA采用二進(jìn)制0,l編碼方式,將問(wèn)題的一個(gè)解表示成一個(gè)串長(zhǎng)為L(zhǎng)的二進(jìn)制串,作為一個(gè)個(gè)體,L稱為鏈長(zhǎng)。編碼表示1.二進(jìn)制編碼二進(jìn)制碼編碼即是將原問(wèn)題的解映射成為0,1組成的位串,然后在位串空間上進(jìn)行遺傳操作。結(jié)果再通過(guò)解碼過(guò)程還原成其解空間的解,然后再進(jìn)行適應(yīng)度的計(jì)算。使用二進(jìn)制編碼方法能表達(dá)的模式數(shù)最多。除此之外,該方法還具有如下優(yōu)點(diǎn)：〔1簡(jiǎn)單易行；〔2符合最小字符集編碼原則；〔3便于模式定理對(duì)算法進(jìn)行理論分析。但在求解連續(xù)化優(yōu)化問(wèn)題時(shí),它存在以下缺點(diǎn)：〔1相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離,例如15和16的二進(jìn)制表示為01111和10000。因此,算法要從15改進(jìn)到16則必須改變所有的位。這種缺陷將降低遺傳算子的搜索效率。二進(jìn)制編碼的這一缺點(diǎn)被稱為Hamming懸崖?！?二進(jìn)制編碼時(shí),一般要先給出求解的精度以確定串長(zhǎng)。而一旦精度確定后,就很難在算法執(zhí)行過(guò)程中進(jìn)行調(diào)整。從而使算法缺乏微調(diào)的功能。若在算法一開(kāi)始就選取較高的精度,那么位串就很長(zhǎng),這樣也會(huì)降低算法的效率?！?在求解高維優(yōu)化問(wèn)題時(shí),二進(jìn)制編碼位串將非常長(zhǎng),從而使得算法的搜索效率很低。2.格雷〔Gray編碼格雷碼即是將二進(jìn)制編碼通過(guò)一個(gè)變換而得到的編碼,其目的是克服二進(jìn)制編碼中Hamming懸崖的缺點(diǎn)。3.實(shí)數(shù)編碼為了克服二進(jìn)制編碼的缺點(diǎn),對(duì)于問(wèn)題的變量是實(shí)向量的情形,可以直接采用十進(jìn)制進(jìn)行編碼。這樣,便可直接對(duì)解進(jìn)行遺傳操作,從而便于引入與問(wèn)題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力。對(duì)實(shí)數(shù)編碼的情形,通常需要針對(duì)十進(jìn)制編碼的特性,引入其他一些遺傳算子。實(shí)驗(yàn)證明,對(duì)于大部分?jǐn)?shù)值優(yōu)化問(wèn)題,通過(guò)一些專門(mén)設(shè)計(jì)的遺傳算子的引入,采用實(shí)數(shù)編碼比采用二進(jìn)制編碼是算法的平均效率要高。4.有序串編碼對(duì)于很多組合優(yōu)化問(wèn)題,目標(biāo)函數(shù)的值不僅與表示解的字符串中的各字符的值有關(guān),而且與其所在字符串的位置有關(guān)。這樣的問(wèn)題稱為排序問(wèn)題。若目標(biāo)函數(shù)的值只與表示解的字符串中各字符的位置有關(guān)而與其具體的字符值無(wú)關(guān),則稱為純排序問(wèn)題。如求解旅行商問(wèn)題就是用的第一種編碼方式。用遺傳算法求解有序問(wèn)題時(shí),傳統(tǒng)的遺傳操作將可能產(chǎn)生非法的后代。因此,對(duì)這類問(wèn)題需要針對(duì)具體問(wèn)題專門(mén)設(shè)計(jì)有效且能保證后代合法的遺傳算子。這類編碼方案在組合優(yōu)化問(wèn)題中使用較多。5.動(dòng)態(tài)編碼動(dòng)態(tài)編碼是當(dāng)算法收斂到某局部極值時(shí)增加搜索的精度。增加精度的辦法是在保持串長(zhǎng)不變的前提下減小搜索區(qū)域。用遺傳算法求解有序問(wèn)題時(shí),傳統(tǒng)的遺傳操作將可能產(chǎn)生非法的后代。因此,對(duì)于這類問(wèn)題需要針對(duì)具體問(wèn)題專門(mén)設(shè)計(jì)有效且能保證后代合法的遺傳算子。3.2適應(yīng)度函數(shù)3.2.1基本的適應(yīng)度函數(shù)適應(yīng)度函數(shù)<FitnessFunction>的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解,因?yàn)檫z傳算法在進(jìn)化搜索中基本不利用外部信息,僅以適應(yīng)度函數(shù)為依據(jù),利用種群中每個(gè)個(gè)體的適應(yīng)度來(lái)進(jìn)行搜索。因?yàn)檫m應(yīng)度函數(shù)的復(fù)雜度是遺傳算法復(fù)雜度的主要組成部分,所以適應(yīng)度函數(shù)的設(shè)計(jì)應(yīng)盡可能簡(jiǎn)單,使計(jì)算的時(shí)間復(fù)雜度最小。遺傳算法評(píng)價(jià)一個(gè)解的好壞不是取決于它的解的結(jié)構(gòu),而是取決于相應(yīng)于該解的適應(yīng)度值,這正體現(xiàn)了遺傳算法"優(yōu)勝劣汰"的特點(diǎn)。遺傳算法不需要適應(yīng)度函數(shù)滿足連續(xù)可微等條件,唯一要求是針對(duì)輸入可計(jì)算出能加以比較的非負(fù)結(jié)果。這一特點(diǎn)使得遺傳算法具有廣泛的適用性。在實(shí)際問(wèn)題中,適應(yīng)度函數(shù)與問(wèn)題的目標(biāo)函數(shù)是不完全一致的,如有的問(wèn)題的目標(biāo)是要求的最小值<費(fèi)用問(wèn)題>,而有的問(wèn)題的目標(biāo)是要求得最大值<利潤(rùn)函數(shù)>。因此在不少場(chǎng)合,需要將目標(biāo)函數(shù)映射成求最大值形式而且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。在函數(shù)優(yōu)化中,適應(yīng)度函數(shù)可由目標(biāo)函數(shù)變換得到,可以有以下三種處理情況：〔1直接以待求解的目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù),即：若目標(biāo)函數(shù)為最大化問(wèn)題若目標(biāo)函數(shù)為最小化問(wèn)題〔2若目標(biāo)函數(shù)為最小問(wèn)題,則：〔3.1其中系數(shù)Cmax存在多種選擇方法,它可以是一個(gè)合適的輸入值,也可以采用迄今為止進(jìn)化過(guò)程中g(shù)<x>的最大值,但Cmax最好與群體無(wú)關(guān)。若目標(biāo)函數(shù)為最大問(wèn)題,則：〔3.2其中系數(shù)Cmin存在多種選擇方法,它可以是一個(gè)合適的輸入值,也可以采用迄今為止進(jìn)化過(guò)程中g(shù)<x>的最小值,但Cmin最好與群體無(wú)關(guān)。〔3若目標(biāo)函數(shù)為最小問(wèn)題,則：〔3.3若目標(biāo)函數(shù)為最大問(wèn)題,則：〔3.4上兩式C為目標(biāo)函數(shù)界限的保守估計(jì)值。適應(yīng)度函數(shù)對(duì)GA的收斂速度和結(jié)果影響很大。如果過(guò)分強(qiáng)調(diào)當(dāng)前的較優(yōu)點(diǎn),就可能很快降低種群的多樣性,造成不成熟收斂；如果對(duì)當(dāng)前較優(yōu)點(diǎn)強(qiáng)調(diào)不夠,算法就很容易丟失已經(jīng)找到的較優(yōu)點(diǎn)信息,從而不能在合理的時(shí)間內(nèi)收斂到較好的點(diǎn)。因此在具體的應(yīng)用中,適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問(wèn)題本身的要求而定。目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù),就是將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)。當(dāng)把一個(gè)最小化問(wèn)題轉(zhuǎn)化為最大化問(wèn)題,可采用以下方法進(jìn)行轉(zhuǎn)換：<3.5>有多種方式來(lái)選擇Cmax。Cmax可以是一個(gè)合適的輸入值,也可采用迄今為止進(jìn)化過(guò)程中g(shù)<x>的最大值,或g<x>的最大值。如果g<x>非負(fù),也可采用轉(zhuǎn)換f<x>=1/g<x>當(dāng)待求解問(wèn)題是求g<x>的最大值時(shí),適應(yīng)度函數(shù)的非負(fù)性可用如下變換得到保證<3.6>Cmin可以是合適的輸入值,或是當(dāng)前一代或前k代中g(shù)<x>的最小值,或g<x>的最小值。適應(yīng)度函數(shù)的調(diào)整應(yīng)用遺傳算法時(shí)〔尤其用它處理小規(guī)模群體時(shí)常常會(huì)出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。在進(jìn)化的初期,通常會(huì)出現(xiàn)一些異常的個(gè)體,若按照輪盤(pán)賭選擇策略,這些異常個(gè)體有可能在群體中占據(jù)很大的比例,這是我們不希望出現(xiàn)的現(xiàn)象,因?yàn)檫@樣可能導(dǎo)致未成熟收斂現(xiàn)象。這是因?yàn)?這些異常個(gè)體競(jìng)爭(zhēng)力太突出,因而會(huì)控制選擇過(guò)程,從而影響算法的全局優(yōu)化性能。對(duì)于未成熟收斂現(xiàn)象,設(shè)法降低某些異常個(gè)體的競(jìng)爭(zhēng)力,這可以通過(guò)縮小相應(yīng)的適應(yīng)度函數(shù)值來(lái)實(shí)現(xiàn)。有時(shí)也需要擴(kuò)大相應(yīng)的適應(yīng)度函數(shù)值。這種適應(yīng)度的縮放稱作適應(yīng)度調(diào)整。目前,調(diào)整方式主要有以下幾種。1.線性調(diào)整設(shè)原適應(yīng)度函數(shù)為?<>,調(diào)整后的適應(yīng)度函數(shù)為,則線性調(diào)整可采用<3.7>式中系數(shù)a和b滿足：原適應(yīng)度平均值要等于調(diào)整后的適應(yīng)度平均值,調(diào)整后適應(yīng)度函數(shù)的最大值要等于原適應(yīng)度函數(shù)平均值的所指定倍數(shù)。即<3.8>其中C是為得到所期待的最優(yōu)個(gè)體的復(fù)制數(shù)。實(shí)驗(yàn)表明,對(duì)于一個(gè)不太大的群體而言,C可在1.2～2.0范圍內(nèi)取值。2.冪調(diào)整該調(diào)整方式可定義為：<3.9>式中指數(shù)k與待求解問(wèn)題有關(guān),而且在算法過(guò)程中可按需要做修正。該調(diào)整方式由Gillies提出,他曾在機(jī)器視覺(jué)實(shí)驗(yàn)中采用了該方法,當(dāng)時(shí),他取=1.005。3.3選擇算子從群體中選擇優(yōu)勝的個(gè)體、淘汰劣質(zhì)個(gè)體的操作叫選擇。在生物的遺傳和自然進(jìn)化過(guò)程中,對(duì)生存環(huán)境適應(yīng)度較高的物種將有更多的機(jī)會(huì)遺傳到下一代,而對(duì)生存環(huán)境適應(yīng)程度較低的物種遺傳到下一代的機(jī)會(huì)就相對(duì)較少。模仿這個(gè)過(guò)程,遺傳算法使用選擇算子對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰。選擇運(yùn)算<SelectionOperator或稱為復(fù)制reproduction運(yùn)算>把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。選擇的標(biāo)準(zhǔn)就是各個(gè)體的適應(yīng)度值大小,個(gè)體的適應(yīng)度值越高,它被選中的概率越大。目前遺傳算法中最常用的選擇算子是比例復(fù)制法。選擇的方法根據(jù)不同的問(wèn)題采用不同的方案。常見(jiàn)的方法有以下幾種：1.適應(yīng)度比例法<fitnessproportionalmodel>該方法又稱為賭輪法<RouletteWheel或蒙特卡洛伽onteCar.lo>模型,是目前最常用的選擇方法。SGA中的選擇算子采用的就是該策略。它是指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比,是一種有循環(huán)的隨機(jī)選擇。具休表達(dá)方法如下：<3.10>式中xi為種群中第i個(gè)染色體對(duì)應(yīng)的數(shù)字串,?<xi>是第i個(gè)染色體的適應(yīng)度值,是種群中所有染色體的適應(yīng)度值之和。用適應(yīng)度比例法進(jìn)行選擇時(shí),首先計(jì)算每個(gè)染色體的適應(yīng)度,然后按比例于各染色體適應(yīng)度的概率進(jìn)入交換〔匹配集的染色體,其具體步驟如下：〔1計(jì)算每個(gè)染色體的適應(yīng)度值?；〔2累加所有染色體的適應(yīng)度值,得最終累加值=〔3產(chǎn)生一個(gè)隨機(jī)數(shù),〔4選擇對(duì)應(yīng)的中間累加值滿足的染色體進(jìn)入交換集；〔5重復(fù)〔3,〔4,直到交換集中包含足夠多的染色體數(shù)字串為止。重復(fù)上述過(guò)程,直到交換集中包含足夠多的染色體為止。顯然,此法要求染色體的適應(yīng)度應(yīng)為正值。2.排序選擇法<Rank-basedmodel>排序選擇方法在計(jì)算除每個(gè)個(gè)體適應(yīng)度后,根據(jù)適應(yīng)度大小在群體中對(duì)個(gè)體排序,然后把事先設(shè)計(jì)好的概率表按序分配給個(gè)體,作為各自的選擇概率。所有個(gè)體按適應(yīng)度大小排序,因而選擇概率和適應(yīng)度無(wú)直接關(guān)系而僅與序號(hào)有關(guān)。這種方法的不足之處在于選擇概率和序號(hào)的關(guān)系需事先確定。此外,它和適應(yīng)度比例方法一樣都是基于概率的選擇,所以仍有統(tǒng)計(jì)誤差。3.最佳個(gè)體保存法<elitistmodel>該方法的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中,當(dāng)然,這樣做的前提是下一代中不存在該個(gè)體。采用這種選擇方法的優(yōu)點(diǎn)是,進(jìn)化過(guò)程中某一代的最優(yōu)解可不被交叉或變異操作破壞。但是,這也隱含了一種危機(jī),即局部最優(yōu)個(gè)體的遺傳基因會(huì)因急速增加,而使進(jìn)化有可能陷于局部解。也就是說(shuō),該方法的全局搜索能力差。它適合于單峰性質(zhì)的優(yōu)化問(wèn)題的空間搜索,而不適于多峰性質(zhì)的空間搜索。所以,該方法一般都與其他選擇方法結(jié)合使用。4.期望值法<expectedvaluemodel>在輪盤(pán)賭選擇方法中,當(dāng)個(gè)體數(shù)不太多時(shí),依據(jù)產(chǎn)生的隨機(jī)數(shù)有可能會(huì)出現(xiàn)不正確地反映個(gè)體適應(yīng)度的選擇。即存在統(tǒng)計(jì)誤差,也就是說(shuō),適應(yīng)度高的個(gè)體有可能被淘汰,適應(yīng)度低的個(gè)體也有可能被選擇。為了克服這種缺點(diǎn),期望值方法用了如下思想：〔1計(jì)算群體中每個(gè)個(gè)體在下一代生存的期望數(shù)目<3.11>〔2若某個(gè)個(gè)體被選中并要參與配對(duì)和交叉,則它在下一代中的生存的期望數(shù)目減去0.5；若不參與配對(duì)和交叉,則該個(gè)體的期望數(shù)目減1?！?在〔2的兩種情況中,若一個(gè)個(gè)體的期望值小于零,則該個(gè)體不參與選擇。5.競(jìng)爭(zhēng)法<tournamentselection>競(jìng)爭(zhēng)法的個(gè)體的選擇公式為：?m=max{?i,?j},即隨機(jī)地選取兩個(gè)個(gè)體,對(duì)其適應(yīng)值進(jìn)行比較,大的被選中,小的被自然淘汰；如果兩個(gè)個(gè)體的適應(yīng)值相同,則任意選取其中的一個(gè)。被選中的個(gè)體放入配對(duì)庫(kù)中。重復(fù)此過(guò)程,直至配對(duì)庫(kù)中包含N個(gè)個(gè)體為止。這種方法既保證了配對(duì)庫(kù)中的個(gè)體在解空間中有較好的分散性,同時(shí)又保證了加入配對(duì)庫(kù)中的個(gè)體具有較大的適應(yīng)值。6.窗口方法<windowingmethod>其方法是首先求出目前解群中適應(yīng)值最小的個(gè)體,令其適應(yīng)值為Q。讓解群中的每個(gè)個(gè)體的適應(yīng)值都減去Q后作為其適應(yīng)值,再用輪盤(pán)賭法形成配對(duì)庫(kù)。采用這種方法時(shí),個(gè)體入選配對(duì)庫(kù)的概率雖不與其適應(yīng)值直接成比例,但關(guān)系比較大,與解群中最大的個(gè)體與最小的個(gè)體的適應(yīng)值之差以及個(gè)體的分散程度有關(guān)。7.線性標(biāo)準(zhǔn)化方法<linearnormalizationmethod>首先,把目前解群中的個(gè)體按適應(yīng)值大小降序排列,令最大的適應(yīng)值為U。解群中的其它個(gè)體的適應(yīng)值以V線性遞減。再用輪盤(pán)賭法產(chǎn)生配對(duì)庫(kù)。V值越大,對(duì)解群中優(yōu)良個(gè)體的選擇壓力越大。以上講述的幾種選擇方式均以適應(yīng)度為基礎(chǔ)進(jìn)行選擇,這就可能在進(jìn)化過(guò)程中導(dǎo)致以下問(wèn)題：〔1在群體中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度值相當(dāng)高的個(gè)體時(shí),采用這類選擇機(jī)制就有可能導(dǎo)致這些個(gè)體在群體中迅速繁殖,經(jīng)過(guò)少數(shù)幾次迭代后就占滿了群體的位置,這樣GA的求解過(guò)程就結(jié)束了,也即收斂了。但這樣很有可能是收斂到局部最優(yōu)解,即遺傳算法的不成熟收斂,即"早熟"現(xiàn)象的出現(xiàn),這是因?yàn)樗阉鞯姆秶苡邢?。因而一般不希望有個(gè)別個(gè)體在GA運(yùn)算的最初幾次迭代時(shí)就在群體中占據(jù)主導(dǎo)地位?！?當(dāng)群體中個(gè)體適應(yīng)度彼此非常接近時(shí),這些個(gè)體進(jìn)入配對(duì)庫(kù)的機(jī)會(huì)相當(dāng),而且交叉后得到的新個(gè)體也不會(huì)有多大變化,這樣搜索過(guò)程就不能有效地進(jìn)行,這類選擇機(jī)制有可能趨向于純粹的隨機(jī)選擇,從而使進(jìn)化過(guò)程陷于停頓的狀態(tài),難以找到全局最優(yōu)解。針對(duì)上述問(wèn)題,可以采用以下幾種提高GA性能的選擇方法：穩(wěn)態(tài)繁殖<steadystatereproduction>：就是在迭代過(guò)程中用部分優(yōu)質(zhì)新個(gè)體<子代>來(lái)更新目前群體中部分舊個(gè)體<父代>后,來(lái)作為下一代群體。這樣一些優(yōu)質(zhì)父代個(gè)體在下一代群體中就得以保留。計(jì)算表明,這種方法也有助于改善GA的行為,但需合理地確定每次用多少子代個(gè)體來(lái)取代父代個(gè)體。沒(méi)有重串的穩(wěn)態(tài)繁殖<steadystatereproductionwithoutduplicates>：在形成新一代群體時(shí),使其中的個(gè)體均不重復(fù)。作法是：在將某個(gè)個(gè)體加入到新一代群體之前,先檢查該個(gè)體與群體中現(xiàn)有的個(gè)體是否重復(fù),如果重復(fù)就舍棄。這種作法會(huì)明顯改善GA的行為,因?yàn)槠湓龃罅藗€(gè)體在群體中的分布區(qū)域,但增加了計(jì)算時(shí)間。3.4交叉算子交叉<crossover>算子也稱重組<recombination>、配對(duì)算子<breeding>。在遺傳算法中,交叉是產(chǎn)生新個(gè)體的主要手段,它在遺傳算法中起著核心作用。它仿照生物學(xué)中雜交的原理,將兩個(gè)父代個(gè)體<染色體>的部分字符<基因>互相交換,由此產(chǎn)生新的個(gè)體。通過(guò)交叉,遺傳算法的搜索能力得以飛躍提高。設(shè)計(jì)交叉算子的要點(diǎn)是應(yīng)當(dāng)保證前一代中優(yōu)秀個(gè)體的性狀能在后一代新個(gè)體中盡可能得到遺傳和繼承。交叉算子作用于染色體,所以和編碼設(shè)計(jì)是相互聯(lián)系的,需要協(xié)調(diào)操作。常用的方法有:1.單點(diǎn)交叉<One-pointcrossover>單點(diǎn)交叉又叫簡(jiǎn)單交叉。具體操作是:在個(gè)體基因串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)。實(shí)行交叉時(shí),該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換,并生成兩個(gè)新個(gè)體。當(dāng)基因鏈碼的長(zhǎng)度為n時(shí),可能有n-1個(gè)交叉點(diǎn)位置。2.二點(diǎn)交叉<Two-pointcrossover>具體操作是隨機(jī)設(shè)定兩個(gè)交叉點(diǎn),互換兩個(gè)父代在這兩點(diǎn)間的基因串,分別生成兩個(gè)新個(gè)體,若染色體有L長(zhǎng),則有<<L-2><L-3>種交叉結(jié)果。單點(diǎn)交叉是常用的交叉算子。在實(shí)際應(yīng)用中,研究者往往以單點(diǎn)交又為出發(fā)點(diǎn)對(duì)其性能進(jìn)行研究,但很多情況下其它交叉方法的性能優(yōu)于單點(diǎn)交叉算子。交叉概率Pc的大小也直接影響著遺傳算法的性能,較大的交叉概率可增強(qiáng)遺傳算法開(kāi)辟新的搜索區(qū)域的能力,但高性能的模式遭到破壞的可能性增大；若交叉概率太低,遺傳算法搜索可能陷入遲鈍狀態(tài)。因而,設(shè)計(jì)合適的交叉概率是算法獲得良好性能的條件之一。一般建議的PC取值范圍是0.50.99之間。3.多點(diǎn)交叉<multi-pointcrossover>多點(diǎn)交叉時(shí)前述兩種交叉方法的推廣。多點(diǎn)交叉有時(shí)又被稱為廣義交叉。若用參數(shù)C表示交叉數(shù),則當(dāng)C=1時(shí),廣義交叉就是單點(diǎn)交叉。C=2,廣義交叉就是兩點(diǎn)交叉。一般來(lái)說(shuō),多點(diǎn)交叉不經(jīng)常被采用。這是因?yàn)楫?dāng)基因鏈碼的長(zhǎng)度n較小,或交叉點(diǎn)數(shù)C較大時(shí),即使這種模式的階和定義矩較小,具有優(yōu)良特性的模式也很容易被破壞。另外通常情況下,出于計(jì)算速度的考慮,基因鏈碼的長(zhǎng)度n不會(huì)很大。4.均勻交叉<uniformcrossover>均勻交叉則是依概率交換兩個(gè)父輩個(gè)體基因串的每一位。其過(guò)程是：先隨機(jī)地產(chǎn)生一個(gè)與父輩個(gè)體基因串具有同樣長(zhǎng)度的二進(jìn)制串,其中0表示不交換,1表示交換。這個(gè)二進(jìn)制串稱為交叉模板；然后根據(jù)模板對(duì)兩個(gè)父輩基因串進(jìn)行交叉,得到的兩個(gè)新基因串即為后代新個(gè)體。均勻交叉在交換位時(shí)并不考慮其所在位置,破壞模式的概率較大。但另一方面它能搜索到一些前面基于點(diǎn)的交叉方法無(wú)法搜索到的模式。交叉算子對(duì)遺傳算法的收斂性是有影響的。交叉算子并未提供算法向最優(yōu)解收斂的保證。模式定理只是考慮到選擇算子可以維持模式,而交叉算子和變異算子會(huì)破壞模式。并在此基礎(chǔ)上指出,低階、短定義距的模式可呈指數(shù)倍增長(zhǎng)。但它并沒(méi)有確認(rèn)這些呈指數(shù)增長(zhǎng)的模式一定向最優(yōu)解收斂。雖然交叉算子缺乏向最優(yōu)解的收斂保證,但這并不影響遺傳算法的實(shí)用性。有時(shí),許多具有向最優(yōu)解收斂的算法卻犧牲了它們的全局性和靈活性。因此,不少很難求解的優(yōu)化問(wèn)題,對(duì)于基于交叉的遺傳算法而言是簡(jiǎn)單可解的了。3.5變異算子變異算子的相關(guān)內(nèi)容變異算子主要模擬生物個(gè)體的隨機(jī)變異現(xiàn)象。對(duì)個(gè)體串的某些基因位的值進(jìn)行隨機(jī)改變,其作用是增強(qiáng)遺傳算法運(yùn)行中群體的多樣性,是對(duì)有效基因缺失的一種補(bǔ)救措施,同時(shí)也對(duì)因選擇操作失去的多樣性的恢復(fù)具有潛在的作用,是實(shí)現(xiàn)遺傳算法全局優(yōu)化性能的重要算子之一。遺傳算法中,交叉算子因其全局搜索能力而作為主要算子,變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過(guò)交叉和變異這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局和局部的均衡搜索能力,這也是使遺傳算法獲得良好收斂性能的前提條件。實(shí)際上,交叉運(yùn)算是遺傳算法區(qū)別于其它進(jìn)化算法的根本所在,在遺傳算法中起關(guān)鍵作用,是產(chǎn)生新個(gè)體的最主要方法,它決定了遺傳算法的全局搜索能力。但因選擇和交叉作用后保留了適應(yīng)度高的個(gè)體,便會(huì)產(chǎn)生封閉競(jìng)爭(zhēng),導(dǎo)致"近親繁殖",從而引起"早熟"現(xiàn)象。變異操作可增加新的搜索空間,改善遺傳算法的局部搜索能力,維持群體的多樣性,防止出現(xiàn)"早熟"現(xiàn)象,但會(huì)降低收斂速度。變異是對(duì)于二進(jìn)制編碼方式而言,變異操作就是把某些基因座上的基因值取反,即1變0或0變1。通常情況,變異個(gè)體的選擇以及變異位置的確定都是采用隨機(jī)的方法產(chǎn)生。變異概率過(guò)大將引起遺傳算法的振蕩,過(guò)小則影響各進(jìn)化迭代搜索區(qū)域的范圍。并且變異概率較小,約為0.0010.01。變異算子的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因位置上的基因值作變動(dòng)。一般來(lái)說(shuō),變異算子操作的基本步驟如下：〔1在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)地確定基因位置?！?以事先設(shè)定的變異概率Pm來(lái)對(duì)這些基因位置的基因值進(jìn)行變異。遺傳算法通過(guò)交叉和變異這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合,是指當(dāng)群體在進(jìn)化中陷于搜索空間中某個(gè)超平面而僅靠交叉不能擺脫時(shí),通過(guò)變異操作可有助于這種擺脫；所謂競(jìng)爭(zhēng),是指當(dāng)通過(guò)交叉已形成所期望的基因塊時(shí),變異操作有時(shí)可能破壞這些基因塊。遺傳算法中使用變異算子使得遺傳算法有局部的隨機(jī)搜索能力,而且可以使遺傳算法維持群體的多樣性。變異算子的搜索能力分析定義3.1：P<b1→b2>,個(gè)體b1通過(guò)變異算子一步變異到個(gè)體b2的概率；對(duì)n<b1,b2>,兩個(gè)個(gè)體差異位數(shù)〔可取1,2,…,L。則有：〔3.12〔1變異概率對(duì)P<b1→b2>的影響對(duì)〔3.12式求偏導(dǎo)數(shù)可得：〔3.13令得：〔3.14以L=20,n<b1,b2>=3為例,分析對(duì)P<b1→b2>的影響,由式〔3.14K可知=n<b1,b2>/L時(shí)概率最大,此時(shí)P<b1→b2>=2.1301e0.04。對(duì)于確定的n<b1,b2>,=n<b1,b2>/L時(shí),P<b1→b2>得到最大值?！?變異位數(shù)n<b1,b2>對(duì)P<b1→b2>的影響對(duì)〔3.12式求n<b1,b2>,的偏導(dǎo)可得：〔3.15函數(shù)〔3.12關(guān)于n<b1,b2>嚴(yán)格單調(diào)遞減,n<b1,b2>=1時(shí),有：<3.16>以L=20,=0.1為例,進(jìn)一步觀察n<b1,b2>對(duì)P<b1→b2>的影響,由公式可知：n<b1,b2>=1時(shí),P<b1→b2>取得最大值,此時(shí)P<b1→b2>=1.3509×10-2}。隨著n<b1,b2>每增加1,搜索范圍迅速變大,同時(shí)搜索概率P<b1→b2>迅速減小一個(gè)數(shù)量級(jí),這使得在n<b1,b2>大于一定程度時(shí),如此小的概率下的搜索變的缺乏實(shí)際意義。同時(shí)從中可以看出,雖然,變異策略在理論上保障了算法的全局收斂性,但是,變異算子主要進(jìn)行的是針對(duì)每個(gè)個(gè)體的局域搜索?！?多個(gè)個(gè)體b1變異到b2的概率和期望定義3.2：,K個(gè)個(gè)體b1通過(guò)變異算子變異產(chǎn)生至少一個(gè)個(gè)體b2的概率；E<b2|K個(gè)b1>,K個(gè)個(gè)體b1通過(guò)變異算子變異產(chǎn)生個(gè)體b2的期望個(gè)數(shù)。則有：〔3.17從式〔3.17可以看出和E<b2|K個(gè)b1>是關(guān)于K和P<b1→b2>的嚴(yán)格單調(diào)遞增函數(shù)。定義算法中概率的可以接受下界為,則有：〔3.19或者〔3.203.6遺傳算法的參數(shù)規(guī)則首先定義如下：在合理的進(jìn)化代數(shù)內(nèi),個(gè)體b能夠搜索到其相鄰區(qū)域的局部極值稱為有效局域搜索。同時(shí),我們把這個(gè)合理進(jìn)化代數(shù)稱為算法最大容許停滯代數(shù),以M表示。假定待求問(wèn)題滿足積木塊假設(shè),我們來(lái)分析變異算子的局部搜索能力。算法迭代進(jìn)化到一定代數(shù)后,一般會(huì)收斂到某一或某幾個(gè)點(diǎn)上,考慮特殊情況下,群體提前收斂于一點(diǎn)b1,則有：K=N,同時(shí)取α=1/M,則有：〔3.21由式〔3.13和〔3.15可得當(dāng)n<b1,b2>=1,Pb1=1時(shí)P<b1→b2>取得最大值?！?.22由式〔3.21,〔3.22可得：〔3.23在滿足積木塊假設(shè)的前提下,任何不是全局最優(yōu)解的個(gè)體b1都可以通過(guò)隨機(jī)的一個(gè)基因位的變異搜索到較優(yōu)解b2,即：存在b2,滿足n<b1,b2>=1,且f<b2>＞f<b1>。所以,可以得到如下的參數(shù)選擇規(guī)則：<3.24>其中,M可以自由設(shè)定,一般可以設(shè)定為最大算法迭代代數(shù)的1/41/3。第四章遺傳算法的程序設(shè)計(jì)4.1遺傳算法程序設(shè)計(jì)的基本原則設(shè)計(jì)遺傳算法程序,利用計(jì)算機(jī)仿真實(shí)際模型或直接求解問(wèn)題,是研究和應(yīng)用遺傳算法的一個(gè)重要領(lǐng)域。自從遺傳算法理論提出后,人們就無(wú)時(shí)無(wú)處不在利用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)各自的遺傳算法研究和應(yīng)用,對(duì)算法的改進(jìn)、新算子的構(gòu)造、算法效果的觀測(cè),都離不開(kāi)編程實(shí)現(xiàn)。本文在前面理論研究和分析的基礎(chǔ)上,也進(jìn)行了計(jì)算機(jī)編程實(shí)現(xiàn)。一般來(lái)講,實(shí)際設(shè)計(jì)任何GA軟件系統(tǒng),都要考慮下面三個(gè)方面。1.通用性一個(gè)好的GA軟件系統(tǒng),應(yīng)該能滿足不同應(yīng)用場(chǎng)合的需要,具有較大的適用范圍,即使要解決某些特殊問(wèn)題,所做的修改也應(yīng)盡量少,并且是在原有基礎(chǔ)上適當(dāng)改動(dòng),而不是重頭再來(lái)或大幅度改變數(shù)據(jù)結(jié)構(gòu)。2．靈活性實(shí)際設(shè)計(jì)的GA系統(tǒng),還應(yīng)有相當(dāng)?shù)撵`活性,可以采用不同的控制參數(shù),接受一定范圍內(nèi)的參數(shù)變化,并能針對(duì)具體情況允許采用不同的操作策略和操作算子。3.可擴(kuò)展性好的GA系統(tǒng)還必須能夠滿足在以后進(jìn)行擴(kuò)展,如對(duì)問(wèn)題解施行新的編碼方式、采用新的編碼結(jié)構(gòu)、接納新的算子等等。采用模塊描述軟件結(jié)構(gòu),能給人全面、整體的設(shè)計(jì)思路和布局,具有一定的指導(dǎo)意義；而利用matlab強(qiáng)大的矩陣運(yùn)算能力,使我們能夠不局限于程序設(shè)計(jì)的細(xì)節(jié),從算法的整體來(lái)進(jìn)行考慮。4.2程序設(shè)計(jì)過(guò)程中需要考慮的問(wèn)題在前面章節(jié)中,我們已經(jīng)說(shuō)明了遺傳算法在解決實(shí)際問(wèn)題時(shí)采用的步驟與方法以及各種具體處理方式,在不同的應(yīng)用場(chǎng)合,遺傳算法的實(shí)現(xiàn)形式也不盡相同,但不管這些差別任何GA實(shí)現(xiàn)都要處理以下這些問(wèn)題。l.染色體編碼遺傳算法不能直接處理問(wèn)題空間的參數(shù),必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成染色體。編碼通常包括對(duì)變量的處理和編碼方法的選擇。問(wèn)題空間的變量一般可分為連續(xù)變量,均勻離散變量和非均勻離散變量三類。在二值編碼的情況下,為了確定碼串長(zhǎng)度,通常需知道變量的最大值、最小值、精度或個(gè)數(shù)。離散變量還應(yīng)考慮編碼中的冗余策略問(wèn)題。編碼方法常用的有一維染色體編碼、多參數(shù)映射編碼、可變?nèi)旧w長(zhǎng)度編碼、二維染色體編碼和樹(shù)結(jié)構(gòu)編碼等。另外,在不同問(wèn)題中,也可能出現(xiàn)某些特殊編碼方法,如以反映問(wèn)題的狀態(tài)空間或矩陣作為一個(gè)染色體。2.初始種群產(chǎn)生根據(jù)問(wèn)題搜索空間不同,群體大小應(yīng)可靈活調(diào)整,應(yīng)允許用戶修改。3.個(gè)體適應(yīng)值評(píng)價(jià)遺傳算法在進(jìn)化搜索中基本不用外部信息,僅以目標(biāo)函數(shù)為依據(jù)。不同的問(wèn)題有不同的目標(biāo)函數(shù)。個(gè)體的性能評(píng)估采用適應(yīng)度函數(shù)。適應(yīng)度函數(shù)一般由目標(biāo)函數(shù)映射而成。另外,為了避免未成熟收斂,適應(yīng)度函數(shù)度應(yīng)有一定的定標(biāo)方法,目前,常采用的定標(biāo)方法大致有以下幾種：<1>線性定標(biāo)。設(shè)原適應(yīng)度函數(shù)為,定標(biāo)后的適應(yīng)度函數(shù)為,則：〔4.1a和b為滿足一定條件的常數(shù)。<2>截?cái)喽?biāo)。即〔4.2為適應(yīng)度平均值,為常數(shù)。<3>乘冪定標(biāo)。即,為常數(shù),根據(jù)不同問(wèn)題進(jìn)行選擇。4.遺傳操作算子選擇算子包括適應(yīng)度比例方法,最佳個(gè)體保存方法,期望值方法,排序選擇方法,聯(lián)賽選擇方法和排擠方法等幾種。每種方法均有自身的特點(diǎn),求解問(wèn)題時(shí)可以根據(jù)具體情況選擇或把它們結(jié)合使用。交叉算子在字符串編碼下常用的有一點(diǎn)交叉、二點(diǎn)交叉、多點(diǎn)交叉和一致交叉。在樹(shù)結(jié)構(gòu)編碼或矩陣編碼等特殊編碼下則應(yīng)采用特殊的交叉算子。變異算子和交叉算子一樣,受編碼方法的影響。若在字符串編碼下,常用的有基本變異算子、逆轉(zhuǎn)算子和自適應(yīng)變異算子。在特殊編碼下則應(yīng)相應(yīng)地采用特殊設(shè)計(jì)的變異算子。5.基本參數(shù)設(shè)定無(wú)論GA采用何種編碼和遺傳操作,有一些參數(shù)是基本的,也是很重要的,主要包括群體規(guī)模N,代溝G,選擇概率Ps,交叉概率Pc。變異概率Pm等。這些參數(shù)對(duì)GA有重要影響,需要靈活而有效的進(jìn)行調(diào)整。6.結(jié)束條件設(shè)定根據(jù)問(wèn)題不同,可選用不同的結(jié)束條件。如果已知目標(biāo)函數(shù)的極值,則可以是否達(dá)到極值要求作為結(jié)束條件。如果對(duì)時(shí)間有要求,則可以運(yùn)行時(shí)間或代數(shù)作為結(jié)束條件：也可以群體中個(gè)體多樣性是否得以保持為結(jié)束條件。開(kāi)發(fā)GA軟件系統(tǒng),必須解決處理以上這幾方面的問(wèn)題,并且在實(shí)際設(shè)計(jì)時(shí),還必須考慮開(kāi)放性、可擴(kuò)充性和靈活性以滿足不同應(yīng)用的要求。第五章遺傳算法在圖像識(shí)別中的應(yīng)用5.1圖像識(shí)別的模式描述待識(shí)別模式可用二維點(diǎn)列P描述：<5.1>為相對(duì)于模式原點(diǎn)的坐標(biāo),為相應(yīng)的灰度值,將模式放大M倍,旋轉(zhuǎn),并將模式原點(diǎn)平移至,點(diǎn)列變?yōu)椋?lt;5.2>其中<5.3>對(duì)于二值圖像〔背景色為白色,前景色為黑色而言,我們可以定義待識(shí)別模式與圖形庫(kù)中相似圖形的匹配率作為識(shí)別性能的評(píng)價(jià)指標(biāo),。〔5.4式中為點(diǎn)序列中滿足的點(diǎn)個(gè)數(shù)。對(duì)于灰度圖像模式的匹配率R用兩個(gè)點(diǎn)序列和的相關(guān)系數(shù)計(jì)算。如果匹配率越大,表明識(shí)別程度越高。由此模式匹配的問(wèn)題轉(zhuǎn)化為在四維空間內(nèi)求取匹配率R的最大值的問(wèn)題。5.2適應(yīng)度函數(shù)的確定在這里舉一個(gè)為數(shù)字圖像確定目標(biāo)函數(shù)的例子。由于一個(gè)的數(shù)字圖像可以分成若干個(gè)的圖像塊,每一個(gè)塊成為一個(gè)K維矢量=,這樣一個(gè)圖像可以分成<Ⅳ／>個(gè)圖像塊．在一個(gè)圖像的VQ碼中找到一個(gè)和圖像最接近的代碼字。當(dāng)然每一個(gè)代碼字也是K維的在遺傳算法中,一個(gè)代碼字可以代表一個(gè)染色體：圖像的格雷水平線代表一對(duì)基因。它的式子表示成2L一般的L=8或l6。換句話說(shuō)一個(gè)K維的代碼字,染色體可以用個(gè)整數(shù)串代表,而且這是一對(duì)基因。每一對(duì)基因可以被比特率傳輸?shù)亩M(jìn)制代碼代表。對(duì)每一塊設(shè)置成R,如果Vg<vig>是一個(gè)侯選代碼字與子集對(duì)應(yīng),則有∈。換句話說(shuō),如果R是這些圖像塊的子集。它的最相近的代碼字是Vg<vig>那么目標(biāo)函數(shù)可表示成<5.5><5.6>Mg是子集Rg中元素的總數(shù)量,是Rg子集中第i行第j列的圖像塊,M是R集中元素的總量。<Ai=l,2>是權(quán)值。是衡量子集Rg圖像塊和侯選代碼字Vg<vig>的相同程度,隨著平均值平方的錯(cuò)誤率減小,F1g的值提高了,F1g是另一個(gè)衡量相似度的變量。由兩項(xiàng)組成：第一項(xiàng)為Vg中用來(lái)均衡圖像塊的最相似的代碼字的數(shù)量,第二項(xiàng)為均衡Vg中相似的影像的圖像塊的數(shù)量。在一系列侯選電報(bào)密碼中,Vc<Vi,i=l,2?,m>Vg代碼字為<5.7><5.8>其中Xj<xij>∈R,在樣本空間中Mg是gj中的元素總量。其中Xj<xij>∈R,gj=1,Xj是Rg中子集元素,Vg是最近的候選代碼字。Rg子集中的元素總量是Mg這樣R中的矢量可以映射到Vc候選碼中。第一階段將限制能導(dǎo)致較少圖象塊侯選代碼的遺傳基因的數(shù)量。第二階段可以改進(jìn)VQ碼中的馬塞克結(jié)果。<5.9><5.10>Xj<xij>∈Rg,Vg<vig>∈Vc,Rg中i行j列圖象塊和i維Vg代碼的差小于時(shí),Nij=1,gj是那些圖象塊總數(shù)和電報(bào)密碼Vg當(dāng)中相應(yīng)像素而言,他們當(dāng)中至少有一個(gè)像素小于。以上是在遺傳算法圖像識(shí)別中目標(biāo)函數(shù)的確定,對(duì)于M圖像樣本,樣本空間包括M<N/n>2K維矢量。每個(gè)矢量成為一個(gè)圖像塊。為產(chǎn)生一個(gè)內(nèi)容為C,并且C依賴于傳輸通道的電報(bào)密碼本,那么就需要尋找優(yōu)化的電報(bào)密碼的集合。其目的是在重建后的圖像在樣本空間中可以保持可接受的逼真效果。個(gè)體的適應(yīng)度可取匹配率指標(biāo)作為為評(píng)價(jià)依據(jù)。對(duì)于二值圖像,由于它的噪聲與信號(hào)具有相同的強(qiáng)度<非0即1>,若直接利用〔5.3式計(jì)算,將使二值圖像中相匹配的個(gè)體具有極高的適應(yīng)度,而在其鄰域中個(gè)體的適應(yīng)度很低且適應(yīng)度值極為相似,從而弱化了適應(yīng)度函數(shù)的導(dǎo)向作用。為此我們將二值圖像進(jìn)行預(yù)處理,將其轉(zhuǎn)化為灰階數(shù)為L(zhǎng)的多值形式。因此,個(gè)體Ii的適應(yīng)度可按下式計(jì)算：〔5.11在0象素點(diǎn)<Wxi,Wyi>的L鄰域中搜索1象素點(diǎn)<Bxi,Byi>,即〔5.12若0象素點(diǎn)的L鄰域中無(wú)1象素點(diǎn),則灰度值為0,并處理下一個(gè)0象素點(diǎn)。計(jì)算0象素點(diǎn)Wi與鄰域中的1象素點(diǎn)Bj的棋盤(pán)距離δij:〔5.133>調(diào)整0象素點(diǎn)灰度值為二值模式描述其中為模式中1象素的坐標(biāo)。5.3圖像識(shí)別的運(yùn)算流程本實(shí)驗(yàn)中我們?cè)O(shè)置的可識(shí)別圖形為三角形、矩形、圓或橢圓、不規(guī)則形。對(duì)所選擇的識(shí)別圖形進(jìn)行噪聲和輪廓平滑處理,再繪制原圖像。程序的最后輸出結(jié)果是圖形,包括待識(shí)別的圖形、圖像識(shí)別、遺傳算法適應(yīng)度進(jìn)化曲線、隨機(jī)搜索適應(yīng)度進(jìn)化曲線、灰階數(shù)、像素?cái)?shù)等。適應(yīng)度進(jìn)化曲線反應(yīng)了最大適應(yīng)度和平均適應(yīng)度隨世代數(shù)的不斷進(jìn)化而變化的關(guān)系。程序運(yùn)行過(guò)程如圖5.1所示,它是圖像識(shí)別過(guò)程圖的一個(gè)擴(kuò)展,是實(shí)驗(yàn)的執(zhí)行全過(guò)程。選擇需識(shí)別的圖形后,對(duì)圖形進(jìn)行輪廓圓滑處理,輪廓圓滑處理如果不滿意,程序返回到"選擇需識(shí)別的圖形",可以重新選擇需識(shí)別的圖形,也可以選擇與上次相同,直到輪廓圓滑處理滿意才進(jìn)入到下一個(gè)處理過(guò)程——加入噪聲否？如果選擇"Y"則加入噪聲,進(jìn)行隨機(jī)描點(diǎn),如果選擇"N"則不需加入噪聲,不用隨機(jī)描點(diǎn)。然后對(duì)圖像進(jìn)行坐標(biāo)變換處理。在新的坐標(biāo)系下繪制圖像,繪制圖像滿意否？不滿意,則重畫(huà)；滿意,程序可以繼續(xù)向下運(yùn)行。程序運(yùn)行結(jié)果的顯示是圖形,因此,我們接下來(lái)的任務(wù)是對(duì)顯示畫(huà)面初始化,初始化適應(yīng)度圖形窗口。圖像識(shí)別的過(guò)程是一個(gè)不斷地運(yùn)用遺傳算法的過(guò)程,在實(shí)驗(yàn)中,我們采用遺傳搜索和隨機(jī)搜索兩種方法,主要是研究遺傳算法。適應(yīng)度函數(shù)采用最優(yōu)保存策略,每次保存適應(yīng)度值最大的個(gè)體,程序結(jié)束的條件是遺傳的世代數(shù)是否小于120,小于則繼續(xù)進(jìn)行,達(dá)到了120代后就結(jié)束。每一代種群,我們都要計(jì)算其所有個(gè)體適應(yīng)度的大小并排序,繪制最大適應(yīng)值對(duì)應(yīng)的圖形。開(kāi)始開(kāi)始隨機(jī)產(chǎn)生初始個(gè)體的遺傳基因顯示原圖像適應(yīng)度<=120?產(chǎn)生新一代種群繪制適應(yīng)度最大的圖形適應(yīng)度排序輪廓平滑處理滿意否？輪廓平滑處理矩形選擇所需識(shí)別的圖形圖形界面初始化計(jì)算群體中所有個(gè)體的適應(yīng)度隨機(jī)產(chǎn)生初始個(gè)體的遺傳基因顯示原圖像適應(yīng)度<=120?產(chǎn)生新一代種群繪制適應(yīng)度最大的圖形適應(yīng)度排序輪廓平滑處理滿意否？輪廓平滑處理矩形選擇所需識(shí)別的圖形圖形界面初始化計(jì)算群體中所有個(gè)體的適應(yīng)度不規(guī)則形圓或不規(guī)則形圓或橢圓三三角形YNN加入噪聲否？Y加入噪聲否？隨機(jī)描點(diǎn)Y隨機(jī)描點(diǎn)計(jì)算種群中所有個(gè)體的適應(yīng)度N計(jì)算種群中所有個(gè)體的適應(yīng)度坐標(biāo)變換處理坐標(biāo)變換處理適應(yīng)度排序適應(yīng)度排序繪制適應(yīng)度最大的圖形繪制圖像繪制適應(yīng)度最大的圖形繪制圖像對(duì)圖像滿意否？對(duì)圖像滿意否？適應(yīng)度<=120?Y適應(yīng)度<=120?N顯示原圖像Y顯示原圖像初始化顯示畫(huà)面初始化顯示畫(huà)面結(jié)束適應(yīng)度圖形窗口初始化結(jié)束適應(yīng)度圖形窗口初始化圖5.1程序運(yùn)行流程圖5.4功能模塊分析遺傳算法在圖像識(shí)別中的應(yīng)用,按照功能可以分為七大模塊：1.主模塊主模塊是程序運(yùn)行的主環(huán)境,在此基礎(chǔ)上通過(guò)調(diào)用各子模塊,來(lái)實(shí)現(xiàn)程序的運(yùn)行。另外,將公用參數(shù)的設(shè)定放在主模塊里,各子模塊通過(guò)參數(shù)傳遞使用這些公用參數(shù),盡量避免使用全局變量〔因?yàn)槿肿兞吭诔绦蚝艽蟮臅r(shí)候,有可能給程序帶來(lái)意想不到的破壞。這些參數(shù)有：群體規(guī)模NUM,自變量的取值范圍MAX、MIN,交叉概率Pc,變異概率Pm,繁殖因子Pg,循環(huán)結(jié)束條件e<精度的要求>和gmax〔循環(huán)的最大代數(shù)限制。2.初始化模塊隨機(jī)產(chǎn)生初始群體,該群體應(yīng)盡量均勻分布在整個(gè)問(wèn)題空間。使用"initialize_gene"函數(shù)對(duì)種群中個(gè)體遺傳基因型進(jìn)行初始化；在初始化界面中使用了"g_draw_frame"函數(shù),對(duì)文本背景、文本前景色及外框顏色做了設(shè)定,在此基礎(chǔ)上通過(guò)調(diào)用"g_disp_image<>"函數(shù),實(shí)現(xiàn)了在初始畫(huà)面中顯示原圖像；適應(yīng)度函數(shù)圖形窗口的初始化則是使用了"g_init_graphs<>"函數(shù),該模塊主要描述了：最大適應(yīng)度、平均適應(yīng)度、世代數(shù)等。3.函數(shù)計(jì)算模塊將函數(shù)計(jì)算模塊獨(dú)立出來(lái),便于模型實(shí)現(xiàn)對(duì)不同問(wèn)題的計(jì)算時(shí)改動(dòng)其他的模塊。4.適應(yīng)度計(jì)算模塊根據(jù)不同的需要,可以對(duì)整個(gè)群體進(jìn)行適應(yīng)度計(jì)算,也可以對(duì)單個(gè)的個(gè)體進(jìn)行適應(yīng)度計(jì)算。計(jì)算過(guò)程中僅以適應(yīng)度函數(shù)為依據(jù),利用種群中每個(gè)個(gè)體的適應(yīng)度來(lái)進(jìn)行搜索。盡可能簡(jiǎn)單、使計(jì)算的時(shí)間復(fù)雜度盡可能小是該模塊的特點(diǎn),它真正體現(xiàn)了遺傳算法"優(yōu)勝劣汰"的特點(diǎn)。5.選擇算子模塊根據(jù)傳入的參數(shù)〔群體適應(yīng)度值,構(gòu)造選擇區(qū)。選擇策略是基于改進(jìn)后的選擇策略。返回選擇后的群體〔競(jìng)爭(zhēng)群體。該模塊從群體中選擇優(yōu)勝的個(gè)體,淘汰劣質(zhì)個(gè)體。從而使得對(duì)生存環(huán)境適應(yīng)度較高的物種有更多的機(jī)會(huì)遺傳到下一代,而對(duì)生存環(huán)境適應(yīng)程度較低的物種遺傳到下一代的機(jī)會(huì)就相對(duì)較少。從而把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。6.交叉算子模塊傳入?yún)?shù)是競(jìng)爭(zhēng)群體,交叉概率Pc。循環(huán)以Pc為概率隨機(jī)地從群體中選出一對(duì)個(gè)體,進(jìn)行算術(shù)交叉后放入中間群體,當(dāng)中間群體的規(guī)模滿足需要后,返回這個(gè)中間群體。該模塊將兩個(gè)父代個(gè)體<染色體>的部分字符<基因>互相交換,由此產(chǎn)生新的個(gè)體。通過(guò)交叉操作,從而提高遺傳算法的搜索能力。該模塊的重點(diǎn)是保證前一代中優(yōu)秀個(gè)體的性狀能在后一代新個(gè)體中盡可能得到遺傳和繼承。7.變異算子模塊該模塊主要是作為輔助模塊。它傳入的參數(shù)是競(jìng)爭(zhēng)群體、變異概率Pm。以Pm為概率隨機(jī)地從群體中選出一個(gè)個(gè)體,進(jìn)行變異操作。在此之前,變異概率Pm是隨著進(jìn)化代數(shù)自適應(yīng)的變化的。模塊返回變異后的群體。該模塊可對(duì)個(gè)體串的某些基因位的值進(jìn)行隨機(jī)改變,增強(qiáng)遺傳算法運(yùn)行中群體的多樣性,能夠?qū)蛉笔нM(jìn)行補(bǔ)救,也能對(duì)因選擇操作而失去的群體多樣性進(jìn)行恢復(fù),使得在選擇和交叉操作后得以保留的適應(yīng)度高的個(gè)體,不產(chǎn)生封閉競(jìng)爭(zhēng),導(dǎo)致"近親繁殖",從而引起"早熟"現(xiàn)象。同時(shí)它還可增加新的搜索空間,改善遺傳算法的局部搜索能力,維持群體的多樣性,實(shí)現(xiàn)遺傳算法的全局優(yōu)化。這些模塊具有相對(duì)的獨(dú)立性,在更改遺傳策略時(shí),可以用相對(duì)應(yīng)的功能模塊替換而不影響整個(gè)算法。5.5程序運(yùn)行結(jié)果及分析運(yùn)行環(huán)境：Windows2000操作系統(tǒng),turboc2。運(yùn)行過(guò)程：⑴把graph.h文件放入turboc2的include文件夾；⑵運(yùn)行程序產(chǎn)生的.exe、.obj文件在D盤(pán),故把HZK16J放在D盤(pán)根目錄下；⑶執(zhí)行tc.exe,打開(kāi)源程序,運(yùn)行；⑷程序初始界面,選擇待識(shí)別的圖形：1：三角形,2：矩形,3：圓或橢圓,4：不規(guī)則圖形。選擇1—4任意數(shù),按回車鍵,屏幕繪制出所選圖形；⑸屏幕提示：輪廓圓滑處理滿意否？1：no2：yes,輸入1并按回車鍵,將返⑷；輸入2并按回車鍵,程序?qū)⒗^續(xù)向下執(zhí)行；⑹屏幕提示：加入噪聲否？1：no2：yes,輸入數(shù)字并按回車鍵；⑺屏幕提示：畫(huà)原圖像滿意否？1：no2：yes,如果輸入的是1,將重新畫(huà)圖如果輸入的是2,并按回車鍵,屏幕將顯示最終畫(huà)面。按照上述運(yùn)行步驟運(yùn)行本程序,得到本次實(shí)驗(yàn)結(jié)果如下列圖所示:圖5.1三角形的識(shí)別圖5.2矩形的識(shí)別圖5.3圓的識(shí)別圖5.4不規(guī)則圖形的識(shí)別圖5.1中遺傳算法適應(yīng)度進(jìn)化曲線在第30代左右時(shí)就取得了最大值,算法收斂到最優(yōu)解,此后適應(yīng)度一直保持該值,而平均適應(yīng)度的值在50代以前保持持續(xù)上升,此后沒(méi)有大的起伏變化。采用隨機(jī)搜索算法,在75代左右搜索到最優(yōu)解。圖5.2中遺傳算法適應(yīng)度進(jìn)化曲線在第75代左右時(shí)就取得了最大值,算法收斂到最優(yōu)解,此后適應(yīng)度一直保持該值,而平均適應(yīng)度的值在90代以前保持持續(xù)上升,此后也沒(méi)有大的起伏變化。采用隨機(jī)搜索算法,在15代左右搜索到最優(yōu)解。同樣,圖5.3中遺傳算法適應(yīng)度進(jìn)化曲線在第25代左右時(shí)就取得了最大值,算法收斂到最優(yōu)解,此后適應(yīng)度一直保持該值,而平均適應(yīng)度的值在40代以前保持持續(xù)上升,此后也沒(méi)有大的起伏變化。采用隨機(jī)搜索算法,在95代左右搜索到最優(yōu)解。圖5.4遺傳算法適應(yīng)度進(jìn)化曲線在第25代左右時(shí)就取得了最大值,算法收斂到最優(yōu)解,此后適應(yīng)度一直保持該值,而平均適應(yīng)度的值在10代以前保持持續(xù)上升,此后沒(méi)有大的起伏變化。采用隨機(jī)搜索算法,在60代左右搜索到最優(yōu)解。結(jié)束語(yǔ)遺傳算法現(xiàn)在正日益應(yīng)用到科學(xué)研究和工程實(shí)踐的眾多領(lǐng)域,越來(lái)越多的人開(kāi)始關(guān)注、研究這一技術(shù)。在這種背景下,本文以遺傳算法理論和應(yīng)用為研究?jī)?nèi)容做了一些工作,分析了遺傳算法的基本實(shí)現(xiàn)技術(shù)。如：編碼、適應(yīng)度函數(shù)、遺傳算法的三大遺傳操作、參數(shù)規(guī)則等。最后在介紹了遺傳算法程序設(shè)計(jì)原則的基礎(chǔ)上,編程實(shí)現(xiàn)了遺傳算法在圖像識(shí)別中的應(yīng)用在實(shí)踐中檢驗(yàn)了遺傳算法的實(shí)際效果。作為一種搜索算法,遺傳算法的基本框架已經(jīng)形成,在各種問(wèn)題的求解和應(yīng)用中展現(xiàn)了它的特點(diǎn)和魅力,同時(shí)也暴露出了在理論上和應(yīng)用技術(shù)上的許多不足和缺陷。比如相對(duì)鮮明的生物基礎(chǔ),其數(shù)學(xué)基礎(chǔ)顯得極為薄弱,尤其是缺乏深刻且具普遍意義的理論分析。所以,我們?cè)谶z傳算法研究方面還有很多工作要做。致謝在大學(xué)畢業(yè)之際,我得到了導(dǎo)師徐曉蓉老師的悉心指導(dǎo),并在她的指導(dǎo)下順利地完成了《遺傳算法及其應(yīng)用》的畢業(yè)設(shè)計(jì)。在此感謝徐老師的教育與指導(dǎo)。徐老師在工作、學(xué)習(xí)中嚴(yán)格要求、一絲不茍的敬業(yè)精神一直是我們的學(xué)習(xí)榜樣,在徐老師的幫助和指導(dǎo)下,我們?cè)诶碚摲矫鎸W(xué)到了如何開(kāi)展科學(xué)研究、設(shè)計(jì)程序等,同時(shí)在實(shí)踐中我們也受到了有益的鍛煉。另外,感謝身邊的同學(xué)們。我們?cè)谝黄鸲冗^(guò)了緊張、愉快的大學(xué)生活,在學(xué)習(xí)和生活中互相幫助共同克服困難,這是一段難以忘記的經(jīng)歷。參考文獻(xiàn)[1]劉勇,康立山,陳毓屏.非數(shù)值并行算法<第二冊(cè)>遺傳算法.北京:科學(xué)出版社,1995[2]張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ).XX:XX交通大學(xué)出版社,2005[3]周明,孫樹(shù)棟.遺傳算法原理及應(yīng)用.北京:國(guó)防工業(yè)出版社,1999[4]王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn).XX:XX交通大學(xué)出版社,2002[5]Z.米凱利維茨.演化程序—遺傳算法和數(shù)據(jù)編碼的結(jié)合.北京:科學(xué)出版社,2004[6]NirwanAnsariEdwinHou.用于最優(yōu)化的計(jì)算智能.北京:清華大學(xué)出版社,1999[7]吳少巖,許卓群.遺傳算法中遺傳算子的啟發(fā)式構(gòu)造策略[J]．計(jì)算機(jī)學(xué)報(bào),1998,21<11>:1003一l008．[8]陳國(guó)良,王熙法等。遺傳算法及其應(yīng)用。北京:人民郵電出版社,1996[9]潘正君,康立山等。演化計(jì)算。清華大學(xué)出版社。廣西科學(xué)技術(shù)出版社,1998[10]GoldbergDE.GeneticAlgorithmsinSearch.OptimizationandMachineLearing,ReadingMA,Addison-WesleyPublishing,1989[11]閻凡平,張長(zhǎng)水。人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算。清華大學(xué)出版社,2000[12]李德,錢(qián)頌迪等。運(yùn)籌學(xué)。清華大學(xué)出版社,1999[13]HollandJH.AdaptationinNatureandArtificialSystem.MITPress,1998[14]HollandJH.GeneticAlgorithmsandClassifierSystems:FoundationsandFutureDirections.GeneticAlgorithmsandTheirApplications.Procofthe2IntOnGeneticAlgori-thms1987,82～89[15]非數(shù)值并行算法——遺傳算法。北京：科學(xué)出版社,1998[16]GoldbergDE.GeneticAlgorithmandWalshFunctions,PartI&II.ComplexSystems,1989,3:129～152,153～171[17]HollandJH基因算法[J]科學(xué),1992,11：24—30[18]ForrestS．Geneticalgorithms：principlesofnaturalSe—lectionappliedtocompu-taion[J]．Science,1993,261：872—878．附錄：源程序代碼#include"stdio.h"#include"stdlib.h"#include"graphics.h"#include"math.h"#include"time.h"#include"string.h"#include"graph.h"#definePOP_SIZE20/*種群大小*/#defineS_RATE0.4/*選擇操作時(shí)淘汰率設(shè)定*/#defineDEFOCUS_L4/*圖像輪廓處理的灰階數(shù)*/#defineG_LENGTH15/*個(gè)體染色體長(zhǎng)度*/#defineXUL100/*原圖像窗口左上角點(diǎn)的X坐標(biāo)*/#defineYUL250/*原圖像窗口左上角點(diǎn)的Y坐標(biāo)*/#defineGX1360/*遺傳算法適應(yīng)度圖形窗口的左上角點(diǎn)X坐標(biāo)*/#defineGY166/*遺傳算法適應(yīng)度圖形窗口的左上角點(diǎn)Y坐標(biāo)*/#defineGX2360/*隨機(jī)算法適應(yīng)度圖形窗口的左上角點(diǎn)X坐標(biāo)*/#defineGY2257/*隨機(jī)算法適應(yīng)度圖形窗口的左上角點(diǎn)Y坐標(biāo)*/#defineGXR250/*適應(yīng)度圖形窗口長(zhǎng)度*/#defineGYR100/*適應(yīng)度圖形窗口寬度*/#defineGSTEP2/*適應(yīng)度圖形X方向步長(zhǎng)*/unsignedchargene[POP_SIZE][G_LENGTH];/*當(dāng)前世代個(gè)體的遺傳基因*/unsignedcharimage[128][128];/*原二值圖像數(shù)據(jù)*/doublefitness[POP_SIZE],trans10[POP_SIZE],trans[G_LENGTH];double_sin[8];_cos[8];/*45度三角函數(shù)表*/doublemax_fit,avg_fit,min_fit;/*當(dāng)前世代最大適應(yīng)度與平均適應(yīng)度、最小適應(yīng)度*/intm_num;/*原圖像構(gòu)成像素點(diǎn)數(shù)*/intm_pnts[2][1000];/*圖像中像素點(diǎn)位置坐標(biāo)*/intpnts[2][1000];/*在圖形窗口顯示用的像素點(diǎn)位置坐標(biāo)*/doubleM_RATE=0.05,C_RATE=0.5;/**/voidtrans_all<>/*所有二進(jìn)制轉(zhuǎn)換成十進(jìn)制*/{inti,j,m;for<i=0;i<POP_SIZE;i++>for<j=G_LENGTH-1,m=0;j>=0&&m<G_LENGTH;j--,m++>trans10[i]+=gene[i][j]+pow<2,m>;}voidtrans_1<unsignedchar*gene,intg>/*個(gè)別基因二進(jìn)制轉(zhuǎn)換成十進(jìn)制*/{intj,m;unsignedchar*gene5;gene5=gene+G_LENGTH*g;for<j=G_LENGTH-1,m=0;j>=0&&m<G_LENGTH;j--,m++> trans[j]+=*<gene5+j>+pow<2,m>;}voidinitialize_gene<gene,pop_size,g_length>/*種群中個(gè)體遺傳基因型的初始化*/unsignedchar*gene;/*遺傳基因*/intpop_size;/*種群大小*/intg_length;/*個(gè)體染色體的長(zhǎng)度*/{inti,j;randomize<>;for<i=0;i<pop_size;i++>for<j=0;j<g_length;j++>*<gene+i*g_length+j>=random<2>;}voidtwo_crossover<gene,g1,g2,g3,g4,g_length>/*兩點(diǎn)交叉*/unsignedchar*gene;/*遺傳基因排列*/intg1,g2,g3,g4;/*g1,g2父?jìng)€(gè)體編號(hào)g3,g4子個(gè)體編號(hào)*/intg_length;/*個(gè)體遺傳基因的位長(zhǎng)*/{unsignedchar*gene1;/*父1遺傳基因的指針*/unsignedchar*gene2;unsignedchar*gene3;unsignedchar*gene4;intc_pos1,c_pos2;inti,j;intwork;doubler;gene1=gene+g_length*g1;gene2=gene+g_length*g2;gene3=gene+g_length*g3;gene4=gene+g_length*g4;c_pos1=random<g_length-1>;c_pos2=random<g_length-1>;while<c_pos1==c_pos2>c_pos2=random<g_length-1>;if<c_pos1>c_pos2>{work=c_pos1;c_pos1=c_pos2;c_pos2=work;}for<j=0;j<g_length;j++>{if<j>=c_pos1&&j<=c_pos2>{*<gene3+j>=*<gene2+j>;*<gene4+j>=*<gene1+j>;}else{*<gene3+j>=*<gene1+j>;*<gene3+j>=*<gene2+j>;}}}voidg_draw_frame<x1,y1,x2,y2,c1,c2,c3,c4,text>/*在圖形區(qū)指定位置寫(xiě)文本*/intx1,y1,x2,y2,c1,c2,c3,c4;/*<x1,y1>為左上角坐標(biāo),<x2,y2>為右下角坐標(biāo),c1為背景色,c2外框顏色,c3為文本背景色,c4為文本前景色*/char*text;{intn,x3;g_rectangle<x1,y1,x2,y2,c1,1>;g_rectangle<x1,y1,x2,y2,c2,0>;g_rectangle<x1,y1,x2,y1+16,c3,1>;g_rectangle<x1,y1,x2,y1+16,c2,0>;n=strlen<text>;x3=x1+<<x2-x1-n*8>/2>;disp_hz16<text,x3,y1,c4>;}voidg_disp_image<>/*顯示原圖像*/{inti,j;for<i=0;i<128;i++>for<j=0;j<128;j++>g_pset<XUL+j,YUL+i,image[j][i]>;}voidg_init_frames<>/*初始化畫(huà)面*/{inti,j,cx,cy,x,y;chartext[17];g_draw_frame<0,0,639,399,15,0,4,15,"遺傳算法在圖像別中的應(yīng)用">;g_draw_frame<0,16,320,170,7,15,8,15,"待識(shí)別的圖形">;itoa<m_num,text,10>;setcolor<9>;disp_hz16<"構(gòu)成點(diǎn)數(shù)=",30,50,15>;disp_hz16<text,118,50,15>;for<i=0;i<m_num;i++>g_pset<m_pnts[0][i]+160,m_pnts[1][i]+110,4>;g_draw_frame<0,170,320,399,7,15,8,15,"">;g_draw_frame<0,170,320,399,7,15,8,15,"圖像識(shí)別">;g_rectangle<XUL-1,YUL-1,XUL+128,YUL+128,15,0>;g_disp_image<>;setcolor<9>;disp_hz16<"像素?cái)?shù)=128x128",30,200,15>;disp_hz16<"灰階數(shù)=",30,220,15>;itoa<DEFOCUS_L,text,10>;disp_hz16<text,102,220,15>;g_draw_frame<320,16,639,207,7,15,8,15,"">;g_draw_frame<320,16,639,207,7,15,8,15,"遺傳算法適應(yīng)度進(jìn)化曲線">;g_draw_frame<320,207,639,399,7,15,8,15,"隨機(jī)搜索適應(yīng)度變化曲線">;}voidg_init_graphs<>/*適應(yīng)度圖形窗口初始化*/{g_rectangle<GX1,GY1,GX1+GXR,GY1+GYR,0,1>;g_rectangle<GX1,GY1,GX1+GXR,GY1+GYR,6,0>;setcolor<1>;disp_hz16<"最大適應(yīng)度",GX1+5,GY1-18,15>;g_line<GX1+90,GY1-10,GX1+110,GY1-10,1>;setcolor<4>;disp_hz16<"平均適應(yīng)度",GX1+120,GY1-18,15>;g_line<GX1+205,GY1-10,GX1+225,GY1-10,40>;setcolor<15>;disp_hz16<"世代數(shù)",GX1+168,GY1+GYR+10,15>;g_text<GX1-20,GY1,15,"1.0">;g_text<GX1-20,GY1+GYR,15,"0.0">;g_rectangle<GX2,GY2,GX2+GXR,GY2+GYR,0,1>;g_rectangle<GX2,GY2,GX2+GXR,GY2+GYR,6,0>;setcolor<1>;disp_hz16<"最大適應(yīng)度",GX2+5,GY2-18,15>;g_line<GX2+90,GY2-10,GX2+110,GY2-10,1>;setcolor<4>;disp_hz16<"平均適應(yīng)度",GX2+120,GY2-18,15>;g_line<GX2+205,GY2-10,GX2+225,GY2-10,4>;setcolor<15>;disp_hz16<"世代數(shù)",GX2+168,GY2+GYR+10,15>;g_text<GX2-20,GY2,15,"1.0">;g_text<GX2-20,GY2+GYR,15,"0.0">;}voidg_set_model<>/*設(shè)置圖像識(shí)別的圖形庫(kù)*/{intx1,y1,x2,y2,x3,y3;inti,j,ok,n1,n2,yn,col;doublerad[90],wx,wy,work;charchoice[2];ok=1;while<ok==1>{g_cls<>; settextstyle<0,0,4>; gprintf<220,20,4,0,"PR-GA">;setcolor<9>; di