Changing Range Genetic Algorithm: A New Optimization Approach with Improved Performance

摘要

An attractive approach to improving a search strategy in genetic algorithms (GA) is reducing the search space towards the feasible region where the global optimum is located. This method dynamically adjusts the size of a search space and directs GA to the global optimum while significantly reducing computational cost and improving the precision of optimal solution. By using the methods of statistical mechanics, the advantages of this new approach were proved analytically. These methods were applied to describe the effect of the size of a search space adjustment on the macroscopic statistical properties of population, such as the average fitness and the variance fitness of population. This study focuses on the interaction of the various genetic algorithm operators and how these interactions give rise to optimal parameters values. The equations of motion are derived for the one-max problem that expressed the macroscopic statistical properties of population after reproductive genetic operators and adjusting a search space size in terms of those prior to the operation. Predictions of the theory are compared with experiments and shown to accurately predict the average fitness and the variance fitness of the final population. In addition, the developed changing range genetic algorithm (CRGA) was implemented to estimate the fractal properties of different packing mechanisms: a packing-limited growth mechanism and Apollonian packing with the random distribution of initially prepacked spheres. The fractal dimensions corresponding with the packing degree and porosity were calculated for a large range of spherical particles (in the order of millions). The results provide an experimental proof of analytically found value for a lower bound of the fractal dimension.