第十讲 粒群优化与蚁群算法知识讲稿教程文件.ppt

* * * ，它射程远，飞行高度低，攻击突然性大。“战斧”巡航导弹射程最远达2500公里，最近为450公里，均在敌火力网外发射，因此发射平台很难被对方发现。导弹在海面飞行高度7～15米，平坦陆地为50米以下，山区和丘陵地带为100米以下，基本是随地形的起伏而不断改变飞行高度，而这一高度又都在对方雷达盲区之内，所以也很难为对方的发现，极易造成攻击的突然性。另外，导弹采取有效隐身措施后，其雷达反射面积仅为0.02～0.1平方米，相当于一只小海鸥的反射能力。新一代巡航导弹在雷达荧光屏上只有针尖大小的一个目标光点，可见很难探测。 世界上第一枚巡航式导弹是德国的V─1飞弹。第二次世界大战期间，德国曾向英国发射了10500枚V─1飞弹，但落在]英国本土的只有约3200枚。 1991年的海湾战争中，美国向伊拉克的重要目标发射了数百枚“战斧”式巡航导弹，大都准确击中了目标。 巡航导弹 第三，它的命中精度高，摧毁能力强。射程2500～3000公里的巡航导弹，命中误差不大于60米，精度好的可达10～30米，基本具有打点状硬目标的能力 1马赫=每小时1126公里 飞行速度6-8马赫 * * 蚁群算法（Ant Colony Optimization, ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone） 作为蚁群前往食物所在地的标记。 信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。 ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。 目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。 * * * * 粒子群优化算法的应用 车辆路径问题的应用 邮政投递 火车及汽车的调度 港口装卸集装箱 蚁群算法 1992年由意大利的学者多里戈提出 模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为 一种新型的优化算法 蚁群的自组织行为 1989年，戈斯等研究蚂蚁觅食的“双桥实验” 通过遗留在来往路径 上的信息素 （Pheromone）的挥 发性化学物质来进行 通信和协调。 蚁群算法的起源 蚁穴 食物 神奇的信息素 蚂蚁觅食的过程 随机移动 遇到食物返回的路上分泌信息素 信息素：易挥发性的化学物质 在回家的路上留下信息素 其它蚂蚁发现留有信息素的路径结束漫游，沿着该路径移动，遇到食物同样返回途中分泌信息素。 信息素会随着时间慢慢挥发，关键路径上的信息素相对浓度高 初始 运行一段时间 蚂蚁系统 多里戈在其博士论文中提出了一种蚂蚁系统（ANT SYSTEM AS）,以解决旅行商问题（TSP） 一个售货员希望去访问若干个城市，开始和结束于同一城市，每两个城市之间都有一条直接通路，怎样行走才能使走过的路径最短？ 蚁群算法 蚂蚁在两个城市之间移动 两个城市之间的信息素越多，蚂蚁就越有可能选择它们之间的路径 能够成功完成遍历的蚂蚁会在路径上留下信息素，路径越短留下的信息素会越多。 蚁群算法原理 基于蚂蚁觅食时的最优路径选择问题，可以构造人工蚁群，来解决最优问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁 人工蚂蚁与自然蚁群 相似之处：优先选择信息素浓度大的路径 区别：人工蚂蚁有一定的记忆能力，能够记忆已经访问过的节点 人工蚁群在选择下一条路径的时候是按一定的算法有意识的寻找最短路径，而不是盲目的。 蚁群算法中的各种行为因子 范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，那么它能观察到的范围以及能够移动的范围都会发生在这样的一个范围之内 环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有其他的蚂蚁，还有信息素，信息素可以设计为单一种类也可以多种类（如两种），一种是找到食物的蚂蚁撒下的食物信息素，另外一种是找到食物的蚂蚁洒下的蚁窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。同时环境也以一定的速率让信息素消失。 蚁群算法中的各种行为因子 觅食规则：在每只蚂蚁能感知的范围