人工智能基础算法

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

2、越性。优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等 .优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度 .爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(evolutionaryalgorithms)的一种 ,它通过模仿自然界的选择与遗传的机理来寻找最优解 .遗传算法有三个基本算子 :选择、交叉和变异 .但是遗传算法的编程实现比较复杂 ,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率 ,并且

3、这些参数的选择严重影响解的品质 ,而目前这些参数的选择大部分是依靠经验.1995 年 eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(particalswarmoptimization-pso)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化 (particalswarmoptimization-pso)算法是近年来发展起来的一种新的进化算法 (evolu2tionaryalgorithm-ea).pso算法属于进化算法的一种 ,和遗传算法相似 ,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度

4、来评价解的品质 .但是它比遗传算法规则更为简单,它没有遗传算法的交叉(crossover)和变异 (mutation) 操作.它通过追随当前搜索到的最优值来寻找全局最优二、遗传算法遗传算法是计算数学中用于解决最佳化的，是进化算法的一种。 进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、 突变、自然选择以及杂交等。 遗传算法通常实现方式为一种模拟。对于一个最优化问题， 一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用表示（即0 和 1 的串），但也可以用其他表示方法。进化从完全随机个体的种群开始， 之后一代一代发生。 在每一代中，

5、整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。主要特点遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。 的共同特征为： 首先组成一组候选解 依据某些适应性条件测算这些候选解的适应度 根据适应度保留某些候选解，放弃其他候选解 对保留的候选解进行某些操作，生成新的候选解。在遗传算法中， 上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、 交换操作和突变操作。 这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法还具有以下几方面的特

6、点：(1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。 传统优化算法是从单个初始值求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其他辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则

7、来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应的基因结构。三、贪婪算法概念：贪婪算法是一种不追求最优解，只希望得到较为满意解的方法。贪婪算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。 贪婪算法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况。 例如平时购物找钱时， 为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案， 而是从最大面值的币种开始， 按递减的顺序考虑各币种，先尽量用大面值的币种， 当不足大面值币种的金额时才去考虑下一种较小面

8、值的币种。 这就是在使用贪婪算法。 这种方法在这里总是最优， 是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5 和 11 单位的硬币，而希望找回总额为15 单位的硬币。按贪婪算法，应找1 个 11 单位面值的硬币和 4 个 1 单位面值的硬币， 共找回 5 个硬币。但最优的解应是 3 个 5单位面值的硬币。四、蚁群算法蚁群算法 (ant colony optimization, aco)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由marco dorigo 于 1992 年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。自然界的种群

9、相当广泛,但大部分都有以下的能力: 蚂蚁们总能找到食物源和蚂蚁窝之间的最短路径 . 一旦这条最短路径被发现, 蚂蚁们就能在这条路上排成一行, 在食物源和蚂蚁窝之间搬运食物. 蚂蚁们是怎么做到的呢 ? 我们知道 ,2 点间直线距离最短 . 但蚂蚁们显然不具备这样的视力和智慧. 它们无法从远处看到食物源 , 也无法计划一个合适的路径来搬运食物. 蚂蚁们采用的方法是全体在老窝的周围区域进行地毯式搜索.而他们之间的是通过分泌化学物质在爬过的路径上 ,这种化学物质叫 (pheromone). 蚂蚁们习惯选择信息素浓度高的路径. 下面的图解释了蚂蚁们的工作原理. 刚开始离开窝的时候 , 蚂蚁们有两条路径选择 : r1 和 r2. 这两者机会相当 . 蚂蚁们在爬过 r1 和 r2 的时候都留下了信息素 . 但是, 由于 r2 的距离短 , 所需要的时间就少 , 而信息素会挥发 , 所以蚂蚁们留在r2 上的信息素浓度就高 . 于是,越来越多的蚂蚁选择r2 作为最佳路径 , 即使它们是从 r1 来到食物源 ,也将选择r2 返回蚂蚁窝 . 而从老巢里出发的蚂蚁们也越来越倾向于r2. 在这样的趋势下 , r1 渐渐变的无人问津了根据蚂蚁们选择路径的方法而得到的启发, dr. dorigo 在 1991 年发表了 (ant algorithm). 十多年来 , 蚂蚁算法 ,以及各种改进过的