遗传算法及其在网络计划中的应用

摘  要

遗传算法(Genetic Algorithm—GA)是一种模拟自然界生物进化的搜索算法，由于它的简单易行、鲁棒性强,尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，取得了许多令人瞩目的成果，引起了广大学者和工程人员的关注。

GA是一种广为人们关注的现代优化技术，它不依赖更多的外部条件和知识便能迅速地进行全局最优搜索，由于这些优点，GA己经并且正在被应用于许多领域。本文将GA的寻优技术引入DCPM问题，实现的算法用随机搜索策略代替了传统算法中的基于领域知识的确定搜索准则，提供了一种更加通用并且简单易行的求解DCPM问题的方法。这种算法容易编程实现，另外，因为GA本身固有的并行性，在计算机系统中可以很容易地在分布式环境中处理大规模DCPM问题。

本文在第一章介绍了数据挖掘的概念，数据挖掘研究的意义以及数据挖掘常用技术和流程；第二章对数据挖掘中的典型算法--遗传算法做了详尽的介绍，包括其由来、发展，和基本原理、设计思想、特点以及改进的遗传算法；第三章介绍了网络计划的概念及其产生、发展和特点。本文在第四章以实例来说明遗传算法在网络计划中的应用。

关键词：数据挖掘  遗传算法  网络计划  DCPM 

                                    

目   次

摘  要 I

Abstract II

1  数据挖掘技术 1

1．1  数据挖掘的提出 1

1．2  数据挖掘研究的意义 1

1．3 数据挖掘定义 2

1．3．1 技术上的定义 2

1．3．2 商业上的定义 2

1．4  数据挖掘常用技术 3

1．4．1 遗传算法 3

1．4．2  人工神经网络 3

1．4．3  决策树 4

1．4．4  近邻算法 5

1．4．5  规则推导 5

1．5  数据挖掘流程 5

1．5．1  数据挖掘环境 5

1．5．2  数据挖掘过程 6

1．5．3  数据挖掘过程工作量 6

1．5．4  数据挖掘流程介绍 7

2  遗传算法 9

2．1  遗传算法的由来 9

2．1．1  引言 9

2．1．2  生物进化 10

2．2  基本遗传算法 11

2．2．1  遗传算法的发展历史 11

2．2．2  遗传算法基本术语 12

2．2．3  遗传算法的基本思想 13

2．2．4  遗传算法的基本操作 14

2．3  遗传算法的特点 16

2．3．1  遗传算法与其他搜索方法的比较 16

2．3．2  遗传算法的特点 18

2．4  标准遗传算法的改进 19

2．4．1  遗传算法中存在的问题 19

2．4．2  改进的遗传算法分类 19

2．4．3 改进的遗传算法 20

3  网络计划技术简介 22

3．1  网络计划技术的基本概念 22

3．2  网络计划技术的产生 22

3．3  网络计划技术的发展 23

3．4  网络计划的优点 24

3．5  网络计划中的问题 25

4  遗传算法在网络计划中的应用 26

4．1  CPM问题概述 26

4．2  求解DCPM问题的GA实现 28

4．2．1  遗传编码 28

4．2．2  设定控制参数，初始种群 28

4．2．3  构造适应度函数 28

4．2．4  选择机制 28

4．2．5  遗传算子设计 29

4．3  用GA求解DCPM问题的步骤 29

4．4  遗传算法求解DCPM问题的应用实例 30

5  结束语 32

5．1  主要的研究工作 32

5．2  将GA引入网络计划中的意义 32

5．3  不足与展望 32

致  谢 34

参 考 文 献 35