细胞型膜进化算法求解旅行商问题  

Cell-based membrane evolutionary algorithm for solving the Travelling Salesman Problem

作　　者：周桃静 许家昌[1] ZHOU Taojing;XU Jiachang(School of Computer Science and Engineering,Anhui University of Science and Technology,Huainan Anhui 232001)

机构地区：[1]安徽理工大学计算机科学与工程学院,安徽淮南232001

出　　处：《宁夏师范学院学报》2024年第7期72-83,共12页Journal of Ningxia Normal University

基　　金：南方林业与生态应用技术国家工程实验室开放基金项目(2023NFLY08);安徽理工大学医学专项项目(YZ2023H2B008)。

摘　　要：结合细胞型膜进化算法探索解决旅行商问题的方法.首先构建一个细胞型膜结构模型,利用膜系统的极大并行性,在基本膜中通过混合粒子群算法初始化种群.然后,通过膜进化算法的分裂、融合、溶解和修复算子,迭代地优化路径的全局最优解.最后,根据每个基本膜的适应度,选取适应度值最大的膜作为旅行商问题的解.在实验中,将该算法应用于多个实例,并与传统的粒子群算法和遗传算法等进行比较.实验结果表明,该算法在求解旅行商问题方面表现出更好的收敛性和搜索能力,显著提高了求解效果.The paper explores a method to solve the Travelling Salesman Problem by combining a cell-based membrane evolutionary algorithm.Firstly,the algorithm constructs a cell-based membrane structure model and takes advantage of the great parallelism of membrane systems to initialize the population in the elementary membrane by Hybrid Particle Swarm Optimization.Then,the global optimal solution of the path is iteratively optimized by splitting,fusion,dissolution,and repair operators of the membrane evolutionary algorithm.Finally,based on the fitness of each elementary membrane,the membrane with the highest fitness value is selected as the solution of the TSP.In the experiments,the algorithm is applied to several TSP instances and compared with traditional Particle Swarm Optimization and Genetic Algorithm,etc.The experimental results show that the proposed algorithm exhibits better convergence and search capabilities in solving the TSP,significantly improving the solution results.

关 键 词：细胞型膜系统 膜进化算法 TSP 混合粒子群算法 适应度 算法融合 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]