基于人工鱼群算法的多目标背包问题研究

发布时间：2017-03-19 17:04

  本文关键词：基于人工鱼群算法的多目标背包问题研究，由笔耕文化传播整理发布。

【摘要】：多目标优化问题和背包问题一直是科学和工程研究领域的难点和热点问.与单目标背包问题相比,多目标背包问题一般包括两个或两个以上的优化目标,因此问题复杂度更高.动态规划之类的经典优化算法很难用可行的计算成本和计算时间搜索到比较满意的高质量解,需要研究更加高效的算法结构以快速找到Pareto最优解.论文首先总结归纳了求解多目标背包问题常用的两种群智能方法：遗传算法和粒子群算法.遗传算法计算简单,容易实现编程,但容易出现早熟现象以及接近最优解时在最优解附近左右摆动;粒子群算法计算速度快,但求解精度低.然后详细介绍了人工鱼群算法,归纳了几种常用距离及人工鱼群算法常用的编码方式,并对人工鱼群算法求解目标背包问题进行重点研究;最后在全局人工鱼群算法的基础上,针对人工鱼编码方式、人工鱼移动策略设计了一种改进的人工鱼群算法.求解多目标背包问题时,人工鱼群算法存在盲目搜索、求解复杂度高、求解精度不高和求解后期收敛速度慢等问题;背包问题一般采用二进制编码进行问题求解,但使用二进制编码需频繁进行编码和解码会大大增加算法计算量：在人工鱼群算法中,两条鱼的距离实际使用的是欧氏距离,具有盲目性和随机性.针对这些问题,本文的主要工作是提出一种改进的人工鱼群算法.论文在设计改进的人工鱼群算法时,首先针对本文多目标背包问题的数学模型,定义了一个实数编码,对人工鱼位置进行实数编码;接着在全局人工鱼群算法的基础上,修改人工鱼的移动策略,去掉欧式距离,加入一个依赖迭代次数的自适应因子,降低人工鱼盲目搜索的机率,从而降低算法的搜索复杂度;最后针对背包问题的离散性和多目标优化问题的特性,采用将搜索到的所有非劣解到原点的距离算术平均值来评价算法的求解精度,用距离算术平均值的变化趋势来评价算法的收敛性.论文对改进的人工鱼群算法进行了实验分析.结果表明,改进的算法在求解多目标背包问题时明显提高了算法的收敛速度和求解精度.同时,与经典的群智能优化算法遗传算法和粒子群算法相比,本文改进的算法在求解质量、高质量解的数量、解分布的均匀性都表现出明显的优势.随着多目标背包问题规模的增加,本文改进的算法优势更加突出.
【关键词】：多目标优化 背包问题 人工鱼群算法 自适应 实数编码
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-5
• ABSTRACT5-11
• 第一章 绪论11-15
• 1.1 研究背景及研究意义11-12
• 1.2 当前国内外研究现状及发展趋势12-13
• 1.3 热点与难点13-14
• 1.4 本文的研究内容及结构安排14-15
• 第二章 理论基础15-22
• 2.1 多目标问题15-16
• 2.1.1 多目标优化中几个常用概念15-16
• 2.2 背包问题16-17
• 2.3 群智能算法17-18
• 2.4 遗传算法简介18-19
• 2.5 粒子群算法简介19-21
• 2.6 本章小结21-22
• 第三章 人工鱼群算法22-31
• 3.1 基本人工鱼群算法22-23
• 3.1.1 觅食行为22
• 3.1.2 聚群行为22-23
• 3.1.3 追尾行为23
• 3.1.4 随机行为23
• 3.2 人工鱼群算法的基本参数23-25
• 3.3 人工鱼群算法的寻优原理25
• 3.4 常用的编码方式25-26
• 3.5 常用距离介绍26-28
• 3.5.1 明氏距离26-27
• 3.5.2 兰氏距离27
• 3.5.3 马氏距离27-28
• 3.5.4 巴氏距离28
• 3.5.5 黑林格距离28
• 3.6 人工鱼群算法的改进28-30
• 3.7 本章小结30-31
• 第四章 求解多目标背包问题的改进人工鱼群算法31-39
• 4.1 引言31
• 4.2 多目标背包问题及其数学模型31-32
• 4.3 人工鱼群算法32-33
• 4.3.1 人工鱼群算法基本原理32
• 4.3.2 人工鱼移动策略32
• 4.3.3 自适应步长32-33
• 4.3.4 全局人工鱼群算法33
• 4.4 改进的人工鱼群算法33-35
• 4.4.1 改进算法人工鱼的行为描述34-35
• 4.4.2 算法基本流程35
• 4.5 数值实验35-36
• 4.5.1 实数编码方式35-36
• 4.5.2 数值算例36
• 4.6 实验结果36-38
• 4.7 本章小结38-39
• 结论39-40
• 参考文献40-44
• 攻读学位期间发表的学术论文44-46
• 致谢46

【参考文献】

中国期刊全文数据库 前10条

1 朱旭辉;倪志伟;程美英;;变步长自适应的改进人工鱼群算法[J];计算机科学;2015年02期

2 马宪民;刘妮;;自适应视野的人工鱼群算法求解最短路径问题[J];通信学报;2014年01期

3 廖煜雷;苏玉民;张磊;;一种自适应人工鱼群算法及其在无人艇控制中的应用[J];中南大学学报(自然科学版);2013年10期

4 李枝勇;马良;张惠珍;;蝙蝠算法在多目标多选择背包问题中的应用[J];计算机仿真;2013年10期

5 张雁;肖伟;;基于禁忌粒子群求解多目标0-1背包问题的研究与实现[J];软件导刊;2012年03期

6 张超群;郑建国;钱洁;;遗传算法编码方案比较[J];计算机应用研究;2011年03期

7 熊小华;宁爱兵;马良;;多目标0-1背包问题的元胞竞争决策算法[J];计算机应用研究;2010年10期

8 孙涛;谢晓方;孙永芹;;基于改进Fish-Search算法的机弹协同航线规划[J];弹箭与制导学报;2010年03期

9 陈广洲;徐晓春;汪家权;胡淑恒;;改进的人工鱼群算法在水质参数识别中的应用[J];水力发电学报;2010年02期

10 王兴伟;秦培玉;黄敏;;基于人工鱼群的ABC支持型QoS单播路由机制[J];计算机学报;2010年04期

中国博士学位论文全文数据库 前1条

1 李晓磊;一种新型的智能优化方法-人工鱼群算法[D];浙江大学;2003年

中国硕士学位论文全文数据库 前1条

1 程永明;群智能优化算法及其在通信中的应用研究[D];山东大学;2010年

  本文关键词：基于人工鱼群算法的多目标背包问题研究，由笔耕文化传播整理发布。

，

本文编号：256271