智能计算综述

1、1 遗传算法1.遗传算法的一般步骤（1）对问题的解进行编码（二进制编码、十进制编码、实数编码、Gary编码）（2）形成编码后的初始种群 方法：完全随机产生 根据已知的先验知识进行随机选取（3）适应度函数的设计与计算 目标函数： 适应度函数： （4）遗传操作 选择算子 作用：判断个体是否优良 判断标准：个体适应度函数值的大小 方法：比例选择方法、精英选择方法、排序选择方法、联赛选择方法、期望值方法等 交叉算子 两个相互配对的个体按照某种方法相互交换各自的部分基因形成新个体 方法：单点交叉、两点交叉、多点交叉、一直交叉 变异算子 类型：基本变异算子、逆转变异算子、自适应变异算子（5）算法终止 一般

2、设定最大迭代次数作为算法的终止条件，简单但不准确 根据种群的收敛程度来判定算法是否停止 2.算法特点（1）与传统相比 将问题参数编码成染色体后进行进化操作使算法不受函数约束条件的限制； 采用群体搜索方法，具有隐含并行搜索特性； 随机操作； 具有全局搜索能力，多用于复杂问题和非线性问题（2）优越性 算法进行全空间并行搜索，很大概率找到全局最优解 算法具有固定的并行性（3）多用于维数较高、环境复杂、问题结构不十分清楚的场合3.遗传算法的应用（1）加工中心组成问题（2）0-1背包问题2 蚁群优化算法<一>算法基础1. 一群蚂蚁随机从出发点出发将在蚁巢和食物之间建立通路，当在觅食路上出现障

3、碍时，蚁群会等概率地选择沿着障碍物向左或向右移动；2. 蚂蚁会在路径上留下信息素以指导后面的蚁群移动；3. 信息素随时间逐渐蒸发；4. 由蚁巢出发的蚂蚁，其选择路径的概率与各路径上的信息素成正比，最终所有蚂蚁会选择同一条较短的路径；<二>算法模型1. 所需的基本变量和常数令：为蚁群中蚂蚁的总数为旅行商问题中的城市个数为到之间的距离，其中为第次迭代（或时刻）弧上的信息素量初始时刻各弧上的信息素量相等，即（为常数）2. 状态转移概率 （2.1）值越大，蚂蚁选择以前经过路径的可能性就越大值越大，蚂蚁选择离开它最近的城市的可能性就越大3. 信息素的更新采用参数表示信息素挥发系数，而表示信息

4、素的残留系数设：再经过个时刻，蚂蚁完成一次循环 （2.2）其中4. 基本蚁群算法求解旅行商问题的主要步骤（1）初始化参数，将只蚂蚁置于n个顶点上；（2）将初始出发点置于当前解路径集合中；对蚂蚁计算选择城市的概率且为蚂蚁未走过的城市，选择概率最大的城市，并将蚂蚁移动到该城市，记入，将该城市置于当前解路劲集合中；（3）分别计算只蚂蚁找到的解所对应的目标函数值，并记录当前最优值；（4）按（2.2）来修改各个弧上的信息素量；（5）令；（6）若小于预定且无退化行为，则转（2）5.蚁群算法的本质选择机制、更新机制、协调机制6. 蚁群算法的特点（1） 具有正反馈机制 （2）较强的鲁棒性 （3）分布式计算（4

5、） 通用型随机优化方法 （5）易于其他方法结合7. 蚁群算法的缺点（1）搜索时间较长 （2）易出现停滞现象3 模拟退火算法1. 模拟退火算法数学模型的组成：（1） 解空间：关于一个问题所有可能的解的集合，它限定了初始解选取的范围和新解产生的范围（2） 目标函数：若干优化目标的一个和式，其选取必须正确体现对问题的整体优化要求（3） 初始解：开始迭代的起点2. 模拟退火算法的基本思想从一个初始解出发，不断反复迭代产生新解，对新解进行判定、舍弃，最终取得令人满意的全局最优解3.运作流程（1）初始化：给定温度的变化范围并对其初始化，对解进行初始化，并计算初始化解所对应的当前目标函数起点；注：初始值要求

6、足够大，但也不宜过大；对每一温度下迭代的次数进行初始化（2） 设一个整数用来记录每一温度下迭代已进行的次数，在每一温度下，循环次第（3）至（6）步；（3） 产生一个新解，根据目标函数分别计算当前解和新解所对应的和，并计算增量（4） 如果，则新解代替当前解作为新的当前解，新解所对应的作为新的当前目标函数值；（5） 如果，则需计算新解的接受率，若，则可以接受作为新的当前解；（6） 如果迭代满足终止条件，则输出当前解作为最优解，结束程序；（7） 逐渐降低温度控制参数，如依然大于0，转步（2） 对数降温策略： 快速降温策略： 直线降温策略： 指数降温策略：，4. 模拟退火算法的特点（1） 优点：具有渐

7、近收敛性，而且计算过程简单、通用、鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题；（2） 缺点：返回一个高质量的近似解的时间花费较多，当问题规模不可避免的增大时，难以承受的运作时间将使算法丧失可行性。5. 模拟退火算法的改进途径（1） 改变算法进行过程中的各种变异方法，如在算法中加入记忆器，记住算法进行过程中曾出现过的最优近似解；（2） 对算法进行大规模的并行计算，真正缩短计算时间；（3）将模拟退火算法与其他智能搜索机制的算法相融合，取长补短。4、 粒子群优化算法1. 基本思想:粒子群优化算法就是对生物群体中的信息共享这种社会行为的模拟，即利用信息共享机制，使得个体之间可以相互借鉴经验，从而促进整个群体的发展。2. 算法流程：（1） 初始化粒子群，即随机设定各个粒子的初始位置和初始速度；（2） 计算每个粒子的适应度；（3） 对每个粒子，将它的适应度和它经历过的最好位置所对应的适应度做比较，如果好于后者，则更新，否则，保持不变；（4） 将本次迭代中的每个粒子的适应度分别和群体所经历最好位置所对应的适应度作比较，如果好于后者，则更新，否则，保持不变；（5） 根据式 和式重新计算每个粒子的速度和位置；（6） 如果算法满足结束条件（产生足够好的位置或达到预先设置的最大迭代次数），则算法终止，否则转步骤（2）。