数学建模社区-数学中国

标题: 智能算法综述（续） [打印本页]

作者: reedbook 时间: 2009-6-1 19:36
标题: 智能算法综述（续）
3.1 特点

   遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为： ① 首先组成一组候选解； ② 依据某些适应性条件测算这些候选解的适应度； ③ 根据适应度保留某些候选解，放弃其他候选解； ④ 对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。
遗传算法还具有以下几方面的特点：

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

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

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

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

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

3.2  运用领域

   前面描述是简单的遗传算法模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域： ① 优化：遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。 ② 程序设计：遗传算法可以用于某些特殊任务的计算机程序设计。 ③ 机器学习：遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等。 ④ 经济学:应用遗传算法对；济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。 ⑤ 免疫系统：应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。 ⑥ 进化现象和学习现象：遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。 ⑦ 社会经济问题：遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流是如何演化出来的。

4 模拟退火算法

   模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f ，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

5 群体（群集）智能（Swarm Intelligence）

   受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
群集智能的特点和优点：群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前网络环境下的工作状态; 没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信(Stimergy)进行合作，这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。因为具有这些优点，虽说群集智能的研究还处于[初级阶段，并且存在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。

   在计算智能(Computational Intelligence)领域有两种基于群智能的算法，蚁群算法(Ant Colony Optimization)和粒子群算法(Particle Swarm Optimization)，前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。

5.1 蚁群优化算法

   受蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群优化算法(Ant Colony Optimization，ACO)来解决计算机算法学中经典的“货郎担问题”。如果有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。
在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近"的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。
蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法，它已经被成功用于解决其他组合优化问题，例如图的着色(Graph Coloring)以及最短超串(Shortest Common Supersequence)等问题。

5.2 粒子群优化算法

   粒子群优化算法(PSO)是一种进化计算技术(Evolutionary Computation)，有Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。
PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。
同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。
粒子群优化算法(PSO) 也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。

5.2.1 算法介绍

   PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

   PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

   PSO初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。

5.2.2 PSO算法过程
① 种群随机初始化。
② 对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。
③ 种群根据适应值进行复制。
④ 如果终止条件满足的话，就停止，否则转步骤 ② 。

   从以上步骤，我们可以看到PSO和遗传算法有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉(crossover)和变异(mutation)，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。

   与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。

   现在已经有一些利用PSO代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法，同时PSO速度比较快而且可以得到比较好的结果。

6 展望

   目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发展。不仅仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大成就。

参考文献
[1] “Ant-Colony Optimization Algorithms(ACO)”，
[2 ]  “Swarm intelligence-what is it and why is it interesting”
[3]  Tony White,“Swarm Intelligence: A Gentle Introduction With Application”,
[4] 胡守仁等.神经网络导论[M].长沙:国防科技大学出版社,1993.113～117.
[5] 姚新,陈国良,徐惠敏等.进化算法研究进展[J].计算机学报,1995,18(9):694-706.
[6] 张晓,戴冠中,徐乃平.一种新的优化搜索算法—遗传算法.控制理论与应用[J].1995, 12(3):265-273.
[7] 杨志英.ＢＰ神经网络在水质评价中的应用[J].中国农村水利水电,2001,9:27-29.

作者: candice_geng 时间: 2009-7-15 12:45
谢谢，顶一下

作者: zhong@quan 时间: 2009-7-29 00:00
very good!

作者: renjian4660129 时间: 2009-7-31 14:08
看看
谢谢楼主

作者: yl_sadness 时间: 2009-8-6 09:35
顶下~~~~知道蛮多的

作者: dean0514 时间: 2009-8-12 23:25
嗯，赞一下！论述的比较好，起码知道是怎么回事了！谢谢总结和分享！

作者: leishengwen 时间: 2009-8-19 11:20
1# reedbook

作者: yinghuawan 时间: 2009-9-2 17:38
haodongxi ya !!!!

作者: Rekcahpu 时间: 2010-12-16 20:52
哎呀又不是俺要的找的

作者: Dawnhxf 时间: 2011-11-15 19:11
详细，不过有具体的算法过程和代码就好了。

作者: pocific 时间: 2011-12-11 19:51
很好,再写深入点就更好了

作者: 李——建辉 时间: 2012-1-25 20:52
Try to make the best use of my time54766852922954565382463340642130847245518262255267242759721895109967713933980608

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)