三分鐘學會遺傳算法-魔扣目錄

三分鐘學會遺傳算法

遺傳算法

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

流程圖

步驟由以下幾步構成：

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

評估適應度（evaluate fitness）——這一步用染色體來進行目標函數運算，染色體的好壞將被指明。

選擇（selection）——從當前染色體中挑選出優良的個體，以一定概率使他們成為父代進行交叉或者變異操作，他們的優秀基因后代得到保留。物競天擇這里得以體現。

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

交叉

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

變異

下面我們將一步一步為各位呈現如何用matlab編寫一個簡單的GA算法。

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

sphere function

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

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

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

%% 選擇
%俄羅斯輪盤賭
function [newchromes,newfitness] = selection(chromes,fitness)
 weights = 1./fitness; % fitness倒數
 totalfit=sum(weights); % 累加所有weights
 totalf = weights./totalfit; %求出各染色體比重
 index = [];
 for i = 1:size(chromes,1) % 循環選出較優染色體
 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

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

%% 交叉
function newchromes = crossover(chromes,pc)
 % 生成一個新的解
 newchromes = ones(size(chromes));
 for i = 1:size(chromes,1)
 % 隨機選取兩個染色體
 parents=randperm(10,2);
 %隨機選取一個位置
 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

變異：以一各小概率生成隨機變異一個gene，代碼如下：

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

主函數，首先初始化各參數，然后進行迭代，當滿足終止條件停止：

% 清除workspace，清屏
clear
clc 
% 染色體數量
chromes_size = 20;
% 問題維數
dim = 10;
% 交叉概率
pc =0.9;
% 變異概率
pm = 0.2;
% 問題上下邊界
lb = -1;
ub = 1;
% 循環次數
maxiter = 1000;
% 目標方程
namefunc= 'objfun';
fd = str2func(namefunc);
?
% 初始化
chromes = init_chromes(chromes_size,dim,lb,ub);
% 求個染色體fitness
 for i = 1:chromes_size
 fitness(i)=feval(fd,chromes(i,:));
 end
% 求出最優解
 [bestfitness bestindex]=min(fitness);
 bestchrome = chromes(bestindex,:);
 % 主循環
for iter=1:maxiter
 % 選擇
 [chromes,newfitness] = selection(chromes,fitness);
 % 交叉
 chromes= crossover(chromes,pc);
 % 變異
 chromes= muatation(chromes,pm,lb,ub);
 % 更新最優
 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')

運行之后生成一個fitness下降曲線，如下圖：