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

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

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

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.