人工基础智能 12

课堂设计一、基本信息课次第11讲课次学时数2学时主题群智能二、设计方案课堂目标（一）知识目标能简述群智能的概念；能描述蚁群算法的主要思想和原理。（二）能力目标能判定蚁群算法的适用范畴；能对比分析不同群智能方法的优缺点；能应用群智能思想分析相关鸟群、鱼群等生物群体的智能行为；能针对简单实际问题提出解决问题的改进思路或方案。（三）素质目标能通过群智能的仿生思想，提升利用自然现象设计启发式算法的创新思维、仿生思维。教学重难点（一）教学重点蚁群算法的实现过程。（二）教学难点群智能的启发式设计方法。教学设计思路（一）教学内容组织1.群智能概念2.蚁群算法原理3.粒子群算法（二）教学方法策略1.教学思路与方法结合学生观察过的群体行为，让学生从身边的群体动物观察出发，结合案例，掌握蚁群算法的过程与基本使用方法。2.课程思政设计（1）崇尚科学意识（2）爱国主义精神：介绍群体智能发展的同时为人民生活带来的贡献，突出国家和人民坚持发展的精神，强化学生对国家的热爱。3.军事特色思考群智能算法军事上有何价值和用途，如何服务于人民部队。教学资源1.头歌（EduCoder）平台在线资源2.《人工智能技术及其应用》在线课程审签新上课教员£上新课教员£内容备注课堂导入智能并不是人类所独有的技能，除了模仿人类的大脑与行为，我们还可以向自然界中的其他物种进行学习，本节课将介绍从群体智能领域设计启发式算法的智能算法。理论讲授一、群智能的概念假定你和朋友正在执行寻宝任务，这个团队每个人都有一个金属探测器，并能把自己的当前位置通过手机传给其他队友。因此每个人都知道团队中伙伴是否比自己更接近宝藏。利用这种方法，我们可以朝着邻近伙伴移动，使得自己找到宝藏的机会得到改善，找到宝藏比单人快得多。这种例子还有很多，群体的力量大于个人，群体表现出来的这种能力，就是群智能。1989年，加利福尼亚大学的教授贝尼在其细胞自动机系统中首次提出群智能的概念。任何一种由昆虫群体或其他动物社会行为机制而激发设计出的算法，或分布式解决问题的策略均属于群智能。群智能已经成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。已有的群智能理论和应用研究都已经证明了群智能方法是一种能够有效解决大多数优化问题的新方法。二、蚁群算法蚂蚁又称“玄驹”、“蚍蜉”或“状元子”，是一种既渺小而又平常的昆虫。在分类上蚂蚁属于节肢动物门、昆虫纲、膜翅目、蚁科，它在昆虫界种类最多、生存量最大。蚂蚁的起源可迫溯到一亿年前的恐龙时代，那时地球上就有蚂蚁的祖先繁衍。随着地球生态环境的变迁，身躯庞大的恐龙早巳灭绝丁，而身躯细小的蚂蚁在弱肉强食、物竞天择的自然界依靠集体的力量和顽强的生命力一直生存繁衍到今天，而且形成了家庭兴旺的蚂蚁王国。目前，全世界的蚂蚁约有260属，16000多种，其中已命名的蚂蚁有9000多种。据生态学家估计，地球上蚂蚁总重量约占陆生动物总量的10％；科学家曾做过计算，蚂蚁能把比自己重1400倍的食物拖回家去，能举起超过自身体重400倍的物体，无愧于动物世界巾的“大力士”这一美誉。蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，蚂蚁在运动过程中能够感知以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。1.蚂蚁搜寻食物的具体过程：当碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。好走到C点，为一半路程。2.蚁群算法模型的建立（1）对蚂蚁个体的抽象蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来，同时摒弃与建立算法模型无关的因素。（2）问题空间的描述蚁群算法所求解的问题空间可用一个重要的数学工具——图（graph）来描述。（3）寻找路径的抽象把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点上人工蚂蚁感知相邻节点边上的信息素浓度。（4）信息素挥发的抽象自然界中，蚂蚁留下的信息素会随着时间的推移而连续不断的挥发。因此使算法中的信息素挥发方式与蚂蚁觅食过程机理相符，要使蚂蚁完成一个节点的移动后，经过一个单位时间，进行一次信息素的挥发。（5）启发因子的引入蚁群算法的自组织性，似的系统的演化需要耗费较长的时间，而实际应用时对算法运行时间的要求也是必不可少的。因此引入一个启发因子，给蚁群算法一个初始的引导，增加算法的时间有效性。3.蚁群算法解决旅行商（TSP）问题设bi（t）表示t时刻位于元素i的蚂蚁数目，τi（t）为t时刻路径（i，j）上的信息量，n表示TSP规模，m为蚁群中蚂蚁的总数目，则m=∑bi（t）。初始时刻各条路径上信息量相等，并设τi（0）=const。蚂蚁k在运动过程中，根据个体路径上的信息量决定其转移方向。这里用一个禁忌表tabuk（k=1,2,…,m）来记录蚂蚁k当前走过的城市。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。为了避免残留信息素过多影响启发信息，在蚂蚁走完一步或者完成对城市的遍历后，就需要对残留信息进行更新处理。按如下规则进行调整4.蚁群算法的改进及应用最初提出的AS有三个版本，在不大于75城市的TSP中，三种基本算法求解能力比较理想。但是当问题规模扩展时，AS的解题能力大幅度下降。改进方法如：（1）精英策略，对于最好的路径给予额外的增强。（2）负反馈机制，蚂蚁如果改变路线，就减少原路的信息素，减小已选则路径再次被选择概率，鼓励蚂蚁走新路。提问：你知道鸟类是如何寻找食物的吗？蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化；分类聚类；一些经典的组合优化问题。提问：你知道鸟类是如何寻找食物的吗？三、粒子群算法粒子群算法是由艾伯哈特博士和肯尼迪博士于1995年提出，模拟鸟群或蜂群的觅食行为。基本思想是通过群体中个体之间的协作和信息共享来找最优解。一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在哪里。但是它们知道自己当前位置距离食物还有多远。粒子群算法建模：把每只鸟抽象成一个粒子。每个粒子的适应度就是鸟到食物（目标函数）的距离。讨论：例子速度和位置更新公式中元素对于算法性能的影响。每个粒子有一个初始的飞行方向，初始时是随机的。讨论：例子速度和位置更新公式中元素对于算法性能的影响。每一次单位时间飞行后，所有粒子共享信息，下一步飞行方向由自身最佳位置和全局最佳位置加权得到。粒子群算法的步骤：初始化粒子群，随即产生初始位置。通过每个粒子当前位置评价其性能。比较个体性能与全体最佳性能。改变每个粒子的速度把每个粒子位置更新转向步骤2，重复递归至收敛。通过生活中的群体智能行为，启发学员思考，理解群智能的概念。通过生活中的群体智能行为，启发学员思考，理解群智能的概念。介绍蚂蚁的一些基本习性，吸引学员学习兴趣。引出蚁群算法。介绍蚂蚁的一些基本习性，吸引学员学习兴趣。引出蚁群算法。提问：蚂蚁是如何找食物的？介绍蚂蚁搜寻食物的过程，帮助学员理解蚁群算法的基本原理。提问：蚂蚁是如何找食物的？介绍蚂蚁搜寻食物的过程，帮助学员理解蚁群算法的基本原理。启发思考：蚁群算法模型建立需要引入哪些要素？启发思考：蚁群算法模型建立需要引入哪些要素？结合蚂蚁觅食的过程，启发学员思考蚁群算法中的要素设计方法。结合蚂蚁觅食的过程，启发学员思考蚁群算法中的要素设计方法。通过例子说明按照信息素浓度概率选择路径的搜索策略，本质是启发式函数。提