演化算法时间复杂性及相关问题

项目名称： 演化算法时间复杂性及相关问题

项目编号： No.60975050

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 丁立新

作者单位： 武汉大学

项目金额： 33万元

中文摘要： 演化算法时间复杂性及其相关问题是演化计算基础理论研究的前沿与难点。本项目拟运用随机稳定性理论、动力系统理论、谱分析理论等技术手段，研究演化算法时间复杂性与动力学行为分析的某些待解问题。具体研究内容为：基于一般优化模型，研究可用于严格分析群体演化算法时间复杂性的基本手段与方法，定量刻画问题类型、群体规模、遗传算子以及与问题相关联的启发式知识等关键因素对演化算法时间复杂度的影响，研究演化算法在多项式时间内求解典型NP-难度问题所得近似解的质量；进一步地，研究与算法时间复杂性相关联的最优转移算子存在的谱条件，探索有限群体模型与无限群体模型的谱关系，推广Karlin定理，使之适应多遗传算子的演化算法动力学行为描述。项目的意义在于：建立演化算法时间复杂度估计的新手段，解决演化算法时间复杂性与动力学行为分析中的某些公开理论问题；为相关理论研究者提供参考，为相关从业者在实践中选择和设计演化算法提供借鉴。

中文关键词： 演化算法；时间复杂性；动力学行为；算子谱；Karlin定理

英文摘要：

英文关键词： Evolutionary Algorithms；Time Complexity；Dynamical Behaviors；Operator Spectrum；Karlin Theorem