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

遺傳算法

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

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

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

下面我們用一個小案例以及代碼诗越，來詳細展示遺傳算法的流程以及代碼的書寫。

問題：（二元函數(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ù)是一個在x方向上震蕩嚷狞，同時在y方向上震蕩的圖形，并且該函數(shù)是一個超越函數(shù)荣堰，用常規(guī)求最大值方法比如求導(dǎo)或者離散方法求解起來十分復(fù)雜床未。

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

首先振坚，我們需要設(shè)置初始種群的大小還有每個個體遺傳信息的編碼（coding）與解碼（decoding）薇搁。初始種群大小可以根據(jù)實際問題自由設(shè)定，較大種群包含的遺傳信息更多屡拨，但是迭代起來更慢只酥。仿照DNA的結(jié)構(gòu)褥实，DNA含有四種堿基呀狼，這四種堿基可以對應(yīng)生成人體所有的蛋白質(zhì)，所以一個DNA序列可以認為是一種四進制編碼损离。數(shù)學(xué)中常見的進制編碼有二進制編碼哥艇，八進制編碼，十進制編碼僻澎，十六進制編碼貌踏，計算機的底層存儲通常是二進制編碼，所以這里我們選用二進制編碼比較合適窟勃，這樣計算起來會快很多祖乳。那么我們需要進行編碼與解碼的過程，編碼則是把性狀變?yōu)檫z傳信息秉氧，而解碼則是把遺傳信息變?yōu)樾誀罹炖ァＲ詘變量為例，x變量的范圍為[-1,12]汁咏，區(qū)間長度為13亚斋，我們需要的精度為小數(shù)點后四位，那么攘滩，通過進制數(shù)之間的轉(zhuǎn)化

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

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

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

%% 初始種群

M = 40;N =32;

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

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

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

子函數(shù)decode_x1和decode_x2類似笑诅，主要實現(xiàn)二進制數(shù)和十進制數(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

得到初始種群的性狀之后调缨，我們要對初始種群進行定量評價，來確定種群中個體之間的適應(yīng)性（fitness）吆你，通常就是我們研究問題的目標弦叶，

則有代碼

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

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

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

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

比如我們有三條染色體芦鳍，他們所對應(yīng)的適應(yīng)度評分分別為5，15葛账，20柠衅，那么累積總適應(yīng)度為，所以籍琳，每個個體被選中的概率為

那么想象有這樣一個輪盤菲宴，中間有三個區(qū)域?qū)?yīng)這三種個體贷祈，轉(zhuǎn)一次輪盤，指針所指個體即為所選中個體喝峦。

為了實現(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é)常識粟耻，類比于染色體的重組與交互，我們知道親代中父本和母本遺傳信息的交互生成了子代的遺傳信息眉踱。交互過程中親代的選擇與遺傳信息的具體結(jié)合方式有很多種挤忙，可以自由設(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è)定好pc的值扭倾，本例中pc選為0.65淀零。

最后則是變異（mutation）過程，變異過程最主要的意義在于避免在迭代中陷入局部最大值附近吆录，也就是函數(shù)極大值附近窑滞，就像本例中琼牧，x方向和y方向上反復(fù)震蕩恢筝，有許多的峰值，如果沒有變異過程巨坊，那么該算法所得到的結(jié)果容易進入極值點附近撬槽，而非最大值附近。正常情況下遺傳信息的變異很復(fù)雜趾撵，包含有替換侄柔，缺失，增添三類占调，為了簡化變異過程暂题，針對二進制編碼的特殊性，變異過程簡易設(shè)計為替換——在某概率下究珊，原編碼中的‘0’變?yōu)椤?’薪者，‘1’變?yōu)椤?’。那么為了實現(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è)置好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)度計算

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

  %所有子代中最優(yōu)個體以及對應(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)個體集合

   gen = gen + 1;

end

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

剩下的臣缀，則是對運行程序得到的結(jié)果進行處理坝橡，遺傳算法通常需要的結(jié)果大致有兩個：

1）最優(yōu)個體（變量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)解對應(yīng)的變量值

figure(1)  

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

所得到結(jié)果為

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

小結(jié)一下：

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

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

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

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

在保證自動車車隊滿足系統(tǒng)穩(wěn)定性的前提之下，使得車隊的總能耗最信河健状知？

我們是一個有靈魂的團隊，堅持探索孽查，致力于分享交流學(xué)習(xí)經(jīng)驗饥悴。

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

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

交通科研Lab.png