本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
遗传算法（Genetic Algorithm，GA）是一种借鉴生物遗传进化机制而设计的智能优化算法
本文讲解遗传算法的思想和具体算法流程，并展示遗传算法解决函数最优化问题的具体例子
通过本文，可以快速了解什么是遗传算法，遗传算法流程，以及如何使用遗传算法来解决优化问题
本节介绍遗传算法的思想与机制,初步了解遗传算法是什么
遗传算法的思想
遗传算法是一种借鉴生物遗传进化机制而设计的寻优算法
生物在多代种群迭代中，优胜劣态，最终种群越来越优秀
这种机制可以迁移到我们的数学求最优值问题上来
种群个体就相当于我们的解，目标函数就是衡量这个个体优秀程度的指标
所以我们可以借鉴生物是怎么进化到一个优秀个体，来让我们的解，也进化（寻找）到一个更优秀的解
遗传算法的机制介绍
遗传算法是以生物进化的概念而设计的一种寻优算法
主要借鉴的机制有三，如下：
👉1. 种群与编码
👉2. 染色体交换与基因突变
👉3. 适者生存
种群与编码
在刚开始时，遗传算法会先初始化一个种群，即一组X
种群的个体(即每个X)都以编码的形式存在，如下
染色体交换与基因突变
然后遗传算法通过个体之间的染色体交换和基因突变来产生新的种群
适者生存
最后，根据种群个体的适应度来选择是否能遗留到下一代种群
通过这种机制，不断的迭代，使得种群的质量不断优化
直到种群无法进化，或者达到最大迭代次数时，终止迭代，最后输出最优的个体
本节讲解遗传算法的具体算法流程，以及展示遗传算法流程图
遗传算法的算法流程
遗传算法的算法流程
遗传算法(Genetic Algorithm，GA)的算法流程如下：
一、初始化种群
初始化g个解
二、迭代T轮
2.1 染色体交换
解与解之间进行部分交换
交换的方式是多种多样，具体问题有具体方案
2.2 基因变异
抽个别解作单独的随机调整
2.3 计算个体适应度
越优秀的解，适应度越大
2.4 赌轮盘选择一下代
(1) 生成轮盘
按适应度占比分配轮盘面积，适应度越大面积就越大
(2) 赌轮盘选择下一代
仍抽g个解作为下一代 ，本轮最优必须进入下一轮，
剩余g-1个通过赌轮盘确定选择哪一个(赌g-1次轮盘)
赌轮盘的方法：
每次生成一个[0,1]之间的随机数，
随机数指向轮盘哪个位置就抽哪个
（有可能重复抽到同一个）
三、输出结果
最后，遗传算法输出历史最优的解作为最终的解
✍️关于遗传算法的自定义内容
遗传算法是一种思想，对于具体的问题，
我们需要自行定义如下部分
(1) 染色体交换的方式（即解与解之间如何进行部分交换）
如果解的形式是一个数值，往往会把它先换为2进制，
再将解进行部分片段交换,以此产生新解
(2) 基因变异的方式（即单个解如何作出随机改变）
(3) 适应度的设计（越优秀值的解适应度越大）
如果是最小化问题，且目标函数恒大于0，
则常见的方法将适应度取为目标函数的倒数
如果解X不是编码形式，还需另外设计如何将X转换成编码形式
例如X如果是数值形式，可以将它转换成二进制形式
遗传算法流程图
遗传算法(Genetic Algorithm，GA)是一种群体寻优算法
遗传算法的算法流程图如下：
遗传算法是一个灵活的算法，流程图中仅包含遗传算法中最基础必备的核心内容
在实际应用中需要根据具体问题设计具体的染色体交换、基因变异方式
本节展示如何使用遗传算法来解决函数最小值问题,以及代码实现
遗传算法例子-解决函数最优化问题
问题
求 为何值时， 取得最小值
易知道，y在处取得最小值0，下面看看遗传算法是否能找到正确解
遗传算法求解数值问题-算法设计
在使用遗传算法时需要先设计遗传算法四个要点
本案例设计如下：
一、编码解码
遗传算法在解决数值问题时，需要将数值转换为编码形式
本问题采用二进制形式作为数值的编码形式，即如下形式：
转为二进制称为“基因编码”，转回十进制则是“基因解码”
二、染色体交换方式
将解群两两随机配对，每一对之间(设为a,b)以如下方式交换：
随机抽取k个位置，将a和b这k个位置的值对调
本案例有x1和x2, 则：a的x1或x2与b的x1或x2按以上方式对调
三、基因变异方式
假设要对a进行基因变异，不妨设a.x1=[0,1,0,1,1,0],
然后对a.x1随机抽个位置，对其取反，同样对a.x2进行变异
例如抽到3，而a.x1的第3位为0，把它变为1
四、适应度设计
我们希望求得的F越小越好，因此F越小，适用度越大
本例采用如下函数作为适应度：
作完以上三个设计后，只需按遗传算法的算法流程进行编码代码即可
遗传算法-代码实现
根据上述设计，结合遗传算法流程，编写代码利用遗传算法求解函数最小值
具体代码如下：
%------代码说明：展示遗传算法求解函数极小值问题 -----------------
% 目标函数为:y = (x1-2)^2+(x2-3)^2,求解x1,x2取何值时y最小
% 来自《老饼讲解神经网络》www.bbbdata.com ,matlab版本：2018a
function gaforfun()
clc;clear all;close all ;
rng(999)
%----------------参数初始化-----------------
m = 30; % 种群规模
t = 1000; % 迭代次数
var_rate = 0.4; % 变异概率
%--------------初始化种群-------------------
bin_num = 20; % 编码位数
xg = cell(m,1); % 初始化种群
for i =1:m
xg{i} = round(rand(2,bin_num)); % 随机初始化种群编码
end
h_best_x = xg{1}; % 初始化历史最优个体
h_best_F = calF(bin2dec(h_best_x)); % 初始化历史最优个体的目标函数值
%----------------迭代主流程------------------
F_list = []; % 每代最优函数值记录列表
for i =1:t
% ----种群交换染色体与基因变异-----
xg = exPart(xg); % 交换染色体
xg = genVar(xg,var_rate); % 基因变异
% ----记录本轮最优与更新历史最优----
[best_x,best_F] = getBest(xg); % 获取本代最佳个体
if(best_F <h_best_F) % 更新历史最优个体
h_best_F = best_F; % 更新历史最优函数值
h_best_x = best_x; % 更新历史最优个体
end
disp(['第',num2str(i),'代:最优F=',num2str(best_F)]) % 显示当前轮的最优个体
F_list = [F_list,best_F]; % 记录历代最优个体
% 判断是否满足退出迭代条件.
% 退出条件:近20代最优个体变化不大，则退出
last_F = F_list(max(1,end-20):end); % 截取最后20轮的最佳函数值
diff = (max(last_F)-min(last_F))/max(abs(mean(last_F)),1); % 最近20轮的差异
if((i>20) && (diff<0.001)) % 判断没什么差异
break % 则退出迭代
end
%-------------赌轮盘生成下一代---------------------------
PPan = getPPan(xg); % 计算种群的概率轮盘
xg = genChildGroup(xg,PPan,h_best_x); % 根据概率轮盘选出下一代种群
end
% 打印最终结果(历史最优)
disp(['h_best_F=',num2str(h_best_F)]) % 打印历史最优目标函数值
disp(['h_best_x=',num2str(bin2dec(h_best_x))]) % 打印历史最优个体
end
% -------目标函数值计算函数------------
function y = calF(x)
y = (x(1)-2).^2+(x(2)-3).^2; % 目标函数:y = (x1-2)^2+(x2-3)^2
end
%------------解码函数:将二进制转为数值--------------
function d = bin2dec(b)
int_num = 12; % 编码中的整数位数
[vn,bin_num] = size(b); % 变量个数与每个变量编码位数
d = zeros(1,vn) ; % 初始化解码后的变量
for i = 1:vn % 逐个变量解码
int_idx = int_num; % 初始化当前位数
for j = 1:bin_num % 逐位解码
if(b(i,j)==1) % 如果编码位置为1
d(i) = d(i) + 2^int_idx; % 则加上对应的数值
end
int_idx=int_idx-1; % 位置减1
end
end
end
%------------染色体交换-------------------------------
function xg = exPart(xg)
m = length(xg); % 种群大小
[vn,n] = size(xg{1}); % 变量个数,编码长度
ex_list = randperm(m); % 随机生成种群排序,用于下面两两匹对交换
for i=1:2:m % 逐对交换
a = xg{ex_list(i)}; % 当前要交换的个体a
b= xg{ex_list(i+1)}; % 当前要交换的个体b
for j=1:vn
ex_part = randperm(n);
ex_part = ex_part(1:fix(n/3)); % 随机交换1/3的片段
a_piece = a(j,ex_part); % a要交换的片段
b_piece = b(j,ex_part); % b要交换的片段
a(j,ex_part) = b_piece; % 将b的片段赋予a
b(j,ex_part )= a_piece; % 将a的片段赋予b
end
xg{ex_list(i)} = a; % 将个体a重新替换回种群
xg{ex_list(i+1)} = b; % 将个体b重新替换回种群
end
end
%------------基因变异-------------------------------
function xg = genVar(xg,var_rate)
m = length(xg); % 种群大小
[vn,n] = size(xg{1}); % 变量个数,编码长度
for i= 1:m
a = xg{i}; % 提取出当前个体
if(rand()<var_rate) % 判断当前个体是否变异
for j = 1:vn % 如果变异,则对当前个体所有变量进行变异
var_part = randperm(n); % 随机生成变异的位置
var_part = var_part(1); % 截断,只变异一个位置
a(j,var_part)=1- a(j,var_part); % 将选择的位置进行取反,如果原来是0,则取1,如果原来是1,则取0
end
xg{i} = a ; % 将变异后的个体替换进种群
end
end
end
%------------获取种群中目标函数值最好的一个----------------
function [x,F]=getBest(xg)
F_list = inf(length(xg),1); % 初始化各个个体的函数值
for i = 1:length(xg)
F_list(i) = calF(bin2dec(xg{i})); % 计算各个个体的目标函数值
end
[F,best_index] =min(F_list) ; % 获取最优的目标函数值与索引
x = xg{best_index}; % 根据索引获取最优的个体
end
%------------计算种群进入下一代的概率轮盘-----------------
function PPan = getPPan(xg)
F_list = inf(length(xg),1); % 初始化各个个体的函数值
for i = 1:length(xg)
F_list(i) = calF(bin2dec(xg{i})); % 计算各个个体的目标函数值
end
F_list = F_list - min(F_list); % 令函数值全大于0
acp_list = 1./(1+F_list); % 计算适应度
PPan = cumsum(acp_list./sum(acp_list)); % 根据适应度计算轮盘概率
end
%------------生成下代种群-------------------------------
function child_xg = genChildGroup(xg,PPan,best_x)
m = length(xg); % 种群个数
child_xg = cell(m,1); % 初始化下一代种群
child_xg{1} = best_x; % 最佳的必定选到下一个种群
for i=2:m
select_idx = min(find(rand()<PPan)); % 生成一个随机数,并找到第一个小于该随机数的位置,就是轮盘指向的位置
child_xg{i} = xg{select_idx}; % 将轮盘选出的个体选入下一代种群
end
end运行结果如下：
第1代:最优F=671149.5123
第2代:最优F=315001.0123
第3代:最优F=310568.1261
第4代:最优F=6982.7277
.....
第82代:最优F=0.00024414
第83代:最优F=0.00024414
第84代:最优F=0.00024414
h_best_F=0.00024414
h_best_x=2.0156 3
可以看到，最后的解为x1= 2.0156，x2 = 3，
与预期的x1= 2, x2=3已经非常接近,说明该算法是有效的
End