求解最优Steiner树的前驱编码粒子群算法  

A predecessor-encoding-based particle swarm optimizer for least-cost Steiner tree problem

作　　者：刘庆[1] 李星 王洋 李迎 LIU Qing;LI Xing;WANG Yang;LI Ying(School of Automation and Information Engineering,Xi’an University of Technology,Xi’an 710048,China;Graduate School of Engineering,Nagoya University,Nagoya 464-8603,Japan;School of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China)

机构地区：[1]西安理工大学自动化与信息工程学院,陕西西安710048 [2]名古屋大学大学院工学研究科,日本名古屋市464-8603 [3]西安工程大学计算机科学学院,陕西西安710048

出　　处：《西安理工大学学报》2020年第2期221-229,共9页Journal of Xi'an University of Technology

基　　金：国家自然科学基金资助项目(61502385)。

摘　　要：本文针对最小代价Steiner树问题,提出一种前驱编码粒子群算法。为了避免环的产生,粒子向量采用前驱节点编码表示;重新设计粒子飞行实现方式,引入了基于邻接矩阵的“开发”算子以及基于剔除相同适应度值粒子策略的“勘探”算子。仿真实验表明,本文提出的算法能有效解决Steiner树问题,并且在多数测试算例上的表现优于已有算法。A predecessor-encoding-based particle swarm optimizer for least-cost Steiner tree problem is proposed.For avoiding the production of loop-topo,each particle-vector is represented in the form of predecessor-encoding.The implementation of particle flying is redesigned through introducing an adjacency-matrix-based exploitation operator and an exploration operator based on removing the particles with the same fitness values.The experimental simulation shows that the proposed algorithm is capable of obtaining high quality Steiner tree topology and surpassing most existing Steiner-tree-algorithms in terms of tree-cost.

关 键 词：粒子群算法 STEINER树 前驱编码 优化 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]