面向组合优化问题的启发式算法推导研究

算法推导是从问题的形式规约出发，通过应用一系列变换规则来得到求解问题的算法程序，但目前的研究主要集中在确定性算法的形式化推导上。本课题将重点研究禁忌搜索、遗传算法、粒子群优化等智能启发式算法的自动推导与程序生成，通过分析典型组合优化问题的结构特征，提出问题空间和搜索空间的统一描述方法，在此基础上建立主要启发式算法的统一框架，采用代数结构模型来刻画算法各要素及其相互关系，特别是使用抽象算子来刻画关键的求解策略，从而针对具体问题应用算法精化和数据类型精化来推导出求解问题的高效算法程序，从根本上提高算法开发的质量和效率。开发一个集算法推导、实验与比较于一体的原型系统，帮助用户为指定问题快速生成和选取最为有效的算法程序。本项目研究能够有效提高智能算法程序设计的自动化水平、推动智能软件构造方法的探索与创新。

本课题对组合优化问题的形式规约、主要启发式算法的抽象框架，以及针对特定组合优化问题的启发式算法推导这三个方面开展了深入研究，建立了涵盖大多数启发式算法的框架模型，开发了面向组合优化问题的启发式算法推导系统，用户可通过指定问题规约和选择算法，生成包括遗传算法、进化规划、禁忌搜索、粒子群优化、差分进化、和声搜索等14种典型的启发式问题求解算法。在此基础上，进一步探索了混合启发式算法和超启发算法的框架模型和推导方法。通过对现有算法框架模型的分析研究，创造性地提出了两种新的启发式算法——生态地理学优化算法和水波优化算法。所开发的启发式算法推导系统用于国家应急专业力量指挥调度平台中的大量调度规划类问题的算法生成，得到的算法成功应用于2012玉树地震、2013雅安地震和定西地震等灾难救援调度行动，社会和经济效益显著。完成了预定的各项研究计划，在算法理论和应用两方面均取得了国际领先水平的研究成果，在IEEE Transactions on Evolutionary Computation, IEEE Transactions on Fuzzy Systems, IEEE Transactions on Intelligent Systems, Applied Soft Computing, Computers & Operations Research, IEEE Congress on Evolutionary Computation、软件学报等国内外知名期刊和会议上发表论文30篇，其中SCI收录22篇；出版论著《算法设计》一部；获国际运筹学领域面向发展中国家的最高荣誉——国际运筹学进展奖二等奖，获军队科技进步二等奖和三等奖各一项。