火力优化分配问题的小生境遗传蚂蚁算法  

Niche-based genetic & ant colony optimization algorithm for generalized assignment problem

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

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

出　　处：《计算机应用》2005年第1期206-209,共4页journal of Computer Applications

基　　金：国家部委预研项目

摘　　要：火力分配问题是NP难题,经典的求解算法存在指数级的时间复杂度。文中提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚂蚁算法,并针对具体问题提出蚂蚁搜索的禁忌规则。对该算法进行了实验,并将实验结果与其他算法进行比较分析,分析结果表明:新算法无论是在优化性能还是在时间性能都取得了非常好的效果。文中算法对其他的NP问题同样适用。Weapon-Target Assignment problem (WTA) is NP hard. Classical methods for solving such problems are based on graph search approaches and usually result in exponential computational complexities. A novel Niching Genetic & Ant Colony Optimization (NGACO) algorithm based on the combination of niche-based genetic algorithm and ant colony algorithm was proposed. Moreover, an intensive study of how to use this algorithm in WTA was made. Some experiments were made. Experiment results were compared with those obtained using other classical optimization algorithm. The results demonstrated that NGACO is an effective and efficient algorithm, and is viable for other NP-hard problem.

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

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]