|
|
|
| |
2008-11-19, 12:22 AM
|
#1 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
 |
模拟退火算法
1. 参考书籍
非数值并行算法(第一册) 模拟退火算法 2. 论文 浙江大学学报（工学版）
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE) 2007 Vol.41 No.41 P.1083-1087 基于MCMC粒子滤波的机器人定位
Robot localization based on MCMC particle filter
许士芳，谢立，刘济林
摘要：针对基于传统粒子滤波的机器人定位方法存在粒子退化的问题，提出了基于马尔科夫蒙特卡罗（MCMC）粒子滤波的机器人定位方法.将传统的粒子滤波算法与典型的 MCMC方法——Metropolis Hastings (MH)抽样算法有机结合，并应用于机器人定位研究中.试验结果表明，MCMC方法可以有效抑制粒子退化问题.与基于传统粒子滤波的机器人定位方法相比，该方法降低了定位误差均值和定位误差最大值，取得了更高的定位精度，有效地解决了机器人定位这一非线性非高斯状态估计问题.关键词： 马尔科夫蒙特卡罗方法；粒子滤波；机器人定位；Metropolis Hastings抽样；粒子退化 中图分类号： TP242 文献标识码： A 文章编号： 1008-973X(2007)07-1083-05 基金项目：国家自然科学基金重点资助项目（60534070）；浙江省重点国际科技合作资助项目（2005C14008）. .作者简介：许士芳（1982－），女，山东德州人，博士生，主要从事机器人定位、视频编解码、图像处理等方面的研究.E-mail: shifang_xu@yahoo.com.cn 通讯联系人：刘济林，男，教授，博导. E-mail: liujl@zju.edu.cn 作者单位：许士芳，谢立，刘济林（浙江大学 信息科学与工程学院，浙江 杭州 310027） 参考文献(References)： ［1］THRN S, FOX D, BURGARD W, et al. Robust Monte Carlo localization for mobile robots［J］. Artificial Intelligence, 2001, 128(1/2): 99-114. ［2］DOUCET A, FREITAS N, GORDON N. Sequential Monte Carlo methods in practice［M］. New York: Springer, 2001. ［3］DOUCET A, GODSILL S, ANDRIEU C. On sequential Monte Carlo sampling methods for Bayesian filtering［J］. State Compute, 2000, 10(3): 197-208. ［4］FOX D. KLD sampling: adaptive particle filters［J］. International Journal of Robotics Research, 2003, 22 (12): 985-1003. ［5］KWOK C, FOX D, MEILA M. Adaptive real-time particle filters for robot localization［C］∥Proceedings of IEEE International Conference on Robotics and Automation. Taipei, China: IEEE, 2003: 2836-2841. ［6］REKLEITIS I M. Cooperative localization and multirobot exploration［D］. Montreal, Canada: McGill University, 2003. ［7］DEREK K. Range only robot localization and SLAM with radio［D]. Pittsburgh: Carnegie Mellon University, 2004. ［8］VAN DER MERWE R, DOUCET A, DE FREITAS N, et al. The unscented particle filter［R]. Cambridge, UK: Cambridge University, 2000. ［9］ANDRIEU C, FREITAS N, DOUCET A. Sequential MCMC for Bayesian model selection［C］∥IEEE Higher Order Statistics Workshop. Ceasarea, Israel: IEEE, 1999: 130-134. ［10］GILKS W R, BERZUINI C. Monte Carlo inference for dynamic Bayesian models［C］∥Medical Research Council. Cambridge, UK: [s.n.], 1998. ［11］GORDON N J, SALOMND D J, SMITH A F M. Novel approach to nonlinear and non-Gaussian Bayesian state estimation［J］. IEEE Proceedings on Radar and Signal Processing, 1993, 140(2):107-113. ［12］KITAGAWA G. Monte Carlo filter and smoother for nonGaussian nonlinear state space models［J］. [WTHZ]Journal of Computational and Graphical Statistics, 1996,5(1):1-25. ［13］[ZK(]LIU J S, CHEN R. Sequential Monte Carlo methods for dynamic systems［J］. Journal of the American Statistical Association, 1998, 93(443):1032-1044.
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] 此帖于 2008-12-28 10:39 PM 被 huangyhg 编辑. |
|
|
| GDT自动化论坛（仅游客可见） |
|
2008-11-21, 04:25 PM
|
#2 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
模拟退火算法
模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 3 模拟退火算法的参数控制问题 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点： (1) 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 (2) 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。 (3) 温度管理问题。 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式： T(t+1)＝k×T(t) 式中k为正的略小于1.00的常数，t为降温的次数 http://baike.baidu.com/view/335371.html
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-11-21, 04:31 PM
|
#3 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
比较模拟退火算法和遗传算法相同点和不同点
模拟退火的话进化是由参数问题t控制的，然后通过一定的操作产生新的解，根据当前解的优劣和温度参数t确定是否接受当前的新解。 遗传算法主要由选择，交叉，变异等操作组成，通过种群进行进化。 主要不同点是模拟退火是采用单个个体进行进化，遗传算法是采用种群进行进化。模拟退火一般新解优于当前解才接受新解，并且还需要通过温度参数t进行选择，并通过变异操作产生新个体。而遗传算法新解是通过选择操作进行选择个体，并通过交叉和变异产生新个体。 相同点是都采用进化控制优化的过程。 两个都是垃圾算法，没什么学习的必要，推荐你看一下方开泰的《数论方法在统计中的应用》和《非线性回归模型参数估计的一个新算法》，学习一下序贯数论算法吧。
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-11-21, 04:44 PM
|
#4 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-11-25, 04:23 PM
|
#5 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
我的qq是67383596（email:xuxh1980@163.com），搂主的qq号(邮箱)是多少，能否告诉我？谢谢！
其实编程的话是要先看懂原理和步骤,比如模拟退火算法 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想: (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L (2) 对k=1，……，L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 算法对应动态演示图：模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] 此帖于 2008-11-25 04:39 PM 被 huangyhg 编辑. |
|
|
|
|
2008-11-25, 04:34 PM
|
#6 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
概述
在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路设计、代码设计、图像处理和电子工程等科技领域中，存在大量组合优化瓿。其中许多问题如货郎担问题、图着色问题、设备布局问题以及布线问题等，至今没有找到有效的多项式时间算法。这些问题已被证明是NP完全问题。
1982年,KirkPatrick将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度加到很高,再缓慢降温(即退火)，使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点.。
在［1］中的解释为：Simulation Annealing is a technique which can be applied to any minimisation or learning process based on successive update steps (either random or deterministic) where the update step length is proportional to an arbitrarily set parameter which can play the role of a temperature. Then, in analogy with the annealing of metals, the temperature is made high in the early stages of the process for faster minimisation or learning, then is reduced for greater stability.
即：模拟退火算法是一种能应用到求最小值问题或基本先前的更新的学习过程（随机或决定性的）。在此过程中，每一步更新过程的长度都与相应的参数成正比，这些参数扮演着温度的角色。然后，与金属退火原理相类似，在开始阶段为了更快地最小化或学习，温度被升得很高，然后才（慢慢）降温以求稳定。
l模拟退火算法的主要思想
就函数最小值问题来说，模拟退火的主要思想是：在搜索区间（二维平面中）随机游走（即随机选择点），再以Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度即是Metropolis算法中的一个重要控制参数，可以认为这个参数的大小控制了随时过程向局部或全局最优解移动的快慢。
冷却参数表、领域结构和新解产生器、接受准则和随机数产生器（即Metropolis算法）一起构成算法的三大支柱。
l重点抽样与Metroplis算法：
Metropolis是一种有效的重点抽样法，其算法为：系统从能量一个状态变化到另一个状态时，相应的能量从E1变化到E2，概率为p = exp[ - (E2- E1)/kT ]。如果E2 < E1，系统接收此状态，否则，以一个随机的概率接收此或丢弃此状态。这种经常一定次数的迭代，系统会逐渐趋于一引稳定的分布状态。
重点抽样时，新状态下如果向下则接受（局部最优），若向上（全局搜索），以一定机率接受。模拟退火方法从某个初始解出发,经过大量解的变换后,可以求得给定控制参数值时组合优化问题的相对最优解。然后减小控制参数T的值，重复执行Metropolis算法，就可以在控制参数T趋于零时，最终求得组合优化问题的整体最优解。控制参数的值必须缓慢衰减。
其中温度是一个Metropolis的重要控制参数，模拟退火可视为递减控制参数什时Metroplis算法的迭代。开始T值大，可能接受较差的恶化解，随着T的减小，只能接受较好的恶化解，最后在T趋于0时，就不再接受任何恶化解了。
在无限高温时，系统立即均匀分布，接受所有提出的变换。T的衰减越小，T到达终点的时间越长；但可使马可夫链越小，到达准平衡分布的时间越短，
l参数的选择：
我们称调整模拟退火法的一系列重要参数为冷却进度表。它控制参数T的初值及其衰减函数，对应的MARKOV链长度和停止条件，非常重要。
一个冷却进度表应当规定下述参数：
1．控制参数t的初值t0;
2．控制参数t的衰减函数；
3．马尔可夫链的长度Lk。（即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布，即一个局部收敛解位置）
4．结束条件的选择
有效的冷却进度表判据：
一．算法的收敛：主要取决于衰减函数和马可夫链的长度及停止准则的选择
二．算法的实验性能：最终解的质量和CPU的时间
参数的选择：
一）控制参数初值T0的选取
一般要求初始值t0的值要充分大，即一开始即处于高温状态，且Metropolis的接收率约为1。
二）衰减函数的选取
衰减函数用于控制温度的退火速度，一个常用的函数为：T(n + 1) = K*T(n)，其中K是一个非常接近于1的常数。
三）马可夫链长度L的选取
原则是：在衰减参数T的衰减函数已选定的前提下，L应选得在控制参数的每一取值上都能恢复准平衡。
四）终止条件
有很多种终止条件的选择，各种不同的条件对算法的性能和解的质量有很大影响，本文只介绍一个常用的终止条件。即上一个最优解与最新的一个最优解的之差小于某个容差，即可停止此次马尔可夫链的迭代。
l参考文献：
2．Numeric Recipes in C
3．计算方法丛书 非数值并行算法 （第一册） 模拟退火算法
在上一篇文章中讲述了模拟退火的基本原理，以下以一个实际的例子来说明，其中所有的源码已贴出，可以从中了解到很多细节。 使用模拟退火法求函数f(x,y) = 5sin(xy) + x2 + y2的最小值 解：根据题意，我们设计冷却表进度表为： 即初始温度为100 衰减参数为0.95 马可夫链长度为10000 Metropolis的步长为0.02 结束条件为根据上一个最优解与最新的一个最优解的之差小于某个容差。 使用METROPOLIS接受准则进行模拟, 程序如下 /* * 模拟退火法求函数f(x,y) = 5sin(xy) + x^2 + y^2的最小值 * 日期:2004-4-16 * 作者:ARMYLAU * EMAIL:armylau2@163.com * 结束条件为两次最优解之差小于某小量 */ using System; namespace SimulateAnnealing { class Class1 { // 要求最优值的目标函数 static double ObjectFunction( double x, double y ) { double z = 0.0; z = 5.0 * Math.Sin(x*y) + x*x + y*y; return z; } [STAThread] static void Main(string[] args) { // 搜索的最大区间 const double XMAX = 4; const double YMAX = 4; // 冷却表参数 int MarkovLength = 10000; // 马可夫链长度 double DecayScale = 0.95; // 衰减参数 double StepFactor = 0.02; // 步长因子 double Temperature = 100; // 初始温度 double Tolerance = 1e-8; // 容差 double PreX,NextX; // prior and next value of x double PreY,NextY; // prior and next value of y double PreBestX, PreBestY; // 上一个最优解 double BestX,BestY; // 最终解 double AcceptPoints = 0.0; // Metropolis过程中总接受点 Random rnd = new Random(); // 随机选点 PreX = -XMAX * rnd.NextDouble() ; PreY = -YMAX * rnd.NextDouble(); PreBestX = BestX = PreX; PreBestY = BestY = PreY; // 每迭代一次退火一次(降温), 直到满足迭代条件为止 do { Temperature *=DecayScale; AcceptPoints = 0.0; // 在当前温度T下迭代loop(即MARKOV链长度)次 <SPAN lang=EN-US style="FONT-SIZE: 9pt; LINE-HEIGHT: 150%; FONT-FAMILY: 新宋体; mso-hansi-font-family: 'Times New Roman'"><FONT face=Arial> for (int i=0;i
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] 此帖于 2008-11-25 04:39 PM 被 huangyhg 编辑. |
|
|
|
|
2008-11-25, 05:01 PM
|
#7 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
蒙特卡罗算法
1. 蒙特卡罗方法的名称与历史 蒙特卡罗方法为计算数学中的一种计算方法，它的基本特点是，以概率与统计中的理论与方法为基础，以是否适于在计算机上使用为重要标志。因此，它虽属计算方法但又与一般计算方法有很大区别。蒙特卡罗是摩纳哥的一个著名城市，以赌博闻名于世。蒙特卡罗方法借用这一城市的名称，属于象征性的，是为了表明该方法的上述基本特点的。蒙特长罗方法也称统计试验方法或计算机随机模拟方法，这些名称同样是为表明该方法的上述基本特点的。 蒙特卡罗方法作为一种可行的计算方法，是由Ulam和Von Neumann在20世纪40年代中叶为解决研制核武器中的计算问题而首先提出并加以运用的。在此之前，作为该方法的基本思想，实际上早已被统计学家所发现和利用了。例如，早在17世纪的时候，人们就知道了依频数来决定概率的方法。又如，在19世纪末，曾有很多人进行随机投针试验。根据针与地面上平行线束（距离均为二倍针长）相交的概率P等于的倒数，用频数n/ N替代概率P，并进而得到。为了使p的有效数字达到4位，置信水平为0.95，所需投针次数要在40万以上。因此，在还不具备实现这样大量试验的条件之前，除非为其他目的，如上例求p是为了验证大数定律，不会有人用进行实际试验的办法来计算所要计算的值。进入20世纪40年代中叶，出现了电子计算机，使得用数学方法在电子计算机上模拟这样大量的试验成为可能。另外，科学技术的不断发展，出现了越来越多的复杂而困难的问题，用通常的解析方法或数值方法都很难得到解决。蒙特卡罗方法就是在这些情况下，作为一种可行的而且是不可缺少的计算方法被提出和迅速发展起来的。 2. 蒙特卡罗方法的一般原理 蒙特卡罗方法解题的一般过程是，首先构成一个概率空间；然后在该概率空间中确定 一个依赖随机变量A(可以为任意维)的统计量g(x)，其数学期望作为G的近似估计。由以上过程看出，蒙特卡罗方法解题的最关键一步是，确定一个统计量，其数学期望正好等于所要求的值。为方便起见，后面将总称这样的统计量为无偏统计量。由于其他原因，如确定数学期望为G的统计量g(x)有困难，或为其他目的，蒙特卡罗方法有时也用G的渐近无偏估计代替一般过程中的无偏估计，并用此渐近无偏估计作为G的近似估计。蒙特卡罗方法的最低要求是，能确定这样一个与计算步数N有关的统计估计量，当时,依概率收敛于所要求的值G，亦即，对于任意的＞0，应有其中P(·)表示事件·的概率。 子样：具有已知分布f(x)的总体，作为它的子样形式，在蒙特卡罗方法中通常被大家所采 用的是简单子样。简单子样指的这样的随机子样，它们之间相互独立，对于任意的x和所有的n = 1，…，N满足简单子样具有三个非常重要的性质。第一个性质是，对于任意的统计量具有同一分布且相互独立，数学期望均等于蒙特卡罗方法的收敛性：蒙特卡罗方法的近似估计依概率1收敛于G，亦即的充分必要条件是无偏统计量g(x)满足就是说，蒙特卡罗方法的收敛性取决于所确定的无偏统计量是否绝对可积，确切些说，是它的绝对数学期望是否存在。如果无偏统计量g(x)满足条件亦即依概率1收敛G的速度为。就是说，蒙特卡罗方法出收敛速度取决于所确定的无偏统计量是几次绝对可积，但收敛速度总不会超过。 蒙特卡罗方法的误差：根据中心极限定理，只要所确定的无偏统计量具有有限的异于零的 方差，对于任意非负的X均有.因此，当N足够大时，就可以认为有如下近似等式：其中为置信度，1 - 为置信水平。根据以上结果，我们可以根据问题的要求，确定出置信水平，然后按照正态积分表确定出X来，而近似估计 与真值G之间的误差就可以用下式近似地de到： 通常取X为0.6745、1.96或3，相应的置信水平依次为0.5、0.95或0.997。 蒙特卡罗方法误差容易确定。对于－般计算方法，要想给出计算结果与真值的误差并不是一件容易办到的事情，蒙特卡罗方法则不然。根据蒙特卡罗方法的误差公式，其中的X是确定的，N是实际的抽样数，未知的仅仅是均方差。可是，它是可以通过计算的同时计算给出的，即对于再复杂的蒙特卡罗方法计算问题，均方差的确定大致上也是如此，因此，误差容易确定成了蒙特卡罗方法另一大优点。一般计算方法常存在着有效位数损失问题，要想解决这一问题有时还是相当困难的，蒙特卡罗方法则不存在这一问题。蒙特卡罗方法的费用：根据上述误差公式，若问题所要求的误差为，置信水平为1 - ，X是按照正态积分表由置信水平所确定的，则应有即子样容量N必须满足进一步假设每计算一次无偏统计量所需要的费用是C，则蒙特卡罗方法的总费用自然应该是就是说，蒙特卡罗方法的费用与方法所确定的无偏统计量的方差及其费用C的乘积C成正比。上述结果表明，在相同条件下，即在相同误差和置信水平要求下，一个蒙特卡罗方法的好坏完全取决于C的值的大小，其值越小相应的方法越好。蒙特卡罗方法的收敛速度与问题的维数无关：由蒙特卡罗方法的误差公式看出，在置信水平一定的情况下，蒙特卡罗方法的误差除了与问题所确定的无偏统计量的方差有关以外，只取决于子样的容量N，而与无偏统计量g()中的是多少维空间的点无关。例如，如下的S重积分计算问题： 蒙特卡罗方法的近似估计是其中，为S维方体内均匀抽样确定的点。由蒙特卡罗方法的误差公式不难看出，如果无偏统计量g(x)的方差不变，则除了由于维数的变化可能引起每次观察费用作较小的变化之外，蒙特卡罗方法的误差是与维数S无关的，或者说，蒙特卡罗方法的收敛速度与问题的维数无关，显然，这一特点是其他计算方法所不常具有的。 蒙特卡罗方法受问题的条件影响不大：蒙特卡罗方法的另一个基本特点是，它受问题条件 限制的影响不大。例如，对于上述积分，如果加上一个积分区域V的限制： 则无论S维单位方体内的区域V如何特殊，我们都可以给出类似的近似估计如下： 显然，这也是其他计算方法所不常具有的。 蒙特卡罗方法不必进行离散化处理：蒙 特卡罗方法的再一个特点是，它不象其他计算方法那样对问题一定要进行离散化处理。明确些说，其他计算方法需要事先确定网格点，一旦网格点确定后，问题所关心的就是这些网格点上的值，而与其他点上的值无关。蒙特卡罗方法完全不需要这些。例如，在化工问题中的如下齐次积分方程本征值： 其中和x为三维空间的点，V一般都比较复杂。对此问题，一般计算方法总是需要在积 分区域V上划分网格点(这一步用计算机实现是比较困难的)，实现离散化，使问题所关心的只是这些网格点上的值(需要占用计算机大量存贮单元)。蒙特卡罗方法则不需要这样做。很明显，蒙特卡罗方法的这一优点，不仅使蒙特卡罗方法更加适于解决那些高维问题，精确度进一步增加，节省计算机大量存贮单元，而且给建立蒙特卡罗方法通用程序带来了很大方便。蒙特卡罗方法具有直接解决问题的能力：蒙特卡罗方法还有一个特点是，对于那些本身具有统计性质的所谓非确定性问题，不需要象常规方法那样首先将它转化成为确定性问题，如转化成某方程的解，然后再通过解决确定性问题得到问题的答案。例如，粒予进入屏蔽层与介质发生多次碰撞后可能被吸收，也可能反射回来或穿过屏蔽层，问题所关心的常是穿透概率。对于这样一个非确定性问题，常规方法是首先给出它所满足的方程，实际上是一个积分微分方程，即转化成为确定性问题，然后用某种计算方法解这一确定 性问题，进而得到问题的解答。蒙特卡罗方法不需要将非确定性问题转化成为确定性问题 ，可以直接从非确定性问题出发，通过模拟原问题的实际过程得到问题的解决。在由非确定性问题转化成确定性问题和用计算方法解这一确定性问题过程中，常常需要作很多近似，蒙特卡罗方法则不需要，因此，有人称蒙特卡罗方法为精确的方法，并常依此为标准衡量其他方法的近似是否是合理的。蒙特卡罗方法具有同时计算多个方案的能力：蒙特卡罗方法的再一个特点是，对于那些需要计算多个方案的问题，有时不需要象常规方法那样逐个方案遂个计算，而可以同时计算所有的方案，其全部计算量几乎与计算一个方案的计算量相当。例如，上述穿透概率计算问题，当屏蔽层为均匀介质平几何情况，要计算I种厚度的穿透概率时，用蒙特卡罗方法只须计算最厚一种情况，其他厚度的穿透概率在计算最厚一种情况时稍加处理便可同时得到。详细些说，在计算最厚一种屏蔽层的穿透概率时，粒子在屏蔽层内随机游动，对于各种厚度的屏蔽层，粒子是离开，或离开再进入，也可能再离开等等情况是请清楚楚的。设第一次离开各种厚度的粒子数依次为，观察的粒子总数为N，则，便分别近似等于各种厚度屏蔽层的穿透概率。 蒙特卡罗方法的缺点：蒙特卡罗方法也存在一些缺点，这些缺点主要有，对于维数少的问 题，一般是二维和二维以下问题，它不如其他计算方法好；对于大的几何系统或小概率事件的计算问题，它的计算结果有时比真值偏低；误差是概率误差，而不是一般意义下的误差。 3. 伪随机数 我们已经看到，由具有已知分布的总体中产生简单子样，在蒙特卡罗方法的问题中占 有非常重要的地位。总体和子样的关系属于一般和若干个别的关系，或者说属于共性和若干个性的关系。由具有已知分布的总体中产生简单子样，就是由简单子样中的诸个性近似地反映总体的共性。 在连续型分布中，最简单而又最基本的一个分布是单位均匀分布。在蒙特卡罗方法中常把该分布的简单子样作为基本量来看待，而由其他分布中产生简单子样时把它看成是已知的。因此，它们虽然都属于由具有已知分布的总体中产生简单子样的问题，但就产生的方法而言，它们之间却有着本质上的差别。均匀分布也常称为矩形分布，其中最基本的是单位均匀分布。单位均匀分布的密度函数如下： f(x) = 1，0≤x≤1。 由具有单位均匀分布的总体中产生的简单子样：，简称为随机数序列，其中的每一个 体称为随机数。随机数在蒙特卡罗方法中占有极其重要的地位。根据随机数的定义，随机数序列是相互独立的具有相同单位均匀分布的随机变量序列。随机数具有非常重要的性质：对于任意自然数S，由S个随机数所组成的S维空间上的点在S维空间的单位方体上均匀分布，亦即对于任意的，0≤≤1，i = 1，…，S，如下等式成立：反之，如果随机变量序列，对于任意自然数S，由S个元素所组成的 维空间上的点在上均匀分布，则随机变数序列是随机数序列。在机器中若没有随机数发生器，可以用下面的子程序RAN产生随机数(在主程序中要先调用INITRAN置初值)。 4. 由已知分布的随机抽样 由已知分布的随机抽样指的是由已知分布的总体中产生简单子样。用F(x)表示已知分布的分布函数，，表示由总体F(x)中产生的容量为N的简单子样。按照简单子样的定义，是用相互独立的抽样方法产生的，具有相同的分布F(x)。由已知分布的随机抽样简称为随机抽样。用表示由已知分布F(x)所产生的简单子样中的个体。对于连续型分布常用密度函数f(x)表示总体的已知分布。用表示由已知分布f(x)所产生的简单子样中的个体。抽样方法有好几种，如直接抽样方法、舍选抽样方法、复合抽样方法、复合舍选抽样方法等。然而，由于在实际问题中随机变量所服从的分布是千差万别的，用这些方法实现随机抽样有时还会遇到困难。概括起来说，可能遇到的困难主要有以下两点：一点是有的分布用上述抽样方法虽然可以实现，但抽样效率很低；另一点是有的分布用上述方法虽然可以实现，抽样效率也不低，但运算量太大。由于上述原因，常采用某种近似抽样方法。 5. 系综的平均观测量 6. 线型高分子链构象模拟示例 线型高分子是由数目很大的结构单元连接而成的长链分子，例如分子量为28,000的聚 乙烯(PE)，结构单元数 = 1000。由于热运动及分子中的单键可以旋转而产生许多不同的构象。当分子量确定后，随着构象的变化，分子的尺寸也在变化。我们用分子末端距（线型高分子链两端的直线距离，h）的均方根来作为描述分子尺寸的参数，通常称为根均方末端距。一般情况下h应该是分子内化学键向量和的模长（e是单位向量，n和l分别为键数和键长）高分子链完全伸直时，主链为锯齿状，对聚乙烯有，l = 0.154nm。根据高分子构象的一些理论模型可以导出分子末端距。例如：柔性链模型的模拟则是在以链段长为半径的球面上取均匀分布的随机点，作为下一链段的起点。同样在n步以后，计算该链的末端距平方。统计了N条高分子链以后，计算出均方末端距。 7. 固体反应中成核过程模拟示例（化学物理学报，7/4 (1994)，118） 固体反应与在流体中进行的反应有很大差别，一般分为成核与生长两个阶段。在较低温度下，分散在母相中的产物以替代缺陷形式占据晶格点，构成二元物系。在成对最近邻相互作用近似下，各向同性互作用系的哈密顿可以表示为式中A和B分别是缺陷在格点上的形成能和成对能；当i格点被产物缺陷占据时，占有数= 1，否则，被反应物占据时，占有数 = 0；表示对所有格点位置求和， 表示求和仅对i的最近邻进行。因而分别是缺陷总数和缺陷对数。哈密顿第二项前的负号表示产物缺陷成对使体系能量降低，这是产物相能成核从反应物相中分离出来的原因。
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-11-25, 05:22 PM
|
#8 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
概率算法简介
——————————————————————————————————
很多算法的每一个计算步骤都是固定的，而在下面我们要讨论的概率算法，允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。 概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。 蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。 拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。 舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。 本文简要的介绍一下数值概率算法和舍伍德算法。 首先来谈谈随机数。随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。 产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列a1,a2,...,an满足 a0=d an=(ban-1+c)mod m n=1,2....... 其中,b>=0, c>=0, d>=m。d称为该随机序列的种子。 下面我们建立一个随机数类RadomNumber，该类包含一个由用户初始化的种子randSeed。给定种子之后，既可产生与之相应的随机数序列。randseed是一个无符号长整型数，既可由用户指定也可由系统时间自动产生。const unsigned long maxshort=65536L const unsigned long multiplier=1194211693L const unsigned long adder=12345L class RandomNumber { private: //当前种子 unsigned long randseed public: //构造函数，缺省值0表示由系统自动产生种子 RandomNumber(unsigned long s=0) //产生0-n-1之间的随机整数 unsigned short Random(unsigned long n) //产生[0，1)之间的随机实数 double fRandom(void) } RandomNumber::RandomNumber(unsigned long s) { if(s==0) randseed=time(0) else randseed=s } unsigned short RandomNumber::Random(unsigned long n) { randseed=multiplier*randseed+adder return (unsigned short)((randseed>>16)%n) } double RandomNumber::fRandom(void) { return Random(maxshort)/double(maxshort) } 函数Random在每次计算时，用线性同余式计算新的种子。它的高16位的随机性较好，将randseed右移16位得到一个0-65535之间的随机整数然后再将此随机整数映射到0-n-1范围内。 对于函数fRandom,先用Random(maxshort)产生一个0-(maxshort-1之间的整型随机序列)，将每个整型随机数除以maxshort，就得到[0，1）区间中的随机实数。 下面来看看数值概率算法的两个例子： 1.用随机投点法计算π 设有一半径为r的圆及其外切四边形，如图所示。向该正方形随机投掷n个点。设落入圆内的点在正方形上均匀分布，因而所投入点落入圆内的概率为πr^2/4r^2，所以当n足够大时，k与n之比就逼近这一概率，即π/4。由此可得使用随机投点法计算π值的数值概率算法。具体实现时，只需要在第一次象限计算即可。  double Darts(int n){ static RandomNumber dart int k=0 for(int i=1i<=ni++){ double x=dart.fRandom() double y=dart.fRandom() if((x*x+y*y)<1) k++ } return 4*k/double(n) } 再简单举个舍伍德算法的例子。 我们在分析一个算法在平均情况下的计算复杂性时，通常假定算法的输入数据服从某一特定的概率分布。例如，在输入数据是均匀分布时，快速排序算法所需的平均时间是O(n logn)。但是如果其输入已经基本上排好序时，所用时间就大大增加了。此时，可采用舍伍德算法消除算法所需计算时间与输入实例间的这种联系。 在这里，我们用舍伍德型选择算法随机的选择一个数组元素作为划分标准。这样既能保证算法的线性时间平均性能又避免了计算拟中位数的麻烦。非递归的舍伍德型算法可描述如下： template<class Type> Type select(Type a[], int l, int r, int k) { static RandomNumber rnd while(true){ if(l>=r) return a[l] int i=l, j=l=rnd.Random(r-l+1) Swap(a[i], a[j]) j=r+1 Type pivot=a[l] while(true) { while(a[++i]<pivot) while(a[--j]>pivot) if(i>=j) break Swap(a[i], a[j]) } if(j-l+1==k) return pivot a[l]=a[j] a[j]=pivot if(j-l+1<k) { k=k-j+l-1 l=j+1 } else r=j-1 } } template <class Type> Type Select(Type a[], int n, int k) { if(k<1||k>n) throw OutOfBounds() return select(a, 0, n-1, k) } 平时我们一般开始考虑的是一个有着很好平均性能的选择算法，但在最坏情况下对某些实例算法效率较低。这时候我们用概率算法，将上述算法改造成一个舍伍德型算法，使得该算法对任何实例均有效。 不过在有些情况下，所给的确定性算法无法直接改造成舍伍德型算法。这时候就可以借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可以得到舍伍德算法的效果。还是刚才的例子，换一种方法实现： template<class Type> void Shuffle(Type a[], int n) { static RandomNumber rnd for(int i=1i<ni++){ int j=rnd.Random(n-i)+i Swap(a[i], a[j]) } } 在上文里，我们对概率算法中的数值概率算法以及舍伍德算法举例作了简要的介绍，希望能使大家对概率算法有一个初步的认识，并且将这种思想运用到自己平时的编程中。 http://i.mop.com/xiaojunping/blog/2...03/4459224.html
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-12-24, 09:47 PM
|
#9 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
感谢原作者：hisky(苍竹琴声)
一个比方 在工程实践中，经常会接触到一些比较“新颖”的算法或理论，比如模拟退火，遗传算法，禁忌搜索，神经网络等。这些算法或理论都有一些共同的特性（比如模拟自然过­程），通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。 这些算法都有什么含义？首先给出个局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻： 为了找出地球上最高的山，一群有志气的兔子们开始想办法。 1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。 2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。 3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的­兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。 4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这­就是禁忌搜索。 智能优化算法的概述 智能优化算法要解决的一般是最优化问题。最优化问题可以分为（1）求解一个函数中，使得函数值最小的自变量取值的函数优化问题和（2）在一个解空间里面，寻找最­优解，使目标函数值最小的组合优化问题。典型的组合优化问题有：旅行商问题（Traveling Salesman Problem，TSP），加工调度问题（Scheduling Problem），0－1背包问题（Knapsack Problem），以及装箱问题（Bin Packing Problem）等。 优化算法有很多，经典算法包括：有线性规划，动态规划等；改进型局部搜索算法包括爬山法，最速下降法等，本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜­索法。而神经网络，混沌搜索则属于系统动态演化方法。 优化思想里面经常提到邻域函数，它的作用是指出如何由当前解得到一个（组）新解。其具体实现方式要根据具体问题分析来定。 一般而言，局部搜索就是基于贪婪思想利用邻域函数进行搜索，若找到一个比现有值更优的解就弃前者而取后者。但是，它一般只可以得到“局部极小解”，就是说，可能­这只兔子登“登泰山而小天下”，但是却没有找到珠穆朗玛峰。而模拟退火，遗传算法，禁忌搜索，神经网络等从不同的角度和策略实现了改进，取得较好的“全局最小解­”。 模拟退火算法（Simulated Annealing，SA） 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候，粒子间的布朗运动增强，到达一定强度后，固体物质转化为液态，这个时候再­进行退火，粒子热运动减弱，并逐渐趋于有序，最后达到稳定。 模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率p。如果新的点（设为pn）的目标函数f（pn）更好，则p=1，表示选取新点；否­则，接受概率p是当前点（设为pc）的目标函数f（pc），新点的目标函数f（pn）以及另一个控制参数“温度”T的函数。也就是说，模拟退火没有像局部搜索那­样每次都贪婪地寻找比现在好的点，目标函数差一点的点也有可能接受进来。随着算法的执行，系统温度T逐渐降低，最后终止于某个低温，在该温度下，系统不再接受变­化。 模拟退火的典型特征是除了接受目标函数的改进外，还接受一个衰减极限，当T较大时，接受较大的衰减，当T逐渐变小时，接受较小的衰减，当T为0时，就不再接受衰­减。这一特征意味着模拟退火与局部搜索相反，它能避开局部极小，并且还保持了局部搜索的通用性和简单性。 在物理上，先加热，让分子间互相碰撞，变成无序状态，内能加大，然后降温，最后的分子次序反而会更有序，内能比没有加热前更小。就像那只兔子，它喝醉后，对比较­近的山峰视而不见，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。 值得注意的是，当T为0时，模拟退火就成为局部搜索的一个特例。 模拟退火的伪码表达： procedure simulated annealing begin t:=0; initialize temperature T select a current string vc at random; evaluate vc; repeat repeat select a new string vn in the neighborhood of vc; (1) if f(vc) then vc:=vn; else if random [0,1] then vc:=vn; until (termination-condition) (3) T:=g(T,t); (4) T:=t+1; until (stop-criterion) (5) end; 上面的程序中，关键的是(1)新状态产生函数，(2)新状态接受函数，(3)抽样稳定准则，(4)退温函数，(5)退火结束准则 （简称三函数两准则）是直接影响优化结果的主要环节。虽然实验结果证明初始值对于最后的结果没有影响，但是初温越高，得到高质量解的概率越大。所以，应该尽量选­取比较高的初温。 上面关键环节的选取策略： （1）状态产生函数：候选解由当前解的邻域函数决定，可以取互换，插入，逆序等操作产生，然后根据概率分布方式选取新的解，概率可以取均匀分布、正态分布、高斯­分布、柯西分布等。 （2）状态接受函数：这个环节最关键，但是，实验表明，何种接受函数对于最后结果影响不大。所以，一般选取min [1, exp ((f (vn)-f (vc))/T)]。 （3）抽样稳定准则：一般常用的有：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；规定一定的步数； （4）退温函数：如果要求温度必须按照一定的比率下降，SA算法可以采用 ，但是温度下降很慢；快速SA中，一般采用 。目前，经常用的是 ， 是一个不断变化的值。 （5）退火结束准则：一般有：设置终止温度；设置迭代次数；搜索到的最优值连续多次保持不变；检验系统熵是否稳定。 为了保证有比较优的解，算法往往采取慢降温、多抽样、以及把“终止温度”设的比较低等方式，导致算法运行时间比较长，这也是模拟退火的最大缺点。人喝醉了酒办起­事来都不利索，何况兔子？ 遗传算法（Genetic Algorithm, GA） “物竞天择，适者生存”，是进化论的基本思想。遗传算法就是模拟自然界想做的事。遗传算法可以很好地用于优化问题，若把它看作对自然过程高度理想化的模拟，更能­显出它本身的优雅——虽然生存竞争是残酷的。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码­、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成­为重要的智能算法之一。 遗传算法的伪码： procedure genetic algorithm begin initialize a group and evaluate the fitness value ; （1） while not convergent （2） begin select; （3） if random[0,1] crossover; （4） if random (0,1) mutation; （5） end; end 上述程序中有五个重要的环节： （1）编码和初始群体的生成：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。然后随机产­生N个初始串结构数据，每个串结构数据称为一个个体， N个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。 比如，旅行商问题中，可以把商人走过的路径进行编码，也可以对整个图矩阵进行编码。编码方式依赖于问题怎样描述比较好解决。初始群体也应该选取适当，如果选取的­过小则杂交优势不明显，算法性能很差（数量上占了优势的老鼠进化能力比老虎强），群体选取太大则计算量太大。 （2）检查算法收敛准则是否满足，控制算法是否结束。可以采用判断与最优解的适配度或者定一个迭代次数来达到。 （3）适应性值评估检测和选择：适应性函数表明个体或解的优劣性，在程序的开始也应该评价适应性，以便和以后的做比较。不同的问题，适应性函数的定义方式也不同­。根据适应性的好坏，进行选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行­选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 （4）杂交：按照杂交概率（pc）进行杂交。杂交操作是遗传算法中最主要的遗传操作。通过杂交操作可以得到新一代个体，新个体组合了其父辈个体的特性。杂交体现­了信息交换的思想。 可以选定一个点对染色体串进行互换，插入，逆序等杂交，也可以随机选取几个点杂交。杂交概率如果太大，种群更新快，但是高适应性的个体很容易被淹没，概率小了搜­索会停滞。 （5）变异：按照变异概率（pm）进行变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，­GA中变异发生的概率很低。变异为新个体的产生提供了机会。 变异可以防止有效基因的缺损造成的进化停滞。比较低的变异概率就已经可以让基因不断变更，太大了会陷入随机搜索。想一下，生物界每一代都和上一代差距很大，会是­怎样的可怕情形。 就像自然界的变异适和任何物种一样，对变量进行了编码的遗传算法没有考虑函数本身是否可导，是否连续等性质，所以适用性很强；并且，它开始就对一个种群进行操作­，隐含了并行性，也容易找到“全局最优解”。 禁忌搜索算法（Tabu Search，TS） 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是­对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地­方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一­个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当­一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达： procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中有关键的几点： （1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当然值在同一“等高线”上的都放进tabu list。 （2）为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太小容易陷入“局部极优解”。 （3）上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于best_to_far的，候选解也全部被禁的­“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。 （4）终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步­保持不变时，终止搜索； 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。 人工神经网络（Artificial Neural Network，ANN） 神经网络从名字就知道是对人脑的模拟。它的神经元结构，它的构成与作用方式都是在模仿人脑，但是也仅仅是粗糙的模仿，远没有达到完美的地步。和冯·诺依曼机不同­，神经网络计算非数字，非精确，高度并行，并且有自学习功能。 生命科学中，神经细胞一般称作神经元，它是整个神经结构的最基本单位。每个神经细胞就像一条胳膊，其中像手掌的地方含有细胞核，称作细胞体，像手指的称作树突，­是信息的输入通路，像手臂的称作轴突，是信息的输出通路；神经元之间错综复杂地连在一起，互相之间传递信号，而传递的信号可以导致神经元电位的变化，一旦电位高­出一定值，就会引起神经元的激发，此神经元就会通过轴突传出电信号。 而如果要用计算机模仿生物神经，就需要人工的神经网络有三个要素：（1）形式定义人工神经元；（2）给出人工神经元的连接方式，或者说给出网络结构；（3）给出­人工神经元之间信号强度的定义。 历史上第一个人工神经网络模型称作M－P模型，非常简单： 其中， 表示神经元i在t时刻的状态，为1表示激发态，为0表示抑制态； 是神经元i和j之间的连接强度； 表示神经元i的阈值，超过这个值神经元才能激发。 这个模型是最简单的神经元模型。但是功能已经非常强大：此模型的发明人McCulloch和Pitts已经证明，不考虑速度和实现的复杂性，它可以完成当前数字­计算机的任何工作。 以上这个M－P模型仅仅是一层的网络，如果从对一个平面进行分割的方面来考虑的话，M－P网络只能把一个平面分成个半平面，却不能够选取特定的一部分。而解决的­办法就是“多层前向网路”。 图2 图2是多层前向网络的示意图。最下面的 称作输入层，最上面一层称作输出层，任何一个中间层都接受来自前一层的所有输入，加工后传入后一层。每一层的神经元之间没有联系，输入输出层之间也没有直接联系­，并且仅仅是单向联系，没有反馈。这样的网络被称作“多层前向网络”。数据在输入后，经过每一层的加权，最后输出结果。 图3 如图3，用可覆盖面来说明多层网络的功能：单层网络只能把平面分成两部分，双层网络就可以分割任意凸域，多层网络则可以分割任意区域。 为了让这种网络有合适的权值，必须给网络一定的激励，让它自己学习，调整。一种方法称作“向后传播算法（Back Propagation，BP）”，其基本思想是考察最后输出解和理想解的差异，调整权值，并把这种调整从输出层开始向后推演，经过中间层，达到输入层。 可见，神经网络是通过学习来达到解决问题的目的，学习没有改变单个神经元的结构和工作方式，单个神经元的特性和要解决的问题之间也没有直接联系，这里学习的作用­是根据神经元之间激励与抑制的关系，改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每个权值之中。 BP算法中有考察输出解和理想解差异的过程，假设差距为w，则调整权值的目的就是为了使得w最小化。这就又包含了前文所说的“最小值”问题。一般的BP算法采用­的是局部搜索，比如最速下降法，牛顿法等，当然如果想要得到全局最优解，可以采用模拟退火，遗传算法等。当前向网络采用模拟退火算法作为学习方法的时候，一般成­为“波尔兹曼网络”，属于随机性神经网络。 在学习BP算法学习的过程中，需要已经有一部分确定的值作为理想输出，这就好像中学生在学习的时候，有老师的监督。如果没有了监督，人工神经网络该怎么学习？ 就像没有了宏观调控，自由的市场引入了竞争一样，有一种学习方法称作“无监督有竞争的学习”。在输入神经元i的若干个神经元之间开展竞争，竞争之后，只有一个神­经元为1，其他均为0，而对于失败的神经元，调整使得向对竞争有利的方向移动，则最终也可能在一次竞争中胜利； 人工神经网络还有反馈网络如Hopfield网络，它的神经元的信号传递方向是双向的，并且引入一个能量函数，通过神经元之间不断地相互影响，能量函数值不断下­降，最后能给出一个能量比较低的解。这个思想和模拟退火差不多。 人工神经网络应用到算法上时，其正确率和速度与软件的实现联系不大，关键的是它自身的不断学习。这种思想已经和冯·诺依曼模型很不一样。 总结 模拟退火，遗传算法，禁忌搜索，神经网络在解决全局最优解的问题上有着独到的优点，并且，它们有一个共同的特点：都是模拟了自然过程。模拟退火思路源于物理学中­固体物质的退火过程，遗传算法借鉴了自然界优胜劣汰的进化思想，禁忌搜索模拟了人类有记忆过程的智力过程，神经网络更是直接模拟了人脑。 它们之间的联系也非常紧密，比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起，取长补短，性能将更加优良。 这几种智能算法有别于一般的按照图灵机进行精确计算的程序，尤其是人工神经网络，是对计算机模型的一种新的诠释，跳出了冯·诺依曼机的圈子，按照这种思想来设计­的计算机有着广阔的发展前景 禁忌搜索算法（Tabu Search，TS） 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达： procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中有关键的几点： （1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当然值在同一“等高线”上的都放进tabu list。 （2）为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太小容易陷入“局部极优解”。 （3）上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于best_to_far的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。 （4）终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终止搜索； 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。 人工神经网络（Artificial Neural Network，ANN） 神经网络从名字就知道是对人脑的模拟。它的神经元结构，它的构成与作用方式都是在模仿人脑，但是也仅仅是粗糙的模仿，远没有达到完美的地步。和冯·诺依曼机不同，神经网络计算非数字，非精确，高度并行，并且有自学习功能。 生命科学中，神经细胞一般称作神经元，它是整个神经结构的最基本单位。每个神经细胞就像一条胳膊，其中像手掌的地方含有细胞核，称作细胞体，像手指的称作树突，是信息的输入通路，像手臂的称作轴突，是信息的输出通路；神经元之间错综复杂地连在一起，互相之间传递信号，而传递的信号可以导致神经元电位的变化，一旦电位高出一定值，就会引起神经元的激发，此神经元就会通过轴突传出电信号。 而如果要用计算机模仿生物神经，就需要人工的神经网络有三个要素：（1）形式定义人工神经元；（2）给出人工神经元的连接方式，或者说给出网络结构；（3）给出人工神经元之间信号强度的定义。 历史上第一个人工神经网络模型称作M－P模型，非常简单： 其中， 表示神经元i在t时刻的状态，为1表示激发态，为0表示抑制态； 是神经元i和j之间的连接强度； 表示神经元i的阈值，超过这个值神经元才能激发。 这个模型是最简单的神经元模型。但是功能已经非常强大：此模型的发明人McCulloch和Pitts已经证明，不考虑速度和实现的复杂性，它可以完成当前数字计算机的任何工作。 以上这个M－P模型仅仅是一层的网络，如果从对一个平面进行分割的方面来考虑的话，M－P网络只能把一个平面分成个半平面，却不能够选取特定的一部分。而解决的办法就是“多层前向网路”。 图2 图2 是多层前向网络的示意图。最下面的称作输入层，最上面一层称作输出层，任何一个中间层都接受来自前一层的所有输入，加工后传入后一层。每一层的神经元之间没有联系，输入输出层之间也没有直接联系，并且仅仅是单向联系，没有反馈。这样的网络被称作“多层前向网络”。数据在输入后，经过每一层的加权，最后输出结果。 图3 如图3，用可覆盖面来说明多层网络的功能：单层网络只能把平面分成两部分，双层网络就可以分割任意凸域，多层网络则可以分割任意区域。 为了让这种网络有合适的权值，必须给网络一定的激励，让它自己学习，调整。一种方法称作“向后传播算法（Back Propagation，BP）”，其基本思想是考察最后输出解和理想解的差异，调整权值，并把这种调整从输出层开始向后推演，经过中间层，达到输入层。 可见，神经网络是通过学习来达到解决问题的目的，学习没有改变单个神经元的结构和工作方式，单个神经元的特性和要解决的问题之间也没有直接联系，这里学习的作用是根据神经元之间激励与抑制的关系，改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每个权值之中。 BP算法中有考察输出解和理想解差异的过程，假设差距为w，则调整权值的目的就是为了使得w最小化。这就又包含了前文所说的“最小值”问题。一般的BP算法采用的是局部搜索，比如最速下降法，牛顿法等，当然如果想要得到全局最优解，可以采用模拟退火，遗传算法等。当前向网络采用模拟退火算法作为学习方法的时候，一般成为“波尔兹曼网络”，属于随机性神经网络。 在学习BP算法学习的过程中，需要已经有一部分确定的值作为理想输出，这就好像中学生在学习的时候，有老师的监督。如果没有了监督，人工神经网络该怎么学习？ 就像没有了宏观调控，自由的市场引入了竞争一样，有一种学习方法称作“无监督有竞争的学习”。在输入神经元i的若干个神经元之间开展竞争，竞争之后，只有一个神经元为1，其他均为0，而对于失败的神经元，调整使得向对竞争有利的方向移动，则最终也可能在一次竞争中胜利； 人工神经网络还有反馈网络如Hopfield网络，它的神经元的信号传递方向是双向的，并且引入一个能量函数，通过神经元之间不断地相互影响，能量函数值不断下降，最后能给出一个能量比较低的解。这个思想和模拟退火差不多。 人工神经网络应用到算法上时，其正确率和速度与软件的实现联系不大，关键的是它自身的不断学习。这种思想已经和冯·诺依曼模型很不一样。 总结 模拟退火，遗传算法，禁忌搜索，神经网络在解决全局最优解的问题上有着独到的优点，并且，它们有一个共同的特点：都是模拟了自然过程。模拟退火思路源于物理学中固体物质的退火过程，遗传算法借鉴了自然界优胜劣汰的进化思想，禁忌搜索模拟了人类有记忆过程的智力过程，神经网络更是直接模拟了人脑。 它们之间的联系也非常紧密，比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供了思路。把它们有机地综合在一起，取长补短，性能将更加优良。 这几种智能算法有别于一般的按照图灵机进行精确计算的程序，尤其是人工神经网络，是对计算机模型的一种新的诠释，跳出了冯·诺依曼机的圈子，按照这种思想来设计的计算机有着广阔的发展前景。
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
|
2008-12-24, 09:52 PM
|
#10 |
|
超级版主
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
|
回复: 模拟退火算法
PSO粒子群优化算法
1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍
同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域
2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的内容
1. 研究如何利用计算技术研究生物现象
2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的.
现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为
例如floys 和 boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计.
在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上.
粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具.
3. 算法介绍
如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索
PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。
在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置
v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b) v[] 是粒子的速度, persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.
程序的伪代码如下
For each particle
____Initialize particle END Do
____For each particle ________Calculate fitness value ________If the fitness value is better than the best fitness value (pBest) in history ____________set current value as the new pBest ____End ____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle ________Calculate particle velocity according equation (a) ________Update particle position according equation (b) ____End While maximum iterations or minimum error criteria is not attained 在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax
4. 遗传算法和 PSO 的比较
大多数演化计算技术都是用同样的过程
1. 种群随机初始化 2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关 3. 种群根据适应值进行复制 4. 如果终止条件满足的话，就停止，否则转步骤2 从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解
但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。
与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子， 这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解
5. 人工神经网络 和 PSO
人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人工神经网络的各个方面。
演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。
不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值
演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦
最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题
这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmark function)IRIS数据集。(Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。
我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。
6. PSO的参数设置
从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数
PSO的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误 PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置
粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200
粒子的长度: 这是由优化问题决定, 就是问题解的长度
粒子的范围: 由优化问题决定,每一维可是设定不同的范围
Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20
学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间
中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.
全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.
另外的一个参数是惯性权重, 由Shi 和Eberhart提出, 有兴趣的可以参考他们1998年的论文(题目: A modified particle swarm optimizer)
7. Online Resources of PSO
The development of PSO is still ongoing. And there are still many unknown areas in PSO research such as the mathematical validation of particle swarm theory.
One can find much information from the internet. Following are some information you can get online:
http://www.particleswarm.net lots of information about Particle Swarms and, particularly, Particle Swarm Optimization. lots of Particle Swarm Links.
http://icdweb.cc.purdue.edu/~hux/PSO.shtml lists an updated bibliography of particle swarm optimization and some online paper links
http://www.researchindex.com/ you can search particle swarm related papers and references.
2006.7.11 13:20 作者：xiao1junif(blogID!=null)document.writeln('<a href="http://'+blogID+'/trackback/doTrackDiary.b?trackDiaryUrl=http://xiao1jun.bokee.com/trackback/trackDiary.b?diaryId=12059089" class="ln-trackbacks">引用0 | '); 收藏 | 评论：0 蚁群算法 简介：蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。  然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明： 1、范围： 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 2、环境： 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 3、觅食规则： 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。 4、移动规则： 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 5、避障规则： 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 7、播撒信息素规则： 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。 问题： 说了这么多，蚂蚁究竟是怎么找到食物的呢？ 在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。 当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。 蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。 引申: 跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点： 1、多样性 2、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！ 参数说明： 最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。 错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。 速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。 记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。 2006.7.11 13:08 作者：xiao1junif(blogID!=null)document.writeln('<a href="http://'+blogID+'/trackback/doTrackDiary.b?trackDiaryUrl=http://xiao1jun.bokee.com/trackback/trackDiary.b?diaryId=12059003" class="ln-trackbacks">引用0 | '); 收藏 | 评论：0 智能算法综述 1 什么是智能算法 智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。 2 人工神经网络算法 “人工神经网络”(ARTIFICIAL NEURALNETWORK，简称ANN)是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年代初期，心理学家McCulloch、数学家Pitts就提出了人工神经网络的第一个数学模型，从此开创了神经科学理论的研究时代。其后，FRosenblatt、Widrow和J. J .Hopfield等学者又先后提出了感知模型，使得人工神经网络技术得以蓬勃发展。 神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本单元。据神经生物学家研究的结果表明，人的一个大脑一般有1010～1011个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支——树突组成。轴突的功能是将本神经元的输出信号(兴奋)传递给别的神经元。其末端的许多神经末梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到的所有信号进行简单处理(如：加权求和，即对所有的输入信号都加以考虑且对每个信号的重视程度——体现在权值上——有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。 2.1 人工神经网络的特点 人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点决定着人工神经网络具有高速信息处理的能力。人脑的每个神经元大约有103～104个树突及相应的突触，一个人的大脑总计约形成1014～1015个突触。用神经网络的术语来说，即是人脑具有1014～1015个互相连接的存储潜力。虽然每个神经元的运算功能十分简单，且信号传输速率也较低(大约100次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1秒内就能完成现行计算机至少需要数10亿次处理步骤才能完成的任务。 人工神经网络的知识存储容量很大。在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息，而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。 由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清，神经网络仍然能够联想思维存在于记忆中的事物的完整图象。只要输入的模式接近于训练样本，系统就能给出正确的推理结论。 正是因为人工神经网络的结构特点和其信息存储的分布式特点，使得它相对于其它的判断识别系统，如：专家系统等，具有另一个显著的优点：健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受轻微损伤之后，并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因，无论是网络的硬件实现还是软件实现中的某个或某些神经元失效，整个网络仍然能继续工作。 人工神经网络是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃。 2.2 几种典型神经网络简介 2.2.1 多层感知网络(误差逆传播神经网络) 在1986年以Rumelhart和McCelland为首的科学家出版的《ParallelDistributed Processing》一书中，完整地提出了误差逆传播学习算法，并被广泛接受。多层感知网络是一种具有三层或三层以上的阶层型神经网络。典型的多层感知网络是三层、前馈的阶层网络，即：输入层I、隐含层(也称中间层)J和输出层K。相邻层之间的各神经元实现全连接，即下一层的每一个神经元与上一层的每个神经元都实现全连接，而且每层各神经元之间无连接。 但BP网并不是十分的完善，它存在以下一些主要缺陷：学习收敛速度太慢、网络的学习记忆具有不稳定性，即：当给一个训练好的网提供新的学习记忆模式时，将使已有的连接权值被打乱，导致已记忆的学习模式的信息的消失。 2.2.2 竞争型(KOHONEN)神经网络 它是基于人的视网膜及大脑皮层对剌激的反应而引出的。神经生物学的研究结果表明：生物视网膜中，有许多特定的细胞，对特定的图形(输入模式)比较敏感，并使得大脑皮层中的特定细胞产生大的兴奋，而其相邻的神经细胞的兴奋程度被抑制。对于某一个输入模式，通过竞争在输出层中只激活一个相应的输出神经元。许多输入模式，在输出层中将激活许多个神经元，从而形成一个反映输入数据的“特征图形”。竞争型神经网络是一种以无教师方式进行网络训练的网络。它通过自身训练，自动对输入模式进行分类。竞争型神经网络及其学习规则与其它类型的神经网络和学习规则相比，有其自己的鲜明特点。在网络结构上，它既不象阶层型神经网络那样各层神经元之间只有单向连接，也不象全连接型网络那样在网络结构上没有明显的层次界限。它一般是由输入层(模拟视网膜神经元)和竞争层(模拟大脑皮层神经元，也叫输出层)构成的两层网络。两层之间的各神经元实现双向全连接，而且网络中没有隐含层。有时竞争层各神经元之间还存在横向连接。竞争型神经网络的基本思想是网络竞争层各神经元竞争对输入模式的响应机会，最后仅有一个神经元成为竞争的胜者，并且只将与获胜神经元有关的各连接权值进行修正，使之朝着更有利于它竞争的方向调整。神经网络工作时，对于某一输入模式，网络中与该模式最相近的学习输入模式相对应的竞争层神经元将有最大的输出值，即以竞争层获胜神经元来表示分类结果。这是通过竞争得以实现的，实际上也就是网络回忆联想的过程。 除了竞争的方法外，还有通过抑制手段获取胜利的方法，即网络竞争层各神经元抑制所有其它神经元对输入模式的响应机会，从而使自己“脱颖而出”，成为获胜神经元。除此之外还有一种称为侧抑制的方法，即每个神经元只抑制与自己邻近的神经元，而对远离自己的神经元不抑制。这种方法常常用于图象边缘处理，解决图象边缘的缺陷问题。 竞争型神经网络的缺点和不足：因为它仅以输出层中的单个神经元代表某一类模式。所以一旦输出层中的某个输出神经元损坏，则导致该神经元所代表的该模式信息全部丢失。 2.2.3 Hopfield神经网络 1986年美国物理学家J.J.Hopfield陆续发表几篇论文，提出了Hopfield神经网络。他利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利用此方法建立求解优化计算问题的系统方程式。基本的Hopfield神经网络是一个由非线性元件构成的全连接型单层反馈系统。 网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元，同时又都接收所有其它神经元传递过来的信息。即：网络中的神经元t时刻的输出状态实际上间接地与自己的t-1时刻的输出状态有关。所以Hopfield神经网络是一个反馈型的网络。其状态变化可以用差分方程来表征。反馈型网络的一个重要特点就是它具有稳定状态。当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。这里的能量函数不是物理意义上的能量函数，而是在表达形式上与物理意义上的能量概念一致，表征网络状态的变化趋势，并可以依据Hopfield工作运行规则不断进行状态变化，最终能够达到的某个极小值的目标函数。网络收敛就是指能量函数达到极小值。如果把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，那么Hopfield神经网络就能够用于解决优化组合问题。 对于同样结构的网络，当网络参数(指连接权值和阀值)有所变化时，网络能量函数的极小点(称为网络的稳定平衡点)的个数和极小值的大小也将变化。因此，可以把所需记忆的模式设计成某个确定网络状态的一个稳定平衡点。若网络有M个平衡点，则可以记忆M个记忆模式。 当网络从与记忆模式较靠近的某个初始状态(相当于发生了某些变形或含有某些噪声的记忆模式，也即：只提供了某个模式的部分信息)出发后，网络按Hopfield工作运行规则进行状态更新，最后网络的状态将稳定在能量函数的极小点。这样就完成了由部分信息的联想过程。 Hopfield神经网络的能量函数是朝着梯度减小的方向变化，但它仍然存在一个问题，那就是一旦能量函数陷入到局部极小值，它将不能自动跳出局部极小点，到达全局最小点，因而无法求得网络最优解。 3 遗传算法 遗传算法（Genetic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密执根（Michigan）大学的霍兰（Holland）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《Adaptationin Natural and Artificial Systems》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。 近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。 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值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 5 群体（群集）智能（Swarm Intelligence） 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。 群集智能的特点和优点：群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前网络环境下的工作状态; 没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信(Stimergy)进行合作，这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。因为具有这些优点，虽说群集智能的研究还处于初级阶段，并且存在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。 在计算智能(ComputationalIntelligence)领域有两种基于群智能的算法，蚁群算法(Ant Colony Optimization)和粒子群算法(ParticleSwarm Optimization)，前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。 5.1 蚁群优化算法 受蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群优化算法(Ant ColonyOptimization，ACO)来解决计算机算法学中经典的“货郎担问题”。如果有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。 在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近"的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。 蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法，它已经被成功用于解决其他组合优化问题，例如图的着色(GraphColoring)以及最短超串(Shortest Common Supersequence)等问题。 5.2 粒子群优化算法 粒子群优化算法(PSO)是一种进化计算技术(EvolutionaryComputation)，有Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。 PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。 同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。 5.2.1 算法介绍 PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。 5.2.2 PSO算法过程 ① 种群随机初始化。 ② 对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。 ③ 种群根据适应值进行复制 。 ④ 如果终止条件满足的话，就停止，否则转步骤 ② 。 从以上步骤，我们可以看到PSO和遗传算法有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉(crossover)和变异(mutation)，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。 与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中, 只有gBest (orlBest) 给出信息给其他的粒子， 这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。 现在已经有一些利用PSO代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法，同时PSO速度比较快而且可以得到比较好的结果。 6 展望 目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发展。不仅仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大成就。 转自：http://xiao1jun.bokee.com/
__________________
借用达朗贝尔的名言：前进吧，你会得到信心! [url="http://www.dimcax.com"]几何尺寸与公差标准[/url] |
|
|
|
平板模式
