遗传算法与多目标优化

遗传算法简介主要内容1、遗传算法的原理和组成；2、遗传算子；3、遗传算法的实现；4、遗传算法的数学理论；5、遗传算法的应用。一、遗传算法（Geneticalgorithm，GA）GA的寻优机制GA模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。美国J.Holland教授1975年《自然界和人工系统的适应性》GA的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数编码•GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。GA通常使用二进制串进行编码。编码示例•例1求下列一元函数的最大值：•x∈[-1,2]，求解结果精确到6位小数。0.2)10sin()(xxxf•由于区间长度为3，求解结果精确到6位小数•可将自变量定义区间划分为3×10^6等份。•又因为2^213×10^62^22，所以本例的二进制编码长度至少需要22位。•本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。几个术语•基因型：1000101110110101000111•表现型：0.637197编码解码个体（染色体）基因多维优化如何编码？•缺点是什么？初始种群•GA可采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。如何随机生成？适应度函数•遗传算法对一个个体（解）的好坏用适应度函数值（通常为正实数）来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。适应度函数的编制影响求解效果选择算子•遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。GA中选择算子可采用轮盘赌选择方法。1、个体被选择概率的计算被选择概率00.1440.6360.69111234各个体被分配的区间2、轮盘赌选择方法（或比例选择算子）00.1440.6360.69111234各个体区间有序随机数产生随机数0.95010.23110.60680.48600.23110.48600.60680.95010.23110.144?否个体1落选0.23110.636?是个体2入选0.48060.636?是个体2入选0.60680.636?是个体2入选0.95010.636?否个体2落选0.95010.691?否个体3落选0.95011?是个体4入选最终选择了3个个体2，1个个体43、轮盘赌选择方法的实现步骤•（1）计算群体中所有个体的适应度函数值（需要解码）；•（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；•（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。交叉算子•所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。GA中交叉算子可采用单点交叉算子。单点交叉运算示例•交叉前：•00000|01110000000010000•11100|00000111111000101•交叉后：•00000|00000111111000101•11100|01110000000010000交叉点•实数编码如何交叉？如何决定哪对个体应交叉？变异算子•所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。GA中变异算子可采用基本位变异算子。基本位变异算子•基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。基本位变异算子的执行过程•变异前：•000001110000000010000•变异后：•000001110001000010000变异点•如何决定哪个个体变异？实数编码个体如何变异？运行参数•（1）M：种群规模（20-100）•（2）T：遗传运算的终止进化代数（100～500）•（3）Pc：交叉概率（0.4～0.9）•（4）Pm：变异概率（0.001～0.01）SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次遗传算法的特点•（1）群体搜索，易于并行化处理；•（2）不是盲目穷举，而是启发式搜索；•（3）适应度函数不受连续、可微等条件的约束，适用范围很广。2221maxxx二、遗传算法的数学原理模式的概念个体编码串适应度01110134101011340111002511100150平均适应度35.75个体编码串适应度01110134111111981110015011101053平均适应度58.75第1代群体第2代群体?模式是指种群个体基因串中的相似样板111***–模式H中确定位置的个数称为模式H的阶，记作O(H)。例如O(10**1)=3。–模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4。模式的阶与定义距模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。模式定理•模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。•模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。模式定理的含义•从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。积木块假设•积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。•模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。三、遗传算法的应用示例测试函数512511211cos1cos,maxiiixiiixiixxf051015202530354045501012141618202224262830epochFitness•Pc=0.8;Pm=0.05;b=2;•popSize=30;epochs=50;实数编码GA运行结果四、多目标优化简介一、问题定义Tmfff)(),...,(),()(min21xxxxFJjhIigtsji,...,2,1,0)(,...,2,1,0)(..xx•具有多个目标函数。•各个函数之间在最优化方向上存在冲突。•往往需要人的参与。•目标函数集要么是求极大，要么是求极小，两者只能取其一。二、发展简史法国经济学家V.Pareto，1896年提出Von.Neumann和J.Morgenstern提出多目标决策问题，1944年T.C.Koopmans多目标最优化问题，Pareto最优解概念，1951年H.W.Kuhn和A.W.T.Tucker向量极值问题的Pareto最优解的概念Z.Johnsen系统地提出了关于多目标决策问题的研究报告，1968年1由人来判断（非Pareto机制）•基本原则：通过加入决策者判断，缩小多目标问题有效解集的范围。2不由人来判断(Paretooptimality)•基本原则：多目标问题优化解的自身特性来搜索多目标问题有效解集的范围。三、多目标优化的最优性判断•加权:由决策者决定每个目标函数不同的权重因子，将所有的目标函数整合为一个目标函数。•目标规划：由决策者确定每个目标函数所能达到的目标值，然后将这些值作为附加的约束整合进问题中，从而优化目标转换为最大或最小化目标值和目标函数值之间的绝对偏差。由人来判断四、Pareto最优解概念占优1、对于所有j=1,2,…,m，有1xjf2xjf不劣于2、至少存在一个mj,...,2,11xjf2xjf优于，有非劣解集（Non-dominatedset）在一组解P中，非劣解解集P’是指所有那些不被P中任何个体占优的解组成的一组解。当P是整个搜索空间时，所得的非劣解集P’被称为Pareto最优解集。若目标函数中有冲突，则一般不存在唯一最优解，而存在若干个可行解。Pareto最优解示意图Pareto最优解不一定对其他所有解占优，但是所有其他解都不能对它占优。ABCXYf1f2解点A,B,C是Pareto最优点APareto支配XCPareto支配YMin[f1,f2]五、基于进化算法的求解方法•每轮迭代可以找到多个Pareto近似最优解•迄今为止还没有找到其他方法比EAs更能有效地解决MOP问题。•在许多复杂应用问题中搜索最优解还存在一定的困难。如何使用GA求解多目标规划问题•适应度函数值•解集的均匀分布要求•对非劣解集的分析进化算法的解更新过程示意minmax同时考虑最大化主产物浓度CB和最小化生产时间tf多目标优化方案的Pareto最优前沿