优化原理与方法12

1、6.1 概述概述 Di为第为第i个设计变量个设计变量xi可取的离散值集合。可取的离散值集合。 设计变量也可以一部分是连续变量，另一部分是设计变量也可以一部分是连续变量，另一部分是离散变量。离散变量。 离散变量优化也称为组合优化，其算法为非多项离散变量优化也称为组合优化，其算法为非多项式算法，属式算法，属NP类问题。类问题。niDxmjxglrxhfiijr,.,2 , 1,.,2 , 10)(,.,2 , 10)(s.t.)(.minx6 6 离散变量优化与遗传算法离散变量优化与遗传算法组合方法组合方法: 隐枚举法隐枚举法,分枝定界法分枝定界法, 动态规划法动态规划法搜索方法搜索方法: 整数梯

2、度法等整数梯度法等变换方法：变换方法：0-1变量技术，拟离散法变量技术，拟离散法模拟方法模拟方法: 模拟退火方法模拟退火方法, 遗传算法遗传算法, 神经元网络神经元网络求解方法概述求解方法概述6 6 离散变量优化与遗传算法离散变量优化与遗传算法算法策略算法策略松弛松弛 ：暂时去除变量的离散约束，形成松弛问题：暂时去除变量的离散约束，形成松弛问题分枝：若松弛问题的解不满足规定的离散值要求，增加分枝：若松弛问题的解不满足规定的离散值要求，增加两个约束以构造两个分枝问题两个约束以构造两个分枝问题定界：所有分枝的松弛解之最小值为原问题解的下界，定界：所有分枝的松弛解之最小值为原问题解的下界，它随着迭代

3、的进行逐渐增加；已获得的可行解的最小值它随着迭代的进行逐渐增加；已获得的可行解的最小值构成原问题解的上界，它随着迭代的进行逐渐减小构成原问题解的上界，它随着迭代的进行逐渐减小剪枝策略：分枝无解；分枝松弛解大于剪枝策略：分枝无解；分枝松弛解大于“上界上界”1.定解，某分枝所获的解满足离散值条件且等于定解，某分枝所获的解满足离散值条件且等于“下界下界”6.2 分枝定界法分枝定界法3 , 2 , 1 053832s.t.437)(.min321321321ixxxxxxxxxxxfi且为整数01232x42x5132114)(05/195/2xfxxx)(15)(xff x01232x42x17)(

4、15)(xff x2/29)(2/132/1321xfxxx3411x01x17)(230321xfxxx18)(3/52)(3/130321xxffxxx15)(xf( )17fx3 , 2 , 1 053832s.t.437)(.min321321321ixxxxxxxxxxxfi且为整数01232x42x17)(15)(xff x3411x01x)(15)(250*321xxffxxx17)(xf18)(xf501x611x3/43)(3/143/1321xfxxx6 6 离散变量优化与遗传算法离散变量优化与遗传算法（一）仿生学方法概述（一）仿生学方法概述6.4 仿生算法仿生算法：神经元

5、网络算法模仿自然界结构的算法模拟退火算法演化算法进化算法遗传算法模仿自然界过程的算法6 6 离散变量优化与遗传算法离散变量优化与遗传算法模拟退火算法模拟退火算法 前一迭代点为前一迭代点为xl，当前获得的新点为，当前获得的新点为x，按接，按接受概率受概率exp(- -f/Tj) 接受该点作为下一迭代点。接受该点作为下一迭代点。其中其中 f = f(x)-f(xl)，Tj 为退火温度。为退火温度。6.4 遗传算法遗传算法6 6 离散变量优化与遗传算法离散变量优化与遗传算法神经元网络神经元网络 6.4 遗传算法遗传算法x1wi1x2wi21yi)(1iinjiijijifysxws1f()f()神经

6、元模型神经元模型ef11)(6 6 离散变量优化与遗传算法离散变量优化与遗传算法神经元网络神经元网络 6.4 遗传算法遗传算法神经元网络神经元网络输出层隐含层输入层黑箱黑箱反馈反馈6 6 离散变量优化与遗传算法离散变量优化与遗传算法（二）遗传算法（二）遗传算法GA的基本方法的基本方法 五要素：参数编码，初始群设定，评估函数设计，遗传操作，算五要素：参数编码，初始群设定，评估函数设计，遗传操作，算法控制参数的选择。法控制参数的选择。参数编码：参数编码：最简单的是用二值编码表示一维染色体。也有浮点编码等最简单的是用二值编码表示一维染色体。也有浮点编码等种群规模：种群规模：n=2L/2,L为编码长度

7、。为编码长度。代沟代沟G：nG参与遗传操作，其余名额择优直接保存到下代中。参与遗传操作，其余名额择优直接保存到下代中。 G=1时，为非重叠群体。时，为非重叠群体。 初始种群：初始种群：随机生成随机生成+适当优选。适当优选。适应度函数：适应度函数：非负，方案优则适应度高，由目标和约束函数变换而得。非负，方案优则适应度高，由目标和约束函数变换而得。 对适应度进行定标，避免优秀个体竞争力过强或竞争力太均化。对适应度进行定标，避免优秀个体竞争力过强或竞争力太均化。6.4 遗传算法遗传算法6 6 离散变量优化与遗传算法离散变量优化与遗传算法（二）遗传算法（二）遗传算法GA的基本方法的基本方法遗传操作：遗

8、传操作：选择、交叉、变异。选择、交叉、变异。选择：选择：适应度比例法（赌轮选择适应度比例法（赌轮选择 或或 蒙特卡罗选择）；蒙特卡罗选择）； 最佳个体保留法（最佳个体直接复制保留至下一代）；最佳个体保留法（最佳个体直接复制保留至下一代）； 期望值法（被选中参加遗传操作的，其适应度值减去期望值的一期望值法（被选中参加遗传操作的，其适应度值减去期望值的一半后，参与保留至下代的竞争；未被选中参加遗传操作的，其适应半后，参与保留至下代的竞争；未被选中参加遗传操作的，其适应度值减去期望值后，参与保留至下代的竞争）度值减去期望值后，参与保留至下代的竞争）交叉：依交叉概率进行交叉操作交叉：依交叉概率进行交叉

9、操作一点交叉：一点交叉： 一致交叉：一致交叉：二点交叉：二点交叉：变异：变异：随机确定基因座，以变异概率对其变异取反。随机确定基因座，以变异概率对其变异取反。6.4 遗传算法遗传算法 00 | 110 | 00 11 | 010 |1000 | 010 | 00 11 | 110 | 10 BABA新个体新个体个体个体 111 |0011 000 | 0110000 | 1100 111 | 0110 BABA新个体新个体个体个体 101101 011110010101 111100 001111 BABA新个体新个体屏蔽字个体个体浮点编码染色体的交叉线性交叉交叉公式子个体父个体1F(父个体2-父个体1)F为0,1间的均匀分布随机数变量1变量2浮点编码染色体的交叉中间交叉交叉公式子