差分进化算法在组合优化问题中的应用研究

摘要

在工程实践和科学研究中存在着大量的组合优化问题,且大多带有约束条件,采用传统的数学优化方法将很难求解。差分进化算法是近年提出的一种新的自然计算方法,也是基于种群迭代的群智能优化方法,虽在求解带约束的组合优化问题中得到较好应用,但在算法的精度和求解效率上仍存在着瓶颈。因此针对具体优化问题,研究并设计高效的差分进化算法正受到国内外研究者的普遍关注,也正逐步成为进化计算领域的研究热点。
　　 本研究紧紧围绕经典的背包问题和等圆Packing问题,它们是两类具有代表性的组合优化问题,进行较深入的探索研究,并取得相应的研究成果:
　　 (1)针对离散空间的组合优化问题,提出了一种基于置换策略的离散差分进化算法。主要的工作有:一是将置换策略和差分进化算法相结合,提出一种基于置换策略的单目标差分进化算法,并将该算法应用于求解单目标背包问题；二是结合NSGA-Ⅱ的精英保留机制,在差分进化算法的基础上,给出多目标差分进化算法；三是给出基于置换策略的多目标差分进化算法,应用该算法求解多目标背包问题。实验结果和分析表明,该算法能够有效地解决背包问题,特别是在大规模问题的求解上,算法优化性能明显优于NSGA-Ⅱ。
　　 (2)针对连续空间的大规模约束的组合优化问题,设计出求解问题的差分进化算法,并验证算法的可行性。本文选取其中的等圆Packing问题进行研究,将等圆Packing问题转换成多目标问题,设计出适合求解等圆Packing问题的差分进化算法,并通过大量实验,验证文中所设计算法的可行性。
　　 本论文通过对离散空间和连续空间组合优化问题的研究,设计了基于置换策略的离散差分进化算法、求解等圆Packing问题的差分进化算法。这些工作不仅对差分进化算法的研究有着重要的意义,也对差分进化算法的实际优化应用有着重要的意义。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景、目的及意义

1.2 课题的国内外研究现状

1.3 本文主要研究工作

1.4 本文的组织结构

第二章 差分进化算法

2.1 进化算法概述

2.1.1 进化算法框架

2.1.2 进化算法基本特征

2.2 差分进化算法

2.2.1 差分进化算法的基本思想

2.2.2 差分进化算法的特征

2.2.3 算法流程

2.2.4 控制参数的选择

2.3 多目标进化算法

2.3.1 多目标优化问题的定义

2.3.2 进化多目标优化的传统方法

2.3.3 性能评价指标

2.4 约束处理机制

2.5 本章小结

第三章 基于置换策略的差分进化算法应用研究

3.1 0/1背包问题描述

3.2 置换策略

3.3 基于置换策略的单目标差分进化算法

3.3.1 算法设计

3.2.3 实验结果

3.4 多目标差分进化算法

3.4.1 非支配精英选择机制

3.4.2 基于拥挤距离和拥挤距离排序机制

3.4.3 算法设计

3.5 基于置换策略的多目标差分进化算法

3.5.1 算法设计

3.5.2 评价指标

3.5.3 测试结果

3.6 本章小结

第四章 差分进化算法在等圆PACKING问题上的应用研究

4.1 等圆PACKING问题概述

4.2 等圆PACKING问题的研究概况

4.3 算法设计

4.3.1 基本思路

4.3.2 编码

4.3.3 整体框架

4.4 算法仿真和性能分析

4.5 本章小结

第五章 :总结和展望

参考文献

致谢

作者简介