改进遗传算法及其在背包问题中的应用  

Improved GA and its application to knapsack problem

作　　者：苑立伟[1] 刘付显[1] 赵保军[1] 

机构地区：[1]空军工程大学导弹学院,陕西三原713800

出　　处：《系统工程与电子技术》2005年第4期718-719,747,共3页Systems Engineering and Electronics

摘　　要：介绍了一种改进的遗传算法,给出了应用该算法的具体步骤。该算法通过使用二元染色体编码方式,利用基因处于不同状态的概率来表示等位基因,既使染色体具有了更多的信息量,又能够保证遗传算法的收敛性。通过旋转变换实现了染色体的进化,提高了算法的全局搜索能力和收敛速度。并利用组合优化中典型的背包问题对算法进行了验证,并和基本遗传算法的结果进行了比较。An improved genetic algorithm is introduced and its procedure is provided in detail. The algorithm provides the chromosome with more amount of information and ensures the convergence by using binary chromosome and expressing alleges with the probability of the gene in different states. The chromosome is evolved through rotation. Global search capability and convergence speed are improved. The effectiveness of the improved approach is demonstrated based on its application to knapsack problem.

关 键 词：遗传算法 二元染色体编码 背包问题 收敛速度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]