求解0-1整数规划问题的混沌遗传算法  

Chaos genetic algorithm for solving 0-1 integer programming problem

作　　者：桑晓丹[1] 罗兴国[1] 禹春来[1] 陈韬[1] 

机构地区：[1]解放军信息工程大学,郑州450002

出　　处：《计算机应用研究》2011年第7期2443-2445,共3页Application Research of Computers

基　　金：国家高技术研究发展计划资助项目(2009AA012201);上海市科委重大科技攻关项目(08dz501600)

摘　　要：针对一类特殊的0-1整数规划求解问题提出一种混沌遗传算法。该算法采用幂函数载波技术提高混沌搜索的充分性与遍历性,以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作,提高种群质量,同时增加种群多样性,改善遗传算法的早熟问题。该算法被用于解决片上网络映射A3MAP(architec-ture-aware analytic mapping)0-1整数规划问题。实验仿真证明,该算法的收敛速度和解的精度均优于A3MAP-GA。This paper proposed a chaos genetic algorithm for a special class of 0-1 integer programming problem. First, improved the adequacy and ergodicity of chaotic search by using the power function carrier technology, then, used the optimal individual derived from chaotic search algorithm as a new population of genetic algorithm to make crossover and mutation opera- tions ,which could improve the population quality and diversity and solve premature problem. Used the algorithm to solve the 0- 1 integer programming problem of network-on-chip A3MAP （architecture-aware analytic mapping） model. Simulation results show that the convergence speed and the accuracy of value is superior to A3MAP-GA.

关 键 词：混沌遗传算法 0-1整数规划 幂函数载波 片上网络 通信代价 

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