《智能计算》教学课件-第三章-遗传算法在优化中的应用.pptVIP

第3章 遗传算法在优化中的应用 武汉大学计算机学院 3.1 无约束优化 无约束优化是指在没有任何约束的前提下极大或极小化某个目标函数的问题。无约束优化问题可描述为： 或 这里S称为有哪些信誉好的足球投注网站空间， 称为目标函数。 3.1 无约束优化 定义3.1 对最小化问题，设 ，若存在 使得对任 且 时，有 则称 是 在S上的一个局部最优解，而称 为一个局部最优值。 定义3.2 对最小化问题，设 ，若对任 有 则称 是 在S上的一个全局最优解，而称 为一个全局最优值。 3.1 无约束优化 考虑下面的Ackley函数优化问题： 当n=2时,目标函数的三维图形如下图所示。 3.1 无约束优化 3.2 一个例子 1．个体的编码 采用实数向量编码，每一个个体是一实数对 . 2. 适应函数：该优化问题是一个极小化问题，可对目标函数作简单变换得到适应函数，譬如取 3. 选择策略：采用随机通用采样. 4. 杂交算子：采用整体算术杂交。 给定两个父体，产生一个随机数，经杂交后得到两个后代个体 3.2 一个例子 , , 产生一个随机数 ，经杂交后得到两个后代个体 5. 变异算子：采用非均匀变异。 6. 参数设置：种群规模 ，最大代数 ，杂交概率 ，变异概率 . 7. 初始化：随机产生初始种群。 8. 终止条件：算法运行所指定的最大代数后终止。 3.3 约束优化 约束优化问题可描述为： 其中 都是定义在 上的实函数，有哪些信誉好的足球投注网站空间为目标函数的定义域，通常为n维矩形： 。 3.3 约束优化 常用的约束处理技术。 1．拒绝法 拒绝法抛弃所有在演化过程中产生的不可行染色体。 2．修复法 修复法是通过一个修复程序对不可行个体进行修复，使之成为可行个体。该方法在求解一些组合优化问题时经常使用。 3.3 约束优化 对0-1背包问题，我们可以设计一个简单的修复程序。若 是一个不可行个体，即有 ，其修复过程如下： (1) 将 的物品按价值-重量比从大到小排序； (2) 按上述次序选择物品，直到背包不能再装为止。 修复后的个体可以只用作评估，也可以用来替代原个体进入种群。 3.3 约束优化 3.3 约束优化 3.3 约束优化 3.3 约束优化 (1) 静态惩罚函数 静态惩罚函数具有下列形式： 其中 是预先指定的常数，称为惩罚系数。d是一个常数，通常取d=1或2。 3.3 约束优化 选择适当的惩罚系数并不是一件容易的事。 若惩罚系数选择过大，则将会由于太注重解的可行性而较早地收敛到某个局部最优解；若这些惩罚系数选择过小，则有可能使得不可行解在种群中占统治地位，从而使算法花费过多的时间在非可行区域中有哪些信誉好的足球投注网站，而且有可能收敛到非可行域。 3.3 约束优化 一种较好的方法是对每个约束，根据该约束的违反程度来确定惩罚系数。该A.S.Homaifar等提出了一种基于这种思想构造惩罚函数的方法。其详细描述如下： 对每个约束，确定 个区间 以度量该约束的违反程度； 对每个约束及违反程度，建立一个惩罚系数 使得违反程度越高，惩罚系数越大； 3.3 约束优化 惩罚函数由下式给出： 这里 由 的偏离程度来决定。 若 ，则 。 该方法的优点是简单、直接、易于实现。但该方法的性能在很大程度上依赖于惩罚系数 的选取。对具有m个约束的问题，需要确定个 参数。即 个待确定区间的端点， 个惩罚系数。 3.3 约束优化 (2) 动态惩罚函数 静态惩罚函数中的惩罚系数 是固定不变 的。一种替代的方法是使