遺傳算法簡(jiǎn)單介紹與MATLAB實(shí)現(xiàn)（二）
引入題目一
上一篇文章中我們簡(jiǎn)單的介紹了一了一下遺傳算法二汛，其中提到了多元函數(shù)$f=f(x, y)$极谊，所以在這里我們就定義一個(gè)二元函數(shù)罕拂，作為第一個(gè)練手的程序颠焦。
我們?cè)谶@里令
$$z = \sin{x}+\cos{y}+0.1(x+y)$$
通過使用MATLAB作圖可以看到下圖
可以看出這是一個(gè)存在很多區(qū)域極大值法精，有很多“坑”沛厨。這正是遺傳算法的缺陷之一——求出來的最優(yōu)解可能并不是全局最優(yōu)解而是局部最優(yōu)解刚照。
從圖中可以看出全局最大值在$(10, 10)$附近刑巧。所以接下來我們就開始編程解決這個(gè)問題喧兄。
遺傳算法MATLAB程序
設(shè)定參數(shù)
首先我們要確定一系列參數(shù)
N = 100; %種群內(nèi)個(gè)體數(shù)目
N_chrom = 2; %染色體節(jié)點(diǎn)數(shù)
iter = 2000; %迭代次數(shù)
mut = 0.2; %突變概率
acr = 0.2; %交叉概率
其中突變概率指的是某個(gè)個(gè)體的染色體發(fā)生突變的概率。因?yàn)閷?shí)際中并不可能每一個(gè)個(gè)體都會(huì)發(fā)生突變啊楚，而是存在一定的概率吠冤，因此我們?cè)谶@里定義每一個(gè)個(gè)體突變發(fā)生的概率為0.2。
同理恭理，交叉概率指的就是某個(gè)個(gè)體與另一個(gè)個(gè)體發(fā)生染色體交叉的概率拯辙。
迭代次數(shù)指的是整個(gè)種群迭代2000多次。
一般來說颜价，并不是突變概率涯保、交叉概率越小或者越大越好。比如說突變概率特別高的話周伦，會(huì)讓整個(gè)種群的最優(yōu)適應(yīng)度飄忽不定夕春。如果特別小的話，會(huì)讓種群迭代的速度特別慢专挪，很難找到最優(yōu)適應(yīng)度及志。這里取0.2是我經(jīng)過多次試驗(yàn)以后，覺得0.2是一個(gè)比較穩(wěn)定不會(huì)亂飄且適應(yīng)度收斂也不錯(cuò)的一個(gè)值寨腔。
迭代次數(shù)也同理速侈，如果一個(gè)特別簡(jiǎn)單的模型去求最優(yōu)解，可能五六次迭代就求出來了迫卢，那么2000次迭代純屬浪費(fèi)時(shí)間倚搬。但是如果是一個(gè)特別復(fù)雜的模型，那么2000次迭代就有可能不夠乾蛤。具體迭代次數(shù)可以自己靈活決定每界。
chrom_range = [-10 -10; 10 10];%每個(gè)節(jié)點(diǎn)的值的區(qū)間
chrom = zeros(N, N_chrom);%存放染色體的矩陣
fitness = zeros(N, 1);%存放染色體的適應(yīng)度
fitness_ave = zeros(1, iter);%存放每一代的平均適應(yīng)度
fitness_best = zeros(1, iter);%存放每一代的最優(yōu)適應(yīng)度
chrom_best = zeros(1, N_chrom+1);%存放當(dāng)前代的最優(yōu)染色體與適應(yīng)度
其中的chrom_range指的是每個(gè)節(jié)點(diǎn)值的區(qū)間。在我們的這個(gè)模型中幻捏，$x\in [-10, 10], y\in[-10, 10]$。第一行放的是兩個(gè)變量的區(qū)間下限命咐，第二行放的是區(qū)間上限篡九。
chrom和fitness兩個(gè)矩陣你們可以自己理解一下為什么這樣子寫。
fitness_ave用來存放每一代的平均適應(yīng)度醋奠，主要是用來最后畫圖榛臼，觀察種群在每一次迭代中適應(yīng)度的變化情況。fitness_best同理窜司。
chrom_best用來存放最優(yōu)適應(yīng)度對(duì)應(yīng)的最優(yōu)染色體與適應(yīng)度沛善，可以回想一下上一章染色體變異中需要最優(yōu)適應(yīng)度，優(yōu)勝劣汰中需要最優(yōu)染色體塞祈，這個(gè)矩陣作用就是如此金刁。
初始化種群
接下來開始初始化參數(shù)
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色體
fitness = CalFitness(chrom, N, N_chrom); %計(jì)算適應(yīng)度
chrom_best = FindBest(chrom, fitness, N_chrom); %尋找最優(yōu)染色體
fitness_best(1) = chrom_best(end); %將當(dāng)前最優(yōu)存入矩陣當(dāng)中
fitness_ave(1) = CalAveFitness(fitness); %將當(dāng)前平均適應(yīng)度存入矩陣當(dāng)中
Initialize函數(shù)是我自定義的一個(gè)函數(shù)，用于初始化染色體。具體操作就是用一個(gè)for循環(huán)對(duì)每個(gè)個(gè)體的染色體進(jìn)行隨機(jī)賦值尤蛮，并利用chrom_range將其限定在變量規(guī)定的區(qū)間之內(nèi)媳友。
function chrom_new = Initialize(N, N_chrom, chrom_range)
chrom_new = rand(N, N_chrom);
for i = 1:N_chrom %每一列乘上范圍
chrom_new(:, i) = chrom_new(:, i)*(chrom_range(2, i)-chrom_range(1, i))+chrom_range(1, i);
end
CalFitness函數(shù)則是計(jì)算chrom內(nèi)每個(gè)個(gè)體的適應(yīng)度，并將其保存在fitness中产捞。這個(gè)函數(shù)很重要醇锚，請(qǐng)著重理解這個(gè)函數(shù)的用法
function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
%開始計(jì)算適應(yīng)度
for i = 1:N
x = chrom(i, 1);
y = chrom(i, 2);
fitness(i) = sin(x)+cos(y)+0.1*x+0.1*y;
end
FindBest函數(shù)尋找出當(dāng)前種群中的最優(yōu)染色體，并將其保存在chrom_best坯临。
function chrom_best = FindBest(chrom, fitness, N_chrom)
chrom_best = zeros(1, N_chrom+1);
[maxNum, maxCorr] = max(fitness);
chrom_best(1:N_chrom) =chrom(maxCorr, :);
chrom_best(end) = maxNum;
CalAveFitness函數(shù)用于計(jì)算當(dāng)前種群中的平均適應(yīng)度焊唬。
function fitness_ave = CalAveFitness(fitness)
[N ,~] = size(fitness);
fitness_ave = sum(fitness)/N;
迭代開始
初始化完以后就開始迭代，為了保證迭代次數(shù)和iter一致看靠，這里我們就直接令t從2開始迭代赶促。
再一次迭代過程中，一個(gè)種群執(zhí)行操作順序?yàn)椋喝旧w變異衷笋，染色體交叉芳杏，計(jì)算適應(yīng)度，尋找最優(yōu)染色體辟宗，替換當(dāng)前存儲(chǔ)的最優(yōu)染色體爵赵，優(yōu)勝劣汰。
需要注意的是這里替換當(dāng)前最優(yōu)染色體泊脐。因?yàn)槲覀儗⑦@個(gè)種群的個(gè)個(gè)個(gè)體的染色體重新變異空幻、交叉過了，所以最優(yōu)染色體也會(huì)變化容客。但是這一代的最優(yōu)染色體不一定比上一次迭代的最優(yōu)染色體好秕铛，所以需要判定是否將最優(yōu)染色體這個(gè)位置給換掉。
因此迭代過程中的代碼為
for t = 2:iter
chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %變異
chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
fitness = CalFitness(chrom, N, N_chrom); %計(jì)算適應(yīng)度
chrom_best_temp = FindBest(chrom, fitness, N_chrom); %尋找最優(yōu)染色體
if chrom_best_temp(end)>chrom_best(end) %替換掉當(dāng)前儲(chǔ)存的最優(yōu)
chrom_best = chrom_best_temp;
end
%%替換掉最劣
[chrom, fitness] = ReplaceWorse(chrom, chrom_best, fitness);
fitness_best(t) = chrom_best(end); %將當(dāng)前最優(yōu)存入矩陣當(dāng)中
fitness_ave(t) = CalAveFitness(fitness); %將當(dāng)前平均適應(yīng)度存入矩陣當(dāng)中
end
其中MutChrom函數(shù)用來對(duì)種群進(jìn)行染色體變異操作缩挑。這里面的操作比較多但两，主要可以分為三步：
- 判斷某節(jié)點(diǎn)是否變異；
- 判斷變異是增加還是減少供置；
- 判斷變異后的值是否越界谨湘。
下面代碼表示為
function chrom_new = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter)
for i = 1:N
for j = 1:N_chrom
mut_rand = rand; %是否變異
if mut_rand <=mut
mut_pm = rand; %增加還是減少
mut_num = rand*(1-t/iter)^2;
if mut_pm<=0.5
chrom(i, j)= chrom(i, j)*(1-mut_num);
else
chrom(i, j)= chrom(i, j)*(1+mut_num);
end
chrom(i, j) = IfOut(chrom(i, j), chrom_range(:, j)); %檢驗(yàn)是否越界
end
end
end
chrom_new = chrom;
越界函數(shù)IfOut函數(shù)我們看它是左越界還是右越界，如果是左越界芥丧，則讓節(jié)點(diǎn)值等于區(qū)間下限紧阔；如果是右越界，則讓節(jié)點(diǎn)值等于區(qū)間上限续担。
function c_new = IfOut(c, range)
if c<range(1) || c>range(2)
if abs(c-range(1))<abs(c-range(2))
c_new = range(1);
else
c_new = range(2);
end
else
c_new = c;
end
AcrChrom函數(shù)是染色體交叉函數(shù)擅耽。邏輯相較染色體變異來說比較簡(jiǎn)單，大致可以分為以下幾點(diǎn)
- 判斷該節(jié)點(diǎn)是否交叉物遇；
- 隨機(jī)尋找一個(gè)與其交叉的節(jié)點(diǎn)乖仇；
- 對(duì)兩個(gè)節(jié)點(diǎn)進(jìn)行交叉憾儒。
function chrom_new = AcrChrom(chrom, acr, N, N_chrom)
for i = 1:N
acr_rand = rand;
if acr_rand<acr %如果交叉
acr_chrom = floor((N-1)*rand+1); %要交叉的染色體
acr_node = floor((N_chrom-1)*rand+1); %要交叉的節(jié)點(diǎn)
%交叉開始
temp = chrom(i, acr_node);
chrom(i, acr_node) = chrom(acr_chrom, acr_node);
chrom(acr_chrom, acr_node) = temp;
end
end
chrom_new = chrom;
ReplaceWorse函數(shù)則是優(yōu)勝劣汰這個(gè)過程，將種群中的最劣染色體替換掉这敬。這里是直接用最優(yōu)染色體替換航夺，并且替換掉的是最后幾個(gè)染色體，目的是加快收斂速度崔涂，但可能會(huì)陷入局部最優(yōu)解阳掐。
function [chrom_new, fitness_new] = ReplaceWorse(chrom, chrom_best, fitness)
max_num = max(fitness);
min_num = min(fitness);
limit = (max_num-min_num)*0.2+min_num;
replace_corr = fitness<limit;
replace_num = sum(replace_corr);
chrom(replace_corr, :) = ones(replace_num, 1)*chrom_best(1:end-1);
fitness(replace_corr) = ones(replace_num, 1)*chrom_best(end);
chrom_new = chrom;
fitness_new = fitness;
end
輸出遺傳算法迭代圖
在這里我們只輸出一個(gè)標(biāo)準(zhǔn)圖為迭代過程中種群的平均適應(yīng)度與最優(yōu)適應(yīng)度。
在之前我們已經(jīng)得到了每一代的平均適應(yīng)度fitness_ave與最優(yōu)適應(yīng)度fitness_best冷蚂，所以可以直接輸出圖像
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均適應(yīng)度', '最優(yōu)適應(yīng)度')
之后我們還想要看得出的點(diǎn)在實(shí)際圖像中哪個(gè)位置缭保，所以我們可以增加一個(gè)用來作圖的函數(shù)PlotModel
function y = PlotModel(chrom)
x = chrom(1);
y = chrom(2);
z = chrom(3);
figure(2)
scatter3(x, y, z, 'ko')
hold on
[X, Y] = meshgrid(-10:0.1:10);
Z =sin(X)+cos(Y)+0.1*X+0.1*Y;
mesh(X, Y, Z)
y=1;
遺傳算法主程序
上面就是所有程序片段，因此把主程序的代碼聯(lián)立起來為
clc, clear, close all
%%基礎(chǔ)參數(shù)
N = 100; %種群內(nèi)個(gè)體數(shù)目
N_chrom = 2; %染色體節(jié)點(diǎn)數(shù)
iter = 2000; %迭代次數(shù)
mut = 0.2; %突變概率
acr = 0.2; %交叉概率
best = 1;
chrom_range = [-10 -10;10 10];%每個(gè)節(jié)點(diǎn)的值的區(qū)間
chrom = zeros(N, N_chrom);%存放染色體的矩陣
fitness = zeros(N, 1);%存放染色體的適應(yīng)度
fitness_ave = zeros(1, iter);%存放每一代的平均適應(yīng)度
fitness_best = zeros(1, iter);%存放每一代的最優(yōu)適應(yīng)度
chrom_best = zeros(1, N_chrom+1);%存放當(dāng)前代的最優(yōu)染色體與適應(yīng)度
%%初始化
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色體
fitness = CalFitness(chrom, N, N_chrom); %計(jì)算適應(yīng)度
chrom_best = FindBest(chrom, fitness, N_chrom); %尋找最優(yōu)染色體
fitness_best(1) = chrom_best(end); %將當(dāng)前最優(yōu)存入矩陣當(dāng)中
fitness_ave(1) = CalAveFitness(fitness); %將當(dāng)前平均適應(yīng)度存入矩陣當(dāng)中
for t = 2:iter
chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %變異
chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
fitness = CalFitness(chrom, N, N_chrom); %計(jì)算適應(yīng)度
chrom_best_temp = FindBest(chrom, fitness, N_chrom); %尋找最優(yōu)染色體
if chrom_best_temp(end)>chrom_best(end) %替換掉當(dāng)前儲(chǔ)存的最優(yōu)
chrom_best = chrom_best_temp;
end
%%替換掉最劣
[chrom, fitness] = ReplaceWorse(chrom, chrom_best, fitness);
fitness_best(t) = chrom_best(end); %將當(dāng)前最優(yōu)存入矩陣當(dāng)中
fitness_ave(t) = CalAveFitness(fitness); %將當(dāng)前平均適應(yīng)度存入矩陣當(dāng)中
end
%%作圖
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均適應(yīng)度', '最優(yōu)適應(yīng)度')
e = PlotModel(chrom_best)
%%輸出結(jié)果
disp(['最優(yōu)染色體為', num2str(chrom_best(1:end-1))])
disp(['最優(yōu)適應(yīng)度為', num2str(chrom_best(end))])
輸出結(jié)果
我們運(yùn)行一下蝙茶， 可以得到最大點(diǎn)為$(7.9541, 6.3834)$艺骂，最大值為3.4237。
可以做出最大值點(diǎn)在空間中的位置如圖所示隆夯。證明我們的結(jié)論比較正確钳恕，起碼沒有落到周圍的極大值的峰上。
下章預(yù)告
本章只是求解了一個(gè)二元函數(shù)蹄衷，下一章我們將來解決一個(gè)實(shí)際模型忧额，來看一下遺傳算法怎么求解不同的模型。
喜歡的話麻煩點(diǎn)個(gè)喜歡哦~
