模糊环境下的一些优化问题模型和算法研究

论文摘要

指派问题,匹配问题,支撑树问题和运输问题在诸如系统优化,作业调度,模式识别和物流等系统中有着广泛的应用。根据应用背景的不同,这些问题又进一步扩展为二次指派,二次匹配,二次支撑树,固定费用的运输问题和均衡优化等问题。而这些扩展问题大多数属于NP-难问题。此外,在这些问题被应用到实际系统中时,有时会遇到大量的不确定性。本文将研究这些问题在模糊环境下的建模方法和遗传算法（共设计了8个算法）。本文首先提出了均衡优化问题和二次匹配的概念,然后利用可信性理论和模糊环境下机会约束规划及其相关机会规划建模的思想,在模糊环境下建立了前述各二次问题,固定费用的运输问题,多任务均衡指派问题,k-基匹配,k-基树,均衡支撑树等问题的数学模型,并讨论了特殊情况下的等价问题。为了求解这些模型,本文在详细分析了这些问题现有遗传算法的基础上,对每一个问题,都详细研究了其遗传算法。例如对多任务的均衡指派问题,设计了基于优先权的进化算子,并将这些算子推广到求解完全二部图赋权覆盖问题的遗传算法。此外,利用网络中支撑树的结构性质,采用全新的编码方式,在设计的关于求解二次支撑树问题的遗传算法中采用了基于回路的进化策略,使得设计的遗传算法完全克服了现有的求解相关问题的遗传算法求解非完备图二次支撑树问题时效率低的问题。并把设计的关于求解二次支撑树问题的遗传算法的思路推广到对k-基树问题和均衡树问题的求解。对于固定费用的运输问题,利用该问题的最优解仍然为可行域极点和基本解结构的性质,设计了基于支撑树和回路的交叉变异算子,克服了一些学者相关算法的缺点。本论文的创新点有:（1）提出了多任务均衡指派问题,均衡支撑树等均衡优化的概念和二次匹配的概念;（2）对二次指派问题和二次匹配问题,设计了基于知识的启发式遗传算法;（3）对多任务均衡指派问题,设计了基于优先权的遗传算法;（4）设计了基于回路的二次支撑树问题的遗传算法,并把这种思路推广到对k-基树问题和均衡树问题的求解;（5）对于固定费用的运输问题,设计了基于支撑树和回路的启发式遗传算法。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 选题背景及意义
• 1.2 国内外研究动向
• 1.3 本文的结构安排
• 第2章 预备知识
• 2.1 可信性理论
• 2.2 遗传算法和模糊模拟
• 2.3 图论基本知识和符号
• 第3章 指派问题及其遗传算法
• 3.1 模糊二次指派问题与模型
• 3.2 模糊二次指派问题模型的等价模型
• 3.3 模糊二次指派问题的遗传算法
• 3.4 模糊多任务的均衡指派问题
• 3.5 模糊多任务的均衡指派问题的遗传算法
• 第4章 赋权匹配问题及其遗传算法
• 4.1 二次匹配问题的基本模型
• 4.2 模糊二次匹配问题模型
• 4.3 二次最大赋权匹配问题的遗传算法
• 4.4 模糊k-基匹配问题及其遗传算法
• 4.5 模糊均衡匹配问题
• 第5章 模糊固定费用的运输问题和遗传算法
• 5.1 问题的描述和一般模型
• 5.2 模糊费用的固定费用运输问题模型
• 5.3 模糊模型的等价模型
• 5.4 固定费用运输问题的遗传算法
• 第6章 模糊树问题及其遗传算法
• 6.1 问题和基本模型
• 6.2 二次支撑树问题的遗传算法
• 6.3 k-基树问题与遗传算法
• 6.4 均衡树问题
• 第7章 结 论
• 1. 论文的主要工作
• 2. 论文的创新点
• 3. 展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果