基于状态转移的组合优化方法PDF电子书下载

第1章 概述 1

1.1 最优化问题及其分类 1

1.1.1 函数优化问题 2

1.1.2 组合优化问题 3

1.2 优化方法 4

1.3 邻域、计算复杂性与NP 7

1.3.1 邻域 7

1.3.2 计算复杂性 9

1.3.3 P、NP、NP-hard与NPC 10

1.4 近似求解方法及其评价 11

1.4.1 近似求解方法 11

1.4.2 基于目标函数值的评价方法 12

1.4.3 基于计算时间的评价方法 13

1.4.4 近似方法的综合评价 14

第2章 函数优化方法 16

2.1 凸集与凸函数 16

2.1.1 凸集 16

2.1.2 凸函数 17

2.2 线性规划 19

2.2.1 线性规划问题及其数学模型 19

2.2.2 基本概念 21

2.2.3 线性规划问题的解的特点 22

2.2.4 单纯形法 22

2.3 一维搜索方法 25

2.3.1 0.618法 26

2.3.2 二分法 27

2.3.3 插值法 28

2.3.4 五点法 31

2.4 无约束函数优化方法 33

2.4.1 梯度法 34

2.4.2 共轭梯度法 34

2.4.3 变尺度法 35

2.4.4 步长加速法 36

2.5 有约束函数优化方法 37

2.5.1 最优性条件 38

2.5.2 二次规划 40

2.5.3 可行方向法 41

2.6 动态规划方法 42

2.6.1 基本概念 42

2.6.2 最优性原理与动态规划的基本方程 44

第3章 组合优化方法 48

3.1 启发式方法 48

3.1.1 一步启发式方法 48

3.1.2 重复迭代搜索方法 50

3.1.3 常用的启发式策略 51

3.2 模拟退火 57

3.2.1 模拟退火的起源 57

3.2.2 模拟退火算法 57

3.2.3 模拟退火算法的关键问题 60

3.3 禁忌搜索 62

3.3.1 禁忌搜索的思想起源 62

3.3.2 禁忌搜索算法 62

3.3.3 禁忌搜索算法的关键问题 63

3.4 遗传算法 65

3.4.1 遗传算法的起源 65

3.4.2 遗传算法及其基本原理 66

3.4.3 遗传算法的关键问题 71

3.5 粒子群算法 74

3.5.1 粒子群算法的起源 74

3.5.2 原始粒子群算法 75

3.5.3 标准粒子群算法 77

3.5.4 粒子群算法的关键问题 78

3.6 神经网络方法 79

3.6.1 绪言 79

3.6.2 Hopfield神经网络 82

3.6.3 弹性网络 86

3.7 混合优化算法 88

第4章 基于状态转移的组合优化方法 91

4.1 基于状态转移的组合优化方法的起源与发展 91

4.1.1 基于状态转移的组合优化方法的起源 91

4.1.2 基于状态转移的组合优化方法研究与发展 93

4.2 基于状态转移的组合优化方法的概念与思想 94

4.2.1 基于状态转移的组合优化方法的基本概念 94

4.2.2 基于状态转移的组合优化方法的基本思想 98

4.2.3 基于状态转移的组合优化方法的主要内容 100

4.3 问题分类方法 100

4.4 定界算法 102

4.4.1 线性规划松弛方法 103

4.4.2 代理松弛方法 104

4.4.3 拉格朗日松弛算法 105

4.4.4 删除约束方法 106

4.4.5 小结 107

4.5 降维方法 108

4.5.1 利用当前最优解与上界（下界）相比较的降维方法 108

4.5.2 利用元素间的关系进行降维 109

4.5.3 基于特征值的降维方法 110

4.5.4 把问题分解成多个子问题的降维方法 111

4.5.5 基于推理的降维方法 113

4.5.6 基于评价函数的降维方法 115

4.5.7 小结 116

4.6 改进近似解的方法 117

4.6.1 改进近似解的方法 118

4.6.2 获取较好的近似求解方法、定界算法的一般思路 119

4.7 精确求解方法 120

4.7.1 网络方法 120

4.7.2 深度优先搜索方法 122

4.7.3 广度优先搜索方法 124

4.7.4 启发式规则与深度优先搜索方法、广度优先搜索方法结合的方法 124

4.7.5 启发式深度-广度优先搜索方法 125

4.7.6 小结 129

第5章 同顺序加工调度问题的求解方法 130

5.1 引言 130

5.2 三机床同顺序加工调度问题的下界 131

5.3 三机床同顺序加工调度问题的近似求解方法 134

5.3.1 选择后续工件应考虑的因素 134

5.3.2 选择后续工件的评价函数 136

5.3.3 参数调整 137

5.3.4 解的评价 138

5.3.5 三机床同顺序加工调度问题的求解步骤与计算量 138

5.3.6 实验结果 139

5.4 一般同顺序加工调度问题的近似求解方法 141

5.4.1 三机床同顺序加工调度问题的求解方法的推广 141

5.4.2 NEH方法 142

5.4.3 使用迭代改进方法时初始解对解的影响 143

5.4.4 同顺序加工调度问题的问题求解的近似方法 144

5.4.5 实验结果 146

5.4.6 小结 148

5.5 同顺序加工调度问题的精确求解方法 148

5.5.1 求解同顺序加工调度问题的启发式广度-深度优先搜索方法 148

5.5.2 加工总时间的计算 149

5.5.3 求解同顺序加工调度问题的启发式双侧广度优先搜索方法 150

5.5.4 实验结果分析 152

5.6 小结 154

第6章 0/1背包问题的精确求解方法 156

6.1 引言 156

6.2 0/1背包问题的上界算法 157

6.2.1 求取物品价值与重量强线性相关的0/1背包问题的上界算法 158

6.2.2 线性松弛方法 158

6.2.3 求取物品价值与重量线性相关的0/1背包问题的上界算法 159

6.2.4 求取第二类背包问题的上界算法 160

6.3 简化方法 174

6.3.1 降维方法 175

6.3.2 改善近似解的方法 178

6.3.3 简化0/1背包问题的步骤 179

6.4 0/1背包问题的精确求解方法 179

6.5 实验结果 182

6.6 小结 184

第7章 旅行推销员问题求解方法 185

7.1 引言 185

7.2 旅行推销员问题的特点 186

7.3 最小1-树与旅行推销员问题 187

7.3.1 最小1-树与旅行推销员问题的下界 187

7.3.2 基于最小1-树的权值矩阵变换方法 188

7.3.3 基于最小1-树的初始解 191

7.4 边对权值 192

7.4.1 α-度量 192

7.4.2 边对与边对权值 194

7.5 旅行推销员问题的近似求解方法 197

7.5.1 近邻法 197

7.5.2 加权法 198

7.5.3 LKH算法 200

7.5.4 MLKH方法 202

7.5.5 基于边对权值的旅行推销员问题求解方法 203

7.6 降维方法 204

7.6.1 基于特征值的降维方法 205

7.6.2 基于推理的降维方法 205

7.6.3 基于下界的降维方法 208

7.6.4 基于问题分解的降维方法 209

7.7 旅行推销员问题的精确求解方法 209

7.8 小结 212

第8章 武器-目标分配问题求解方法 213

8.1 引言 213

8.2 静态武器-目标分配问题求解方法 214

8.2.1 静态武器-目标分配问题的定界算法 215

8.2.2 静态武器-目标分配问题求解的仿真方法 218

8.2.3 静态武器-目标分配问题求解的启发式方法 223

8.3 坦克战中武器-目标分配问题求解方法 227

8.3.1 坦克战中武器-目标分配问题 227

8.3.2 坦克战中动态武器-目标分配问题的求解方法 232

8.3.3 动态武器-目标分配问题求解步骤 234

8.3.4 实验结果分析 235

8.3.5 小结 236

8.4 目标选择方法 237

8.4.1 目标优先权的确定 237

8.4.2 只考虑对方威胁的目标选择方法 240

8.4.3 考虑命中概率、目标毁伤情况和对方威胁的目标选择方法 243

8.4.4 目标选择模型求解方法 244

8.4.5 小结 251

8.5 坦克作战中的弹药选择模型 251

8.5.1 坦克战中弹药选择的依据 252

8.5.2 弹药选择过程的量化 253

8.6 小结 255

参考文献 256