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

摘要

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

目录

摘要

第一章 绪论

1．1 研究背景及研究意义

1．2 当前国内外研究现状及发展趋势

1．3 热点与难点

1．4 本文的研究内容及结构安排

第二章 理论基础

2．1 多目标问题

2．1．1 多目标优化中几个常用概念

2．2 背包问题

2．3 群智能算法

2．4 遗传算法简介

2．5 粒子群算法简介

2．6 本章小结

第三章 人工鱼群算法

3．1 基本人工鱼群算法

3．1．1 觅食行为

3．1．2 聚群行为

3．1．3 追尾行为

3．1．4 随机行为

3．2 人工鱼群算法的基本参数

3．3 人工鱼群算法的寻优原理

3．4 常用的编码方式

3．5 常用距离介绍

3．5．1 明氏距离

3．5．2 兰氏距离

3．5．3 马氏距离

3．5．4 巴氏距离

3．5．5 黑林格距离

3．6 人工鱼群算法的改进

3．7 本章小结

第四章 求解多目标背包问题的改进人工鱼群算法

4．1 引言

4．2 多目标背包问题及其数学模型

4．3 人工鱼群算法

4．3．1 人工鱼群算法基本原理

4．3．2 人工鱼移动策略

4．3．3 自适应步长

4．3．4 全局人工鱼群算法

4．4 改进的人工鱼群算法

4．4．1 改进算法人工鱼的行为描述

4．4．2 算法基本流程

4．5 数值实验

4．5．1 实数编码方式

4．5．2 数值算例

4．6 实验结果

4．7 本章小结

结论

参考文献

攻读学位期间发表的学术论文

声明

致谢