人工鱼群法在组合优化问题的研究_毕业论文(编辑修改稿)

人工鱼群法在组合优化问题的研究_毕业论文(编辑修改稿)内容摘要：

之间的路径上残留的信息量。 来模拟实际蚂蚁的信息素浓度。 在初始化的时候， m 个蚂蚁被放置在不同的城市上，赋予每条边上的信息量为 ij （ 0）。 每个蚂蚁 k 的 ktabu 的第一个元素赋值为它所在的城市。 用 )(tpkij 表示在￡时刻蚂蚁 k 由城市 i 转移到城市 j 的概率，则 )(tpkij =o th e r w is ea llo w e djtttt ka llo w e dr ijijijijk ,0,)()( )()(  （ 1） 其中 kallowed 表示蚂蚁 k 下一步允许走过的城市的集合，它随蚂蚁 k 的行进过程而动态改变；信息量 )(tij 随时间的推移会逐步衰减，用 1 表示 , 分别 表示蚂蚁在运动过程中所积累的信息量及 启发式因子在蚂蚁选择路径中所起的不同作用 , )(tij 为由城市 i 转移到城市 j 的期望程度 可根据某种启发算法而定。 经过 n 个时刻。 蚂蚁 k 走完所有的城市，完成一次循环。 此时，要根据下式对各路径上的信息量作更新： ijijij tnt   )(.)( （ 2） 6 其中： ij =mkkij1  （ 3） kij 表示蚂蚁 k 在本次循环中在城市 i 和城市 j 之间留下的信息量，其计算方法根据计算模型而定，在最常用的 ant cycle system 模型中 ； kij =o t h e r w i s ejkLQ k,0i, 和城市在本次循环中经过城市若蚂蚁 (4) 其中 Q 为常数 , kL 为蚂 k 在本次循环中所走路径的长度。 粒子群算法 粒子群算法，也称 粒子群优化算法 （ Particle Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的进化算法（ Evolu2tionary Algorithm EA）。 PSO 算法属于进化算法的一种，和 遗传算法 相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的 “交叉 ”(Crossover) 和 “变异 ”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。 这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 设想这样一个场景：一群鸟在随机搜索食物。 在这个区域里只有一块食物。 所有的鸟都不知道食物在那里。 但是他们知 道当前的位置离食物还有多远。 那么找到食物的最优策略是什么呢。 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO 从这种 模型 中得到启示并用于解决优化问题。 PSO 中，每个优化问题的解都是搜索空间中的一只鸟。 我们称之为“粒子”。 所有的例子都有一个由被优化的函数决定的适应值 (fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。 然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子 (随机解 )。 然后通叠代找到最优解。 在每一次叠代中，粒子通过跟踪两个 极值 来更新自己。 第一个就是粒子本身所找到的最优解。 这个解叫做个体极值。 这个极值是全局极值 gBest。 另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这两个最优值时 ,粒子 7 根据如下的公式来更新自己的速度和新的 位置 v[]=w*v[] 1c *rand()*(pbest[]present[]) 2c *rand()*(gbest[]present[]) (a) present[]=persent[] v[] (b) v[]是粒子的速度 ,w是惯性权重 ,persent[]是当前粒子的位置 .pbest[] 和 gbest[]如前定义 rand()是介于（ 0， 1）之间的随机数 . 1c , 2c 是学习因子。 通常 1c = 2c =2，大多数情况 0≤ 1c = 2c ≤ 4 在每一维粒子的速度都会被限制在一个最大速度 maxV ，如果某一维更新后的速度超过用户设定的 maxV ，那么这一维的速度就被限定为maxV . 几种智能算法特点 遗传算法发展历史长，理论基础完备，已经在组合优化领域取得巨大成功。 遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。 具有自组织、自适应和自学习性。 但是，由于遗传算法是基 于个体竞争这样一种机制，使得算法后期多样性匾乏，降低算法效率。 蚁群算法鲁棒性强，具有优越的正反馈机制， 每个个体只能感知局部的信息，一不直接使用全局信息。 个体可改变环境、并通过环境来进行间接通讯。 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局最优解。 其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性及目标函数和约束函数的精确数学描述。 是一类基于多主体的智能算法，各主体之间通过相互协作来更好地适应环境。 具有潜在的并行性，其搜索过程不是从一点出发，而是从多个点同时过行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高整个算法的运行效率和快速反应的能力。 蚁群算法 在构造解的过程中，随机选择策略增加了生成解的随机性，接收了解在一定程度上的退化，使得搜索范围在一段时间内保持足够大这样影响了算法的收敛速度。 粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解，它具有概念简单容易实现，搜索速度快，搜索范围大的突出优点，粒子群算法参数少，原理简单，易于编程实现最初是用来解决连续优化问题，一般采用实 8 数编码。 由于粒子群算法粒子间快速的信息交换，使得粒子群算法早期收敛速度较快，但是这种信息交换方式是建立在粒子都向最优方向移动机制的基础上，使得粒子趋向同一化，所以到 寻优后期算法容易陷入局部最优。 小结 本章主要介绍了遗传算法，蚁群算法几种智能算法的基本理论和求解组合优化问题的的基本步骤和方法，总结了这几种智能算法的优缺点，为本课题在研究人工鱼群算法求解组合优化问题提供参考。 3 基本人工鱼群算法 人工鱼群算法 (Artificial Fishschool Algofithm)是一种基于模拟鱼群行为的优化算法，在基本 AFSA 中，主要是利用了鱼群的觅食、聚群和追尾行为，从构造一条鱼的底层行为做起，通过鱼群中各个体的局部寻优，达到全局最优值在群体中突现出来的目的。 该算法 具有良好的克服局部极值、取得全局极值的能力。 并且算法中只使用目标函数的函数值，无需目标函数的梯度值等特殊信息，对搜索空间具有一定的自适应能力 .算法对初值无要求，对各参数的选择也不很敏感。 动物在进化过程中，经过漫长的自然界的优胜劣汰，形成了形形色色的觅食和生存方式，这些方式为人类解决问题的思路带来了不少启发和鼓舞。 动物一般不具备人类所具有的复杂逻辑推理能力和综合判断能力的高级智能，它们的目的是在个体的简单行为或通过群体的简单行为而达到或突现出来的。 人工鱼群算法模型 人工鱼群算法是一种基于行为的人工智 能思想 ,通过鱼在水里的行为方式模拟构建了一种鱼群模式 ,用来解决寻优问题 ,从而产生了一种新型的智能算法。 在一片水域中，鱼生存的数目最。