時(shí)間：2019.8.13
老師：姚香娟
內(nèi)容：遺傳算法基本原理
個(gè)性：和藹、娓娓道來(lái)

感想：遺傳早有接觸，這次再來(lái)參加，主要是想能夠在理論介紹方面，對(duì)遺傳算法有一個(gè)較為詳細(xì)的學(xué)習(xí)。另一個(gè)就是希望能夠針對(duì)寫作，對(duì)流程再次熟悉，在國(guó)賽前復(fù)現(xiàn)準(zhǔn)備。果然一些數(shù)值計(jì)算需要線性代數(shù)的知識(shí),當(dāng)時(shí)大一時(shí)候，看了好多次的遺傳，總是不夠通透。

1.遺傳算法起源與發(fā)展

遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和孟德爾遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。

1975年密西根大學(xué)的J.Holland教授提出一種簡(jiǎn)單遺傳算法(simple genetic algorithm, SGAran'se)由編解碼、個(gè)體適應(yīng)度評(píng)估和遺傳運(yùn)算三大模塊構(gòu)成，而遺傳算法又包括染色體復(fù)制、交叉、變異甚至到位等。

改良的遺傳算法和融合新型技術(shù)的遺傳算法都是簡(jiǎn)單遺傳算法的變異形式。

20世紀(jì)60年代，Holland教授及其學(xué)生和同事提出，一種全局概率搜索優(yōu)化算法，借鑒生物。
1975 De Jong建立了著名的五函數(shù)測(cè)試平臺(tái)。
1983 Goldberg第一次把遺傳算法用于實(shí)際工程應(yīng)用。

2.遺傳算法基本原理

三大模塊：編解碼，個(gè)體適應(yīng)度評(píng)估，遺傳運(yùn)算

數(shù)學(xué)模型
$max\ f(X) \\ {s.t.}\left\{ \begin{aligned} X\in{U} \\ U\in{R}^n \end{aligned} \right.$
編碼：把問(wèn)題的解從其解空間轉(zhuǎn)換到遺傳算法的搜索空間的轉(zhuǎn)換方法。
最常用的是二進(jìn)制編碼，構(gòu)成的個(gè)體基因型是二進(jìn)制符號(hào)串。
個(gè)體適應(yīng)度：對(duì)應(yīng)個(gè)體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)值，適應(yīng)度越大。
個(gè)體基因型：編碼之后的個(gè)體表示方法 $a_1a_2a_3La_n$
個(gè)體表現(xiàn)型：原來(lái)的個(gè)體表現(xiàn)方法 $x_1x_2x_3Lx_n$

3.遺傳算法基本步驟

step1: 初始種群，生成 $X_i$
step2: 個(gè)體評(píng)價(jià) $f(X_i)$ 適應(yīng)值函數(shù)
step3: 是否滿足終止條件
step4: 選擇、交叉、變異
step5: 得到子代種群
step6: 子代代替父代，重復(fù)step2及之后，直到找到需要解為止

考慮：

解的遺傳表示
初始種群的產(chǎn)生
個(gè)體的評(píng)價(jià)函數(shù)
遺傳算子（選擇、交叉、變異）
算法的控制參數(shù)（種群規(guī)模、交叉和變異概率等）

4.遺傳算法的特點(diǎn)

傳統(tǒng)算法
模型結(jié)構(gòu)固定，有較為精確的問(wèn)題描述
給出精確解
如：線性規(guī)劃、整數(shù)規(guī)劃、運(yùn)輸問(wèn)題……

智能優(yōu)化方法
對(duì)優(yōu)化模型沒(méi)有結(jié)構(gòu)上的要求
在可接受的時(shí)間里找到滿意解（可以使用機(jī)器學(xué)習(xí)的方法進(jìn)行評(píng)價(jià)）
如：遺傳算法、蟻群算法、粒子群算法】免疫算法……

適合組合優(yōu)化問(wèn)題：裝箱，著色，匹配，TSP，工業(yè)設(shè)計(jì)（電路板，洗衣液配方，輪胎橡膠設(shè)計(jì)）

5.實(shí)例分析

采用米哈來(lái)維茨的范式
求解如下約束條件下的最優(yōu)解
個(gè)體表示（考慮精度要求）
eg.精度小數(shù)點(diǎn)后4位， $x_{j}$ 取值范圍[a,b]
則設(shè)需要 $m_j$ 位二進(jìn)制，需滿足 $2^{m_j-1}<(b-a)×10^4<=2^{m_j}-1$
從二進(jìn)制到十進(jìn)制實(shí)數(shù) $x_j$ 的映射為：
$x_{i}=a_{i}+decimal(substring_i)×\frac{b-a}{2^{m_j}-1}$ 最低值+小區(qū)間個(gè)數(shù)×小區(qū)間長(zhǎng)度

每個(gè)解的二進(jìn)制編碼位數(shù)即: $m_1+m_2+m_3+.....+m_n$
比如 $001,100,010$ 6位

隨機(jī)初始種群
實(shí)施個(gè)體評(píng)價(jià)（終止條件設(shè)定為1000代）
遺傳算子，使用輪盤賭算法，選擇概率和適應(yīng)值成正比。
交叉和變異依交叉和變異概率對(duì)基因進(jìn)行操作
用當(dāng)前種群代替初始種群，循環(huán)操作。

7.調(diào)用MATLAB的GA工具箱實(shí)現(xiàn)遺傳算法

調(diào)用命令：

${min}\ f(x) \\ s.t.\left\{ \begin{aligned} Ax\le{B} \\ Aeq\cdot{x}=Beq \\ C(x)\lt0 \\ Ceq(x)=0 \end{aligned} \right.$
其中，f(x)是標(biāo)量函數(shù)；A，B，Aeq，Beq是相應(yīng)維數(shù)的矩陣和向量（構(gòu)成約束），C(x)和Ceq(x)是非線性向量函數(shù)
[X,FVAL]=GA(FITNESSFCN, NVARS,A,B,Aeq,Beq,lb,ub,NONLCON,options)

example

 function f = myfit(x)
         f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) + 2*x(2) + 1);

 function [c,ceq] = myconstr(x) %約束條件列表
         c = [1.5 + x(1)*x(2) - x(1) - x(2);
               -x(1)*x(2) - 10];
         % No nonlinear equality constraints:
          ceq = [];

[x,fval]= ga(@(x)myfit(x),2,[],[],[],[],[],[],@(x)myconstr(x))

可視化工具箱界面配置

選擇GA

function [ y ] = target(x)
% 工具箱只支持求解最小值，將求解最大值變成求解最小值
y = -x-10*sin(5*x)-7*cos(4*x);
end

下面設(shè)置參數(shù)，關(guān)于一些約束條件的理解需要參考上面公式，完全理解需要線性代數(shù)的知識(shí)，猶記得去年大一的時(shí)候，那時(shí)沒(méi)有學(xué)習(xí)線性代數(shù)，建了四五次模型，經(jīng)常想著去使用遺傳算法，然而總沒(méi)能實(shí)現(xiàn)完全復(fù)現(xiàn)。當(dāng)然，當(dāng)時(shí)資料相比于現(xiàn)在，還是很殘缺的。如今互聯(lián)網(wǎng)上，更多人愿意去做詳細(xì)的教程型博客了，這是一個(gè)巨大的改觀。我的話，現(xiàn)在仍以記錄自己的總結(jié)為主，主要是幫自己梳理一下。

設(shè)置參數(shù)，約束條件的理解參考上面的公式

8.編寫.m函數(shù)實(shí)現(xiàn)遺傳算法

學(xué)習(xí)參考博客：遺傳算法介紹及詳盡代碼
學(xué)習(xí)推薦參考博客：很詳盡
代碼參考博客：遺傳算法流傳版本改錯(cuò)

% 下面舉例說(shuō)明遺傳算法 %
% 求下列函數(shù)的最大值 %
% f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] %
% 將 x 的值用一個(gè)10位的二值形式表示為二值問(wèn)題，一個(gè)10位的二值數(shù)提供的分辨率是每為 (10-0)/(2^10-1)≈0.01 
% 將變量域 [0,10] 離散化為二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一個(gè)二值數(shù)。 %
% %
%--------------------------------------------------------------------------------------------------------------%
%--------------------------------------------------------------------------------------------------------------

% 2.0 主程序
%遺傳算法主程序
%Name:genmain05.m
%要求精度不大于0.01，
function []=yichuan()
popsize=20;                         %群體大小
chromlength=10;                  %字符串長(zhǎng)度(個(gè)體長(zhǎng)度)
pc=0.6;                                %交叉概率，只有在隨機(jī)數(shù)小于pc時(shí)，才會(huì)產(chǎn)生交叉
pm=0.001;                           %變異概率

pop=initpop(popsize,chromlength);               %隨機(jī)產(chǎn)生初始群體
for i=1:20                                                        %20為遺傳代數(shù)
        [objvalue]=calobjvalue(pop);                  %計(jì)算目標(biāo)函數(shù)
        fitvalue=calfitvalue(objvalue);                 %計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度

        [newpop]=selection(pop,fitvalue);                 %復(fù)制
        [newpop1]=crossover(newpop,pc);               %交叉
        [newpop2]=mutation(newpop1,pc);               %變異
        
        [objvalue]=calobjvalue(newpop2);                 %計(jì)算目標(biāo)函數(shù)
        fitvalue=calfitvalue(objvalue);                       %計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度
        
        [bestindividual,bestfit]=best(newpop2,fitvalue);     %求出群體中適應(yīng)值最大的個(gè)體及其適應(yīng)值
        y(i)=bestfit;                                                              %返回的 y 是自適應(yīng)度值，而非函數(shù)值
        x(i)=decodechrom(bestindividual,1,chromlength)*10/1023;      %將自變量解碼成十進(jìn)制
        pop=newpop2;
end
fplot(@(x)10.*sin(5.*x)+7.*cos(4.*x))
hold on
plot(x,y,'r*')                                          
hold on

[z, index]=max(y);             %計(jì)算最大值及其位置
x5=x(index)                     %計(jì)算最大值對(duì)應(yīng)的x值
ymax=z

% 2.1初始化(編碼)
% initpop.m函數(shù)的功能是實(shí)現(xiàn)群體的初始化，popsize表示群體的大小，chromlength表示染色體的長(zhǎng)度(二值數(shù)的長(zhǎng)度)，
% 長(zhǎng)度大小取決于變量的二進(jìn)制編碼的長(zhǎng)度(在本例中取10位)。
function [pop]=initpop(popsize,chromlength) 
pop=round(rand(popsize,chromlength)); 
% rand隨機(jī)產(chǎn)生每個(gè)單元為 {0,1} 行數(shù)為popsize，列數(shù)為chromlength的矩陣，
% round對(duì)矩陣的每個(gè)單元進(jìn)行圓整。這樣產(chǎn)生的初始種群。

% 2.2.3 計(jì)算目標(biāo)函數(shù)值
% calobjvalue.m函數(shù)的功能是實(shí)現(xiàn)目標(biāo)函數(shù)的計(jì)算，其公式采用本文示例仿真，可根據(jù)不同優(yōu)化問(wèn)題予以修改。
%遺傳算法子程序
%Name: calobjvalue.m
%實(shí)現(xiàn)目標(biāo)函數(shù)的計(jì)算，將 二值域 中的數(shù)轉(zhuǎn)化為 變量域的數(shù)
function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10);   %將pop每行轉(zhuǎn)化成十進(jìn)制數(shù)
x=temp1*10/1023;                         %在精度不大于0.01時(shí)，最小整數(shù)為1023，即需要10位二進(jìn)制
objvalue=10*sin(5*x)+7*cos(4*x);   %計(jì)算目標(biāo)函數(shù)值

% 2.3 計(jì)算個(gè)體的適應(yīng)值
%遺傳算法子程序
%Name:calfitvalue.m
%計(jì)算個(gè)體的適應(yīng)值
function fitvalue=calfitvalue(objvalue)

[px,~]=size(objvalue);                   %目標(biāo)值有正有負(fù)
for i=1:px
        if objvalue(i)>0                    
                temp=objvalue(i);          
        else
                temp=0.0;
        end
        fitvalue(i)=temp;
end
fitvalue=fitvalue';

% 2.4 選擇復(fù)制
% 選擇或復(fù)制操作是決定哪些個(gè)體可以進(jìn)入下一代。程序中采用賭輪盤選擇法選擇，這種方法較易實(shí)現(xiàn)。
% 根據(jù)方程 pi=fi/∑fi=fi/fsum ，選擇步驟：
% 1） 在第 t 代，由（1）式計(jì)算 fsum 和 pi 
% 2） 產(chǎn)生 {0,1} 的隨機(jī)數(shù) rand( .)，求 s=rand( .)*fsum
% 3） 求 所有fi≥s 中最小的 k ，則第 k 個(gè)個(gè)體被選中
% 4） 進(jìn)行 N 次2）、3）操作，得到 N 個(gè)個(gè)體，成為第 t=t+1 代種群
%遺傳算法子程序
%Name: selection.m
%選擇復(fù)制
function [newpop]=selection(pop,fitvalue) 
totalfit=sum(fitvalue);                   %求適應(yīng)值之和
fitvalue=fitvalue/totalfit;                %單個(gè)個(gè)體被選擇的概率
fitvalue=cumsum(fitvalue);            %如 fitvalue=[1 2 3 4]，則 cumsum(fitvalue)=[1 3 6 10]，不明白為什么要累加 
[px,~]=size(pop);                       %20*10
ms=sort(rand(px,1));                   %從小到大排列
fitin=1;
newin=1;
while newin<=px                          %選出20個(gè)新個(gè)體，有重復(fù)情況，和上面介紹的方法不太一樣
        if(ms(newin))<fitvalue(fitin)
                newpop(newin,:)=pop(fitin,:);
                newin=newin+1;
        else
                fitin=fitin+1;
        end
end

% 2.5 交叉
% 交叉(crossover)，群體中的每個(gè)個(gè)體之間都以一定的概率 pc 交叉，即兩個(gè)個(gè)體從各自字符串的某一位置
% （一般是隨機(jī)確定）開始互相交換，這類似生物進(jìn)化過(guò)程中的基因分裂與重組。例如，假設(shè)2個(gè)父代個(gè)體x1，x2為：
% x1=0100110,x2=1010001
% 從每個(gè)個(gè)體的第3位開始交叉，交又后得到2個(gè)新的子代個(gè)體y1，y2分別為：
% y1＝0100001,y2＝1010110
% 這樣2個(gè)子代個(gè)體就分別具有了2個(gè)父代個(gè)體的某些特征。利用交又我們有可能由父代個(gè)體在子代組合成具有更高適合度的個(gè)體。
% 事實(shí)上交叉是遺傳算法區(qū)別于其它傳統(tǒng)優(yōu)化方法的主要特點(diǎn)之一。
%遺傳算法子程序
%Name: crossover.m
%交叉
function [newpop]=crossover(pop,pc)          %pc=0.6
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1                                             %步長(zhǎng)為2，是將相鄰的兩個(gè)個(gè)體進(jìn)行交叉
        if(rand<pc)
                cpoint=round(rand*py);
                newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
                newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
        else
                newpop(i,:)=pop(i,:);
                newpop(i+1,:)=pop(i+1,:);
        end
end

% 2.6 變異
% 變異(mutation)，基因的突變普遍存在于生物的進(jìn)化過(guò)程中。變異是指父代中的每個(gè)個(gè)體的每一位都以概率 pm 翻轉(zhuǎn)，
%即由“1”變?yōu)椤?”，或由“0”變?yōu)椤?”。
%遺傳算法的變異特性可以使求解過(guò)程隨機(jī)地搜索到解可能存在的整個(gè)空間，因此可以 在一定程度上 求得全局最優(yōu)解。
%遺傳算法子程序
%Name: mutation.m
%變異
function [newpop]=mutation(pop,pm)
        [px,py]=size(pop);
        newpop=ones(size(pop));
        for i=1:px
                if(rand<pm)
                        mpoint=round(rand*py);     %產(chǎn)生的變異點(diǎn)在1-10之間
                        if mpoint<=0
                                mpoint=1;                         %變異位置
                        end
                        newpop(i,:)=pop(i,:);
                        if any(newpop(i,mpoint))==0
                                newpop(i,mpoint)=1;
                        else
                                newpop(i,mpoint)=0;
                        end
                else
                newpop(i,:)=pop(i,:);
                end
        end

% 2.7 求出群體中最大得適應(yīng)值及其個(gè)體
%遺傳算法子程序
%Name: best.m
%求出第 t 代群體中適應(yīng)值最大的值
function [bestindividual,bestfit]=best(pop,fitvalue)
[px,~]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:px
        if fitvalue(i)>bestfit
                bestindividual=pop(i,:);
                bestfit=fitvalue(i);
        end
end

% 2.2 計(jì)算目標(biāo)函數(shù)值
% 2.2.1 將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)(1)
%遺傳算法子程序
%Name: decodebinary.m
%產(chǎn)生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，將二進(jìn)制轉(zhuǎn)化為十進(jìn)制
function pop2=decodebinary(pop)
[~,py]=size(pop);                   %求pop行和列數(shù)
for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i);
end
pop2=sum(pop1,2);                 %求pop1的每行之和

% 2.2.2 將二進(jìn)制編碼轉(zhuǎn)化為十進(jìn)制數(shù)(2)
% decodechrom.m函數(shù)的功能是將染色體(或二進(jìn)制編碼)轉(zhuǎn)換為十進(jìn)制，參數(shù)spoint表示待解碼的二進(jìn)制串的起始位置
% (對(duì)于多個(gè)變量而言，如有兩個(gè)變量，采用20為表示，每個(gè)變量10為，則第一個(gè)變量從1開始，另一個(gè)變量從11開始。本例為1)，
% 參數(shù)1ength表示所截取的長(zhǎng)度（本例為10）。
%遺傳算法子程序
%Name: decodechrom.m
%將二進(jìn)制編碼轉(zhuǎn)換成十進(jìn)制
function pop2=decodechrom(pop,spoint,length)          %1  10
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1);                                           %將pop每行轉(zhuǎn)換成十進(jìn)制值，結(jié)果是20*1的矩陣

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【國(guó)賽培訓(xùn)】遺傳算法

【國(guó)賽培訓(xùn)】遺傳算法

1.遺傳算法起源與發(fā)展

2.遺傳算法基本原理

3.遺傳算法基本步驟

4.遺傳算法的特點(diǎn)

5.實(shí)例分析

7.調(diào)用MATLAB的GA工具箱實(shí)現(xiàn)遺傳算法

調(diào)用命令：

可視化工具箱界面配置

8.編寫.m函數(shù)實(shí)現(xiàn)遺傳算法

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【國(guó)賽培訓(xùn)】遺傳算法

1.遺傳算法起源與發(fā)展

2.遺傳算法基本原理

3.遺傳算法基本步驟

4.遺傳算法的特點(diǎn)

5.實(shí)例分析

7.調(diào)用MATLAB的GA工具箱實(shí)現(xiàn)遺傳算法

調(diào)用命令：

可視化工具箱界面配置

8.編寫.m函數(shù)實(shí)現(xiàn)遺傳算法

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av