寫在前面：隨著研究問題的復(fù)雜化，有的時(shí)候會(huì)有一些尋找最優(yōu)參數(shù)的科研任務(wù)，這就需要我們會(huì)使用一些優(yōu)化方法，而遺傳算法則是眾多優(yōu)化算法中最基礎(chǔ)和最常見的方法。本次分享依舊屬于科普貼，擬分兩期給初次接觸優(yōu)化算法的同學(xué)介紹遺傳算法，第一期借助一個(gè)遺傳算法的案例代碼，對(duì)遺傳算法的原理進(jìn)行簡單介紹；第二期借助GA工具箱，對(duì)遺傳算法程序進(jìn)行優(yōu)化與簡化，以提高遺傳算法運(yùn)行效率和查錯(cuò)效率。

遺傳算法

我們都知道進(jìn)化論的基本規(guī)則就是“自然選擇，適者生存”，每個(gè)個(gè)體通過交配繁衍出后代，后代在成長過程中經(jīng)過自然法則的篩選而淘汰掉部分個(gè)體，而那些擁有優(yōu)良性狀的個(gè)體得以存活并且通過繁衍使得優(yōu)秀遺傳信息得以保留和擴(kuò)散。

遺傳算法（Genetic Algorithm, GA）正是借鑒了這種思想。我們把生物的進(jìn)化過程抽象成一個(gè)數(shù)學(xué)模型，生物進(jìn)化指的是初始種群里擁有各種各樣的同種生物，經(jīng)過繁衍和自然選擇得到的最終種群里，每個(gè)個(gè)體或者說絕大部分是最適應(yīng)環(huán)境的優(yōu)秀個(gè)體。那么對(duì)應(yīng)的數(shù)學(xué)模型則可簡化成，初始集合中包含一定數(shù)量的隨機(jī)數(shù)，而這些隨機(jī)數(shù)通過一定規(guī)則反復(fù)迭代計(jì)算，然后設(shè)計(jì)一種個(gè)體的評(píng)價(jià)體系，把不符合規(guī)則或者評(píng)分比較低的個(gè)體淘汰，得到的最終集合里絕大部分是最符合規(guī)則的數(shù)。

有了生物進(jìn)化和對(duì)應(yīng)的抽象數(shù)學(xué)模型之后，我們用一個(gè)圖示來簡要說明遺傳算法中的一些術(shù)語和流程。

下面我們用一個(gè)小案例以及代碼，來詳細(xì)展示遺傳算法的流程以及代碼的書寫。

問題：（二元函數(shù)在給定區(qū)間的最值）

原函數(shù)在區(qū)間上的圖像如圖所示：

syms x y

x=-1:0.01:12;

y=4:0.01:6;

[X,Y]=meshgrid(x,y);

f=X.*sin(pi.*X)+Y.*sin(exp(Y));

mesh(X,Y,f);

可以看出，函數(shù)是一個(gè)在x方向上震蕩，同時(shí)在y方向上震蕩的圖形，并且該函數(shù)是一個(gè)超越函數(shù)，用常規(guī)求最大值方法比如求導(dǎo)或者離散方法求解起來十分復(fù)雜。

下面我們用遺傳算法來求解該問題。

首先，我們需要設(shè)置初始種群的大小還有每個(gè)個(gè)體遺傳信息的編碼（coding）與解碼（decoding）。初始種群大小可以根據(jù)實(shí)際問題自由設(shè)定，較大種群包含的遺傳信息更多，但是迭代起來更慢。仿照DNA的結(jié)構(gòu)，DNA含有四種堿基，這四種堿基可以對(duì)應(yīng)生成人體所有的蛋白質(zhì)，所以一個(gè)DNA序列可以認(rèn)為是一種四進(jìn)制編碼。數(shù)學(xué)中常見的進(jìn)制編碼有二進(jìn)制編碼，八進(jìn)制編碼，十進(jìn)制編碼，十六進(jìn)制編碼，計(jì)算機(jī)的底層存儲(chǔ)通常是二進(jìn)制編碼，所以這里我們選用二進(jìn)制編碼比較合適，這樣計(jì)算起來會(huì)快很多。那么我們需要進(jìn)行編碼與解碼的過程，編碼則是把性狀變?yōu)檫z傳信息，而解碼則是把遺傳信息變?yōu)樾誀?。以x變量為例，x變量的范圍為[-1,12]，區(qū)間長度為13，我們需要的精度為小數(shù)點(diǎn)后四位，那么，通過進(jìn)制數(shù)之間的轉(zhuǎn)化

那么x變量的二進(jìn)制編碼長度至少為17位，同理若是y變量的精度為小數(shù)點(diǎn)后四位，那么y變量所需要的二進(jìn)制編碼長度至少為15位

那么同時(shí)包含變量x，y的編碼總共需要的二進(jìn)制編碼長度為32位。這32位二進(jìn)制編碼則是生物學(xué)中的遺傳信息，而對(duì)應(yīng)的性狀則是變量x，y的十進(jìn)制值，所以解碼過程則是把二進(jìn)制信息轉(zhuǎn)換成十進(jìn)制性狀。由此可以看出，遺傳算法中的編碼與解碼，實(shí)際上就是數(shù)學(xué)中不同進(jìn)制數(shù)之間的相互轉(zhuǎn)換。解碼過程不再詳細(xì)贅述，這里只給出一個(gè)公式：，x的二進(jìn)制編碼為，則長度為n+1位，那么十進(jìn)制數(shù)為

設(shè)置好了種群大小和編碼與解碼過程，我們可以寫出種群設(shè)置代碼。

%% 初始種群

M = 40;N =32;

pop = round(rand(M,N)); %隨機(jī)0-1矩陣生成，產(chǎn)生初始種群遺傳信息

x1 = decode_x1(pop(:,1:17)); %對(duì)x1和x2進(jìn)行解碼

x2 = decode_x2(pop(:,18:end));

子函數(shù)decode_x1和decode_x2類似，主要實(shí)現(xiàn)二進(jìn)制數(shù)和十進(jìn)制數(shù)之間的轉(zhuǎn)換

function [x1]=decode_x1(code)

[M,N] = size(code);

sum = zeros(N);

for i=1:M

   for j=1:N

   sum(i)=sum(i)+code(i,j)*2^(N-j);

   end

 x2(i) = 4.0 + sum(i)*(12.0 - (-4.0))/(2^N - 1);
end

得到初始種群的性狀之后，我們要對(duì)初始種群進(jìn)行定量評(píng)價(jià)，來確定種群中個(gè)體之間的適應(yīng)性（fitness），通常就是我們研究問題的目標(biāo)，

則有代碼

fitness = x1.*sin(pi*x1) +x2.*sin(exp(x2)); %適應(yīng)度

那么fitness大的個(gè)體就是我們所需要尋找的，小的個(gè)體則被淘汰，所以后續(xù)代碼則實(shí)現(xiàn)如何產(chǎn)生并選擇fitness大的個(gè)體。

我們?cè)O(shè)計(jì)一個(gè)迭代規(guī)則，主要是為了實(shí)現(xiàn)優(yōu)秀親代如何產(chǎn)生子代的過程，其中包括選擇，交互和變異。

首先看看選擇（selection）過程，這里是為了選擇出優(yōu)秀親代，讓優(yōu)秀親代之間產(chǎn)生子代。通常所使用的方法是賭輪盤選擇，該方法簡單，容易編寫代碼，但是選擇誤差較大。

比如我們有三條染色體，他們所對(duì)應(yīng)的適應(yīng)度評(píng)分分別為5，15，20，那么累積總適應(yīng)度為，所以，每個(gè)個(gè)體被選中的概率為

那么想象有這樣一個(gè)輪盤，中間有三個(gè)區(qū)域?qū)?yīng)這三種個(gè)體，轉(zhuǎn)一次輪盤，指針?biāo)競€(gè)體即為所選中個(gè)體。

為了實(shí)現(xiàn)賭輪盤的選擇規(guī)則，我們寫出如下賭輪盤子函數(shù)：

%賭輪盤子函數(shù)

function [B]=seclection(fitness,A)

   [M,N]=size(A);

   fit_sum = sum(fitness);

   for i = 1:M

     probability(i) = fitness(i)/fit_sum;

   end

   for i = 2:M

     probability(i) =probability(i) + probability(i-1);
  
   end

   for j = 1:M

     p = rand();

     i = 1;

     while p > probability(i)

       i = i+1;

     end
  
     B(j,:) = A(i,:);
    
   end

end

然后，來看看優(yōu)秀親代之間的交互（crossover）過程。通過生物學(xué)常識(shí)，類比于染色體的重組與交互，我們知道親代中父本和母本遺傳信息的交互生成了子代的遺傳信息。交互過程中親代的選擇與遺傳信息的具體結(jié)合方式有很多種，可以自由設(shè)計(jì)，這里我們采取一種最簡單的方式，即種群編號(hào)相鄰的兩個(gè)個(gè)體為親代的父本和母本，并且隨機(jī)生成一個(gè)二進(jìn)制編碼點(diǎn)位，該點(diǎn)位到編碼最后一位即為交互片段。為了實(shí)現(xiàn)該過程，我們可以寫出交互子函數(shù)：

%交互子函數(shù)

function [newpop]=crossover(pc,A)

  newpop=A;

  [M,N]=size(A);

   for i= 1:2:M-1

     if rand < pc

       p = ceil(rand()*N);

         for j= p:N

           ch = A(i,j);

           newpop(i,j) = A(i+1,j);

           newpop(i+1,j) = ch;

         end

       end

    end

end

這里的pc則是交互概率，根據(jù)實(shí)際問題提前設(shè)定好pc的值，本例中pc選為0.65。

最后則是變異（mutation）過程，變異過程最主要的意義在于避免在迭代中陷入局部最大值附近，也就是函數(shù)極大值附近，就像本例中，x方向和y方向上反復(fù)震蕩，有許多的峰值，如果沒有變異過程，那么該算法所得到的結(jié)果容易進(jìn)入極值點(diǎn)附近，而非最大值附近。正常情況下遺傳信息的變異很復(fù)雜，包含有替換，缺失，增添三類，為了簡化變異過程，針對(duì)二進(jìn)制編碼的特殊性，變異過程簡易設(shè)計(jì)為替換——在某概率下，原編碼中的‘0’變?yōu)椤?’，‘1’變?yōu)椤?’。那么為了實(shí)現(xiàn)變異過程，我們可以寫出變異子函數(shù)：

%變異子函數(shù)

function [newpop]=mutation(pm,A)

  [M,N]=size(A);

  newpop=A;

  W = rand(M,N)<pm;

   for i=1:M

     for j=1:N

       if W(i,j) ==1

         if A(i,j)~=1

           newpop(i,j)= 1;

         else

           newpop(i,j) = 0;

         end

        end

       end

    end

end

其中pm則是變異概率，同樣的，根據(jù)實(shí)際問題提前設(shè)置好pm的值，在本例中，pm值選為0.08。

**寫好了選擇，交互和變異過程的子函數(shù)，我們可以來寫遺傳算法迭代主體代碼了。**

%% 迭代主題代碼

gen = 1;

while gen < generation

   [B] = seclection(fitness,pop); %賭輪盤子函數(shù)

    [newpop] = crossover(pc,B); %交互子函數(shù)

    [B] = mutation(pm,newpop); %變異子函數(shù)

    pop = B;

   x1 = decode_x1(pop(:,1:17));

   x2 = decode_x2(pop(:,18:end));

   fitness = x1.*sin(pi*x1) +x2.*sin(exp(x2)); %該代子代適應(yīng)度計(jì)算

   [fit_best,index] = max(fitness);%該代子代中最優(yōu)個(gè)體適應(yīng)度以及對(duì)應(yīng)的遺傳信息

  %所有子代中最優(yōu)個(gè)體以及對(duì)應(yīng)性狀（變量值）尋找

   if fit_best >= maxdata

     maxdata = fit_best;

     verter = pop(index,:);

     x_1 = decode_x1(verter(1:17));

     x_2 = decode_x2(verter(18:end));

   end

  num(gen) = maxdata; %每一代子代中最優(yōu)個(gè)體集合

   gen = gen + 1;

end

遺傳算法預(yù)先可以設(shè)置迭代停止條件，比如本代最優(yōu)個(gè)體與所有子代中最優(yōu)個(gè)體之間差值小于某個(gè)范圍則停止迭代，這里我們采用的是最簡單的停止方法，當(dāng)代數(shù)進(jìn)行到一定值時(shí)，停止迭代，即generation，預(yù)先設(shè)置為200代。初始最優(yōu)適應(yīng)度maxdata可以任意選擇，在本例中，maxdata選為-2。

剩下的，則是對(duì)運(yùn)行程序得到的結(jié)果進(jìn)行處理，遺傳算法通常需要的結(jié)果大致有兩個(gè)：

1）最優(yōu)個(gè)體（變量x和y的值）以及最優(yōu)適應(yīng)度（二元函數(shù)的最大值）；

2）遺傳算法每一代適應(yīng)度變化過程。

本例中，結(jié)果處理的代碼為

%% 結(jié)果與畫圖

disp(sprintf('max f=￡o%.6f',num(gen-1)));%輸出最優(yōu)解

disp(sprintf('x_1=￡o%.5f x_2=￡o%.5f',x_1,x_2));%最優(yōu)解對(duì)應(yīng)的變量值

figure(1)  

plot(num,'k');%畫圖

所得到結(jié)果為

這里變量的結(jié)果精度為小數(shù)點(diǎn)后五位，并不是原先設(shè)定的四位，原因是在解碼時(shí)候產(chǎn)生的。

小結(jié)一下：

遺傳算法模擬了生物的進(jìn)化過程，看起來很麻煩，但實(shí)際上理清生物進(jìn)化的幾個(gè)過程之后，分步寫出對(duì)應(yīng)各個(gè)過程的子函數(shù)，遺傳算法代碼也是比較容易書寫的。雖是如此，有的同學(xué)仍然覺著遺傳算法代碼好長啊，找bug時(shí)候比較困難，沒關(guān)系，下一期會(huì)介紹遺傳算法工具箱的使用方法，十幾行的代碼就可以寫完一個(gè)遺傳算法程序。

最后，為了加強(qiáng)遺傳算法的應(yīng)用，我們來看一個(gè)實(shí)際的優(yōu)化問題。姜銳老師研究傳統(tǒng)車輛的行駛之后提出了全速度差模型

從模型上來看，這是一個(gè)確定性模型，并且有兩個(gè)不同的敏感度系數(shù)和 ，我們把全速度差模型設(shè)計(jì)成自動(dòng)車的上層模型，那么一個(gè)自動(dòng)車車隊(duì)每輛車都可以認(rèn)為是同質(zhì)的，不存在傳統(tǒng)車輛中不同司機(jī)對(duì)于敏感度系數(shù)和 的影響，模型中參數(shù)變量只有和 。

那么，我們?nèi)绾斡眠z傳算法去尋找這樣的參數(shù)和 ：

在保證自動(dòng)車車隊(duì)滿足系統(tǒng)穩(wěn)定性的前提之下，使得車隊(duì)的總能耗最??？

我們是一個(gè)有靈魂的團(tuán)隊(duì)，堅(jiān)持探索，致力于分享交流學(xué)習(xí)經(jīng)驗(yàn)。

想獲取更多交通建模，論文寫作，開源資料等科研信息的小伙伴就請(qǐng)關(guān)注

微信公眾號(hào)【交通科研Lab】 （所有信息均在公眾號(hào)第一時(shí)間發(fā)布）

交通科研Lab.png