【作者】 蒋培；

【导师】 杨敬安；

【作者基本信息】 合肥工业大学 ， 计算机应用技术， 2001， 博士

【摘要】 仿生学创立于20世纪50年代中期，在仿生学的研究过程中，许多科学家从生物的进化规律中获得了指导人造系统研究的新方法。其代表性工作包括Holland提出的遗传算法，Fogel提出的进化规划，Rechenberg提出的进化策略以及由Koza提出的遗传规划。而其中遗传算法的理论体系和算法结构较为完善并被人们广泛认同。 在现实中，我们遇到的许多问题可以表述成在一个巨大的由测试事例构成的空间中查找正确的解。在这类问题中，对于所有的候选解而言，由于其数目太多而无法对它们进行评估，而且随机的测试事例采样也不能提供有用的信息。对于这种问题，要想正确地评估所有候选解的绝对好坏是一件困难的事情。相反，通过对不同候选解的比较和测试，则可能获得这些候选解的准确和有效的评价，从而揭示候选解中的优缺点。这类问题可以从游戏策略、生物仿真、机器学习以及生化药剂的研制方面得到体现。这就是对抗性问题。 本文第一章为引言部分，对各种进化算法，特别是遗传算法的发展和研究现状进行了综述。 第二章分析了对抗性问题的来源和一些基本特点，并据此给出了该类问题的一般性定义和实际工作中的应用前景。在此基础上，通过分析早期求解方法中出现的一些局限性，并且根据对抗性问题的特点，提出了竞争性共同进化遗传算法（Competitive Coevolutionary Genetic Algorithm，CCGA）的算法模型，用于求解对抗性问题。 第三章从对抗性问题的几个主要方面论证了CCGA的理论依据，证明了该方法在求解对抗性问题的优越性。另外，通过分析模式的全局性和单调性，证明对于某些问题搜索其全局最优模式可以大大缩小解空间，从而导致更快、更顺利地收敛到最优解，并把模式的单调性用于对遗传算法欺骗问题的划分，结合吸收模式的性质，进一步探讨影响遗传算法困难的模式因素。本章提出了一些定理，并给出了这些定理的详细证明，对今后的遗传算法设计具有一定的指导意义。 第四章根据CCGA的特点，提出了无限群体的概念，并在此概念的基础上就对抗性问题设计了几种独特的方法，这些方法包括：共享适应值、基因连锁、 摘 要自适应变异、虚幻寄生体、精英群体、共享采样和同胞选择等，然后从理论和实验上对这些方法给予的充分说明和论证。这些方法从不同的角度对对抗性问题的难点问题提供了解决方案，有利于对抗性问题的求解。 本文第五章利用前面章节给出的CCGA算法模型和方法对两个对抗性问题进行实验。其中一个问题为细胞自动机的规则学习，属于机器学习范畴。在我们的实验中对其稍加转换，构成了对抗性问题。另一个则是追逃oursuer工vader）实验，这是一个生物环境的模拟仿真，是一类典型的复杂对抗性问题。通过对仿真实验结果的分析，指出了CCGA的一些设计要点，并验证 f了CCGA对对抗性问题求解的有效性。 第六章对CCGA和对抗性问题的一些特性做了深入的探讨，这些探讨主要是借鉴一些生物学的研究成果来拓展CCGA的算法性能，包括CCGA在生物学上的意义、物种间的军备竞赛以及进化阶梯的作用等。 论文最后一章先对全文进行了总结，然后，提出了几个以后值得关注的研究方向，以期对CCGA的研究有更进一步的了解，也希望给今后的研究工作带来启示和借鉴。更多还原

【Abstract】 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更多还原