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

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

本文针对最小代价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.