商品详情
书名：差分演化算法的理论与应用
定价：95.0
ISBN：9787030527363
作者：熊盛武，胡中波，苏清华
版次：31
出版时间：2017-06
内容提要：
全书内容分为差分演化算法（以下简称算法）的理论与应用两篇。理论篇主要内容包括算法的不确保依概率收敛性的理论分析、算法依概率收敛的充分条件、改进算法的收敛性分析、辅助算法收敛的子空间聚类算子的设计。应用篇主要内容包括收敛算法在螺旋压缩弹簧参数优化问题中的应用、算法在薄膜太阳能电池抗反射层微结构设计和在彩色图像颜色量化问题优化中的应用。
目录：
目录
《信息科学技术学术著作丛书》序
前言
第1章 绪论 1
1.1 引言 1
1.2 差分演化算法 2
1.3 差分演化算法理论研究概述 4
1.3.1 差分演化算法算子的搜索机理 5
1.3.2 差分演化算法的渐近收敛性 5
1.3.3 差分演化算法的计算复杂度 6
1.3.4 依概率收敛的差分演化算法设计 6
1.4 差分演化的算法改进研究概述 7
1.4.1 差分演化算法控制参数的设置研究 7
1.4.2 差分演化算法的演化算子改进研究 10
1.5 差分演化算法在工程应用领域的研究概述 12
参考文献 14
**篇 差分演化算法的收敛性理论与收敛算法设计
第2章 差分演化算法的不确保依概率收敛性 31
2.1 相关差分演化算法收敛性结论的分析 31
2.2 基于马尔可夫链的差分演化算法收敛性分析 33
2.2.1 相关定义与定理 33
2.2.2 连续解空间的离散化 34
2.2.3 差分演化算法的马尔可夫链建模 35
2.2.4 基于马尔可夫链的差分演化算法收敛性证明 35
2.3 基于随机漂移模型的差分演化算法收敛性分析 37
2.3.1 差分演化算法的随机漂移建模 37
2.3.2 线性欺骗函数的构造 38
2.3.3 基于随机漂移模型的差分演化算法收敛性证明 40
2.4 一类让经典DE算法不能确保收敛的函数 42
2.4.1 函数的结构特征分析 43
2.4.2 数值实验分析 45
2.4.3 函数难优化的缘由分析 46
2.5 本章小结 48
参考文献 48
第3章 差分演化算法依概率收敛的充分条件 50
3.1 充分条件的推理 50
3.2 充分条件的注记 52
3.3 几个差分演化算法的收敛性分析 52
3.3.1 DE-RW算法的收敛性证明 52
3.3.2 CCoDE算法的收敛性证明 54
3.3.3 msDE算法的收敛性证明 57
3.4 本章小结 59
参考文献 59
第4章 差分演化算法的依概率收敛模式及辅助算子 60
4.1 一个依概率收敛的差分演化算法模式 60
4.2 辅助差分演化算法收敛的常用繁殖算子 61
4.2.1 均匀变异算子 61
4.2.2 高斯变异算子 62
4.3 常用繁殖算子的辅助效率测试 63
4.3.1 实验设计与实验参数设置 64
4.3.2 实验结果与分析 64
4.4 本章小结 77
参考文献 77
第5章 依概率收敛差分演化算法的辅助算子设计 78
5.1 子空间聚类算子 78
5.1.1 子空间聚类算子的概率分析 79
5.1.2 子空间聚类算子的统计分析 82
5.1.3 子空间聚类算子的程序实现 84
5.2 一类基于子空间聚类算子的收敛差分演化算法 85
5.3 算法的收敛性证明 86
5.4 数值实验分析 88
5.4.1 测试函数集 88
5.4.2 实验设计与参数设置 89
5.4.3 实验结果与分析 91
5.5 本章小结 106
参考文献 106
第二篇 差分演化算法的应用
第6章 依概率收敛差分演化算法在螺旋压缩弹簧参数优化中的应用 109
6.1 螺旋压缩弹簧参数优化问题的模型建立 109
6.2 面向CCS优化设计的子空间聚类差分演化算法 111
6.2.1 面向CCS优化设计的罚函数约束处理技术 111
6.2.2 CCS优化中混合变量的处理技术 112
6.3 实验设计与结果分析 112
6.4 本章小结 114
参考文献 115
第7章 薄膜太阳能电池抗反射层微结构设计与优化 116
7.1 薄膜太阳能电池抗反射层研究现状 116
7.2 梯度氮化硅/氮氧化硅结构的光捕获设计与优化 119
7.2.1 优化模型 119
7.2.2 单因素分析 121
7.2.3 基于差分演化算法的设计与优化 124
7.2.4 与纳米粒子结构的性能比较 128
7.3 多层梯度抗反射层结构设计与优化 130
7.3.1 优化模型 131
7.3.2 基于差分演化算法的优化与设计 132
7.3.3 与纳米粒子结构的性能比较 135
7.4 介质纳米粒子与多层抗反射层的光捕获性能比较 138
7.4.1 介质纳米粒子的等效模型 138
7.4.2 与多层抗反射层比较 141
7.5 石墨烯透明导电薄膜光捕获结构设计与优化 143
7.5.1 优化模型 144
7.5.2 基于差分演化算法的优化与设计 146
7.6 本章小结 150
参考文献 151
第8章 彩色图像颜色量化问题的优化与算法参数设置 153
8.1 彩色图像颜色量化问题的优化方法发展现状 153
8.2 彩色图像颜色量化的基本优化策略 155
8.2.1 基于基本差分演化算法的彩色图像颜色量化优化策略 155
8.2.2 彩色图像颜色量化基本优化策略的参数设置 172
8.3 彩色图像颜色量化的混合优化策略 173
8.3.1 彩色图像颜色量化优化模型的元素置换等效性 173
8.3.2 混合策略 173
8.3.3 彩色图像颜色量化的混合差分演化算法 174
8.3.4 数值实验 176
8.3.5 实验结果分析 177
8.4 本章小结 183
参考文献 184
第9章 彩色图像颜色量化问题的自适应优化方法 185
9.1 差分演化算法参数的自适应化 186
9.2 彩色图像颜色量化的混合自适应差分演化算法 186
9.3 数值实验 188
9.4 实验结果分析 194
9.5 彩色图像颜色量化自适应混合优化策略在数字油画制作软件中的应用 194
9.6 本章小结 195
参考文献 196
附录 198
在线试读：
第1章 绪论
1.1 引言
人工智能（artificial intelligence，AI）是创造智能机器的科学与工程［1］，计算智能（computational intelligence，CI）是实现人工智能的技术与方法［2］，基于自然精神的算法是计算智能的主要组成部分，包括神经网络（neural networks）、模糊系统（fuzzy system）和演化计算（evolutionary computation，EC）等。演化计算方法又分为群体智能算法（swarm intelligence algorithms）和演化算法（evolutionary algorithms），典型的演化算法有遗传算法（genetic algorithm，GA）、遗传程序设计（genetic programming，GP）、演化策略（evolution strategy，ES）、演化规划（evolution programming，EP）和差分演化（differential evolution，DE）算法等。
差分演化算法［3］是Storn和Price 1995年为求解切比雪夫多项式拟合问题提出的一种基于演化机理的随机搜索算法。国内一般有差分演化算法、差分进化算法和差异进化算法等三种称谓。近20年的数值模拟与工程应用研究表明，差分演化算法是*强有力的智能计算方法之一。
差分演化算法具有优化效果稳健、控制参数少、易于编程实现等优点，自提出以来迅速引起了众多学者关注。2005年Springer出版差分演化算法的**本专著Differential Evolution:A Practical Approach to Global Optimization［4］。2007～2009年，汤姆森科技信息集团的科学引文检索收录有关差分演化算法的文章不少于3964篇［5］。 2011年2月，IEEE Transaction on Evolutionary Computation出版了一期差分演化算法的专辑。目前，该算法已经被应用到了组合优化［6］、多目标优化［7］、函数优化［8］和图像颜色量化［9］等二十多个领域，算法源码已经被包含在诸如Built in optimizer in MATHEMATICA′s function Nminimize(since version 4.2)，MATLAB′s GA toolbox contains a variant of DE，Digital Filter Design，Diffraction grating design，Electricity market simulation，Auto2Fit，LMS Virtual Lab Optimization，Optimization of optical systems，Finite Element Design，LabView，Microwave Office 10.0 by AWR Corp.和OPTIMUS等12个应用软件包中［10］。
众多比较性数值模拟与应用研究表明，差分演化算法是*强有力的随机优化算法之一。文献［11］应用34个测试函数，比较了差分演化算法、粒子群算法、一个改进的粒子群算法［12,13］（attractive and repulsive PSO，arPSO）和基本演化算法［14］（simple evolutionary algorithm，SEA）的性能，比较结果显示差分演化算法的整体性能优于被比较的其他三个算法。文献［15］运用差分演化算法和遗传算法优化给排水系统，在6个案例上的数值实验结果表明差分演化算法能得到更好的优化效果。文献［7］比较了差分演化算法和模拟退火算法（simulated annealing，SA）在辐射传递问题上的优化效果，结果表明差分演化算法和模拟退火算法都能得到较好的优化结果，但是差分演化算法相对模拟退火算法更稳健。
在历届演化优化的国际竞赛（international contest on evolutionary optimization,ICEO）中，差分演化算法是**的在每届比赛中都表现优异的算法［5］。在1996年的**届ICEO竞赛中，差分演化算法虽然只获得第三名［16,17］，但却是表现*好的演化算法（排名在前两位的是非智能算法）。接下来，在1997年的第二届ICEO竞赛中，差分演化算法获得**名［17,18］，数值实验结果表明差分演化算法是所有参赛算法中表现*优异的。表1.1给出了自2006～2013年各届ICEO竞赛的结果，表中“-V”表示基于某算法的改进算法。由此可见，ICEO的测试数据集包括约束与无约束的单目标优化、约束与无约束的多目标优化、大规模单目标优化和动态优化等。在这些数据集上，差分演化算法或者差分演化算法的改进算法（differential evolution variants，DE-V）是**一个能够一直排名前五的演化计算方法。差分演化算法是当前*有影响力的演化计算方法之一［19-22］。
表1.1历届演化计算国际竞赛（ICEO2006～2013）排名前五的算法
注：“-V”表示基于某算法的改进算法，“Other”表示非演化计算方法。
1.2 差分演化算法
差分演化算法常被用来求解连续优化问题，不失一般性，*小化边界约束连续优化问题的形式化表达式为
（1.1）
其中，RD是D维搜索空间；是解空间，Uj和Lj分别是xj的上下界。
记该问题的*优解是*，*优解集是B*。除非特别说明，接下来的讨论将基于上述*小化问题展开研究。
差分演化算法的基本思想是运用当前种群个体的差来重组得到中间个体，即实验个体（trail individual），然后运用父子个体适应值竞争来获得新一代个体。差分演化算法是*典型的演化算法之一，与其他演化算法类似，算法通过变异、交叉和选择等三步的循环来达到寻优目的。算法流程如下。
Step1，（初始化） 初始化种群规模（population size,N）、个体维数（individual dimension,D）、变异因子（mutation factor,F）、交叉概率（crossover probability,CR）、初始化种群Xt=(t1,t2,…,tN)。这里迭代次数t=0，表示第0代的初始化种群；ti,i=1,2,…,N表示第t代的第i个个体，每个个体都是D维向量。
Step2，（变异） 算法通过变异操作为每个个体产生一个对应的捐助向量v（donor vector），*常用的5个变异操作如下。
**，DE/rand/1：
第二，DE/best/1：
第三，DE/current-to-best/1：
第四，DE/best/2：
第五，DE/rand/2：
其中，ti，i=1,2,…,N是第t代种群中的第i个个体，称为目标向量（target vector）；r1,r2,…,r5是1～N中不等于i的相异的随机整数；tbest是第t代种群中的*优个体；变异因子F是经验参数，一般在区间(0,1］上取值。
Step3，（交叉） 算法通过目标向量和捐助向量之间的交叉操作为每个目标个体产生一个实验向量u，差分演化算法经典的交叉操作有指数交叉（exponential crossover）和二项式交叉（binomial crossover），*常用的二项式交叉可以表示为
其中，j=1,2,…,D；CR是算法的第二个经验参数，一般在(0,1)上取值；rand(0,1)是在［0,1］上服从均匀分布的随机数；jrand是1和D之间的一个随机整数，保证至少在某一维上实施交叉操作。
Step4，（选择） 差分演化算法通过在目标向量和实验向量之间实施贪婪的选择操作来产生下一代种群，选择操作（针对*小化问题）可表示为
这里f(·)是*小化问题的目标函数值。
Step5，（终止） 循环执行Step2～Step4，直至达到设定的循环终止条件，输出*优结果。常用的终止条件有两个：一是设定*大迭代次数，二是设置精度水平。
算法注解。
① 差分演化算法*具特色的是它自适应的变异操作。在演化的初期阶段，因为种群中个体的差异较大，因此用来作为变异扰动的差向量也较大，个体的扰动就较大，有利于算法的全局搜索；随着演化的进行，当算法趋于收敛的时候，种群中个体的差异随之较小，因此用来变异扰动的差向量也随之自适应地变小，较小的扰动有利于算法的局部搜索。正是这种简单又独具特色的变异操作有效地平衡了差分演化算法的全局搜索能力和局部搜索能力。需要注意的是，差分演化算法的变异操作对于搜索空间是不封闭的，即变异后得到的捐助向量可能会溢出搜索空间。周期模式（Periodic Mo差分演化）是常用的处理方法之一，即
其中，“%”是“求余”运算。
② 相对其他演化算法，差分演化具有算法简单、易于实现的优点。
③ 差分演化算法仅有三个经验控制参数，即种群规模N、变异因子F和交叉概率CR。算法的表现对参数的设置是敏感的，针对其中两个关键控制参数F和CR，已经研究出了较多简单有效的自适应（或者适应）控制方法。
④ 相对其他有竞争力的同类算法，较小的空间复杂度是差分演化算法的另一个优势，如协方差矩阵自适应进化策略（covariance matrix adaptation-evolution strategy，CMA-ES）。在不高于100维的优化问题上，CMA-ES表现出很强的竞争力，但是在更高维的大规模优化问题上，空间复杂度的优势让差分演化算法表现出更强的可拓展性。
1.3 差分演化算法理论研究概述
随着差分演化算法在数值模拟和众多工程应用领域的成功，越来越多的学者开始关注差分演化算法的理论研究。演化计算方法的理论研究是一个研究的难点，差分演化算法的理论研究更是进展缓慢。接下来，从算子搜索机理、算法渐近收敛性、算法复杂度和收敛算法设计等四个方面介绍当前的理论研究成果，然后分析在该领域可能存在的研究空间。
1.3.1 差分演化算法算子的搜索机理
差分演化算法是典型的演化算法之一，与传统的遗传算法类似，通过循环执行变异、交叉和选择操作来实现种群的逐步优化，算子搜索能力的强弱直接影响算法的整体优化性能。算子的搜索能力可分为全局搜索（globalexploration）能力和局部搜索（localexploitation）能力，全局搜索能力可由种群的多样性反映，种群的多样性又可由种群的方差反映。沿着这一研究思路，Zaharie应用基于统计量的方法从理论上研究了差分演化算法的算子搜索机理。
2001年，Zaharie［67］研究了差分演化算法的变异算子、交叉算子和种群方差的数学期望之间的关系，进而推演得到种群方差的数学期望与变异因子、交叉概率之间的函数关系，并证明差分演化算法（不含选择操作）的种群方差比演化策略的大，即种群多样性比演化策略的好，这也从某种程度上解释了差分演化算法在数值模拟上表现优越的内在原因。在此基础上，2002年Zaharie［68］进一步从理论上探讨了参数的取值与算法早熟之间的关系；进而，Zaharie［69］给出一种基于上述理论研究的自适应参数策略，该策略通过控制种群方差来控制种群的多样性。2008年，Zaharie［70］提出一个不使用经典差运算算子的变异操作，并从理论上证明该算子对种群方差与经典变异算子和交叉算子有等同的影响力。同时，也对二进制差分演化的种群分布做了初步的分析。
差分演化算法的交叉算子*常用的有二项式交叉（bionomial crossover）和指数型交叉（exponential crossover）。Zaharie［71,72］从理论上分析了差分演化算法交叉算子和交叉概率对算法行为的影响。理论和实验的研究结果表明，相对于常用的二项式交叉而言，指数型交叉对问题的规模更敏感，且两个交叉算子对差分演化算法行为的影响主要是通过控制变异组件来实现的。
与Zaharie基于统计量研究思路不同，Dasgupta等［73］建立了差分演化算法的动力系统模型，论证了差分演化算法搜索过程有梯度下降特征，并应用模型研究了差分演化的收敛速度与变异因子、交叉概率的相关性，进而应用李雅普诺夫稳定性定理（Lyapunov’s stability theorems）分析了差分演化算法的稳定性。
胡中波和熊盛武等［74］从代数系统是否同构的角度在理论上证明了DE算法不适合与Koziel［75］的约束处理映射相结合，而遗传算法却适合与该约束处理映射相结合。该结论从理论上论证了差分演化算法和遗传算法搜索机理的差异。
1.3.2 差分演化算法的渐近收敛性
2005年，Xue等［76］简化基本差分演化算法，只考虑算法的变异和交叉操作，假设初始种群符合正态分布，建立了连续的多目标差分演化算法的数学模型，并证明在初始种群中包含问题的帕累托（Pareto）*优解的前提下，算法能够收敛到帕累托*优解。同年，Xue等［77］把上述工作推广到离散的多目标差分演化模型中，得到了类似的结论。
2010年，贺毅朝等［78］认为差分演化算法的演化算子可以看成一个随机映射，然后运用压缩映像定理证明基本差分演化算法的渐近收敛性。同年，孙成富［79］运用马尔可夫链模型分析并证明基本差分演化算法的种群序列是有限齐次马尔可夫链，进而采用马尔可夫链的吸收态说明了基本差分演化算法无法保证全局依概率收敛。
2012年，Gohosh等［80］运用李雅普诺夫稳定性定理证明基本差分演化算法在一类特殊函数上的渐近收敛性。该类函数具有两个特征，即函数二阶连续可导，函数在可行域内只有**的全局*优值点。
1.3.3 差分演化算法的计算复杂度
因演化搜索的随机性带来了求解时间的不确定性，使得随机算法的算法复杂度的分析显得尤其重要。差分演化算法是随机搜索算法，2005年Zielinski等［81］从理论上和数值实验上研究了差分演化算法对不同终止准则的计算复杂度。Zielinski等指出，差分演化算法的两个繁殖操作——变异、交叉——在种群（记种群规模是NP）每一个个体（记个体维数是D）的每一维上执行，且变异操作的执行次数与循环的总数是成比例的。因此，如果终止准则是达到*大循环次数G_max，则差分演化算法的计算复杂度是O(NP·D·G_max)，进而推出结论，从整体上看，*大距离终止准则对差分演化算法有更小的计算复杂度。这里的*大距离终止准则是指，当种群中每个向量到种群中*好的向量之间的*大距离小于给定值时终止循环。
1.3.4 依概率收敛的差分演化算法设计
考虑到收敛的算法具有较高的稳健性，随着差分演化算法理论研究成果的逐步显现，收敛差分演化算法的设计正在逐步成为差分演化算法设计的一个研究分支。
2006年，Ter Braak［82］设计了一个差分演化马尔可夫链算法，并证明该算法的种群序列收敛到一个平稳分布。2009年，Zhao等［83］利用停滞个体的重新抽样（抽样函数）机制改进了经典的差分演化算法，并证明改进的算法是依概率收敛的。2012年，Zhan等［84］基于随机游动机制（random walk）设计了一个差分演化随机游动算法，文章虽然没有给出算法的收敛性理论证明，但该算法的依概率收敛性不难证明。2013年，Li［85］设计了一个基于高斯变异（Guassian mutation）和多样性逆转
定价：95.0
ISBN：9787030527363
作者：熊盛武，胡中波，苏清华
版次：31
出版时间：2017-06
内容提要：
全书内容分为差分演化算法（以下简称算法）的理论与应用两篇。理论篇主要内容包括算法的不确保依概率收敛性的理论分析、算法依概率收敛的充分条件、改进算法的收敛性分析、辅助算法收敛的子空间聚类算子的设计。应用篇主要内容包括收敛算法在螺旋压缩弹簧参数优化问题中的应用、算法在薄膜太阳能电池抗反射层微结构设计和在彩色图像颜色量化问题优化中的应用。
目录：
目录
《信息科学技术学术著作丛书》序
前言
第1章 绪论 1
1.1 引言 1
1.2 差分演化算法 2
1.3 差分演化算法理论研究概述 4
1.3.1 差分演化算法算子的搜索机理 5
1.3.2 差分演化算法的渐近收敛性 5
1.3.3 差分演化算法的计算复杂度 6
1.3.4 依概率收敛的差分演化算法设计 6
1.4 差分演化的算法改进研究概述 7
1.4.1 差分演化算法控制参数的设置研究 7
1.4.2 差分演化算法的演化算子改进研究 10
1.5 差分演化算法在工程应用领域的研究概述 12
参考文献 14
**篇 差分演化算法的收敛性理论与收敛算法设计
第2章 差分演化算法的不确保依概率收敛性 31
2.1 相关差分演化算法收敛性结论的分析 31
2.2 基于马尔可夫链的差分演化算法收敛性分析 33
2.2.1 相关定义与定理 33
2.2.2 连续解空间的离散化 34
2.2.3 差分演化算法的马尔可夫链建模 35
2.2.4 基于马尔可夫链的差分演化算法收敛性证明 35
2.3 基于随机漂移模型的差分演化算法收敛性分析 37
2.3.1 差分演化算法的随机漂移建模 37
2.3.2 线性欺骗函数的构造 38
2.3.3 基于随机漂移模型的差分演化算法收敛性证明 40
2.4 一类让经典DE算法不能确保收敛的函数 42
2.4.1 函数的结构特征分析 43
2.4.2 数值实验分析 45
2.4.3 函数难优化的缘由分析 46
2.5 本章小结 48
参考文献 48
第3章 差分演化算法依概率收敛的充分条件 50
3.1 充分条件的推理 50
3.2 充分条件的注记 52
3.3 几个差分演化算法的收敛性分析 52
3.3.1 DE-RW算法的收敛性证明 52
3.3.2 CCoDE算法的收敛性证明 54
3.3.3 msDE算法的收敛性证明 57
3.4 本章小结 59
参考文献 59
第4章 差分演化算法的依概率收敛模式及辅助算子 60
4.1 一个依概率收敛的差分演化算法模式 60
4.2 辅助差分演化算法收敛的常用繁殖算子 61
4.2.1 均匀变异算子 61
4.2.2 高斯变异算子 62
4.3 常用繁殖算子的辅助效率测试 63
4.3.1 实验设计与实验参数设置 64
4.3.2 实验结果与分析 64
4.4 本章小结 77
参考文献 77
第5章 依概率收敛差分演化算法的辅助算子设计 78
5.1 子空间聚类算子 78
5.1.1 子空间聚类算子的概率分析 79
5.1.2 子空间聚类算子的统计分析 82
5.1.3 子空间聚类算子的程序实现 84
5.2 一类基于子空间聚类算子的收敛差分演化算法 85
5.3 算法的收敛性证明 86
5.4 数值实验分析 88
5.4.1 测试函数集 88
5.4.2 实验设计与参数设置 89
5.4.3 实验结果与分析 91
5.5 本章小结 106
参考文献 106
第二篇 差分演化算法的应用
第6章 依概率收敛差分演化算法在螺旋压缩弹簧参数优化中的应用 109
6.1 螺旋压缩弹簧参数优化问题的模型建立 109
6.2 面向CCS优化设计的子空间聚类差分演化算法 111
6.2.1 面向CCS优化设计的罚函数约束处理技术 111
6.2.2 CCS优化中混合变量的处理技术 112
6.3 实验设计与结果分析 112
6.4 本章小结 114
参考文献 115
第7章 薄膜太阳能电池抗反射层微结构设计与优化 116
7.1 薄膜太阳能电池抗反射层研究现状 116
7.2 梯度氮化硅/氮氧化硅结构的光捕获设计与优化 119
7.2.1 优化模型 119
7.2.2 单因素分析 121
7.2.3 基于差分演化算法的设计与优化 124
7.2.4 与纳米粒子结构的性能比较 128
7.3 多层梯度抗反射层结构设计与优化 130
7.3.1 优化模型 131
7.3.2 基于差分演化算法的优化与设计 132
7.3.3 与纳米粒子结构的性能比较 135
7.4 介质纳米粒子与多层抗反射层的光捕获性能比较 138
7.4.1 介质纳米粒子的等效模型 138
7.4.2 与多层抗反射层比较 141
7.5 石墨烯透明导电薄膜光捕获结构设计与优化 143
7.5.1 优化模型 144
7.5.2 基于差分演化算法的优化与设计 146
7.6 本章小结 150
参考文献 151
第8章 彩色图像颜色量化问题的优化与算法参数设置 153
8.1 彩色图像颜色量化问题的优化方法发展现状 153
8.2 彩色图像颜色量化的基本优化策略 155
8.2.1 基于基本差分演化算法的彩色图像颜色量化优化策略 155
8.2.2 彩色图像颜色量化基本优化策略的参数设置 172
8.3 彩色图像颜色量化的混合优化策略 173
8.3.1 彩色图像颜色量化优化模型的元素置换等效性 173
8.3.2 混合策略 173
8.3.3 彩色图像颜色量化的混合差分演化算法 174
8.3.4 数值实验 176
8.3.5 实验结果分析 177
8.4 本章小结 183
参考文献 184
第9章 彩色图像颜色量化问题的自适应优化方法 185
9.1 差分演化算法参数的自适应化 186
9.2 彩色图像颜色量化的混合自适应差分演化算法 186
9.3 数值实验 188
9.4 实验结果分析 194
9.5 彩色图像颜色量化自适应混合优化策略在数字油画制作软件中的应用 194
9.6 本章小结 195
参考文献 196
附录 198
在线试读：
第1章 绪论
1.1 引言
人工智能（artificial intelligence，AI）是创造智能机器的科学与工程［1］，计算智能（computational intelligence，CI）是实现人工智能的技术与方法［2］，基于自然精神的算法是计算智能的主要组成部分，包括神经网络（neural networks）、模糊系统（fuzzy system）和演化计算（evolutionary computation，EC）等。演化计算方法又分为群体智能算法（swarm intelligence algorithms）和演化算法（evolutionary algorithms），典型的演化算法有遗传算法（genetic algorithm，GA）、遗传程序设计（genetic programming，GP）、演化策略（evolution strategy，ES）、演化规划（evolution programming，EP）和差分演化（differential evolution，DE）算法等。
差分演化算法［3］是Storn和Price 1995年为求解切比雪夫多项式拟合问题提出的一种基于演化机理的随机搜索算法。国内一般有差分演化算法、差分进化算法和差异进化算法等三种称谓。近20年的数值模拟与工程应用研究表明，差分演化算法是*强有力的智能计算方法之一。
差分演化算法具有优化效果稳健、控制参数少、易于编程实现等优点，自提出以来迅速引起了众多学者关注。2005年Springer出版差分演化算法的**本专著Differential Evolution:A Practical Approach to Global Optimization［4］。2007～2009年，汤姆森科技信息集团的科学引文检索收录有关差分演化算法的文章不少于3964篇［5］。 2011年2月，IEEE Transaction on Evolutionary Computation出版了一期差分演化算法的专辑。目前，该算法已经被应用到了组合优化［6］、多目标优化［7］、函数优化［8］和图像颜色量化［9］等二十多个领域，算法源码已经被包含在诸如Built in optimizer in MATHEMATICA′s function Nminimize(since version 4.2)，MATLAB′s GA toolbox contains a variant of DE，Digital Filter Design，Diffraction grating design，Electricity market simulation，Auto2Fit，LMS Virtual Lab Optimization，Optimization of optical systems，Finite Element Design，LabView，Microwave Office 10.0 by AWR Corp.和OPTIMUS等12个应用软件包中［10］。
众多比较性数值模拟与应用研究表明，差分演化算法是*强有力的随机优化算法之一。文献［11］应用34个测试函数，比较了差分演化算法、粒子群算法、一个改进的粒子群算法［12,13］（attractive and repulsive PSO，arPSO）和基本演化算法［14］（simple evolutionary algorithm，SEA）的性能，比较结果显示差分演化算法的整体性能优于被比较的其他三个算法。文献［15］运用差分演化算法和遗传算法优化给排水系统，在6个案例上的数值实验结果表明差分演化算法能得到更好的优化效果。文献［7］比较了差分演化算法和模拟退火算法（simulated annealing，SA）在辐射传递问题上的优化效果，结果表明差分演化算法和模拟退火算法都能得到较好的优化结果，但是差分演化算法相对模拟退火算法更稳健。
在历届演化优化的国际竞赛（international contest on evolutionary optimization,ICEO）中，差分演化算法是**的在每届比赛中都表现优异的算法［5］。在1996年的**届ICEO竞赛中，差分演化算法虽然只获得第三名［16,17］，但却是表现*好的演化算法（排名在前两位的是非智能算法）。接下来，在1997年的第二届ICEO竞赛中，差分演化算法获得**名［17,18］，数值实验结果表明差分演化算法是所有参赛算法中表现*优异的。表1.1给出了自2006～2013年各届ICEO竞赛的结果，表中“-V”表示基于某算法的改进算法。由此可见，ICEO的测试数据集包括约束与无约束的单目标优化、约束与无约束的多目标优化、大规模单目标优化和动态优化等。在这些数据集上，差分演化算法或者差分演化算法的改进算法（differential evolution variants，DE-V）是**一个能够一直排名前五的演化计算方法。差分演化算法是当前*有影响力的演化计算方法之一［19-22］。
表1.1历届演化计算国际竞赛（ICEO2006～2013）排名前五的算法
注：“-V”表示基于某算法的改进算法，“Other”表示非演化计算方法。
1.2 差分演化算法
差分演化算法常被用来求解连续优化问题，不失一般性，*小化边界约束连续优化问题的形式化表达式为
（1.1）
其中，RD是D维搜索空间；是解空间，Uj和Lj分别是xj的上下界。
记该问题的*优解是*，*优解集是B*。除非特别说明，接下来的讨论将基于上述*小化问题展开研究。
差分演化算法的基本思想是运用当前种群个体的差来重组得到中间个体，即实验个体（trail individual），然后运用父子个体适应值竞争来获得新一代个体。差分演化算法是*典型的演化算法之一，与其他演化算法类似，算法通过变异、交叉和选择等三步的循环来达到寻优目的。算法流程如下。
Step1，（初始化） 初始化种群规模（population size,N）、个体维数（individual dimension,D）、变异因子（mutation factor,F）、交叉概率（crossover probability,CR）、初始化种群Xt=(t1,t2,…,tN)。这里迭代次数t=0，表示第0代的初始化种群；ti,i=1,2,…,N表示第t代的第i个个体，每个个体都是D维向量。
Step2，（变异） 算法通过变异操作为每个个体产生一个对应的捐助向量v（donor vector），*常用的5个变异操作如下。
**，DE/rand/1：
第二，DE/best/1：
第三，DE/current-to-best/1：
第四，DE/best/2：
第五，DE/rand/2：
其中，ti，i=1,2,…,N是第t代种群中的第i个个体，称为目标向量（target vector）；r1,r2,…,r5是1～N中不等于i的相异的随机整数；tbest是第t代种群中的*优个体；变异因子F是经验参数，一般在区间(0,1］上取值。
Step3，（交叉） 算法通过目标向量和捐助向量之间的交叉操作为每个目标个体产生一个实验向量u，差分演化算法经典的交叉操作有指数交叉（exponential crossover）和二项式交叉（binomial crossover），*常用的二项式交叉可以表示为
其中，j=1,2,…,D；CR是算法的第二个经验参数，一般在(0,1)上取值；rand(0,1)是在［0,1］上服从均匀分布的随机数；jrand是1和D之间的一个随机整数，保证至少在某一维上实施交叉操作。
Step4，（选择） 差分演化算法通过在目标向量和实验向量之间实施贪婪的选择操作来产生下一代种群，选择操作（针对*小化问题）可表示为
这里f(·)是*小化问题的目标函数值。
Step5，（终止） 循环执行Step2～Step4，直至达到设定的循环终止条件，输出*优结果。常用的终止条件有两个：一是设定*大迭代次数，二是设置精度水平。
算法注解。
① 差分演化算法*具特色的是它自适应的变异操作。在演化的初期阶段，因为种群中个体的差异较大，因此用来作为变异扰动的差向量也较大，个体的扰动就较大，有利于算法的全局搜索；随着演化的进行，当算法趋于收敛的时候，种群中个体的差异随之较小，因此用来变异扰动的差向量也随之自适应地变小，较小的扰动有利于算法的局部搜索。正是这种简单又独具特色的变异操作有效地平衡了差分演化算法的全局搜索能力和局部搜索能力。需要注意的是，差分演化算法的变异操作对于搜索空间是不封闭的，即变异后得到的捐助向量可能会溢出搜索空间。周期模式（Periodic Mo差分演化）是常用的处理方法之一，即
其中，“%”是“求余”运算。
② 相对其他演化算法，差分演化具有算法简单、易于实现的优点。
③ 差分演化算法仅有三个经验控制参数，即种群规模N、变异因子F和交叉概率CR。算法的表现对参数的设置是敏感的，针对其中两个关键控制参数F和CR，已经研究出了较多简单有效的自适应（或者适应）控制方法。
④ 相对其他有竞争力的同类算法，较小的空间复杂度是差分演化算法的另一个优势，如协方差矩阵自适应进化策略（covariance matrix adaptation-evolution strategy，CMA-ES）。在不高于100维的优化问题上，CMA-ES表现出很强的竞争力，但是在更高维的大规模优化问题上，空间复杂度的优势让差分演化算法表现出更强的可拓展性。
1.3 差分演化算法理论研究概述
随着差分演化算法在数值模拟和众多工程应用领域的成功，越来越多的学者开始关注差分演化算法的理论研究。演化计算方法的理论研究是一个研究的难点，差分演化算法的理论研究更是进展缓慢。接下来，从算子搜索机理、算法渐近收敛性、算法复杂度和收敛算法设计等四个方面介绍当前的理论研究成果，然后分析在该领域可能存在的研究空间。
1.3.1 差分演化算法算子的搜索机理
差分演化算法是典型的演化算法之一，与传统的遗传算法类似，通过循环执行变异、交叉和选择操作来实现种群的逐步优化，算子搜索能力的强弱直接影响算法的整体优化性能。算子的搜索能力可分为全局搜索（globalexploration）能力和局部搜索（localexploitation）能力，全局搜索能力可由种群的多样性反映，种群的多样性又可由种群的方差反映。沿着这一研究思路，Zaharie应用基于统计量的方法从理论上研究了差分演化算法的算子搜索机理。
2001年，Zaharie［67］研究了差分演化算法的变异算子、交叉算子和种群方差的数学期望之间的关系，进而推演得到种群方差的数学期望与变异因子、交叉概率之间的函数关系，并证明差分演化算法（不含选择操作）的种群方差比演化策略的大，即种群多样性比演化策略的好，这也从某种程度上解释了差分演化算法在数值模拟上表现优越的内在原因。在此基础上，2002年Zaharie［68］进一步从理论上探讨了参数的取值与算法早熟之间的关系；进而，Zaharie［69］给出一种基于上述理论研究的自适应参数策略，该策略通过控制种群方差来控制种群的多样性。2008年，Zaharie［70］提出一个不使用经典差运算算子的变异操作，并从理论上证明该算子对种群方差与经典变异算子和交叉算子有等同的影响力。同时，也对二进制差分演化的种群分布做了初步的分析。
差分演化算法的交叉算子*常用的有二项式交叉（bionomial crossover）和指数型交叉（exponential crossover）。Zaharie［71,72］从理论上分析了差分演化算法交叉算子和交叉概率对算法行为的影响。理论和实验的研究结果表明，相对于常用的二项式交叉而言，指数型交叉对问题的规模更敏感，且两个交叉算子对差分演化算法行为的影响主要是通过控制变异组件来实现的。
与Zaharie基于统计量研究思路不同，Dasgupta等［73］建立了差分演化算法的动力系统模型，论证了差分演化算法搜索过程有梯度下降特征，并应用模型研究了差分演化的收敛速度与变异因子、交叉概率的相关性，进而应用李雅普诺夫稳定性定理（Lyapunov’s stability theorems）分析了差分演化算法的稳定性。
胡中波和熊盛武等［74］从代数系统是否同构的角度在理论上证明了DE算法不适合与Koziel［75］的约束处理映射相结合，而遗传算法却适合与该约束处理映射相结合。该结论从理论上论证了差分演化算法和遗传算法搜索机理的差异。
1.3.2 差分演化算法的渐近收敛性
2005年，Xue等［76］简化基本差分演化算法，只考虑算法的变异和交叉操作，假设初始种群符合正态分布，建立了连续的多目标差分演化算法的数学模型，并证明在初始种群中包含问题的帕累托（Pareto）*优解的前提下，算法能够收敛到帕累托*优解。同年，Xue等［77］把上述工作推广到离散的多目标差分演化模型中，得到了类似的结论。
2010年，贺毅朝等［78］认为差分演化算法的演化算子可以看成一个随机映射，然后运用压缩映像定理证明基本差分演化算法的渐近收敛性。同年，孙成富［79］运用马尔可夫链模型分析并证明基本差分演化算法的种群序列是有限齐次马尔可夫链，进而采用马尔可夫链的吸收态说明了基本差分演化算法无法保证全局依概率收敛。
2012年，Gohosh等［80］运用李雅普诺夫稳定性定理证明基本差分演化算法在一类特殊函数上的渐近收敛性。该类函数具有两个特征，即函数二阶连续可导，函数在可行域内只有**的全局*优值点。
1.3.3 差分演化算法的计算复杂度
因演化搜索的随机性带来了求解时间的不确定性，使得随机算法的算法复杂度的分析显得尤其重要。差分演化算法是随机搜索算法，2005年Zielinski等［81］从理论上和数值实验上研究了差分演化算法对不同终止准则的计算复杂度。Zielinski等指出，差分演化算法的两个繁殖操作——变异、交叉——在种群（记种群规模是NP）每一个个体（记个体维数是D）的每一维上执行，且变异操作的执行次数与循环的总数是成比例的。因此，如果终止准则是达到*大循环次数G_max，则差分演化算法的计算复杂度是O(NP·D·G_max)，进而推出结论，从整体上看，*大距离终止准则对差分演化算法有更小的计算复杂度。这里的*大距离终止准则是指，当种群中每个向量到种群中*好的向量之间的*大距离小于给定值时终止循环。
1.3.4 依概率收敛的差分演化算法设计
考虑到收敛的算法具有较高的稳健性，随着差分演化算法理论研究成果的逐步显现，收敛差分演化算法的设计正在逐步成为差分演化算法设计的一个研究分支。
2006年，Ter Braak［82］设计了一个差分演化马尔可夫链算法，并证明该算法的种群序列收敛到一个平稳分布。2009年，Zhao等［83］利用停滞个体的重新抽样（抽样函数）机制改进了经典的差分演化算法，并证明改进的算法是依概率收敛的。2012年，Zhan等［84］基于随机游动机制（random walk）设计了一个差分演化随机游动算法，文章虽然没有给出算法的收敛性理论证明，但该算法的依概率收敛性不难证明。2013年，Li［85］设计了一个基于高斯变异（Guassian mutation）和多样性逆转