Coevolutionary genetic algorithm using partial fitness functions for sampling schemata

摘要

A coevolutionary genetic algorithm (CGA) that effectively samples and. integrates schemata using partial fitness functions is presented. A fitness function is transformed into partial fitness functions having the same schema-sampling ability as the original fitness function. The binary-valued chromosome of the evaluation individual expresses the partial fitness function and is used to evaluate object individuals. Through competition between the object population and the evaluation population, the fitness of object individuals is defined as the number of evaluation individuals from which the object individual is received. Conversely, the fitness of evaluation individuals is defined as its inverse function, Thus, exploitation of new schema proceeds in, preserving the existing schema. Ideal partial fitness functions, which can decide the existing of schema, are applied to the royal road problem and two-bit problem. Markov chain analysis is used to evaluate the best performing CGA for each problem. The analysis results confirm that the CGA is effective at solving deceptive problems and that the CGA is not greatly influenced by mutation of the evaluation individual. The selection of partial fitness functions and the effectiveness of CGA are studied with respect to design problems in neural networks. If partial fitness functions are selected to be decision functions of the coincidence between the partial set of outputs and corresponding true outputs, then execution time for finding the optimum solution to the 4-2-4 encoder decoder problem and 4 neuron blinker problem can be shortened by 2.0% and 15.3% respectively, compared to the simple GA.