优化原理与方法12.ppt

第 12 讲 §6 离散变量优化与遗传算法 §6.1 概述 Di为第i个设计变量xi可取的离散值集合。 设计变量也可以一部分是连续变量，另一部分是离散变量。 离散变量优化也称为组合优化，其算法为非多项式算法，属NP类问题。 §6 离散变量优化与遗传算法 组合方法: 隐枚举法,分枝定界法, 动态规划法 有哪些信誉好的足球投注网站方法: 整数梯度法等 变换方法：0-1变量技术，拟离散法 模拟方法: 模拟退火方法, 遗传算法, 神经元网络 求解方法概述 §6 离散变量优化与遗传算法 算法策略 松弛 ：暂时去除变量的离散约束，形成松弛问题 分枝：若松弛问题的解不满足规定的离散值要求，增加两个约束以构造两个分枝问题 定界：所有分枝的松弛解之最小值为原问题解的下界，它随着迭代的进行逐渐增加；已获得的可行解的最小值构成原问题解的上界，它随着迭代的进行逐渐减小 剪枝策略：①分枝无解；②分枝松弛解大于“上界” 定解，某分枝所获的解满足离散值条件且等于“下界” §6.2 分枝定界法 0 1 2 0 1 2 3 4 0 1 2 3 4 5 6 §6 离散变量优化与遗传算法 （一）仿生学方法概述 §6.4 仿生算法 §6 离散变量优化与遗传算法 模拟退火算法 前一迭代点为xl，当前获得的新点为x，按接受概率exp(-△f/Tj) 接受该点作为下一迭代点。其中 △f = f(x)-f(xl)，Tj 为退火温度。 §6.4 遗传算法 §6 离散变量优化与遗传算法 神经元网络 §6.4 遗传算法 x1 wi1 x2 wi2 θ1 yi s1 μ f(μ) μ f(μ) 神经元模型 §6 离散变量优化与遗传算法 神经元网络 §6.4 遗传算法 神经元网络 输出层 隐含层 输入层 黑箱 反馈 §6 离散变量优化与遗传算法 （二）遗传算法GA的基本方法 五要素：参数编码，初始群设定，评估函数设计，遗传操作，算法控制参数的选择。 参数编码：最简单的是用二值编码表示一维染色体。也有浮点编码等 种群规模：n=2L/2,L为编码长度。 代沟G：nG参与遗传操作，其余名额择优直接保存到下代中。 G=1时，为非重叠群体。 初始种群：随机生成+适当优选。 适应度函数：非负，方案优则适应度高，由目标和约束函数变换而得。 对适应度进行定标，避免优秀个体竞争力过强或竞争力太均化。 §6.4 遗传算法 §6 离散变量优化与遗传算法 （二）遗传算法GA的基本方法 遗传操作：选择、交叉、变异。 选择：适应度比例法（赌轮选择 或 蒙特卡罗选择）； 最佳个体保留法（最佳个体直接复制保留至下一代）； 期望值法（被选中参加遗传操作的，其适应度值减去期望值的一半后，参与保留至下代的竞争；未被选中参加遗传操作的，其适应度值减去期望值后，参与保留至下代的竞争） 交叉：依交叉概率进行交叉操作 一点交叉： 一致交叉： 二点交叉： 变异：随机确定基因座，以变异概率对其变异取反。 §6.4 遗传算法 浮点编码染色体的交叉 线性交叉 交叉公式 子个体＝父个体1＋F×(父个体2-父个体1) F为[0,1]间的均匀分布随机数 变量1 变量2 浮点编码染色体的交叉 中间交叉 交叉公式 子个体i＝父个体1i＋Fi×(父个体2i— 父个体1i) Fi为[0,1]间的均匀分布随机数 浮点编码染色体的变异 浮点编码变异 GA的框图 产生初始群体 是否满足终止准则 是 输出结果并结束 计算个体适应度值 选择运算 交叉运算 变异运算 否 产生的新一代群体规模是否已达到要求 被选保留至下一代 被选参与交叉 重复执行直至生成新一代群体为止 否 是