摘要: 遗传算法是根据生物进化的模型提出的一种优化算法。适用于在复杂空间中随机搜索，为许多传统的优化方法难以解决的优化问题提供了新的途径。自适应遗传算法是遗传算法的改进与衍生，在遗传算法的基础上，自适应的调整种群的交叉率和变异率等参数，本文先介绍基本遗传算法的研究背景、原理、特点并采用一种自适应策略来调整种群的变异率；接着针对旅行商问题和学生宿舍分配问题，论述了遗传算法在编码和适应度函数、选择、交叉算子、变异算子等方面的应用情况，并将自适应遗传算法应用在解决两个问题上，实验结果验证了自适应遗传算法在解决这两个实际问题中的有效性。

 

关键词：自适应遗传算法；旅行商问题；宿舍分配问题

 

目录

摘要

Abstract

1 绪论-1

2 自适应遗传算法（AGA）-2

2.1 基本遗传算法的流程-2

2.2 编码-3

2.2.1二进制编码方法-3

2.2.2格雷码编码法-4

2.2.3浮点编码法-4

2.3 适应度函数-5

2.4 选择算子-5

2.4.1 轮盘赌选择-5

2.4.2 锦标赛选择法-7

2.5交叉算子-7

2.5.1单点交叉算子-7

2.5.2双点交叉算子-8

2.5.3均匀交叉算子-9

2.6变异算子-9

2.7自适应策略-10

3 旅行商问题-12

3.1 引言-12

3.2 问题建模-13

3.3 编码-14

3.3.1 Adjacency representation (AR)-14

3.3.2 Ordinal representation（OR）-15

3.3.3 Path representation (PR)-15

3.4 初始化-16

3.5 适应度计算-16

3.6 选择-17

3.7 终止条件-17

3.8 交叉-17

3.9变异-19

3.9.1 随机交换几个基因的位置变异-19

3.9.2 随机交换两块基因的位置变异-19

3.9.3 随机翻转部分基因位置变异-20

3.10 自适应策略-20

3.11 实验结果-20

4学生宿舍分配问题-23

4.1 问题描述-23

4.2 编码-24

4.3 适应度计算-25

4.4 选择-25

4.5 交叉-25

4.6 变异-26

4.7自适应策略-26

4.8 实验结果-27

结    论-28

参 考 文 献-29

致    谢-30