一文读懂遗传算法及其运用

杨利霞

& o$ l2 s5 z' o# a
( x  V% [3 G: E. I

一文读懂遗传算法及其运用

郑铿城

遗传算法（Genetic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是20世纪70年代初期由美国密执根（Michigan）大学的霍兰（Holland）教授发展起来的。迄今为止，遗传算法是进化算法中最广为人知的算法。
& V6 K' A, @' I9 f遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了一些令人信服的成果，所以引起了很多人的关注。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题，等等。1．遗传算法具有以下几方面的特点。遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此操作使得遗传算法可以直接对结构对象进行操作。许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。遗传算法基本上不用搜索空间的知识或其他辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的限制，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展了。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导搜索的方向。具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索，适应度大的个体具有较高的生存概率，并能获得更适应环境的基因结构。2．遗传算法中的基本概念群体（population）：又称种群、染色体群，是个体（individual）的集合，代表问题的解空间子集。串（string）及串空间：串是个体的表达形式，对应着遗传学中的染色体，对应实际问题的一个解。群体规模（population size）：染色体群中个体的数目称为群体的大小或群体规模。基因（gene）：是指染色体的一个片段，可以是一个数值、一组数或一串字符。交换（crossover）：指在一定条件下两条染色体上的一个或几个基因相互交换位置。交换概率：判断是否满足交换条件的一个小于1的阈值。变异（mutation）：指在一定条件下随机改变一条染色体上的一个或几个基因值。变异概率：判断是否满足变异条件的一个小于1的阈值。后代：染色体经过交换或变异后形成的新的个体。适应度（fittness）：用来度量种群中个体优劣（符合条件的程度）的指标值，它通常表现为数值形式。选择（selection）：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。3．遗传算法终止规则给定一个最大的遗传代数MAXGEN，算法迭代在达到MAXGEN时停止。当进化中两代最优个体小于要求的偏差x时，算法终止。所有个体或者指定比例以上个体趋同，此时停止计算。达到最大计算时间限制。例子：求解file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml8288\wps1.jpg的最小值，x取值范围0～100之间的整数：

首先设置函数：objfun=@(x)(x-50).^2

设置X的取值：x=0:100;

设置Y：y=(x-50).^2;

用plot进行画图：plot(x,y)

设置随机种子：rng(0)

c=randperm(100,4)'

做二进制和十进制的转化：str = dec2bin(c)

第一代

%%%%  选择

idx_choose=reshape(randperm(4),2,2)

cp1=str(idx_choose(:,1),  % 选择配对1

cp2=str(idx_choose(:,2),   % 选择配对2

% 单点交叉，交叉点生成

% cros_p1=randperm(6,1)

% cros_p2=randperm(6,1)

cros_p1=5;

cros_p2=4;

%%%%  交叉

cp1_new=[cp1(1,1:cros_p1) cp1(2,cros_p1+1:end);

bin2dec(cp1)   % 原始数据

bin2dec(cp1_new)  % 新数据

cp2_new=[cp2(1,1:cros_p2) cp2(2,cros_p2+1:end);

bin2dec(cp2)   % 原始数据

bin2dec(cp2_new)  % 新数据

str_new=[cp1_new;

bin2dec(str_new)

%%%%  变异

if str_new(15)=='1'

    str_new(15)='0';

else

    str_new(15)='1';

end

str_new

c_new=bin2dec(str_new)

c_alltemp=[c;c_new]

b=objfun(c_alltemp)

[bbest,idx_b]=sort(b)

c_1=c  % 保存历史数据

c=c_alltemp(idx_b(1:4))

第二代

str = dec2bin(c)

idx_choose= [    2     3

cp1=str(idx_choose(:,1),  % 选择配对1

cp2=str(idx_choose(:,2),   % 选择配对2

% 单点交叉，交叉点生成

% cros_p1=randperm(6,1)

% cros_p2=randperm(6,1)

cros_p1=2;

cros_p2=3;

%%%%  交叉

cp1_new=[cp1(1,1:cros_p1) cp1(2,cros_p1+1:end);

bin2dec(cp1)   % 原始数据

bin2dec(cp1_new)  % 新数据

cp2_new=[cp2(1,1:cros_p2) cp2(2,cros_p2+1:end);

bin2dec(cp2)   % 原始数据

bin2dec(cp2_new)  % 新数据

str_new=[cp1_new;

bin2dec(str_new)

%%%%  变异

if str_new(9)=='1'

    str_new(9)='0';

else

    str_new(9)='1';

end

str_new

c_new=bin2dec(str_new)

c_alltemp=[c;c_new]

b=objfun(c_alltemp)

[bbest,idx_b]=sort(b)

c_2=c  % 保存历史数据

c=c_alltemp(idx_b(1:4))

第三代

str = dec2bin(c)

idx_choose= [    2     3

cp1=str(idx_choose(:,1),  % 选择配对1

cp2=str(idx_choose(:,2),   % 选择配对2

% 单点交叉，交叉点生成

% cros_p1=randperm(6,1)

% cros_p2=randperm(6,1)

cros_p1=5;

cros_p2=2;

%%%%  交叉

cp1_new=[cp1(1,1:cros_p1) cp1(2,cros_p1+1:end);

bin2dec(cp1)   % 原始数据

bin2dec(cp1_new)  % 新数据

cp2_new=[cp2(1,1:cros_p2) cp2(2,cros_p2+1:end);

bin2dec(cp2)   % 原始数据

bin2dec(cp2_new)  % 新数据

str_new=[cp1_new;

bin2dec(str_new)

%%%%  变异

if str_new(3)=='1'

    str_new(3)='0';

else

    str_new(3)='1';

end

if str_new(7)=='1'

    str_new(7)='0';

else

    str_new(7)='1';

end

str_new

c_new=bin2dec(str_new)

c_alltemp=[c;c_new]

b=objfun(c_alltemp)

[bbest,idx_b]=sort(b)

c_3=c  % 保存历史数据

c=c_alltemp(idx_b(1:4))

以上步骤更加细化，如用循环，可表述如下：file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml8288\wps2.jpgfile:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml8288\wps3.jpgfile:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml8288\wps4.jpg在实践运用中，使用ga函数进行遗传算法分析：

file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml8288\wps5.jpg