中文摘要：

NP完全问题是一类难解问题，具有重要的工程背景和实际意义，目前研究表明其计算复杂度与相变有关，在相变点处的问题计算复杂度最大。极值动力学优化(Extremal Optimization, EO)算法是一种新颖的局部搜索启发式算法，其理论基础是自组织临界性理论，非常适合于求解带相变点的NP完全问题。目前学界对EO算法的研究远未成熟，尚存在大量亟需解决的问题。针对这一研究现状，本项目拟对以下关键问题展开研究对EO算法的收敛性进行分析，奠定E0算法的理论基础；从全局适应度函数和局部适应度函数的内在关联入手，研究EO算法的局部适应度定义准则；研究骨架导向的EO算法，提高EO算法的搜索性能；对多目标场合下的EO算法展开研究，提出一系列改进的多目标EO算法。本项目的研究内容将为EO算法的进一步发展奠定坚实的基础，也将促进EO算法广泛用于解决实际工程应用问题，具有重要的理论意义和实用价值。

结论摘要：

NP完全问题是一类难解问题，具有重要的工程背景和实际意义，目前研究表明其计算复杂度与相变有关，在相变点处的问题计算复杂度最大。极值动力学优化(Extremal Optimization, EO)算法是一种新颖的局部搜索启发式算法，其理论基础是自组织临界性理论，非常适合于求解带相变点的NP完全问题。目前学界对EO算法的研究远未成熟，尚存在大量亟需解决的问题。针对这一研究现状，本项目对以下关键问题展开了研究对EO算法的收敛性进行分析，奠定E0算法的理论基础；研究骨架导向的EO算法，提高EO算法的搜索性能；研究EO算法与其它智能优化算法（如混合蛙跳算法、人工蜂群算法、量子进化等）的融合；研究一系列改进的多目标EO算法（包括 tau-MOEO算法、基于混合粒子群—极值动力学优化的多目标优化算法MOPSOEO），并应用这些算法解决了多目标数值优化问题和多目标机械组件优化设计问题。