Heterogeneous Spatial Structure-Based Population Migration Dynamics Optimization Algorithm

doi:10.3778/j.issn.1673-9418.1909060

Abstract

Abstract:

To solve some complex optimization problems, an optimization algorithm of population migration dynamics with heterogeneous spatial structure (HSS-PMDO) is proposed by using the theory of population migration dyna-mics with heterogeneous spatial structure. In this algorithm, the solution space of the optimization problem corre-sponds to the island composed of several patches, each of which has one of the three survival conditions of compe-tition, mutual benefit and predator-prey. Populations will choose the patch with better adaptability for migration according to the living conditions of the patch. On the patch, populations interact with each other to adapt to the living conditions. Five operators are developed according to population migration and interaction. The competition operator can improve the exploitation ability of the algorithm. The mutual benefit operator and predator-prey ope-rator can improve the exploration ability of the algorithm. Migration operator can make the information exchange among populations sufficient, so as to improve the balance of exploration ability and exploitation ability. The selec-tion operator can ensure the global convergence of the algorithm. When the population evolves continuously, only part of its features change each time. The characteristic can improve the convergence speed. The test results show that the HSS-PMDO algorithm has fast convergence speed, strong exploration, exploitation and balance ability, and can quickly solve some complex optimization problems with higher dimensions.

Key words: swarm intelligence optimization algorithm, global optimization, population migration dynamics theory with heterogeneous spatial structure

摘要：

为了求解一些复杂优化问题，采用异质空间结构种群迁徙动力学理论，提出了异质空间结构种群迁徙动力学优化算法（HSS-PMDO）。在该算法中，优化问题的解空间与由若干个斑块组成的海岛相对应，每个斑块具有竞争、互利和捕食-被食3个生存条件之一。种群会依据所在斑块的生存条件选择适应度更好的斑块进行迁徙。在斑块上，种群相互之间展开与生存条件相适应的相互作用。依据种群的迁徙和相互作用开发出了5个算子：竞争算子可提升算法的求精能力；互利算子和捕食-被食算子可提升算法的探索能力；迁徙算子可使得种群间信息交换充分，从而提升了探索能力和求精能力的平衡性；选择算子可确保算法具有全局收敛性。当种群不断进化时，每次只有其部分特征发生变化，该特征可提高收敛速度。测试结果表明，HSS-PMDO算法具有收敛速度快，探索、求精及其平衡能力强，能够快速求解一些维数较高的复杂优化问题。

关键词: 群智能优化算法, 全局优化, 异质空间结构种群迁徙动力学理论

HUANG Guangqiu, LU Qiuqin. Heterogeneous Spatial Structure-Based Population Migration Dynamics Optimization Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1787-1800.

黄光球，陆秋琴. 异质空间结构种群迁徙动力学优化算法[J]. 计算机科学与探索, 2020, 14(10): 1787-1800.

References

[1] Chen L S, Meng X Z, Jiao J J. Biodynamics[M]. Beijing: Science Press, 2009. 陈兰荪, 孟新柱, 焦建军. 生物动力学[M]. 北京: 科学出版社, 2009.
[2] Wang K. Stochastic biological mathematical model[M]. Bei-jing: Science Press, 2010. 王克. 随机生物数学模型[M]. 北京: 科学出版社, 2010.
[3] Wang S Q, Wang W X, Xu H G. Stability theory and method of mathematical ecology[M]. Beijing: Science Press, 2004. 王顺庆, 王万雄, 徐海根. 数学生态学稳定性理论与方法[M]. 北京: 科学出版社, 2004.
[4] Xue W Y, Zhao J, Hao C Q, et al. Hyper heuristic ant colony optimization algorithm based on pheromone negative feedback[J]. Computer Engineering and Applications, 2019, 55(4): 163-172.薛文艳, 赵江, 郝崇清, 等. 基于信息素负反馈的超启发式蚁群优化算法[J]. 计算机工程与应用, 2019, 55(4): 163-172.
[5] Li W, Chao X Q. Improved particle swarm optimization met-hod for feature selection[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(6): 990-1004. 李炜, 巢秀琴. 改进的粒子群算法优化的特征选择方法[J]. 计算机科学与探索, 2019, 13(6): 990-1004.
[6] Liu M X, You X M, Liu S. Adaptive dynamic chaotic ant colony algorithm based on degree of aggregation[J]. Computer Engineering and Applications, 2019, 55(3): 15-22.刘明霞, 游晓明, 刘升. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[7] Praveen C, Duvigneau R. Low cost PSO using metamodels and inexact pre-evaluation: application to aerodynamic shape design[J]. Computer Methods in Applied Mechanics & Engineering, 2018, 198(9): 1087-1096.
[8] Simon D. Biogeography-based optimization[J]. IEEE Trans-actions: Evolutionary Computation, 2008, 12(6): 702-713.
[9] Wang C, Wang Y, Wang K S, et al. An improved hybrid algo-rithm based on biogeography/complex and metropolis for many-objective optimization[J]. Mathematical Problems in Engin-eering, 2017(5): 1-14.
[10] Garg H. An efficient biogeography based optimization alg-orithm for solving reliability optimization problems[J]. Swarm and Evolutionary Computation, 2015, 24: 1-10.
[11] Zhou X, Liu Y H, Li B, et al. Multiobjective biogeography based optimization algorithm with decomposition for com-munity detection in dynamic networks[J]. Physica A: Stati-stical Mechanics and Its Applications, 2015, 436: 430-442.
[12] Karthigeyan P, Senthil R M, Hariharan R, et al. Comparison of harmony search algorithm, improved harmony search algorithm with biogeography based optimization algorithm for solving constrained economic load dispatch problems[J]. Procedia Technology, 2015, 21: 611-618.
[13] Yang G Q, Liu Y K. Optimizing an equilibrium supply chain network design problem by an improved hybrid biogeography based optimization algorithm[J]. Applied Soft Computing, 2017, 58: 657-668.
[14] Li C X, Zhang Y. Biogeography-based optimization algo-rithm based on the dual-mode migration strategy[J]. Journal of Xi??an University of Posts and Telecommunications, 2019, 24(1): 73-78. 李昌兴, 张颖. 基于双模式迁移策略的生物地理学优化算法[J]. 西安邮电大学学报, 2019, 24(1): 73-78.
[15] Zhang X M, Kang Q, Cheng J F, et al. Biogeography-based optimization algorithm with differential mutation and cross migration[J]. Journal of Zhengzhou University (Natural Science Edition), 2018, 50(1): 47-53. 张新明, 康强, 程金凤, 等. 差分变异和交叉迁移的生物地理学优化算法[J]. 郑州大学学报(理学版), 2018, 50(1): 47-53.
[16] Zhang X M, Kang Q, Wang X, et al. Biogeography-based optimization with differential migration and global-best mu-tation[J]. Journal of Chinese Computer Systems, 2018, 39(6): 1168-1177. 张新明, 康强, 王霞, 等. 差分迁移和趋优变异的生物地理学优化算法[J]. 小型微型计算机系统, 2018, 39(6): 1168-1177.
[17] Zhang X M, Kang Q, Tu Q, et al. Hybrid BBO algorithm based on chemotaxis operator of bacterial foraging algori-thm[J]. Journal of Zhengzhou University (Natural Science Edition), 2016, 48(4): 44-53. 张新明, 康强, 涂强, 等. 融合细菌觅食趋化算子的生物地理学优化算法[J]. 郑州大学学报(理学版), 2016, 48(4): 44-53.
[18] Ma P, Liu S H, Sun G Y, et al. Neighbor force learning bio-geography-based optimization[J]. Computer Engineering and Applications, 2018, 54(22): 35-41. 马萍, 刘思含, 孙根云, 等. 基于邻域引力学习的生物地理学优化算法[J]. 计算机工程与应用, 2018, 54(22): 35-41.
[19] Parimal K G, Sagar S D, Dehuri S. Adaptive neighbour-hood for locally and globally tuned biogeography based optimization algorithm[J]. Journal of King Saud University-Computer and Information Sciences, 2018: 1-15.
[20] Reihanian A, Feizi-Derakhshi M R, Aghdasi H S. NBBO: a new variant of biogeography-based optimization with a novel framework and a two-phase migration operator[J]. Information Sciences, 2019, 504(10): 178-201.
[21] Kaveh M, Mesgari M S. Improved biogeography-based opti-mization using migration process adjustment: an approach for location-allocation of ambulances[J]. Computers & Indu-strial Engineering, 2019, 135(9): 800-813.
[22] Kaveh M, Khishe M, Mosavi M R. Design and implemen-tation of a neighborhood search biogeography-based optimi-zation trainer for classifying sonar dataset using multi-layer perceptron neural network[J]. Analog Integrated Circuits and Signal Processing, 2019, 100(2): 405-428.
[23] Farswan P, Bansal J C. Fireworks-inspired biogeography-based optimization[J]. Soft Computing, 2019, 23(16): 7091-7115.
[24] Zhao F Q, Qin S, Zhang Y, et al. A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2019, 126(7): 321-339.
[25] Huang G Q. SIS epidemic model-based optimization[J]. Journal of Computational Science, 2014, 5: 32-50.
[26] Wang X, Dong X M, Yan R X, et al. Improved DE/EDA algorithm for difficult COPs[J]. Application Research of Computers, 2010, 27(11): 4114-4117. 王翔, 董晓马, 阎瑞霞, 等. 改进DE/EDA算法在求解难约束优化问题中的应用研究[J]. 计算机应用研究, 2010, 27(11): 4114-4117.
[27] Liang J J, Qu B Y, Suganthan P N, et al. Problem defini-tions and evaluation criteria for the CEC 2013 special session on real-parameter optimization: technical report 201212[R]. Singapore: Nanyang Technological University, 2013.
[28] Bansal J C, Farswan P. A novel disruption in biogeography-based optimization with application to optimal power flow problem[J]. Applied Intelligence, 2017, 46(3): 590-615.
[29] Ma H P, Simon D. Blended biogeography-based optimization for constrained optimization[J]. Engineering Applications of Artificial Intelligence, 2011, 24(3): 517-525.
[30] Zhang Y, Wu X, Lu S, et al. Smart detection on abnormal breasts in digital mammography based on contrast-limited adaptive histogram equalization and chaotic adaptive real-coded biogeography-based optimization[J]. Simulation, 2016, 92(9): 873-885.
[31] Al-Roomi A R, El-Hawary M E. Metropolis biogeography-based optimization[J]. Information Sciences, 2016, 360: 73-95.
[32] Wang S, Li P, Chen P, et al. Pathological brain detection via wavelet packet tsallis entropy and real-coded biogeography-based optimization[J]. Fundamenta Informaticae, 2017, 151(1): 275-291.
[33] Bi X J, Wang J, Li B. Multi-objective optimization based on hybrid biogeography-based optimization[J]. Journal of Systems Engineering and Electronics, 2014, 36(1): 179-186.毕晓君, 王珏, 李博. 基于混合生物地理学优化的多目标优化算法[J]. 系统工程与电子技术, 2014, 36(1): 179-186.