最大独立集问题的一类进化算法研究

摘要

最大独立集问题是图论中的经典组合优化问题。已被证明是NP完备的，具有较高的计算复杂性。本文从最大独立集问题的应用背景、界的估计、求解的难点以及现代优化算法的设计等方面综述了国内外专家学者对此问题的研究成果。 在此基础上，本文首先给出并证明了独立数的一个上界，然后通过分析最大独立集元素的构成特点，综合现代启发式算法，提出了一种新的具有多项式时间的算法——非邻域贪婪算法，并依此算法过程证明了独立数的一个下界。然后详细介绍了解决最大团问题的性能最好的遗传算法——EA/G算法，接着对此算法进行分析，指出它存在的不足，从而在此基础上提出自学习进化算法。此外，还利用DIMACS提供的benchmark基准图，对非邻域贪婪算法和自学习进化算法的性能进行了测试，实验结果表明，非邻域贪婪算法产生的极大独立集的性能较好，而自学习进化算法产生的最大独立集的性能较好。在适当地选取参数后，自学习进化算法能够求解得到绝大多数基准图的最优解，充分表明了该算法的有效性。

目录

文摘

英文文摘

声明

第一章绪论

1.1最大独立集问题概述

1.1.1最大独立集问题及其相关问题概述

1.1.2最大独立集问题的复杂性

1.1.3最大独立集问题的实际意义

1.2国内外研究现状及存在的问题

1.2.1国内研究现状

1.2.2国外研究现状

1.2.3存在的问题

1.3本文研究的主要内容和创新点

1.3.1本文研究的主要内容

1.3.2本文的主要创新点

第二章独立数的界与估计

2.1最大独立集的界

2.1.1下界

2.1.2上界

2.2在简单例图上的实验结果

第三章最大独立集问题及其启发式算法

3.1最大独立集问题的函数形式

3.2启发式算法

3.2.1贪婪算法

3.2.2禁忌搜索算法

3.2.3模拟退火法

3.2.4遗传算法

3.2.5人工神经网络算法

3.2.6并行算法

3.3本章小结

第四章最大独立集问题的改进启发式算法

4.1改进贪婪算法

4.1.1构造独立集

4.1.2与经典贪婪算法的比较

4.1.3改进独立集

4.2改进遗传算法

4.2.1 EA/G算法的思想和特征

4.2.2 EA/G算法的实现过程和算法描述

4.2.3 EA/G算法的不足和改进策略

4.2.4自学习进化算法求解最大独立集问题的算法描述

4.2.5实验结果

4.3本章小结

第五章总结与展望

5.1结论

5.2进一步的工作与展望

参考文献

致谢