计算机应用 ›› 2019, Vol. 39 ›› Issue (10): 2992-2996.DOI: 10.11772/j.issn.1001-9081.2019030434

• 先进计算 • 上一篇    下一篇

求解旅行商问题的多样化搜索帝国竞争算法

陈孟辉, 刘俊麟, 徐健锋, 李向军   

  1. 南昌大学 软件学院, 南昌 330047
  • 收稿日期:2019-03-15 修回日期:2019-06-04 出版日期:2019-10-10 发布日期:2019-06-12
  • 通讯作者: 徐健锋
  • 作者简介:陈孟辉(1981-),男,台湾屏东人,副教授,博士,主要研究方向:机器学习、组合优化;刘俊麟(1998-),男,江西赣州人,主要研究方向:机器学习、启发式算法;徐健锋(1973-),男,江西南昌人,教授,博士研究生,主要研究方向:智能信息处理、数据挖掘、粒计算、机器学习;李向军(1972-),男,江西萍乡人,教授,硕士,主要研究方向:人工智能、数据挖掘、机器学习、组合优化、区块链。
  • 基金资助:
    国家自然科学基金资助项目(61763031,61762062,61862042);江西省科技创新平台项目(20181BCD40005);江西省主要学科学术和技术带头人项目(20172BCB22030)。

Imperialist competitive algorithm based on multiple search strategy for solving traveling salesman problem

CHEN Menghui, LIU Junlin, XU Jianfeng, LI Xiangjun   

  1. School of Software, Nanchang University, Nanchang Jiangxi 330047, China
  • Received:2019-03-15 Revised:2019-06-04 Online:2019-10-10 Published:2019-06-12
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61763031, 61762062, 61862042), the Science and Technology Innovation Platform Project of Jiangxi Province (20181BCD 40005), the Major Discipline Academic and Technical Leader Training Project of Jiangxi Province (20172BCB22030).

摘要: 帝国竞争算法是一种局部搜索能力较强的群智能优化算法,但过度的局部搜索会导致多样性丢失并陷入局部最优。针对这一问题提出基于多样化搜索的帝国竞争算法(MSSICA)。将国家定义为一条可行解,将王国定义成四种特性不同的组合人造解方式。在搜索时使用区块机制保留各自的优势解片段,并对不同的帝国使用差异化的组合人造解方式以搜索不同解空间的有效可行解信息。在陷入局部最优时,使用多样化搜索策略注入均匀分布的可行解替换较无优势的解以提升多样性。实验结果显示,多样化搜索策略可以有效地改善帝国算法的求解多样性,并提升求解质量与稳定性。

关键词: 组合性问题, 人造解, 帝国竞争算法, 全局搜索

Abstract: The imperialist competitive algorithm is a swarm intelligence optimization algorithm with strong local search ability, but excessive local search will lead to the loss of diversity and fall into local optimum. Aiming at this problem, an Imperialist Competitive Algorithm based on Multiple Search Strategy (MSSICA) was proposed. The country was defined as a feasible solution and the kingdoms were defined as four mechanisms of combinatorial artificial chromosome with different characteristics. The block mechanism was used to retain the dominant solution fragment during search and differentiated mechanisms of combinatorial artificial chromosome was used for different empires to search the effective and feasible solution information of different solution spaces. When it come to the local optimum, the multiple search strategy was used to inject a uniformly distributed feasible solution to replace a less advantageous solution to enhance the diversity. Experimental results show that the multiple search strategy can effectively improve diversity of the imperialist competitive algorithm and improve the quality and stability of the solution.

Key words: combinatorial problem, artificial chromosome, imperialist competitive algorithm, global search

中图分类号: