基于蚁群并行算法的电气接线路径优化及仿真

Application of Ant Colony System to Wiring Path Optimization of Relay System and Its Parallel Algorithm Implementation

继电控制系统中元件的连接关系可以使用网络拓扑图描述,元件间的接线路径优化类似于旅行商(TSP)问题,属于NP完备的组合优化问题。本文将ACS蚁群算法引入接线路径优化,建立了适用于继电系统接线路径优化的计算模型,并在MPI(消息传递界面)的基础上实现了算法的并行化。通过对算法初始参数进行仿真分析,确定了各参数的最佳取值范围,实验结果证明,在参数选择适当的情况下,ACS蚁群算法具有很好的全局搜索能力和较快的收敛速度。

The connecting relation between electrical elements in relay system can be described through network topological graph. The optimization of electrical wiring path is similar with the traveling salesman problem, which is a typical combinational optimization problem and is proved to be NP-Complete. In this paper, Ant Colony System (ACS) algorithm is introduced into wiring path optimization of relay system, a mathematical model for wiring path optimization of relay control system has been made up, and a parallel algorithm of ACS has been implemented following message passing interface (MPI) model. A lot of computing simulation examples show its validity and prove that it can find better solution at higher convergence speed with the proper parameters.