-
极值优化算法
- 时间：2024-03-12 来源：佚名 人气：
EO算法是受复杂系统自组织临界进化模型的启发，发展形成的一种启发式只能算法。自然界和人类社会中存在许多复杂系统,它们在无外界驱动的情况下,能够自发地演化形成复杂的结构,这样的结构能以一种精妙的方式优化资源的使用.例如生态系统进化形成了一种强大相互依赖连接的网络, 能高效地使用有限的资源;网络系统如果工作在临界状态下,就能获得最高的数据传输效率.为了描述这种突现的复杂性,Bak提出了自组织临界(SOC)的概念. [1]
SOC普遍存在于复杂系统,如地貌的形成、地震、森林火灾、网络交通流、城市演化、收入和财富的分布、经济破产、技术创新和股市波动等.为了研究SOC系统的内部机理,研究者建立了一些能产生SOC状态的计算机模拟模型,其中最著名的有沙堆模型和Bak-Snappen进化模型. [1]
根据自然界的物种进化过程,在一个生物群落中,适应能力最差的物种总是被淘汰,或变异以获得生存的能力.Bak-Sneppen模型就是根据这一原则建立的.设群落中有n个物种,物种i的适值为λi属于[0,1]，在进化的每一步,适值最差的物种及其相关的物种被选中,它们的适值被更新(赋予一个0~1之间的随机数).尽管模型的规则简单,但在演化过程中体现了丰富的动态特性,包括自组织临界状态的出现,适值的广泛分布等.EO算法抽取 Bak-Sneppen模型的机理.发展成为一种动态的优化过程. [1]
基本的EO算法步骤非常简单。并且不需要凋整参数,具有实现容易、计算效率高等优点.其具体实现步骤如下:
Stepl:针对具体问题中的变量,定义合适的物种(变量划分)xi及对应的适值函数λi;
Step2:初始化,随机产生一个问题的初始配置 (初始变量);
Step3:计算每个物种的适值λi,并根据适值大小对物种xi排序;
Step4:选择适值最小的物种xm,并且更新(按一定概率分布产生随机数来替换原有的xm);
Step5:如果满足停止准则,则算法停止,输出结果.否则返回Step3.
下面以TSP问题为例,说明EO算法的实现过程.TSP算法是典型的NP难题,并且应用广泛, 具有代表性.
在TSP问题中,一个城市被定义为一个物种. EO算法的原则是系统内部的各个物种追求局部最好值,并通过局部的相互作用获得整体最优.在一个巡回中,城市i追求的局部最优是与相连接的城市之间有最短的路径,因而定义城市i的适值为λi=3/(pi+qi).将其余各个城市与城市i的路径从小到大排序,例如与i相连的两个城市分别排在第pi位和第qi位,记为和。
此外,更新适值最差的城市m,不采用通常的两两交换法(这种方法效率较低),而是按照到城市m的路径,将其他城市从小到大排列,即n=1是离m最近的城市n=2是离m第二近的城市,依此类推.按照概率P(n)~n^(-τ),选择一个城市j与城市m相连接;然后同时断开与m和J相连的两条路径,调整形成一条新的合法路径.数值结果显示, 对于Euclidean TSP问题.在随机产生的城市数N=16,32,64,128,256的例子中,EO算法只比SA算法的精度差1%,而在非EuclideanTSP问题中,EO算法得到的结果精度比SA算法的要高.
E0算法中有两个关键问题:
1)如何针对不同的问题定义局部组分(物种)。 这是运用EO算法的突破点.如果一个问题中的各个变量耦合太深或组分之间没有相似点,即各个组分对目标函数的贡献不同,这类问题就难以用EO算法来求解.尽管如此,还是有相当多的问题满足EO算法的要求,或者通过变化能够达到要求,所以 EO具有广泛的适用性.
2)如何定义每个局部划分的适值函数,这是 EO算法发挥效力的关键.例如在图分解问题中, Boettcher定义的适值函数同时考虑了一个顶点的边(与顶点本部分相连的边)和差的边(跨过分界的边)，所以算法的效果较好。 [1]
基本的EO算法只选择最差的物种更新,限制了解的更新范围,有时算法会陷入局优解.为了避免陷入僵局,Boettcher等提出了τ-EO算法,引入一个可变参数τ,调节变量的选择概率。
具体实现为:将各个变量对应的适值xi从小到大排序,得到排列λ_∏(1)<=λ_∏(2)<=……<=λ_∏(n)。适值最差的变量xj排在第1值,j=∏(1);最好的变量,排在第n位,j=∏(n).定义选择第k位变量的概率函数
GEO算法适用于求解连续的函数优化问题。EO算法的关键是给每个五种分配一个适值，但有时这样的分配不易实现。GEO算法克服了这一缺点,改变了适值的定义方式, ,用一个长度为L的二进制为变量编码，给二进制串中的每一位分配一个适值，适值决定该位是否变异。在编码过程中，将问题的N个变量按序排列，每个变量用lj(j=1,2,……，N)位二进制表示，最终得到的编码序列如同GA算法中的染色体。编码位上的适值越小，该位变异的概率越大。
如果问题包含约束，则可对不满足约束位的变异设置一个较高的适值（求最小值），限制不满足约束变异的发生。文献[19]用非线性、多峰、多维的检验函数作了数值验证,并与标准的GA和合作进化 GA(CCGA)进行比较,结果表明GEO算法的效果与CCGA相当,对于某几类函数具有更快的收敛性.? [1]
J-EO算法是一种改进的τ-EO算法.J-EO定义的适值函数在原先基础上增加了一个记忆变量,记为Γki,.其中:0<Γ<1是衰退参数,ki是物种i被选中的次数.记忆变量增加了被重复选中的物种适值,降低了此变量以后被选择的概率.这类似于禁忌搜索算法中禁忌表的作用,可降低孵被重复操作的概率.于是便增加了算法的弹性,扩大了搜索空间, 提高了算法效率.数值结果表明。对于2维和3维的自旋玻璃基态问题, J-EO算法与τ-EO算法相比,在相同的运算次数内能得到更好的解。
Zhou等提出一种连续极值优化(CEO)算法.算法由两部分组成:一部分是经典的EO算法, 负责全局搜索;男一部分是局部搜索算法,负责局部的精细搜索,将CEO运用于Lennard—Jones聚类优化问题,井与SA和GA算法作了比较.取得了较好的效果.
EO算法采用产生新的随机数来更新适值最差的变量,因此采用的随机分布对算法效果有重要作用.Menai等提出一种在量子物理学中使用的概率分布Bose-Einstein来更新变量,并将改进的EO算法应用于MΛXSAT问题,取得了良好的效果. [1]
与其他优化算法相比,EO算法具有以下特点:
1)EO算法不是全局算法,而是将待解问题分解为相似的局部组分,为每个局部组分定义适值,通过局部比较和相互作用突现全局的最优。所以在一次迭代中只处理一个解,利用解中变量之间的关系进行优化,减少了计算时间.
通常的种群优化算法(如遗传算法、PSO算法、蚁群算法等)将多个解组成一个种群,通过比较、移动、交叉、组合等解之间的相互作用,达到寻优的目的。其优势是种群容易产生，但是每步迭代运算都要计算多个解。随着问题规模的增加,计算量呈指数增加.例如规模为N的问题,如果PSO算法选择的微粒个数为30,那么每步迭代需要计算30*N个不同的解.而EO算法只需计算一个解,计算量只有PSO算法的1/30.
2)非平衡性(准平衡性):EO算法不会静止到一个平衡态,算法随机更新后,将无条件接受新的 解,算法运行到后期,仍有很大的波动性.保持持续搜索解空问的活力.模拟退火算法在后期将收敛到一个平衡点,波动很小,对于一些处于临界状态的难题难以跨越障碍,因而易陷入局优点。
3)EO算法的优化是通过淘汰最差适值的局部分量实现的,而其他算法是通过选择、培养好的解或向好的方向移动进行优化的.EO算法体现了一种新的寻优方式,为智能优化算法的研究开拓了新的思路,优化向题作为一个动态演化的系统,被EO算法加以分解,通过内部分量之间的相互作用与竞争, 进而获得整体的优化.这突出反映了生物群落进化过程中的竞争性,即各物种均向适值最好的方向演化,但对资源的竞争导致最差的物种被淘汰或被迫变异,由此整个群落进化到SOC状态,获得对有限资源的高效利用. [1]
EO算法及其各种改进算法已得到广泛的应用.最初,EO算法只限于求解一些组合优化问题和物理学问题,包括图分解问题、TSP问题、SAT问题、图着色闻题等.与其他智能优化算法的比较研究表明,EO算法是解决NP难题的一种有效方法.后来经过改进和变化,EO算法扩大了应用范围。可求解函数优化问题,因而可应用于系统参数的优化设计。目前，EO算法已经运用到越来越多的领域,例如模式识别、信号测、各类设计优化、分子团簇的聚类等.下面简要介绍主要的几方面应用.
EO算法在模式识别和计算机视觉方面的应用主要是设计点匹配算法.文献 [2]提出一种基于EO算法的准确、快速和鲁棒性的点匹配方法。定义鲁棒点为算法中的变量划分,并且构造一个有效的外层移除方案,处理有噪声和外部数据影响的情况. 文献 [3]提出一种新的框架,利用奇异值分解的某些特性,结合EO算法进行点匹配.奇异值分解的作用在于产生配置,而EO算法用于精练匹配.
扩展的GEO算法成功地应用于优化系统参数 的设计问题,例如最小化支架质量的10一bar支架设计问题,太空船的热量控制系统设计,热传输管道的优化设计等.这些优化设计问题充分体现了GEO算法易于实现,能高效处理非线性,离散或整数变量函数的优势. 另一个成功应用是识别复杂网络的群落结构,近年来,描述复杂网络的结构成为研究复杂系统的热点问题.群落结构的划分原则是:群落结点的相互联结大于群落内结点与外部的连接,因而可定义一个连接度,通过最大化连接度进行网络中的群落划分.这是一个NP难题.数值仿真表明,EO算法的效果比SA和GA算法好. [1]
