求解0-1背包问题的改进粒子群算法与鸡群算法研究

发布时间：2023-03-23 22:32

　　随着全球经济的飞速发展,人们对于某些复杂问题处理效率的关注度日益增长,试图建立数学模型对其进行最优化求解。背包问题(KP,Knapsack Problem)作为运筹学中一类经典的组合优化问题,已被应用于诸多领域。而0-1背包问题(0-1KP)是背包问题中最基本的一个子问题,它有效刻画最初的设计状态和方程的原始思想,因此所有类型的KP都可以通过0-1KP转化变形,于是对0-1KP的优化及高效求解,成为目前研究的重要方向之一。但由于0-1KP实质为有约束优化问题,易出现非正常编码个体概率过高,易早熟等现象。本文基于0-1KP自身特点,以基本粒子群算法和鸡群算法为出发点,立足非正常编码个体、迭代效率和参数评价这三个主要问题进行处理。主要内容如下:首先,对于算法运行中出现的非正常编码个体,考虑现有贪心算法无法修复所有个体,为此引入两种贪心算子GMO和GOO,不仅能对非正常编码个体修正,更能对正常编码个体作进一步优化,从而显著提高算法的求解精度和效率。其次,考虑基本粒子群算法(PSO)局部搜索能力较差,易早熟,提出贪心优化粒子群算法(GOPSO)。在求解0-1KP时,设计线性递减的惯性权重,通过...

【文章页数】：42 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 前言
    1.1 研究背景及意义
    1.2 问题模型
    1.3 国内外研究现状
    1.4 论文内容与结构安排
第2章 基本粒子群算法和鸡群算法概述
    2.1 基本PSO算法
        2.1.1 算法简介
        2.1.2 算法原理
        2.1.3 算法设计及总体流程
    2.2 基本CSO算法
        2.2.1 算法简介
        2.2.2 算法原理
        2.2.3 算法设计及总体流程
    2.3 本章小结
第3章 求解0-1背包问题的贪心优化粒子群算法
    3.1 贪心算子的设计
    3.2 GOPSO算法设计及总体流程
    3.3 测试用例及环境描述
    3.4 实验结果分析
    3.5 本章小结
第4章 求解0-1背包问题的离散型鸡群优化算法
    4.1 离散化策略
    4.2 变异过程
        4.2.1 自适应权重组合变异
        4.2.2 定向变异
    4.3 DCSO算法设计及总体流程
    4.4 参数分析
    4.5 测试用例及环境描述
    4.6 实验结果分析
    4.7 本章小结
第5章 两种改进算法的对比
    5.1 测试数据
    5.2 实验结果及对比分析
    5.3 本章小结
第6章 总结与展望
    6.1 论文总结
    6.2 展望
参考文献
致谢
在学期间的科研情况



本文编号：3768881