Research On Informative Dimension Based Coevolutionary Algorithms

Coevolutionary algorithms, based on coevolutionary mechanisms among correlated species in ecology, have been introduced as an extension of the evolutionary algorithm. CEAs have a lot of potential in terms of addressing complex problems which are difficult for traditional EAs. In Machine Learning, there are many problems with no intrinsic objective measure, such as concept learning, game-playing, in which candidate solutions are evaluated based on their performance on tests. The number of possible tests in such problems is typically very large, evaluating an individual on all possible tests is therefore generally infeasible, and using a small fixed set of tests is prone to overfitting. Coevolution evolves simultaneously candidate solutions and tests, in which the fitness of an individual is based on direct competition with individuals of other species, and can thereby in principle provide an effective approach to addressing problems of this kind.Since evaluation in coevolution is based on evolving individuals, coevolution setups can suffer from inaccurate evaluation, leading to problems such as overspecialization and cycling. Therefore, how to organize this dynamic setup to yield reliable and effective search methods is a central challenge in coevolution research.Studies have shown that there exists an implicit set of informative dimensions within test-based problem domains, evaluation information can be compressed into a potentially small set of dimensions. Each dimension is viewed as an underlying objective, individuals are evaluated in the sense of evolutionary multi-objective optimization. In the dissertation, studies are mainly focused on improving the reliability and efficiency of coevolution algorithms, combined with dimension structures of problem domains, several new reliable coevolution algorithms for "test-based" problems are proposed. The main works can be summarized as follows.(1) A common technique in coevolution aimed at improving reliability is the use of archive. The archive sizes in current reliable methods are generally too large, limiting their practical application. Aimed at this issue, a coevolutionary archive scheme based on dimension identifying is proposed. During execution, by dimension identifying, the scheme maintains only the highest tests found so far in each dimension, and at the same time, selects to reserve solution-individuals by viewing these tests as evaluation objective, so as to prevent evolution from backsliding along each dimension. The archive is minimized while maintaining reliability. Dimension identifying is the key to the scheme. Corresponding to the different classes of problems, two dimension identifying methods and their suited algorithms are presented. One algorithm is for the "COMPARE-ON-ONE" kind of problems, named EPCA; another algorithm is for the "COMPARE-ON-ALL" kind of problems, named DI-CA. Experiments demonstrate that the efficiency and performance of two algorithms are greatly improved.(2) An online dimension extraction approach is proposed. The approach extracts the dimension system according to the characteristic outcome relationships among individuals, and then revises the dimension system by right of the property that tests on the same dimension are ordered by strictness. Therefore, the extracted dimension system is more accurate. Based on this approach, a coevolutionary algorithm with dimension extraction named PCA-DE is put forward. During execution, PCA-DE synchronously extracts the dimensions of the problem, and utilizes them to provide accurate evaluation for solution-individuals and to guide selection and reservation, thus guaranteeing monotonic progress. Experimental results demonstrate the feasibility of the proposed algorithm, and show that it outperforms other existing similar algorithms in both performance and accuracy of dimension extraction.(3) In order to reduce the condition of dimension extraction, a bidirectional dimension extraction scheme based on uncertain method is proposed. A coevolution archive algorithm based on bidirectional dimension extraction is designed, named CA-BDE. CA-BDE extracts dimensions from both sides of candidate solutions and tests, and then selects only tests and high-performance candidate solutions that possess dimension representative features to be resided in archives, so as to maintain progress along various dimensions. CA-BDE prevents archives from growing overly large. Comparing with other methods, the applicability of CA-BDE is greatly increased. Experimental results demonstrate that CA-BDE maintains relatively small archives during execution and outperforms other existing similar algorithms in performance.