日日摸日日碰夜夜爽无码久久吃奶,秋霞福利一区二区,国产精品一区二区三区洲

三分鐘學(xué)會(huì)遺傳算法

遺傳算法

此節(jié)介紹最著名的遺傳算法(GA)。遺傳算法屬于進(jìn)化算法，基本思想是取自“物競天澤、適者生存”的進(jìn)化法則。簡單來說，遺傳算法就是將問題編碼成為染色體，然后經(jīng)過不斷選擇、交叉、變異等操作來更新染色體的編碼并進(jìn)行迭代，每次迭代保留上一代好的染色體，丟棄差的染色體，最終達(dá)到滿足目標(biāo)的最終染色體。整個(gè)流程由下圖構(gòu)成（手寫，見諒 -_-!!）

流程圖

步驟由以下幾步構(gòu)成：

編碼（coding）——首先初始化及編碼。在此步，根據(jù)問題或者目標(biāo)函數(shù)（objective function）構(gòu)成解數(shù)據(jù)（solutions），在遺傳算法中，該解數(shù)據(jù)就被稱為染色體（chromosome）。值得一提的是，遺傳算法為多解（population based）算法，所以會(huì)有多條染色體。初始化中會(huì)隨機(jī)生成N條染色體，, 這里表示染色體包含了n條。其中，這里表示第i條染色體由d維數(shù)值構(gòu)成。GA會(huì)以這個(gè)N個(gè)數(shù)據(jù)作為初始點(diǎn)開始進(jìn)行進(jìn)化。

評估適應(yīng)度（evaluate fitness）——這一步用染色體來進(jìn)行目標(biāo)函數(shù)運(yùn)算，染色體的好壞將被指明。

選擇（selection）——從當(dāng)前染色體中挑選出優(yōu)良的個(gè)體，以一定概率使他們成為父代進(jìn)行交叉或者變異操作，他們的優(yōu)秀基因后代得到保留。物競天擇這里得以體現(xiàn)。

交叉（crossover）——父代的兩個(gè)兩個(gè)染色體，通過互換染色體構(gòu)成新的染色體。例如下圖，父親母親各提供兩個(gè)基因給我。這樣我既保留了父母的基于，同時(shí)又有自己的特性。

交叉

變異（mutation）——以一定概率使基因發(fā)生突變。該算子一般以較低概率發(fā)生。如下圖所示：

變異

下面我們將一步一步為各位呈現(xiàn)如何用matlab編寫一個(gè)簡單的GA算法。

本問題為實(shí)數(shù)最小化minimization問題。我們需要在解空間內(nèi)找到最小值或近似最小值，此處我們使用sphere函數(shù)作為目標(biāo)函數(shù)（讀者可以自行修改為其他的目標(biāo)函數(shù)）。

sphere function

初始化：在這一步中，我們將在給定問題空間內(nèi)生成隨機(jī)解，代碼如下：

% %% 初始化
% % 輸入：chromes_size，dim維數(shù),lb下界，ub上界
% % 輸出：chromes新種群
function chromes=init_chromes(chromes_size,dim,lb,ub)
 % 上下界中隨機(jī)生成染色體
 chromes = rand(chromes_size,dim)*(ub-lb)+lb;
end

選擇：選擇是從當(dāng)前代中挑選優(yōu)秀的染色體保留以繁殖下一代。我們這里采取的方法是俄羅斯輪盤選擇方式。誰的解優(yōu)，誰獲得選中的概率越高。首先，我們需要先求出各染色體的fitness倒數(shù)。
,然后求出各染色體的比重，比重越大，被保留機(jī)會(huì)越大。。代碼如下：

%% 選擇
%俄羅斯輪盤賭
function [newchromes,newfitness] = selection(chromes,fitness)
 weights = 1./fitness; % fitness倒數(shù)
 totalfit=sum(weights); % 累加所有weights
 totalf = weights./totalfit; %求出各染色體比重
 index = [];
 for i = 1:size(chromes,1) % 循環(huán)選出較優(yōu)染色體
 pick = rand;
 while pick == 0
 pick = rand;
 end
 for j = 1:size(chromes,1)
 pick = pick - totalf(j);
 if pick<0
 index = [index j];
 break
 end
 end
 end
 newchromes =chromes(index,:);
 newfitness = fitness(index);
end

交叉：此步會(huì)隨機(jī)選取兩個(gè)選擇過后的染色體作為父代，從兩個(gè)染色體中各截取一部分基因生成新的染色體，代碼如下：

%% 交叉
function newchromes = crossover(chromes,pc)
 % 生成一個(gè)新的解
 newchromes = ones(size(chromes));
 for i = 1:size(chromes,1)
 % 隨機(jī)選取兩個(gè)染色體
 parents=randperm(10,2);
 %隨機(jī)選取一個(gè)位置
 pos = round(rand*size(chromes,2));
 if(rand<pc)
 % 交叉生成新的解
 newchromes(i,:)=[chromes(parents(1),1:pos) chromes(parents(2),pos+1:size(chromes,2))];
 else
 newchromes(i,:)=chromes(i,:);
 end
 end
end

變異：以一各小概率生成隨機(jī)變異一個(gè)gene，代碼如下：

% 變異
function newchromes= muatation(chromes,pm,lb,ub)
 for i = 1:size(chromes,1)
 newchromes(i,:) = chromes(i,:);
 if (rand<pm)
 %隨機(jī)選取一位
 pos = ceil(rand*size(chromes,2));
 %變異
 newchromes(i,pos)= rand*(ub-lb)+lb;
 end
 end
end

主函數(shù)，首先初始化各參數(shù)，然后進(jìn)行迭代，當(dāng)滿足終止條件停止：

% 清除workspace，清屏
clear
clc 
% 染色體數(shù)量
chromes_size = 20;
% 問題維數(shù)
dim = 10;
% 交叉概率
pc =0.9;
% 變異概率
pm = 0.2;
% 問題上下邊界
lb = -1;
ub = 1;
% 循環(huán)次數(shù)
maxiter = 1000;
% 目標(biāo)方程
namefunc= 'objfun';
fd = str2func(namefunc);
?
% 初始化
chromes = init_chromes(chromes_size,dim,lb,ub);
% 求個(gè)染色體fitness
 for i = 1:chromes_size
 fitness(i)=feval(fd,chromes(i,:));
 end
% 求出最優(yōu)解
 [bestfitness bestindex]=min(fitness);
 bestchrome = chromes(bestindex,:);
 % 主循環(huán)
for iter=1:maxiter
 % 選擇
 [chromes,newfitness] = selection(chromes,fitness);
 % 交叉
 chromes= crossover(chromes,pc);
 % 變異
 chromes= muatation(chromes,pm,lb,ub);
 % 更新最優(yōu)
 for i = 1:chromes_size
 fitness(i)=feval(fd,chromes(i,:));
 if fitness(i)<bestfitness
 bestfitness= fitness(i)
 bestchrome = chromes(i,:);
 end
 end
 trace(iter)=bestfitness;
 
end
?
% 繪制fitness曲線
plot(trace)
title('Fitness curve')
xlabel('Iterations')
ylabel('Fitness value')

運(yùn)行之后生成一個(gè)fitness下降曲線，如下圖：