代表性成果之二

并行演化优化理论、方法及应用

（2002~2006） 

成果类别：基础研究  

主要完成者：（带*号者为固定人员）

*康立山、*李元香、*吴志健、*丁立新、*邹秀芬、*王玲玲、

曹宏庆、康卓、李艳、何军、刘勇、曾三友、涂航、董文永

摘   要

上世纪80年代中后期以来，康立山教授领导并行计算与智能计算研究室,一直致力于并行算法和演化算法设计与分析的理论及其应用研究。近20年来的潜心耕耘，取得了一系列的成果，其中多项成果分别获得国家自然科学奖、教育部科技进步奖和湖北省自然科学奖，赢得了国内同行的认可，软件工程国家重点实验室也被认为是并行计算和演化计算有影响的研究基地之一。

90年代以来，演化计算作为智能计算的一个重要的领域、一类重要的优化方法而备受重视。在过去5年中，从提高演化算法的求解效率和精度出发，特别是与并行计算理论和技术有机结合，在并行演化计算的理论及其应用等方面进行了系统深入研究，提出了一些新理论、新方法，并研制了相应的软件系统。

（1）建立了并行演化优化算法的理论体系。以复杂函数优化问题和组合优化中的NP难题为主要对象，系统深入地研究并行演化算法设计与分析的理论、应用与实现技术，提出了一系列实用、高效的演化优化算法，包括单、多目标函数优化、组合优化算法及动态优化算法。

（2）建立了并行演化建模算法的理论体系，作为演化计算及优化算法的典型应用。以复杂系统的分析、建模和预测为主要对象，提出了演化自适应建模的理论与方法，建立了若干典型的复杂系统模型，包括静态模型和动态模型，如分类系统、微分方程和差分方程模型等。

（3）演化计算的理论分析，给出了演化算法群体动力学特性的分析模型，证明了演化建模中自动程序设计复杂性定理，给出了有限搜索空间中演化算法时间复杂性分析的技术框架，并研究了典型计算模型的时间复杂性问题，给出了演化算法渐近收敛行为的统一刻画。

（4）并行算法及其实现，给出了函数优化、组合优化与演化建模的高效并行算法，在YH系列超级计算机上实现了若干典型问题的并行求解，如具有挑战性的百万维Bump问题。

（5）演化软件系统，针对典型应用，建立了演化优化软件演示系统和演化建模软件演示系统，演化优化系统可用于求解复杂的函数优化和组合优化问题，演化建模系统从复杂系统的数据中自动发现规律，建立数学模型，预测系统的行为，也可用于知识的自动发现和数据挖掘。

（6）演化硬件技术，演化硬件是演化算法和演化建模理论的拓展和应用，给出了演化硬件设计的模型和框架，提出了基于演化硬件的SoC软硬件协同设计的方法和自动设计实现技术，提出基于演化硬件的自主计算模型以及自适应计算系统。

（7）演化硬件设计平台，研制了一个演化硬件设计平台原型WU-EHW，打破自顶向下的设计方法，平台自动完成对电路的设计和性能优化，可用于数字电路和模拟电路的自动演化设计。该平台的进一步发展是自主计算模型及自适应计算系统。

该项成果就其理论的系统性与广泛性，算法的系统性与鲁棒性以及建模过程的自动化程度等总体上处于同类研究的国际先进水平，对完善智能计算的基础理论与推动智能计算科学的向前发展具有重要理论意义。