基于概率分布的多峰演化算法

Probability Distribution Based Evolutionary Computation Algorithms for Multimodal Optimization

演化算法通过模拟自然界生物迭代演化的智能现象来求解优化问题,因其不依赖于待解问题具体数学模型特性的优势,已成为求解复杂优化问题的重要方法.分布估计算法是一类新兴的演化算法,它通过估计种群中优势个体的分布状况建立概率模型并采样得到子代,具有良好的搜索多样性,且能通用于连续和离散空间的优化问题.为进一步推动基于概率分布思想的演化算法发展,概述了多峰优化演化算法的研究现状,并总结出2个基于概率分布的演化算法框架:面向多解优化的概率分布演化算法框架和基于概率分布的集合型离散演化算法框架.前者针对现有的演化算法在求解多峰多解的优化难题时缺乏足够的搜索多样性的缺点,将广义上基于概率分布的演化策略与小生境技术相结合,突破多解优化的搜索多样性瓶颈;后者围绕粒子群优化等部分演化算法在传统上局限于连续实数向量空间的不足,引入概率分布估计的思想,在离散的集合空间重定义了算法的演化操作,从而提高了算法的可用性.

Evolutionary computation(E C)is a category of algorithms which simulate the intelligentevolutionary behavior in nature for solving optimization problems.A s E C algorithms do not rely onthe mathematical characteristics of the problem m o d e l,they have been regarded as an important toolfor complex optimization.Estimation of distribution algorithm(E D A)is a n e w class of E Calgorithms,which w o r k s by constructing a probability m odel to estimate the distribution of thepredominant individuals in the population,and sampling n e w individuals based on the probabilitym o d e l.W i t h this probability-based search behavior,E D A is good at maintaining sufficient searchdiversity,and is applicable in both continuous and discrete search space.In order to promote theresearch of probability-based E C(P B E C)algorithms,this paper gives a survey on E C algorithms formultimodal optimization,and then further builds t w o f r ameworks for P B E C:P B E C f r a m e w o r k forseeking multiple solutions in multimodal optimization,and P B E C f r a m e w o r k for discrete optimization.T h e first f r a m e w o r k presents a m e t h o d to combine probability-based evolutionary operators with theniching strategy,so that higher search diversity can be maintained for seeking multiple solutions inmultimodal optimization.In particular,the f r a m e w o r k understands P B E C algorithms in a broadsense,that is,it allows both explicit P B E C algorithms(e.g.E D A)and implicit P B E C algorithms(e.g.ant colony optimization)to operate in the f r a m e w o r k,resulting in t w o representativealgorithms:multimodal E D A(M E D A)and adaptive multimodal ant colony optimization(A M-A C O).T h e second f r a m e w o r k aims at extending the applicability of E C algorithms on both continuous anddiscrete space.Since s o m e popular E C algorithms are originally defined on continuous real vectorspace and they cannot be directly used to solve discrete optimization p r o b l e m s,this f r a m e w o r kintroduces the idea of probability distribution based evolution and redefines their evolutionaryoperators on discrete set space.A s a result,the applicability of these algorithms can be significantlyimproved.