为什么只有状态转移算法才是真正意义上的智能优化算法 ...
0 旁白长期以来，“论文为王”的观念被推崇至上，没有论文就没有发言权，发表了大量学术论文才能高谈阔论、坐而论道，以至于出现“大家都忙着写论文，没有时间搞科研”的反常局面，不知内情者以为发论文就是搞科研。本文正是在这种反常局面下诞生，如果列位看官对智能优化算法感兴趣，且带着求真务实的态度搞科研，倒可以看看本文，否则纯粹浪费时间。
1 引言
自从上世纪70年代美国密歇根大学Holland提出遗传算法以来，各种智能优化算法如雨后春笋般涌出，比如粒子群优化算法、差分进化算法、人工蜂群算法等。特别是近10年来，澳大利亚格里菲斯大学Seyedali Mirjalili提出了诸如灰狼优化算法、鲸鱼优化算法、飞蛾扑火优化算法等10余种智能优化算法，让人惊掉下巴，哭笑不得。
从最优化算法的设计原理上看，只要产生候选解（或解集）和更新当前解（或解集）的机制稍微不一样，就是一种不同的最优化算法，这也不难理解如今为什么会有如此名目繁多的最优化算法。可是这些所谓的“智能优化算法”真的是智能优化算法么？！
抛开那些“挂羊头卖狗肉”的所谓群体智能或生物启发机制不论，本文从另一个角度阐述为什么只有状态转移算法才是真正意义上的智能优化算法，其它的都是“假冒伪劣”！
2 几种智能优化算法简介
下面就几种常见的智能优化算法进行介绍。
2.1 遗传算法简介
遗传算法（Genetic Algorithm，GA）是20世纪六七十年代由美国密歇根大学的Holland教授创立，它是一类模拟自然界遗传机制和生物进化论的随机搜索算法。遗传算法从代表最优化问题可能潜在解集的一个种群开始，首先将表现型映射到基因型，即编码，从而将解空间映射到编码空间，每个编码对应问题的一个解，称为染色体或个体。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助自然遗传学进行组合交叉和变异，产生出代表新的解集的种群。这个过程使种群像自然进化一样，后代种群比前代更加适应于环境。
遗传算法里两种经典操作，交叉和变异，示意图分别如下：
图 1 交叉操作
图 2 变异操作
2.2 粒子群优化算法简介
粒子群优化算法(Particle Swarm Optimization，PSO) 由Eberhart和Kennedy博士于1995年提出，其思想源于对鸟群觅食过程的模拟，通过鸟之间的相互协作完成食物的搜寻。PSO算法把优化问题的解域类比为鸟类的飞行空间，将优化问题的候选解类比为鸟群中的鸟，每只鸟抽象为飞行空间内一个无质量无体积的微粒，问题需搜寻的最优解则等同于鸟群要寻找的食物。鸟群在觅食过程中，有时候需要分散的寻找，有时候需要鸟群集体搜寻，即时而分散时而群集。对于整个鸟群来说，它们在找到食物之前会从一个地方迁移到另一个地方，在这个过程中总有一只鸟对食物的所在地较为敏感，对食物的大致方位有较好的侦查力，从而，这只鸟也就拥有了食源的较为准确信息。在鸟群搜寻食物的过程中，它们一直都在互相传递各自掌握的食源信息，特别是这种较为准确的信息。所以在这种“较准确信息”的吸引下，使得鸟群都集体飞向食源，在食源的周围群集，最终达到寻找到食源的结果。
粒子群优化算法中的速度和位置更新公式如下：
v_{i d}^{t+1}= w v_{i d}^{t}+c_{1} r_{1}\left(p_{i d}^{t}-x_{i d}^{t}\right)+c_{2} r_{2}\left(p_{g d}^{t}-x_{i d}^{t}\right) \\x_{i d}^{t+1}=x_{i d}^{t}+v_{i d}^{t+1}
其中 x_{i d}^{t} 表示在 t 时刻第 i 个粒子第 d 维的位置， v_{i d}^{t} 表示在 t 时刻第 i 个粒子第 d 维的速度， w 代表惯性权重， c_1, c_2 分别代表自我和社会学习因子， r_1, r_2 为随机数。
2.3 差分进化算法简介
差分进化算法(Differential Evolution，DE)是由美国学者 Storn 和Price于1995 年提出的一种计算方法，最开始是用于求解切比雪夫(Chebyshev)多项式问题，后来人们发现DE也是一种解决优化问题的有效算法。DE是一种基于群体进化的算法，具有记忆个体最优解和种群内信息共享的特点，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的随机优化算法。差分进化算法与其他进化算法的不同之处为：DE将随机的两个个体的差异信息作为基础个体的扰动量，使得算法在搜索步长和搜索方向上具有自适应性，同时具有较强的全局收敛能力和鲁棒性。在进化早期，由于种群中个体间差异较大，使得扰动量较大，能在较大范围内搜索，具有较强的全局搜索能力；在进化后期，算法趋于收敛，个体间差异较小，在个体附近的较小范围内搜索，这也使得差分进化算法具有较强的局部搜索能力。
差分进化算法中有如下几种变异算子：
[*]rand/1 :v_{i}(g+1)=x_{r 1}(g)+F\left(x_{r 2}(g)-x_{r 3}(g)\right)
[*]best/1 :v_{i}(g+1)=x_{b e s t}(g)+F\left(x_{r 1}(g)-x_{r 2}(g)\right)
[*] current-to-best:v_{i}(g+1)=x_{i}(g)+F\left(x_{b e s t}(g)-x_{i}(g)\right)+F\left(x_{r 1}(g)-x_{r 2}(g)\right)
[*] best/2:v_{i}(g+1)=x_{b e s t}(g)+F\left(x_{r 1}(g)-x_{r 2}(g)\right)+F\left(x_{r 3}(g)-x_{r 4}(g)\right)
[*] rand/2:v_{i}(g+1)=x_{r 1}(g)+F\left(x_{r 2}(g)-x_{r 3}(g)\right)+F\left(x_{r 4}(g)-x_{r 5}(g)\right)
其中 x_{r 1}(g)、x_{r 2}(g)、x_{r 3}(g) 表示从当前种群中随机选择的三个个体， r1,r2,r3 为互不相同随机整数， x_{b e s t}(g) 为当前种群中的最佳个体， F 为缩放因子。
2.4 状态转移算法
状态转移算法(state transition algorithm，STA)是一种基于结构主义学习的智能优化算法，它抓住最优化算法的本质、目的和要求，以全局性、最优性、快速性、收敛性、可控性为核心结构要素，需要什么才学习什么。2012年，周晓君教授正式提出这种新颖的智能型随机性全局优化方法,它的基本思想是：将最优化问题的一个解看成是一个状态, 解的迭代更新过程看成是状态转移过程, 利用现代控制理论的状态空间表达式来作为产生候选解的统一框架, 基于此框架来设计状态变换算子。与大多数基于种群的进化算法不同, 基本的状态转移算法是一种基于个体的进化算法, 它基于给定当前解, 通过采样方式, 多次独立运行某种状态变换算子产生候选解集, 并与当前解进行比较, 迭代更新当前解，直到满足某种终止条件。 值得一提的是, 基本状态转移算法中的每种状态变换算子都能够产生具有规则形状、可控大小的几何邻域, 它设计了包括旋转变换、平移变换、伸缩变换、坐标轴搜索等不同的状态变换算子以满足全局搜索、局部搜索以及启发式搜索等功能需要, 并且以交替轮换的方式适时地使用各种不同算子, 使得状态转移算法能够以一定概率很快找到全局最优解。
几种常用的状态变换算子如下：
（1）旋转变换
s_{k+1}=s_{k}+\alpha \frac{1}{n\left\|s_{k}\right\|_{2}} \boldsymbol{R}_{r} s_{k}
其中 \alpha 为旋转因子； \boldsymbol{R}_{r} \in \mathbb{R}^{n \times n} 为随机矩阵，其元素取值于[-1,1]之间均匀分布； \|\cdot\|_{2} 表示取向量的模。旋转变换能够以当前解s_{k}为原点，在给定半径 \alpha 的超球体内进行局部搜索。
旋转变换示意图
（2）平移变换
s_{k+1}=x_{k}+\beta \boldsymbol{R}_{t} \frac{s_{k}-s_{k-1}}{\left\|s_{k}-s_{k-1}\right\|_{2}}
其中 \beta 为平移因子；\boldsymbol{R}_{t} \in \mathbb{R}^{n \times n} 是一个随机向量，其元素取值于之间均匀分布。平移变换沿着当前解s_{k} 和前一个历史解s_{k-1}所形成的的直线上进行启发式搜索。
（3）伸缩变换
s_{k+1}=s_{k}+\gamma \boldsymbol{R}_{e} s_{k}
其中 \gamma 为伸缩因子； \boldsymbol{R}_{e} \in \mathbb{R}^{n \times n} 是一个非零元素取值服从正态分布的随机对角矩阵。从式子中不难理解，伸缩变换能够以正态分布的概率，将当前解s_{k} 的每个维度上的值伸缩到实轴上的任意位置，具有全局搜索的能力。
（4）轴向变换
s_{k+1}=s_{k}+\delta \boldsymbol{R}_{a} s_{k}
其中 \delta 为轴向因子； \boldsymbol{R}_{a} \in \mathbb{R}^{n \times n} 是一个非零元素取值服从正态分布的稀疏对角矩阵，在基本状态转移算法中，\boldsymbol{R}_{a} 仅有一个位置为非零元素。坐标变换能够从当前解s_{k} 出发，随机挑选一个维度进行搜索，能够增强单一维度的搜索能力。
轴向变换示意图
3 常见智能优化算法剖析
从表面上看，上述这几种智能优化算法貌似没有本质区别，都是产生候选解（解集）和选择更新当前解（解集），只是机制不同而已。它们产生候选解的机制，是算子设计上的不同；而它们的学习机制，可以从行为主义模仿学习和结构主义（建构）学习上加以区别，遗传算法、粒子群优化算法、差分进化算法等是行为主义模仿学习，而状态转移算法是结构主义学习。换句话说，状态转移算法学习的目的是为了解决最优化问题，而其它的仅仅是模仿生物行为，并没有紧紧围绕解决最优化问题这个核心目的。
目前虽然有形形色色的智能优化算法，但有一个基本的问题，其它的智能优化算法无法解决，那就是算法的终止条件问题。很多智能优化算法的终止条件是最大迭代次数，这个显然就不合理也不科学，让使用者无所适从。有些智能优化算法虽然设置了种群停止更新就终止的条件，但效果往往更差。事实上，不管是设置最大迭代次数，种群停止更新或者其它什么终止条件，这些智能优化算法都无法保证得到的解是最优解。从这个角度上说，这些智能优化算法连最基本的最优性都无法保证，那根本称不上是最优化算法，只能是“假冒伪劣”产品，或者最多算是一种启发式搜索方法，滥用优化这个名词。所以说，其实一句话可以说明状态转移算法和其它的智能优化算法的区别，那就是通过设置一定的终止条件，状态转移算法可以保证得到的解是最优解，而其它智能优化算法不行！
要证明一个结论是对的很难，而要证明一个结论是错误的倒很容易，举个简单的例子就可以说明一切。
考虑下面这个经典测试函数：
Rastrigin function：
f_{rastrigin}(\mathbf{x})= 10 n + \sum_{i=1}^n \left
其中， x_{i} \in [-5.12,5.12] ，该函数有全局最优解 \mathbf{x} ^{*}= \mathbf{0} ，此时 f_{rastrigin}(\mathbf{x} ^{*}) = \mathbf{0} .
图 5 Rastrigin function示意图
设置 n = 500 , 采用MATLAB R2018b进行编程，利用自带的ga和particleswarm两个命令，终止条件为Optimization terminated: average change in the fitness value less than options.FunctionTolerance.
求得的结果如下：
表1 不同智能优化算法的测试结果
算法目标函数值梯度范数GA4.7482e+03964.8148PSO4.8819e+04464.1154STA8.1855e-112.9232e-04 结果表明遗传算法等智能优化算法运行终止时，梯度还较大，不满足最优性，因此不能称之为最优化算法。请感兴趣的读者可以自行测试，结果带有一定的随机性，但是本文的主要结论不变。
一定有人会说，遗传算法、粒子群优化算法等都已经被证明了，怎么会有错？那么请问：是证明这些算法全局收敛还是收敛到全局最优？证明收敛到全局最优的假设是什么？如果那些证明是对的，为什么跟实际不符？正确的证明得经得起实践的考验才是！实际上，关于智能优化算法的证明实际上是亡羊补牢，因为最优化算法不是一个证明问题，而是一个设计问题（这句话要细品，内行才能品出味来）。此外，IT界还有一句话，talking is cheap show me the code， 很多时候算法效果怎么样，将代码运行一下就知道了，不管多少争辩的话都是纸上谈兵。
也一定有人会说，这些标准版本的遗传算法、粒子群优化算法等效果不好，改进版的才效果好。这话本身就已暴露这些智能优化算法存在问题，肯定是效果不行，才需要改进。从已发表文献上看，目前这些智能优化算法的改进版本已经成百上千种。可是仔细一想，思细极恐，某种智能优化算法的改进版本越多，不是越说明这种智能优化算法不好么？换句话说，为什么不好的东西反而流行且讨人喜欢呢？出现这种反逻辑的原因只有一个，那就是功利，因为这些智能优化算法容易改进，容易发论文、出成果、捞好处。
4 结论
譬如遗传算法、粒子群优化等所谓的智能优化算法并不是真正意义上的智能优化算法，它们既不智能，也不寻优，充其量只能是算是启发式搜索算法而已，只有状态转移算法才是真正意义上的智能优化算法。
5 编者按
科研不是写论文，论文并不能代表科研水平。“破五唯”的论调已经提出来若干年，不破不立，破了以后怎么立，这个革命实是一件难事，难就难在“干革命的和被革命的往往是同一类人”。很多时候就像《皇帝的新装》讲的那样，所有人都知道皇帝根本没有穿衣服，可是没有人敢说出来，只有那个小孩，也被称为“傻子”。
什么时候大家能坐下来讨论交流“无公害的纯学术”，而不是忙着发论文、申项目，争评人才帽子，到处忽悠捞好处，不去追求这些低级趣味的东西，那科学的春天就又到了。 建议多看看CMA-ES或者NES吧！！！ 经测试，当Dim = 500时，CMA-ES本质上没有区别，当目标函数值连续若干代不更新时，不能保证是最优点，不满足导数为0，仅为停滞点。 关于ES的理论分析：https://link.springer.com/article/10.1007/s10107-014-0793-x 发表在数学优化顶刊 https://jmlr.org/papers/v18/14-467.html 发表在机器学习顶刊 评价见2015年Nature演化计算综述 如果测试 建议使用BBOB进行系统比较！ 发表在订刊上的论文就是对的，合理的吗？有多少发表在Nature和Science上的论文被撤稿了呢，实用性又有多大呢？ 请仔细阅读该文，搞明白什么叫全局收敛和收敛到全局最优，以及收敛到最优解的假设条件，现实中能满足么？数学证明通常是形式逻辑，能证明出来的东西，假设一般较强，实用性一般较差。 BBOB的测试函数已经做过比较 既然你质疑这3篇论文，就找出这些发在顶刊/顶会论文中的错误！并将你的算法发在领域内的期刊与会议上，让大家好好评判！而不只是在知乎上宣称！历史会给予公平的评价！ES可以追溯到1960年代！ 并不是想质疑，而是希望大家阅读论文的时候认真阅读，而不是看了题目或摘要不看内容，ES提出很早，并不能代表什么，理论证明是有假设的，实践是检验真理的唯一标准。 评判的标准是什么呢？我写这篇知乎的只是阐述传统智能优化算法并不能保证找到最优解，连续多次目标函数值不更新，就终止迭代，看终止的点是否满足梯度很小？可以运行代码看看，多数理论文章并不会关注这个问题。甚至把陷入局部最优这个概念误导大众，其实并没有陷入局部最优，而是陷入停滞点，这也是本文的目的。
页:
[1]
2