Analyzing the Effects of Memetic Variations on Convergence in Overlapping Swarm Intelligence
摘要
Evolutionary algorithms often struggle when there exists a high degree of interdependence between the variables (epistasis), non-separability, discontinuity, high dimensionality, and sparsity. These complexities can lead to hitchhiking, where poor parameters are associated with good schemata, and “two steps forward and one step back” where near-optimal parameters are lost in favor of lower-quality parameters that immediately improve fitness; phenomena that contribute to premature convergence. Overlapping Swarm Intelligence (OSI) has been introduced as a cooperative coevolutionary algorithm that utilizes overlap of variables between subswarms to encourage sharing and competing among variables across the subswarms. OSI has shown success in handling epistasis, however it can still suffer from premature convergence when subswarms get stuck in “pseudo-optima,” i.e., when a subset of variables is at a minimum with respect to the reduced search space but not the entire space. We investigate convergence on memetic variations of OSI, CPSO (OSI with no overlap), and Particle Swarm Optimization using block coordinate descent applied to the CEC2010 Benchmark problems. The memetic algorithms show some success in assisting subpopulations in finding more optimal solutions compared to their non-memetic counterparts. We also use the Gini coefficient on a solution’s derivative to estimate the proportion of variables stuck in pseudo-optima to help understand what contributes to premature convergence.