logo资料库

数学建模蚁群算法ppt.pptx

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.59M 资料格式：pptx 举报 版权申诉
第1页 / 共54页
第2页 / 共54页
第3页 / 共54页
第4页 / 共54页
第5页 / 共54页
第6页 / 共54页
第7页 / 共54页
第8页 / 共54页
资料共54页，剩余部分请下载后查看
    蚁 群 优 化 算 法 （ACO算法） 一、概述 二、蚂蚁系统（AS） 三、算例 四、改进的ACO算法
    一、概述 （一）算法背景——蚁群的自组织行为特征 1、高度结构化的组织——虽然蚂蚁的个体行为极其 简单，但由个体组成的蚁群却构成高度结构化的社会 组织，蚂蚁社会的成员有分工，有相互的通信和信息 传递。 2、自然优化——蚁群在觅食过程中，在没有任何提示 下总能找到从蚁巢到食物源之间的最短路径；当经过的 路线上出现障碍物时，还能迅速找到新的最优路径。 3、信息正反馈——蚂蚁在寻找食物时，在其经过的路 径上释放信息素（外激素）。蚂蚁基本没有视觉，但能 在小范围内察觉同类散发的信息素的轨迹，由此来决定 何去何从，并倾向于朝着信息素强度高的方向移动。 4、自催化行为——某条路径上走过的蚂蚁越多，留下 的信息素也越多（随时间蒸发一部分），后来蚂蚁选择 该路径的概率也越高。
    （二）算法的产生与发展 1、产生——受蚁群觅食行为启发，意大利学者M.Dorigo 于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群 的新型智能优化算法“蚂蚁系统（Ant system,简称AS）”， 并用该法求解旅行商问题，获得了较好的效果。 2、发展——后来，提出者及许多研究者对该算法作了各种 改进，将其应用于更为广泛的领域，如图着色问题、二次分 配问题、工件排序问题、车辆路径问题、车间作业调度问题、 网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo 等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化 （Ant Colony Optimization,简称ACO）”，并将所有符合ACO 框架的算法称为“蚁群优化算法（ACO algorithm）”。 3、展望——初步的研究结果已显示出ACO算法在求解复杂 优化问题，特别是离散优化问题方面的优越性。虽然严格的 理论基础尚未奠定，但从当前的应用效果来看，此算法具有 光明的发展前景。
    （三）特点 ◆是一种基于多主体的智能算法，不是 单个蚂蚁行动，而是多个蚂蚁同时搜索， 具有分布式的协同优化机制。 ◆本质上属于随机搜索算法（概率算法）， 具有概率搜索的特征。 ◆是一种全局搜索算法，能够有效地避免 局部最优。
    （四）优点 ◆求解问题的快速性——由正反馈机制 决定； ◆全局优化性——由分布式计算决定， 避免蚁群在寻优空间中过早收敛； ◆有限时间内答案的合理性——由贪婪 式搜索模式决定，使能在搜索过程的早期 就找到可以接受的较好解。
    二、蚂蚁系统（AS算法）——最早的ACO算法 （一）算法基本思想（以旅行商为例说明） 1、根据具体问题设置多只蚂蚁，分头并行搜 索。 2、每只蚂蚁完成一次周游后，在行进的路上 释放信息素，信息素量与解的质量成正比。 3、蚂蚁路径的选择根据信息素强度大小（初 始信息素量设为相等），同时考虑两点之间的距 离，采用随机的局部搜索策略。这使得距离较短 的边，其上的信息素量较大，后来的蚂蚁选择该 边的概率也较大。
    4、每只蚂蚁只能走合法路线（经过每个城市 1次且仅1次），为此设置禁忌表来控制。 5、所有蚂蚁都搜索完一次就是迭代一次，每 迭代一次就对所有的边做一次信息素更新，原 来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。 6、更新信息素包括原有信息素的蒸发和经过 的路径上信息素的增加。 7、达到预定的迭代步数，或出现停滞现象 （所有蚂蚁都选择同样的路径，解不再变化）， 则算法结束，以当前最优解作为问题的最优解。
    （二）参数含义及符号 m k t n ijd ij ——蚂蚁数量； ——蚂蚁编号； ——时刻； ——城市数；  ——城市 之间的距离； i, ——启发式因子（能见度），反映蚂蚁由 城市 转移到城市 的启发程度； j i j ij ——边 上的信息素量； i, j 
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

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

    热门标签

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

    最新资料