从冰糖葫芦说遗传算法

巴山学长

发布于 2019-07-15 15:11:50

5490

发布于 2019-07-15 15:11:50

Hello,大家好。今天我们来聊一聊GA(遗传算法)。见名知意，GA是科学家们从生物学上得来的启示,这一渊源早已在江湖上流传,就不赘言。本文希望能用糖葫芦帮助初学者们一窥GA,了解具体的糖(真)葫(的)芦(皮)制作流程以及如何用Matlab实现简单优化。

1遗传算法中四个重要元素

问题编码（以二进制为例）

初始群体的设定（具有一定随机性）

适应度函数的设计（分段盈利函数）

控制参数设定（种群规模,变异率,交叉率,最大代数等）

2 基础概念

王二狗卖糖葫芦。他就问了，到底是山楂赚钱多还是橘子赚钱多？假设用橘子来表示1，山楂来表示0，它们的串在一起表示的二进制位所代表的十进制数值就是他们的价格，一串山楂价格为：00000(0)一串橘子价格为 11111(31)。设收入函数为：

上述问题相当于求分段函数S的极大值。可以知道在初代中应该选择卖橘子。种群规模为2,交叉率为100%,变异率为0。种群空间为

S = {0,1}2

设t为繁衍代数, s1, s2为初代种群中的两个个体。

突然有一天，王二狗想掺在一起卖，一根糖葫芦又想穿山楂又想穿橘子

种群与个体

按照利润函数来看,这样的卖法利润比前两种更大。继续迭代下去就能得出问题的最优解。

3 流程

王二狗总结了上述过程，他认为这个套路可以这么理解：

4 举个栗子

4.1 流程讲解及代码示例

下面通过一个例子来详细了解GA。求以下函数在（0,31）上的极值：

王二狗眉头一皱，发现这个问题并不是求导辣么简单。原问题可转化为在区间（0,31）中搜案能使y取最大值的点a的问题。求解步骤为：

（1）选择适合问题的一个编码方式，定义一个适应度函数，给定种群随机产生种群空间的N个个体，组成初始种群。置种群代数计数器t＝1

本例中采用5位二进制数编码染色体，将种群规模设定为4，取下列个体组成初始种群

s1=13(01101) s2=24(11000) s3=8(01000) s4=19(10011)

（2）根据问题以及编码方式定义适应度函数为目标函数

（3）计算各代种群中各个体的适应度，并对其染色体进行遗传操作

迭代的过程为：

第一代种，首先计算种群S中各个体s的适应度如下

再计算种群S中各个体的选择概率

4）若满足算法终止规则，则算法停止，取S中适应度最大的个体作为所求结果，否则按照赌轮选择法决定的在下一代的选中机会，每次从S中随机选定1个个体并将其染色（复制），共做N次，然后将复制所得的N个染色体组成群体S。

赌轮选择法的示意图如图所示。下面的子过程可以大致模拟：

a 在（0,1）区间内产生一个均匀分布的随机数r； b 若r≤q1，则染色体x1被选中； c 若q(k-1)＜r≤qk（2≤k≤M)，则染色体xk被选中；其中的q称为染色体x（i＝1，2…，n）的积累概率，公式为：

一看公式王二狗有点蒙圈，但他比划比划觉得这个公式或许可以是介样子滴：

在（0,1）中所得的随机数在下图中画为一条横线（红色）

再经过变异和交叉迭代后即可。由于这个函数比较简单，所以可以直接使用matlab中的缺省设置。

function y = ga_square(x) 
y = -x^2;  % ga调用格式默认求极小值

LB=zeros(1,1)；
UB=[31];
x=ga(@ga_square,1,[],[]，[],[],LB,UB);

遗传算法中在选中有随机性因素，所以调用该算法每次得出的结果均不相同，但多运行几次，结果是差不多滴。

4.2 Rastrigin函数测试

Rastrigin函数：

Rastrigin 是最常用于遗传算法测试的函数之一，因为它拥有很多局部极值点，使用老方法查找全局极值十分困难。

不止一个极值点

咳咳，不好意思，放错图了。应该是下面这张。

Rastrigin函数有很多局部极值点

在使用遗传算法时，也相对复杂一些，需要调整一些参数，避免种群迭代过程中优化效果不明显（种群早熟）。

function y = ga_rastrigin(x)
y=20+x(1)^2+x(2)^2-10*(cos(2*pi*x(1))+cos(2*pix(2)));

% 种群大小为500，交叉率0.85,变异率0.15,最大代数500
fitnessfcn=@ga_rastrigin;
nvars=2;
options=gaoptimset;
options=gaoptimset(options,'PopulationSize',500);
options=gaoptimset(options,'CrossoverFraction',0.85);
options=gaoptimset(options,'MigrationFraction',0.15);
options=gaoptimset(options,'Generations',500);
[x,fval,exitflag]=ga(fitnessfcn,nvars,options);

好了，浅显的介绍就到这里了。更多关于遗传算法的探讨请继续关注Matlab爱好者公众号！辉夜大小姐诚邀您点赞，转发和关注！