计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (28): 225-228.

• 工程与应用 • 上一篇    下一篇

求解巡警调度问题的遗传退火算法

代亚楠1,冯华玉1,孙国立2   

  1. 1.河南大学 物理与电子学院,河南 开封 475004
    2.河南大学 数学与信息科学学院,河南 开封 475004
  • 出版日期:2012-10-01 发布日期:2012-09-29

Genetic annealing algorithm for police officer scheduling problem

DAI Yanan1, FENG Huayu1, SUN Guoli2   

  1. 1.School of Physics and Electronic, Henan University, Kaifeng, Henan 475004, China
    2.School of Mathematics and Information Sciences, Henan University, Kaifeng, Henan 475004, China
  • Online:2012-10-01 Published:2012-09-29

摘要: 科学合理地调度巡警服务资源是提高公安部门执法能力的重要因素,为了优化调度方案并提高执法信息化水平,建立了巡警调度问题的数学模型,提出一种求解巡警调度问题的遗传退火算法。通过化简约束条件,方便了遗传算法的编码与解码、遗传与变异算子的设计。在遗传算法中引入模拟退火算法的Boltzmann更新机制,有效提高了算法的寻优能力。实验结果证明,遗传退火算法具有比传统遗传算法更强的寻优能力。

关键词: 遗传算法, 调度, 模拟退火

Abstract: It is an important factor for public security bureau to plan police officer scheduling in a scientific and reasonable way. In order to optimize scheduling method as well as enhance information innovation level of the security bureau, a mathematic model is proposed, and a genetic annealing algorithm is given. The constraints of the model are simplified, so it becomes easy to map the problem into genetic algorithm code, the method to design genetic or variation code are also simplified as well. The Boltzmann mechanism of simulated annealing is introduced into the genetic algorithm, so the ability of finding the best result is greatly enhanced. The experimental results show that the proposed algorithm is better than ordinary genetic algorithm to find the best result.

Key words: genetic algorithm, scheduling, simulated annealing