第一章 遗传算法的基础 1
1.1 引言 1
1.1.1 遗传算法的一般结构 1
1.1.2 探索与扩展 3
1.1.3 基于种群的搜索 3
1.1.4 亚--启发式 4
1.1.5 主要优点 4
1.1.6 遗传算法词汇 5
1.2 简单的遗传算法举例 5
1.2.1 最优化问题 5
1.2.2 配词问题 11
1.3 编码问题 13
1.4 选择 15
1.4.1 采样空间 15
1.4.2 采样机理 17
1.4.3 选择概率 19
1.4.4 选择压力 22
1.5 混合遗传算法 23
1.5.1 Lamarck进化 23
1.5.2 元算法 24
1.6 遗传算法学界的重要事件 25
1.6.1 遗传算法的著作 25
1.6.2 学术会议与研讨会 26
1.6.3 遗传算法的杂志与杂志专集 28
1.6.4 互联网上公共访问的遗传算法信息 29
第二章 约束优化问题 31
2.1 无约束优化 31
2.1.1 Ackley函数 31
2.1.2 用遗传算法极小化Ackley函数 32
2.2 非线性规划 35
2.2.1 满足约束 36
2.2.2 惩罚函数 37
2.2.3 遗传运算 42
2.2.4 计算例子 45
2.3 随机优化 47
2.3.1 数学模型 47
2.3.2 Monte Carlo仿真 48
2.3.3 随机优化问题的进化程序 49
2.4 非线性目标规划 53
2.4.1 非线性目标规划的公式化 54
2.4.2 非线性目标规划的遗传算法 54
2.4.3 数值例子 56
2.5 区间规划 58
2.5.1 引言 58
2.5.2 遗传算法 62
2.5.3 数值例子 66
第三章 组合优化问题 68
3.1 引言 68
3.2 背包问题 68
3.2.1 二进制表达法 69
3.2.2 顺序表达法 70
3.2.3 变长表达法 71
3.3 二次指派问题 72
3.3.1 编码 72
3.3.2 遗传算子 73
3.4 最小生成树问题 74
3.4.1 问题的描述 75
3.4.2 树的编码 75
3.4.3 遗传算法方法 78
3.5 旅行商问题 82
3.5.1 表达 83
3.5.2 交叉算子 84
3.5.3 变异算子 88
3.6 影片递送问题 90
3.6.1 表达 90
3.6.2 遗传运算 91
第四章 可靠性优化问题 93
4.1 引言 93
4.1.1 系统可靠性的组合特性 93
4.1.2 多种失效模式的可靠性优化模型 95
4.1.3 可选设计的可靠性优化模型 96
4.2 可靠性优化的简单遗传算法 97
4.2.1 问题的表述 97
4.2.2 遗传算法与计算实例 98
4.3 冗余单元和可选设计的可靠性优化 101
4.3.1 问题的表述 101
4.3.2 遗传算法与计算实例 102
4.4 冗余混合元件的可靠性优化 106
4.4.1 问题的描述 106
4.4.2 遗传算法与计算实例 108
4.5 模糊目标和模糊约束的可靠性优化 110
4.5.1 问题的描述 110
4.5.2 遗传算法与计算实例 112
4.6 区间系数的可靠性优化 114
4.6.1 问题的描述 115
4.6.2 遗传算法 117
4.6.3 计算实例 119
第五章 流水车间调度问题 122
5.1 引言 122
5.2 两台机器的流水车间问题 123
5.3 一般m台机器流水车间问题的启发方法 124
5.3.1 Palmer启发式算法 124
5.3.2 Gupta启发式算法 124
5.3.3 CDS启发式算法 125
5.3.4 RA启发式算法 125
5.3.5 NEH启发式算法 125
5.4 Gen-Tsujimura-Kubota方法 126
5.4.1 表达方法 126
5.4.2 评估函数 126
5.4.3 交叉与变异 126
5.4.4 实例 127
5.5 Reeves方法 128
5.5.1 初始种群 128
5.5.2 遗传算子 129
5.5.3 选择 129
5.5.4 计算实例 130
5.6 Ishibuchi-Yamamoto-Murata-Tanaka方法 131
5.6.1 模糊流水车间问题 131
5.6.2 混合式遗传算法 132
5.6.3 计算实例 133
第六章 作业车间调度问题 135
6.1 引言 135
6.2 古典作业车间模型 136
6.2.1 整数规划模型 137
6.2.2 线性规划模型 138
6.2.3 图模型 139
6.3 传统启发式方法 139
6.3.1 优先分配启发式方法 140
6.3.2 随机分配启发式 141
6.3.3 瓶颈移动启发式方法 142
6.4 作业车间调度问题的遗传算法 142
6.4.1 表达方法 142
6.4.2 讨论 151
6.4.3 混合式遗传搜索 153
6.5 Gen-Tsujimura-Kubota方法 158
6.6 Cheng-Gen-Tsujimura方法 160
6.7 Falkenauer-Bouffouix方法 162
6.8 Dorndorf-Pesch方法 163
6.9 计算结果与讨论 164
第七章 机器调度问题 166
7.1 引言 166
7.1.1 单机调度问题 166
7.1.2 提前/拖期(E/T)调度问题 169
7.1.2 并行机器调度问题 171
7.2 Cleveland-Smith方法 173
7.2.1 遗传算子 173
7.2.3 选择 174
7.3 Gupta-Gupta-Kumar方法 174
7.3.1 评价函数 175
7.3.2 替代策略 175
7.3.3 收敛性策略 175
7.3.4 总体步骤 175
7.4 Lee-Kim方法 176
7.4.1 表达法 177
7.4.2 并行子种群 177
7.4.3 交叉与变异 178
7.4.4 评估与选择 178
7.4.5 并行遗传算法 179
7.5 Cheng-Gen方法 179
7.5.1 表达法与初始化 179
7.5.2 交叉 180
7.5.3 变异 181
7.5.4 确定最好交货期 183
7.5.5 评价与选择 184
7.5.6 计算实例 184
第八章 运输问题 186
8.1 引言 186
8.2 线性运输问题 186
8.2.1 LTP的描述 186
8.2.2 表达方式 188
8.2.3 遗传运算 189
8.3 双准则线性运输问题 192
8.3.1 BLTP的描述 192
8.3.2 评估 192
8.3.3 总体过程 193
8.3.4 数值实例 195
8.4 双准则三维运输问题 196
8.4.1 BSTP的描述 196
8.4.2 初始化 197
8.4.3 遗传运算 198
8.4.4 数值实例 199
8.5 模糊多准则三维运输问题 200
8.5.1 问题描述 200
8.5.2 遗传算法 201
8.5.3 数值实例 204
第九章 设备布局设计问题 206
9.1 引言 206
9.2 机器布局问题 206
9.3 单行机器布局问题 208
9.3.1 数学模型 208
9.3.2 单行机器布局问题的遗传算法 209
9.4 多行机器布局问题 211
9.4.1 数学模型 211
9.4.2 表达方式 212
9.4.3 初始化 214
9.4.4 交叉 216
9.4.5 变异 217
9.4.6 评估函数 218
9.4.7 实例 218
9.5 模糊设备布局问题 220
9.5.1 设备布局问题 220
9.5.2 模糊混和 220
9.5.3 表达方式 221
9.5.4 初始化 222
9.5.5 交叉 224
9.5.6 变异 225
9.5.7 从染色体建立一个布局 225
9.5.8 评估和选择 228
9.5.9 数值实例 229
第十章 工程设计中的选择专题 235
10.1 资源受限项目调度问题 235
10.1.1 问题描述 235
10.1.2 混和遗传算法 236
10.1.3 实例 241
10.2 模糊车辆路径与调度问题 244
10.2.1 问题描述 244
10.2.2 相关的遗传算法研究 248
10.2.3 混和遗传算法 248
10.2.4 实验结果 255
10.3 布局--分配问题 257
10.3.1 布局--分配模型 257
10.3.2 混和进化方法 258
10.3.3 数值实例 260
10.4 障碍布局--分配问题 262
10.4.1 障碍布局--分配模型 262
10.4.2 可行布局 264
10.4.3 避免障碍的最短路径 264
10.4.4 混和进化方法 264
10.4.5 实例研究 265
10.5 生产计划问题 267
10.5.1 生产计划问题描述 267
10.5.2 生产计划问题评价 268
10.5.3 例子 270
参考文献 272