Paper Info
Title
Balanced-evolution genetic algorithm for combinatorial optimization problems: the general outline and implementation of balanced-evolution strategy based on linear diversity index.
Abstract
How to rationally inject randomness to control population diversity is still a difficult problem in evolutionary algorithms. We propose balanced-evolution genetic algorithm (BEGA) as a case study of this problem. Similarity guide matrix (SGM) is a two-dimensional matrix to express the population (or subpopulation) distribution in coding space. Different from binary-coding similarity indexes, SGM is able to be suitable for binary-coding and symbol-coding problems, simultaneously. In BEGA, opposite-direction and forward-direction regions are defined by using two SGMs as reference points, respectively. In opposite-direction region, diversity subpopulation always tries to increase Hamming distances between themselves and the current population. In forward-direction region, intensification subpopulation always tries to decrease Hamming distances between themselves and the current elitism population. Thus, diversity subpopulation is more suitable for injecting randomness. Linear diversity index (LDI) measures the individual density around the center-point individual in coding space, which is characterized by itself linearity. According to LDI, we control the search-region ranges of diversity and intensification subpopulations by using negative and positive perturbations, respectively. Thus, the search efforts between exploration and exploitation are balanced. We compared BEGA with CHC, dual-population genetic algorithm, variable dissortative mating genetic algorithm, quantum-inspired evolutionary algorithm, and greedy genetic algorithm for 12 benchmarks. Experimental results were acceptable. In addition, it is worth noting that BEGA is able to directly solve bounded knapsack problem (i.e. symbol-coding problem) as one EA-based solver, and does not transform bounded knapsack problem into an equivalent binary knapsack problem.
Year
DOI
Venue
2018
10.1007/s11047-018-9670-5
Natural Computing
Keywords
Field
DocType
Population diversity control,Feedback control scheme,Similarity guide matrix,Linear diversity index,Symbol-coding problem,Bounded knapsack problem
Discrete mathematics,Population,Hamming code,Mathematical optimization,Evolutionary algorithm,Evolution strategy,Knapsack problem,Solver,Genetic algorithm,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
17
3
1567-7818
Citations 
PageRank 
References 
1
0.36
31
Authors
3
Name
Order
Citations
PageRank
Hongguang Zhang110616.70
Y. Liu2578102.76
Jie Zhou3232.92