最优权动态控制学习机制的多种群遗传算法

doi:10.3778/j.issn.1673-9418.2008044

摘要/Abstract

摘要：

遗传算法（GA）的全局搜索能力强，易于操作，但收敛速度慢，易陷入局部极值。为克服上述缺陷，首先对算法初始化方法进行改进，采用海明距离作为聚类划分的相似性度量提出了一种均匀分区多种群初始化方法。该方法以相似性度量为准则划分出不同集合的聚类中心点，然后以偏好随机的方式产生多个不同的种群，避免算法因种群初始个体在解空间分布不够均匀而陷入局部收敛。其次在遗传算法中引入多种群并行机制和学习机制来提高算法的性能，通过对已有研究中两种机制在遗传算法中的作用进行分析，指出各自的优势和不足，分别对两种机制进行改进，提出改进的多种群并行机制与最优权动态控制的学习机制，并从理论角度探讨了改进的两种机制的合理性。最后，将两种机制有机结合起来，充分发挥两种机制的优点，抑制各自的不足之处。仿真实验结果表明，算法中经过改进的两种机制具有良好的沟通能力，结合新的初始化方法，使得算法在收敛速度和精度上都要优于其他几种已有的改进算法。

关键词: 遗传算法（GA）, 最优权, 多种群并行机制, 学习机制

Abstract:

Genetic algorithm (GA) has strong global search ability and is easy to operate, but it has some disadvantages, such as slow convergence speed, and easy to fall into local extreme. In order to overcome these disadvantages, an improved genetic algorithm is proposed in this paper. Firstly, instead of the random initialization method, a uniform partition multi-population initialization method is used to generate the initial populations. This method calculates clustering centers by the criterion of Hamming distance, so as to generate different populations. The algorithm can make the initial solutions disperse in the solution space as much as possible, thus avoiding the problem of local extremes. Secondly, the ideas of multi-population parallel mechanism and learning mechanism are introduced to further improve the performance of algorithm. Based on the analysis of advantages and disadvantages of the two mechanisms, new improvements are made to these two mechanisms. Modified multi-population parallel mechanism and optimal weight dynamic control learning mechanism are proposed. In addition, the rationality of the two improved mechanisms is discussed. At last, the above mentioned two mechanisms and the new initialization method are combined. Simulation results show that the proposed algorithm has better performance in convergence speed and accuracy than other genetic algorithms.

Key words: genetic algorithm (GA), optimal weight, multi-population parallel mechanism, learning mechanism

潘家文, 钱谦, 伏云发, 冯勇. 最优权动态控制学习机制的多种群遗传算法[J]. 计算机科学与探索, 2021, 15(12): 2421-2437.

PAN Jiawen, QIAN Qian, FU Yunfa, FENG Yong. Multi-population Genetic Algorithm Based on Optimal Weight Dynamic Control Learning Mechanism[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2421-2437.

参考文献

[1] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advanced in Engineering Software, 2014, 69(3): 46-61.
[2] HE J F, FU Z, YI S L, et al. Image segmentation with multi-threshold of gray-level & gradient-magnitude entropy based on genetic algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(8): 995-1003.
贺建峰, 符增, 易三莉, 等. 基于遗传算法的灰度-梯度熵多阈值图像分割[J]. 计算机科学与探索, 2015, 9(8): 995-1003.
[3] JIANG X K, FAN Y Q, WANG W. BP neural network camera calibration based on particle swarm optimization genetic algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(10): 1254-1262.
江祥奎, 范永青, 王婉. 基于粒子群遗传算法的BP神经网络摄像机标定[J]. 计算机科学与探索, 2014, 8(10): 1254-1262.
[4] MI A Z, LU Y. Classifier selection method with hybrid diversity measure[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(9): 1522-1530.
米爱中, 陆瑶. 使用混合差异性度量的分类器选择方法[J]. 计算机科学与探索, 2018, 12(9): 1522-1530.
[5] ZHENG M, ZHUO M G, ZHANG S G, et al. Reconstruction for gene regulatory network based on hybrid parallel genetic algorithm and threshold value method[J]. Journal of Jilin University (Engineering and Technology Edition), 2017, 47(2): 624-631.
郑明, 卓慕瑰, 张树功, 等. 基于混合并行遗传算法和阈值限定法的基因调控网络构建[J]. 吉林大学学报(工学版), 2017, 47(2): 624-631.
[6] WANG M, TAN Y S. Emergency dispatch of network public resources on cloud computing platform[J]. Computer Simulation, 2018, 35(2): 371-374.
王猛, 谭跃生. 云计算平台网络公共资源应急调度仿真研究[J]. 计算机仿真, 2018, 35(2): 371-374.
[7] LIU Z H, XUE Y, ZHOU C, et al. Population initialization improvement of robot path planning based on genetic algorithm[J]. Machine Tool & Hydraulics, 2019, 47(21): 5-8.
刘志海, 薛媛, 周晨, 等. 基于遗传算法的机器人路径规划的种群初始化改进[J]. 机床与液压, 2019, 47(21): 5-8.
[8] GUO X J, GUO C X, BAI L J. Improved genetic algorithm using semi-initialization and probabilistic sidturbance strategy[J]. Application Research of Computers, 2019, 36(12): 3670- 3673.
郭晓金, 郭彩杏, 柏林江. 采用半初始化和概率扰动策略改进的遗传算法[J]. 计算机应用研究, 2019, 36(12): 3670-3673.
[9] PEI X B, ZHANG C H. An imrpoved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J]. CAAI Transactions on Intelligent Systems, 2019, 14(3): 541-550.
裴小兵, 张春花. 应用改进区块遗传算法求解置换流水车间调度问题[J]. 智能系统学报, 2019, 14(3): 541-550.
[10] DONG L L, GONG G H, LI N, et al. Adaptive parallel sim-ulated annealing genetic algorithms based on cloud models[J]. Journal of Beijing University of Aeronautics and Astro-nautics, 2011, 37(9): 1132-1136.
董丽丽, 龚光红, 李妮, 等. 基于云模型的自适应并行模拟退火遗传算法[J]. 北京航空航天大学学报, 2011, 37(9): 1132-1136.
[11] ZHOU Y, ZHOU L S, WANG Y, et al. Application of multiple-population genetic algorithm in optimizing the train-set cir-culation plan problem[J]. Complexity, 2017: 3717654.
[12] HINTON G E, NOWLAN S J. How learning can guide evolution[J]. Complex Systems, 1987, 1(3): 495-502.
[13] TANG W B, CHEN Y N, ZHANG M. An energy balanced routing algorithm with simplex method[J]. Computer Tech-nology and Development, 2019, 29(3): 55-59.
汤文兵, 陈亚楠, 张牧. 一种引入单纯形法的能量均衡路由算法[J]. 计算机技术与发展, 2019, 29(3): 55-59.
[14] YU X M, SUN X H, LIU L P, et al. A phase unwrapping algorithm based on improved stimulated annealing genetic algorithm for interferometric SAR[J]. Computer Applications and Software, 2016, 33(10): 230-232.
于向明, 孙学宏, 刘丽萍, 等. 基于改进模拟退火遗传算法的INSAR相位解缠算法[J]. 计算机应用与软件, 2016, 33(10): 230-232.
[15] ZHANG G J, WU Z H, LIU X Y. Parallel genetic algorithm based on learning mechanism[J]. Journal of Computer App-lications, 2005, 25(2): 374-376.
张桂娟, 武兆慧, 刘希玉. 一种基于学习机制的并行遗传算法[J]. 计算机应用, 2005, 25(2): 374-376.
[16] HE W W, WANG J L, HU L S. The improvement and app-lication of real-coded multiple-population genetic algorithm[J]. Chinese Journal of Geophysics, 2009, 52(10): 2644-2651.
何委微, 王家林, 胡龙胜. 实数编码多种群遗传算法的改进及应用[J]. 地球物理学报, 2009, 52(10): 2644-2651.
[17] LI L Y, TANG Y B, LIU J X, et al. Application of the multiple population genetic algorithm in optimum design of air-core permanent magnet linear synchronous motors[J]. Proceedings of the CSEE, 2013, 33(15): 69-77.
李立毅, 唐勇斌, 刘家曦, 等. 多种群遗传算法在无铁心永磁直线同步电机优化设计中的应用[J]. 中国电机工程学报, 2013, 33(15): 69-77.
[18] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence[M]. 2nd ed. Cambridge: MIT Press, 1992.
[19] MA H W, CHEN F S. Optimal arrangement of dampers based on coarse-grained parallel genetic algorithm[J]. Journal of South China University of Technology (Natural Science Edition), 2019, 47(11): 104-111.
马宏伟, 陈丰收. 基于粗粒度并行遗传算法的阻尼器优化布置[J]. 华南理工大学学报(自然科学版), 2019, 47(11): 104-111.
[20] YANG J S, WANG Y, LI J, et al. Solving intuitionistic fuzzy multi-objection programming by improved genetic algorithm[J]. Journal of Detection & Control, 2017, 39(5): 96-101.
杨进帅, 王毅, 李进, 等. 求解直觉模糊多目标规划的改进遗传算法[J]. 探测与控制学报, 2017, 39(5): 96-101.
[21] CORRêA H P, DE CARVALHO V R R, VIEIRA F H T, et al. Reliability based genetic algorithm applied to allocation of fiber optics links for power grid automation[J]. Energies, 2019, 12(11): 1-26.
[22] XIAO J, PACHL J, LIN B L, et al. Solving the block-to-train assignment problem using the heuristic approach based on the genetic algorithm and tabu search[J]. Transportation Research Part B: Methodological, 2018, 108: 148-171.