智能计算综述

一．遗传算法1.遗传算法的一般步骤（1）对问题的解进行编码（二进制编码、十进制编码、实数编码、Gary编码）（2）形成编码后的初始种群方法：完全随机产生根据已知的先验知识进行随机选取（3）适应度函数的设计与计算目标函数：)(xf适应度函数：)(min)(xfxF)(max)(xfxF（4）遗传操作选择算子作用：判断个体是否优良判断标准：个体适应度函数值的大小方法：比例选择方法、精英选择方法、排序选择方法、联赛选择方法、期望值方法等交叉算子两个相互配对的个体按照某种方法相互交换各自的部分基因形成新个体方法：单点交叉、两点交叉、多点交叉、一直交叉变异算子类型：基本变异算子、逆转变异算子、自适应变异算子（5）算法终止一般设定最大迭代次数作为算法的终止条件，简单但不准确根据种群的收敛程度来判定算法是否停止FFFFimax或2.算法特点（1）与传统相比将问题参数编码成染色体后进行进化操作使算法不受函数约束条件的限制；采用群体搜索方法，具有隐含并行搜索特性；随机操作；④具有全局搜索能力，多用于复杂问题和非线性问题（2）优越性算法进行全空间并行搜索，很大概率找到全局最优解算法具有固定的并行性（3）多用于维数较高、环境复杂、问题结构不十分清楚的场合3.遗传算法的应用（1）加工中心组成问题（2）0-1背包问题二．蚁群优化算法一算法基础1.一群蚂蚁随机从出发点出发将在蚁巢和食物之间建立通路，当在觅食路上出现障碍时，蚁群会等概率地选择沿着障碍物向左或向右移动；2.蚂蚁会在路径上留下信息素以指导后面的蚁群移动；3.信息素随时间逐渐蒸发；4.由蚁巢出发的蚂蚁，其选择路径的概率与各路径上的信息素成正比，最终所有蚂蚁会选择同一条较短的路径；二算法模型1.所需的基本变量和常数令：m为蚁群中蚂蚁的总数n为旅行商问题中的城市个数ijd为i到j之间的距离，其中nji,1)(tij为第t次迭代（或t时刻）弧ji,上的信息素量初始时刻各弧上的信息素量相等，即cij)0(（c为常数）2.状态转移概率否则若0)()()()()()()(iJjtttttpkiJsisisijijkijk（2.1）值越大，蚂蚁选择以前经过路径的可能性就越大值越大，蚂蚁选择离开它最近的城市的可能性就越大3.信息素的更新采用参数表示信息素挥发系数，而1表示信息素的残留系数设：再经过l个时刻，蚂蚁完成一次循环ijijijtlt)(（2.2）其中mkkijij14.基本蚁群算法求解旅行商问题的主要步骤（1）初始化参数，0nc，gen，0t，cij)0(，将m只蚂蚁置于n个顶点上；（2）将初始出发点置于当前解路径集合中；对蚂蚁k计算选择城市j的概率kijp且j为蚂蚁未走过的城市，选择概率最大的城市，并将蚂蚁移动到该城市，记入ktabu，将该城市置于当前解路劲集合中；（3）分别计算m只蚂蚁找到的解所对应的目标函数值，并记录当前最优值；（4）按（2.2）来修改各个弧上的信息素量；（5）令1ncnc；（6）若nc小于预定gen且无退化行为，则转（2）5.蚁群算法的本质选择机制、更新机制、协调机制6.蚁群算法的特点（1）具有正反馈机制（2）较强的鲁棒性（3）分布式计算（4）通用型随机优化方法（5）易于其他方法结合7.蚁群算法的缺点（1）搜索时间较长（2）易出现停滞现象三．模拟退火算法1.模拟退火算法数学模型的组成：（1）解空间：关于一个问题所有可能的解的集合，它限定了初始解选取的范围和新解产生的范围（2）目标函数：若干优化目标的一个和式，其选取必须正确体现对问题的整体优化要求（3）初始解：开始迭代的起点2.模拟退火算法的基本思想从一个初始解出发，不断反复迭代产生新解，对新解进行判定、舍弃，最终取得令人满意的全局最优解3.运作流程（1）初始化：给定温度T的变化范围并对其初始化，对解S进行初始化，并计算初始化解S所对应的当前目标函数)(SE起点；注：初始值要求足够大，但也不宜过大；对每一温度下迭代的次数进行初始化（2）设一个整数K用来记录每一温度T下迭代已进行的次数，LK,0在每一温度T下，循环k次第（3）至（6）步；（3）产生一个新解S，根据目标函数分别计算当前解S和新解S所对应的)(SE和)(SE，并计算增量)()(SESEE（4）如果0E，则新解S代替当前解S作为新的当前解，新解所对应的SE作为新的当前目标函数值；（5）如果0E，则需计算新解的接受率KTSESEr)()(exp，若randr，则可以接受S作为新的当前解；（6）如果迭代满足终止条件，则输出当前解作为最优解，结束程序；（7）逐渐降低温度控制参数T，如T依然大于0，转步（2）对数降温策略：0log/KKaTk快速降温策略：)1/(KbTk直线降温策略：0)/1(TkKTk④指数降温策略：1kkTaT，]99.0,5.0[a4.模拟退火算法的特点（1）优点：具有渐近收敛性，而且计算过程简单、通用、鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题；（2）缺点：返回一个高质量的近似解的时间花费较多，当问题规模不可避免的增大时，难以承受的运作时间将使算法丧失可行性。5.模拟退火算法的改进途径（1）改变算法进行过程中的各种变异方法，如在算法中加入记忆器，记住算法进行过程中曾出现过的最优近似解；（2）对算法进行大规模的并行计算，真正缩短计算时间；（3）将模拟退火算法与其他智能搜索机制的算法相融合，取长补短。四、粒子群优化算法1.基本思想:粒子群优化算法就是对生物群体中的信息共享这种社会行为的模拟，即利用信息共享机制，使得个体之间可以相互借鉴经验，从而促进整个群体的发展。2.算法流程：（1）初始化粒子群，即随机设定各个粒子的初始位置X和初始速度V；（2）计算每个粒子的适应度；（3）对每个粒子，将它的适应度和它经历过的最好位置iP所对应的适应度做比较，如果好于后者，则更新iP，否则，iP保持不变；（4）将本次迭代中的每个粒子的适应度分别和群体所经历最好位置gP所对应的适应度作比较，如果好于后者，则更新gP，否则，gP保持不变；（5）根据式)(*()*)(*()*211titgtitititiXPrandCXPrandCVV和式11tititiVXX重新计算每个粒子的速度和位置；（6）如果算法满足结束条件（产生足够好的位置或达到预先设置的最大迭代次数），则算法终止，否则转步骤（2）。3.粒子群优化算法的特点：（1）粒子具有记忆性，可以记忆整个种群经历过的最有位置，并将其传递给其他的粒子；（2）需要调整的参数较少，算法结构简单；（3）没有复杂的运算，依赖粒子运动来完成搜索；（4）粒子的运动受到自身认知和社会认知的修正。