搜索

AI人工智能的几种常用算法概念

gecimao 发表于 2019-06-11 09:36 | 查看: | 回复:

  粒子群算法,也称粒子群优化算法(Particle Swarm Optimization),缩写为 PSO, 是近年来发展起来的一种新的进化算法((Evolu2tionary Algorithm - EA)。PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。

  优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题。为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等。优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度。爬山法精度较高,但是易于陷入局部极小。遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解。遗传算法有三个基本算子:选择、交叉和变异。但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。

  粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质。但是它比遗传算法规则更为简单,它没有遗传算法的交叉(Crossover)和变异(Mutation)操作。它通过追随当前搜索到的最优值来寻找全局最优

  遗传算法是计算数学中用于解决最佳化的,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种模拟。对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上,解用表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中,整个种群的适应度被评价,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。

  遗传算法是解决搜索问题的一种通用算法,对于各种通用问题都可以使用。的共同特征为:

  在遗传算法中,上述几个特征以一种特殊的方式组合在一起:基于染色体群的并行搜索,带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。

  (1)遗传算法从问题解的串集开始搜索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。

  (2)遗传算法同时处理群体中的多个个体,即对搜索空间中的多个解进行评估,减少了陷入局部最优解的风险,同时算法本身易于实现并行化。

  (3)遗传算法基本上不用搜索空间的知识或其他辅助信息,而仅用适应度函数值来评估个体,在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

  (4)遗传算法不是采用确定性规则,而是采用概率的变迁规则来指导他的搜索方向。

  (5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时,适应度大的个体具有较高的生存概率,并获得更适应的基因结构。

  贪婪算法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪算法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况。例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪算法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。

  蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

  自然界的种群相当广泛,但大部分都有以下的能力: 蚂蚁们总能找到食物源和蚂蚁窝之间的最短路径。 一旦这条最短路径被发现, 蚂蚁们就能在这条路上排成一行, 在食物源和蚂蚁窝之间搬运食物。 蚂蚁们是怎么做到的呢?

  我们知道,2点间直线距离最短。 但蚂蚁们显然不具备这样的视力和智慧。 它们无法从远处看到食物源, 也无法计划一个合适的路径来搬运食物。 蚂蚁们采用的方法是全体在老窝的周围区域进行地毯式搜索。而他们之间的是通过分泌化学物质在爬过的路径上,这种化学物质叫(Pheromone)。

  刚开始离开窝的时候, 蚂蚁们有两条路径选择: R1和R2. 这两者机会相当。 蚂蚁们在爬过R1和R2的时候都留下了信息素。 但是, 由于R2的距离短, 所需要的时间就少, 而信息素会挥发, 所以蚂蚁们留在R2上的信息素浓度就高。 于是,越来越多的蚂蚁选择R2作为最佳路径, 即使它们是从R1来到食物源,也将选择R2返回蚂蚁窝。 而从老巢里出发的蚂蚁们也越来越倾向于R2. 在这样的趋势下, R1渐渐变的无人问津了

  根据蚂蚁们选择路径的方法而得到的启发, Dr. Dorigo在1991年发表了(Ant algorithm)。 十多年来, 蚂蚁算法,以及各种改进过的蚂蚁算法,被广泛的应用在实际生活的各个方面。 在应用中,它可以作为网络路由控制的工具。 在交通控制中, 它也成功解决了车辆调度问题。在图表制作中, 它被用来解决颜色填充问题。 此外, 它还可以被用来设计大规模的时刻表。 而问题,既在多个不同地点间往返的最佳路径选择问题, 应该算是蚂蚁算法最重要的用途了

本文链接:http://rachmashop.com/dingyiyu/438.html
随机为您推荐歌词
推荐文章

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部