|Table of Contents|

Linkage Indentification Genetic Algorithm for Duty Planning


Research Field:
Publishing date:


Linkage Indentification Genetic Algorithm for Duty Planning
ZHOU KunXIA Hong-shan
College of Civil Aviation,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
duty planning genetic algorithms gene linkage building blocks
TP301. 6
To improve the optimization performance of the genetic algorithm for duty planning,a linkage identification genetic algorithm is proposed. The algorithm defines linkage of genes based on the structure of duties, so that the relationship between different genes can be quantified. To optimize the structure of a chromosome,a locus-reordering operator is devised. The operator partitions the set of duties depending on linkage,and permutes genes with tight linkage sequentially. According to the optimized structure,a multi-point crossover operator is designed to construct offspring chromosomes by gene sections,which uses linkage to select the location of crossover points. In this way,different building blocks in parent chromosomes can be exchanged effectively. Therefore, the genetic algorithm has a satisfied performance and convergence property. The experimental results prove that the proposed algorithm can solve the problem successfully.


[1] SouaiN,Teghem J. Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem [J ]. European Journal of Operational Research, 2009, 199( 3) : 674-683.
[2] Park T,Kwang R R. Crew pairing optimization by a genetic algorithm with unexpressed genes[J]. Journal of Intelligent Manufacturing, 2006, 17( 4) : 375-383.
[3] Levine D. Application of a hybrid genetic algorithm to airline crew scheduling[J]. Computers and Operations Research, 1996, 23( 6) : 547-558.
[4] Kornilakis H, Stamatopoulos P. Crew pairing optimization with genetic algorithm[A]. Methods and Application of Artificial Intelligence[C]. Heidelberg,Germany: Springer, 2002: 109-120.
[5] Kotecha K,Sanghani G,Gambhava N. Genetic algorithm for airline crew scheduling problem using cost-based uniform crossover[A]. Applied Computing [C]. Heidelberg,Germany: Springer, 2004: 84-91.
[6] 周树德,孙增圻. 遗传算法中的联结关系[J]. 智能 系统学报, 2009,4 ( 6) : 483-489.
[7] Aporntewan C,Chongstitvatana P. Building-block identification by simultaneity matrix[J]. Soft Computing— A Fusion of Foundations,Methodologies and Applications, 2007, 11( 6) : 541-548.
[8] Munetomo M,Murao N,Akama K. A parallel genetic algorithm based on linkage identification[A]. Genetic and Evolutionary Computation[C]. Heidelberg,Germany: Springer, 2003: 1222-1233.
[9] Cheng Tao-ming,Yan Rong-zheng. Integrating messy genetic algorithms and simulation to optimize resource utilization[J]. Computer-Aided Civil and Infrastructure Engineering, 2009, 24( 6) : 401-415.
[10] Chen Ying-ping,Goldberg D E. Tightness time for the linkage learning genetic algorithm[A]. Genetic and Evolutionary Computation[C]. Heidelberg,Germany: Springer, 2003: 837-849.
[11] 孙晓燕,巩敦卫,杜学艳. 基于连接识别的协同进化 种群分割算法研究[J]. 控制与决策,2005,20( 6) : 702-705.
[12] 吕军,冯博琴,李波. 遗传算法进化中积木块的识别 和利用研究[J]. 西安交通大学学报,2006,40( 2) : 133-137.
[13] CCAR91—2007,一般运行和飞行规则[S].
[14] 付维方,张伟刚,孙春林. 航班排班中航班串生成与 筛选问题的算法与实现[J]. 中国民航学院学报, 2006, 24( 5) : 4-6.
[15] Zuo Guo-yu,Gong Dao-xiong,Ruan Xiao-gang. A linkage learning genetic algorithm with linkage matrix [J]. Journal of Electronic Science and Technology of China, 2006,4 ( 1) : 29-34.
[16] 朱宁,冯志刚,王祁. 基于小生境遗传算法的支持向 量机分类器参数优化[J]. 南京理工大学学报, 2009, 33( 1) : 16-20.
[17] 鲁峰,黄金泉. 航空发动机部件性能参数融合预测 [J]. 航空学报, 2009, 30( 10) : 1795-1800.
[18] 朱剑英. 智能系统非经典数学方法[M]. 武汉: 华中 科技大学出版社, 2001: 282-283.


Last Update: 2012-10-23