计算机应用 ›› 2012, Vol. 32 ›› Issue (06): 1682-1684.DOI: 10.3724/SP.J.1087.2012.01682

• 人工智能 • 上一篇    下一篇

改进的自适应遗传算法求解0/1背包问题

王娜1,向凤红1,毛剑琳2   

  1. 1. 昆明理工大学 信息工程与自动化学院，昆明 650000
    2. 昆明理工大学 信息工程与自动化学院，昆明 65000
  • 收稿日期:2011-11-14 修回日期:2012-01-18 发布日期:2012-06-04 出版日期:2012-06-01
  • 通讯作者: 王娜
  • 作者简介:王娜(1978-),女，河南漯河人，硕士研究生,主要研究方向：背包问题；〓向凤红(1964－)，男，四川绵阳人，教授，主要研究方向：工业生产过程控制与优化、先进控制技术；〓毛剑琳（1976-），女，广西桂林人，副教授，主要研究方向：无线传感器网络、网络控制系统。
  • 基金资助:
    云南省应用基础研究基金资助项目;云南省教育厅科学研究基金资助项目(08Y0093)

Modified adaptive genetic algorithms for solving 0/1 knapsack problems

WANG Na1,XIANG Feng-hong1,MAO Jian-lin2   

  1. 1. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming Yunnan 650000, China
    2. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming Yunnan 65000, China
  • Received:2011-11-14 Revised:2012-01-18 Online:2012-06-04 Published:2012-06-01
  • Contact: WANG Na

PDF

摘要： 为提高遗传算法求解问题的性能，提出一种改进的自适应遗传算法，该算法在交叉概率和变异概率公式中引入了当代迭代次数因子，提出了基因差别比例（Ca）的概念。Ca越大的基因位发生交叉、变异的概率越大，产生新个体的可能性越大；在模式生成操作中，确定基因位的选取同样由Ca决定。仿真结果表明，此算法在求解0/1背包问题时，其寻优能力有很大提高。

关键词: 0/1背包问题, 自适应遗传算法, 交叉变异概率, 交叉变异操作, 模式替代操作

Abstract: 0/1 Knapsack Problems is a typical optimization problem in Operations Research, Genetic Algorithms is one of the most commonly evolutionary algorithms used to solve the problems. This paper proposed an improved adaptive genetic algorithm. In this algorithm, we introduce the evolution number into the crossover probability and mutation probability formula、improve the crossover operator and mutation operator, and add a pattern replacement operation. The simulation results show that, the solution speed and the optimal solution have greatly improved with our algorithms.

Key words: 0/1 knapsack problems, adaptive genetic algorithms, crossover and mutation probability, crossover and mutation operator, pattern replacement operation

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：