智能优化技术 适应度地形理论及组合优化问题的应用

前言
优化是一个老生常谈的问题，在军事和民用领域中都具有广阔的应用空间。现实生活中的优化问题大部分为组合优化问题，解空间大，具有组合爆炸效应等，求解难度大。因此，智能优化成为解决实际领域中组合优化问题的关键技术。
目前，智能优化算法在自身性能优化及算法融合方面依赖人工经验，对于算法参数的选择、邻域搜索策略设计等方面考虑较少，算法融合的效果也大部分依赖于后期的实验调节，缺少理论性量化的分析。另外，算法的设计与问题的耦合程度不深，借助于特定的智能优化算法框架（如差分进化算法、粒子群算法、蚁群算法等），缺乏从求解问题搜索空间角度的分析和研究。然而，正是解空间的结构决定了问题的难度，也决定了算法的搜索策略。因以调度问题为例，类似领域间调度问题的研究没有形成关联，在调度理论研究方面相对独立，虽然不同的调度问题特性不同，但彼此之间在解空间结构等方面可能存在内在的联系和相似性，需要进行深入的挖掘和探讨。
适应度地形理论旨在从优化问题解空间特性的角度出发，分析优化问题解空间地形分布特性，进而挖掘出优化问题的解空间特性，从而为了解优化问题提供技术手段，为优化问题求解以及参数控制等方面提供指导，即为解决上述问题提供一种新思路。
本书共有15章内容，分别介绍了适应度地形理论和应用。
第1章引言对本书涉及的一些基础内容进行了概述，介绍了优化问题、组合优化问题、智能优化方法以及适应度地形等内容。
第2~9章为本书的第一部分，重点介绍了适应度地形理论的主要特性以及相应的特征指标等内容，全面地探讨了适应度地形。这部分内容一方面从静态适应度地形和动态适应度地形分析两个角度探讨了地形特性；另一方面分别从时域、频域和空域三个角度探讨了地形特性。其中：第2章主要介绍了适应度地形的崎岖性以及评价地形崎岖性的定性和定量指标，反映适应度值的变化程度；第3章从中性的角度探讨了适应度地形以及评价地形中性的定性和定量指标，反映地形是否具有平原区域等特性；第4章介绍了适应度地形的可演进性以及相应的定性和定量指标，反映适应度值的进化能力；第5章探讨了适应度地形的依赖性以及相应的评价指标，衡量变量之间的相互依赖程度；第6章介绍了适应度地形的相似性以及相应的特性指标，衡量不同问题间或者同类问题间的关系；第7章利用频域分析技术探讨了适应度地形的特征，重点介绍了幅度谱、振幅变化稳定性、频域尖锐性、周期性以及平均适应度值变化程度等技术指标，将研究视角切换到频域，探讨了适应度地形的特性；第8章从地形可视化和空域分析的角度探讨了适应度地形，并详细介绍了空间映射方法等技术。第9章从动态适应度地形的角度出发，重点介绍了动态地形的分析方法，用以反映动态优化条件下的地形特征。
第10~15章为本书的第二部分，以调度问题为例重点介绍了适应度地形理论在组合优化问题中的应用。其中：第10章重点分析了调度问题，凝练一类Job-based调度问题，并阐述了其解空间的获取方法，为介绍后续章节提供了基础；第11章利用适应度地形特性指标从时域、频域和空域三个角度对调度问题的解空间特性进行了探讨；第12章基于地形分析的结果，利用调度问题间的异同性，从通用调度算法框架设计的角度进行了阐述，并给出一种通用框架体系以及相应的讨论；第13章和第14章分别从单目标优化算法设计、多目标优化算法设计和问题特性的角度出发，利用适应度地形分析结果指导算法设计，分别给出多中心变尺度优化算法、基于Pareto前沿预测等思想的调度理论，并利用适应度地形参数作为反馈量，探讨了基于适应度地形参数的适应性参数控制理论；第15章介绍了调度问题仿真平台的相关内容，在理论研究的基础上形成一体化应用平台，以便灵活扩展。本书内容覆盖适应度地形的主要内容，撰写过程中力图覆盖从理论研究到实际应用的全过程，注重实用性。
衷心感谢国家自然科学基金面向项目（61671041）、国家自然科学基金青年基金（61101153）、教育部基础科研课题、国防科工局基础科研课题和国防科工局技术基础等课题的支持。感谢IEEE Fellow史玉回教授在百忙之中认真审阅书稿，并给予了宝贵意见和建议。感谢本书所有作者的共同努力，感谢本领域相关同事和国内外同行专家、学者在本书撰写过程中给予的热心指导和宝贵建议。感谢北京航空航天大学智能仿真、通信与导航研究组全体成员。
非常希望献给读者一本适应度地形理论方面既有前沿理论又体现实际应用的好书，但由于作者水平有限，书中难免存在疏漏和不妥之处，恳请各位专家、学者和广大读者不吝指正。
路辉Email:mluhui@buaaeducn
2019年6月于北京航空航天大学

序
前言
第1章引言1
11优化问题1
12组合优化问题2
121组合优化问题的定义2
122组合优化问题的特点2
123组合优化问题的应用3
124组合优化问题的求解方法4
13智能优化方法6
131智能优化方法简介6
132智能优化方法的分类7
133典型的智能优化方法8
14适应度地形10
141适应度地形的基本概念10
142适应度地形的发展11
15本章小结14
参考文献14
第2章崎岖性18
21定义18
22NK地形19
23适应度的相关性20
24距离相关性21
25信息熵分析21
26尖锐性24
27本章小结26
参考文献26
第3章中性28
31中性随机游走28
32中性网络29
33局部最优网络30
34标准遗传距离35
35本章小结36
参考文献36
第4章可演进性38
41适应度进化肖像38
42适应度云41
43负斜率系数42
44适应度概率云44
45本章小结46
参考文献46
第5章依赖性48
51上位方差48
52位上位性50
53香农信息论50
54内/外上位性52
55本章小结54
参考文献54
第6章相似性55
61相似性指标55
62标准函数的分析56
621基本初等函数和标准测试函数适应度
地形分析56
622动态基准地形的分析59
63本章小结63
参考文献63
第7章频域分析64
71幅度谱64
711适应度地形的傅里叶分析64
712幅度谱64
713NK模型分析65
72离散时间傅里叶变换的分析66
721振幅变化稳定性66
722频域尖锐性67
723周期性67
724平均适应度值的变化程度68
725频域指标的分析68
73本章小结73
参考文献73
第8章地形可视化技术74
81分析适应度地形74
82网络可视化75
83空间地形可视化76
831空间适应度地形求解框架77
832映射策略78
833空域特征的分析80
84本章小结87
参考文献87
第9章动态适应度地形89
91定义89
92动态适应度地形的生成90
93动态适应度地形的分析工具92
931拓扑属性的分析92
932动态属性的分析94
933动态适应度地形的频域分析94
94本章小结95
参考文献95
第10章调度问题96
101Job-based类调度问题96
102数学模型的分析97
103解空间的获取方法100
1031枚举方法100
1032采样方法101
104本章小结102
参考文献102
第11章调度问题的多维度适应度地形
分析105
111时频域适应度地形的分析105
1111小规模实例的分析105
1112大规模实例的分析112
112空间适应度地形的分析115
1121特征参数的分析115
1122评价指标的对比117
113本章小结119
参考文献119
第12章一种调度算法框架120
121关键调度策略120
1211分组调度策略120
1212分配规则PBSCR122
122编码方式123
123组内优化目标124
124改进粒子群算法124
125仿真实验与结果分析126
1251求解体系应用于TTSP126
1252求解体系应用于FJSP127
1253求解体系应用于UPMSP128
126本章小结128
参考文献129
第13章单目标调度算法131
131单目标Job-based类调度问题的
分析131
1311问题特性的分析131
1312多模优化算法的分析133
132多中心变尺度优化算法133
1321多中心策略134
1322变尺度策略134
1323算法过程135
133基于适应度地形参数的适应性参数
控制135
1331评价指标136
1332奖惩机制137
134实验仿真与应用137
1341标准多模测试函数138
1342调度问题139
1343变异程度的调参实验142
1344中心点数目的调参实验145
135本章小结146
参考文献146
第14章多目标调度算法147
141多目标Job-based类调度问题的
分析147
1411问题特性的分析147
1412优化算法的分析149
142多目标Job-based类调度问题的
优化算法149
1421纯粹的“精英”策略150
1422基于缩减规模的非支配快速
排序151
1423去重策略151
1424前沿预测策略152
1425变尺度的搜索策略154
143基于多目标前沿分布的适应性参数
控制155
1431前沿分布155
1432调整策略156
144实验仿真与应用156
1441评价指标156
1442基于前沿预测多目标优化算法的
性能分析157
1443多目标变尺度搜索算法的
性能分析158
1444前沿点数目的调参161
145本章小结162
参考文献162
第15章调度问题的集成分析平台164
151需求分析164
152架构设计164
1521实例选择与产生模块165
1522适应度地形分析模块166
1523调度规划模块168
153原型平台170
154本章小结172
参考文献172