基于单亲遗传算法求解卫勤保障最短回路问题  

Solving shortest circuit problem of military health support based on partheno-genetic algorithm

作　　者：蒋兴波[1] 许开云[2] 刘晓荣[1] 

机构地区：[1]第二军医大学卫生勤务学系卫生勤务学教研室,上海200433 [2]第二军医大学长海医院急诊科,上海200433

出　　处：《第二军医大学学报》2010年第1期74-79,共6页Academic Journal of Second Military Medical University

基　　金：全军"十一五"科技攻关课题(08G078)~~

摘　　要：目的提出一种用于求解卫勤保障最短回路问题的有效算法。方法采用仅使用变异算子和选择算子来繁殖后代的单亲遗传算法(PGA)。该算法基于K-随机近邻算法,同时结合了随机两点位置互换、相邻两点位置互换、环形部分逆转、随机插入等4种变异算子,在选择操作过程中结合贪心策略,进一步提高PGA算法的"爬山"能力。结果通过对CTSP31以及多组TSP标准数据集的测试结果表明,该算法相对于文献中已有算法更加有效。结论该算法可作为今后开发计算机辅助软件的基础,为提高卫勤指挥的质量和速度而提供辅助优化决策。Objective To propose an effective algorithm for solving the shortest circuit problem of military health support. Methods Partheno-genetic algorithm （ PGA） ,which only used mutation operation and selection operation,was adopted in the present study. The algorithm was based on K-random-nearer-neighbor algorithm combined with two-random-point exchange,two-neighbor -point exchange,circular-based part inversion and random insertion mutation operations. Furthermore,greedy strategy was applied in selection to improve the hill -climbing capability of PGA. Results The simulation results of CTSP31 and standard dataset from TSP library indicated that the PGA was more effective than existing algorithms from the literature. Conclusion PGA can serve as a basis for further development of a computer-assisted program,and it provides optimized decision-making scheme for improving the quality and speed of military medical service disposition.

关 键 词：卫勤保障最短路径问题 旅行商问题 单亲遗传算法 K随机近邻算法 

分 类 号：R821.4[医药卫生—临床医学]