遺傳算法的基本原理

1、第二章第二章遺傳算法的基本原理遺傳算法的基本原理2.12.1遺傳算法的基本描述遺傳算法的基本描述2.1.12.1.1全局優(yōu)化問題全局優(yōu)化問題全局優(yōu)化問題的定義：全局優(yōu)化問題的定義：給定非空集合S作為搜索空間，f：S—R為目標(biāo)函數(shù)，全局優(yōu)化問題作為任務(wù)給出，即在搜索空間中找到至少一個(gè)使目)(maxxfSx?標(biāo)函數(shù)最大化的點(diǎn)。全局最大值（點(diǎn)）的定義：全局最大值（點(diǎn)）的定義：函數(shù)值稱為一個(gè)全局最大值，????)(xff當(dāng)且僅當(dāng)成立時(shí)，被稱為一

2、個(gè)全局最大值點(diǎn)（全)()(xfxfSx????Sx?局最大解）。局部極大值與局部極大值點(diǎn)（解）的定義：局部極大值與局部極大值點(diǎn)（解）的定義：假設(shè)在S上給定了某個(gè)距離度量，如果對(duì)，，使得對(duì)，?Sx?0???Sx??，則稱x’為一個(gè)局部極大值點(diǎn)，f(x’)為一個(gè)局部極大)()()(xfxfxx?????值。當(dāng)目標(biāo)函數(shù)有多個(gè)局部極大點(diǎn)時(shí)，被稱為多峰或多模態(tài)函數(shù)（multimodalityfunction）。主要考慮兩類搜索空間：偽布爾優(yōu)化問題

3、：偽布爾優(yōu)化問題：當(dāng)S為離散空間BL=01L即所有長度為L且取值為0或1的二進(jìn)制位串的集合時(shí)，相應(yīng)的優(yōu)化問題在進(jìn)化計(jì)算領(lǐng)域稱為偽布爾優(yōu)化問題。連續(xù)參數(shù)優(yōu)化問題：連續(xù)參數(shù)優(yōu)化問題：當(dāng)取S偽n維實(shí)數(shù)空間Rn中的有界集合，][1iinibaS???其中，i=12…n時(shí)，相應(yīng)的具有連續(xù)變量的優(yōu)化問題稱為連續(xù)參數(shù)iiba?優(yōu)化問題。對(duì)S為BL=01L，常采用的度量時(shí)海明距離，當(dāng)時(shí)，常采][1iinibaS???用的度量就是歐氏距離。2.1.2遺傳

4、算法的基本流程GA編碼空間中對(duì)位串個(gè)體進(jìn)行操作。定義定義：由問題空間向GA編碼空間的映射稱為編碼，而有編碼空間向問題空間的映射成為譯碼。問題編碼一般應(yīng)滿足以下三個(gè)原則：1）完備性完備性（completeness）：?jiǎn)栴}空間中的所有點(diǎn)都能能成為GA編碼空間中的點(diǎn)的表現(xiàn)型。即編碼應(yīng)能覆蓋整個(gè)問題空間。2）健全性健全性（soundness）：GA編碼空間中的染色體位串必須對(duì)應(yīng)問題空間中的某一潛在解。即每個(gè)編碼必須是有意義的。3）非冗余性非冗余

5、性（nonredundancy）：染色體和潛在解必須一一對(duì)應(yīng)。在某些情況下，為了提高GA的運(yùn)行效率，允許生成包含致死基因的編碼位串，它們對(duì)應(yīng)于優(yōu)化問題的非可行解。雖然會(huì)導(dǎo)致冗余或無效的搜索，但可能有助于生成全局最優(yōu)解所對(duì)應(yīng)的個(gè)體，所需的總計(jì)算量可能反而減少。根據(jù)模式定理，DeJong進(jìn)一步提出了較為客觀明確的編碼評(píng)估準(zhǔn)則，稱之為編碼原理。具體可以概括為兩條規(guī)則：1）有意義積木塊編碼規(guī)則有意義積木塊編碼規(guī)則：編碼應(yīng)易于生成與所求問題相關(guān)的

6、短距和低階的積木塊。2）最小字符集編碼規(guī)則最小字符集編碼規(guī)則：編碼應(yīng)采用最小字符集，以使問題得到自然、簡(jiǎn)單的表示和描述。1二進(jìn)制編碼二進(jìn)制編碼1）連續(xù)實(shí)函數(shù)的二進(jìn)制編碼）連續(xù)實(shí)函數(shù)的二進(jìn)制編碼設(shè)一維連續(xù)實(shí)函數(shù)采用長度維L的二進(jìn)制字符串進(jìn)行定長編][)(vuxxf?碼，建立位串空間：，，??KLaaaS21??)(21kLkkkaaaa????10?klak=12…Kl=12…LK=2L其中，個(gè)體的向量表示為，其字符串形式為)(21kLk