【优化】一篇入门之-遗传算法(GA)

遗传算法(Genetic Algorithm，GA)可以说是智能优化算法中的老大哥了，许多人接触智能优化算法，都是从遗传算法开始的，它是一种借鉴生物遗传进化机制而设计的优化算法，那么今天我们就来看看遗传算法是什么吧~然后再用代码来实现它，看一看它在函数优化上的效果。

一、遗传算法-GA

1.1. 遗传算法是什么

遗传算法是一种借鉴生物遗传进化机制而设计的智能优化算法，生物在多代种群迭代中，优胜劣态，最终种群越来越优秀，这种机制可以迁移到我们的数学求最优值问题上来：

遗传算法借鉴物竞天择的原理，种群个体就相当于我们的解，目标函数就是衡量这个个体优秀程度的指标，所以遗传算法就是借鉴生物是怎么将一个渣渣群体进化到一个优秀群体，来让我们的解也进化(寻找)到一批更优秀的解，然后再从中挑出最好的解。

1.2. 遗传算法的机制介绍

好了，要理解遗传算法，就先理解它借鉴生物进化中的三个概念：

1. 种群与编码

2. 染色体交换与基因突变

3. 适者生存

种群与编码

先来说说种群与编码，在刚开始时，遗传算法会先初始化一个种群，也就是一批X，然后种群的个体(也就是单个X)都以编码的形式存在，如下：

不了解什么是编码也没关系，看下去自然就会知道了，总的来说，就是每一代都是一批X，然后将这批X不断进化，最后再挑出整批X中最好的。

染色体交换与基因突变

好了，我们再来说说遗传算法中的染色体交换与基因突变。

遗传算法是怎么产生新的解的呢？它主要通过个体之间的染色体交换，和基因突变来产生新的个体。

如图，染色体交换就是两个个体之间，交换一段编码，而基因突变呢，就是以一定的概率来对单个个体做出一些大胆的修改。

适者生存

最后，根据种群个体的适应度来选择是否能遗留到下一代种群：

如图所示，适应度越大的个体，就会有更大的概率被遗留到下一代，通过这种机制，不断的迭代，使得种群的质量不断优化，直到种群无法进化，或者达到最大迭代次数时，终止迭代，最后输出最优的个体。

如果看到这里，还是糊糊涂涂的，那也是没关系的，有个大概的印象就可以了，看下去就会越来越具体、越来越明白是怎么一回事了，有时学习就像拼拼图，东一块西一块，最后不知不觉中就完整了。

二、遗传算法-算法流程

好了，了解了上面的概念，我们就可以来正式地说说遗传算法的具体、完整算法流程了。

2.1. 遗传算法的算法流程

遗传算法(Genetic Algorithm，GA)的算法流程如下：

一、初始化种群

       初始化g个解

二、迭代T轮

2.1. 染色体交换

       解与解之间进行部分交换，交换的方式是多种多样，具体问题有具体方案

2.2. 基因变异

       抽个别解作单独的随机调整

2.3. 计算个体适应度

       越优秀的解，适应度越大

2.4. 赌轮盘选择一下代

       (1) 生成轮盘

            按适应度占比分配轮盘面积，适应度越大面积就越大

       (2) 赌轮盘选择下一代

            仍抽g个解作为下一代 ，本轮最优必须进入下一轮，

            剩余g-1个通过赌轮盘确定选择哪一个(赌g-1次轮盘)

       赌轮盘的方法：

       每次生成一个(0,1)之间的随机数，随机数指向轮盘哪个位置就抽哪个（有可能重复抽到同一个）。

三、输出结果

       最后，遗传算法输出历史最优的解作为最终的解

2.2. 遗传算法中的编码

特别地，有时我们的解X，并不是编码形式，例如我们的X是个数值的时候，它就不是编码形式，这时候可以把它转换成二进制形式，就会变成编码形式了，如下：

当然，也可以使用其它的编码方式，但数值型的X，一般都是转换为二进制编码形式，如果不知道二进制编码是什么的，自己去百度一下就行了。

2.3. 关于遗传算法的自定义内容

值得注意的是，遗传算法是一种开放式算法，对于具体的问题，我们需要自行定义如下部分：

1. 染色体交换的方式

    也就是解与解之间如何进行部分交换

2. 基因变异的方式

    也就是单个解如何作出随机改变

3. 适应度的设计

    也就是怎么衡量解的优秀程度

三、遗传算法流程图

好了，最后的最后，我们来看一下遗传算法的算法流程图吧，如下：

 遗传算法是一个灵活的算法，流程图中仅包含遗传算法中最基础必备的核心内容，在实际应用中需要根据具体问题设计具体的染色体交换、基因变异方式。

四、遗传算法-代码实现

下面我们就实际来使用一下遗传算法吧，作为学习我们用它来优化一个简单的函数：

容易知道，y的最小值在处取得最小值0，下面我们使用遗传算法来进行求解，看看它能不能找到这个最优值，闲话少说，直接上代码，如下：

% 本代码展示遗传算法求解函数极小值问题,目标函数为:y = (x1-2)^2+(x2-3)^2
% 本代码来自《老饼讲解神经网络》www.bbblearn.com ,matlab版本：2018a   
function gaforfun()
clc;clear all;close all ;
setdemorandstream(888);                                         % 为方便复现结果,设定随机种子
%----------------参数初始化-----------------                                
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);                     % 将选择的位置进行取反
        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

代码运行结果如下：

可以看到，最后的解为，与预期的x1= 2, x2=3已经非常接近，说明算法是有效的。

总结

遗传算法就是靠染色体交换与基因突变来产生新的种群，然后再通过赌轮盘的方式来选出更优的个体作为下一代，通过这样不断地进化，使得最后的种群越来越优秀，在使用时，要根据自己的问题，设计一下染色体交换、基因突变、和适应度函数，当然，套用固定的方法也是可以的，但效果自然也会受到一定的限制。