| Bionics was founded in the mid-1950s. During the process of bionic research, many scientists obtained from the theories of biological evolution some novel methods that can guide the research on artificial systems. These methods included Genetic Algorithms, Evolutionary Programming, Evolutionary Strategy and Genetic Programming. Since the theoretical and algorithmic research on genetic algorithms is more extensive with better results gained than the others, this method has been widely accepted.In practice, we may meet many problems which can be formulated as the search for a correct solution over a large space of test cases. In such problems, there are too many test cases to evaluate all the candidates, and a random sampling of test cases can be uninformative. This makes accurate evaluation of candidate solutions difficult. By contrast, accurate and efficient evaluations can be obtained by comparing and testing different solutions to expose their advantages and flaws. This sort of problems includes game-playing strategies, biologic simulations, machine learning, and biochemical medicament development. This is the Adversarial Problem.The first chapter of this dissertation is the introduction. We summarize the development and actuality of evolutionary algorithm research, especially about genetic algorithms.The second chapter makes research on the derivation and characters of adversarial problem, gives it a general definition, and describes the prospect of it. Then, according to the characters of adversarial problems and the limitations of previous methods, we present an algorithmic model of CCGA (Competitive Coevolutionary Genetic Algorithm) for adversarial problems solving.The third chapter gives some theoretic foundations of CCGA from several aspects, and proves its advantages for adversarial problems solving. In addition, we make research on the convergence of Genetic Algorithms by analyzing the globality and monotonicity of the schemata. It is demonstrated that for some kinds of the problems, the method of searching global best schemata can greatly decrease theIxAbstractsolution space and lead to converging quickly and successfully to the optimum. The monotonicity of schemata is used to determine deceptive problems and, with the aid of absorbing schemata, to analyze the schematic factors leading to GA-hard problems. In this chapter, some theorems are proposed and detailed proofs of these theorems are presented. These proofs will guide our CCGA designs for the future.The fourth chapter presents a concept of infinite population according to the features of CCGA, and designs some particular methods for adversarial problems solving based on this concept. These methods include shared fitness, gene linkage, self-adapted mutation, phantom parasite, elitist population, shared sampling and brood selection. Then we give the explanation and argumentation of these methods in theory and in experiment. These methods give solutions of adversarial problems by focusing on different points of view, and are of great advantage to adversarial problems solving.The fifth chapter gives two demonstrations of adversarial problems solving by using the algorithmic model and methods of CCGA. One of them is a learning task of cellular automata rules. We translate this task from a machine learning problem to an adversarial problem. Another is a typical complex adversarial problem - a pursuer-evader experiment which is a simulation of biologic environment. From the analysis of these two experiments, we give some essentials for CCGA design, and illustrate the efficiency of CCGA in adversarial problems solving.In the sixth chapter, we discuss several additional issues about CCGA, including biological implications, arms race among species, and evolutionary pedagogy.In the seventh and final chapter, first we give a summary of this dissertation, then we propose several noteworthy issues. These issues may help us gain a better understanding of CCGA, and may shed some light o...
|
PDF Full Text Request