进化算法——生物地理学

2023-11-20 19:50
文章标签 算法 进化 生物 地理学

本文主要是介绍进化算法——生物地理学,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

生物地理学这门科学可以追溯到19世纪最著名的自然学家阿尔弗雷德·华莱士和查尔斯·达尔文的工作。人们通常认为华莱士是生物地理学之父。

生物地理学的数学模型描述物种形成(新物种的进化),物种在岛屿之间的迁徙,以及物种的灭绝。一个岛屿是指任何一个栖息地,它在地理上与其他栖息地隔离。

益于生物生存的地理区域可以说具有高的生境适宜度指数(HSI)。与HSI相关的特征包括像降雨量、植物多样性、地形多向性、土地面积以及温度等因素。这些特征被称为适应度指数变量(SIVs)。

HSI高的岛屿适合各种各样的物种,在HSI低的岛屿上则只有几种物种可以生存。由于HSI高的岛屿上生存着大量的生物,有很多物种会从HSI高的岛屿迁徙到附近的栖息地。在用生物地理学开发BBO(生物地理学优化)时假定一个物种从一个岛迁出则该物种在岛上灭绝。

HSI高的岛屿有高迁出入以及低迁入率,HSI低的岛屿则有着高的迁入率。如下图所示:

物种多样性与HSI有关,来到HSI低的岛屿的物种越多,这个岛的HSI增大的机会就越大。上图说明在单个岛上物种丰富程度的模型。迁入率\lambda和迁出率\mu随着岛上的物种数变化。上图的迁移曲线是直线,一般要比这复杂。

当岛上物种为0时,迁到这个岛上栖息的迁入率最大,记为I。栖息地能支撑的最大物种数量是S_{max}。如果岛上没有物种,则迁出率为0,当岛上物种增加,变得拥挤就会有更多的物种离开,迁出率增加。当岛上物种达到它能支撑的最大值,迁出率达到最大,记为E。


目录

生物地理学是一个优化的过程

基于生物地理学的优化

BBO的扩展 

BBO与遗传算法



生物地理学是一个优化的过程

生物地理学是种群分布的一种自然方式,人们常常把它看作为在栖息地维持均衡的过程来研究。在生物地理学中,稳定性和最优性是一个硬币的两面。生物地理学中的最优性涉及能高度适应其环境的多样的复杂的群体。生物地理学中的稳定性涉及已有种群的持久性。复杂的群体比简单的群体适应性更强。

人们普遍人同最优性和稳定性之间的互补特征。均衡和最优不过是对同一现象的不同看法。

生物地理学是一个正反馈现象,它类似于自然选择,适者生存。


基于生物地理学的优化

假设有一个优化问题和一些候选解,称候选解为个体。好的个体在问题上的表现好,差的个体在问题上表现差。好的个体类似于高HSI的岛屿,差的个体类似于低HSI的岛屿。宜居的岛屿迁入率比不太宜居的岛屿迁入率低,好的个体比差的个体更抗拒改变。好的个体易于与差的个体分享好的个体的特征,不太宜居的岛屿更有可能接受来自宜居岛屿的很多移民。新特征的加入可能会提高差的个体的质量。基于这个方法的进化算法被称为基于生物地理学优化(BBO)

假定每一个BBO个体都由完全相同的物种数的曲线表示,如下图。S1代表一个较差的个体,S2代表一个较好的个体。对于S1迁入率较高,这意味着它有可能接受来自别的候选解的新特征。对于S2迁出率较高,这意味着它有可能与其他个体分享其特征。

 利用每一个个体的迁移率在个体之间以概率分享信息。假设种群规模为N,x_{k}是种群中的第k个个体,优化问题的维数为n,x_{k}(s)x_{k}中的第s个独立变量,其中k∈[1,N],s∈[1,n]。在每一代,第k个个体的每一个解的特征,存在被替换的概率为\lambda _{k}(迁入概率):对于k∈[1,N],s∈[1,n]有:

\lambda _{k}x_{k}中第s个独立变量被替换的概率

如果选出了要被替换的解的特征,我们用与迁出概率{\mu _{i}}成正比的概率选出迁出的解。在这一步可以采用任何一种基于适应度的选择方法,如果使用轮盘赌选择则:

由此可以得到下面的算法(标准BBO算法,也称基于部分迁入的BBO算法)。在当前这一代,种群中的个体被替换之前要完成没一个个体的迁移和变异,因此在算法中需要借用临时种群z。


BBO的扩展 

1.迁移曲线

生物地理学中的迁移曲线是非线性的,很难量化生物地理学的迁移曲线的确切形状,不同岛的迁移曲线也不同,但在自然界中有很多曲线呈S型。

非归一化的曲线建模为:

其中r_{k}是种群中第k个个体的适应度的排名,对于适应性最差的个体, r_{k}=1,而对于最好的个体,r_{k}=N(种群规模)。用正弦迁移率建模,迁移率的值设定为:

由上式得到的S型曲线如下图所示:

2.混合迁移

在混合交叉中,子代的基因不再复制父代的单个基因,而是两个父代基因的凸组合。这促使我们在BBO中使用混合迁移算子。在标准BBO算法中,个体z_{k}的特征全部由个体x_{j}的特征替换。

在BBO的混合迁移中,个体 z_{k}的特征不是由个体x_{j}的特征替换,而是等于z_{k}(s)x_{j}(s)的凸组合:

其中α∈[0,1],如果α=0,则混合的BBO算法退化为标准的BBO,可见,混合BBO是对标准BBO的推广。混合参数α可以是随机的、确定的或与  z_{k}x_{j}的相对适应度成正比。

混合迁移适合用于连续解特征的问题。

与标准迁移比较,采用混合迁移有两个理由:首先,好的个体不大可能因为迁移而退化,因为在迁移过程中它们最初的特征会有一部分保留下来。其次,差的个体在迁移过程中至少会接受来自好的个体一部分解的特征。

3.BBO其他办法

BBO还有其他的实施方法。不是对每一个解的特征都用\lambda _{k}检验随机数,而是对一个个体只用一次\lambda _{k}检验,如果决定迁入,就替换z_{k}的所有解的特征。可以称之为基于总迁入的BBO。

还可以利用\mu _{i}决定是否迁出已知个体的一个特征。只有当决定迁出之后,才用变量{\lambda _{k}} 在轮盘赌程序中选择迁入地。根据这个思路得到基于迁入的BBO。

将上面的思想组合起来实施会得到4中BBO算法,第一种,基于部分迁入的BBO算法,它是默认的方法。第二种,基于部分迁出的BBO算法。第三种,基于总迁入的BBO算法。第四种,基于中迁出的BBO算法。第2-4中算法如下所示:

BBO与遗传算法

在才用均匀交叉的遗传算法中,每个子代基因都随机的从它的父代中选择。在基因库重组中,所谓的多父代重组和扫描交叉,子代的每个基因也是随机的从它的父代中选择,这时父代的个数大于2。实施全局均匀重组是基因库重组的一种方式,子代基因从其父代随机得选出来,这里父代种群等价于整个遗传算法种群,并根据适应度值随机地选择(如轮盘赌选择)。

如果我们才用全局均匀重组,并对每一个后代的每一个解的特征采用基于适应度的选择,就得到了下面的算法:

其实BBO算法是特殊类型的全局均匀重组遗传算法的一个推广。因为如果不在BBO算法中令\lambda _{k}=1-\mu _{k},而是对所有k令\lambda _{k}=1,则BBO算法就等价于GA/GUR算法。

这篇关于进化算法——生物地理学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/397031

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖