Research On Coevolutionary Algorithm And It's Application

Coevolutionary Algorithm (CEA) belongs to global optimizing algorithms inspired by coevolution, which is prevalent in nature. CEA is a new research issue in the field of evolu-tionary algorithm (EA). This dissertation analyzes the algorithm model and theoretical foun-dation of CEA, and probes into its application in functional optimization and image vector quantization. The main contributions of this dissertation include:1 Evolutionary Computation and Coevolutionary Algorithm are reviewed. In this dis-sertation Evolutionary Computation is classified into two classes: traditional EA and new EA. Traditional EA includes Genetic algorithm (GA), Evolutionary Programming (EP), and Evo-lution Strategies (ES). New EA includes Estimation of distribution algorithm (EDA), Differ-ential Evolution Algorithm (DEA), and Coevolutionary Algorithm (CEA). Standard genetic algorithm evaluates individuals by their chromosomes, independent of other individuals in the evolutionary system. So the fitness in SGA is an absolute fitness. In comparison, CEA evalu-ates individuals by their performance relative to others. So the fitness is a relative fitness. According to the ways to evaluate individuals, CEA are generally divided into two categories: Competitive Coevolution Algorithm (Comp-CEA) and Cooperative Coevolutionary Algo-rithm (Coop-CEA). Comp-CEA assesses individuals by their competitive performance in re-lation to opponents in competition. In Comp-CEA, survival pressure compels the individual to defeat more and better opponents. Coop-CEA assesses individuals by their cooperative per-formance relative to cooperators in cooperation. In Coop-CEA, survival pressure compels the individual to cooperate more effectively with the cooperators, producing better cooperative results. The application, and merits, and shortcomings of the two up-said coevolutionary algo-rithms are summarized. The key issues in applying coevolutionary algorithm are also dis-cussed and analyzed.2 An Unified Coevolutionary Algorithm (UCEA) is presented. In UCEA there are two kinds of fitness: survival fitness and chromosome fitness. UCEA covers all the possible co-evolutionary relations in ecology. The total influence received by an individual from any other individual has only three possibilities: benefit, harmful or neutral. Two kind of UCEA are presented: simple UCEA (UCEA-I) and modified UCEA (UCEA-II). In UCEA-I, individuals form a pair randomly, giving each other benefit influence, harmful influence, or neutral influ- ence according to probability set beforehand. In UCEA-II, an individual's survival fitness is affected by it hamming distance from the Elite in the population. Because of the principle of competitive exclusion and the phenomena character displacement, all individual tend to mu-tate and carry out morphological differentiation, stimulating the emergence of new building blocks. Function optimizing experiment results support the validity of the modification: UCEA-II outperforms UCEA-I and SGA, show strong excellent optimizing performance.3 This dissertation presents a modified genetic algorithm based on competitive coevo-lution (MGACC). MGACC incorporates CEA and genetic algorithm. In MGACC, there are two kinds of fitness: absolute fitness assessed by the individual's chromosome, and the rela-tive fitness assessed by its competitive performance relative to its opponents. Absolute fitness measures an individual's ability to solve a problem. And relative fitness measures an individ-ual's ability to survive. An individual's survival ability is determined by the amount and the characteristic of the opponents it defeats. All the individuals are refined gradually during the endeavor to defeat more opponents or more excellent opponents. Experimental results of function optimization shows that MGACC converges rapidly, and alleviates the problem of premature convergence and maintains the population diversity more effectively, outperform-ing the competing genetic algorithms.4 This dissertation presents a coevolution based code book design algorithm for image vector quantization (CLBG). First, the theory of image vector quantization is described briefly, and then the classical algorithm in image vector quantization, LBG, is introduced. There are three main shortcomings in LBG: (1) the performance of the codebook depends on initial codebook heavily; (2) empty cells exist, in other words, there are codeword including no vec-tor; (3) traditional LBG can only obtain local optimal codebook, but not global optimal code-book. Accordingly three improvements are presented in this chapter: (1) this dissertation pre-sents a novel improvement on codebook design for image vector quantization with the most dispersed codewords in initialization (MDCI). (2) This dissertation presents a new empty cell strategy which is based on maximization the distance between of the code words. (3) Inspired by the universal coevolution in nature ecology, a codebook design algorithm for image vector quantization in described (CLBG), providing a new idea for how to design global optima codebook.