改进的极值优化算法及其在组合优化问题中的应用研究

摘要

组合优化作为优化领域的一个重要分支，在计算机科学、人工智能、交通运输、生产调度、网络通信、统计物理、生物信息学等诸多领域都有着广泛的应用。近年来，借鉴统计物理的理论和方法，为组合优化理论和算法的研究注入了新的活力。极值优化就正是一种受统计物理中自组织临界理论启发而提出的新兴优化方法，在部分经典benchmark和工程问题中都有着较为成功的应用。但是，相比模拟退火算法、遗传算法等成熟算法而言，有关极值优化的研究才刚刚起步，还存在若干问题有待解决。比如，求解旅行商问题、SK自旋玻璃问题和蛋白质折叠问题等强连接问题的效果并不理想；算法的演化概率分布还有待深入研究；以往绝大多数算法都忽略了问题本身的结构特征，如骨架信息等。
　　 本文从极值优化算法的演化概率分布、初始解等方面入手，结合组合优化问题本身的特征，对极值优化的算法改进及其在旅行商问题、最大满足性问题、SK自旋玻璃问题和HP蛋白质折叠问题等几类典型NP-hard组合优化问题中的应用进行了研究。具体地讲，本文的研究工作包括如下几个方面：
　　 (1)针对以往极值优化算法都采用幂律分布作为演化概率分布的情况，提出了基于拓展演化概率分布的改进极值优化算法(MEO)；并受TSP最优路径第k邻点分布统计性质的启发，提出了带有启发式初始解的改进EO算法(NNMEO)。首次通过对随机TSP和多个难求解的经典实例的仿真研究发现：在极值优化算法中，除了以往所常用的幂律分布外，诸如指数分布和混合分布也可能是有效的甚至是更佳的演化概率分布，这也在很大程度可以消除前人有关μ-EO算法不如τ-EO算法有效的误会；另外，在演化概率分布相同的情况下，极值优化算法从带有启发式信患的初始解出发通常比从完全随机的初始解出发更为有效。
　　 (2)针对以往几乎所有EO算法都采取静态演化策略的情况，提出了一种基于动态演化策略的“多级极值优化算法(MSEO)”。MSEO将整个优化过程分解为多个优化阶段，在每个优化阶段中将上一阶段所得到的最好解作为当前阶段的初始解，并采用不同的演化概率参数值进行再优化。对TSPLIB95中多个旅行商问题实例的仿真研究表明：相比“静态”极值优化算法，MSEO算法具有更好的优化性能。
　　 (3)受MEO和BE-EO算法基本思想的启发，提出了一类基于Bose-Einstein分布初始解和拓展演化概率分布的改进极值优化方法，简称EOSAT。在EOSAT框架下，提出了两种新颖的改进算法即BE-EEO和BE-HEO算法。对相变附近的最大满足性问题(Max-SAT)实例的仿真研究表明：相比文献中BE-EO等优化算法，本文提出的改进算法更为有效。
　　 (4)在EOSAT的基础上，将组合优化问题的骨架信息嵌入到搜索过程中，从而提出了一类基于骨架信息导向的极值优化算法(BGEO)。对大量Max-SAT问题测试基准的仿真结果表明：相比EOSAT和文献中其它经典的优化算法，BGEO算法具有更良好的优化性能。这为组合优化算法的设计提供了一种新颖的且更为有效的思路和方法。
　　 (5)在以上研究工作的基础上，将MEO算法的基本思想扩展应用到基于HP模型的蛋白质折叠问题中，并将MEO和BGEO算法的基本思想拓展应用到SK自旋玻璃的基态求解问题中。通过大量的仿真实验进一步表明了改进算法在求解强连接问题中的有效性。