进化算法简单介绍
共 2224字,需浏览 5分钟
·
2022-05-29 21:59
进化计算(Evolution Computing)
进化计算是采用简单的编码技术来表示各种复杂的结构,并通过简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用种群(即一组表示)的方式组织搜索,这使得它可以同时搜索解空间内的多个区域,特别适合大规模并行计算。
进化计算具有自组织、自适应、自学习的特点,并且不受其搜索空间限制性条件(如可微、单峰等)的约束,不需要其他辅助信息(如导数)。这使得进化计算不仅能获得较高的效率,而且操作简单、通用性强。
进化计算的发展过程
进化计算在20世纪六七十年代并未受到普遍的重视。其主要原因,
一是因为这些方法本身还不够成熟;
二是由于这些方法需要较大的计算量,而当时的计算机还不够普及且速度较慢,这样便限制了它们的应用;
三是当时基于符号处理的人工智能方法正处于其顶峰时期,使得人们难以认识到其他方法的有效性及适应性。
到了20世纪80年代,人工智能方法的局限性越来越突出,并且随着计算机速度的提高和并行计算机的普及,已使得进化计算对机器速度的要求不再是制约其发展的因素。
进化计算的不断发展及其在一些应用领域内取得的成功,已表现出了良好的应用前景。由于进化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成功,引起了各领域科学家们的极大兴趣,自20世纪80年代中期以来,世界上许多国家都掀起了进化计算的研究热潮。
目前,有数种以进化计算为主题的国际会议在世界各地定期召开,并已出版了多种有关进化计算的杂志。可以预料,随着进化计算理论研究的不断深入和应用领域的不断拓广,进化计算必将取得更大的成功。
进化计算的主要分支
进化计算的三大分支包括:遗传算法(Genetic Algorithm,简称GA)、进化规划(Evolutionary Programming,简称EP)和进化策略(Evolution Strategies ,简称ES)。
这三个分支在算法实现方面具有一些细微的差别,但它们具有一个共同的特点,即都是借助生物进化的思想和原理来解决实际问题。下面我们分别就这三个分支作以简单的介绍。
遗传算法
遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法,由美国Holand J教授于1975年首次提出。它是利用某种编码技术作用于称为染色体的二进制数中,其基本思想是模拟由这些串组成的种群的进化过程,通过有组织的、然而是随机的信息交换来重新组合那些适应性好的串。
遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并根据适应性来选择染色体,使适应性好的染色体比适应性差的染色体有更多的繁殖机会。
遗传算法尤其适用于处理传统搜索方法难于解决的复杂的非线性问题,可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域,是21世纪有关智能计算中的关键技术之一。
进化策略
1964年,由德国柏林工业大学的Rechenberg I等人提出。在求解流体动力学柔性弯曲管的形状优化问题时,用传统的方法很难在优化设计中描述物体形状的参数,然而利用生物变异的思想来随机地改变参数值并获得了较好的结果。随后,他们便对这种方法进行了深入的研究和发展,形成了进化计算的另一个分支——进化策略。进化策略与遗传算法的不同之处在于:进化策略直接在解空间上进行操作,强调进化过程中从父体到后代行为的自适应性和多样性,强调进化过程中搜索步长的自适应性调节;而遗传算法是将原问题的解空间映射到位申空间之中,然后再施行遗传操作,它强调个体基因结构的变化对其适应度的影响。进化策略主要用于求解数值优化问题。
进化规划
进化规划的方法最初是由美国人Fogel L J等人在20世纪60年代提出的。他们在人工智能的研究中发现,智能行为要具有能预测其所处环境的状态,并按照给定的目标做出适当的响应的能力。在研究中,他们将模拟环境描述成是由有限字符集中符号组成的序列。
进化计算的主要特点
进化算法与传统的算法具有很多不同之处,但其最主要的特点体现在下述两个方面:
智能性
进化计算的智能性包括自组织、自适应和自学习性等。
应用进化计算求解问题时,在确定了编码方案、适应值函数及遗传算子以后,算法将根据“适者生存、不适应者淘汰”的策略,利用进化过程中获得的信息自行组织搜索,从而不断地向最佳解方向逼近。
自然选择消除了传统算法设计过程中的一个最大障碍:即需要事先描述问题的全部特点,并说明针对问题的不同特点算法应采取的措施。于是,利用进化计算的方法可以解决那些结构尚无人能理解的复杂问题。
本质并行性
进化计算的本质并行性表现在两个方面:
一是进化计算是内在并行的,即进化计算本身非常适合大规模并行。
二是进化计算的内含并行性,由于进化计算采用种群的方式组织搜索,从而它可以同时搜索解空间内的多个区域,并相互交流信息,这种搜索方式使得进化计算能以较少的计算获得较大的收益。
公众号粉丝礼包: 后台关键词:python大礼包 礼包内容:Matlab,数据分析与机器学习实战,数据科学概率基础,数学基础,算法讲解视频 整理不易,还请点击在看与分享,谢谢。 星标🌟公众号,可以更快接收文章!
每日一得“在看”