一种求解多目标无约束0-1二次规划问题的文化基因算法

周莹，刘云霞

（深圳信息职业技术学院计算机学院，广东 深圳 518172）

【信息技术理论研究】

一种求解多目标无约束0-1二次规划问题的文化基因算法

周莹，刘云霞

（深圳信息职业技术学院计算机学院，广东 深圳 518172）

针对多目标无约束0-1二次规划问题，提出一种文化基因算法。该算法采用基于分解的多目标演化算法框架，能够获得分布均匀的非占优解；同时，采用一种简单、有效的禁忌搜索，能够利用更多问题相关的信息，获得质量更优的非占优解。该算法在优化的过程中能够动态地平衡多样性与收敛性。实验结果证明该算法能够很好地求解多目标无约束0-1二次规划问题，并且性能优于目前求解该问题较先进的算法。

多目标无约束0-1二次规划问题；文化基因算法；基于分解的多目标演化算法；禁忌搜索算法

mUBQP具有广阔的应用场景[1]。在实际生活中，大量难以解决的问题都可转化为mUBQP。此外，许多图论问题也可转化为mUBQP，如双目标着色问题[1]。mUBQP是一种多目标优化问题，该类问题通常不存在一个能使多个目标同时达到最优的解，而是存在一组可供选择的折中解。因此，需设计多目标优化算法对其进行求解。

mUBQP是一种新的多目标优化问题，据我们所知，目前对mUBQP的研究成果仍然较少。2013年，文献[1]首先提出一组mUBQP的测试数据集。该测试数据集按照问题规模、密度、目标个数以及目标之间的相关性分为50个算例。其次，作者借鉴成功求解单目标UBQP的算法，提出第一个求解mUBQP的算法：混合型元启发式算法（HM）。……