用智能优化算法求解固定费用运输问题

摘要

固定费用运输问题是一种特殊的线性规划问题。与线性运输问题的特征相似，固定费用运输问题也需满足供应与需求约束，且具有运输网络特征，但固定费用的出现使得目标函数出现不连续性，从而导致其成为一个NP难问题。该问题的求解目标是在满足目的地需求的同时，分配每个源地可用供应量，以使得分配后所产生的总的变化成本和固定成本之和最小。 求解固定费用运输问题的方法很多。起初人们用一些精确算法来求解，例如切平面法，极点排列法，分枝定界法等。但这些方法被证明低效且计算费时，只适合求解较小规模问题。为了克服计算时间过长的问题，一些启发式方法被用于求解该问题，例如拉格朗日松驰法，邻近极点法等。虽然这些方法计算耗时较少，但所获得的解的质量较差。近年来，相继出现一些现代启发式遗传算法求解该问题，例如基于矩阵排列编码的遗传算法、禁忌搜索算法、利用边集编码的遗传算法等。经实验证明，它们也各有其优点与不足。 本论文的总体框架如下： 第一章简要介绍了运输问题的四个研究分支，深入分析了固定费用运输问题的背景、国内外研究现状及各类求解方法。 第二章深入讨论了智能优化算法的基本概念和定理，如标准遗传算法，免疫遗传算法等，并给出了技术路线、实现方法和研究内容。 第三章介绍了基于Prufer数编码的生成树方法，分析了它的优点与不足。 第四章提出了一种森林补充式多点交叉操作的遗传算法。为了进一步改进智能优化算法求解固定费用运输问题的性能，利用其解是运输图的一棵生成树的特性，对采用先根遍历边构成有序边集编码的生成树，提出了一种新的森林补充式多点交叉操作的启发式遗传算法。通过理论证明和不同类型和规模实验检测实验，结果表明该算法所得解的质量优于基于边集编码的遗传算法。该算法丰富了近似求解固定费用运输问题的思路。 第五章提出了一种求解固定费用运输问题的免疫遗传算法。为了进一步体现该遗传算法的性能，与基于矩阵编码的遗传算法和基于边集编码的遗传算法进行了对比，实验结果表明，免疫遗传算法的综合性能优于其他两种方法。该算法丰富了近似求解固定费用运输问题的思路。

目录

文摘

英文文摘

论文说明:图表目录

声明

第1章绪论

1.1运输问题背景

1.2国内外文献综述

1.2.1固定费用运输问题

1.2.2多目标运输问题

1.2.3容量限制的工厂选址问题

1.2.4带模糊系数的双目标运输问题

1.3小结

第2章智能优化算法

2.1最优化问题及其分类

2.1.1组合优化问题

2.1.2优化算法及其分类

2.1.3邻域函数与局部搜索

2.2计算复杂性与NP完全问题

2.2.1计算复杂性的基本概念

2.2.2 P类，NP类，NP完全类和NP难解类

2.3遗传算法

2.3.1模式定理和隐含并行性

2.3.2一般可测状态空间上遗传算法的收敛性

2.3.3收敛性分析及收敛速度估计

2.3.4遗传算法关键参数与操作的设计

2.3.5标准遗传算法的一般结构

2.4免疫遗传算法

2.4.1免疫遗传算法步骤

2.4.2免疫遗传算法收敛性

2.4.3免疫算子的机理与构造

2.5小结

第3章基于生成树的遗传算法

3.1树的表示

3.2初始化

3.3遗传运算

3.4评价与选择

3.5算法描述

3.6遗传算法的实现

3.7小结

第4章森林补充式多点交叉操作的遗传算法

4.1边集的定义和性质

4.2先根遍历边排列编码

4.3构造生成树

4.4多点交叉操作

4.5变异操作

4.6修补操作

4.7算法分析

4.8计算实验与分析

4.8.1解的质量

4.8.2平均CPU时间

4.9结论

第5章求解固定费用运输问题的免疫遗传算法

5.1种群初始化

5.1.1先根遍历边排列编码

5.1.2构造生成树

5.2交叉和变异操作

5.3修补操作

5.4接种疫苗和免疫选择

5.5免疫算子

5.6实验结果

5.7结论

结论

参考文献

致谢

附录A攻读学位期间所发表的学术论文目录