| 摘要: |
| 目的提出一种用于求解卫勤保障最短回路问题的有效算法。方法采用仅使用变异算子和选择算子来繁殖后代的单亲遗传算法（PGA）。该算法基于K-随机近邻算法，同时结合了随机两点位置互换、相邻两点位置互换、环形部分逆转、随机插入等4种变异算子,在选择操作过程中结合贪心策略，进一步提高PGA算法的“爬山”能力。结果通过对CTSP31以及多组TSP标准数据集的测试结果表明，该算法相对于文献中已有算法更加有效。结论该算法可作为今后开发计算机辅助软件的基础，为提高卫勤指挥的质量和速度而提供辅助优化决策。 |
| 关键词: 卫勤保障最短路径问题 旅行商问题 单亲遗传算法 K-随机近邻算法 |
| DOI：10.3724/SP.J.1008.2010.074 |
| 投稿时间：2009-07-01修订日期：2009-11-20 |
| 基金项目:全军“十一五”科技攻关课题(08G078). |
|
| Solving shortest circuit problem of military health support based on partheno-genetic algorithm |
| JIANG Xing-bo1,XU Kai-yun2,LIU Xiao-rong1* |
| (1.Department of Military Health Service,Faculty of Health Services,Second Military Medical University,Shanghai 200433,China;2.Department of Emergency Medicine,Changhai Hospital,Second Military Medical University,Shanghai 200433,China) |
| Abstract: |
| ObjectiveTo propose an effective algorithm for solving the shortest circuit problem of military health support.MethodsPartheno-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.ResultsThe simulation results of CTSP31 and standard dataset from TSP library indicated that the PGA was more effective than existing algorithms from the literature.ConclusionPGA 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. |
| Key words: the shortest circuit problem of health support traveling salesman problem partheno genetic algorithm K-random-nearer-neighbor algorithm |
