基于竞争性共同进化遗传算法求解对抗性问题
|
摘要
仿生学创立于20世纪50年代中期，在仿生学的研究过程中，许多科学家
从生物的进化规律中获得了指导人造系统研究的新方法。其代表性工作包括
Holland提出的遗传算法，Fogel提出的进化规划，Rechenberg提出的进化策略
以及由Koza提出的遗传规划。而其中遗传算法的理论体系和算法结构较为完
善并被人们广泛认同。
在现实中，我们遇到的许多问题可以表述成在一个巨大的由测试事例构成
的空间中查找正确的解。在这类问题中，对于所有的候选解而言，由于其数目
太多而无法对它们进行评估，而且随机的测试事例采样也不能提供有用的信息。
对于这种问题，要想正确地评估所有候选解的绝对好坏是一件困难的事情。相
反，通过对不同候选解的比较和测试，则可能获得这些候选解的准确和有效的
评价，从而揭示候选解中的优缺点。这类问题可以从游戏策略、生物仿真、机
器学习以及生化药剂的研制方面得到体现。这就是对抗性问题。
本文第一章为引言部分，对各种进化算法，特别是遗传算法的发展和研究
现状进行了综述。
第二章分析了对抗性问题的来源和一些基本特点，并据此给出了该类问题
的一般性定义和实际工作中的应用前景。在此基础上，通过分析早期求解方法
中出现的一些局限性，并且根据对抗性问题的特点，提出了竞争性共同进化遗
传算法（Competitive Coevolutionary Genetic Algorithm，CCGA）的算法模型，用于
求解对抗性问题。
第三章从对抗性问题的几个主要方面论证了CCGA的理论依据，证明了该
方法在求解对抗性问题的优越性。另外，通过分析模式的全局性和单调性，证
明对于某些问题搜索其全局最优模式可以大大缩小解空间，从而导致更快、更
顺利地收敛到最优解，并把模式的单调性用于对遗传算法欺骗问题的划分，结
合吸收模式的性质，进一步探讨影响遗传算法困难的模式因素。本章提出了一
些定理，并给出了这些定理的详细证明，对今后的遗传算法设计具有一定的指
导意义。
第四章根据CCGA的特点，提出了无限群体的概念，并在此概念的基础上
就对抗性问题设计了几种独特的方法，这些方法包括：共享适应值、基因连锁、
摘 要
自适应变异、虚幻寄生体、精英群体、共享采样和同胞选择等，然后从理论和
实验上对这些方法给予的充分说明和论证。这些方法从不同的角度对对抗性问
题的难点问题提供了解决方案，有利于对抗性问题的求解。
本文第五章利用前面章节给出的CCGA算法模型和方法对两个对抗性问
题进行实验。其中一个问题为细胞自动机的规则学习，属于机器学习范畴。在
我们的实验中对其稍加转换，构成了对抗性问题。另一个则是追逃
oursuer工vader）实验，这是一个生物环境的模拟仿真，是一类典型的复杂对抗
性问题。通过对仿真实验结果的分析，指出了CCGA的一些设计要点，并验证
f
了CCGA对对抗性问题求解的有效性。
第六章对CCGA和对抗性问题的一些特性做了深入的探讨，这些探讨主要
是借鉴一些生物学的研究成果来拓展CCGA的算法性能，包括CCGA在生物
学上的意义、物种间的军备竞赛以及进化阶梯的作用等。
论文最后一章先对全文进行了总结，然后，提出了几个以后值得关注的研
究方向，以期对CCGA的研究有更进一步的了解，也希望给今后的研究工作带
来启示和借鉴。
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 the
Ix
Abstract
solution 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
从生物的进化规律中获得了指导人造系统研究的新方法。其代表性工作包括
Holland提出的遗传算法，Fogel提出的进化规划，Rechenberg提出的进化策略
以及由Koza提出的遗传规划。而其中遗传算法的理论体系和算法结构较为完
善并被人们广泛认同。
在现实中，我们遇到的许多问题可以表述成在一个巨大的由测试事例构成
的空间中查找正确的解。在这类问题中，对于所有的候选解而言，由于其数目
太多而无法对它们进行评估，而且随机的测试事例采样也不能提供有用的信息。
对于这种问题，要想正确地评估所有候选解的绝对好坏是一件困难的事情。相
反，通过对不同候选解的比较和测试，则可能获得这些候选解的准确和有效的
评价，从而揭示候选解中的优缺点。这类问题可以从游戏策略、生物仿真、机
器学习以及生化药剂的研制方面得到体现。这就是对抗性问题。
本文第一章为引言部分，对各种进化算法，特别是遗传算法的发展和研究
现状进行了综述。
第二章分析了对抗性问题的来源和一些基本特点，并据此给出了该类问题
的一般性定义和实际工作中的应用前景。在此基础上，通过分析早期求解方法
中出现的一些局限性，并且根据对抗性问题的特点，提出了竞争性共同进化遗
传算法（Competitive Coevolutionary Genetic Algorithm，CCGA）的算法模型，用于
求解对抗性问题。
第三章从对抗性问题的几个主要方面论证了CCGA的理论依据，证明了该
方法在求解对抗性问题的优越性。另外，通过分析模式的全局性和单调性，证
明对于某些问题搜索其全局最优模式可以大大缩小解空间，从而导致更快、更
顺利地收敛到最优解，并把模式的单调性用于对遗传算法欺骗问题的划分，结
合吸收模式的性质，进一步探讨影响遗传算法困难的模式因素。本章提出了一
些定理，并给出了这些定理的详细证明，对今后的遗传算法设计具有一定的指
导意义。
第四章根据CCGA的特点，提出了无限群体的概念，并在此概念的基础上
就对抗性问题设计了几种独特的方法，这些方法包括：共享适应值、基因连锁、
摘 要
自适应变异、虚幻寄生体、精英群体、共享采样和同胞选择等，然后从理论和
实验上对这些方法给予的充分说明和论证。这些方法从不同的角度对对抗性问
题的难点问题提供了解决方案，有利于对抗性问题的求解。
本文第五章利用前面章节给出的CCGA算法模型和方法对两个对抗性问
题进行实验。其中一个问题为细胞自动机的规则学习，属于机器学习范畴。在
我们的实验中对其稍加转换，构成了对抗性问题。另一个则是追逃
oursuer工vader）实验，这是一个生物环境的模拟仿真，是一类典型的复杂对抗
性问题。通过对仿真实验结果的分析，指出了CCGA的一些设计要点，并验证
f
了CCGA对对抗性问题求解的有效性。
第六章对CCGA和对抗性问题的一些特性做了深入的探讨，这些探讨主要
是借鉴一些生物学的研究成果来拓展CCGA的算法性能，包括CCGA在生物
学上的意义、物种间的军备竞赛以及进化阶梯的作用等。
论文最后一章先对全文进行了总结，然后，提出了几个以后值得关注的研
究方向，以期对CCGA的研究有更进一步的了解，也希望给今后的研究工作带
来启示和借鉴。
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 the
Ix
Abstract
solution 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
引文
[1] Holland J H. Adaption in Natural and Artificial Systems. Ann Arbor Univ. of Michigan Press, 1975
[2] Goldberg D E. Genetic Algorithms in Search, Optimization, Machine Learning. MA: Addison Wesley, 1989
[3] Fogel David B. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, 1995.
[4] 席裕庚，柴天佑，恽为民．《遗传算法综述．控制》，理论与应用，1996，13(6)：697～708
[5] Schraudolph N. N., Belew R. K. Dynamic Parameter Encoding for Genetic Algorithms. Machine Learning 1992(9): 9～21
[6] 恽为民，席裕庚．《遗传算法的收敛性和计算效率分析》．控制理论与应用，1996，13(4)：455～460
[7] Janikov C. Z. and Michalewicz. Z. An Experimental Comparison of Binary and Floating Point representation in Genetic Algorithm. ICGA4. Betew R. K. and Booker L. B., Eds, CA: Morgan-Kaufmann, 1991, 31-36.
[8] Michalewicz Z. and Janikov C. Z. A Handling Constraints in Genetic Algorithms. ICGA4, Betew R. K. and Booker L. B., Eds. CA: Morgan-Kaufmann, 1991, 151-157.
[9] Kuo T. and Hwang S. Y. A Genetic Algorithm with Disruptive Selection. IEEE Transactions on Sys., Man, and Cybernetics, Part B: Cybernetics, 1996, (26): 299-307.
[10] Syswerda G, Uniform Crossover in Genetic Algorithms. ICGA3, Schaffer J. D. ed, CA: Morgan-Kaufmann. 1989, 2-9.
[11] Ackley D. H., A Connectionist Machine for Genetic Hill-climbing. Boston, MA: Kluwer, 1987.
[12] Kreinovic V., Quintana C., and Fuentes O., Genetic Algorithms: What Fitness Scaling is Optimal? Cybernrtics and Systems: An International Journal, 1993, (24): 9-26.
[13] Forrest S. Documentation for PRISONERS DILEMMA and NORMS Programs that Use the Genetic Algorithm. Unpublished manuscript, University of Michigan, Ann Arbor, 1985.
[14] Baker J. E. Adaptive Selection Methods for Genetic Algorithms. Proceeds of International Conference on Genetic Algorithms and Their Applications, Pittsburgh P. A.. J. Grefenstette, Eds, 1985, 101-111
[15] Gillies A.M. Machine Learning Procedures for Generating Image Domain Feature Detectors. Doctoral Dissertation, University of Michigan, Ann Arbor. 1985.
[16] Hopfield, J. J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities. Proc. Natl. Acad. Sci., 1982, (79): 2554-2558
[17] Davidor Y, Genetic Algorithms and Robotics: A Heuristic Strategy for Optimization. Singapore: World Scientific, 1993
[18] Grefenstette John J. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. on Sys., Man., & Cybernetics, 1986, (1): 122～128
[19] Miller John A., Potter Walter D., Gandham Ravi V., et al. An Evaluation of Local Improvement Operators for Genetic Algorithms. IEEE Trans on Sys., Man., & Cybernetics, 1993 (5): 1340～1350
[20] 丁承民，张传生，刘贵忠．《利用正交试验法优化配置遗传算法控制参数》．西安交通大学电子与信息工程学院信息工程研究所研究报告，1996
[21] Srinivas M., Patnaik L. M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms. IEEE Trans on Sys., Man., & Cybernetics, 1994, (4): 656～667
[22] 章珂，刘贵忠．《杂交位置非等概率选取的遗传算法》．西安交通大学电子与信息工程学院信息工程研究所研究报告，1996
[23] Hillis D. W. Coevolving Parasites Improve Simulated Evolution as an Optimization Proceduce. Aritificail Life Ⅱ, SFI Studies in the Sciences of Complexity, Langton C. G. ed., Addison-Wesley Press, 1991, 313～324
[24] Rosin C. D., Belew R. K. Methods for Competitive Coevolution: Finding Opponents worth beating. ICGA6, Rumelhart D. E. ed., CA: Morgan-Laufmann, 1995, 373～380
[25] Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton University Press, 1944.
[26] Mehlmann. Applied Differential Games. Plenum, 1988.
[27] Fudenberg D., Levine D. K.. Theory of Learning in Games. published online at http://levine.sscnet.ucla.edu/Papers/CONTENTS.HTM, 1997.
[28] Cohn, D.A., Z. Ghahramani, and M.I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 1996, 4:129～145
[29] Plutowki M. and H. White. Selecting concise training sets from clean data. IEEE Transactions on Neural Networks, March 1993, 4(2):305～318
[30] Bshouty N.H., Cleve R., Kannan S., Tamon C. Oracles and Queries that are Sufficient for Exact Learning. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 94. ACM, 1994.
[31] Berlekamp E.R., Conway J.H., Guy R.K.. Winning Ways for Your Mathemalical Plays. Academic Press, 1982.
[32] Tesauro G.. Temporal Difference Learning and TD-Gammon. Communications of the ACM, 1995, 38(3):58--68,
[33] Walker S., Lister R., Downs T.. Temporal difference, non-determinism, and noise: a case study on the 'Othello' board game. In M. Marinaro et al., eds, ICANN ’94. Berlin: Springer-Verlag, 1994.
[34] Chuen-Tsai Sun, Ying-Hong Liao, Jing-Yi Lu, and Fu-May Zheng. Genetic Algorithm Learning in Game Playing with Multiple Coaches. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press, 1994.
[35] Epstein S.L.. Toward an Ideal Trainer. Machine Learning, June 1994, 15(3):251--277
[36] Angeline P. J., Pollack J. B.. Competitive Environments Evolve Better Solutions for Complex Tasks. In Forrest S. ed. ICGA 5. CA: Morgan-Kaufmann, 1993.
[37] Grosso P. B. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Inter-
action in a Multilocus Model. Ph. D. thesis, University of Michigan, 1985
[38] Tanese R. Parallel Genetic Algorithms for a hypercube, Genetic Algorithms and their Application: ICGA 2, Lawrence Erbaum Associates, 1987,177-183
[39] Starkweather T., Whitley D., Mathias K. Optimization Using Distributed Genetic Algorithms. PPSN 1, Berlin: Springer-Verlag, Schwefel H-P, Manner Red, 1991, 176-186
[40] Muhlenbein H., Schomisch M., Born J. The Parallel Genetic Algorithm as Function Optimizer. Parallel Computing, 1991,17(6-7) : 619
[41] Cantu-Paz E., Mejia-Olvera M. Experimental Results in Distributed Genetic Algorithms. Int. Symp. on Applied Corporate Computing, Mnterrey, Mexico, 1994,99-108
[42] Munetomo M., Takai Y., Sato Y. An Efficient Migration Scheme for Subpopulation-based Asynchronously Parallel Genetic Algorithms. ICGA5, Forrest S. ed, CA: Morgan-Kaufmann, 1993,649
[43] Braun H. On Solving Trasvelling Salesman Problems by Genetic Algorithms. PPSN1, Berlin: Springer-Verlag, Schwefel H_P, Manner Red, 1991, 129-133
[44] Kroger B., Schwenderling P., Vomberger O. Parallel Genetic Packing of Rectangles. PPSNI, Berlin: Springer-Verlag, Schwefel HJP, Manner Red, 1991, 160-164
[45] Pettey C. B., Leuze M. R., Grefenstette J. J. A Parallel Genetic Algorithm. ICGA2, Lawrence Erlbaum Associates, Grefeenstette J. J. ed., 1987,155-161
[46] Pettey C. B., Leuze M. R. A Theoretical Investigation of a Parallel Genetic Algorithm. ICGA3, Belew R. K., Booker L R., ed., CA: Morgan-Kaufmann, 1989,398-405
[47] Gordon V. S., Whitley D. Serial and Parallel Genetic Algorithms as Function Optimizers. ICGA4, Forrest S. ed., CA: Morgan-kaufmann, 1993,177-183
[48] Collins R. J., Jefferson D. R. Selection in Massively Parallel Genetic Algorithms. ICG A3, Belew R. K., ed., CA: Morgan-Kaufmann, 1991,249-256
[49] Spiessens P., Manderick B. A Massively Parallel Genetic Algorithm: Implementation and First Ananlysis. 1CGA4, Belew R. K., ed., CA: Morgan-Kaufmann, 1991,279-286
[50] Sarma J., Jong K. D. An Analysis of the Effects of Neighbourhood Size and Shape on Local Selection Algorithms. PPSN IV, Berlin: Springer-Verlag, 1995,236-244
[51] Husbands P., Mill F. Simulated Coevolution as the Mechanism for Emergent Planning and Scheduling. 1CGA4, Belew R. K., ed., CA: Morgan-Kaufmann, 1991, 264-270
[52] Paredis J. The Symbiotic Evolution of Solutions and their Representations. ICGA6, Eshel-man L. ed., CA: Morgan-Kaufmann, 1995, 359-365
[53] Axelrod R.. Evolution of Strategies in the Iterated Prisoner's Dilemma. In Davis L., ed. Genetic Algorithms and Simulated Annealing. CA: Morgan-Kaufmann, 1989．
[54] Sims K. Evolving 3d Morphology and Behavior by Competition. In Brooks R. A. et al., eds. Artificial Life IV. MA: MIT Press, 1994．
[55] Pollack J., Blair A., Land M. Coevolution of a Backgammon Player. In Artificial Life V, 1996．
[56] Sebald A.V., Schlenzig J. Minimax Design of Neural Net Controllers for Highly Uncertain Plants. IEEE Trans, on Neural Networks, January 1994, 5(l):73-82
[57] Potter M.A. The Design and Analysis of a Computational Model of Cooperative Coevolution. PhD thesis, George Mason University, 1997．
[58] Anthony M., Brightwell G., Cohen D., Shawe-Laylor J. On Exact Specification by Examples. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 1992
[59] Goldman S.A, Kearns M.J. On the Complexity of Teaching. In Warmuth M.K. et al., eds, Proceedings of the Fourth Annual Workshop on Computational Learning Theory. CA: Morgan-Kaufmann, 1991
[60] Southwell R. V. Relaxation Methods in Theoretical Physics. Oxford: Clarendon Press. 1946
[61] Firedman M., Savage L. S., Planning Experiments Seeking Maxima. Selected Techniques of Statistical Analysis for Scientific and Industrial Research, and Production and Management Engineering, Eisenhart M. W. eds. 1947, 363～372
[62] Kauffman S. A., Johnsen S. Coevolution to the Edge of Chaos: Coupled Fitness Landscapes, Posed States, and Coevolutionary Avalanches. Artificial Life Ⅱ, SFI Studies in the Sciences of Complexit, Langton C. G. eds. 1991, vol(10), 325～369
[63] Van Valen L. A New Evolutionary Law, Evolutionary Theory 1, 1973, 1-30
[64] Samuel A. L. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development, 1959, 3(3), 210～229
[65] Rudolph G. Convergence Properties of Canonical Genetic Algorithms. IEEE Trans. on Neural Networks, 1994, 5(1): 96～101
[66] Qi X., Palmieri F. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space Part Ⅰ: Basic Properties of Selection and Mutation. IEEE Trans. on Neural Networks, 1994, 102～119
[67] Goldman R. Introduction to Stochastic Models. Reading, MA: Benjamin / Cummings, 1988.
[68] Fogel D. B. Asymptotic Convergence Properties of Genetic Algorithms and Evolutionary Programming: Analysis and Experiments. Cybernetics and Systems, 25, 1994, 389-407
[69] 陈国良、王煦法、庄镇泉、王东生，《遗传算法及其应用》，人民邮政出版社，1996
[70] 蒋培，黄焱，杨敬安，关于遗传算法收敛性的分析，《湖南师范大学学报》，Vol．22(1)，1999
[71] Michael D. V. Generalizing the Notion of Schema in Genetic Algorithms. Artificial Intelligence, 50(3), 1991, 385-396
[72] Davis L., Ed. Handbook of Genetic Algorithm. New York: Van Nostrand Reinhold, 1991.
[73] Liepins G. E, Vose M. D. Representational Issue in Genetic Optimization. Journal of Experimental and Theoretical. Artificial Intelligence, 10(2), 1991, 101-115.
[74] Whitley L. D. Foundations of Genetic Algorithms. San Mateo, CA: Morgan-Kaufmann, 1991.
[75] Goldberg D. E. Genetic Algorithms and Simulated Annealing. Los Altos, CA: Morgan Kaufman, 1987, 74-88.
[76] 王丽薇、洪勇、洪家荣，《遗传算法的收敛性研究》，《计算机学报》，19(10)，1996，794-797
[77] 黄焱，蒋培，王嘉松，杨敬安，《基于可调变异算子求解遗传算法的欺骗问题》，《软件学报》，1999，2(10)，216-219
[78] Lindgren K., Nordahl M.G. Artificial Food Webs. In Artificial Life Ⅲ, 1994
[79] Goldberg D. E., Richardson J. Genetic Algorithms with Sharing for Multimodal Function Optimization. In Grefenstette J. J., Ed., ICGA 2, L. Ertbaum Assoc., 1987
[80] Smith R.E., Forrest S., Perelson A.S. Searching for Diverse, Cooperative Populations with Genetic Algorithms. Evolutionary Computation, 1993, 1(2):
[81] Giordana A. Neri F. Search-intensive Concept Induction. Evolutionary Computation, 1995, 3(4):
[82] 刘祖洞，《遗传学》，高等教育出版社
[83] 蒋培，王洪燕，杨敬安，关于进化算法中连锁的分析，《合肥工业大学学报》，Vol．23(4)，2000，1-5
[84] Michalski R. S., Carbonell J. G., Mitchell T. M., Machine Learning, an Artificial Intelligence Approach, Springer-Verlag, 1993
[85] Goldberg D. E. Computer-aided Gas Pipeline Operation Using Genetic Algorithm and Rule Learning, Engineering with Computers, 1987, 47～58
[86] Tackett W.A., Carmi A. The Unique Implications of Brood Selection for Genetic Programming. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE, 1994
[87] Mitchell M. Machine Learning. NY: McGraw-Hill, 1997, 249-270
[88] 蒋培，王洪燕，王漫，杨敬安，基于竞争性协同进化算法求解对抗性问题，PACMA 2000’，235-238
[89] Land, M. Belew, R K. No Prefect Two-State Cellular Automata For Density Classification Exists. Physical Review Letters, 1995, 74(25): 1548-1550
[90] Mitchell M., Crutchfield J. P. and Peter T. H. Evolving Cellular Automata To Perform Computations: Mechanisms And Impediments. Physica 1994, D75, 361-391.
[91] Das R., Mitchell M. and Crutchfield J. P. A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata. In: Parallel Problem Solving from Nature Ⅲ, LNCS 866. Berlin: Springer-Verlag. 1994, 344-353.
[92] Andre D., Bennett F. H. and Koza J. R. Evolution Of Intricate Long-Distance Communication Signals In Cellular Automata Using Genetic Programming. In: Proceedings of the Fifth Artificial Life Conference. 1996, 16-18.
[93] 蒋培，王洪燕，杨敬安，人工生命仿真的分析，《长沙铁道学院学报》，Vol．17(2)，1999，34-39
[94] 王洪燕 杨敬安 蒋培，基于生长神经网络的进化机器人行为研究，《电子学报》，Vol．28，No．12，2000
[95] D. Cliff, G. Miller, Co-evolution of Pursuit and Evasion H: Simulation Methods and Resuits, SAB96, MIT Press Bradford Books 1996
[96] Futuyma D.J., Slatkin D.K. Coevolution. Sinauer, 1983.
[97] Dawkins R. and J.R. Krebs. Arms races between and within species. Proceedings of the Royal Society of London B, 205:489--511, September 1979.
[98] Bakker R.T. The Wolf Pursues: Incongruencies in Predator-prey Coevolution. In Futuyma D.J. and M. Slatkin, eds., Coevolution, Sinauer 1983
[99] Condra J.H. and E.A. Emini. Preventing HIV-1 drug resistance. Science & Medicine, January/February 1997.
[100] Jerison H.J, Evolution of the Brain and Intelligence. Academic Press, 1973.
[101] May R.M. and R.M. Anderson. Parasite-Host coevolution. In D.J. Futuyma and M. Slatkin, eds., Coevolution. Sinauer, 1983.
[102] 王洪燕，基于神经网络的进化机器人行为集成方法的研究，博士学位论文，合肥工业大学，2000
[103] McInerney J. Biologically Influenced Algorithms and Parallelism in Non-linear Optimization. Ph.D. thesis, University of California, San Diego, 1992.
[104] 王洪燕，杨敬安，蒋培，基于神经网络的进化机器人组合行为方法研究，《计算机研究与发展》，Vol．37，2000
[2] Goldberg D E. Genetic Algorithms in Search, Optimization, Machine Learning. MA: Addison Wesley, 1989
[3] Fogel David B. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, 1995.
[4] 席裕庚，柴天佑，恽为民．《遗传算法综述．控制》，理论与应用，1996，13(6)：697～708
[5] Schraudolph N. N., Belew R. K. Dynamic Parameter Encoding for Genetic Algorithms. Machine Learning 1992(9): 9～21
[6] 恽为民，席裕庚．《遗传算法的收敛性和计算效率分析》．控制理论与应用，1996，13(4)：455～460
[7] Janikov C. Z. and Michalewicz. Z. An Experimental Comparison of Binary and Floating Point representation in Genetic Algorithm. ICGA4. Betew R. K. and Booker L. B., Eds, CA: Morgan-Kaufmann, 1991, 31-36.
[8] Michalewicz Z. and Janikov C. Z. A Handling Constraints in Genetic Algorithms. ICGA4, Betew R. K. and Booker L. B., Eds. CA: Morgan-Kaufmann, 1991, 151-157.
[9] Kuo T. and Hwang S. Y. A Genetic Algorithm with Disruptive Selection. IEEE Transactions on Sys., Man, and Cybernetics, Part B: Cybernetics, 1996, (26): 299-307.
[10] Syswerda G, Uniform Crossover in Genetic Algorithms. ICGA3, Schaffer J. D. ed, CA: Morgan-Kaufmann. 1989, 2-9.
[11] Ackley D. H., A Connectionist Machine for Genetic Hill-climbing. Boston, MA: Kluwer, 1987.
[12] Kreinovic V., Quintana C., and Fuentes O., Genetic Algorithms: What Fitness Scaling is Optimal? Cybernrtics and Systems: An International Journal, 1993, (24): 9-26.
[13] Forrest S. Documentation for PRISONERS DILEMMA and NORMS Programs that Use the Genetic Algorithm. Unpublished manuscript, University of Michigan, Ann Arbor, 1985.
[14] Baker J. E. Adaptive Selection Methods for Genetic Algorithms. Proceeds of International Conference on Genetic Algorithms and Their Applications, Pittsburgh P. A.. J. Grefenstette, Eds, 1985, 101-111
[15] Gillies A.M. Machine Learning Procedures for Generating Image Domain Feature Detectors. Doctoral Dissertation, University of Michigan, Ann Arbor. 1985.
[16] Hopfield, J. J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities. Proc. Natl. Acad. Sci., 1982, (79): 2554-2558
[17] Davidor Y, Genetic Algorithms and Robotics: A Heuristic Strategy for Optimization. Singapore: World Scientific, 1993
[18] Grefenstette John J. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. on Sys., Man., & Cybernetics, 1986, (1): 122～128
[19] Miller John A., Potter Walter D., Gandham Ravi V., et al. An Evaluation of Local Improvement Operators for Genetic Algorithms. IEEE Trans on Sys., Man., & Cybernetics, 1993 (5): 1340～1350
[20] 丁承民，张传生，刘贵忠．《利用正交试验法优化配置遗传算法控制参数》．西安交通大学电子与信息工程学院信息工程研究所研究报告，1996
[21] Srinivas M., Patnaik L. M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms. IEEE Trans on Sys., Man., & Cybernetics, 1994, (4): 656～667
[22] 章珂，刘贵忠．《杂交位置非等概率选取的遗传算法》．西安交通大学电子与信息工程学院信息工程研究所研究报告，1996
[23] Hillis D. W. Coevolving Parasites Improve Simulated Evolution as an Optimization Proceduce. Aritificail Life Ⅱ, SFI Studies in the Sciences of Complexity, Langton C. G. ed., Addison-Wesley Press, 1991, 313～324
[24] Rosin C. D., Belew R. K. Methods for Competitive Coevolution: Finding Opponents worth beating. ICGA6, Rumelhart D. E. ed., CA: Morgan-Laufmann, 1995, 373～380
[25] Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton University Press, 1944.
[26] Mehlmann. Applied Differential Games. Plenum, 1988.
[27] Fudenberg D., Levine D. K.. Theory of Learning in Games. published online at http://levine.sscnet.ucla.edu/Papers/CONTENTS.HTM, 1997.
[28] Cohn, D.A., Z. Ghahramani, and M.I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 1996, 4:129～145
[29] Plutowki M. and H. White. Selecting concise training sets from clean data. IEEE Transactions on Neural Networks, March 1993, 4(2):305～318
[30] Bshouty N.H., Cleve R., Kannan S., Tamon C. Oracles and Queries that are Sufficient for Exact Learning. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 94. ACM, 1994.
[31] Berlekamp E.R., Conway J.H., Guy R.K.. Winning Ways for Your Mathemalical Plays. Academic Press, 1982.
[32] Tesauro G.. Temporal Difference Learning and TD-Gammon. Communications of the ACM, 1995, 38(3):58--68,
[33] Walker S., Lister R., Downs T.. Temporal difference, non-determinism, and noise: a case study on the 'Othello' board game. In M. Marinaro et al., eds, ICANN ’94. Berlin: Springer-Verlag, 1994.
[34] Chuen-Tsai Sun, Ying-Hong Liao, Jing-Yi Lu, and Fu-May Zheng. Genetic Algorithm Learning in Game Playing with Multiple Coaches. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press, 1994.
[35] Epstein S.L.. Toward an Ideal Trainer. Machine Learning, June 1994, 15(3):251--277
[36] Angeline P. J., Pollack J. B.. Competitive Environments Evolve Better Solutions for Complex Tasks. In Forrest S. ed. ICGA 5. CA: Morgan-Kaufmann, 1993.
[37] Grosso P. B. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Inter-
action in a Multilocus Model. Ph. D. thesis, University of Michigan, 1985
[38] Tanese R. Parallel Genetic Algorithms for a hypercube, Genetic Algorithms and their Application: ICGA 2, Lawrence Erbaum Associates, 1987,177-183
[39] Starkweather T., Whitley D., Mathias K. Optimization Using Distributed Genetic Algorithms. PPSN 1, Berlin: Springer-Verlag, Schwefel H-P, Manner Red, 1991, 176-186
[40] Muhlenbein H., Schomisch M., Born J. The Parallel Genetic Algorithm as Function Optimizer. Parallel Computing, 1991,17(6-7) : 619
[41] Cantu-Paz E., Mejia-Olvera M. Experimental Results in Distributed Genetic Algorithms. Int. Symp. on Applied Corporate Computing, Mnterrey, Mexico, 1994,99-108
[42] Munetomo M., Takai Y., Sato Y. An Efficient Migration Scheme for Subpopulation-based Asynchronously Parallel Genetic Algorithms. ICGA5, Forrest S. ed, CA: Morgan-Kaufmann, 1993,649
[43] Braun H. On Solving Trasvelling Salesman Problems by Genetic Algorithms. PPSN1, Berlin: Springer-Verlag, Schwefel H_P, Manner Red, 1991, 129-133
[44] Kroger B., Schwenderling P., Vomberger O. Parallel Genetic Packing of Rectangles. PPSNI, Berlin: Springer-Verlag, Schwefel HJP, Manner Red, 1991, 160-164
[45] Pettey C. B., Leuze M. R., Grefenstette J. J. A Parallel Genetic Algorithm. ICGA2, Lawrence Erlbaum Associates, Grefeenstette J. J. ed., 1987,155-161
[46] Pettey C. B., Leuze M. R. A Theoretical Investigation of a Parallel Genetic Algorithm. ICGA3, Belew R. K., Booker L R., ed., CA: Morgan-Kaufmann, 1989,398-405
[47] Gordon V. S., Whitley D. Serial and Parallel Genetic Algorithms as Function Optimizers. ICGA4, Forrest S. ed., CA: Morgan-kaufmann, 1993,177-183
[48] Collins R. J., Jefferson D. R. Selection in Massively Parallel Genetic Algorithms. ICG A3, Belew R. K., ed., CA: Morgan-Kaufmann, 1991,249-256
[49] Spiessens P., Manderick B. A Massively Parallel Genetic Algorithm: Implementation and First Ananlysis. 1CGA4, Belew R. K., ed., CA: Morgan-Kaufmann, 1991,279-286
[50] Sarma J., Jong K. D. An Analysis of the Effects of Neighbourhood Size and Shape on Local Selection Algorithms. PPSN IV, Berlin: Springer-Verlag, 1995,236-244
[51] Husbands P., Mill F. Simulated Coevolution as the Mechanism for Emergent Planning and Scheduling. 1CGA4, Belew R. K., ed., CA: Morgan-Kaufmann, 1991, 264-270
[52] Paredis J. The Symbiotic Evolution of Solutions and their Representations. ICGA6, Eshel-man L. ed., CA: Morgan-Kaufmann, 1995, 359-365
[53] Axelrod R.. Evolution of Strategies in the Iterated Prisoner's Dilemma. In Davis L., ed. Genetic Algorithms and Simulated Annealing. CA: Morgan-Kaufmann, 1989．
[54] Sims K. Evolving 3d Morphology and Behavior by Competition. In Brooks R. A. et al., eds. Artificial Life IV. MA: MIT Press, 1994．
[55] Pollack J., Blair A., Land M. Coevolution of a Backgammon Player. In Artificial Life V, 1996．
[56] Sebald A.V., Schlenzig J. Minimax Design of Neural Net Controllers for Highly Uncertain Plants. IEEE Trans, on Neural Networks, January 1994, 5(l):73-82
[57] Potter M.A. The Design and Analysis of a Computational Model of Cooperative Coevolution. PhD thesis, George Mason University, 1997．
[58] Anthony M., Brightwell G., Cohen D., Shawe-Laylor J. On Exact Specification by Examples. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 1992
[59] Goldman S.A, Kearns M.J. On the Complexity of Teaching. In Warmuth M.K. et al., eds, Proceedings of the Fourth Annual Workshop on Computational Learning Theory. CA: Morgan-Kaufmann, 1991
[60] Southwell R. V. Relaxation Methods in Theoretical Physics. Oxford: Clarendon Press. 1946
[61] Firedman M., Savage L. S., Planning Experiments Seeking Maxima. Selected Techniques of Statistical Analysis for Scientific and Industrial Research, and Production and Management Engineering, Eisenhart M. W. eds. 1947, 363～372
[62] Kauffman S. A., Johnsen S. Coevolution to the Edge of Chaos: Coupled Fitness Landscapes, Posed States, and Coevolutionary Avalanches. Artificial Life Ⅱ, SFI Studies in the Sciences of Complexit, Langton C. G. eds. 1991, vol(10), 325～369
[63] Van Valen L. A New Evolutionary Law, Evolutionary Theory 1, 1973, 1-30
[64] Samuel A. L. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development, 1959, 3(3), 210～229
[65] Rudolph G. Convergence Properties of Canonical Genetic Algorithms. IEEE Trans. on Neural Networks, 1994, 5(1): 96～101
[66] Qi X., Palmieri F. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space Part Ⅰ: Basic Properties of Selection and Mutation. IEEE Trans. on Neural Networks, 1994, 102～119
[67] Goldman R. Introduction to Stochastic Models. Reading, MA: Benjamin / Cummings, 1988.
[68] Fogel D. B. Asymptotic Convergence Properties of Genetic Algorithms and Evolutionary Programming: Analysis and Experiments. Cybernetics and Systems, 25, 1994, 389-407
[69] 陈国良、王煦法、庄镇泉、王东生，《遗传算法及其应用》，人民邮政出版社，1996
[70] 蒋培，黄焱，杨敬安，关于遗传算法收敛性的分析，《湖南师范大学学报》，Vol．22(1)，1999
[71] Michael D. V. Generalizing the Notion of Schema in Genetic Algorithms. Artificial Intelligence, 50(3), 1991, 385-396
[72] Davis L., Ed. Handbook of Genetic Algorithm. New York: Van Nostrand Reinhold, 1991.
[73] Liepins G. E, Vose M. D. Representational Issue in Genetic Optimization. Journal of Experimental and Theoretical. Artificial Intelligence, 10(2), 1991, 101-115.
[74] Whitley L. D. Foundations of Genetic Algorithms. San Mateo, CA: Morgan-Kaufmann, 1991.
[75] Goldberg D. E. Genetic Algorithms and Simulated Annealing. Los Altos, CA: Morgan Kaufman, 1987, 74-88.
[76] 王丽薇、洪勇、洪家荣，《遗传算法的收敛性研究》，《计算机学报》，19(10)，1996，794-797
[77] 黄焱，蒋培，王嘉松，杨敬安，《基于可调变异算子求解遗传算法的欺骗问题》，《软件学报》，1999，2(10)，216-219
[78] Lindgren K., Nordahl M.G. Artificial Food Webs. In Artificial Life Ⅲ, 1994
[79] Goldberg D. E., Richardson J. Genetic Algorithms with Sharing for Multimodal Function Optimization. In Grefenstette J. J., Ed., ICGA 2, L. Ertbaum Assoc., 1987
[80] Smith R.E., Forrest S., Perelson A.S. Searching for Diverse, Cooperative Populations with Genetic Algorithms. Evolutionary Computation, 1993, 1(2):
[81] Giordana A. Neri F. Search-intensive Concept Induction. Evolutionary Computation, 1995, 3(4):
[82] 刘祖洞，《遗传学》，高等教育出版社
[83] 蒋培，王洪燕，杨敬安，关于进化算法中连锁的分析，《合肥工业大学学报》，Vol．23(4)，2000，1-5
[84] Michalski R. S., Carbonell J. G., Mitchell T. M., Machine Learning, an Artificial Intelligence Approach, Springer-Verlag, 1993
[85] Goldberg D. E. Computer-aided Gas Pipeline Operation Using Genetic Algorithm and Rule Learning, Engineering with Computers, 1987, 47～58
[86] Tackett W.A., Carmi A. The Unique Implications of Brood Selection for Genetic Programming. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE, 1994
[87] Mitchell M. Machine Learning. NY: McGraw-Hill, 1997, 249-270
[88] 蒋培，王洪燕，王漫，杨敬安，基于竞争性协同进化算法求解对抗性问题，PACMA 2000’，235-238
[89] Land, M. Belew, R K. No Prefect Two-State Cellular Automata For Density Classification Exists. Physical Review Letters, 1995, 74(25): 1548-1550
[90] Mitchell M., Crutchfield J. P. and Peter T. H. Evolving Cellular Automata To Perform Computations: Mechanisms And Impediments. Physica 1994, D75, 361-391.
[91] Das R., Mitchell M. and Crutchfield J. P. A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata. In: Parallel Problem Solving from Nature Ⅲ, LNCS 866. Berlin: Springer-Verlag. 1994, 344-353.
[92] Andre D., Bennett F. H. and Koza J. R. Evolution Of Intricate Long-Distance Communication Signals In Cellular Automata Using Genetic Programming. In: Proceedings of the Fifth Artificial Life Conference. 1996, 16-18.
[93] 蒋培，王洪燕，杨敬安，人工生命仿真的分析，《长沙铁道学院学报》，Vol．17(2)，1999，34-39
[94] 王洪燕 杨敬安 蒋培，基于生长神经网络的进化机器人行为研究，《电子学报》，Vol．28，No．12，2000
[95] D. Cliff, G. Miller, Co-evolution of Pursuit and Evasion H: Simulation Methods and Resuits, SAB96, MIT Press Bradford Books 1996
[96] Futuyma D.J., Slatkin D.K. Coevolution. Sinauer, 1983.
[97] Dawkins R. and J.R. Krebs. Arms races between and within species. Proceedings of the Royal Society of London B, 205:489--511, September 1979.
[98] Bakker R.T. The Wolf Pursues: Incongruencies in Predator-prey Coevolution. In Futuyma D.J. and M. Slatkin, eds., Coevolution, Sinauer 1983
[99] Condra J.H. and E.A. Emini. Preventing HIV-1 drug resistance. Science & Medicine, January/February 1997.
[100] Jerison H.J, Evolution of the Brain and Intelligence. Academic Press, 1973.
[101] May R.M. and R.M. Anderson. Parasite-Host coevolution. In D.J. Futuyma and M. Slatkin, eds., Coevolution. Sinauer, 1983.
[102] 王洪燕，基于神经网络的进化机器人行为集成方法的研究，博士学位论文，合肥工业大学，2000
[103] McInerney J. Biologically Influenced Algorithms and Parallelism in Non-linear Optimization. Ph.D. thesis, University of California, San Diego, 1992.
[104] 王洪燕，杨敬安，蒋培，基于神经网络的进化机器人组合行为方法研究，《计算机研究与发展》，Vol．37，2000