A Binary Differential Evolution Algorithm with Hybrid Encoding

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.