基于智能计算的最优指派问题求解技术及其应用研究

摘要

最优指派问题是运筹学中的经典问题，在生产调度、运输规划、物流管理、决策系统支持建立等方面有着广泛的应用。本文以求解最优指派问题及其扩展问题为目标，以遗传算法和粒子群优化算法为求解手段，提出了新的求解算法，并用以解决了机器人足球决策系统中若干关键问题。 讨论了标准最优指派问题的一般定义和数学模型；根据实际需要，对最优指派问题进行了推广；并在分析“匈牙利”算法原理和求解步骤的基础上，说明了该算法存在的不足。 设计了一种基于改进遗传算法的最优指派问题求解算法。算法引进精英交叉策略和交叉、变异概率的全局自适应引导方法，使得进化过程具有良好的导向性。使用一般最优指派问题和“匈牙利”算法难以收敛的典型最优指派问题，对该算法进行测试，并与自适应遗传算法进行性能对比，结果表明了算法具有更好的收敛性，更快的求解速度。 提出了一种基于粒子群优化的最优指派问题求解算法。在总结粒子群优化算法及其各种改进的基础上，结合基于排列组合的最优指派问题描述，以经典的速度一位移模型为参照，针对最优指派问题的离散性和特殊性，重新定义了粒子的位置和速度，建立了相应的速度和位移的更新机制，并给出了保证种群多样性的改进。实验表明，该算法不但对一般类型最优指派问题有良好的适应性和有效性，且应用于较大规模的最优指派问题亦能取得理想效果，且在整体性能上优于上述改进遗传算法。 针对现有机器人足球决策系统中阵型选择环节和角色分配环节存在的不足，从阵型确定和阵型执行两个层面上，给出了阵型复合和全局角色分配方法，并用上述粒子群优化算法予以求解，从而解决了阵型的稳定性和连续性问题。 综合应用上述研究成果，设计并实现了行之有效的仿真 11VS11机器人足球决策系统。该决策系统代表武汉工程大学参加了多次国内外机器人足球比赛，取得了良好成绩。实践证明，该决策系统较好的满足了 FIRA 机器人足球仿真 11VS11 比赛的需要。

目录

文摘

英文文摘

声明

第1章绪论

1.1最优指派问题简介

1.2遗传算法概述

1.2.1遗传算法简介

1.2.2遗传算法的研究现状

1.3粒子群优化算法概述

1.3.1粒子群优化算法简介

1.3.2粒子群优化算法的研究现状

1.4机器人足球及其决策系统

1.4.1机器人足球简介

1.4.2 FIRA机器人足球仿真比赛

1.4.3机器人足球决策系统

1.5本文的主要工作

第2章最优指派问题

2.1标准最优指派问题

2.2 OAP的推广问题之一

2.2.1推广问题之一的描述

2.2.2推广问题之一的转化思路

2.3 OAP的推广问题之二

2.3.1推广问题之二的描述

2.3.2推广问题之二的转化思路

2.4 OAP的推广问题之三

2.4.1推广问题之三的描述

2.4.2推广问题之三的转化思路

2.5 OAP的经典求解方法及其不足

2.6本章小结

第3章基于改进遗传算法的最优指派问题求解

3.1个体和种群的设计

3.1.1编码方式

3.1.2初始种群的生成

3.1.3适应度函数的设计

3.2遗传操作的设计

3.2.1选择操作

3.2.2交叉操作

3.2.3变异操作

3.3交叉概率和变异概率的自适应算法

3.4算法测试与分析

3.4.1一般OAP求解

3.4.2 HA不收敛的OAP求解

3.4.3与AGA的性能比较

3.4.4实验结论与分析

3.5本章小结

第4章基于改进粒子群优化算法的最优指派问题求解

4.1 PSO的基本原理

4.1.1 PSO算法的一般求解过程

4.1.2基本PSO算法的数学描述

4.1.3基本PSO算法的流程

4.1.4基本PSO算法的分析

4.2基本PSO算法的改进

4.2.1引入惯性因子的PSO改进算法

4.2.2引入收敛因子的PSO改进算法

4.2.3动态系统下的PSO改进算法

4.2.4经典PSO算法模型及其参数集

4.3基于PSO的OAP求解算法设计

4.3.1基于排列组合的OAP模型

4.3.2变量的定义

4.3.3基本运算操作的定义

4.3.4位置和速度的更新机制

4.3.5保证种群多样性的改进

4.4算法测试与分析

4.4.1一般OAP求解

4.4.2 HA不收敛的OAP求解

4.4.3与改进遗传算法的性能比较

4.4.4实验结论与分析

4.5本章小结

第5章机器人足球比赛中的最优指派问题及其应用

5.1基于最优指派的阵型复合

5.1.1问题的提出

5.1.2基于最优指派的求解

5.2基于最优指派的动态角色分配

5.2.1问题的提出

5.2.2 基于最优指派的求解

5.3基于动态角色分配的决策系统设计

5.3.1以球为中心的区域划分

5.3.2态势分析

5.3.3阵型确定

5.3.4动态角色分配

5.3.5角色执行

5.4决策系统的软件实现

5.5决策系统的测试及效果

5.6本章小结

结论

附录A

参考文献

攻读硕士学位期间发表或完成的论文

攻读硕士学位期间参与项目及所获奖励情况

致谢