Study Of Search Efficiency And Encoding Schemes Of Genetic Algorithms

Though genetic algorithms (GA's) are regarded as highly efficient global search algorithms, they turned out in many applications and simulation calculations to be not good at local search. Researches on their optimization mechanism can provide guidelines to improve their searching performance. Many of such researches have been carried out, however, there are still theoretical blanks. Studies in this paper focus on three of these blanks, including schemata-processing efficiency, encoding schemes and local search efficiency.One of the superior features of GA's over other optimization algorithms is that a large quantity of schemata are processed inherently while processing a relatively small quantity of individual strings, which is known as their implicit parallelism. However, it fails in explaining why GA's are inefficient in local search. This paper goes a step forward by showing the relationships respectively between schemata-processing efficiency and schema orders, and between schemata-processing efficiency and schema definition lengths.That GA's are low in local-search quality is not a deduced conclusion but perceptual knowledge induced from the results of applications and simulation calculations. There still lacks of correlative theoretical analyses. Some results of tentative analyses on this subject are put forwarded in this paper, including: 1) a lower bound on the iterative number required to locate the optimum with a certain probability; 2) a sufficient condition of when a GA will be inefficient in local search. It is also pointed out that low local-search efficiency is inevitable as long as linear-weight-encoding GA's, such as binary, decimal and real ones, are applied to the optimization of those smooth functions that can be linearized into the function y = ax + b around the optimum point.