现代智能优化算法遗传算法

现代智能优化算法—

遗传算法2008年2月1简介1995毕业于东北电力学院，获学士学位2000年毕业于东北电力学院，获硕士学位2005年毕业于天津大学，获博士学位2007年UniveristyofStrathclyde博士后2现代智能优化算法遗传算法禁忌算法蚁群算法粒子群算法细菌算法混沌算法TSGAACOPSOBCCOA混沌算法DE3遗传算法（GeneticAlgorithm,GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它是由美国Michigan大学的J.Holland教授于1975年首先提出的。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制等领域，是21世界有关智能计算中的关键技术之一。4GA四个基本条件1.存在由多个生物个体組成的种群2.生物个体之间存在着差异，或全体具有

多样性3.生物能够自我繁殖4.不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力強，反之則弱5GA--特点遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。6GA--特点遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。7达尔文1858年用自然选择来解释物种起源和生物的进化，其自然选择学说包括以下三个方面1遗传种瓜得瓜，种豆得豆。生物有了这个特征，物种才能稳定存在；2变异一母生九子，九子各不同。变异的选择和积累是生物多样性的根源；3适者生存具有适应性变异的个体被保留下来，通过一代代生存环境的选择作用，物种一代代进化，演变为新的物种8GA的基础术语染色体（Chromosome）生物细胞中含有的一种微小的丝状化合物。是遗传物质的主要载体，由多个遗传基因组成DNA&RNAinthechromosome基因（gene）也称遗传因子，DNA或RNA长链中占有一定位置的基本单位。生物的基因数量根据物种不同多少不一，从几个（病毒）到几万个（动物）。9GA的基础术语基因座（locus）染色体中基因的位置表现型（phenotype）由染色体决定性状的外部表现基因型（genetype）与表现型密切相关的基因组成个体（individual）指染色体带有特征的实体种群（population）一定数量个体的集合10GA的基础术语适应度（fitness）个体对环境的适应程度进化（evolution）生物逐渐适应其生存环境，使得其品质不断提高选择（selection）指决定以一定概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程复制（reproduction）细胞分裂时，遗传物质DNA通过复制转移到新的细胞中，新的细胞就继承了旧细胞的基因11GA的基础术语交叉（crossover）两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体变异（mutation）在细胞复制时，基因的某个位发生某种突变，产生新的染色体编码（coding）DNA中遗传信息按一定的方式排列，也可看作从表现型到遗传型的映射解码（decoding）从遗传型到表现型的映射12GA的三个基本算子复制／选择(Reproduction/Selection)

依据每一物种的适应程度来决定其在下一代中应被复制或淘汰个数的多少轮盘式选择竞争式选择13GA三个基本算子—交叉

交叉式一种提供个体间彼此交换信息的机制，交叉过程主要是母代中较优良的染色体作某些基因的交换，预期产生更优良的后代。一般常见的交叉方式有：

（1）单点交叉(One-pointcrossover)

（2）双点交叉(Tail-tailcrossover)

（3）均匀交叉14GA三个基本算子—变异

通过突变的方式，使得解可以跳脱单纯的交叉产生的区域，进而产生新的染色体，变异的过程主要以随机的方式，将染色体的基因位由0变成1或由1变成0，主要的变异方式有：（1）等位基因突变(SimpleMutation)（2）均匀突变(UniformMutation)（3）非均匀突变(Non-UniformMutation)15GA的基本流程根据问题编码，并初始化种群计算群体适应度选择操作交叉操作变异操作满足收敛条件否N输出计算结果Y16算例说明—编码求解问题maxf(x)=x2

[0,31]x取正整数第一步：编码采用二进制形式我们把变量x编码为5位长的二进制无符号整数表示形式0000003111111700111120110017算例说明—种群生成第二步初始种群的生成由于遗传算法的群体型操作需要，所以为遗传操作准备了一个由若干初始解组成的初始群体。这里我们取群体大小为4，即群体由4个个体组成，每个个体通过随机初始化产生初始群体也称为进化的初始代，即第一代（firstgeneration），初始化后，群体为

01101110000100010011

18算例说明—适应度评价遗传算法用评价函数（适应度函数值）来评估个体（解）的优劣，并作为以后遗传操作的依据。这里我们根据f(x)=x2

在评价个体适应度值大小时，首先要解码，即把基因型个体变成表现型个体（即搜索空间的解）这里就是二进制到十进制的转换基因型01101110000100010011表现型x

1324819f(x)=x2169

57664361

（适应值）19算例说明—选择选择概率适应度总和1170，平均值293运用轮盘赌选择结果1201计算结果为0.140.490.060.3120算例说明—选择初始族群適應值E(i)複製個數011101960.180.711110005760.522.072100012890.261.04100111490.040.180初始族群01110110001000100111选择后0111011000100011100021算例说明—交叉单点交叉为例两个染色体1011100111001100假设交叉点在位置41011|10011100|1100101111001100100122算例说明—交叉01110110001100010001选择后的结果配对情况1和2配对3和4配对

01110110001100010001交叉点选择第一对位置3，第二对位置1交叉前01|1101100|011|0001000|1交叉后0100011001111101000023算例说明—交叉交配池配對交叉点交叉后xf(x)011102301000864110001311110309001100041110012562510001311000016256f=1845平均适应度值f=46124算例说明—变异变异基因数的决定基因总数×变异概率=(4×5)×0.1=2

有兩個基因將被突變随机选取染色体进行变异随机选取要变异染色体的基因位变异目的在避免陷入局部最优解25算例说明—变异01000110011111010000假设变异基因发生在第一个染色体的第3位和第四个染色体的第二位上变异就是把二进制的0变成1把1变成0变异前01000110011111010000变异后0110011001111101001026算例说明—变异变异池是否有变异变异点变异后ff(x)01000是3011001010011001否3111103090011110否1110012562510000是11001018324f=1949

平均适应度值f=48727算例说明—进化过程进化代数染色体xf(x)f平均值最佳值1011011100001000100111324819169576

6436111702921920110011001111101001012133018144169900324

15373843031010011001111101101022233024484529900576248962230410101111011111100010

29312

841961422475623128算例说明—终止准则一般而言，遗传算法终止条件有以下几种：

（1）达到最大的进化代数；

（2）所求的解达到可接受的范围；

（3）连续几代最佳解无变化或变化非常微小；

（4）达到最大的运算时间。29遗传算法--参数配置种群数量视具体问题和解空间的维数问题越复杂，维数越高，种群数量要求越大遗传运算的终止进化代数根据问题的复杂程度，一般取为100~500交叉率一般选取范围在0.4~0.99之间变异率一般选取范围在0.001~0.1之间现代一般采用自适应变化的交叉率和变异率30遗传算法—应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。31遗传算法—应用组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。32遗传算法—应用生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。33遗传算法—应用自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结