遺傳算法——matlab代碼解析
本文為學習B站老哥數學模組化課程之後的一點筆記,圖檔源自web,代碼源自老哥程式包,侵權删。
詳細的遺傳算法原理不再贅述,百度即可找到。
算法定義
遺傳算法(GA)是模拟達爾文生物進化論的自然選擇和孟德爾遺傳學機理的生物進化過程的計算模型,是一種通過模拟自然進化過程搜尋最優解的方法。它模仿生物的遺傳進化原理,通過選擇(Selection)、交叉(Crossover)與變異(Mutation)等操作機制,使種群中個體的适應性(Fitness)不斷提高,最終達到最優。其可以用來解決多目标線性規劃問題,複雜函數優化問題群組合優化問題,影響因素名額及關聯程度問題等等。
注意的幾點:
以目标函數為适應度函數,若目标函數為最小值問題,還得在前面加個負号。交叉率建議取值範圍0.4~0.9。變異率一般可取0.001~0.1。
算法流程圖
算法代碼
1.主程式
程式設計示例:
% 求下列函數的最大值 %
% f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] %
% 将 x 的值用一個10位的二值形式表示為二值問題,一個10位的二值數提供的分辨率是每為 (10-0)/(2^10-1)≈0.01 。 %
% 将變量域 [0,10] 離散化為二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一個二值數。 %
function genmain()
tic;
clear
clf
popsize=20; %群體大小
chromlength=10; %字元串長度(個體長度)
pc=0.6; %交叉機率
pm=0.001; %變異機率
pop=initpop(popsize,chromlength); %随機産生初始群體
for i=1:20 %20為疊代次數
[objvalue]=calobjvalue(pop); %計算目标函數
fitvalue=calfitvalue(objvalue); %計算群體中每個個體的适應度
[newpop]=selection(pop,fitvalue); %複制
[newpop]=crossover(pop,pc); %交叉
[newpop]=mutation(pop,pc); %變異
[bestindividual,bestfit]=best(pop,fitvalue); %求出群體中适應值最大的個體及其适應值
y(i)=max(bestfit);
n(i)=i;
pop5=bestindividual;
x(i)=decodechrom(pop5,1,chromlength)*10/1023;
pop=newpop;
end
fplot('10*sin(5*x)+7*cos(4*x)',[0 10]) %固定函數繪圖 新版matlab用fplot(@(x)10.*sin(5.*x)+7.*cos(4.*x))
hold on
plot(x,y,'r*')
hold off
[z index]=max(y); %計算最大值及其位置
x5=x(index)%計算最大值對應的x值
y=z
toc
2.初始化(編碼)
% 2.1初始化(編碼)
% initpop.m函數的功能是實作群體的初始化,popsize表示群體的大小,chromlength表示染色體的長度(二值數的長度),
% 長度大小取決于變量的二進制編碼的長度(在本例中取10位)。
%遺傳算法子程式
%Name: initpop.m
%初始化
function pop=initpop(popsize,chromlength)
pop=round(rand(popsize,chromlength)) % rand随機産生每個單元為 {0,1} 行數為popsize,列數為chromlength的矩陣,
% roud對矩陣的每個單元進行圓整。這樣産生的初始種群。
3.計算目标函數值
% 2.2 計算目标函數值
% 2.2.1 将二進制數轉化為十進制數(1)
%遺傳算法子程式
%Name: decodebinary.m
%産生 [2^n 2^(n-1) ... 1] 的行向量,然後求和,将二進制轉化為十進制
function pop2=decodebinary(pop)
[px,py]=size(pop); %求pop行和列數
for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i);
end
pop2=sum(pop1,2); %求pop1的每行之和
% 2.2.2 将二進制編碼轉化為十進制數(2)
% decodechrom.m函數的功能是将染色體(或二進制編碼)轉換為十進制,參數spoint表示待解碼的二進制串的起始位置
% (對于多個變量而言,如有兩個變量,采用20為表示,每個變量10為,則第一個變量從1開始,另一個變量從11開始。本例為1),
% 參數1ength表示所截取的長度(本例為10)。
%遺傳算法子程式
%Name: decodechrom.m
%将二進制編碼轉換成十進制
function pop2=decodechrom(pop,spoint,length)
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1);
% 2.2.3 計算目标函數值
% calobjvalue.m函數的功能是實作目标函數的計算,其公式采用本文示例仿真,可根據不同優化問題予以修改。
%遺傳算法子程式
%Name: calobjvalue.m
%實作目标函數的計算
function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10); %将pop每行轉化成十進制數
x=temp1*10/1023; %将二值域 中的數轉化為變量域 的數
objvalue=10*sin(5*x)+7*cos(4*x); %計算目标函數值
4.計算個體适應值
% 2.3 計算個體的适應值
%遺傳算法子程式
%Name:calfitvalue.m
%計算個體的适應值
function fitvalue=calfitvalue(objvalue)
global Cmin;
Cmin=0;
[px,py]=size(objvalue);
for i=1:px
if objvalue(i)+Cmin0
temp=Cmin+objvalue(i);
else
temp=0.0;
end
fitvalue(i)=temp;
end
fitvalue=fitvalue';
5.選擇複制
% 2.4 選擇複制
% 選擇或複制操作是決定哪些個體可以進入下一代。程式中采用賭輪盤選擇法選擇,這種方法較易實作。
% 根據方程 pi=fi/∑fi=fi/fsum ,選擇步驟:
% 1) 在第 t 代,由(1)式計算 fsum 和 pi
% 2) 産生 {0,1} 的随機數 rand( .),求 s=rand( .)*fsum
% 3) 求 ∑fi≥s 中最小的 k ,則第 k 個個體被選中
% 4) 進行 N 次2)、3)操作,得到 N 個個體,成為第 t=t+1 代種群
%遺傳算法子程式
%Name: selection.m
%選擇複制
function [newpop]=selection(pop,fitvalue)
totalfit=sum(fitvalue); %求适應值之和
fitvalue=fitvalue/totalfit; %單個個體被選擇的機率
fitvalue=cumsum(fitvalue); %如 fitvalue=[1 2 3 4],則 cumsum(fitvalue)=[1 3 6 10]
[px,py]=size(pop);
ms=sort(rand(px,1)); %從小到大排列
fitin=1;
newin=1;
while newin=px
if(ms(newin))fitvalue(fitin)
newpop(newin)=pop(fitin);
newin=newin+1;
else
fitin=fitin+1;
end
end
6.交叉
% 2.5 交叉
% 交叉(crossover),群體中的每個個體之間都以一定的機率 pc 交叉,即兩個個體從各自字元串的某一位置
% (一般是随機确定)開始互相交換,這類似生物進化過程中的基因分裂與重組。例如,假設2個父代個體x1,x2為:
% x1=0100110
% x2=1010001
% 從每個個體的第3位開始交叉,交又後得到2個新的子代個體y1,y2分别為:
% y1=0100001
% y2=1010110
% 這樣2個子代個體就分别具有了2個父代個體的某些特征。利用交又我們有可能由父代個體在子代組合成具有更高适合度的個體。
% 事實上交又是遺傳算法差別于其它傳統優化方法的主要特點之一。
%遺傳算法子程式
%Name: crossover.m
%交叉
function [newpop]=crossover(pop,pc)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1
if(randpc)
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
7.變異
% 2.6 變異
% 變異(mutation),基因的突變普遍存在于生物的進化過程中。變異是指父代中的每個個體的每一位都以機率 pm 翻轉,即由“1”變為“0”,
% 或由“0”變為“1”。遺傳算法的變異特性可以使求解過程随機地搜尋到解可能存在的整個空間,是以可以在一定程度上求得全局最優解。
%遺傳算法子程式
%Name: mutation.m
%變異
function [newpop]=mutation(pop,pm)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:px
if(randpm)
mpoint=round(rand*py);
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
8.求出群體中最大得适應值及其個體
% 2.7 求出群體中最大得适應值及其個體
%遺傳算法子程式
%Name: best.m
%求出群體中适應值最大的值
function [bestindividual,bestfit]=best(pop,fitvalue)
[px,py]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:px
if fitvalue(i)bestfit
bestindividual=pop(i,:);
bestfit=fitvalue(i);
end
end
實際代碼需根據題目要求靈活變化。
遺傳算法還可以用來優化BP神經網絡,将BP神經網絡的誤差作為适應度值,則通過遺傳算法可得到最優的BP權值。
GA擅長全局優化搜尋,BP擅長局部優化搜尋;兩者結合,可提高收斂速度,克服GA過早收斂的問題。
先用GA找出全局最優解的大概位置,然後采用BP算法微調得到全局最優解。兩者結合算法流程如下圖。
遺傳算法——matlab代碼解析 相關文章
matlab中如何建立自己的子產品庫
matlab中如何建立自己的子產品和子產品庫 參考:https://www.mathworks.com/help/simulink/ug/adding-libraries-to-the-library-browser.html https://www.mathworks.com/help/simulink/ug/creating-block-libraries.html 1.首先建立一個空檔案夾,最好放在matla
中國剩餘定理(CRT)與擴充中國剩餘定理(EXCRT)
以上兩種算法都是用于解決現行同餘方程組問題,隻不過中國剩餘定理是擴充中國剩餘定理的一個特殊化解法。 1.中國剩餘定理 中國剩餘定理給出了以下的一進制線性同餘方程組: 有解的判定條件,并用構造法給出了在有解情況下解的具體形式。 中國剩餘定理說明:假
算法5:解密回文——棧
上一節中我們學習了隊列,它是一種先進先出的資料結構。還有一種是後進先出的資料結構它叫做棧。棧限定隻能在一端進行插入和删除操作。比如說有一個小桶,小桶的直徑隻能放一個小球,我們現在向小桶内依次放入 2 号、1 号、3 号小球。假如你現在需要拿出 2
【python刷題】回溯算法(深度優先搜尋DFS)
回溯算法架構: result = []def backtrack(路徑, 選擇清單): if 滿足結束條件: result.add(路徑) return for 選擇 in 選擇清單: 做選擇 backtrack(路徑, 選擇清單) 撤銷選擇 多叉樹的周遊架構 def traverse(TreeNode root): for child in root.children: #前
限流算法
在開發高并發系統時,有三把利器用來保護系統:緩存、降級和限流。 那麼何為限流呢顧名思義,限流就是限制流量,就像你寬帶包了1個G的流量,用完了就沒了。通過限流,我們可以很好地控制系統的qps,進而達到保護系統的目的。 本篇文章将會介紹一下常用的限流
JVM(四)分代垃圾回收機制和垃圾回收算法
一、什麼是GC ?GC (Garbage Collection)垃圾回收,顧名思義就是專門回收垃圾的。,在C/C++中,我們需要用到記憶體的時候,需要先手動申明一下,使用完後又需要在手動回收一下,這兩部非常麻煩而且還經常會出這個方面的問題。而這一切在Java中就已經被自動執行
最短路-Bellmm-ford算法
Bellmm-ford算法 解決什麼樣的問題 有邊數限制的最短路,存在負權邊,負環 概念 通俗的來講就是:假設 1 号點到 n 号點是可達的,每一個點同時向指向的方向出發,更新相鄰的點的最短距離,通過循環 n-1 次操作,若圖中不存在負環,則 1 号點一定會到達 n 号
《算法筆記》n皇後問題
問題:n*n的棋盤上放置n個皇後,使得n個皇後不能互相攻擊(不能在同一行、同一列、同一對角線上) 思路(暴力):枚舉1-n的全排列,判斷每個全排列是否合法 #includecstdio#includecstring#includealgorithmusing namespace std;int n,count1=0;int p[110];b
二分查找算法-Node.js實作
1、二分查找法,其實就是通過三個數來查找。 2、選一個開始值,選一個末尾值,在選數組中間值。 3、再用你想查找的值,做比較,如果大于中間值那麼把開始值放當剛求的中間值,也就是把中間值當成開始值,繼續求平均值,繼續跟提供的值做比較, 如果是小于中
Tarjan:這個算法大神
摘要: 圖的算法是進行靜态分析的基礎資料算法,如何提高圖的分析效率,就需要對圖的算法有進一步的認識。 1. 引言 在靜态分析技術中, 我們常用會将代碼轉成抽象文法樹(AST), 然後采用深度周遊(DFS)來完成對文法樹的周遊和查詢,找到潛在的問題缺陷。 對于