高嘉 任亚明

【关键词】组合优化问题;模拟退火;分支界定

【中图分类号】O221.4 【文献标识码】A 【文章编号】1674-0688（2021）05-0066-03

0 引言

在优化领域中，根据变量性质的不同大体可以分为两类：一类是包含连续变量的优化问题;另一类是包含整数变量的优化问题（也可称之为组合优化问题）。组合优化问题的目标是从组合问题的可行解集中求出最优解，组合优化往往涉及排序、分类等问题，它是优化领域的一个重要分支。

在求解组合优化问题中，人们首先想到的是取整的方法，即互联组合优化问题变量必须为整数的约束条件，按照连续变量的优化问题对其进行求解，对于得到的结果按照某种方法取整。该方法简单，但是所得到的结果往往会违背优化问题的约束条件或者得到次优的结果。在取整的基础上，分支界定方法被提出，分支界定方法的本质也是按照连续变量的优化问题对其进行求解，不过在每次得到的结果不满足整数约束时，并不是进行简单的取整操作，而是通过缩小变量可行域的方法，逐步逼近问题的最优解。分支界定方法可以有效处理组合优化问题，但是其每次缩小可行域就要进行一次连续优化问题的求解[1]，因此计算量大。同时，由于采取连续变量的优化问题对其进行求解，對于所求解的数学问题有这严格的数学要求，例如函数必须连续且必须为凸，这样才可以保证所求的解为问题的全局最优解，如果是多极值问题，无法保证结果为问题的全局最优解，解的状态与问题的初始值密切相关，而初始值一般是随机给定，因此分支界定方法的使用受到较多的约束与限制。……