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

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

演化算法计算复杂性是演化计算理论研究领域的重要课题，也是目前演化计算基础理论研究的薄弱环节。通过三年的研究，本项目完成的研究工作和取得的研究成果如下：（1）运用非时齐Markov过程理论，研究了自适应演化算法模型的渐近行为和时变特征，建立了可用于分析一般演化算法时间复杂度的技术手段和理论框架；（2）基于建立的理论框架，综合运用适应值分层技术和截尾不等式，获得了一些典型计算问题的时间复杂度估计；（3）研究了对应于演化算法的随机树的产生过程刻画，探讨了演化算法对应的随机树上的概率结构与概率性质，为引入随机树方法作为演化算法时间复杂度估计的新手段奠定了理论基础；（4）运用Markov链理论和动力系统理论，研究了遗传算子、选择策略、群体规模对EA时间复杂度的影响，给出了演化算法对应的转移算子的谱与算法时间复杂度的理论关系；（5）研究了基于演化算法的近似解质量与算法时间复杂度的关系，为演化算法有效求解复杂计算问题提供了一定理论支持；（6）研究了elitist演化算法的收敛速度与平均首达时间、量子演化算法的收敛性、群体规模可变的自适应演化算法的时间复杂性问题，得到了这些经典演化算法模型的极限行为刻画；（7）研究了演化算法的难易问题的划分与度量准则，基于演化算法所对应的转移算子的谱特征研究演化算法的动力学行为，基于推广的Karlin定理刻画了多遗传算子演化算法的动力学行为。项目的成果已经发表或录用在国内外核心学术刊物和相关学术会议上，已发表学术论文37篇。本项目的研究工作建立了演化算法时间复杂性分析的基础框架，解决了演化算法时间复杂性分析的一些公开理论问题。