第28章基于改進(jìn)的遺傳算法的城市交通信號(hào)優(yōu)化

1、 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用第第28章章 基于改進(jìn)的遺傳算法的城市交通信基于改進(jìn)的遺傳算法的城市交通信號(hào)優(yōu)化分析號(hào)優(yōu)化分析 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.1 遺傳算法基本理論遺傳算法基本理論遺傳學(xué)認(rèn)為，遺傳是作為一種指令遺傳碼封裝在每個(gè)細(xì)胞中，并以基因的形式包含在染色體中，每個(gè)基因有特殊的位置并控制某個(gè)特殊的性質(zhì)。每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境有一定的適應(yīng)性?；螂s交和突變可能產(chǎn)生對(duì)環(huán)境適應(yīng)性強(qiáng)的后代，通過(guò)優(yōu)勝劣汰的自然選擇，適應(yīng)度值高的基因結(jié)構(gòu)就保存下來(lái)。遺傳算法借鑒“適者生存”的遺傳遺傳學(xué)理論，

2、將優(yōu)化問(wèn)題的求解表示成“染色體”的“適者生存”過(guò)程，通過(guò)“染色體”群的一代代復(fù)制、交叉、變異的進(jìn)化，最終得到的是最適應(yīng)環(huán)境的個(gè)體，從而得到問(wèn)題的最優(yōu)解或者滿意解。這是一種高度并行、隨機(jī)和自適應(yīng)的通用的優(yōu)化算法。遺傳算法的一系列優(yōu)點(diǎn)使它近年來(lái)越來(lái)越受到重視，在解決眾多領(lǐng)域的優(yōu)化問(wèn)題中得到了廣泛的應(yīng)用，其中也包括在交通領(lǐng)域的成功應(yīng)用。 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.1.3 遺傳算法的特點(diǎn)遺傳算法的特點(diǎn)遺傳算法是模擬生物自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。是一類(lèi)可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法，與其他一些優(yōu)化算法相

3、比，它具有很多特點(diǎn)。傳統(tǒng)的優(yōu)化算法主要有三種：枚舉法、啟發(fā)式算法和搜索算法：1枚舉法枚舉法枚舉法在可行解集合內(nèi)枚舉所有可行解，以求出精確最優(yōu)解。對(duì)于連續(xù)函數(shù)，該方法要求先對(duì)其進(jìn)行離散化處理，這樣就可能因離散處理而永遠(yuǎn)達(dá)不到最優(yōu)解。此外，當(dāng)枚舉空間比較大時(shí)，該算法的求解效率非常低，極其耗時(shí)。2啟發(fā)式算法啟發(fā)式算法啟發(fā)式算法尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，以找到一個(gè)最優(yōu)解或近似最優(yōu)解。啟發(fā)式算法的求解效率比較高，但對(duì)每一個(gè)需求解的問(wèn)題必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則一般無(wú)通用性，不適合于其他問(wèn)題。3搜索算法搜索算法搜索算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作，以找到問(wèn)題的最優(yōu)解或者近似

4、最優(yōu)解。搜索算法雖然保證不了一定能夠得到問(wèn)題的最優(yōu)解，但若適當(dāng)?shù)睦靡恍﹩l(fā)知識(shí)，就可在近似解的質(zhì)量和效率上達(dá)到一種較好的平衡。 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.2 基本遺傳算法的工作流程基本遺傳算法的工作流程 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.3.2 適應(yīng)度函數(shù)適應(yīng)度函數(shù)若目標(biāo)函數(shù)為最小化問(wèn)題，則 maxmax,0,cfxfxcFit fxothers若目標(biāo)函數(shù)為最大化問(wèn)題，則 minmin,0,othersf xcf xcFit f x（3）若目標(biāo)函數(shù)為最小問(wèn)題，則 11Fit f xcf x

5、 若目標(biāo)函數(shù)為最大化問(wèn)題，則 11Fit f xcf x 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.3.3 選擇算子選擇算子選擇又稱為復(fù)制，是在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過(guò)程。遺傳算法使用選擇算子來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，根據(jù)每個(gè)個(gè)體的適應(yīng)度大小選擇，適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；反之亦然。這樣就可以使得群體中個(gè)體的適應(yīng)度值不斷接近最優(yōu)解。選擇算子的確定的好壞，直接影響到遺傳算法的計(jì)算結(jié)果。下面介紹幾種典型常用的選擇算子：1輪盤(pán)賭選擇輪盤(pán)賭選擇2隨機(jī)競(jìng)爭(zhēng)選擇隨機(jī)競(jìng)爭(zhēng)選擇3隨機(jī)遍歷選擇隨機(jī)遍歷選擇4排序選擇排序選擇5聯(lián)

6、賽選擇聯(lián)賽選擇 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.3.4 交叉算子交叉算子下面介紹幾種適合于二進(jìn)制編碼個(gè)體或十進(jìn)制編碼個(gè)體的交叉算子。l單點(diǎn)交叉單點(diǎn)交叉單點(diǎn)交叉（One-point Crossover）又稱為簡(jiǎn)單交叉，是最常用和最基本的交叉操作算子。它以二值串中的隨機(jī)選擇點(diǎn)開(kāi)始，對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。2兩點(diǎn)交叉與多點(diǎn)交叉兩點(diǎn)交叉與多點(diǎn)交叉兩點(diǎn)交叉（Two-point Crossover）是指在個(gè)體編碼串中隨即設(shè)置兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。兩點(diǎn)交叉的具體過(guò)

7、程是：（1）在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨即設(shè)置兩個(gè)交叉點(diǎn)。（2）交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。 3均勻交叉均勻交叉 均勻交叉是指兩個(gè)配對(duì)個(gè)體的每個(gè)基因座上基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。其具體運(yùn)算可通過(guò)設(shè)置一屏蔽字來(lái)確定新個(gè)體的各個(gè)基因如何由哪一個(gè)父代個(gè)體來(lái)提供。4算術(shù)交叉算術(shù)交叉算術(shù)交叉是指由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。為了能夠進(jìn)行線性組合運(yùn)算，算術(shù)交叉的操作對(duì)象一般是浮點(diǎn)數(shù)編碼所表示的個(gè)體。 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.3.5 變異算子變異算子遺傳算法中所謂的變異運(yùn)算，是指將個(gè)體染

8、色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。變異是遺傳算法生成新個(gè)體的主要方法之一，變異運(yùn)算可以使算法在運(yùn)行過(guò)程中維持種群的多樣性，有效避免早熟，起到改善遺傳算法局部搜索能力的作用。遺傳算法中變異算子也應(yīng)根據(jù)不同的要求進(jìn)行選擇和設(shè)計(jì)，下面是幾種常用的變異算子：l基本位變異基本位變異2均勻變異均勻變異3邊界變異邊界變異邊界變異操作是上述均勻變異操作的一個(gè)變形。在進(jìn)行邊界變異操作時(shí)，隨機(jī)地取基因座的兩個(gè)對(duì)應(yīng)邊界基因值之一去替代原有的基因值。當(dāng)變量的取值范圍特別寬，并且無(wú)其他約束條件時(shí)，邊界變異會(huì)帶來(lái)不好的作用。但它特別適用于最優(yōu)點(diǎn)位于或者接近于可行解的邊

9、界時(shí)的一類(lèi)問(wèn)題。 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.5 遺傳算法的改進(jìn)遺傳算法的改進(jìn)針對(duì)適應(yīng)度值標(biāo)定問(wèn)題本章提出以下計(jì)算公式：minminmax1fffff 圖28- 2 適應(yīng)度值的標(biāo)定 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用自適應(yīng)遺傳算法在保持群體多樣性的同時(shí)，保證遺傳算法的收斂性?？捎孟旅鎯晒絼?dòng)態(tài)調(diào)整個(gè)體的交叉變異概率。1maxmaxmin2,avgcavgkffffffpkff3maxmax4,avgavgmavgkffffffpkff（1）當(dāng)適應(yīng)度值低于平均適應(yīng)度值時(shí)，說(shuō)明該個(gè)體是性能不好的個(gè)體，對(duì)

10、它就采用較大的交叉率和變異率；如果適應(yīng)度值高于平均適應(yīng)度值，說(shuō)明該個(gè)體性能優(yōu)良，對(duì)它就根據(jù)其適應(yīng)度值取相應(yīng)的交叉率和變異率。（2）當(dāng)適應(yīng)度值越接近最大適應(yīng)度值時(shí)，交叉率和變異率就越??；（3）當(dāng)適應(yīng)度值等于最大適應(yīng)度值時(shí)，交叉率和變異率的值為零。這種調(diào)整方法對(duì)于群體處于進(jìn)化后期比較合適，但對(duì)于進(jìn)化初期不利，因?yàn)檫M(jìn)化初期群體中的較優(yōu)的個(gè)體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時(shí)的優(yōu)良個(gè)體不一定是優(yōu)化的全局最優(yōu)解，這容易使進(jìn)化走向局部最優(yōu)解的可能性增加。 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用28.6 基于改進(jìn)遺傳算法的道路交通信號(hào)優(yōu)化基于改進(jìn)遺傳算法的道路交通信號(hào)

11、優(yōu)化41,max3 100.85iiiiieCLetCLCytg 22421112 121ijiijijiijijijxCDqxqx 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用22421112 121ijiijijiijijijxCDqxqx123412341303813026332259261303833223733130382622442213038263333ttttCLtttt2改進(jìn)的遺傳算法改進(jìn)的遺傳算法 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用2改進(jìn)的遺傳算法改進(jìn)的遺傳算法minminmax1fffff % 計(jì)算

12、適應(yīng)度 for j=1:sizepop x=individuals.chrom(j,:); % 解碼 individuals.fitness(j)=fun(x); % 染色體的適應(yīng)度 end fmax = max(individuals.fitness); % 適應(yīng)度最大值 fmin = min(individuals.fitness); % 適應(yīng)度最小值 favg = mean(individuals.fitness); % 適應(yīng)度平均值 individuals.fitness = (individuals.fitness + abs(fmin)./(fmax+fmin+delta); %適

13、應(yīng)度標(biāo)定 % 找到最小和最大適應(yīng)度的染色體及它們?cè)诜N群中的位置 newbestfitness,newbestindex=min(individuals.fitness); worestfitness,worestindex=max(individuals.fitness); % 代替上一次進(jìn)化中最好的染色體 if bestfitnessnewbestfitness bestfitness=newbestfitness; bestchrom=individuals.chrom(newbestindex,:); end 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用1

14、maxmaxmin2,avgcavgkffffffpkff3maxmax4,avgavgmavgkffffffpkff pick=rand(1,2); while prod(pick)=0 pick=rand(1,2); end index=ceil(pick.*sizepop); f1 = fun( chrom(index(1),:) ); % 個(gè)體適應(yīng)度值 f2 = fun( chrom(index(2),:) ); % 個(gè)體適應(yīng)度值 f3 = max(f1,f2); % 兩者中大者 if f3=favg pcross = k1*(fmax - f3)./(fmax-favg); else pcross = k2; end 第二十八章第二十八章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)