生物地理学优化算法的迁移率模型分析

书书书 第 卷 增刊 年 月 东 南 大 学 学 报 自 然 科 学 版 生物地理学优化算法的迁移率模型分析 马海平 李 雪 林升东 绍兴文理学院物理与电子信息系 绍兴 摘要 为了提高算法的优化性能 在标准生物地理学优化算法基础上 概括了生物地理学理论 的基本平衡定理 探索了在该定理下优化算法的各种迁移率模型的特点及行为 同时对这些迁 移率模型进行一些典型基准函数的性能测试 通过函数优化实验可知 不同的迁移率模型将对 算法的优化性能产生重要影响 同时符合自然规律的复杂迁移率模型的性能要优于简单的线性 迁移率模型的性能 另外 变异率的不同也将对算法性能产生影响 对提高解集的适应度起着 一定的作用 通过分析表明生物地理学优化算法是一种具有发展潜力的新型优化算法 并得出 当前最有效的迁移率模型 关键词 优化 进化计算 迁移率模型 生物地理学 中图分类号 文献标识码 文章编号 增刊 收稿日期 作者简介 马海平 男 讲师 生物地理学是一门研究生物物种地理分布的学科 主要研究物种地理分布的数学模型 包括物种的 迁移过程 以及相邻栖息地之间的物种分布情况 他们的研究激发了人们对物种地理分布的思考 受蚁 群算法 差分进化 进化策略 遗传算法 粒子群算法 等智能计算方法的影响 将这一自然现 象与工程最优问题联系起来 提出了一种新的进化算法 生物地理学优化 算法 该算法由美国学者 首次创建 从目标函数的测试结果来看 该算法具 有良好的收敛性和稳定性 期望成为一种新的受欢迎的进化算法 是一种生物地理学理论应用于优化问题而形成的一种新型进化算法 其基本思想是根据栖息 地之间物种迁移来完成信息流通 通过调整迁移过程中的迁入率与迁出率 迁移拓扑 迁移时间间隔和迁 移策略来实现信息共享 提高栖息地的适应性 从而得到问题的最优解 最大的特点是在进化的每 一代中 其原始种群 这里指栖息地 不会消失 而是通过迁移来提高种群的适应度 反过来又通过适应 度来决定迁移率的大小 本文首先介绍 的理论机制及实现过程 并证明一个新的平衡定理 其次分 析了 算法的各种迁移率模型 接着通过目标函数对各种模型进行性能测试 最后总结全文及提出 下一步工作 生物地理学优化算法 生物地理学理论 生物地理学基本理论大致描述如下 在一个区域内 如果某个栖息地非常适合生物居住 则该栖息 地具有高居住适宜度指数 与该指数相关的因子包括该区域内的降雨量 温度和湿度等自然因数称之为适宜度指数变量 具有高 的栖息地往 往能够容纳较多的物种 而具有低 的栖息地则只能容纳少量物种 另外高 栖息地上的物种由于 生存空间饱和等问题而大量迁出到相邻栖息地 同时只有少量物种迁入 而低 的栖息地由于物种稀 少而使得较多的物种迁入和较少的物种迁出 但是当一个栖息地的 一直保持较低水平时 那么由于 某种自然灾害可能造成居住在这里的某些物种趋于灭绝 造成其他大量物种的迁入 将研究这种自然现 象的理论称之为生物地理学理论 由于栖息地的 与该地的物种多样性成正比 因此物种迁移有助于 提高栖息地上的物种多样性 从而改善和提高栖息地的 类似于一般的智能计算方法 假定有一优 化问题和多个候选解 并且给定解集可以用 作为适应度函数量化 那么一个好的解集对应具有高 的栖息地 一个不好的解集对应于具有低 的栖息地 通过栖息地之间的物种迁移 造成具有高 的解集与低 解集共享某些特征 这并不意味着高 解集的这些特征消失 相反 可以使具有 低 的解集从高 的解集中接受一些新的特征 从而提高解集的适应度 将这种基于生物地理学理 论的智能方法称为生物地理学优化算法 为了说明生物地理学理论的基本原理 以单个栖息地上的物种迁移为模型进行描述 其中迁入率 与迁出率 是关于栖息地上物种种类 的函数 同时假定栖息地能够容纳的最大物种数为 定义该栖息 地具有物种种类 的概率为 则在 到 时间内 概率 改变为 为了使 时刻内有 类物种 必须满足下列条件之一 在 时刻有 类物种 在 到 时刻间 没 有迁入和迁出发生 物种概率为 在 时刻有 类物种 存在某一物种的迁 入 概率改变为 在 时刻有 类物种 存在某一物种的迁出 概率改变为 假定 足够小使得超过一类物种的迁入或迁出的概率能忽略不计 那么当 时 式 对时间 求极限 可以得到 定义 式 可以用矩阵方程表示为 从该矩阵可以看出 矩阵 的第一行表示物种种类 只可能从 转变到 最后一行表示物种种类 只可能从 转变到 定理 当某一栖息地的物种种类处于稳定状态时 对应的概率为 证明 当物种种类处于稳定状态时 根据式 可得 即 增刊 马海平 等 生物地理学优化算法的迁移率模型分析 根据式 得 把式 中的每一个方程与其上面的方程相加 得到 对式 进行转换 可得 因为 得到 即可得到式 证明完毕 生物地理学优化算法 根据上述的生物地理学理论 并以适应度最优化为求解目的 提出了生物地理学优化算法 该算法具有一般进化算法简单有效的特性 是一种解决优化问题的新的智能方法 假定有一优化问题和 用栖息地 表示的多个候选解 进一步假定 作为评价解集好坏的标准 那么 类似于遗传算法中 的适应度函数 对 而言 其进化过程主要有 个步骤 分别是迁移和变异 定义 迁移是一种依据迁移率来调整栖息地 的概率算子 首先根据其迁入率 依概率选择需要迁入的栖息地 确定 后 根据迁出率 依概率选择需要 迁出的栖息地 接着从 中随机地选择 替代 中的 这里 表示解集特征 等同于遗传 算法中的 基因 最后通过计算 来评价解集的适应度 定义 变异是一种在先验概率 基础上修改栖息地 的概率算子 即依概率 选择需要修改的栖息地 确定 后 随机产生一个 替代 中的 这种变异 策略使得具有低 的解集通过变异得到一次改进 同时使得具有高 的解集获得提高的机会 是在迁移算子和变异算子基础上修改栖息地 的一种进化迭代算法 其中一代的实现方式为 每个栖息地 每个 根据迁入率 决定是否需要迁入到栖息地 需要迁入 根据迁出率 选择迁出的栖息地 东南大学学报 自然科学版 第 卷 根据变异率 决定是否对栖息地 实行变异 实行变异 随机产生一个 替代栖息地 中的 迁移率模型分析 根据生物地理学物种分布情况 可以得到不同的迁移率模型 如图 所示 图中 迁入率 与迁出 率 是关于栖息地上物种种类 的函数 表示最大迁入率 表示最大迁出率 为栖息地平衡时的物 种种类 即在该点处迁入率与迁出率相等 图 四种不同的迁移率模型 模型 线性迁移率模型 在该模型中 如图 所示 迁入率 和迁出率 是关于物种种类 的线性函数 从曲线可以看 出 当栖息地上没有物种的时候 迁入率为最大 而迁出率为零 随着物种种类的增加 栖息地变得越 来越拥挤 迁入的可能性越来越小 而离开该地 到相邻栖息地的物种越来越多 即迁出率越来越大 最 后当物种种类达到饱和状态 时 迁入率为零 迁出率为最大 模型 指数迁移率模型 在该模型中 如图 所示 迁入率 和迁出率 是关于物种种类 的指数函数 从曲线可以看 出 当栖息地上有较少的物种时 迁入率快速下降而迁出率缓慢增加 而当栖息地临近饱和状态时 迁 入率缓慢减少 同时迁出率快速上升 模型 二次迁移率模型 图 显示了栖息地的二次迁移率模型 从曲线可以看出 其迁移变化特点类似于指数迁移率模型 模型 余弦迁移率模型 图 显示了栖息地的余弦迁移率模型 从曲线可以看出 当栖息地上有较少或较多物种时 迁入 率和迁出率变化比较平稳 而当栖息地具有一定数量的物种时 迁入率和迁出率变化相对较快 性能分析 与其他进化算法的性能比较已完成 因此本文的主要目的是测试各种迁移率模型对 算 增刊 马海平 等 生物地理学优化算法的迁移率模型分析 法性能的影响 为了验证迁移策略的有效性 采用 个测试函数 见表 进行函数优化实验 且这些函 数的全局最小值均为 表 测试函数 函数表达式定义域函数表达式定义域 槡 槡 便于比较的合理性和公正性 算法和函数的参数设置如下 测试函数的维数 种群 栖息地 大 小 最大迁入率 最大迁出率 变异率 分别为 进化代数为 算 法独立运行 次 种迁移率模型的优化结果见表 表 测试函数的结果比较 函数变异率 最佳值平均值 模型 模型 模型 模型 模型 模型 模型 模型 由表可知 在不同迁移率模型下 的性能具有很大的差别 无论从平均值还是从最佳值角度考 虑 模型 在多数测试函数中优于其他 种模型 也就是说 接近自然规律的迁移率模型性能要优于简 单的线性迁移率模型 这与基于自然规律的改进遗传算法相似 另一方面 根据表可知 不同变异率 或许对提高解集的适应度具有一定的作用 但对函数的性能优化并没有明显的规律 东南大学学报 自然科学版 第 卷 结语 本文利用生物地理学的基本理论 概括了栖息地上的物种平衡定理 并在这基础上提出了不同的迁 移率模型 同时结合 算法思想 完成不同迁移方式对 算法性能影响的探索 通过函数优化实 验可知 不同迁移率将对 的性能产生重要影响 复杂迁移率模型的性能要优于简单的迁移率模型 目前 算法还处于研究的起步阶段 其潜在的优越性还有待于进一步探索 因此下一步的工作 主 要包括以下几个方面 理论分析 利用有效的数学工具对算法的运行行为 收敛性及