蚁群算法求解MKP问题的设计与实现

论文摘要

背包问题（KP）是经典的NP-Hard难组合优化问题之一,多维背包问题（MKP）对背包问题增加多维的约束,大大增加了求解难度,该问题在资源分配和资金预算等方面具有重要的应用。蚁群算法（ACO）作为一种比较新的元启发算法,目前在一些路径选择优化问题上的应用效果显著,但是关于ACO在MKP问题上应用的论述还很少。本文通过对MKP问题研究现状的分析,提出一个新的蚁群优化算法Core-ACO,对问题实例的地形分析和基于效率函数的核心概念进行研究。通过利用适应度地形分析MKP问题解空间的特性,将适用于MKP的解优化法和核心区局部搜索方法融入ACO算法中。通过向可能的收敛方向提高搜索的纵向探测,增强算法局部搜索能力,成功的把Core-ACO算法运用于解MKP问题。通过实验发现,此算法在取得很好所得解质量的前提下,有效减小搜索空间。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 MKP介绍
• 1.1.1 MKP的问题描述
• 1.1.2 MKP的benchmark
• 1.2 研究内容
• 1.2.1 解空间适应度度地地形分析
• 1.2.2 ACO与MKP问题题特特性的结合
• 1.3 研究意义
• 1.4 本文结构
• 第二章 各类背包问题的综述
• 2.1 背包问题
• 2.2 背包问题的衍生问题
• 2.2.1 多维背包问题Multidimensional Knapsack Problem
• 2.2.2 二次背包问题Quadratic Knapsack Problem（QKP）
• 2.2.3 多目标标背背包问题Multi-Object Knapsack Problem
• 2.2.4 多选择背包问题Multiple-choice Knapsack Problem
• 2.2.5 多（重）背包问题Multiple Knapsack Problem
• 2.2.6 容易混淆的几个问题与多维背包问题的区别
• 2.3 求解MKP问题的方法综述
• 2.3.1 精确算法
• 2.3.2 遗传算法:Genetic Algorithm
• 2.3.3 模模拟拟退火:Simulated Annealing
• 2.3.4 禁忌算法:Taboo Search
• 2.3.5 蚂蚁算法:ANT Algorithm
• 2.3.6 MKP问题分析
• 2.4 本章小结
• 第三章 MKP问题的地形分析
• 3.1 简介
• 3.2 基本概念
• 3.3 小规模问题上的地形分析
• 3.3.1 MKP问题的解模式分析
• 3.3.2 解模式与搜索空间的关系
• 3.3.3 结果分析
• 3.4 HCF-ANT分析地形
• 3.4.1 超立方框架（Hyper-Cube Framework）
• 3.4.2 HCF-ANT
• 3.4.3 结果分析
• 3.5 小结
• 第四章 Core-ACO方法求解MKP问题
• 4.1 核心Core的概念
• 4.1.1 适用于KP问题的核心概念
• 4.1.2 适用于MKP问题的核心概念
• 4.2 Core-ACO解MKP
• 4.2.1 计算物体的效率值
• 4.2.2 信息素的初始化
• 4.2.3 动态核心区
• 4.2.4 局部搜索
• 4.3 试验结果
• 4.4 本章小结
• 第五章 总结
• 5.1 已完成工作总结
• 5.2 今后的研究展望
• 参考文献
• 发表文章目录
• 致谢
• 附录A MKP实例文件格式
• 附录B 代码说明
• 附录C 代码片段