广义分配问题的一种小生境遗传蚁群优化算法  

A Niching Genetic and Ant Colony Optimization Algorithm for Generalized Assignment Problem

作　　者：陈云飞[1] 刘玉树[1] 范洁[1] 赵基海[1] 

机构地区：[1]北京理工大学信息科学技术学院计算机科学工程系,北京100081

出　　处：《北京理工大学学报》2005年第6期490-494,共5页Transactions of Beijing Institute of Technology

基　　金：国家部委预研项目(11415133)

摘　　要：提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚁群优化算法用于求解NP难的广义分配问题,以避免经典求解算法存在的易陷于局部最优的缺陷.以典型的广义分配问题——火力分配为例,对该算法进行实验,并将实验结果与其它算法进行分析比较.结果表明:新复合算法优化效率高,运行时间短,对其它的NP问题同样适用.<Abstrcat> A niching genetic and ant colony optimization (NGACO) algorithm is proposed for the NP hard generalized assignment problem. NGACO is based on the combination of niching genetic algorithm and ant colony optimization algorithm to avoid local optima which often reside in the results of classical methods. Moreover, an intensive study on how to use this algorithm in GAP is made. Some experiments were made on weapon-target assignment problem (a typical application of GAP). Experiments' results are compared with those obtained by using other classical optimization algorithms. The results demonstrated that NGACO has high performance and short runtime in solving weapon-target assignment problem, and is viable for other NP-hard problems.

关 键 词：小生境遗传算法 蚁群优化算法 广义分配问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]