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

项目名称： 演化和蚁群算法的近似性能分析

项目编号： No.61170081

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 计算机科学学科

项目作者： 周育人

作者单位： 华南理工大学

项目金额： 56万元

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

中文关键词： 演化算法；蚁群算法；近似性能；优化；

英文摘要：

英文关键词： Evolutionary algorithms；ant colony algorithms；approximation performance；optimization；