摘要
设计了求解VRPSDP的粗粒度并行遗传算法(CGPGA),其中遗传算法以最优划分法计算适应值,邻域搜索法作为变异算子,定义了群体多样性结构。并行算法以单向环作为连接拓扑,各子群体独立进行遗传操作,迁移算子用于群体间的信息交流,采用多样性替换的方法进行个体替换。论文给出了CGPGA算法在集群系统上的重复非阻塞MPI实现。对典型VRPSDP实例进行测试的结果表明:CGPGA算法在大部分实例上超过了已知最好解,未达到已知最好解的实例与已知最好解的相对误差不超过1.5%。在计算速度方面,CGPGA算法具有接近线性甚至超线性的加速比,提高了遗传算法的求解速度。
A coarse-grained parallel genetic algorithm (CGPGA) was developed to solve VRPSDP, which uses an optimal splitting procedure to get the fitness value, a local search as the mutation operator The measure of population diversity was defined properly. The parallel algorithm used 1D ring as the topology, with a serial GA (SGA) running on each processor The migration operator was used to communicate between subpopulations, and the diversity replacement to replace individuals. The algorithm with the repeatedly non-blocking MPI on cluster system was implemented. The computational results carded out on VRPSDP benchmark instances indicate that the proposed CGPGA outperforms the best-known solutions in most instances, and the relative errors to the best-known solutions on the rest instances are less than 1.5%. The results also reveal that the CGPGA has linear even super linear speedup ratio, improving the computing speed of SGA significantly.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2009年第7期1962-1968,1973,共8页
Journal of System Simulation
基金
天津市自然科学基金资助项目(05YFJMJC01300)
天津市科技发展计划资助项目(043185111-12)
关键词
车辆路径问题
集送货需求
并行遗传算法
粗粒度
vehicle routing problem
delivery and pick-up
parallel genetic algorithm
coarse-grained