华为杯研赛数学建模之遗传算法

1047521767

遗传算法简介
维基百科上的概念如下
遗传算法（英语：genetic algorithm (GA) ）是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
: I: s0 {+ {5 Q! O1 T. I0 {
遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

这看起来是不是很抽象？没关系，我们举一个例子
比如你家住的那一块地方有一群老鼠，有一些跑得快而且也聪明，有一些傻得大白天在你面前跳舞，然后理所当然就被你捕获然后进行土葬。故那群跑得快而且也聪明自然活下来的概率比傻的大的多，我们称老鼠是否活下来为适应度，适应度高的更容易在你手上活下来，而低的更容易被你土葬。活下来的老鼠们，它们中大多都是适应度高的，它们进行交配繁殖，老鼠子类大多都是继承了老鼠父母的特点，当然也存在一定几率变异，变异数除以总体老鼠为变异率，变异率一般都不是很大的常数。但总体来说，由于淘汰机制，故所产生的鼠类比起它们的父类，平均来说更为聪明。通过一代代的优化，使得老鼠越来越聪明，而你越来越抓不到老鼠。这就是遗传算法的核心。
% W" I8 |5 V4 f  i
遗传算法的步骤
1.编码
' @! _" n+ f0 T  N/ w编码有多种，如二进制编码，浮点数编码，格雷码等。最常见的是二进制编码和浮点数编码。
; _- k& H4 h0 t4 C
二进制编码
二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
优点：
2 j" C- t: V: X" }' @8 B: T) m
2 e* r% r4 C7 U% ]" C简单。无论是编码还是解码操作都非常方便和快捷。
( \7 j# X7 V. a& a+ `方便交叉和变异。
符合最小字符集编码原则。
缺点：

( m- N, s  B, S/ g! @2 z% ~不适合连续函数的优化问题，局部搜索能力差。
2 K7 f: E# N/ h  G8 Q% p连续的数值之间有时候存在距离大的问题。例如63和64对应的二进制分别是0111111和1000000。（连续数值对应的二进制数7位全都不同）
对于高精度的问题，变异后可能会出现远离最优解的情况，表现型不稳定。
) I! {. f" j6 {8 d案例：
. Y  {5 a1 G' W7 J: _" u0 m, X# z假设有f(x)，x∈[0,1023],采用定长二进制编码,串0010101111就代表了175，编码精度为1.

$ F% ]. g7 ?. c8 a" F$ q浮点数编码
定义：
个体基因值用某范围内的一个实数来表示。编码长度等于决策变量的个数。
优点：

4 V/ L+ A( b: `精度高，适用于连续变量问题。避免了海明悬崖问题。
9 L4 I! `# Y! A/ Z3 a" q适用于表示范围比较大的数值，适合空间较大的一串算搜索
降低了计算复杂性，提升效率
3 S/ @+ |" t: j' n, c: a便于遗传算法与经典优化方法的混合使用
/ m) l, w  c0 N- a" p7 W, }+ l便于设计针对问题的专门知识的知识型遗传算子
便于处理复杂的决策变量约束条件，适合于组合优化问题
案例：
假设某优化问题有五个变量，每个变量的变化范围都不同。其中X={5.30,5.20,4.70,3.40,4.80}就是一个基因型，对应的表现型是x={5.30,5.20,4.70,3.40,4.80}。

( L; a4 V# ^# f+ M0 M2.解码
. X6 H; f7 r$ a8 e以二进制为例。
解码的目的就是将不直观的二进制数据串还原成十进制。

5 j( E* D3 _* @3.交配（交叉）
/ Q2 V6 M7 s" d以二进制为例。
“交配运算”是使用单点或多点进行交叉的算子。首先用随机数产生一个或多个交配点位置，然后两个个体在交配点位置互换部分基因码，形成两个子个体。例如，两条染色体S1=01001011，S2=10010101。交换其后4位基因，得S1’=01000101,S2’=10011011可以被看做原染色体S1和S2的子代染色体。
( r3 `1 L3 W1 A
9 \9 o2 A7 p2 b8 T% H4.变异
突变
" c- E4 O) d; x8 O) S: z. U突变是指基因突变。例如对于S1=010110011，第三位0突变成1，那么我们得到S1‘=011110011。
倒位
( t/ Y+ F$ j+ O! A0 N2 X倒位是指一个染色体某区段正常排列顺序发生180°的颠倒，造成染色体内的DNA序列重新排列。例如对于S1=1010100010110110101001进行倒位时得到S1‘=010101101000110101001。
其他
8 _, l  C& B" G! A+ b不一一举例，大家自行查阅理解。

  {- S$ l/ k& K4 M; R$ X* r6 @) m6 D+ d5 F6.适应度评估
" }( O- C4 c& }4 r% ~! R遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体的机会。个体适应度大的个体更容易被遗传到下一代。通常情况下，求目标函数最大值的问题可以直接把目标函数作为检测个体适应度大小的函数
* L( P, \" n  E9 V$ S
7.选择
, T5 i" o' v, f7 W选择运算时根据个体适应度大小决定其下代遗传的可能性。设种群中个体总数为N，个体i的适应度为fi，则个体i被选取的几率为：
! ?" s6 }# T% ?4 Q

遗传算法伪代码
, h+ X. G9 r5 {* |. T9 yBEGIN
8 O, _) _  A7 Z. [/ O: B    t = 0;                       %遗传代数
    初始化P(t);                  %初始化种群或者染色体
/ W; [9 e! M7 V5 b    计算P(t)的适应值;
    while(不满足停止准则) do
        begin
        t = t+1;
. v% j9 n3 [5 I! f. H( v        从P(t-1)中选择P(t);       %选择
, [; W/ U* O* b4 z        重组P(t);                 %交叉或变异
        计算P(t)的适应值;
         end
    end
END
遗传算法工具箱
如果前面没看懂，没关系！！！为了省略艰深难懂的遗传算法，MATLAB软件做成了专门的遗传算法工具箱GA Toolbox,方便用户调用。（但有时候遗传工具并不是万能的，很多的情况下更需要具体问题具体分析）
/ T7 l$ a$ r$ s2 f我们在MATLAB中帮助文档查看ga函数的定义
Find minimum of function using genetic algorithm
意思就是通过使用遗传算法找到函数的最小值。
它的用法，如下：
x = ga(fitnessfcn,nvars)
x = ga(fitnessfcn,nvars,A,b)
x = ga(fitnessfcn,nvars,A,b,Aeq,beq)
7 E5 v  c% I8 L( K4 g+ r  _x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)
" G% R8 R$ A  g; l  Jx = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)
x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)
( I- u7 p9 ?& ~1 X8 zx = ga(fitnessfcn,nvars,A,b,[],[],LB,UB,nonlcon,IntCon)
+ H# \5 h  _* I( Q7 O' ?x = ga(fitnessfcn,nvars,A,b,[],[],LB,UB,nonlcon,IntCon,options)
0 i8 E1 t$ A& |: }/ Yx = ga(problem)
[x,fval] = ga(fitnessfcn,nvars,…)
[x,fval,exitflag] = ga(fitnessfcn,nvars,…)
$ L% X. H7 r) |, i[x,fval,exitflag,output] = ga(fitnessfcn,nvars,…)
[x,fval,exitflag,output,population] = ga(fitnessfcn,nvars,…)
[x,fval,exitflag,output,population,scores] = ga(fitnessfcn,nvars,…)
x为经过遗传进化以后的自变量最佳染色体返回值；fval为最佳染色体的适应度，exitflag为算法停止的原因；output为包含每一代输出的结构以及有关算法性能的其他信息；population返回矩阵，群体其行是最终总体；scores返回最终群体的得分。
; h) q" ?* N  V8 Efitnessfcn为适应度函数，nvars为目标函数自变量的个数，A,b,Aeq,beq为约束条件（与线性规划类似）LB,UB为自变量的上界和下界；函数nonlcon接受x并返回矢量C和Ceq，分别表示非线性不等式和等式；IntCon要求中列出的变量采用整数值；options为默认优化参数由options中的值替换。
我们用的更多的是这种
[x,fval] = ga(fitnessfcn,nvars,options)
令options=gaoptimset()函数，gaoptimset函数用法如下：

属性如下：



0 g# s; _' }; m

9 r" ?; R, q1 L; q: u) T/ x  D