|
遺傳算法的概念最早是由Bagley J.D 于1967年提出的。后來(lái)Michigan大學(xué)的J.H.Holland教授于1975年開(kāi)始對(duì)遺傳算法（Genetic Algorithm, GA）的機(jī)理進(jìn)行系統(tǒng)化的研究。遺傳算法是對(duì)達(dá)爾文生物進(jìn)化理論的簡(jiǎn)單模擬，其遵循“適者生存”、“優(yōu)勝略汰”的原理。遺傳算法模擬一個(gè)人工種群的進(jìn)化過(guò)程，并且通過(guò)選擇、雜交以及變異等機(jī)制，種群經(jīng)過(guò)若干代以后，總是達(dá)到最優(yōu)（或近最優(yōu)）的狀態(tài)。 自從遺傳算法被提出以來(lái)，其得到了廣泛的應(yīng)用，特別是在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制等領(lǐng)域，遺傳算法更是發(fā)揮了重大的作用，大大提高了問(wèn)題求解的效率。遺傳算法也是當(dāng)前“軟計(jì)算”領(lǐng)域的重要研究課題。 本文首先結(jié)合MATLAB對(duì)遺傳算法實(shí)現(xiàn)過(guò)程進(jìn)行詳細(xì)的分析，然后通過(guò)1個(gè)實(shí)際的函數(shù)優(yōu)化案例對(duì)其應(yīng)用進(jìn)行探討。 1. 遺傳算法實(shí)現(xiàn)過(guò)程 現(xiàn)實(shí)生活中很多問(wèn)題都可以轉(zhuǎn)換為函數(shù)優(yōu)化問(wèn)題，所以本文將以函數(shù)優(yōu)化問(wèn)題作為背景，對(duì)GA的實(shí)現(xiàn)過(guò)程進(jìn)行探討。大部分函數(shù)優(yōu)化問(wèn)題都可以寫成求最大值或者最小值的形式，為了不是一般性，我們可以將所有求最優(yōu)值的情況都轉(zhuǎn)換成求最大值的形式，例如，求函數(shù)f(x)的最大值，
若是求函數(shù)f(x)的最小值，可以將其轉(zhuǎn)換成g(x)=-f(x)，然后求g(x)的最大值，
這里x可以是一個(gè)變量，也可是是一個(gè)由k個(gè)變量組成的向量, x=(x1, x2, …, xk)。每個(gè)xi, i=1,2,…,k, 其定義域?yàn)?em>Di，Di=[ai, bi]。 一般規(guī)定f(x)在其定義域內(nèi)只取正值，若不滿足，可以將其轉(zhuǎn)換成以下形式，
其中C是一個(gè)正常數(shù)。 1.1 編碼與解碼 要實(shí)現(xiàn)遺傳算法首先需要弄清楚如何對(duì)求解問(wèn)題進(jìn)行編碼和解碼。對(duì)于函數(shù)優(yōu)化問(wèn)題，一般來(lái)說(shuō)，有兩種編碼方式，一是實(shí)數(shù)編碼，一是二進(jìn)制編碼，兩者各有優(yōu)缺點(diǎn)，二進(jìn)制編碼具有穩(wěn)定性高、種群多樣性大等優(yōu)點(diǎn)，但是需要的存儲(chǔ)空間大，需要解碼過(guò)程并且難以理解；而實(shí)數(shù)編碼直接用實(shí)數(shù)表示基因，容易理解并且不要解碼過(guò)程，但是容易過(guò)早收斂，從而陷入局部最優(yōu)。本文以最常用的二進(jìn)制編碼為例，說(shuō)明遺傳編碼的過(guò)程。 從遺傳算法求解的過(guò)程來(lái)看，需要處理好兩個(gè)空間的問(wèn)題，一個(gè)是編碼空間，另一個(gè)是解空間，如下圖所示
從解空間到編碼空間的映射過(guò)程成為編碼過(guò)程；從編碼空間到解空間的映射過(guò)程成為解碼過(guò)程。下面就以求解一個(gè)簡(jiǎn)單的一維函數(shù)f(x) = -(x-1)^2+4, x的取值范圍為[-1,3]最大值為例，來(lái)說(shuō)明編碼及解碼過(guò)程。 編碼： 在編碼之前需要確定求解的精度，在這里，我們?cè)O(shè)定求解的精度為小數(shù)點(diǎn)后四位，即1e-4。這樣可以將每個(gè)自變量xi的解空間劃分為 解碼： 解碼即將編碼空間中的基因串翻譯成解空間中的自變量的實(shí)際值的過(guò)程。對(duì)于二進(jìn)制編碼而言，每個(gè)二進(jìn)制基因串都可以這樣翻譯成一個(gè)十進(jìn)制實(shí)數(shù)值， 1.2 初始化種群 在開(kāi)始遺傳算法迭代過(guò)程之前，需要對(duì)種群進(jìn)行初始化。設(shè)種群大小為pop_size，每個(gè)染色體或個(gè)體的長(zhǎng)度為chromo_size，種群的大小決定了種群的多樣性，而染色體的長(zhǎng)度則是由前述的編碼過(guò)程決定的。一般隨機(jī)生成初始種群，但是如果知道種群的實(shí)際分布，也可以按照此分布來(lái)生成初始種群。假設(shè)生成的初始種群為(v1, v2, …, vpop_size)。 1.3 選擇操作 選擇操作即從前代種群中選擇個(gè)體到下一代種群的過(guò)程。一般根據(jù)個(gè)體適應(yīng)度的分布來(lái)選擇個(gè)體。以初始種群(v1, v2, …, vpop_size)為例，假設(shè)每個(gè)個(gè)體的適應(yīng)度為(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般適應(yīng)度可以按照解碼的過(guò)程進(jìn)行計(jì)算。以輪盤賭的方式選擇個(gè)體，如下圖
隨機(jī)轉(zhuǎn)動(dòng)一下輪盤，當(dāng)輪盤停止轉(zhuǎn)動(dòng)時(shí)，若指針指向某個(gè)個(gè)體，則該個(gè)體被選中。很明顯，具有較高適應(yīng)度的個(gè)體比具有較低適應(yīng)度的個(gè)體更有機(jī)會(huì)被選中。但是這種選擇具有隨機(jī)性，在選擇的過(guò)程中可能會(huì)丟失掉比較好的個(gè)體，所以可以使用精英機(jī)制，將前代最優(yōu)個(gè)體直接選到下一代中。 輪盤賭選擇具體算法如下（這里假定種群中個(gè)體是按照適應(yīng)度從小到大進(jìn)行排列的，如果不是，可以按照某種排序算法對(duì)種群個(gè)體進(jìn)行重排）： Selection Algorithm var pop, pop_new;/*pop為前代種群，pop_new為下一代種群*/ var fitness_value, fitness_table;/*fitness_value為種群的適應(yīng)度，fitness_table為種群累積適應(yīng)度*/ for i=1:pop_size r = rand*fitness_table(pop_size);/*隨機(jī)生成一個(gè)隨機(jī)數(shù)，在0和總適應(yīng)度之間，因?yàn)閒itness_table(pop_size)為最后一個(gè)個(gè)體的累積適應(yīng)度，即為總適應(yīng)度*/ first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; /*下面按照排中法選擇個(gè)體*/ while (first <= last) && (idx == -1) if r > fitness_table(mid) first = mid; elseif r < fitness_table(mid) last = mid; else idx = mid; break; end if mid = round((last+first)/2); if (last - first) == 1 idx = last; break; end if end while for j=1:chromo_size pop_new(i,j)=pop(idx,j); end for end for /*是否精英選擇*/ if elitism p = pop_size-1; else p = pop_size; end if for i=1:p for j=1:chromo_size pop(i,j) = pop_new(i,j);/*若是精英選擇，則只將pop_new前pop_size-1個(gè)個(gè)體賦給pop，最后一個(gè)為前代最優(yōu)個(gè)體保留*/ end for end for 1.3 交叉操作 交叉操作是對(duì)任意兩個(gè)個(gè)體進(jìn)行的（在這里我們實(shí)現(xiàn)的算法是直接對(duì)相鄰的兩個(gè)個(gè)體進(jìn)行的）。隨機(jī)選擇兩個(gè)個(gè)體，如下圖所示
然后隨機(jī)生成一個(gè)實(shí)數(shù)0<=r<=1, 如果r<cross_rate， 0<cross_rate<1為交叉概率，則對(duì)這兩個(gè)個(gè)體進(jìn)行交叉，否則則不進(jìn)行。如果需要進(jìn)行交叉，再隨機(jī)選擇交叉位置(rand*chromo_size)，如果等于0或者1，將不進(jìn)行交叉。否則將交叉位置以后的二進(jìn)制串進(jìn)行對(duì)換（包括交叉位置）。（注意：有時(shí)候還可以進(jìn)行多點(diǎn)交叉，但是這里只討論單點(diǎn)交叉的情況） 單點(diǎn)交叉具體算法如下： Crossover algorithm for i=1:2:pop_size if(rand < cross_rate)/*cross_rate為交叉概率*/ cross_pos = round(rand * chromo_size);/*交叉位置*/ if or (cross_pos == 0, cross_pos == 1) continue;/*若交叉位置為0或1，則不進(jìn)行交叉*/ end if for j=cross_pos:chromo_size pop(i,j)<->pop(i+1,j);/*交換*/ end for end if end for 1.4 變異操作 變異操作是對(duì)單個(gè)個(gè)體進(jìn)行的。首先生成一個(gè)隨機(jī)實(shí)數(shù)0<=r<=1, 如果r<mutate_rate，則對(duì)此個(gè)體進(jìn)行變異操作， 0<mutate_rate<1為變異概率，一般為一個(gè)比較小的實(shí)數(shù)。對(duì)每一個(gè)個(gè)體，進(jìn)行變異操作，如下圖所示
如個(gè)體需要進(jìn)行變異操作，首先需要確定變異位置(rand*chromo_size)，若為0則不進(jìn)行變異，否則則對(duì)該位置的二進(jìn)制數(shù)字進(jìn)行變異：1變成0, 0變成1.（當(dāng)然也可以選擇多點(diǎn)進(jìn)行變異） 單點(diǎn)變異的具體算法描述如下： Mutation algorithm for i=1:pop_size if rand < mutate_rate/*mutate_rate為變異概率*/ mutate_pos = round(rand*chromo_size);/*變異位置*/ if mutate_pos == 0 continue;/*若變異位置為0，則不進(jìn)行變異*/ end if pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*將變異位置上的數(shù)字至反*/ end if end for 1.5 遺傳算法流程 遺傳算法計(jì)算流程圖如下圖所示
1.6 MATLAB程序?qū)崿F(xiàn) 初始化： %初始化種群 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 function initilize(pop_size, chromo_size) global pop; for i=1:pop_size for j=1:chromo_size pop(i,j) = round(rand); end end clear i; clear j; 計(jì)算適應(yīng)度：（該函數(shù)應(yīng)該根據(jù)具體問(wèn)題進(jìn)行修改，這里優(yōu)化的函數(shù)是前述的一維函數(shù)） %計(jì)算種群個(gè)體適應(yīng)度，對(duì)不同的優(yōu)化目標(biāo)，此處需要改寫 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 function fitness(pop_size, chromo_size) global fitness_value; global pop; global G; for i=1:pop_size fitness_value(i) = 0.; end for i=1:pop_size for j=1:chromo_size if pop(i,j) == 1 fitness_value(i) = fitness_value(i)+2^(j-1); end end fitness_value(i) = -1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1); fitness_value(i) = -(fitness_value(i)-1).^2+4; end clear i; clear j; 對(duì)個(gè)體按照適應(yīng)度大小進(jìn)行排序： %對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序，并且保存最佳個(gè)體 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 function rank(pop_size, chromo_size) global fitness_value; global fitness_table; global fitness_avg; global best_fitness; global best_individual; global best_generation; global pop; global G; for i=1:pop_size fitness_table(i) = 0.; end min = 1; temp = 1; temp1(chromo_size)=0; for i=1:pop_size min = i; for j = i+1:pop_size if fitness_value(j)<fitness_value(min); min = j; end end if min~=i temp = fitness_value(i); fitness_value(i) = fitness_value(min); fitness_value(min) = temp; for k = 1:chromo_size temp1(k) = pop(i,k); pop(i,k) = pop(min,k); pop(min,k) = temp1(k); end end end for i=1:pop_size if i==1 fitness_table(i) = fitness_table(i) + fitness_value(i); else fitness_table(i) = fitness_table(i-1) + fitness_value(i); end end fitness_table fitness_avg(G) = fitness_table(pop_size)/pop_size; if fitness_value(pop_size) > best_fitness best_fitness = fitness_value(pop_size); best_generation = G; for j=1:chromo_size best_individual(j) = pop(pop_size,j); end end clear i; clear j; clear k; clear min; clear temp; clear temp1; 選擇操作： %輪盤賭選擇操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %cross_rate: 是否精英選擇 function selection(pop_size, chromo_size, elitism) global pop; global fitness_table; for i=1:pop_size r = rand * fitness_table(pop_size); first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; while (first <= last) && (idx == -1) if r > fitness_table(mid) first = mid; elseif r < fitness_table(mid) last = mid; else idx = mid; break; end mid = round((last+first)/2); if (last - first) == 1 idx = last; break; end end for j=1:chromo_size pop_new(i,j)=pop(idx,j); end end if elitism p = pop_size-1; else p = pop_size; end for i=1:p for j=1:chromo_size pop(i,j) = pop_new(i,j); end end clear i; clear j; clear pop_new; clear first; clear last; clear idx; clear mid; 交叉操作： %單點(diǎn)交叉操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %cross_rate: 交叉概率 function crossover(pop_size, chromo_size, cross_rate) global pop; for i=1:2:pop_size if(rand < cross_rate) cross_pos = round(rand * chromo_size); if or (cross_pos == 0, cross_pos == 1) continue; end for j=cross_pos:chromo_size temp = pop(i,j); pop(i,j) = pop(i+1,j); pop(i+1,j) = temp; end end end clear i; clear j; clear temp; clear cross_pos; 變異操作： %單點(diǎn)變異操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %cross_rate: 變異概率 function mutation(pop_size, chromo_size, mutate_rate) global pop; for i=1:pop_size if rand < mutate_rate mutate_pos = round(rand*chromo_size); if mutate_pos == 0 continue; end pop(i,mutate_pos) = 1 - pop(i, mutate_pos); end end clear i; clear mutate_pos; 打印算法迭代過(guò)程： %打印算法迭代過(guò)程 %generation_size: 迭代次數(shù) function plotGA(generation_size) global fitness_avg; x = 1:1:generation_size; y = fitness_avg; plot(x,y) 算法主函數(shù)： %遺傳算法主函數(shù) %pop_size: 輸入種群大小 %chromo_size: 輸入染色體長(zhǎng)度 %generation_size: 輸入迭代次數(shù) %cross_rate: 輸入交叉概率 %cross_rate: 輸入變異概率 %elitism: 輸入是否精英選擇 %m: 輸出最佳個(gè)體 %n: 輸出最佳適應(yīng)度 %p: 輸出最佳個(gè)體出現(xiàn)代 %q: 輸出最佳個(gè)體自變量值 function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism) global G ; %當(dāng)前代 global fitness_value;%當(dāng)前代適應(yīng)度矩陣 global best_fitness;%歷代最佳適應(yīng)值 global fitness_avg;%歷代平均適應(yīng)值矩陣 global best_individual;%歷代最佳個(gè)體 global best_generation;%最佳個(gè)體出現(xiàn)代 fitness_avg = zeros(generation_size,1); disp "hhee" fitness_value(pop_size) = 0.; best_fitness = 0.; best_generation = 0; initilize(pop_size, chromo_size);%初始化 for G=1:generation_size fitness(pop_size, chromo_size); %計(jì)算適應(yīng)度 rank(pop_size, chromo_size); %對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序 selection(pop_size, chromo_size, elitism);%選擇操作 crossover(pop_size, chromo_size, cross_rate);%交叉操作 mutation(pop_size, chromo_size, mutate_rate);%變異操作 end plotGA(generation_size);%打印算法迭代過(guò)程 m = best_individual;%獲得最佳個(gè)體 n = best_fitness;%獲得最佳適應(yīng)度 p = best_generation;%獲得最佳個(gè)體出現(xiàn)代 %獲得最佳個(gè)體變量值，對(duì)不同的優(yōu)化目標(biāo)，此處需要改寫 q = 0.; for j=1:chromo_size if best_individual(j) == 1 q = q+2^(j-1); end end q = -1+q*(3.-(-1.))/(2^chromo_size-1); clear i; clear j; 2. 案例研究 對(duì)上一節(jié)中的函數(shù)進(jìn)行優(yōu)化，設(shè)置遺傳算法相關(guān)參數(shù)，程序如下 function run_ga() elitism = true;%選擇精英操作 pop_size = 20;%種群大小 chromo_size = 16;%染色體大小 generation_size = 200;%迭代次數(shù) cross_rate = 0.6;%交叉概率 mutate_rate = 0.01;%變異概率 [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism); disp "最優(yōu)個(gè)體" m disp "最優(yōu)適應(yīng)度" n disp "最優(yōu)個(gè)體對(duì)應(yīng)自變量值" q disp "得到最優(yōu)結(jié)果的代數(shù)" p clear; 結(jié)果如下： "最優(yōu)個(gè)體" m = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 "最優(yōu)適應(yīng)度" n = 4.0000 "最優(yōu)個(gè)體對(duì)應(yīng)自變量值" q = 1.0000 "得到最優(yōu)結(jié)果的代數(shù)" p = 74 此結(jié)果非常準(zhǔn)確。 算法迭代過(guò)程圖形：
從上圖中可以看出，隨著迭代次數(shù)的增加，算法逐漸收斂。 3. 總結(jié) 本文詳細(xì)的介紹了簡(jiǎn)單遺傳算法的實(shí)現(xiàn)過(guò)程，并以一個(gè)簡(jiǎn)單的函數(shù)優(yōu)化作為案例說(shuō)明了其應(yīng)用。但是由于該測(cè)試函數(shù)過(guò)于簡(jiǎn)單，在實(shí)際的應(yīng)用過(guò)程中，還需要對(duì)相關(guān)參數(shù)進(jìn)行調(diào)整，使其效率得到更大的提高。 |
|
|
