基于遗传算法的多目标优化

基于遗传算法的多目标优化

摘    要

遗传算法作为一种有效的随机搜索方法，在优化方法中具有独特的优越性，并有着非常重要的理论意义和广泛的应用领域。

本文第一部分从遗传算法算法的基本概念、基本特点与原理、主要步骤以及应用关键等方面系统的介绍了遗传算法。通过算例分析基本遗传算法的实现步骤及优缺点，对遗传算法提出改进措施，并将其运用于考试系统，建立了基于遗传算法的组卷优化模型。

本文第二部分分析现阶段多目标优化的基本模型以及将遗传算法应用于多目标优化的可行性，建立具有乘客满意度和公交公司满意的公交调度优化模型，以此作为多目标优化问题。在此基础上，建立基于遗传算法的公交调度模型，在编码方案和遗传操作等方面提出创新点，并设计公交调度优化模型流程图。最后，通过改进的选择、交叉、变异操作确定最优发车数量和各时段最优发车间隔时间，实现了公交调度优化方案。

关键字：遗传算法；组卷模型；多目标优化；公交调度优化

目 录

中文摘要 ……………………………………………………………………………………………… i

英文摘要 ………………………………………………………………………………………………ii

目 录………………………………………………………………………………………………… iii

第一章  前言 1

1.1  论文研究的背景和意义 1

第二章  遗传算法概述 2

2.1  遗传算法的基本概念以及特点 2

2.1.1  遗传算法的基本概念 2

2.1.2  遗传算法的特点 2

2.1.3  遗传算法的若干应用 3

2.2  遗传算法的基本原理和基本步骤 3

2.2.1  遗传算法的基本原理 3

2.2.2  遗传算法的主要步骤 3

2.2.3  遗传算法的应用关键 5

2.2.4  遗传算法与传统方法的比较 6

2.3  遗传算法的应用实例 7

2.3.1  方案表示 7

2.3.2  种群初始化 8

2.3.3  适应度函数 8

2.3.4  遗传操作 8

2.3.5  参数设定及结果分析 9

第三章  遗传算法改进策略 13

3.1  初始种群的产生 13

3.2  选择算子的改进 13

3.3  交叉和变异概率的改进策略 13

第四章  遗传算法在组卷系统中的应用 15

4.1  组卷系统数学模型 15

4.2  组卷模型的实现方法 16

4.2.1  试题编码及种群初始化 16

4.2.2  适应度函数设计 16

4.2.3  操作算子设计 17

4.2.4  终止条件 19

第五章  多目标优化问题的若干基础 20

5.1  多目标优化问题的数学模型 20

5.2  多目标优化问题的偏好结构 21

5.3  遗传算法应用于多目标优化问题的分析 21

5.4  求解多目标问题的遗传算法 22

5.5  多目标问题约束条件处理方法分析 23

第六章  基于遗传算法的公交调度优化设计 24

6.1  模型的假设 24

6.2  乘客满意度模型 24

6.3  公交公司满意度模型 26

6.4  公交调度优化模型 27

6.5  遗传算法在公交调度中的运用 27

6.5.1  编码方案及种群初始化 27

6.5.2  适应度函数 28

6.5.3  遗传操作设计 28

6.5.4  交叉概率和变异概率的自适应调整 30

5.5.5  算法的参数及其终止条件 32

6.5.6  模型总结 32

第七章  总结 33

致  谢 34

参考文献 35

附  录 36