logo资料库

回溯法及蚁群算法解最大团问题.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：doc 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    回溯法及蚁群算法解最大团问题
    摘要
    正文
    一、问题介绍
    二、回溯法
    1.回溯法介绍
    2.回溯法解最大团问题
    3.流程实现
    4.算法优化
    5.伪代码
    6.运行结果
    三、启发式算法
    1.蚁群算法概述
    2.算法组成
    3.算法流程
    四、结果分析
    五、感想与总结
    参考文献
    回溯法及蚁群算法解最大团问题 摘要 先后用回溯法和蚁群算法两种算法对于最大团问题进行了求解，前者采用确定性算法， 后者属于启发式算法.在回溯法的部分，我们以课内的知识为基础，自行设计了优化的剪枝 策略以提高算法的效率.后又通过阅读相关文献学习和实现了蚁群算法，对这一问题进行了 求解，取得了效果上的进步. 关键词：回溯法，蚁群算法，最大团问题 正文 本文将全面地介绍两个算法的基本内容、核心思想、操作过程及其执行结果，并对结果 给出分析.其中，第一部分简单介绍了回溯法的有关内容，并且对之前的执行情况以及改进 优化后的执行情况进行了对比. 第二部分介绍了蚁群算法的算法背景、基本思想以及流程实 现，并且用表格形式给出了针对不同测试文件最终的执行情况. 一、问题介绍 给定无向图 G=(V,E)，其中 V 是非空集合，称为顶点集；E 是 V 中元素构成的无序二元 组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示.如 果 U⊂V，且对任意两个顶点 u，v∈U 有(u,v)∈E，则称 U 是 G 的完全子图.G 的完全子图 U 是 G 的团当且仅当 U 不包含在 G 的更大的完全子图中.G 的最大团是指 G 中所含顶点数最 多的团. 如果 U⊂V 且对任意 u，v∈U 有(u,v)不属于 E，则称 U 是 G 的空子图.G 的空子图 U 是 G 的独立集当且仅当 U 不包含在 G 的更大的空子图中.G 的最大独立集是 G 中所含顶点数最 多的独立集. 对于任一无向图 G=(V,E)，其补图 G'=(V',E')定义为：V'=V，且(u,v)∈E'当且仅当(u,v) ∉ E. 如果 U 是 G 的完全子图，则它也是 G'的空子图，反之亦然.因此，G 的团与 G'的独立集 之间存在一一对应的关系.特殊地，U 是 G 的最大团当且仅当 U 是 G'的最大独立集. 通俗点讲就是在一个无向图中找出一个点数最多的完全图.
    二、回溯法 1.回溯法介绍 回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达 到目标.但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择， 这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点". 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索 解空间树.当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结 点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯.(其实回溯法 就是对隐式图的深度优先搜索算法). 若用回溯法求问题的所有解时，要回溯到根，且根结 点的所有可行的子树都要已被搜索遍才结束. 而若使用回溯法求任一个解时，只要搜索到问 题的一个解就可以结束. 2.回溯法解最大团问题 回溯法（Backtracking Algorithm, BA）有“通用的解题法”之称，用它可以系统地搜索 一个问题的所有解或任一解，是一个既带有系统性又带有跳跃性的搜索算法.在包含问题的 所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树.算法搜索至解空 间树的任一结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过 对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按照 深度优先的策略进行搜索.BA 在用来求问题的所有解时，要回溯到根，且根结点的所有子树 都已被搜索遍才结束.而 BA 在用来求问题的任一解时，只要搜索到问题的一个解即可结束. 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大 的问题. 回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点.在 当前扩展节点处，搜索向纵深方向移至一个新节点.这个新节点就成为一个新的活结点，并 成为当前扩展节点.如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死 结点.此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点. 回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点 为止. 搜索：回溯法从根结点出发，按深度优先策略遍历解空间树，搜索满足约束条件的解. 剪枝：在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者 是否超出目标函数的界；也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以 该结点为根的子树的搜索，即剪枝（Pruning）；否则，进入以该结点为根的子树，继续按 照深度优先的策略搜索. 3.流程实现 一般来讲，回溯法求解问题的基本步骤如下： (1)针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式 搜索解空间，并在搜索过程中利用 Pruning 函数剪去无效的搜索.
    (2)无向图 G 的最大团问题可以看作是图 G 的顶点集 V 的子集选取问题.因此可以用子 集树表示问题的解空间.设当前扩展节点 Z 位于解空间树的第 i 层.在进入左子树前，必须确 认从顶点 i 到已入选的顶点集中每一个顶点都有边相连.在进入右子树之前，必须确认还有足 够多的可选择顶点使得算法有可能在右子树中找到更大的团. (3)用邻接矩阵表示图 G，n 为 G 的顶点数，cn 存储当前团的顶点数，bestn 存储最大团 的顶点数.cn+n-i 为进入右子树的上界函数，当 cn+n-i
    运行时间 已经找到的最大团规模 2s 230s 864s 2532s 22 23 24 25 表格 1 优化前 运行时间 已经找到的最大团规模 3s 26
    1534s 8400s 27 28 表格 2 优化后 通过上面列出的对于同一个测试文件的运行结果可以体现出，进过改进，算法的效率有 了极大的提升，并且找到的最大团规模也有了增长，改进的效果立竿见影，我们用更大规模 的文件进行了更进一步的测试，以下是测试的结果. 文件名 运行时间 已经找到的 最大团规模 frb30-15-1.clq 2h frb59-26-1.clq 7s frb100-40.clq 10s 28 49 81 表格 3 回溯法测试结果
    三、启发式算法 启发式算法（heuristic algorithm)是相对于最优化算法提出的.一个问题的最优算法求得 该问题每个实例的最优解.启发式算法可以这样定义：一个基于直观或经验构造的算法，在 可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解， 该可行解与最优解的偏离程度一般不能被预计. 启发式解决问题的方法是与算法相对立的.算法是把各种可能性都一一进行尝试，最终 能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案.启 发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决.但由 于这种方法具有尝试错误的特点，所以也有失败的可能性.科学家的许多重大发现，常常是 利用极为简单的启发式规则. 认知心理学的信息加工理论认为，启发式是人类思维解决问题的重要方法.在人工智能 中常用启发式设计计算机程序，模拟人类解决问题的思维活动.已经证明，这是一条有效的 途径. 人们对诸多启发算法有不同的分类方法，每种方法都有其特定的角度.这些分类方法的 差异在于所选择的用来区别这些算法的性质的不同.通常根据启发式方法区分的自启发算法 （遗传算法，蚁群算法）和非自启发的（如迭代局部搜索和禁忌搜索）.按每次迭代产生的 解的数量分，有基于种群的（例如遗传算法、蚁群算法、粒子群算法）和单点搜索的（例如 迭代局部搜索、禁忌搜索、可变近邻搜索）.依据算法本身的理论机制区分，有对局部搜索 算法的智能扩展方法（如模拟退火搜索、迭代局部搜索、禁忌搜索）和依据对解的各个组成 部分的关系的学习而识别高质量区域的方法（例如遗传算法、蚁群算法）. 我们选用的启发式方法是蚁群算法. 1.蚁群算法概述 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路 径的机率型算法.它由 Marco Dorigo 于 1992 年在他的博士论文中提出，其灵感来源于蚂蚁在 寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法，初步的研究表明该算法具 有许多优良的性质.针对 PID 控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法 设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有 效性和应用价值. 其基本原理在于：各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物. 当一只找到食物以后，它会向环境释放一种挥发性分泌物 pheromone (称为信息素,该物质随 着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的 蚂蚁过来，这样越来越多的蚂蚁会找到食物.有些蚂蚁并没有像其它蚂蚁一样总重复同样的 路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂 蚁被吸引到这条较短的路上来.最后，经过一段时间运行，可能会出现一条最短的路径被大 多数蚂蚁重复着. 2.算法组成 (1)信息素模型 信息素模型可以算作是蚁群算法中最为关键的部分，信息素模型的选择一般都和构成解
    的各个部分相关.一种最直接的思路是将信息素模型的数据结构与组成解的各个部分相对应. 最大团问题中，可以选择与各个顶点做对应得到信息素模型的数据结构.信息素模型还包含 信息素挥发率、上下界限等参数.恰当的选择挥发率和信息素强度的上下界限对于算法的平 衡有着很大的作用，对算法效果的优劣很重要. 总的来说，信息素模型用来储存在解的各个部分上沉淀的信息素的数量.在算法运行过 程中，各个人工蚂蚁通过对信息素数据结构的访问得到蚂蚁行为的历史信息，以提示自己的 解的构造过程.各人工蚂蚁们还会在适当的时机“释放”信息素，对信息素数据结构里面的 数据进行更新.信息素模型是每个功能简单的蚂蚁得以通讯和协同工作的基础. (2)解的构造 蚁群算法和遗传算法类似，都是通过迭代过程产生一代又一代的解，在一次迭代中，人 工蚁群中所有的蚂蚁都要构造一个解. 解的构造过程与方法会依据问题而有所不同，但基本都遵循这样一个原则：依据所对应 的信息素元素中的信息素强度随机选择构成解的各个组成部分.在这个与具体问题相关的构 造过程中将会根据与问题相关的启发式来参与解的构造.选取什么样的利用信息素的方法， 采用什么样的与问题相关的启发式都是解构造过程中需要注意选择的.对不同选择的不同组 合会对同一个问题的处理结果产生不同的影响，选择与蚁群优化算法其它算子相适应的组合 有利于算法平衡，从而获得更好的求解效果. (3)解的改进 解的启发式通常分为两类：解的构造启发式和改进启发式.通过构造启发式可以获得解 空间中的一个元素：还可以依据需要在解空间中该解的近邻区域内寻找一个拥有更好的目标 函数评价的解，这个局域搜索以改进所得解的手段称为解的改进启发式.解的改进启发式基 本都是与具体问题直接相关的，没有一种对蚁群算法通用的抽象形式.作为解的改进启发式 的局部搜索可以根据不同的优化问题选择是否使用和使用何种形式的启发式以使算法有更 好的求解效果. (4)信息素的更新 本算法中采用的是全局更新策略，在每代蚂蚁工作结束后进行信息素的更新，更新策略 是对当代蚂蚁找到的最大团中的点进行信息素的增加，而让最大团以外的点的信息素进行挥 发. 更新式如下图所示： (5)选点 在算法中另一个很重要的问题是选取点的策略，在基本蚁群算法中一般选择概率大者作 为下一个顶点.这样虽然强化了启发函数和信息素的引导，但是很容易出现停滞现象，过早 的收敛与局部最优解.解决办法是增加搜索的随机性，兼顾解空间的各种情况. 基于上述分析，我们采取的策略是，采用最大原则或者轮盘赌两种方式进行选点，给定 参数 q，每次选点时生成一个随机数，对这个随机数与 q 进行比较，如果比 q 小，就按照最
    大原则，选取概率最大的点，点的概率计算公式如下所示： 式中计算的是蚂蚁 K 下一步转移到顶点 j 的概率. 而如果随机数比 q 大，就会采取轮盘赌的方法，轮盘赌的伪代码如下所示： 3.算法流程 整个算法的流程实现如下所示： (1)初始化算法，读入图的基本信息，建立信息素数组 (2)针对每一代蚂蚁，创建出一定数量的蚂蚁，为每只蚂蚁随机选取一个出发点，将当 前所在位置的所有邻接节点加入队列 (3)之后循环选取下一个临街节点加入队列，并且将队列中那些与已知团不能成团的节 点去除 (4)在所有蚂蚁完成这一过程后，对每一只蚂蚁所找到的极大团进行比较，找到当代蚂 蚁找到的最大团 (5)进行全局的信息素的更新，增强这一代找到的最大团的顶点的信息素浓度，如果为 历史最大，则更新历史最大 (6)重复迭代 n 次（n 为蚂蚁的代数） 经过测试，该算法取得了不错的效果，以下将测试的数据以及运行时间同样通过表格的 形式给出：
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料