基于禁忌搜索的启发式求解背包问题算法

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于禁忌搜索的启发式求解背包问题算法

张晓琴, 黄玉清

文章导航 > 电子科技大学学报 > 2005 > 34(3): 359-362

张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法[J]. 电子科技大学学报, 2005, 34(3): 359-362.

引用本文:

张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法[J]. 电子科技大学学报, 2005, 34(3): 359-362.

ZHANG Xiao-qin, HUANG Yu-qing. Heuristics Algorithm for Knapsack Problem Based on the Tabu Search[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(3): 359-362.

Citation:

ZHANG Xiao-qin, HUANG Yu-qing. Heuristics Algorithm for Knapsack Problem Based on the Tabu Search[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(3): 359-362.

基于禁忌搜索的启发式求解背包问题算法

1.
西南科技大学信控学院四川绵阳 621010

基金项目:

四川省教育厅青年基金资助项目(200-A53)

作者简介:
张晓琴(1974-),女,硕士,主要从事智能控制方面的研究.

中图分类号: TP18

Heuristics Algorithm for Knapsack Problem Based on the Tabu Search

1.
Dept. of Info & Contr,SWUST Sichuan Mianyang 621010

摘要: 设计了一种基于禁忌搜索的遗传算法,利用遗传算法提供的并行搜索主框架,结合禁忌算法的个体串行搜索方式,能扩大搜索空间,快速实现全局优化。把基于禁忌搜索的遗传算法与启发式方法相结合用来求解背包问题,经过计算机仿真,其优化性能指标及搜索效率均有大幅度的提高。
- 禁忌搜索 /
- 背包问题 /
- 遗传算法 /
- 贪婪算法
Abstract: The paper design a genetic algorithm based on the tabu search. By utilizing the main frame of parallel search supplied by the genetic algorithm and the individual serial search mode of the tabu algorithm, this method can enlarge the search space and swiftly implement the overall optimization. If it is combined with the heuristics algorithm to solve the knapsack problem, according to the results of computer simulation, it can effectively improve the index of optimization performance and search efficiency.
- tabu search /
- knapsack problem /
- genetic algorithm /
- greedy algorithm

[1]	万建臣, 靳宗信. 多峰值函数优化问题的免疫遗传算法求解 . 电子科技大学学报, 2013, 42(5): 769-772. doi: 10.3969/j.issn.1001-0548.2013.05.024
[2]	薛羽, 庄毅, 朱浩, 张友益礻禹. 求解协同干扰问题的高效免疫遗传算法 . 电子科技大学学报, 2013, 42(3): 452-458. doi: 10.3969/j.issn.1001-0548.2013.03.026
[3]	欧鹏, 李志蜀, 胡建, 林珣. 利用Betweenness Centrality计算网络流量矩阵的新算法 . 电子科技大学学报, 2012, 41(1): 152-157. doi: 10.3969/j.issn.1001-0548.2012.01.029
[4]	侯孟书, 李玉军, 秦志光. 三维传感器网络中贪婪算法的可达性分析 . 电子科技大学学报, 2012, 41(3): 441-446. doi: 10.3969/j.issn.1001-0548.2012.03.023
[5]	刘勇国, 朱婵, 晏华. 基于禁忌遗传算法的RNA二级结构预测 . 电子科技大学学报, 2011, 40(5): 765-771. doi: 10.3969/j.issn.1001-0548.2011.05.025
[6]	曾志民, 郑洁莹, 张天魁. OFDM系统多小区联合资源分配算法 . 电子科技大学学报, 2008, 37(6): 811-814.
[7]	岳培培, 刘建, SHEIKH Anjum, 陈杰. NoC映射问题中的列举路径分配算法 . 电子科技大学学报, 2008, 37(1): 54-57.
[8]	李向阳, 张亚非. 一种基于遗传算法的语义标注 . 电子科技大学学报, 2007, 36(1): 86-89.
[9]	吴传信, 倪明放, 陈鸣. 路由选择的一种新遗传算法 . 电子科技大学学报, 2006, 35(5): 744-747.
[10]	田延硕, 刘晓云. 一种提高局部搜索能力的混合遗传算法 . 电子科技大学学报, 2006, 35(2): 232-234,256.
[11]	唐普英, 李志辉, 黄顺吉. 基于遗传算法和禁忌搜索的多用户检测器 . 电子科技大学学报, 2004, 33(5): 499-502.
[12]	佘堃, 沈仟, 周明天. 背包问题在硬币抛掷协议上的研究 . 电子科技大学学报, 2003, 32(4): 417-419.
[13]	黄羽, 黄迪明, 何险峰, 武明. 遗传算法在入侵检测中的应用 . 电子科技大学学报, 2003, 32(6): 679-682.
[14]	王忠, 柴贺军, 刘浩吾. 关于进化遗传算法的几点改进 . 电子科技大学学报, 2002, 31(1): 76-79.
[15]	王海枚, 游志胜. 基于遗传算法与模糊控制的建模方法 . 电子科技大学学报, 2002, 31(3): 266-269.
[16]	张宇, 郭晶, 周激流. 动态变异遗传算法 . 电子科技大学学报, 2002, 31(3): 234-239.
[17]	饶克谨, 苟益. 电路模拟吸收体的遗传算法设计 . 电子科技大学学报, 2000, 29(1): 54-60.
[18]	王勇, 陈光. 面向时滞测试生成的改进遗传算法 . 电子科技大学学报, 1999, 28(2): 157-161.
[19]	吴斌, 吴坚, 涂序彦. 快速遗传算法研究 . 电子科技大学学报, 1999, 28(1): 49-53.
[20]	潘中良, 陈光. 测试图形生成的遗传算法研究 . 电子科技大学学报, 1997, 26(5): 511-514.

WeChat

点击查看大图

计量

文章访问数: 3488
HTML全文浏览量: 199
PDF下载量: 185
被引次数: 0

基于禁忌搜索的启发式求解背包问题算法

1. 西南科技大学信控学院四川绵阳 621010

基金项目:

四川省教育厅青年基金资助项目(200-A53)

作者简介:
张晓琴(1974-),女,硕士,主要从事智能控制方面的研究.

收稿日期: 2004-01-15
刊出日期: 2005-06-15

中图分类号: TP18

关键词:

摘要: 设计了一种基于禁忌搜索的遗传算法,利用遗传算法提供的并行搜索主框架,结合禁忌算法的个体串行搜索方式,能扩大搜索空间,快速实现全局优化。把基于禁忌搜索的遗传算法与启发式方法相结合用来求解背包问题,经过计算机仿真,其优化性能指标及搜索效率均有大幅度的提高。

English Abstract

张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法[J]. 电子科技大学学报, 2005, 34(3): 359-362.

引用本文:

张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法[J]. 电子科技大学学报, 2005, 34(3): 359-362.

ZHANG Xiao-qin, HUANG Yu-qing. Heuristics Algorithm for Knapsack Problem Based on the Tabu Search[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(3): 359-362.

Citation:

ZHANG Xiao-qin, HUANG Yu-qing. Heuristics Algorithm for Knapsack Problem Based on the Tabu Search[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(3): 359-362.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发