演化和蚁群算法的近似性能分析

大量的数值实验显示，演化和蚁群算法能够有效地求解众多的复杂优化问题。但对于NP-完全（难）问题，由于其难解性，人们也难以期待演化和蚁群算法在多项式时间内找到全部NP-完全（难）优化问题的精确解。本项目研究演化和蚁群算法关于NP-完全（难）优化问题的近似性能。针对命题公式的最大可满足问题、最大团问题、旅行商问题等组合优化问题，分析两种算法在最坏情况和平均情况下，在多项式时间或指数时间内达到的近似比；同时在输入问题存在随机扰动的假设下，分析两算法的光滑近似性能；建立演化算法和蚁群算法近似性能分析框架和理论基础。演化和蚁群算法近似性能的分析更接近算法设计与应用的真实情景，其研究有助于理解算法的工作原理和指导算法的应用。

演化算法和蚁群算法是求解复杂优化问题的随机启发式算法的出色代表。当前演化和蚁群算法理论研究远远落后于算法的数值实验和真实应用。理论研究可以使人们更好地理解算法的工作原理，为算法的设计、算法的参数选取、算法的应用等指明改进的方向。本项目分析演化和蚁群算法关于NP-完全（难）优化问题的近似性能，其分析接近算法设计与应用的真实情景，其研究具有现实意义。.本项目在2012年1月至2015年12年期间，按项目计划执行预定的研究任务,在演化算法与蚁群算法的近似性能理论分析以及演化算法设计取得若干进展和成果。分析了演化算法和蚁群算法关于一些经典NP完全（难）组合优化问题的近似性能,如最大割问题、多机调度问题、0-1背包问题、旅行商问题、Steiner树问题、最小标签生成树问题等，研究结果表明演化算法和蚁群算法关于这些NP完全（难）组合优化问题可在平均多项式时间内获得一些特定的近似比；讨论了算法参数对于近似性能的影响；将演化算法和蚁群算法与其他局部搜索算法从理论分析上进行比较。应用蚁群算法求解矩阵乘法问题、可满足问题等；以及使用蜂群算法求解高维多目标优化问题等。完成学术论文16篇，其中14篇已发表，2篇已录用待发表。完成论文包括11篇SCI期刊论文，主要成果发表在“Algorithmica”、“IEEE Transactions on Evolutionary Computation”、“ IEEE Transactions on Cybernetics”、“ European Journal of Operational Research”、“ Journal of Global Optimization”、“ Science China”等相关研究领域重要国际刊物。