一种具有混合编码的二进制差分演化算法

A Binary Differential Evolution Algorithm with Hybrid Encoding

差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入"差异算子"等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入"辅助搜索空间"和"个体混合编码"等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的.HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.

Differential evolution （DE） is an evolutionary algorithm that is based on the individual differential reconstruction idea. It is proposed by Stom and Price in 1997, and is very suitable to solve optimization problem over continuous spaces. First of all, with the introduction of concepts of differential operator （DO）, etc., the concise description of DE is given and the analyis of its main features is advanced. For solving discrete optimization problem using DE, based on the idea of mathematic transform, the concepts of adjuvant search space and individual hybrid encoding are advanced. And with a definition of special mapping and the function of adjuvant search space, the high efficient differential evolution search over a continuous space is transformed into the homomorphism evolution search over discrete spaces. Thus, the binary differential evolution algorithm with hybrid encoding （HBDE） is first proposed. Subsequently, given definitions of probabilistic convergence and complete convergence of HBDE, and proved these by using Markov random theory. HBDE not only has the advantages of DE, but also is very suitable to solve discrete optimization problems. Calculations of instances to random 3-SAT problem and 0/1 knapsack problem show that HBDE has better convergence capability and stability, and its property is far more superior to binary particle swarm optimization as well as genetic algorithm.