摘  要: 计算机的飞速发展一方面促进了优化方法的不断发展，另一方面也使优化问题变得越来越复杂。其中，任务 问题是一种比较典型的 问题，它属于 难问题，而且计算 度很高。1991年， 等人提出的一种 的仿生优化 ——蚁群算法，它属于随机搜索算法。 适用于求解各种不同 的 问题，但是还存在很多不足。本文介绍了 及其改进的 算法，并利用 优化算法求解 问题，如 路径优化问题。针对 易陷入 的不足,提出了一种混合 ,该算法将 嵌入 优化算法,计算结果表明，这样的改进提高了蚁群优化算法的优化能力。75694

毕业论文关键词：组合优化，优化算法，蚁群算法，混合算法

Abstract: The rapid development of computer boosts the continuous development of optimization methods。 On the other hand, it complicates optimization problem。 The task allocation problem is a kind of typical combinatorial optimization problem。 This problem belongs to the class of NP-hard problem and is categorized by computational complexity。 Ant colony algorithm is a novel bionic optimization algorithm proposed by M。Dorigo et al in 1991, which belongs to the random search algorithm。 Ant colony algorithm is applied to solving a variety of combinatorial optimization problems。 However, there are also many shortcomings。 This paper is introduced the ant colony algorithm and its improved intelligent optimization algorithm。 What’s more, it also includes solving the task assignment problem like the distribution route optimization problem by using ant colony optimization。 Aiming at the shortage of the ant colony optimization algorithm which is easily trapped into local optimum, this paper put forward a kind of hybrid algorithm which combined ant colony optimization algorithm with genetic algorithm。 The calculation results show that this improvement enhance optimization ability of the ant colony optimization algorithm。

Key words: combinatorial optimization, optimization algorithm, ant colony algorithm,hybrid algorithm

目  录

1 绪论4

1。1 研究背景4

1。2 研究目的与意义5

1。3 课题内容介绍5

2 蚁群算法6

2。1 蚁群算法的背景信息6

2。2 蚁群算法的原理6

2。3 蚁群算法的结构框架7

2。4 蚁群算法的算法实现9

2。5 蚁群优化算法的优点与不足10

3 蚁群算法的改进11

3。1 精英蚂蚁系统11

3。2 最大—最小蚂蚁系统11

3。3 排序蚂蚁系统12

3。4 基于遗传学的改进蚁群算法研究12

3。5 混合算法的应用13

4 蚁群算法与其改进算法的比较14

4。1 蚁群算法与改进算法的异同14

4。2 蚁群优化算法的应用15

4。2。1 旅行商问题15

4。2。2 二次分配问题16

4。2。3 车间任务调度问题17

4。2。4