《仿生蚊子追踪算法_冯翔》由会员分享，可在线阅读，更多相关《仿生蚊子追踪算法_冯翔（15页珍藏版）》请在金锄头文库上搜索。
1、书书书第 卷第期 年月计算机学报 收稿日期： ； 最终修改稿收到日期： 本课题得到国家自然科学基金（ ， ， ） 、 上海市教育委员会科研创新项目、 中央高校基本科研业务费、 大学生创新项目资助冯翔， 女， 年生， 博士， 教授， 博士生导师， 中国计算机学会（ ） 会员， 主要研究领域为分布并行计算、 人工智能、 网络通信 ： 张进文， 男， 年生， 硕士研究生， 主要研究方向为分布并行计算、 网络通信虞慧群， 男， 年生， 博士， 教授， 博士生导师， 主要研究领域为软件工程、 可信计算和形式化方法仿生蚊子追踪算法冯翔张进文虞慧群（ 华东理工大学计算机科学与工程系上海 ）摘要旅行商问题（
2、， ） 是 完全问题中最为著名的问题， 它易于陈述而难于求解， 至今尚未找到准确有效的求解大规模 问题的方法 文中提出了能求出 有效近似最优解的新的蚊子追踪（ ， ） 算法， 证明了蚊子的目标追踪行为和 数学模型的一致性、 蚊子追踪算法的收敛性， 并通过理论证明确定了 算法中各参数的选择范围 蚊子追踪算法是一个全新的仿生算法 文中以 问题为载体， 详细提出了蚊子追踪算法的动机、 生物学模型、 数学模型、 算法、 理论基础（ 数学证明） 及大量实验结果 从理论和实验两方面证明了蚊子追踪算法能够求出 问题理论上的优化解关键词仿生算法； 旅行商问题； 蚊子追踪算法； 分布并行算法中图法分类号 号 （
3、 ， ， ） （ ） （ ） ， （ ） ， ， ， ， ； （ ） ； （ ） ； 引言南加州大学的 教授在 上发表的论文“ ” 中指出： “ 自然（ 生物学和物理） 和计算（ 计算机科学） 是相关的， 重要的学术成果将会在两者的交叉领域中取得” 在信息科学领域， 尤其在计算机科学领域， 受自然界法则启发， 模拟智能体实施智能行为的原理而来的理论、 方法和技术越来越成为研究热点智能体包括人、 动物等具有智能行为能力的所有物体 智能体本身也可以由许多智能体组成， 如蚊子群图灵提出了图灵机（ 也就是计算设备） 的概念，为计算机的发明和计算机学科的产生和发展奠定了理论基础 纽厄尔和西蒙提出了图灵机
4、的扩展概念物理符号系统及物理符号系统假说 物理符号系统假说的内容是： 人、 动物等智能体是物理符号系统，广义的计算机及算法也是物理符号系统， 那么可以得出以下推论可以用广义计算机及算法来模拟人、动物等智能体的智能行为 以上理论也论证了本文的可行性， 即计算机及算法可以模拟蚊子追踪目标的自然演化行为既然自然法则有计算属性， 计算机及算法又有模拟的可能性， 本文的目标是探索和发展一个全新的自然演化算法 蚊子追踪算法（ ， ） 通过研究和模拟蚊子目标追踪行为， 建立运动学和动力学模型， 研究复杂环境和复杂交互模式下群体智能的演化机制， 建立个体微观行为与群体宏观智能之间的关系模型， 研究基于蚊子追踪
5、行为模型的分布并行智能处理理论与方法， 并用以求解 问题一些组合优化问题（ ， ） ， 如 旅 行 商 问 题 （ ， ） 属于一类典型的 完全问题（ ） ， 这类问题的计算时间复杂性随问题规模增大成指数性增长 问题易于陈述而难于求解自 年 提出以来， 至今尚未找到准确有效的求解大规模 问题的方法在过去的几十年里， 一些新的仿生、 仿物理方法被提出， 用来求解 问题的近似优化解这些仿生 方法包 括：（）演 化 算 法如 遗 传 算 法（ ，）、 演化策略 （ ） 、 演化规划（ ）等； （）行 为仿生 算法如蚁 群 优 化 （ ， ）、 粒子群优化（ ， ） 、 群搜索算法（ ， ） 等； （
6、） 其他的仿生算法 如人造免疫系统（ ， ） 、 人造神经网络（ ，） 、 细胞自动机（ ） 、 广义细胞自动机（ ） 、 细胞神经网络（ ） 、 反应生长模型（ ） 等 虽然仿生算法是计算方法研究的边缘领域， 但却是近些年来计算方法研究领域中的热点 它们发展较快、 相当活跃， 已被成功地应用于解决现实生活中许多复杂难解的问题， 有非常广泛的影响现有仿生算法的局限性： 现有仿生算法使用和应用比较复杂 以蚁群算法为例， 由于它的算法结构特点， 除了解决图问题（ 如 问题） 比较有效以外， 很难求解那些不能转化为图问题的问题 另外，现有仿生算法需要更多的参数 对于不同的问题， 现有仿生算法为了找到
7、参数有效的设定区间， 需要通过多次实验来调整参数基于现有仿生算法的这些局限性， 我们开始研究新的仿生算法与仿生方法相对比， 近年来只有两个重要且成功的仿物理方法被提出求解 问题： 模拟退火算法（ ， ） 和弹性网络算法（ ， ） 模拟退火算法的局限性： 该算法不能完全描述和处理所待解决问题的动力学特性， 特别是那些高维、 非线性、 随机性问题中的动力学弹性网络算法的局限性： （） 弹性网络中的目标节点在一维或多维空间中的位置是固定不变的； （） 目标节点之间没有相互作用， 不能表达节点间复杂的非线性社会交互行为； （） 弹性网络中的能够形变的橡皮圈是均匀的， 连接各个节点的橡皮 带 也 是 均
8、 匀 的， 不 能表示非对称力的作用；（） 弹性网络仅仅在吸引力的作用下伸展， 而没有考虑其他种类的力， 如反作用力、 不对称的单向力等； （） 弹性网络仅考虑对称的弹性形变， 而不考虑不对称的弹性形变； （） 弹性网络中在橡皮圈上任何两个节点间， 或目标节点和弹性网络节点间， 力的属性是关于它们之间距离的函数， 这个函数是固定的， 从而力的属性也是固定的， 不能反映随时间变化的属性； （） 弹性网络仅仅是一个单回路弹性圈， 而不是多回路弹性圈以上这些局限性严重妨碍了弹性网络方法在复杂动态优化问题中的应用 弹性网络方法不能处理系统中随机发生的、 并发的复杂的社会交互行为， 也很难刻画问题中实体
9、的自治性、 意志和愿望由于目前存在的自然演化方法有其局限性， 本文通过模拟“ 蚊子” 追踪目标， 建立受各种目标物“ 力”的作用而不断“ 运动” 的生物学模型， 以 第二稳定性定理为理论基础， 以弹性网络理论和方法为基点， 发展提出一种新的自然演化算法结合仿生仿物理算法优点的蚊子追踪理论和方法， 旨在克服现有方法的一些局限性， 使之能够： （） 具有高度内在 并 行 性， 能 处 理 大 规 模 复 杂 问 题；（）用 第二定 理 能 证明算法收敛且 解 为 全 局 最优解， 逼近理论上的最优解， 较近来一些文献上提出的自然演化算法及其他常用优化算法有更好的性能； （） 参数的选取范围是从算法
10、的收敛性、期冯翔等：仿生蚊子追踪算法有效性等理论证明中推导而来， 不需要先验知识和算法学习； （） 算法与现存的自然演化方法、 其他常用优化方法在动机、 原理、 优化机制、 基本单元及状态、 生物物理模型、 数学模型、 算法、 理论基础（ 数学证明） 等方面有着本质的不同； （） 蚊子追踪模型能够描述复杂、 高维、 非线性、 宏观演化、 微观演化、随机的行为和动力学； （） 能够实现多目标优化；（） 算法具有强的鲁棒性， 蚊子追踪算法能够独立于初始条件、 问题规模、 参数小范围变化等； （） 能处理问题中各参数的实时改变， 能处理动态复杂问题； （） 算法通用性、 灵活性强， 容易应用于更广范
11、围的不同复杂问题 问题描述 问题是求解遍历个城市的最短路径的问题 问题中的主要变量和 矩阵（） 分别见表和表表 问题中的主要变量符号含义关于 （，） （，） （，）（，） （）（）槡 ， ； ， ， （） ， ； ， （） ， 表 矩阵（）城市 ， ， ， ， ， ， ， ， ， ， ， ， 定义 问题的数学描述为 ：， ， ； ； ； 蚊子追踪算法的动机和仿生模型在自然界中， 雄性和雌性蚊子一般靠吸花蜜以及植物的汁液为营养素维持生命， 但雌蚊子还有吸食动物血的能力雌蚊子吸血主要是为了繁殖后代也就是说， 只有雌蚊子才会追踪动物目标去袭击它们 在日常生活中， 观察发现雌蚊子的追踪能力十分强， 它
12、们主要是通过探查一定距离内的二氧化碳（ ） 和辛烯醇（ ） 来寻找目标雌蚊有追踪动物目标的行为， 而雄蚊没有如图所示，一群蚊子正在随机搜索能袭击的动物目标可以总结雌蚊追踪目标的个步骤如下（ 见图） ：（） 雌蚊感觉到二氧化碳和气味物质（） 判断出是它喜欢叮的动物的气味， 就朝浓度高的方向找去（） 感觉到动物体温的热幅射后就降落（ 确认是皮肤就开始吸血）图一群蚊子搜索能袭击的动物目标图雌蚊追踪目标的个步骤在本文中， 提出了蚊子追踪算法（ ） 模拟蚊子的目标追踪探查行为， 求解 问题 蚊子追踪算法把 矩阵（） 中的每一个元素视为一个人造蚊子 ，个城市间的 问题求解就转化为了一群蚊子（） 的目标追踪
13、行为 由于 矩阵由 组成， 因此让 分别代表矩阵中的元素和计算机学报 年对应的人造蚊子如图所示， 一群人造蚊子等圆周角均匀地分布在一个可袭击的目标周围 每个人造蚊子， 只要是雌蚊子都会被目标产生的二氧化碳、 气味物质和幅射热吸引， 而向目标飞去 人造蚊子和目标之间的径向距离代表这个人造蚊子的个体效用（ ） ， 即它追踪目标的成功值（ ） 二氧化碳和气味物质浓度越高， 这群人造蚊子朝目标追踪的速度越快当所有人造蚊子停止移动， 达到一个平衡状态， 就得到 问题的优化解图中， 靠近圆周的点代表这群人造蚊子的初始状态， 靠近圆心的点代表这群蚊子经过目标追踪行为（ 向目标运动） 后的更优状态图蚊子目标追
14、踪模型更具 体 地 说， 每 个 人 造 蚊 子 有 一 个 灰 度 值（ ） ， 灰度值将随人造蚊子的移动而在和之间不断改变 当人造蚊子停止移动（ 静止） ，它的灰度值将为或 当灰度值为时（ ） ， 代表相应的人造蚊子（ ） 追踪到目标； 对应于 问题， 代表路径（ ） （ 城市和城市之间的路径）为通（ 着黑色） ， 即最短路径通过路径 相反， 代表人造蚊子 没有袭击到目标， 则 问题中路径 为断（ 着白色） ， 最短路径不通过路径 当人造蚊子在运动过程中， 它的灰度值为（，） 间的数， 对应 问题中， 路径 的着色为不同灰度的灰色不同灰度代表人造蚊子追踪目标的成功度此外， 每个人造蚊子 有
15、一个性别属性 代表人造蚊子 为雌性， 否则 代表人造蚊子 为雄性 不随时间而演化 的存在一方面符合仿生系统中蚊子的客观属性， 另一方面也为解决城市间有路径不通的 问题提供可能我们知道雄蚊子是不吸血的， 故目标对它们没有吸引力 类比之， 在 问题中， 两两城市间如果路径不通， 的最短路径不应该包含这两两城市间这条不通的路径 因此， 如果遇到有城市和城市之间路径不通的 问题， 蚊子追踪算法的数学模型中就可以设 ； 否则， 在蚊子追踪模型中， ， 代表人造蚊子 为雄性， 该蚊子的灰度值 就不会随时间而演化， 将一直为， 只有雌蚊的灰度值 才会随蚊子 的运动而改变 雄蚊的灰度值将总为， 对应于 问题就
16、是相应的路径 总为断（ 着白色） ， 从而蚊子追踪算法求出的 的最短路径将不会包含城市和城市之间路径 总结蚊子追踪模型的机理为 （）（）（）（） （） （） ：即为蚊子追踪的数学模型和相应算法， 他们将会在下一部分中提出为了解释蚊子追踪模型与 问题求解之间的关系， 我们举一个简单的 的例子图显示了用蚊子追踪算法求解 问题过程中各路径灰度的变化和最短路的求解过程 在计算过程中， 两两城市间的路径的灰度随着对应的人造蚊子的灰度值的并行计算， 而并行变化图用蚊子追踪算法求解 的过程图中（） 所示， 此 问题的解最短路为期冯翔等：仿生蚊子追踪算法在最终状态 时， ， ， ， ， ， ， ， 其余 蚊子
17、追踪算法的数学模型在这一部分， 将定义求解个城市 问题的蚊子追踪算法的数学模型 首先， 我们介绍一个变量 ， 代表城市对（，） 间的权重， （） ， ， （）， 在蚊子追踪模型中， 也代表人造蚊子 强弱 越大， 说明人造蚊子 追踪能力越强， 越容易追踪到目标， 接触到皮肤达到静止， 求得优化点； 反之， 亦然 和 将随人造蚊子对目标的追踪而并行演化让 （） 代表在时刻人造蚊子 和目标之间的径向距离， 让（） 代表在时刻所有人造蚊子的整体效用， 分别定义为 （） （ （） （） （） ） ；（） （）（）在时刻， 由 目 标 （ ） 产 生 的 吸 引 力 函 数（） ， 定义为（） （） （）
18、其中，（） 越大， 人造蚊子追踪目标越快， 问题优化越快目标产生的吸引使人造蚊子， 尤其是效用最小的人造蚊子（ 成功值最小， 距目标最远的蚊子） 向目标运动， 从而使其个体效用增大在时刻， 人造蚊子间的交互行为函数（） 定义为（） （） （）， （ ） （）人造蚊子能够在以下因素的影响下， 沿着自己的径向轨道向目标运动：（） 个体目标追踪行为（） 蚊子群整体目标追踪行为（） 目标的吸引力（） 人造蚊子群之间的交互行为这种吸引因素促使人造蚊子向目标追踪运动 我们将这种因素对人造蚊子 产生的吸引力用混合吸引函数 （） 来表示， 定义为 （） （）（）（）（）（）其中，为了动态并行地求解 问题， 模
19、型中每一个人造蚊子 可以分别按下式迭代地更新 和 ，从而达到求出优化解（ 最短路） 目的 （） （） （）（） （）（） （）（） （）（） （） （） （）（） （）（） （）（） （）（）其中（） （） （ （） （） ） 人造蚊子 的运动方程定义为 （） （）（）（） （） （）（） （） （）（） （）（） （） （） （） （） （）烅烄烆（）其中 （） 为关于 （） 的分段线性函数， 定义为 （）， （） （） ， （）， （）烅烄烆（）求解 的并行蚊子追踪算法已知个城市的坐标和 （ 城市和之间是否可达） ， 蚊子追踪算法如算法算法 蚊子追踪算法初始化人造蚊子的数量为； 并行初始化
20、人造蚊子的性别为 ； 并行初始化人造蚊子的灰度值 为均值；并行初始化人造蚊子的强弱值 为 ； 初始化相关的系数，分别为 ， ， ， ， 据式（） 并行计算每个人造蚊子的个体效用值 （）和 （） 分别据式（） 和（） ， 并行计算每一个人造蚊子的 （） 和 （） 分别据公式 （） （） （） 和 （） （） （） 并行更新每一个人造蚊子的灰度值 （） 和强度值 （） 如果所有的人造蚊子停子追踪达到静止， 即所 有 （） ， 那么此时所有人造蚊子的灰度值 （） 为计算机学报 年 问题的优化解， 成功结束计算； 否则转到第步蚊子追踪算法的生物学模型和数学模型的一致性证明在第节和第节， 我们已分别介绍
21、了蚊子追踪算法的生物学模型和数学模型， 现在我们给出两者的一致性证明命题 据式（） 和（） 分别更新人造蚊子 的强度值 和成功度值（ 灰度值） ， 将使这个人造蚊子追踪目标的速度（ 式（） 中的（） ） 发生改变证明 让 （）和 （）分 别 代 表式（） 和式 （） 中 的 第项 当 据 式 （） 更 新，式（） 的第项和第项将分别使人造蚊子 产生如下的速度增量： （） （） （） （） （） （）（） （） （） （） （） （） （）（） （） （） （）（） （） （） （）（） （） （） （）（ ）类似地， 当 据式（） 更新， 式（） 的第项和第项 将 分 别 使 人 造 蚊 子
22、产 生 如 下 的 速 度增量： （） （） （） （） （）； （） （） （） （） （）同样， 对式（） ， 能求得 （） ， 因此得 （） （） （） （）（） （）（） （） （） （） （） （）（）因此， 据式（） 和式（） 分别更新（） 和（） 将使人造蚊子 的追踪目标的速度发生改变， 其改变量为式（） 中的（）证毕命题 据式（） 和（） 分别更新人造蚊子 的强度值 和成功度值（ 灰度值） ， 式（） 和（）中的第项和第项将使人造蚊子 向目标运动，即该人造蚊子的个体效用 将增加， 其增加程度与（） 成正比证明 据式（） 和式（ ） ， 式（） 和（） 第项和第项的和为 （） （
23、） （） （） （） （） （） （） （） （）（） （） （） （） （）因此， 式（） 和（） 的第项和第项将使 （） 单调增加证毕命题 蚊子追踪数学模型中， 如果较小，则目标的吸引力函数（ 式（） ） 的增加， 将会使离目标最远的人造蚊子向目标飞近 即， 使人造蚊子中最小个体效用增加证明 假定（） ， （） ， 有 （） ） （ （） ） （） ） 对以上不等式的符号两边同时取对数， 得（） （ （） ）（） 因为 是常数， 而较小（到之间的小数） ， 我们得到（） （ （） ） （）这就证明了在时刻， 目标吸引力函数（） 代表所有人造蚊子 中最大的一个 （） ， 即所有人造蚊子中最小
24、个体效用 因此， 增加目标吸引力函数（） ， 将使最小的 （） 增加证毕命题 据式（） 和（） 分别更新 和 ， 将使人造蚊子中离目标最远的那个人造蚊子向目标运动， 即最小 增加， 其增加程度与成正比证明 由目标吸引力函数（） 产生的人造蚊子 向目标追踪的速度增量为 （） （） （） （） （） （） （） （） （）据式（） 和（） ， 得（）（） （） （）（） （） （） （） （） （） （） （） （） （） （） （） 期冯翔等：仿生蚊子追踪算法其中， （） （） （） 因此， 使用式（） 和（） 会使（） 单调增加 又根据命题，（） 的增加会导致人造蚊子中最小效用增加， 其增加程
25、度与成正比证毕命题 据式（） 和（） 更新 和 ， 将导致所有人造蚊子的效用增加， 即所有人造蚊子会向目标运动， 其增加程度与成正比证明 与命题类似， 当人造蚊子 据式（） 、（） 更新强弱值 和目标追踪成功值 ， 整群人造蚊子的效用函数（） 的增量将非负即（）增量非负意味着（） 将会单调增加， 增加程度与成正比证毕命题 据式（） 和（） 更新 和 ， 将导致所有人造蚊子的交互函数（） 单调减少， 其减少程度与成正比证明 与前面类似， 有 （）（） （） （） （） （） （）；那么， 我们得 （）（） （） （）（） （） （） （） （） （）因此，（） 单调减少， 其减少程度与成正比证毕
26、蚊子追踪算法的收敛性和参数分析 收敛性分析在这一部分， 将证明蚊子追踪算法中所有人造蚊子将会收敛于它们的稳定状态（ 平衡静止状） 即对应于 问题， 蚊子追踪算法一定能求出有效的优化解数学中， 稳定性理论（ ） 研究微分方程和动力学系统的解的稳定性 由于前面提出的蚊子追踪算法的数学模型是由微分方程组成， 且算法的生物学模型中一群人造蚊子是在目标的吸引力下向其追踪运动， 故具有动力学特征 因此， 用稳定性理论证明蚊子追踪算法的收敛性具有可行性 稳定性理论中， 稳定性的定义包括 稳定性和结构稳定性 我们下面将证明蚊子追踪算法满足 稳定性 稳定性是检查有动力学特征的模型（ 系统） 是否具有稳定性的一种
27、方法 它比检验是否具有稳定性的其他方法更为通用 方程是用来证明模型的状态点是否具有稳定性的一个或一组方程 要证明我们的蚊子追踪算法的收敛性需要找到蚊子追踪模型的一个适当的 方程 稳定性证明方法的主要优点是不需求出 方程（ 状态方程） 的根 当所求解的问题用各种方法都不能求得准确解时， 这个优点将非常关键 而大规模的 问题正是不能求解准确解的问题， 并且我们在 问题和解之间构建的桥梁 蚊子追踪生物学模型、 数学模型和算法， 具有非线性动力学特征， 因此， 用 稳定性理论证明蚊子追踪算法能够收敛且能求出 问题有效的优化解， 既可行又非常适合那么蚊子追踪模型为什么具有动力学特征？ 判定动力学系统的标
28、准是看其是否为能量开销（ ） 系统能量开销（ ） 系统的特征是系统的总能量将随着时间的推移而减少， 直至能量为零 在蚊子追踪的生物学模型中， 目标（ ） 对所有的人造蚊子都具有吸引力， 目标吸引力即为该模型的能量， 使整个模型运动 随着时间的推移， 目标吸引力不断变化， 一旦目标吸引力为零， 蚊子追踪的生物学模型将会停止运动， 达到稳定的状态 对应于 问题， 其求解最短路的目标将会使每一个城市对间的路径的灰度不断演化， 当最短路径找到， 路径的灰度将全部为黑色（） 或是白色（） ， 达到稳定状态， 不再演化因此， 我们的求解 问题的蚊子追踪模型具有动力学特征明显地， 在具有动力学特征的模型中，
29、 可通过度量能量来判断整个系统的稳定性 在蚊子追踪算法的数学模型中， 我们用“ 混合目标吸引力函数（ （） ） ” 来对模型中的目标吸引力进行定量化， 此函数类似于其他动力学系统中的能量函数 在下面的收敛性证明中， 将构建一个基于目标吸引函数的正定函数作为 函数 通过分析所构建的 函数是否随时间单调减少， 来判断蚊子追踪模型的稳定性下面我们先介绍 第二稳定性定理 第二稳定性定理 考虑到函数（） 有（）（）（ 正定， ） ；（）（） ） （ 负定， ）那么（） ） 被称为 方程的备选方程，满足 渐近稳定性 第二稳定性定理的机理是很容易理计算机学报 年解的 蚊子追踪模型是由一群人造蚊子和一个目标组
30、成 我们可以想象， 如果目标消失， 对人造蚊子的吸引将不存在， 而目标消失之前的吸引力又不会储存， 因此， 这群人造蚊子一定会停止运动达到一个静止状态 这个最终的静止状态就是稳定的平衡状态对于 第二稳定性定理来说， 方程的一个好的选择是蚊子追踪模型中的混合吸引力函数 当然， 如果在证明过程中需要对此函数进行一些变形， 也是可以接受的定理 如果条件式（ ） 成立， 蚊子追踪算法将收敛于一个稳定的平衡状态证明 对 于 蚊 子 追 踪 模 型， 我 们 定 义 一 个 方程（） ） 如下：（） ）（）（） 据式（） 更新，（）（）（） ； （） （） （） （）（） （）（） （）（） （） 并行初
31、始化和更新后， 得到的矩阵要进行以下个步骤的处理：（） 如果 ，那么 这样是为了确保雄性人造蚊子的灰度值总为（） 非负性： 如果 ， ，那么让 ， （） 标准化： 让 且 ，这样是为了满足 问题的约束（ 见定义） ， 即 且 ， ， 据式（） 并行更新后， 矩阵也要进行以上步骤的处理通过使用上面提到的个步骤， 矩阵和矩阵将在单位维空间中演化因为 ， 那么（） 所以（） ） （） ） ， （） ，其中 （） （） （） （） （） （） （） （） （） （） （） （） （），其中， （） （） （） （） （） （） （） （） （）（） （）（） （） （） （） （） （）， （） （）
32、 （） （） （） （）（） （）（） （）（） （） （） （） （） （）所以（） ） ， （） （） （） （） （） （） （） （） （）（） （）（） （）（） （）（ ）如果式（ ） 中各项之和小于， 那么（） ） 即 （） （） （） （） （） （） （） （） （）（） （）（） （）（） （）（ ）分析上式（ ） ：当 （），那么 （）， （）因此 矩阵中的元素当 （）时不需要演化更新计算事实上， 仅 （）的 矩阵元素被处理为雌性人造蚊子因此， 在蚊子追踪算法的演化模型中 （）除了矩阵元素 （）， （）， （）， 总得到 （） ， （）所以 （） （） （）且 （） （）
33、那么 （） （） （）我们有 （） （） （） （） （） 明显地， 除了 矩阵元素 （） ， （） ， （）， 那么 （） （） （） （） 因此，式（ ） 的第项大于因此要使式（ ） 存在， 第项（） （）（） （）（） （）小于即（） （）（） （）（） （）（ ）根据 第二稳定性定理， 只要我们据式（ ） 恰当地选择参数， 蚊子追踪算法期冯翔等：仿生蚊子追踪算法的收敛性能够保证 即， 当 ， 那么（）证毕 参数分析在蚊子追踪算法中仅仅只有个参数， 它们是，和 这里， 我们分析它们， 然后指出它们应该怎样选值首先，代表目标对人造蚊子的吸引力的强度越大， 所有人造蚊子将朝目标移动得更快 因
34、此，影响 问题的收敛速度 据命题，应该选取较小的值， 通常定理 关于蚊子追踪算法中的参数， 可以据式（ ） 得以下结论（） 如果，和同时成比例变化， 蚊子追踪算法的解将不变 因此， 我们能让，（，）（） 无论在（，） 间选择什么值， 蚊子追踪算法的收敛性几乎不受到影响（） 当比，之和大较多时（ 满足式（ ） ） ，蚊子追踪算法收敛证明 （） 从式（ ） ， 可以得到结论（） 对于式（ ） ， 其中（） （）；（） （） （ ） （ ）；（） （） （ ）将式（ ） 中正的项放在“” 左边， 负的项移动右边 那么式（ ） 成为 （ ） （ ）（） （）（ ）式（ ） 中， 因为 ， 且， 那么
35、（ ） （ ）通常为较大的常数， 所以非常小在式（ ） 中要视为的系数， 因此几乎不影响蚊子追踪算法的收敛性（） 基于结论， 式（ ） 将近似为（） （）（ ）其中（） （） （ ） ；因此， 式（ ） 为 （ ）因此， 当 时， 条件式（ ） 将满足， 蚊子追踪算法将收敛越大， 蚊子追踪算法收敛的越快证毕实验结果这一部分， 给出关于蚊子追踪算法个方面（ 如何使用、 有效性和并行性） 的详细实验结果首先， 使用一个非常简单的（ 小规模） 问题， 一步一步详细解释蚊子追踪算法是怎样使用其次， 用蚊子追踪算法去求解大量的、 大规模随机产生的 问题，测试算法的有效性， 并给出实验结果最后， 给出了用
36、蚊子追踪算法在超级并行计算机集群上计算不同规模的 问题的真实收敛时间， 测试算法的并行性和效率， 并与文献中最新的并行算法相比较所有的实验都是在联想深腾 高性能计算集群上完成的， 该机群系统拥有 个计算结点， 每一个结点的配置为 ， 内存 ， 硬盘 蚊子追踪算法的使用为了能解释清楚蚊子追踪算法是怎样求解出 问题的解， 又不占用太多的文章篇幅， 这里我们使用一个非常小规模的个城市的 问题为例， 用蚊子追踪算法找出这个实例的遍历个城市的最短路径， 并给出算法计算过程中的详细步骤随机产生个城市节点的坐标（ 见图） ， 即初始化这个城市的轴和轴坐标为到之间的随机数，（，） 为（ ， ）（ ， ）（ ，
37、 ）（ ， ）（ ， ）（ ， ）（ ， ）（ ， ）蚊子追踪算法计算过程步骤 ：由于有个城市节点， 故在蚊子追踪模型中有 个人造蚊子因为没有城市间的节点是不可到达的， 故所有 ， 即模型中所有人造蚊子都为雌性， 个雌计算机学报 年图个城市节点的 实例性人造蚊子都要并行进行演化 ：（） 初始化人造蚊子的强弱值 与两城市节点间的距离 相关， （） ， 这样处理是为了让求最大化问题变为求最小化问题（ 最短路问题）（） 让 ，让个人造蚊子 ， ，为非常非常弱， 使它们不可能追踪到目标即让 （） 当时， （）（）槡（，）为城市节点的坐标（） 对初始化的矩阵， 还要做以下步处理： 如果 ，那么 非负 性
38、： 如 果 ， ， 那 么 让 ， 标准化： 让 且 ， 此步是为了满足 问题的约束条件 且 ， ，初始化的矩阵（ ）为 烄烆烌烎 ：初始化：（）（） 初始化所有人造蚊子 的灰度值 为均值， 即（ ）（ ） 这里 被初始化为均值 此外， 也可以被初始化为到之间的随机数事实上， 基于我们所做的大量实验的结果， 发现不论 始何初始化， 都不会对所求的优化解产生影响（） 对初始化的矩阵， 还要做以下步处理： 如果 ，那么 非负性： 如果 ， ， 那么让 ， 标准化： 让 且 ， 此步是为了满足 问题的约束条件 且 ， ，（） ：（） （） 步骤并行计算和更新每一个人造蚊子的灰度值 和 强度值（ 这里
39、我们仅给出蚊子追踪算法第步演化迭代的结果，） 并行计算 和 的增量：（） ：根据式（） ， 得 ，其中， （ ） ， （ ） ， （ ） （ ） ， （） （ ） （） ：根据式（） ， 得 ，其中， （ ） ， （ ） ， （ ） （ ） ， （ ） 并行更新 （） 和 （） ： （） （） （） ， （） （） （） ， ， ， ， 在并行更新完 （） 和 （） 后， 矩阵和需要分别使用步骤 （） 和步骤 （） 中的步进行处理第次并行更新后的矩阵（ ）为期冯翔等：仿生蚊子追踪算法 烄烆烌烎 第次并行更新后的矩阵（ ）为 烄烆烌烎 第次并行更新后（） （） ， 比（） （）优化了很多参数，和
40、，根据定理和我们做的大量实验能得到以下结论：（） 当越大， 蚊子追踪算法的收敛速度越快（） 当参数，和成比例改变， 实验结果不会受到影响（） 参数的选取， 对蚊子追踪算法的收敛性和所求得的解影响不大（） 为了使蚊子追踪算法收敛， 即求解出 问题的优化解， 需要根据式（ ） ， 设定参数远大于参数和之和在重复步骤的并行迭代更新第 次后， 我们得到个城市节点 实例的最优解（ 遍历个城市的最短路见图）蚊子追踪算法在迭代第 步后， 得每一个人造蚊子的灰度值 （ ） 如表 表 灰度值 （ ） 灰度值 代表城市节点和之间路径为通（ 着黑色） ， 即最短路经过路径 同时， 也代表人造蚊子追踪到目标 反之，
41、如果灰度值 ， 代表城市节点和之间路径为断（ 着白色） ， 即最短路不经过路径 对应地， 也代表人造蚊子没有追踪到目标表总结了此 实例的计算结果从表可以得知， 蚊子追踪算法在求得优化解收敛以后， 不论再并行计算演化多少步， 其优化解不变而且， 对于该 问题， 用蚊子追踪算法求解， 其所得优化解和其他结果都相同 这表明了蚊子追踪算法具有相当好的稳定性 因为此实例规模相当小， 我们仅用了一个并行节点计算表 实验的计算结果参数值并行处理器个数 问题规模达到收敛时迭代次数 收敛时间 （ ） （ ，） ） 通过大量的实验， 我们发现所有灰度值 总会收敛于或 当 问题规模较小时， 收敛时间和步数少； 当规
42、模较大时， 收敛时间和步数大即使当 问题有上千个城市节点时， 蚊子追踪算法也能每次都收敛， 千万个人造蚊子的灰度值 将经过数万次的并行计算更新， 而最终收敛为或 我们曾做过实验， 在超级并行计算机集群上， 用 个并行计算节点， 并行计算 个城市节点的 问题， 用蚊子 追 踪 算 法 花 （ 约） 得 到 优 化 解， 个灰度值并行计算 后全部收敛于或图当时， 人造蚊子的灰度值对应于 问题的优化图图分别给出了人造蚊子的灰度值对应于 实例的优化， 从初始到 收敛过程中的演化情况图中， 两城市节点间的直线的灰色度越深， 代表 越大； 当 时， 达到稳定优化状态， 我们用实线表示， 以区别于灰度值较小
43、的虚线；当 越小， 直线的灰色度越浅； 当 ， 蚊子追踪算法收敛时， 所有 不是为就是为， 两两城市节点要么为实线连接， 要么无连钱（ 连线为白色） ， 遍历城市节点的最短路线自然显现， 求得了 实例的最优解计算机学报 年 蚊子追踪算法的有效性我们已随机选取大量的不同规模的 问题，用蚊子追踪算法去求解 问题的规模从几个城市到上千个城市节点， 蚊子追踪算法总是能够收敛并且求出 问题的优化解在真实的自然界里， 蚊子间在追踪目标时很少有合作行为， 每个蚊子独自追踪目标 在我们的蚊子追踪模型中， 每一个人造蚊子在没有信息交换的情况下并行演化和运动因此， 蚊子追踪算法具有内在并行性， 但只能求出问题的近
44、似解 如图 和图 所示， 虽然蚊子追踪算法能求得 问题的优化解， 但也易于陷入局部优化图 用 算法求得的 个城市和 个城市 问题的优化解 蚊子追踪算法的并行性和效率蚊子追踪算法由于其内在的并行性， 为不能用传统方法求解的问题提供了有价值的、 可能求近似优化解的方法 蚊子追踪模型中， 所有人造蚊子的灰度值 和强弱值 在没有信息交换的情况下并行计算和更新， 这就是蚊子追踪算法并行性的基础大量的实验结果也证明了蚊子追踪算法好的并行性和高的计算效率 对于不同规模的 问题， 其真实的计算收敛时间和迭代步数见表 我们分别使用和 个集群上的并行计算节点来完成表中 中的典型的 实验表中， “ ” 和“” 分别
45、为 用 和个并行计算结点计算 问题收敛时间“ ” 为期冯翔等：仿生蚊子追踪算法图 用 算法求得的 个城市和 个城市 问题的优化解 用 个并行计算结点计算的加速比， “ ” 为 的并行效率， 表 算法求解不同规模 问题的收敛时间和效率 问题测试集并行计算时间 单节点计算时间加速比 并行效率 如图 所示， 当蚊子追踪算法以非并行方式在一个并行计算节点上计算时， 收敛时间随 规模的增大呈指数增长， 这与其他准确性方法相类似 但当蚊子追踪算法以并行方式同时在多个集群的并行节点上计算时， 收敛时间大大降低 实验结果验证了蚊子追踪算法的并行性求解 问题并行性较好的最新的自然演化算法有： 并行遗传算法（ ，
46、） （ ） ，并 行 蚁 群 算 法 （ ， ） （ ） ， 并行遗传蚁群算法（ ， ） （ ） ， 并行免疫算法 ， ） （ ） 和改进的并图 不同问题规模 的收敛时间行免疫算法（ ， ） （ ） 我们将 与这些最新的并行自然演化算法在并行效率方面进行实验比较 实验结果见表表 与其它并行算法的比较 问题测试集算法并行计算时间 单节点计算时间并行效率 如图 所示， 对于不同规模的 ， 算法比其他并行算法的并行计算时间少很多 如图 所示， 求解不同规模的 的并行效率都大于 ， 而其他的并行算法的并行效率通常在 到 之间， 的并行性更好计算机学报 年结论本文以 问题为载体， 提出了受蚊子追踪目标行
47、为启发的蚊子追踪算法（ ） 此算法将 矩阵中的每一个元素处理为一个人造蚊子， 问题的求解就转化为一群人造蚊子对目标的追踪行为 在蚊子追踪模型中， 每一个人造蚊子独立地追踪目标， 朝着目标不断运动演化 人造蚊子向目标移近一步， 它们的灰度值和强度值发生相应的演化当所有人造蚊子停止运动（ 追踪到目标或没有追踪到） ， 蚊子追踪模型达到稳定状态， 所有人造蚊子的灰度值将收敛为或， 映射到 问题城市节点间的路径着色上， 就得到了 问题的优化解 的仿生模型、 数学模型、 并行算法、 模型算法的一致性证明、 收敛性证明、 参数分析在本文中被详细的阐述 此外， 怎样使用 算法以及该算法的有效性和并行性相关的
48、实验结果也在本文中给出 理论和实验都证明， 蚊子追踪算法能够收敛，能够求出 问题的优化解， 并在并行性上有其他算法不能替代的优势蚊子追踪算法除了能求解 问题以外， 应用领域主要还有网络、 信息融合、 多目标优化和智能系统中现有方法难以处理的某些复杂问题， 具体为：（） 多传感器信息融合， 如机器人运动中多传感器信息融合问题（） 网络动态优化问题， 如内容分发网络缓存资源分配问题、 保障 的带宽动态分配问题（） 智能系统中的复杂的优化问题， 如涉及各类社会行为多 系统中的优化问题（） 高性能集群计算机系统工作流均衡问题（） 多目标优化问题（） 目前传统方法难以求解的某些复杂问题，如 序列聚类、
49、匹配， 蛋白质序列预测问题针对以上应用问题， 根据蚊子追踪算法的特点，我们的解决方案如下：（） 将上述问题转化为蚊子追踪算法能并行求解的数学问题描述（） 改进蚊子追踪算法的具体数学模型、 动力学方程等去求解这些问题改进的方法， 一是从问题出发； 二是从类似本文中的收敛性证明和有效性证明方法反推（） 算法中参数的选取和设定 其方法同（）（） 提出算法步骤根据应用的问题和改进后的蚊子追踪算法的数学模型而提出， 并设定算法如何初始化和终止（） 用大量的实验和模拟对改进后的蚊子追踪算法进行测试， 检验其对具体应用问题的有效性、 收敛性、 并行性等方面的性能参考文献 ， ， （ ） ： ： ， ， （
50、） ： ， ， （ ） ： ， ， （ ） ： ， ， ， ， （ ） ： ， ， （） ： ： ， ， ： ， ， ， ， （ ） ： 期冯翔等：仿生蚊子追踪算法 ， ， ， ， （） ： ， ， ， ， ， ： ， ， （） ： ， ， ： ， ， （） ： ， ， ， ， ， （） ： ： ， ， （ ） ： ， ， ， ， （ ） ： ， ， ， （ ） ： ， ， ， ， （） ： ， ， ， ， ， （） ： ： ， ， ： ， ， ， ： ， ， ， ， ， （） ： ， ， ， ， ， ， ， ， ， ， ， ， （） （ ） （ ） ， ， ， ， ， ， ， ， ， ， （） ；（） ； （） ， （ ） （ ） ， ： （ ） ， （ ） ， （ ） ， （ ） ， ， ， （ “ ” ） ， （ “ ” ） （ “ ” ） ， （ “ ” ） （ “ ” ）计算机学报 年
