ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (8): 1746-1757.doi: 10.7544/issn1000-1239.2019.20190198

所属专题: 2019人工智能前沿进展专题

• 人工智能 • 上一篇    下一篇

实值优化问题的非对称负相关搜索算法

于润龙1,赵洪科2,汪中1,叶雨扬1,张培宁1,刘淇1,陈恩红1   

  1. 1(大数据分析与应用安徽省重点实验室(中国科学技术大学) 合肥 230027);2(天津大学管理与经济学部 天津 300072) (yrunl@mail.ustc.edu.cn)
  • 出版日期: 2019-08-01
  • 基金资助: 
    国家自然科学基金项目(61672483,U1605251);中国科学院青年创新促进会优秀会员专项(2014299);安徽省科技创新战略与软科学研究专项(201806a02020055)

Negatively Correlated Search with Asymmetry for Real-Parameter Optimization Problems

Yu Runlong1, Zhao Hongke2, Wang Zhong1, Ye Yuyang1, Zhang Peining1, Liu Qi1, Chen Enhong1   

  1. 1(Anhui Province Key Laboratory of Big Data Analysis and Application (University of Science and Technology of China), Hefei 230027);2(College of Management and Economics, Tianjin University, Tianjin 300072)
  • Online: 2019-08-01

摘要: 现实世界中的许多应用与实值优化问题紧密相关.为了求解复杂的实值优化问题,一些研究工作提出不同的元启发式假设并设计相应的搜索策略.在搜索解空间过程中,如何平衡探索解空间新区域(多样化)与实现优质解利用(集约化)之间的关系,是提高元启发式搜索算法性能的关键因素之一.特别地,负相关搜索(negatively correlated search, NCS)通过在搜索进程中引入负相关的搜索趋势,促进了解的多样性,有效改进了并行爬山算法的搜索性能.负相关搜索将每一个搜索进程的搜索行为建模为概率分布,在此基础上,根据搜索进程的搜索范围的相对大小,将搜索行为进一步划分为全局搜索行为和局部搜索行为.然后提出一种新的元启发式搜索算法,即非对称负相关搜索(negatively correlated search with asymmetry, NSA),它假设具有全局搜索行为的搜索进程应尽可能远离具有局部搜索行为的搜索进程.得益于搜索进程之间非对称的负相关的搜索趋势,提出的算法相比负相关搜索拥有更优的搜索效率.实验结果表明:相比成熟的搜索方法,非对称负相关搜索在20个多模态实值优化问题上取得了最佳的整体性能.

关键词: 复杂实值优化问题, 探索与利用, 并行爬山算法, 负相关搜索, 搜索行为

Abstract: As many real-world applications are closely related to complex real-parameter optimization problems, some metaheuristic assumptions are employed to help design search strategies and have been shown to be powerful tools. The balance between exploration (diversification) of new areas of the search space and exploitation (intensification) of good solutions accomplished by this kind of algorithms is one of the key factors for their high performance with respect to other metaheuristics. In particular, negatively correlated search (NCS) improves the search performance of parallel hill climbing by introducing negative correlation of search trends between search processes, which contributes greatly to the diversity maintenance of solutions. NCS models the search behaviors of individual search processes as probability distributions. On this basis, we further divide the search behaviors of a couple of search processes into global search behavior and local search behavior according to the size of the coverage of each search process. Then we present a new metaheuristic, namely negatively correlated search with asymmetry (NSA), which assumes that the search process with global search behavior should be away from the search process with local search behavior. Due to the asymmetry of the negative correlation between search processes, the efficiency of NSA has been greatly improved compared with NCS. The experimental results show that NSA is competitive to well-established search methods in the sense that NSA achieves the best overall performance on 20 multimodal real-parameter optimization problems.

Key words: complex real-parameter optimization, exploration and exploitation, parallel hill climbing, negatively correlated search (NCS), search behavior

中图分类号: