CARP问题混代并行遗传算法的研究

Research on Mixed Generation Parallel Genetic Algorithm for Capacitated Arc Routing Problem

遗传算法因为具有直接对结构对象进行操作、具有内在的隐并行性和更好的全局寻优能力、自适应地调整搜索方向等优点,已被人们广泛地应用于组合优化、函数优化、机器人学、信号处理等领域.但是随着传统遗传算法暴露出来的收敛速度慢且具有最优值无趣的缺陷等缺点,并行遗传算法得到了广泛的研究与发展.本文在现有CARP遗传算法基础上进行并行性改进,提出并实现全新的并行遗传算法——混代并行遗传算法(MGPGA算法),理论分析及实验结果表明:并行遗传算法较非并行遗传算法有更快的求解速度,混代并行遗传算法可行且更有效.

Genetic algorithm has many advantages such as directly operating on the structure of the ob- ject, inner implicit parallelism and better global optimization and adaptively adjusting search direction with no need for certain rules etc. Genetic algorithm has been widely applied in combination optimization, func- tion optimization, robotics and signal processing by people. But along with the exposure of insufficiency in traditional genetic algorithm such as slow convergence speed and boring of optimal value, parallel genetic algorithm has been widely researched and developed. This paper improves parallelism of CARP genetic al- gorithm and realizes MGPGA algorithm. The theoretical analysis and experimental results show that the parallel genetic algorithm, compared with non-parallel genetic algorithm, is faster on speed of solving problem. MGPGA algorithm is feasible and more effective.