博文
地学相关模型（3）
||||
3、遗传算法（Genetic Algorithm，简称GA）
（1）背景
19的世纪世界四大学说之一是达尔文的自然选择学说。其主要内容有四点：过度繁殖，生存斗争（也叫生存竞争），遗传和变异，适者生存。在生存斗争中，具有有利变异的个体，容易在生存斗争中获胜而生存下去。反之，则容易在生存斗争中失败而死亡。达尔文把在生存斗争中，适者生存、不适者被淘汰的过程叫做自然选择。
遗传算法就是根据自然界这个“物竞天择，适者生存”现象而提出来的一种随机搜索算法。遗传算法起源于对生物系统所进行的计算机模拟研究。
早在本20世纪世纪1940年代．就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遴传过程棋拟等研究工作。进入60 年代后，美国密执安大学的Holland 教授及其学生们受到这种生物模拟技术的启发．创造出了一种基于生物遗传和进化机制的适合子复杂系统优化计算的自适应概率优化技术一遗传算法。
1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。
进入20世纪1980年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。
1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。
进入20世纪1980年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。
1989年，Holland的学生D.E.Goldberg出版了专著 《搜索、优化和机器学习中的遗传算法》。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。
在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。
1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。
1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machine》《IEEE Transactions on Signal Processing》《IEEE Transactions on Neural Networks》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。【1】
1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machine》《IEEE Transactions on Signal Processing》《IEEE Transactions on Neural Networks》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。【1】
可以说，进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。【2】
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。【2】
遗传算法的一些应用领域：
（1）优化。遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。
（2）程序设计。遗传算法可以用于某些特殊任务的计算机程序设计，如元胞计算机。
（3）机器学习。遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，如预测天气或预测蛋白质的结构。
（4）经济学。应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
（5）免疫系统。应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。
（6）生态学。遗传算法可以应用于对生态学的一些现象进行建模，包括生物间的生存竞争，宿主——寄生物的共同进化，共生现象，甚至包括生物学“军备竞赛”。
（7）进化现象和学习现象。遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。
（8）社会经济问题。遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流的是如何演化出来的。
（1）优化。遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。
（2）程序设计。遗传算法可以用于某些特殊任务的计算机程序设计，如元胞计算机。
（3）机器学习。遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，如预测天气或预测蛋白质的结构。
（4）经济学。应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
（5）免疫系统。应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。
（6）生态学。遗传算法可以应用于对生态学的一些现象进行建模，包括生物间的生存竞争，宿主——寄生物的共同进化，共生现象，甚至包括生物学“军备竞赛”。
（7）进化现象和学习现象。遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。
（8）社会经济问题。遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流的是如何演化出来的。
（2）概念
遗传算法是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。遗传算法已经成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。
有关基本概念：
群体（population）：又称种群、染色体群，个体（individual）的集合，代表问题的解空间子集。
串（string）及串空间：串是个体的表达形式，对应着遗传学中的染色体。对应实际问题的一个解。
群体规模（population size）：染色体群中个体的数目称为群体的大小或群体规模。
基因（gene）：是指染色体的一个片段，基因可以是一个数值、一组数或一串字符。
交换（crossover）：指在一定条件下两条染色体上的一个或几个基因相互交换位置。
交换概率：判断是否满足交换条件的一个小于1的阀值。
变异（mutation）：指在一定条件下随机改变一条染色体上的一个或几个基因值
变异概率：判断是否满足变异条件的一个小于1的阀值。
后代：染色体经过交换或变异后形成的新的个体。
适应度（fittness）：用来度量种群中个体优劣（符合条件的程度）的指标值，它通常表现为数值形式。
选择（selection）：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。
有关基本概念：
群体（population）：又称种群、染色体群，个体（individual）的集合，代表问题的解空间子集。
串（string）及串空间：串是个体的表达形式，对应着遗传学中的染色体。对应实际问题的一个解。
群体规模（population size）：染色体群中个体的数目称为群体的大小或群体规模。
基因（gene）：是指染色体的一个片段，基因可以是一个数值、一组数或一串字符。
交换（crossover）：指在一定条件下两条染色体上的一个或几个基因相互交换位置。
交换概率：判断是否满足交换条件的一个小于1的阀值。
变异（mutation）：指在一定条件下随机改变一条染色体上的一个或几个基因值
变异概率：判断是否满足变异条件的一个小于1的阀值。
后代：染色体经过交换或变异后形成的新的个体。
适应度（fittness）：用来度量种群中个体优劣（符合条件的程度）的指标值，它通常表现为数值形式。
选择（selection）：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。
对概念的案例理解：
GA对于复杂问题寻找最优解特别适用。如著名的旅行推销员问题：一个推销员希望设计一个送货车的路线计划，送货车需要送到许多商店，商店的先后顺序并不重要，主要是如何确定路线使得总里程最节省。人们已经发现这个问题没有常规的解决策略。然而，通过模拟一大批智能车（每一辆车相当于自然部落中的一个生命个体），开始每辆车都随机地选择行驶路径，通过比较他们完成任务所必须的里程数的长短进行类似自然淘汰的过程（短的在竞争中胜出），然后从这些竞争中胜出的车辆中随机地选择配对，混合他们的路径选择产生新一代的车辆，这样新生代车辆中含有上一代车辆双方的部分特征，那些产生的后代比自己还短的车辆配偶被保留下来，这样慢慢地车辆会变得越来越聪明，选择的路径也越来越优化。
（3）原理
一般把具有以下6个操作的遗传算法称为标准遗传算法：
（1）编码。通过这个步骤，将处理空间的解数据表示成遗传空间的基因型串结构数据。
（2）初始群体的生成。通过随机方法产生初始群体的每个个体，即进化的第一代。
（3）适应度评估检测。构成一个适应度函数，用来评价个体或解的优劣，并作为以后遗传操作的依据。
（4）选择。选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代，为下一代繁殖子孙。
（5）交叉。对配对库中的个体进行随机配对，并在配对个体中随机设定交叉处，使配对个体彼此交换部分信息。
（6）变异。把某一位的内容进行改变，这是十分微妙的遗传操作，它需要和交叉操作妥善地配合使用。
（4）软件工具
常用的是 MATLAB 遗传算法工具箱。基于Matlab的遗传算法工具箱有好多种，是不同的人在不同的时间开发的，现在已知的有：
GAOT，中国学术期刊网上大部分研究遗传算法的中文论文都是使用的这个工具箱。这个工具箱用的似乎是最广的，虽然不是Matlab自带的，但在网上也很容易下载到。然而它的版本实在是太老了，是适用于Matlab5.0版的，到目前为止还没有更新版本发布。
GADS 这个是Matlab7.0版本自带的工具箱。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。
GAOT，中国学术期刊网上大部分研究遗传算法的中文论文都是使用的这个工具箱。这个工具箱用的似乎是最广的，虽然不是Matlab自带的，但在网上也很容易下载到。然而它的版本实在是太老了，是适用于Matlab5.0版的，到目前为止还没有更新版本发布。
GADS 这个是Matlab7.0版本自带的工具箱。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。
【1】遗传算法的发展历史，http://www.itpub.net/thread-1204578-1-1.html
进一步阅读：
https://m.sciencenet.cn/blog-43347-473689.html
上一篇：地学相关模型（2）
下一篇：地学相关模型（5）
