遺傳算法講義4slides

1、第四章 遺傳算法與函數(shù)優(yōu)化4.1 研究函數(shù)優(yōu)化的必要性：首先，很多實(shí)際問題進(jìn)行數(shù)學(xué)建模后，可抽象為一個數(shù)值函數(shù)的優(yōu)化問題。其次，便于系統(tǒng)、規(guī)范地研究測試遺傳算法地性能。4.2 評價遺傳算法性能的常用測試函數(shù)在設(shè)計(jì)用于評價遺傳算法性能的測試函數(shù)時，必須考慮實(shí)際應(yīng)用問題的數(shù)學(xué)模型中所可能呈現(xiàn)出的各種數(shù)學(xué)特性，以及可能遇到的各種情況和影響因素。這里所說的數(shù)學(xué)特性主要包括：連續(xù)函數(shù)或離散函數(shù)；凹函數(shù)或凸函數(shù)；二次函數(shù)或非二次函數(shù)；低維函數(shù)或高維函數(shù)；確定性函數(shù)或隨機(jī)性函數(shù)；單峰值函數(shù)或多峰值函數(shù)，等等。下面是一些在評價遺傳算法性能時經(jīng)常用到的測試函數(shù)：De Jong函數(shù)F1：這是一個簡單的平方和函數(shù)，

2、只有一個極小點(diǎn)f1(0, 0, 0)0。De Jong函數(shù)F2：這是一個二維函數(shù)，它具有一個全局極小點(diǎn)f2(1，1) = 0。該函數(shù)雖然是單峰值的函數(shù)，但它卻是病態(tài)的，難以進(jìn)行全局極小化。De Jong函數(shù)F3：這是一個不連續(xù)函數(shù)，對于區(qū)域內(nèi)的每一個點(diǎn)，它都取全局極小值。 De Jong函數(shù)F4：這是一個含有高斯噪聲的4次函數(shù)，當(dāng)不考慮噪聲的影響時，它具有一個全局極小值f4(0，0，0)0。De Jong函數(shù)F5：這是一個多峰值函數(shù)，它總共有25個局部極小點(diǎn)，其中有一個是全局極小點(diǎn)，全局極小值為f5(-32，-32)0.998。Shaffer函數(shù)F6：該函數(shù)在其定義域內(nèi)只具有一個全局極小點(diǎn)f6

3、(0，0)0。Shaffer函數(shù)F7：該函數(shù)在其定義域內(nèi)只具有一個全局極小點(diǎn)f7(0，0)0。Goldstein-Price函數(shù)：該函數(shù)在其定義域內(nèi)只具有一個全局極小點(diǎn)f(0，-1)3。Shubert函數(shù)：這是一個多峰值函數(shù)，在其定義域內(nèi)它總共有760個局部最小點(diǎn)，其中的18個點(diǎn)是全局最小點(diǎn)，全局最小值為f-186.731。六峰值駝背函數(shù)（Six-hump Camel Back Function）：該函數(shù)共有六個局部極小點(diǎn)，其中(-0.0898，0.7126)和(0.0898，-0.7126)為全局最小點(diǎn)，最小值為f(-0.0898，0.7126) f(0.0898，-0.7126) -1.0

4、31628。帶有復(fù)雜約束條件的函數(shù)(之一)：該函數(shù)的全局最小點(diǎn)為：f(1，1，1，1，1，1，1，1，3，3，3，1) = -15。帶有復(fù)雜約束條件的函數(shù)(之二)：該函數(shù)的全局最大點(diǎn)為：f(1，0，0) = 2.471428。4.3 De Jong的研究結(jié)論De Jong用來進(jìn)行函數(shù)優(yōu)化問題研究的研究對象是前面所介紹的De Jong測試函數(shù)F1F5。他采用了下面的一些研究方法：1編碼方法用二進(jìn)制編碼符號串來表示個體。2算法的影響參數(shù)群體大小M；交叉概率pc；變異概率pm；代溝G。3算法種類(子代群體復(fù)制策賂)R1：基本遺傳算法(比例選擇、單點(diǎn)交叉、基本位變異)；R2：保留最佳個體模型；R3：期

5、望值模型；R4：保留最佳期望值模型；R5：排擠因子模型；R6：廣義交叉模型。群體規(guī)模對離線性能的影響（優(yōu)化策略為R1，測試函數(shù)為F1）群體規(guī)模對等位基因損失的影響（優(yōu)化策略為R1，測試函數(shù)為F1）變異概率對等位基因損失的影響（優(yōu)化策略為R1，測試函數(shù)為F1）群體規(guī)模對在線性能的影響（優(yōu)化策略為R1，測試函數(shù)為F1）變異概率對在線性能的影響（優(yōu)化策略為R1，測試函數(shù)為F1）變異概率對離線性能的影響（優(yōu)化策略為R1，測試函數(shù)為F1）優(yōu)化策略R1，R2，R3的離線性能比較（測試函數(shù)為F1）優(yōu)化策略R1，R2，R3在基因損失方面的性能比較（測試函數(shù)為F1）排擠因子對離線性能的影響（優(yōu)化策略為R5，測試

6、函數(shù)為5）優(yōu)化策略R1，R2，R3的在線性能比較（測試函數(shù)為F1）經(jīng)過仔細(xì)分析和計(jì)算，De Jong得到了下述幾條重要的結(jié)論：結(jié)論1群體的規(guī)模越大，遺傳算法的離線性能越好，越容易收斂。結(jié)論2規(guī)模較大的群體，遺傳算法的初始在線性能較差；而規(guī)模較小的群體，遺傳算法的初始在線性能較好。結(jié)論3雖然變異概率的增大也會增加群體的多樣性，但它卻降低了遺傳算法的離線性能相在線性能，并且隨著變異概率的增大，遺傳算法的性能越來越接近于隨機(jī)搜索算法的性能。結(jié)論4使用保留最佳個體模型或期望值模型的遺傳算法比基本遺傳算法的性能有明顯的改進(jìn)。結(jié)論5對于廣義交叉算子，隨著交叉點(diǎn)數(shù)的增加會降低遺傳算法的在線性能和離線性能。這

7、些結(jié)論在遺傳算法的開發(fā)研究和實(shí)際應(yīng)用中具有重要的指導(dǎo)意義。4.4 多目標(biāo)優(yōu)化4.4.1 多目標(biāo)優(yōu)化問題的定義多目標(biāo)優(yōu)化問題一般可描述為下面的數(shù)學(xué)模型：式中，V-min表示向量極小化，即向量目標(biāo)中的各個子目標(biāo)函數(shù)都盡可能地極小化的意思。難點(diǎn)：在很多情況下，各個子目標(biāo)有可能是相互沖突的，一個子目標(biāo)的改善有可能會引起另一個子目標(biāo)性能的降低，也就是說，要同時使這多個子目標(biāo)都一起達(dá)到最優(yōu)值是不可能的，而只能是在它們中間進(jìn)行協(xié)調(diào)和折衷處理，使各個子目標(biāo)函數(shù)都盡可能地達(dá)到最優(yōu)。【定義4.4.1】：設(shè)是多目標(biāo)優(yōu)化模型的約束集，是多目標(biāo)優(yōu)化時的向量目標(biāo)函數(shù)， 。并且則稱解x1比解x2優(yōu)越?！径x4.4.2】：設(shè)

8、是多目標(biāo)優(yōu)化模型的約束集，是向量目標(biāo)函數(shù)，若，并且x*比X中的所有其他點(diǎn)都優(yōu)越，則稱x*是多目標(biāo)極小化模型的最優(yōu)解。由該定義可知，多目標(biāo)優(yōu)化問題的最優(yōu)解x*就是使向量目標(biāo)函數(shù)f(x)的每一個子目標(biāo)函數(shù)都同時到達(dá)最優(yōu)點(diǎn)的解，如左圖所示。顯然，在大多數(shù)情況下，多目標(biāo)優(yōu)化問題的最優(yōu)解是不存在的。 【定義4.4.3】：設(shè)是多目標(biāo)優(yōu)化模型的約束集，是向量目標(biāo)函數(shù)，若，并且不存在比更優(yōu)越的x，則稱為多目標(biāo)極小化模型的Pareto最優(yōu)解，或稱為非劣解。由該定義可知，多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解僅僅只是它的一個可以接受的“不壞”的解，并且通常的多目標(biāo)優(yōu)化問題大多都具有很多個Pareto最優(yōu)解，如右圖所示

9、。由上述三個定義可知，若一個多目標(biāo)優(yōu)化問題存在最優(yōu)解的話，則這個最優(yōu)解必定是Pareto最優(yōu)解，并且Pareto最優(yōu)解也只由這些最優(yōu)解所組成，再不包含有其他解。所以可以這么說，Pareto最優(yōu)解是多目標(biāo)優(yōu)化問題的合理的解集合。4.4.2 求解多目標(biāo)優(yōu)化問題的遺傳算法幾種主要的方法。1權(quán)重系數(shù)變化法對于一個多目標(biāo)優(yōu)化問題，若給其各個子目標(biāo)函數(shù)fi(x)，(i1，2，p)，賦予不同的權(quán)重wi(i1，2，p)，其中各wi的大小代表相應(yīng)子目標(biāo)fi(x)在多目標(biāo)優(yōu)化問題中的重要程度。則各個子目標(biāo)函數(shù)的線性加權(quán)和可表示為：若以這個線性加權(quán)和作為多目標(biāo)優(yōu)化問題的評價函數(shù)，則多目標(biāo)優(yōu)化問題就可轉(zhuǎn)化為單目標(biāo)優(yōu)化

10、問題。權(quán)重系數(shù)變化法就是在這個評價函數(shù)的基礎(chǔ)上，對每個個體取不同的權(quán)重系數(shù)，就可以利用通常的遺傳算法來求出多目標(biāo)優(yōu)化問題的多個Pareto最優(yōu)解。2并列選擇法并列選擇法的基本思想是：先將群體中的全部個體按子目標(biāo)函數(shù)的數(shù)目均等地劃分為一些子群體，對每個子群體分配一個子目標(biāo)函數(shù)，各個子目標(biāo)函數(shù)在其相應(yīng)的子群體中獨(dú)立地進(jìn)行選擇運(yùn)算，各自選擇出一些適應(yīng)度較高的個體組成一個新的子群體，然后再將所有這些新生成的子群體合并為一個完整的群體。在這個完整的群體中進(jìn)行交叉運(yùn)算和變異運(yùn)算，從而生成下一代的完整群體，如此這樣不斷地進(jìn)行“分割并列選擇合并”過程，最終可求出多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解。這種方法很容

11、易產(chǎn)生個別子目標(biāo)函數(shù)的極端最優(yōu)解，而要找到所有目標(biāo)函數(shù)在某種程度上較好的協(xié)調(diào)最優(yōu)解卻比較困難。3排序選擇法排序選擇法的基本思想是：基于“Pareto最優(yōu)個體”的概念來對群體中的各個個體進(jìn)行排序，依據(jù)這個排列次序來進(jìn)行進(jìn)化過程中的選擇運(yùn)算，從而使得排在前面的Pareto最優(yōu)個體將有更多的機(jī)會遺傳到下一代群體中。如此這樣經(jīng)過一定代數(shù)的循環(huán)之后，最終就可求出多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解。這里所謂的Pareto最優(yōu)個體，是指群體中的這樣一個或一些個體，群體中的其他個體都不比它或它們更優(yōu)越。需要說明的是，在群體進(jìn)化過程中所產(chǎn)生的Pareto最優(yōu)個體并不一定就對應(yīng)于多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解

12、。當(dāng)然，當(dāng)遺傳算法運(yùn)行結(jié)束時，我們需要取排在前面的幾個Pareto最優(yōu)個體，以它們所對應(yīng)的解來作為多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解。對群體中的所有個體進(jìn)行Pareto最優(yōu)個體排序的算法是：算法ParetoIndividual設(shè)置初始序號r = 1。求出群體中的Pareto最優(yōu)個體，定義這些個體的序號為r從群體中去掉Pareto最優(yōu)個體并更改序號r = r+1。轉(zhuǎn)到第步，直到處理完群體中的所有個體。排序選擇法僅僅度量了各個個體之間的優(yōu)越次序，而未度量各個個體的分散程度，所以它易于生很多個相似的Pareto最優(yōu)解，而難于生成分布較廣的Pareto最優(yōu)解。4共享函數(shù)法求解多目標(biāo)優(yōu)化問題時，一般希望

13、所得到的解能夠盡可能地分散在整個Pareto最優(yōu)解集合內(nèi)，而不是集中在其Pareto最優(yōu)解集合內(nèi)的某一個較小的區(qū)域上。為達(dá)到這個要求，可以利用小生境遺傳算法來求解多目標(biāo)優(yōu)化問題。這種求解多目標(biāo)優(yōu)化問題的方法稱為共享函數(shù)法，它將共享函數(shù)的概念引入求解多目標(biāo)優(yōu)化問題的遺傳算法中。在利用通常的遺傳算法求解最優(yōu)化問題時，算法并未限制相同個體或類似個體的數(shù)量。但當(dāng)在遺傳算法中引入小生境技術(shù)之后，算法對它們的數(shù)量就要加以限制，以便能夠產(chǎn)生出種類較多的不同的最優(yōu)解。對于某一個個體X而言，在它的附近還存在有多少種、多大程度相似的個體，這是可以度量的，這種度量值稱之為小生境數(shù)(Niche Count)（又有叫共

14、享度）。小生境數(shù)有很多種不同的度量計(jì)算方法，一般可定義為：式中，s(d)為共享函數(shù)，它是個體之間距離d的單調(diào)遞減函數(shù)。例如，共享函數(shù)s(d)的一種定義是：式中，d(X, Y)是兩個個體X、Y之間的海明距離，0是預(yù)先指定的一個表示小生境范圍的參數(shù)。在計(jì)算出各個個體的小生境數(shù)之后，可以使小生境數(shù)較小的個體能夠有更多的機(jī)會被選中遺傳到下一代群體中，即相似個體較少的個體能夠有更多的機(jī)會被遺傳到下一代群體中，這樣也就增加了群體的多樣性，相應(yīng)地也會增加解的多樣性。下面是一種遺傳算法中的選擇操作方法，它綜合運(yùn)用聯(lián)賽選擇和共享函數(shù)的思想，來選擇當(dāng)前群體中的優(yōu)良個體遺傳到下一代群體中。算法Tournament

15、Sharing Selection從群體中隨機(jī)選取k個個體組成個體比較集合C，其中k是預(yù)先指定的一個表示比較集合規(guī)模的常數(shù)。從群體中隨機(jī)選擇2個個體組成個體聯(lián)賽集合T。分別比較個體聯(lián)賽集合T中的2個個體與個體比較集合C中各個個體之間的優(yōu)越關(guān)系，根據(jù)這個比較結(jié)果，按下述方法從個體聯(lián)賽集合T中選擇出一個個體遺傳到下一代群體中。如果集合T中的一個個體(記為X)比集合C中的所有個體都優(yōu)越，而集合T中的另一個個體不比集合C中的所有個體優(yōu)越，則將個體X遺傳到下一代群體中；如果由上面的一種情況未能選擇出一個個體，則利用共享函數(shù)的概念從集合T中選擇出一個小生境數(shù)較小的個體遺傳到下一代群體中。優(yōu)點(diǎn)：它能夠得到多

16、種不同的Pareto最優(yōu)解；缺點(diǎn)：由于每次進(jìn)行選擇操作時都需要進(jìn)行大量的個體之間優(yōu)越關(guān)系的評價和比較運(yùn)算，所以使得算法的搜索效率較低。5混合法前面所介紹的幾種求解多目標(biāo)優(yōu)化問題的遺傳算法各有各的優(yōu)、缺點(diǎn)。如果混合使用上述幾種求解多目標(biāo)優(yōu)化問題的方法，將有可能盡量地克服各自的缺點(diǎn)，而充分地發(fā)揮各自的優(yōu)點(diǎn)。下面介紹一種使用遺傳算法求解多目標(biāo)優(yōu)化問題的混合方法。該方法的主要思想是：選擇算子的主體使用并列選擇法，然后通過引入保留最佳個體和共享函數(shù)的思想來彌補(bǔ)僅僅只使用并列選擇法的不足之處。算法的主要過程如下：算法Hybrid Selection并列選擇過程：按所求多目標(biāo)優(yōu)化問題的子目標(biāo)函致的個數(shù)，將整個群體均等地劃分為一些子群體，各個子目標(biāo)函數(shù)在相應(yīng)的子群體中產(chǎn)生其下一代子群體。保留Pareto最優(yōu)個體過程：對于各個子群體中的Pareto最優(yōu)個體，不讓其參與個體的交叉運(yùn)算和變異運(yùn)算，而是將這個或這些Pareto最優(yōu)個體直接保留到下一代于群體中。共享函數(shù)處理過程：若所得到的Pareto最優(yōu)個體的數(shù)量已超過規(guī)定的群體規(guī)模，則需要利用共享函數(shù)的處理方法來對這些Pareto最優(yōu)個體進(jìn)行挑選，以形成規(guī)