遗传算法与多目标优化选编课件.ppt

1、1、遗传算法的原理和组成；2、遗传算子；3、遗传算法的实现；4、遗传算法的数学理论；5、遗传算法的应用。一、遗传算法（一、遗传算法（Genetic algorithm，GA） GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。GA通常使用进行编码。 编码示例 例1 求下列一元函数的最大值： 0 . 2)10sin()(xxxf 由于区间长度为3，求解结果精确到6位小数 可将自变量定义区间划分为3106等份。 又因为221 3106 222 ，所以本例的二进制编码长度至少需要22位。 本例的编码过程实质上是将区间-1，2内

2、对应的实数值转化为一个二进制串（b21b20b0）。 基因型：1000101110110101000111 表现型：0.637197 编码解码个体（染色体）基因 GA可采用生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称。 遗传算法对一个个体（解）的好坏用适应度函数值（通常为正实数）来评价，。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：的个体被到下一代群体中的；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，

3、遗传到下一代群体。GA中选择算子可采用选择方法。 00.1440.6360.69111234各个体被分配的区间各个体被分配的区间00.1440.6360.69111234各个体区间各个体区间有序随机数有序随机数产生随机数产生随机数0.144 ? 否个体1落选0.636 ? 是个体2入选0.636 ? 是个体2入选0.636 ? 是个体2入选0.636 ? 否个体2落选0.691 ? 否个体3落选1 ? 是个体4入选 （1） 计算群体中所有个体的适应度函数值（需要解码）； （2） 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率； （3） 采用模拟赌盘操作（即生成0到1之间的随机

4、数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。 所谓交叉运算，是指对两个相互配两个相互配对的染色体对的染色体依据交叉概率交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个形成两个新的个体体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 GA中交叉算子可采用单点交叉算子。 交叉前： 00000 11100 交叉后： 00000 11100交叉点交叉点 所谓变异运算，是指依据 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它

5、决定了遗传算法的，同时。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 GA中变异算子可采用基本位变异算子。 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0 。 变异前： 00000111000 000010000 变异后： 00000111000 000010000变异点变异点 （1）M ： 种群规模（ 20-100 ） （2）T ： 遗传运算的终止进化代数 （100500） （3

6、）Pc ： 交叉概率 （0.40.9） （4）Pm ： 变异概率 （0.0010.01）产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次 （1）群体搜索，易于并行化处理； （2）不是盲目穷举，而是启发式搜索； （3）适应度函数不受连续、可微等条件的约束，适用范围很广。2221 maxxx 二、遗传算法的数学原理二、遗传算法的数学原理模式的概念01110134101011340111002500

7、135.750111013411111198001500105358.75 模式 H 中确定位置的个数称为模式 H 的，记作O(H)。例如O(10*1)=3 。 模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的，记作(H)。例如(10*1)=4 。 模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 模式定理：具有以及于种群平均适应度的模式在子代中呈指数增长。 模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理

8、提供了数学基础。 从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。 积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。 三、遗传算法的应用示例三、遗传算法的应用示例512511211cos1cos, maxiiixiiixiixxf0510

9、15202530354045501012141618202224262830epochFitness一、问题定义一、问题定义Tmfff)(),.,(),()(min21xxxxFJjhIigtsji,.,2 , 1 , 0)(,.,2 , 1 , 0)(. .xx具有多个目标函数。 各个函数之间在最优化方向上存在冲突。 往往需要人的参与。 目标函数集要么是求极大，要么是求极小，两者只能取其一。二、发展简史二、发展简史法国经济学家V. Pareto，1896年提出 Von. Neumann和J. Morgenstern提出多目标决策问题，1944年 T. C. Koopmans 多目标最优化问题

10、 ，Pareto最优解概念，1951年H. W. Kuhn和A. W. T. Tucker 向量极值问题的Pareto最优解的概念Z. Johnsen系统地提出了关于多目标决策问题的研究报告， 1968年1 由人来判断（非Pareto机制） 基本原则：通过加入决策者判断，缩小多目标问题有效解集的范围。2 不由人来判断(Pareto optimality) 基本原则：多目标问题优化解的自身特性来搜索多目标问题有效解集的范围。三、多目标优化的最优性判断三、多目标优化的最优性判断 : 由决策者决定每个目标函数不同的权重因子，将所有的目标函数整合为一个目标函数。 ：由决策者确定每个目标函数所能达到的目

11、标值，然后将这些值作为附加的约束整合进问题中，从而优化目标转换为最大或最小化目标值和目标函数值之间的绝对偏差。四、四、Pareto最优解概念最优解概念1、对于所有j=1,2,m，有 1xjf2xjf不劣于2、至少存在一个 mj,.,2 , 1 1xjf2xjf优于，有（Non-dominated set） 在一组解P中，非劣解解集P是指所有那些不被P中任何个体占优的解组成的一组解。当P是整个搜索空间时，所得的非劣解集P被称为Pareto最优解集最优解集。 若目标函数中有冲突，则一般不存在唯一最优解，而存在若干个可行解。 Pareto最优解不一定对其他所有解占优，但是所有其他解都不能对它占优。ABCXYf1f2解点解点A, B, C是是Pareto最优点最优点A Pareto支配支配X C Pareto 支配支配Y五、基于进化算法的求解方法五、基于进化算法的求解方法 每轮迭代可以找到多个Pareto近似最优解 迄今为止还没有找到其他方法比EAs更能有效地解决MOP问题。 在许多复杂应用问题中搜索最优解还存在一定的困难。 同时考虑最大化主产物浓度同时考虑最大化主产物浓度CB和最小化生产和最小化生产时间时间tf