论文部分内容阅读
【关键词】组合优化问题;模拟退火;分支界定
【中图分类号】O221.4 【文献标识码】A 【文章编号】1674-0688（2021）05-0066-03
0 引言
在优化领域中，根据变量性质的不同大体可以分为两类：一类是包含连续变量的优化问题;另一类是包含整数变量的优化问题（也可称之为组合优化问题）。组合优化问题的目标是从组合问题的可行解集中求出最优解，组合优化往往涉及排序、分类等问题，它是优化领域的一个重要分支。
在求解组合优化问题中，人们首先想到的是取整的方法，即互联组合优化问题变量必须为整数的约束条件，按照连续变量的优化问题对其进行求解，对于得到的结果按照某种方法取整。该方法简单，但是所得到的结果往往会违背优化问题的约束条件或者得到次优的结果。在取整的基础上，分支界定方法被提出，分支界定方法的本质也是按照连续变量的优化问题对其进行求解，不过在每次得到的结果不满足整数约束时，并不是进行简单的取整操作，而是通过缩小变量可行域的方法，逐步逼近问题的最优解。分支界定方法可以有效处理组合优化问题，但是其每次缩小可行域就要进行一次连续优化问题的求解[1]，因此计算量大。同时，由于采取连续变量的优化问题对其进行求解，對于所求解的数学问题有这严格的数学要求，例如函数必须连续且必须为凸，这样才可以保证所求的解为问题的全局最优解，如果是多极值问题，无法保证结果为问题的全局最优解，解的状态与问题的初始值密切相关，而初始值一般是随机给定，因此分支界定方法的使用受到较多的约束与限制。
另一种求解组合优化问题的方法为智能化方法。常见的智能化方法有粒子群算法[2]、遗传算法[3]、模拟退火算法[4]等。粒子群算法根据其迭代规则，如果变量为整数变量，需要在其迭代规则的基础上进行进一步讨论。遗传算法和模拟退火算法其初始变量随机生成，可以直接转化为相关的整数，不需要做额外的变化。也就是说，遗传算法和模拟退火算法都可以求解组合优化问题。遗传算法与模拟退火算法相对比，遗传算法需要选择、交叉、变异，而模拟退火算法仅需要生成新的解，采取Metropolis准则与原解进行比较并进行相应的跟新操作。模拟退火算法迭代过程简单，容易实现，因此本文采取模拟退火算法求解组合优化问题。
1 模拟退火算法的基本原理及编程实现
模拟退火算法通过观察自然科学中固体退火过程类推而来，最早的思想是由N. Metropolis等人于1953年提出[5]。我们首先给出模拟退火算法的具体迭代步骤，然后逐条对其进行相应的解释。
模拟退火算法的具体迭代步骤如下。
（1）设置模拟退火算法初始温度T，降温速率q，结束温度Tend，Metropolis准则链长L。
（2）随机生成组合优化问题的随机初始解S1。
（3）将S1带入组合优化问题的目标函数，求解目标函数值f 1。
（4）设置K=0。
（5）随机生成新的组合优化问题的解S2;将S2带入组合优化问题的目标函数，求解目标函数值f 2。
（6）Metropolis准则，比较f 1和f 2更新S1。
（7）更新k=k+1;假如k （8）更新温度T=T*q，假如T<Tend，则停止迭代输出结果;否则转步骤（4）。
1.1 随机生成组合优化问题的解的随机生成
组合优化问题的随机解生成代码如下所示。
S1=round（LB+（UB-LB）*rand（1，N）） （1）
公式（1）中，S1为随机生成组合优化问题的随机解，LB和UB分别代表与预先给定的变量的下限和上限向量，rand为Matlab函数，表示生成0～1的均匀分布随机数。round（）为Matlab函数，表示按照指定的小数位数进行四舍五入运算的结果，通过round操作可以保证组合优化问题的初始解为整数，而且是在给出的上下限范围之内。
1.2 模拟退火算法的Metropolis准则
Metropolis准则的制定在于以一定的概率跳出当前的最优解，即以一定的概率接收新的解，即使该新解目标函数评价低于已经存在的最优解，其目的是跳出局部最优解，使得算法具有全局搜索的能力，这也是模拟退火算法最为核心的概念[6]。
S1表示当前解，其对应的目标函数值为f （S1）;S2表示新生成的解，其对应的目标函数值为f （S2）。组合优化问题的解由S1变为S2的接受概率P：
P=1，f （S2）f （S1） （2）
根据公式（2）的描述可知，当f （S2）f （S1）时模拟退火算法不会立刻将新生成的解S2抛弃，其实进行相应的概率操作，首先利用均匀分布函数生成一个0～1的服从均匀分布概率的随机数，然后将这个随机数和e^（-（f （S2）-f （S1））/T）相比较，假如生成的随机数小于e^（-（f （S2）-f （S1））/T）则接受组合优化问题的解由S1变为S2，否则抛弃生成的新解S2。具体的伪代码如下所示。
随机生成新解S2;
S1评价指标=以S1为变量带入目标函数，返回的目标函数值;
S2评价指标=以S2为变量带入目标函数，返回的 目标函数值; 评价指标差=S2评价指标-S1评价指标
if评价指标差<0
S1=S2;
S1评价指标=S2评价指标;
else
if exp（-dC/温度）>0-1之间的均匀随机数
S1=S2;
S1评价指標=S2评价指标;
end
end
通过对Metropolis准则的分析我们发现，只有当f （S2）>f （S1）时，Metropolis准则才会以e^（-（f （S2）-f （S1））/T）的概率接受新解，此时-（f （S2）-f （S1））/T的值一定为负，因此e^（-（f （S2）-f （S1））/T）的值一定是0～1的开区间。同时我们发现e^（-（f （S2）-f （S1））/T）的大小还与当前时刻温度T有关，根据模拟退火算法的具体迭代步骤可知，随着迭代次数的增加，温度T是逐渐变小，我们假设f （S2）-f （S1）大小不变的情况下，随着温度T变小e^（-（f （S2）-f （S1））/T）的值也在不断变小趋近于0。因此，在迭代的初期，模拟退火算法以较高的概率跳出当前最优解，其目的是保证算法的全局收敛能力，在迭代的末期，模拟退火算法以较低的概率跳出当前最优解，其目的是在最优解附件搜索提高算法结果的精度。
2 仿真
2.1 仿真算例
在这一节中，我们采取的算例是来自2019年“电工杯数学建模大赛”A题，电源规划第二问。具体的算例描述如下：IEEE-RTS单阶段电源扩展规划（目标函数只考虑机组投资费用），IEEE-RTS系统由32台发电机组构成，总装机容量为3 405 MW，峰值负荷为2 850 MW。以2019年为基准年，假设2030年系统峰值负荷增长30%，规划2030年当年增装机组的类型和数量（见表1）。
根据问题的描述，我们建立如下的数学模型：
minF=x1*220+x2*90+x3*60+x4*50
s.t. 5≥x1≥0，x1≥为整数
11≥x2≥0，x2≥为整数 （3）
17≥x3≥0，x3≥为整数
21≥x4≥0，x4≥为整数
x1*250+x2*100+x3*65+x4*50+3 405≥4 446
其中，变量x1、x2、x3和x4分别代表表2中机组类型1、2、3和4的新建机组数量。当然根据工程建设的要求，我们需要以最小的工程造价为目标函数。
2.2 仿真分析
设置模拟退火算法初始温度T=150，降温速率q=0.9，结束温度Tend=1e-06，Metropolis准则链长L=1 000，运行模拟退火算法得到结果：[x1，x2，x3，x4]=[3 3 0 0]，目标函数为930，其目标函数变化曲线如图1所示。
为了验证模拟退火算法得到结果的准确性，我们采取分支界定算法对问题（3）进行求解，得到的变量的解和最优目标函数值为[x1，x2，x3，x4]=[3 1 3 0]，目标函数为930。很明显，模拟退火算法和分支界定算法得到的最优目标函数均为930，但是两者得到的解不相同。这说明了组合优化问题（3）有多个解。为了求解组合优化问题（3）的解，我们定义矩阵RESULT保存迭代过程中最优解及其函数值的信息，前4列保存解，第5列保存该解所对应的目标函数，矩阵RESULT的初始值=[迭代步骤（2）随机生成的初始解S1，S1对应的目标函数]，对模拟退火算法每次迭代的Metropolis准则进行改进，具体的伪代码如下所示。
随机生成新解S2;
S1评价指标=以S1为变量带入目标函数，返回的 目标函数值;
S2评价指标=以S2为变量带入目标函数，返回的 目标函数值;
评价指标差= S2评价指标- S1评价指标
if评价指标差<0
S1=S2;
S1评价指标=S2评价指标;
end
if评价指标差>0
if exp（-dC/温度）>0-1之间的均匀随机数
S1=S2;
S1评价指标=S2评价指标;
end
end
if评价指标差==0
flag=0;
if 矩阵RESULT第一行最后一列>S2评价指标
矩阵RESULT置为空矩阵;
RESULT=[S2，S2评价指标];
end
if矩阵RESULT第一行最后一列==S2评价指标
for i=1：矩阵RESULT的行数
if矩阵RESULT第i行前4列与S2相同
置变量flag为1，跳出当前循环;
end
end
if flag==0
RESULT=[RESULT;[S2，S2评价指标]];
end
end
end
现在根据我们改进过的模拟退火算法，再次执行程序，得到结果见表2。在表2中，我们得到了3组最优解，其最优目标函数值均为930。说明这3组解均为原问题（3）的最优解。
3 总结
本文利用模拟退火算法求解组合优化问题，仿真结果证明了模拟退火算法的有效性，通过进一步分析与比较仿真结果与分支界定算法仿真结果，发现仿真算例存在多个极值点，我们在原有基础上进一步改进模拟退火算法的Metropolis准则，同时输出组合优化调度问题的多个极值点。
参 考 文 献
[1]龚纯，王正林.精通MATLAB最优化计算[M].北京：电子工业出版社，2009.
[2]吴辰斌，李海明，刘栋，等.一种改进型粒子群优化算法在电力系统经济负荷分配中的应用[J].电力系统保护与控制，2016（10）：44-48.
[3]何大阔，王福利，毛志忠.基于改进遗传算法的电力系统经济负荷分配[J].控制与决策，2007（2）：230-232.
[4]王述红，朱宝强，王鹏宇.模拟退火聚类算法在结构面产状分组中的应用[J].东北大学学报（自然科学版），2020，41（9）：1328-1333.
[5]郑小虎，鲍劲松，马清文，等.基于模拟退火遗传算法的纺纱车间调度系统[J].纺织学报，2020，41（6）：36-41.
[6]陈科胜，鲜思东，郭鹏.求解旅行商问题的自适应升温模拟退火算法[J].控制理论与应用，2021，38（2）：245-
254.
【中图分类号】O221.4 【文献标识码】A 【文章编号】1674-0688（2021）05-0066-03
0 引言
在优化领域中，根据变量性质的不同大体可以分为两类：一类是包含连续变量的优化问题;另一类是包含整数变量的优化问题（也可称之为组合优化问题）。组合优化问题的目标是从组合问题的可行解集中求出最优解，组合优化往往涉及排序、分类等问题，它是优化领域的一个重要分支。
在求解组合优化问题中，人们首先想到的是取整的方法，即互联组合优化问题变量必须为整数的约束条件，按照连续变量的优化问题对其进行求解，对于得到的结果按照某种方法取整。该方法简单，但是所得到的结果往往会违背优化问题的约束条件或者得到次优的结果。在取整的基础上，分支界定方法被提出，分支界定方法的本质也是按照连续变量的优化问题对其进行求解，不过在每次得到的结果不满足整数约束时，并不是进行简单的取整操作，而是通过缩小变量可行域的方法，逐步逼近问题的最优解。分支界定方法可以有效处理组合优化问题，但是其每次缩小可行域就要进行一次连续优化问题的求解[1]，因此计算量大。同时，由于采取连续变量的优化问题对其进行求解，對于所求解的数学问题有这严格的数学要求，例如函数必须连续且必须为凸，这样才可以保证所求的解为问题的全局最优解，如果是多极值问题，无法保证结果为问题的全局最优解，解的状态与问题的初始值密切相关，而初始值一般是随机给定，因此分支界定方法的使用受到较多的约束与限制。
另一种求解组合优化问题的方法为智能化方法。常见的智能化方法有粒子群算法[2]、遗传算法[3]、模拟退火算法[4]等。粒子群算法根据其迭代规则，如果变量为整数变量，需要在其迭代规则的基础上进行进一步讨论。遗传算法和模拟退火算法其初始变量随机生成，可以直接转化为相关的整数，不需要做额外的变化。也就是说，遗传算法和模拟退火算法都可以求解组合优化问题。遗传算法与模拟退火算法相对比，遗传算法需要选择、交叉、变异，而模拟退火算法仅需要生成新的解，采取Metropolis准则与原解进行比较并进行相应的跟新操作。模拟退火算法迭代过程简单，容易实现，因此本文采取模拟退火算法求解组合优化问题。
1 模拟退火算法的基本原理及编程实现
模拟退火算法通过观察自然科学中固体退火过程类推而来，最早的思想是由N. Metropolis等人于1953年提出[5]。我们首先给出模拟退火算法的具体迭代步骤，然后逐条对其进行相应的解释。
模拟退火算法的具体迭代步骤如下。
（1）设置模拟退火算法初始温度T，降温速率q，结束温度Tend，Metropolis准则链长L。
（2）随机生成组合优化问题的随机初始解S1。
（3）将S1带入组合优化问题的目标函数，求解目标函数值f 1。
（4）设置K=0。
（5）随机生成新的组合优化问题的解S2;将S2带入组合优化问题的目标函数，求解目标函数值f 2。
（6）Metropolis准则，比较f 1和f 2更新S1。
（7）更新k=k+1;假如k
1.1 随机生成组合优化问题的解的随机生成
组合优化问题的随机解生成代码如下所示。
S1=round（LB+（UB-LB）*rand（1，N）） （1）
公式（1）中，S1为随机生成组合优化问题的随机解，LB和UB分别代表与预先给定的变量的下限和上限向量，rand为Matlab函数，表示生成0～1的均匀分布随机数。round（）为Matlab函数，表示按照指定的小数位数进行四舍五入运算的结果，通过round操作可以保证组合优化问题的初始解为整数，而且是在给出的上下限范围之内。
1.2 模拟退火算法的Metropolis准则
Metropolis准则的制定在于以一定的概率跳出当前的最优解，即以一定的概率接收新的解，即使该新解目标函数评价低于已经存在的最优解，其目的是跳出局部最优解，使得算法具有全局搜索的能力，这也是模拟退火算法最为核心的概念[6]。
S1表示当前解，其对应的目标函数值为f （S1）;S2表示新生成的解，其对应的目标函数值为f （S2）。组合优化问题的解由S1变为S2的接受概率P：
P=1，f （S2）
根据公式（2）的描述可知，当f （S2）
随机生成新解S2;
S1评价指标=以S1为变量带入目标函数，返回的目标函数值;
S2评价指标=以S2为变量带入目标函数，返回的 目标函数值; 评价指标差=S2评价指标-S1评价指标
if评价指标差<0
S1=S2;
S1评价指标=S2评价指标;
else
if exp（-dC/温度）>0-1之间的均匀随机数
S1=S2;
S1评价指標=S2评价指标;
end
end
通过对Metropolis准则的分析我们发现，只有当f （S2）>f （S1）时，Metropolis准则才会以e^（-（f （S2）-f （S1））/T）的概率接受新解，此时-（f （S2）-f （S1））/T的值一定为负，因此e^（-（f （S2）-f （S1））/T）的值一定是0～1的开区间。同时我们发现e^（-（f （S2）-f （S1））/T）的大小还与当前时刻温度T有关，根据模拟退火算法的具体迭代步骤可知，随着迭代次数的增加，温度T是逐渐变小，我们假设f （S2）-f （S1）大小不变的情况下，随着温度T变小e^（-（f （S2）-f （S1））/T）的值也在不断变小趋近于0。因此，在迭代的初期，模拟退火算法以较高的概率跳出当前最优解，其目的是保证算法的全局收敛能力，在迭代的末期，模拟退火算法以较低的概率跳出当前最优解，其目的是在最优解附件搜索提高算法结果的精度。
2 仿真
2.1 仿真算例
在这一节中，我们采取的算例是来自2019年“电工杯数学建模大赛”A题，电源规划第二问。具体的算例描述如下：IEEE-RTS单阶段电源扩展规划（目标函数只考虑机组投资费用），IEEE-RTS系统由32台发电机组构成，总装机容量为3 405 MW，峰值负荷为2 850 MW。以2019年为基准年，假设2030年系统峰值负荷增长30%，规划2030年当年增装机组的类型和数量（见表1）。
根据问题的描述，我们建立如下的数学模型：
minF=x1*220+x2*90+x3*60+x4*50
s.t. 5≥x1≥0，x1≥为整数
11≥x2≥0，x2≥为整数 （3）
17≥x3≥0，x3≥为整数
21≥x4≥0，x4≥为整数
x1*250+x2*100+x3*65+x4*50+3 405≥4 446
其中，变量x1、x2、x3和x4分别代表表2中机组类型1、2、3和4的新建机组数量。当然根据工程建设的要求，我们需要以最小的工程造价为目标函数。
2.2 仿真分析
设置模拟退火算法初始温度T=150，降温速率q=0.9，结束温度Tend=1e-06，Metropolis准则链长L=1 000，运行模拟退火算法得到结果：[x1，x2，x3，x4]=[3 3 0 0]，目标函数为930，其目标函数变化曲线如图1所示。
为了验证模拟退火算法得到结果的准确性，我们采取分支界定算法对问题（3）进行求解，得到的变量的解和最优目标函数值为[x1，x2，x3，x4]=[3 1 3 0]，目标函数为930。很明显，模拟退火算法和分支界定算法得到的最优目标函数均为930，但是两者得到的解不相同。这说明了组合优化问题（3）有多个解。为了求解组合优化问题（3）的解，我们定义矩阵RESULT保存迭代过程中最优解及其函数值的信息，前4列保存解，第5列保存该解所对应的目标函数，矩阵RESULT的初始值=[迭代步骤（2）随机生成的初始解S1，S1对应的目标函数]，对模拟退火算法每次迭代的Metropolis准则进行改进，具体的伪代码如下所示。
随机生成新解S2;
S1评价指标=以S1为变量带入目标函数，返回的 目标函数值;
S2评价指标=以S2为变量带入目标函数，返回的 目标函数值;
评价指标差= S2评价指标- S1评价指标
if评价指标差<0
S1=S2;
S1评价指标=S2评价指标;
end
if评价指标差>0
if exp（-dC/温度）>0-1之间的均匀随机数
S1=S2;
S1评价指标=S2评价指标;
end
end
if评价指标差==0
flag=0;
if 矩阵RESULT第一行最后一列>S2评价指标
矩阵RESULT置为空矩阵;
RESULT=[S2，S2评价指标];
end
if矩阵RESULT第一行最后一列==S2评价指标
for i=1：矩阵RESULT的行数
if矩阵RESULT第i行前4列与S2相同
置变量flag为1，跳出当前循环;
end
end
if flag==0
RESULT=[RESULT;[S2，S2评价指标]];
end
end
end
现在根据我们改进过的模拟退火算法，再次执行程序，得到结果见表2。在表2中，我们得到了3组最优解，其最优目标函数值均为930。说明这3组解均为原问题（3）的最优解。
3 总结
本文利用模拟退火算法求解组合优化问题，仿真结果证明了模拟退火算法的有效性，通过进一步分析与比较仿真结果与分支界定算法仿真结果，发现仿真算例存在多个极值点，我们在原有基础上进一步改进模拟退火算法的Metropolis准则，同时输出组合优化调度问题的多个极值点。
参 考 文 献
[1]龚纯，王正林.精通MATLAB最优化计算[M].北京：电子工业出版社，2009.
[2]吴辰斌，李海明，刘栋，等.一种改进型粒子群优化算法在电力系统经济负荷分配中的应用[J].电力系统保护与控制，2016（10）：44-48.
[3]何大阔，王福利，毛志忠.基于改进遗传算法的电力系统经济负荷分配[J].控制与决策，2007（2）：230-232.
[4]王述红，朱宝强，王鹏宇.模拟退火聚类算法在结构面产状分组中的应用[J].东北大学学报（自然科学版），2020，41（9）：1328-1333.
[5]郑小虎，鲍劲松，马清文，等.基于模拟退火遗传算法的纺纱车间调度系统[J].纺织学报，2020，41（6）：36-41.
[6]陈科胜，鲜思东，郭鹏.求解旅行商问题的自适应升温模拟退火算法[J].控制理论与应用，2021，38（2）：245-
254.