蚁群算法与粒子群算法优缺点个人精华篇

精品文档 1欢迎下载 蚁群算法与粒子群算法优缺点蚁群算法与粒子群算法优缺点 蚁群算法 ACO 是受自然界中蚂蚁搜索食物行为的启发 是一种群智能优化算法 它基 于对自然界真实蚁群的集体觅食行为的研究 模拟真实的蚁群协作过程 算法由若干个蚂 蚁共同构造解路径 通过在解路径上遗留并交换信息素提高解的质量 进而达到优化的目 的 蚁群算法作为通用随机优化方法 已经成功的应用于 TSP 等一系列组合优化问题中 并取得了较好的结果 但由于该算法是典型的概率算法 算法中的参数设定通常由实验方 法确定 导致方法的优化性能与人的经验密切相关 很难使算法性能最优化 蚁群算法中每只蚂蚁要选择下一步所要走的地方 在选路过程中 蚂蚁依据概率函数 选择将要去的地方 这个概率取决于地点间距离和信息素的强度 t 上述方程 表示信息素的保留率 1 表示信息素的挥发率 为了防止信息的无限积累 取值范围限定在 0 1 ij 表示蚂蚁 k 在时间段 t 到 t n 的过程中 在 i 到 j 的路 径上留下的残留信息浓度 在上述概率方程中 参数 和 是通过实验确定的 它们对算法性能同样有很大的 影响 值的大小表明留在每个节点上信息量受重视的程度 其值越大 蚂蚁选择被选过 的地点的可能性越大 值的大小表明启发式信息受重视的程度 这两个参数对蚁群算法性能的影响和作用是相互配合 密切相关的 但是这两个参数只能 依靠经验或重复调试来选择 在采用蚁群 粒子群混合算法时 我们可以利用 PSO 对蚁群系统参数 和 的进行 训练 具体训练过程 假设有 n 个粒子组成一个群落 其中第 i 个粒子表示为一个二维的 向量 xi xi1 xi2 i 1 2 n 即第 i 个粒子在搜索空间的中的位置是 xi 换言之 每个粒子的位置就是一个潜在的解 将 xi 带入反馈到蚁群系统并按目标函数 就可以计算出其适应值 根据适应值的大小衡量解的优劣 蚁群算法的优点 蚁群算法与其他启发式算法相比 在求解性能上 具有很强的鲁棒性 对基本蚁群算 法模型稍加修改 便可以应用于其他问题 和搜索较好解的能力 蚁群算法是一种基于种群的进化算法 具有本质并行性 易于并行实现 蚁群算法很容易与多种启发式算法结合 以改善算法性能 蚁群算法存在的问题 TSP 问题是一类经典的组合优化问题 即在给定城市个数和各城市之间距离的条件下 找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线 蚁群算法在 TSP 问 题应用中取得了良好的效果 但是也存在一些不足 1 如果参数 和 设置不当 导致求解速度很慢且所得解的质量特别差 2 基本蚁群算法计算量大 求解所需时间较长 3 基本蚁群算法中理论上要求所有的蚂蚁选择同一路线 该线路即为所求的最优线路 但在实际计算中 在给定一定循环数的条件下很难达到这种情况 另一方面 在其它的实际应用中 如图像处理中寻求最优模板问题 我们并不要求所 有的蚂蚁都找到最优模板 而只需要一只找到最优模板即可 如果要求所有的蚂蚁都找到 最优模板 反而影响了计算效率 蚁群算法收敛速度慢 易陷入局部最优 蚁群算法中初始信息素匮乏 蚁群算法一般 需要较长的搜索时间 其复杂度可以反映这一点 而且该方法容易出现停滞现象 即搜索 进行到一定程度后 所有个体发现的解完全一致 不能对解空间进一步进行搜索 不利于 发现更好的解 精品文档 2欢迎下载 粒子群优化具有相当快的逼近最优解的速度 可以有效的对系统的参数进行优化 粒 子群算法的本质是利用当前位置 全局极值和个体极值 3 个信息 指导粒子下一步迭代位 置 其个体充分利用自身经验和群体经验调整自身的状态是粒子群算法具有优异特性的关 键 PSO 算法的优势在于求解一些连续函数的优化问题 PSO 算法存在的问题 问题最主要的是它容易产生早熟收敛 尤其是在处理复杂的多峰搜索问题中 局部寻优能 力较差等 PSO 算法陷入局部最小 主要归咎于种群在搜索空间中多样性的丢失 不同算法的混合模型主要分为两类 1 全局优化算法与局部优化算法混合 2 全局优化算法与全局优化算法混合 纵观各种与 PSO 算法相关的混合算法 大多数基本上 采用一种策略对其改进 要么与其他算法 要么加入变异操作 同时采用两种策略的混合 算法较少 上述策略中 两者之间有一定的矛盾性 全局算法与局部算法相混合 尽管可以提高 局部收敛速度 但也加剧了陷入局部极小的可能 全局算法与全局算法的混合 算法的局 部细化能力仍然没有改善 但如果只加入变异操作 则算法的探测能力得到提高 但也损 害了其局部开发能力 因此如果将局部搜索和变异操作同时混合到 PSO 算法中 通过适当的调节 发挥各自 的优点 提高算法的开发能力 增加变异操作防止算法早熟 来共同提高 PSO 算法的全局 寻优能力 融合策略 1 针对蚁群算法初始信息素匮乏的缺点 采用其他算法生成初始信息素分布 利用 蚁群算法求精确解 从而提高时间效率和求解精度 使用的其他算法的求解结果以什么规 则转换成蚁群算法的信息素初值 需要通过多次实验 2 将其他算法 如遗传算法 引入到蚁群算法系统的每次迭代过程中 以蚁群系统 每一代形成的解作为其他算法的初始种群 然后经过其他算法的多次迭代 试图寻找更好 的解 从而加快蚁群系统的收敛速度 提高求解速率 3 蚁群算法中 的选取往往是通过经验来取得的 而选取不当时会造成算法 的性能大大降低 因此可以利用其他算法对蚁群系统参数 进行训练 4 对于蚁群算法出现过早收敛于非全局最优解以及时间过长的缺点 可以通过使用 蚁群算法进行搜索 然后用其他算法对蚁群算法得到的有效路由路径 通过选择 交叉 变异等优化过程 产生性能更优的下一代