生物地理学优化算法及原理（Biogeography-Based ...

unityloverz · 发表于 2022-5-8 19:44

生物地理学优化算法

丹.西蒙 IEEE 高级会员
翻译by 海绵宝宝
摘要：生物地理学是研究生物体地理分布的学说。早在20世纪60年代，用来描述生物体地理分布的数学方程首先被发现并且发展起来。工程师的理念：我们可以向大自然学习。这激励人们使用生物地理学去解决优化问题。就像生物遗传的数学算法激励了遗传算法的发展以及生物神经网络的数学算法激励了人工神经网络的发展。本文认为生物地理学的数学算法会成为一个新领域的发展基础：基于生物地理学的优化算法（BBO）。本文讨论了自然生物地理和它的数学方法，然后讨论了如何使用它解决优化问题。本文可以看出BBO和其他基于生物学的优化算法相比有共同的特征，比如遗传算法和粒子群算法。这就使得BBO适用于许多遗传算法和粒子群算法适用类型的问题，换句话说，具有多目标优化的高维度问题。然而，BBO同样具有与其他基于生物学的优化算法不同的特性。本文展示了BBO在一组14项基准指标中的表现并且把它和其他7种基于生物学的优化算法进行了比较。本文也展示了BBO在现实世界为航空发动机健康评估做的传感器选择问题。
关键词：生物地理学，进化算法，卡尔曼滤波，最优化，传感器选择。
I.简介

生物地理科学可以追溯到19 世纪自然科学家的工作，比如 Alfred

[1]

和 Charles Darwin

[2]

。直到 20 世纪 60 年代，生物地理学都是描述性和历史的。20 世纪60年代早期，Robert MacArthur和 Edward Wilson开始在一起做生物地理数学模型的工作。他们的工作以1967年发表的经典岛屿生物地理学论

[3]

而告终。他们感兴趣的主要是集中在物种在相邻岛屿之间的分布上。他们对物种的迁徙和消灭数学模型比较感兴趣。由于 MacArthur和 Wilson的工作，生物地理学已经变成了一个主要的研究领域

[4]

。最近搜索的生物学摘要（一项生物学研究指数）显示,在2005年有25452篇和生物地理学主题相关的论文被发表。然而,一项科学文摘的搜索（一项工程研究指数）显示，没有生物地理学论文被写过。针对这个问题，本文的一部分目的就是为了合并蓬勃发展的生物地理学和工程使其两个科目可以互相收益。生物地理学的应用工程类似于过去近几十年所产生的与遗传算法、神经网络、模糊逻辑、粒子群算法和其他领域的计算机智能。生物地理学的数模型描述了物种如何从一个岛屿迁移到另从一个岛屿，新物种是如何产生的,以及物种是如何灭绝的。“岛”这个专业术语在这里是描述性的。而不是照字面意思随便使用的。也就是说，一个岛屿是地理上孤立于其他任何栖息地的栖息地。因此，我们在本文中使用更通用的术语“栖息地” (而不是“岛”)

[4]

。适合生物种作为住宅的地理区域，应该有较高适宜性指数 (HSI)

[5]

。和适应性指数有关的几个特性指数，包括降雨量、植被的多样性、地形特征的多样性、土地面积和环境温度。这些可以表征可居住性适宜度的变量被称为适宜性指数变量 (SIVs)。适宜性指数变量可以被认为是栖息地的自变量，而栖息地适宜度指数可以认为是因变量。栖息地适宜度指数高的栖息地往往有大量的物种,而那些栖息地适宜度指数低的区域却只有少数的物种。栖息地适宜度指数高的栖息地有许多物种,移民到附近的栖息地，仅仅凭借它们群集的大量物种。栖息地适宜度指数高的栖息地物种的移入率较低，因为它们的物种已经接近饱和。因此，栖息地适宜度指数较高的栖息地比适宜度指数低的栖息地在生物分布上更稳定。出于同样的原因，高适宜度指数的栖息地有较高的迁出率；生活在适宜度指数高的栖息地的大量物种有很多机会移民到邻近的栖息地。(这并不意味着一个正在迁出的物种完全从本土栖息地消失;只有少数代表移民,所以一个正在迁徙的物种仍然栖息在本土栖息地。于此同时迁移到邻近的栖息地。)具有低HIS的栖息地由于他们人口稀疏所以具有更高的迁入率。这种迁入的新物种很可能会提高栖息地适宜度指数，因为栖息地的适宜性正比于其生物多样性。然而如果一个栖息地的栖息地适宜度指数仍然较低，然后驻留在那里的物种将会趋于灭绝。这将进一步为额外的迁入移民腾出空间。因此,具有较低HIS的栖息地比高HIS的栖息地有更活跃的物种分布。
生物地理学是自然的物种分布方式，类似于一般问题的解决方案。假设我们面临一个问题还有很多候选的解决方案时。这样的问题存在于生活的任何领域(工程、经济学、医学、商业、城市规划、体育等等)，只要我们有一个可以量化的衡量给定解决方案的适用性。一个好的解决方案类似于栖息地适宜度指数高的一个岛屿,一个表现差的解决方案类似于一个适宜度指数低的岛屿。适宜度指数高的解决方案抵制改变超过适宜度指数低的解决方案。同样,栖息地适宜度指数高的解决方案更倾向于向栖息地适宜度指数较低的解决方案分享他们的特性。(这并不意味着HSI高的解决方案的特性会消失，这些可分享的特性依然留在HSI高的解决方案中,同时出现在HSI低的解决方案中。这类似于一个物种的代表迁移到一个栖息地，而其他代表仍然留在原来的栖息地)。较差的解决方案从良好的解决方案接受很多新特性。这些新特性的加入会使这些解决方案的质量得到改善。我们称这种解决问题的新方法为生物地理学优化算法(BBO)。
BBO与其他基于生物学的算法有一些共同的特点。比如遗传算法（GA）和粒子群算法（PSO），BBO有一种在解决方案之间共享信息的方式。遗传算法解决方案的每一代最终会“死”,而PSO和BBO的解决方案却永远生存了下来(虽然他们的特点随着优化过程的进展而改变)。PSO的解决方案更容易聚集在类似的团体中，而GA和BBO解决方案却不一定有内置集群的倾向。
本文的目的有三部分。首先,我们想给出一个一般的描述优化方法的新方法称为生物地理学算法。我们首先通过研究自然生物地理学,然后概括它获得一个通用的优化算法。第二，我们要比较和对比BBO与其他基于种群的优化方法。我们是从一个算法的观点来观察其共性和差异，并通过比较它们在一组基准函数的表现来做的。第三，我们要把BBO应用到现实的问题解决中，这个项目是航空发动机健康评估的传感器选择问题。这将证明BBO在现实世界问题中的适用性。
第二部分回顾了生物地理学的思想和数学描述，而第三部分讨论了如何使用生物地理学理论制定一般的优化算法。第四部分回顾航空发动机健康评估和如何使用卡尔曼滤波估计发动机的健康。第五部分提供了一些比较BBO与其他优化方法的仿真结果，针对一般基准测试函数和传感器的选择问题。第六部分提出了一些结论和对进行进一步工作的建议。
II.生物地理学

图1根据参考文献3展示了单个栖息地的物种丰富度模型。迁入率λ和迁出率μ是该栖息地物种数量的函数。
考虑到迁入率曲线。设该栖息地最大可能的迁入率为

，当该栖息地的物种为零时取最大值。随着物种的数量增加,栖息地变得更加拥挤，能够成功迁入该栖息地生存的物种减少，同时迁入率不断降低。该栖息地可以承受的最大物种数量为，与此同时迁入率变为0。

图1. .单栖息地的物种丰富度模型
现在考虑迁出曲线。如果没有物种的栖息地迁出率必须为零。随着物种数量的增加，栖息地变得更加拥挤,更多的物种就会离开栖息地去探索其它可能的聚居地,从而使迁出率增加。设最大的迁出率为 ,当栖息地包含它可以承受的最多物种时取最大值。
物种数量平衡时的物种数量记为

，此时的迁入率和迁出率相等。然而,可能由于瞬时效应的影响

会出现漂移。正的漂移可能是由于井喷式的迁入(由异常引起的。也许，是来自邻近的栖息地大块漂浮物)，或突然形成的物种大爆发(就像一个微型的寒武纪爆发)。负的漂移可能是由于疾病、特别贪婪的捕食者的引入，或其它自然灾害。在一个大的扰动后，大自然需要花很长时间才能使物种数量达到新的平衡

[4][6]

。在图1中，我们描述的迁入迁出曲线都是直线，但总的来说,实际上它们很可能是更复杂的曲线。然而，这个简单的模型给我们提供了一个通用的描述迁入迁出的过程。如果需要，可以在细节上进行调整。
现在，考虑某栖息地包含S中物种的概率  。  从时间t到时间（t+Δt）按如下规律变化：

在这里，  和  是当该栖息地有S种物种时的迁入迁出率。该方程有效的条件：为了使得在（t+Δt）时刻有S种物种，必须满足下面条件中的一个：
1) 在t 时刻有S种物种，并且在t到（t+Δt）时刻没有迁入和迁出。
2) 在t时刻有S-1种物种，并且没有新的物种迁入；
3) 在t时刻有s+1种物种，并且没有新的物种迁出；
我们假设Δt足够的小以至于多一点点的迁出或迁出率可以别忽略。对于公式（1）当Δt趋于0的时候给出了公式（2）：

我们为了计数的简单，定义n= ，并且P=[ 0…  ],现在我们可以把

（S=0，…n）方程排列进一个矩阵方程中：

此处给出的矩阵A如下所示：
对于图1中给出的直线曲线，此处有：

现在我们讨论特殊的情况，E=1。在这种情况下，有公式六，并且矩阵A变成了如下形式：

然后定义 ′如以上公式所示。
1) 观察1：0是矩阵 ′的特征值，其特征向量为：

此处 ‘是一个比( +1)/2稍大或者相等的整数即 ’= (( +1)/2)。该观察已经被直接证明了，但是因为不知道特征值方程 ‘ =  中的比例系数k和其特征向量所以证明过程显得有些冗长乏味。比如当n=4时，我们得到特征向量

当n=5时，可以得到，

2) 推断1：矩阵 ’的特征值应该为：

这个推论还没有被证明，但是通过观察发现到目前为止对于所有的n都是成立的。
定理1: 每一物种数量的概率稳态值如下公式所示:

其中v和vi在公式（8）中已经给出了。证明在附录中已经给出了。
III.基于生物地理学的优化算法

在本部分中，我们讨论前面提到的生物地理学理论是如何被应用在离散领域里的优化问题。
A. 迁移

假设我们面临一个问题和一个候选解决方案群体，它们可以用整数矩阵表示。在解向量里的每个整数可以被看作一个适宜性指数变量。进一步假设我们有一些评估解决方案好坏的方式。这些好的解决方案可以看作是具有高适宜度指数的栖息地。这些不好的解决方案可以看作是具有低适宜度指数的栖息地。适宜度指数类似于其他基于群体优化算法中的适应度（比如遗传算法）。高适宜度指数解决方案代表了拥有很多生物的栖息地，低适宜度指数解决方案指的是拥有少量物种的栖息地。我们假设每一种解决方案（栖息地）都有一个相同的生物曲线（比如满足E=I），但是解决方案所代表的S值取决于它的适宜度指数。在图2中，S1代表一个低适宜度指数的解决方案，而S2则代表了一个高适宜度指数的解决方案。在图2中，S1代表了一个有很少物种的栖息地而S2代表了一个具有许多物种的栖息地。然而对与S1的迁入率 1将会比s2的迁入率高。S1的迁出率 2却比S2的迁出率低。
我们使用每种解决方案的迁入率和迁出率在栖息地间进行概率信息的分享。根据，我们根据其他解决方案修正每个解决方案。如果一个给定的解决方案被选择要修正，然后我们选择它的迁入率λ盖然性得决定是否要修正该解决方案中的每个适宜度指标变量。如果在某个给定的解决方案  中的某个适宜度指数变量SIV被选择要做修正，然后我们使用其他解决方案的迁出率μ盖然性得决定最终哪个解决方案应该随机地迁移出选择出来的SIV到解决方案  中。
BBO算法的迁移策略类似于饲养遗传算法的全局重组的方式和进化策略就是有许多父代可以遗传给单个后代，但是至少在一方面是不同的。在进化策略中，全局重组是为了产生新的解决方案，而BBO迁移策略是为了改善现存的策略。基因重组在遗传策略中是再生复制的过程，而迁移策略在BBO中是自适应的过程。为的是修正已经存在的孤岛。
与其他基于种群的算法一样，我们为了在种群群中保留最佳的解决方案，主要吸收一些杰出的精英。这就使得最好的解决方案避免了因为外来迁入而导致的崩溃。

B. 突变

突如其来的大事件可以剧烈地改变自然栖息地的适宜度指数。这可以导致某物种数量偏离其平衡值（比如来自于邻近栖息地的大量飘移者、疾病、自然灾害）。因此，一个栖息地的适宜度指数可以因为明显的随机事件而改变。我们在BBO中把这种现象作为模型的适宜度因素突变，并且我们根据生物物种数量概念决定突变率。
每种物种的计数概率可以根据给出的公式（2）中的差分方程来计算。通过观察图片2中的物种曲线的平衡点，我们可以得到无论是在高物种数量还是低物种数量的时候都有相对较低的概率。这也可以从公理1中推断出来。适量的物种数量有比较高的概率因为它们处于平衡点附近。
举个例子，考虑这样一个情况，当 =10的时候。可以得，公式（2）中的稳态解是独立于初始概率P(0)的。并且每个数值上的概率都可以计算出来。或者根据公理（1）直接得到P(∞)，如（13）所示。

P(∞)中的每个元素的加和为1（在舍入误差范围内）。并且它们的图像是关于中值的偶函数。
每个种群的数量都有相关的概率，这个概率表明了它被期望作为给定问题的解的可能性。具有很高适宜度指数的解决方案和具有很低适宜度指数的解决方案都是同样不大可能的。具有中间适度适宜度指数的解决方案是相对比较有可能的。如果一个给定的的解决方案S，具有很低的概率  ，那么它很可能意外的被作为解决方案。然而，它很可能会突变成其他解决方案。相反地，一个具有很高概率的解决方案是不大可能突变成另外的解决方案的。这是可以实现的，因为突变率m是对于解的概率是反比例函数：

在这里，

是一个自定义参数。这种突变策略往往增加了种群的多样性。没有这样的修改，像高概率的解就会在种群中变得越来越显著。这种策略使得低适宜度指数的解更可能发生突变，这就使得它们有机会去改进自己。这也使得具有高适宜度指数的解更可能发生突变，这就使得它们更有机会提升自己，使自己比现在更加的优秀。注意，我们使用了精英策略来保留栖息地的特征，该栖息地在BBO算法过程中有最好的解决方案，所以即使突变毁掉了适宜度指数，我们已经保留了它并且如果需要还能够再返回。所以，我们使用突变（一种高风险的过程）在不好的解决方案和好的解决方案。那些普通的解，都希望是已经改进了的，并且因此我们不在对它们进行突变处理(尽管依然存在突变的可能，除了那个最适宜的解)。
这种应用突变机理依然是很成问题的，就像遗传算法中的突变。在我们的传感器选择问题（将在第4部分讨论）中，如果一个解决方案被选择进行突变，然后我们只是简单的使用新的解来任意的替代在这些解中被挑选的传感器。在本文中，我们还没有探索可供选择的进化策略，但是推断起来，那些在遗传算法中可实现的突变策略都可以应用在BBO中。
C. BBO定义和算法

在这部分中，我们提供了一些定义作为规范BBO算法的第一步。我们也提供了该算法的轮廓。我们使用R代表实数集，Z代表整数集，代表了空集。
定义1：栖息地H∈ 是m维的整数向量，它代表了某问题的可行解。:
定义2：适宜度指标变量SIV∈C是一个整数，该整数在栖息地被容许。C∈  是在该栖息地所容许的所有整数。
SIV∈C的要求被称为约束条件。进一步讲，H∈ 的要求也是约束条件。
定义3：栖息地适宜度指标HSI：H→R是一种衡量指标，用来衡量被栖息地代表的解决方案的好坏。
注意：在大多数的基于种群的优化算法中，HSI被称为适应度。
定义4：生态系统  是n个栖息地的组合。
生态系统的大小n是恒定的。未来的工作将会允许大小可变的生态系统，比如一些带气味的遗传算法是允许群体大小可变。
定义5：迁入率λ(HSI)：R→R是一个HSI的单调非递增的函数。  正比于适宜度指标变量SIVs从邻近栖息地迁移到栖息地  的可能性。
定义6：迁出率μ(HSI)：R→R是一个HIS的单调非递减的函数。  正比于适宜度指标变量SIVs从栖息地  迁移到邻近栖息地的可能性。
实际上，我们假设λ和μ和相同的最大值成线性关系。然而，这些假设仅仅是为了使数学上计算方便，并且当这些假设放宽的时候或许能得到更好的表现。
定义7：栖息地修正Ω(  , )：  →H是盖然性的操作该操作是根据生态系统  来自适应的调整栖息地H。H被修正的概率正比于它的迁入率λ，来自于  的修正来源概率正比于迁出率  。
栖息地修正可以按下面的方式轻松地描述出来。
选择概率正比于  的栖息地
如果  被选择
For j=1 to n
选择概率正比于  的栖息地
如果被选择
从  中随机的选择一个适宜度指数变量 σ
用σ代替  中一个随机的适宜度指数变量
End
End
End
从这个算法，我们注意到精英主义可以通过对p最好的栖息地设定其λ=0来实现，此处p是自然选择的精英参数。同时也注意到Ω的设定保证了修正后的栖息地H也满足适宜度指数变量的约束条件。
定义8：突变M( ，μ)：H→H是一种感染性的操作，它是根据该栖息地已经存在的先验概率随机地修改该栖息地的适宜度指标变量。
现存的栖息地概率计算是从λ和μ计算得到的，已经在第二部分讨论过了。
突变过程可以如下面描述：
For j=1 to m
使用  和  来计算概率
选择正比于  的栖息地  ( )的适宜度指标变量SIV
If ( )被选择
使用随机产生的SIV来代替  ( )
End
End
随着栖息地的修正，精英策略可以通过对p最好的栖息地设定其突变选择概率  =0来实现。从上面的定义可知，突变必须被约束导致一个HIS满足SIV的约束集。
定义9：生态系统转换函数Ψ=(m,n,λ,μ,Ω,M): →  是一个6元的数组用来使生态系统在一次次的迭代的过程中从得到优化。
生态系统转换函数可以被写作：
换句话说，生态系统转换函数开始于计算每个栖息地的迁入迁出率。然后，栖息地根据每个栖息地逐个进行修正，紧接着是HIS的重新计算。最后，突变再执行，然后每个栖息地再次进行HIS的重新计算。
定义10：BBO算法BBO=(Ｉ，Ψ，T)是一个三元的，能够对优化问题提出解决方案。Ｉ：→{  ， }是一个初始化栖息地生态系统并且计算其相应的HIS的函数。Ψ是提前就定义好的生态系统转换函数，并且T：Hn→{true，false}是一个终止条件。
Ｉ可以通过随机函数产生器、优化问题的启发式解和一些其他的问题相关的程序来实现。T可以通过Ψ的迭代次数来决定，或者HSI最高的栖息地，或者其他一些问题相关的准则。BBO算法描述如下。
I
While not T
Ψ
End
BBO算法可以不拘泥于形式的描述为下面的算法。
初始化BBO的参数。这一步意味着要得到一种组织问题解决方案的SIVs和栖息地（可以参照定义1和2）的方法，该过程要依据具体问题而定。我们也要初始化物种种群数量的最大值，最大的迁移率E和I（见图2），最大的突变率（见公式14）和精英策略参数（见第三部分A中的最后一段）。注意到最大的物种种群数量和迁移率最大值都是相对量。也就是说，如果他们都按照相同比例的变化，那么BBO算法的行为结果是不会变的。这是因为如果Ε，Ｉ和改变的话，那么迁移率μ，λ，和物种数量S就会在每个解决方案中按照一样的相对量发生改变。
初始化一组随机地栖息地，每个栖息地都是和给定问题的解决方案相一致的。这就是在定义10中介绍的I操作的实现过程。
对每个栖息地，编码物种数量S的HIS，迁入率λ和迁出率μ（图2和定义5、6）。
就像第三部分A中描述的，盖然地利用迁入迁出来修正每个非精英的栖息地，然后重新计算每个HSI（看定义7）。
对每个栖息地，利用公式2来更新它的物种数量的概率。然后，根据第三部分B中描述的那样依据它的概率来突变每个非精英的栖息地，并且重新计算每个HIS（见定义8）。
回到第3步进入下一次的迭代。该循环可以在以下情况结束：达到预先设定的迭代次数，一个可以接受的问题解决方案被找到。这是定义10中所描述的T操作的实现过程。
注意到在没个栖息地被修正以后（第2,4和5步），它作为问题解决方案的可行性就会被证实。如果它不代表一种可行的解，那么为了使它能映射到可行的解中就需要一些方法来实现。
D. BBO和其它一些基于种群的优化算法之间的区别

在这一部分，我们指出BBO的一些特异性。首先，我们注意到虽然BBO是一种基于种群的优化算法但它没有涉及繁殖和子代。这明显地是它区别于像遗传算法中的繁殖策略和进化策略的地方。
BBO也很明显地区别于蚁群算法ACO，因为蚁群算法每次迭代都会产生一些新的解决方案。BBO，另一方面，依据迁移概率地更新了这些解决方案，使得从一次迭代到下一次迭代都保留了它的解集。
BBO具有和PSO和DE这样的算法大部分共同的策略。在这些方法中，解从一次迭代到下一次迭代都被保持了下来，但是每种解决方案都能够从它的邻近方案得到学习，并且随着算法的进程自我更新。PSO表现为把每种解决方案作为空间中的一个点，它把每种解决方案随时间的改变作为速度矢量。然而，PSO中解决方案不是直接改变的。它更确切地说是速度矢量的改变，并且这种间接地改变导致了位置（解决方案）的改变。DE是直接改变了它的解决方案，但是在特殊的DE解决方案中改变是根据不同DE解决方案的差异来的。而且，DE不是生物方式驱动的。BBO同PSO和DE相比，在于BBO的解决方案是通过从其他解决方案（岛）迁移直接改变的。换句话说，BBO的解决方案直接地和其他解决方案分享自己的属性。
就是这些在BBO和其他基于种群的优化算法之间的差异或许可以证明它的长处。一些开放性的调查问题：比如这些差异是如何使得BBO的表现特性和其他基于种群的优化算法表现不同呢？这些差异不同对于诸如到底什么更适合BBO算法的问题到底说明了什么？本文主要代表了关于BBO最初的探索，但是把这些问题留给了将来的工作。

IV.航空器发动机健康评估

在这部分，我们回顾一下对于航空器发动机健康评估的传感器选择问题，这是为了我们把它用作BBO理论的检测问题。
图片3，展示了一个航空涡轮风扇式发动机的原理图

[9]

。进风口送风到风扇。空气离开风扇后被分成两股气流，一股穿过发动机核心，而另一股穿过了旁路通道。风扇是由低压涡轮机驱动的。空气穿过发动机核心后进入一个由高压涡轮机驱动的压缩机。燃料注入并且在燃烧室里激发，产生高温气体来驱动涡轮机。这两股气流在扩增器管里面汇合，此处额外燃料的加入进一步提升了温度。空气以非常高的速度从喷嘴（有一个可调节的横截面区域）喷出并且因此产生推动力。
在本文中使用的这个发动机的仿真叫做模块化的航空推进系统仿真 (MAPSS)

[9]

。并且是使用的matlab 仿真系统。控制器的更新率是50HZ。在MAPSS中使用的三个状态变量是低压风轮转速，高压风轮转速和平均热节金属温度。涡轮风扇发动机的离散时不变方程模型可以概括为如下：

此处，k是时间索引，x是三维的状态向量，u是三维的控制向量，p是十维的健康参数向量，y是测量向量。测量包括我们用来测量发动机的传感器输出。健康参数的变化随时间是很慢得。在测量间隔内它们的差异接近于0可以看做是噪声wp(k)。叫做噪声的wp(k)代表了系统模型的不精确。而e(k)代表了测量噪声。状态，控制，健康参数和测量在

[10]

中做了总结，和它们的数值。可以使用卡尔曼滤波器和公式16来估计状态向量x和健康参数p。卡尔曼滤波器的好处之一不仅仅是它估计出了x和p，而且它提供了估计不确定性的测量。估计不确定性是由误差协方差和带来的，这是卡尔曼滤波器递归过程计算的一部分。
至此，我们有三个状态和十个健康参数，协方差的和就是一个13*13的矩阵。对角线元素给出了状态和健康参数估算误差的协方差。前三个对角线元素给出了状态估算误差的协方差，而后面的十个对角线元素给出了健康参数估算误差的协方差。在本文中我们考虑的问题是，我们仅仅是对健康参数估算误差感兴趣，所以我们最要是关心对角元素Σ(4,4)，Σ(5,5)，…Σ(13,13)。
我们可以选择使用哪个传感器来做健康评估过程。如果想，我们也可以复制传感器。我们有11个不同的传感器如[10]中描述的那样，但是我们可以在同一个位置使用多个传感器如果需要的话。比如，我们可以使用2个或3个完全相同的传感器来测量风扇出口压力，从而有效的降低了我们测量中的信号噪声比，或者我们可以完全的减少其中一个传感器用来达到经济的节省。使用更多的传感器将导致误差平方和减少，也就是说我们的健康评估会更好。但是，有一个回报降低点。使用越多的传感器将花费更多的钱。并且为了得到少量的健康评估而消耗大量的费用是不值得的。因此，对于该健康评估问题有一个最优化的准则，可以被写作：

和С 是为了实现归一化而选择的参考值。是我们使用所有11个传感器而没有副本的时候协方差的结果，而С 是装备11个传感器是的经济花费。α是一个比例系数，它用来调节经济花费相对于健康评价精度的最缺性。对于这个健康评价问题来说J就是目标函数。这种传感器的选择问题首相是使用遗传算法的时候提出来的

[12]

。当BBO被用来解决该问题，J其实是叫做HSI。选择什么传感器来使J最小化是一个最优化问题。回想一下，我们有11 个传感器变量。该问题中我们主要有一些典型的约束，比如我们总共能用的传感器数量Ｎ，相同的传感器不能使用超过Ｍ次。如果Ｎ＝12并且Ｍ＝3.那么我么有下面的例子：
１,２,３,４,４,５，６,７,８,８,８,１１
－合理组合（没有传感器使用超过３次）
１,２,３,４,４,４,４,５,６,７，８,９
——不合理的组合（传感器４被使用超过了３次）
一般而言，我们想从Ｋ（在本文中Ｋ＝１１）种不同的传感器中总共选择Ｎ种，其中每个传感器不能多于Ｍ次。（其中K,N,M都是根据具体问题而定的）。所有的可能组合可以根据下面的方法得到。首先，我们有个多项式 (x)如下：

选择N个传感器的所有组合数正好等于

。这可以根据多项式定理得到[13]。
作为一个简单地例子，假设我们想从三种各不相同的传感器中选择四个，同时每种传感器不能超过两个。可能的传感器组合在公式19中展示出来：

可以看出总共有六个可能的组合，相关的多项式如公式20表示：

四次项的系数在多项式中等于6；这就是说在这个问题中有六种不同的组合。

V.仿真结果

在这一部分，我们主要看 BBO 的表现和其它基于种群优化算法的比较。首先，我们比较对于一组共通地用于基本函数的表现，然后，比较涡轮发动机传感器选择问题。
A.测试函数

为了探究BBO算法的好处，我们把它的性能和其他7中其他的基于种群的优化算法就基本测试函数问题上做了大量的对照。ACO

【14
】

-【17
】

是一种基于蚂蚁信息素沉积物的算法。DE

【17
】

-
【

19
】

是利用两个解决方案中的不同来盖然的产生第三个解决方案的一个简单算法。ES

[20]-[22]

这种算法通常对复制和变异两种操作是同等重要的对待，这就允许两个父母得到一批子代。GA

【8
】【

20
】【

23
】

是基于生物进化理论中自然选择的一种方法。PBIL

[
24

]
[25]

是遗传算法的一种，它主要是维持了种群的统计特性而不是直接的保持了种群。PSO

[
17

]
[26]-[28]

是基于鸟群、鱼群以及其他生物群落的行为。学习型遗传算法（SGA）

[
29

]

是使用每代中最好的个体做交叉的遗传算法。我们最小化的基准函数是用来测试文章中提到的各种优化算法对比性能的代表函数。其中一些是多峰的，这就意味着这个函数有许多局部最小值。一些是不可分离的，意味着该函数不能写作各个变量的和函数。有一些是常规的，意味着它们在作用域里的每一点都是可微的。在本研究中每个函数都有二十个自变量。函数都罗列在表I中。关于这些函数跟多的信息包括它们的作用域可以在文章[8][30]和[31]中找到。
这些基本测试函数都有是在MATLAB环境中用各种优化算法的整数形式实现的。每个基本测试函数的精度或粒度是0.1，除了四次函数。由于四次函数的每一维的作用域只有±1.28，所以它的粒度是0.01。
为了得到合理的性能指标，我们对每种优化算法都进行了粗调，但是并没有做特别的努力去微调算法。对于ACO，我们使用了下面的参数：初始信息素值是

=10^-6，信息素更新常数Q=20，探测常数

=1，全局信息素衰减比

=0.9，局部信息素衰减比

0.5，信息素灵敏性

并且可见性灵敏度

。对于
BBO，我们设置了如下参数：栖息地修正概率=1，迁入概率介于[0,1]之间，概率的数值积分的步长为1，迁入迁出率的最大值为1，变异率为0.（对于BBO来说，变异最要是对小规模种群有益的。）对于DE来说，我们用了一个权重系数
F=0.5并且交叉常数CR=0.5。对于ES，我们使每一代都产生

个子代，并且偏差

对于改变的解决方案。对于GA，我们使用了轮盘赌选择法，单个点的交叉概率是1，变异率是0.01.对于PBIL，我们使用的学习率是0.05 ，1个好的的种群数，0个不好的种群数用来更新每一代的概率向量，精英参数为1，概率向量变异率是0.对于PSO来说，我们只使用了全局学习率（没有局部学习率），惯性常数是0.3，认知常数是1，粒子相互作用的社会常数是1.对于SGA，我们设定交叉概率为1，变异率为0.01.

每种算法都有50个种群，精英参数为2（除非在前面的段落中有说明），并且只跑50代。我们运行了100次蒙特卡洛模拟程序针对每一个基准测试函数和优化算法。表二和表三分别展示了模拟的效果。表二表示的是每种优化算法平均最小的发现，是100次蒙特卡洛运行后的平均结果。而表三表示的是100次蒙特卡洛模拟中每种算法的绝对最小发现。表二表示的是每种优化算法的平均性能，而表三表示的是每种算法的最优表现。注意表中的线性化是基于不同的比例的，所以在两个表中的数值是不能比较的。
从表二中，我们可以看到BBO和SGA是7种方法在14种测试基准函数中平均性能表现的最好的。表三可以得到：SGA是这7种方法在14中测试基准函数中表现的最好的，当多次运行它在寻找函数极值方面表现出来是最有效率的。BBO在前四个基本函数中是表现的第二有效率的。而ACO在三个基本函数中是表现最好的。
对基本函数测试结果必须持有怀疑的态度。首先，我们在这一部分并没有在整定优化算法上下功夫。在优化算法中，不同的整定参数值会对它们的性能产生显著的影响。其次，现实世界中的优化问题可能和基准测试函数没有太大的联系。第三，当等级标准和问题设置改变了之后，测试函数可能会得到不同的结论。在这一部分，我们验证的最好结果和平均结果是在某个特定的种群数量和特定的迭代次数下的。然而，我们可能得到不同的结论，如果我们改变迭代次数的限制，或者看一看它到底需要多少次迭代才能达到某个值，或者我们改变种群的数量。尽管这么多警告，这些测试结果展示在这里说明BBO是有希望的，并且已经表明这个新的范式很可能会在过剩的基于种群的算法中找到一个新的方向或有利可图的市场。
这八种优化算法对计算的需求是相似的。我们选择这些优化算法应用在这14种测试函数中的平均计算时间在这部分进行一下讨论。结果在表二中展示出来。PBIL是最快的优化算法。BBO是这8种优化算法中排名第五的。然而，需要注意的是：在现实世界应用的绝大部分中，适宜度函数评价是基于种群的算法中最昂贵的部分。
B.传感器选择结果

传感器的选择问题可以用基于种群的优化算法来处理。种群数目可以由整数向量来组成，向量中的每个元素都是和传感器的号码相对应。种群成员的适宜度或者HSI由公式（17）给出，其中

。如果在优化过程中产生了无效的传感器组合，由于有某个型号的传感器太多了，然后，我们就随便选择一个强制适宜的传感器来代替重复出现的传感器类型。
我们假定这里总共使用20个传感器（它们是从11种不同的传感器中选出来的）并且每种传感器不能多于4个。传感器组合的数量从多项式（21）中20次方的系数中选择出来：

根据二项式定理，我们知道这个系数是4755070。这就是所有的传感器组合数，必须全部都寻找一遍，这样才能找到使公式（17）中J的最小值。为了计算每个组合的J，我们需要解决针对该组合的求和。为了解决求和，我们需要解决离散的Riccati代数方程

[
11

]

。这可以使用MATLAB提供的控制系统工具箱中的DARE函数来解决。有13个状态（包括三个最初的状态加上十个健康参数）和20种测量值的DARE解决方案需要花费0.02s在公认的过时的1.2GHz的个人电脑上。所以，为了搜索所有者3755070种传感器组合，我们需要CPU工作21个小时。需要注意到，传感器组合的花费最小值以及它的花费都将被独立的计算，因为MATLAB的DARE计算是数值的。21小时的CPU运作时间是不合理的如果它只是被运行一次。然而，如果它被运行很多次（比如为了20个传感器，或则19个传感器或者21个传感器）或者当问题的不同方面发生了改变（比如信噪比、系统操作点等）它就需要被重复的运行好多次，然后CPU的工作时间很快就变得不切实际。代替21个小时的强力搜索，我们可以使用计算智能来找到次最优的传感器组合。我们实现了基于种群的优化算法来搜寻最好的传感器组合。我们使用的这些算法和在第四部分A中使用的算法是一样的。对于BBO，我们使用的是第三部分C中给出的。对于每种算法，我们采用的种群大小都是50，迭代数是100，精英个数是2。每运行一种优化算法需要4802次DARE评估，相关的穷举搜索大约计算保留在99.87％.

表4展示了优化算法在传感器选择问题上的结果。我们可以看出，BBO无论是平均表现水平还是最好的性能指标都表现的最好。
图片4.展示的是在种群数量为20的情况下，有没有基于概率的突变对于BBO寻优算法的结果的影响。图片展示了每种方法在平均100次的蒙特卡洛模拟下的结果。我们可以得出，不同方法的性能进行了对比，但是具有基于概率的突变的BBO算法比没有突变的算法性能明显更好。注意到我们在图4中使用的种群数理非常的小。对于种群数理比较大的情况，突变是不利的。但是当小种群概率下的突变有利于增加物种多样性从而增加好的解决方案的改变。

这些模拟和仿真结果不能一味着BBO就比其他基于种群的优化算法就好。这种一般性的概述需要做一个极端的简化，特别是针对没有免费午餐定律

[32
]

。然而，在本文中展示的结果表现出BBO的确提供了比其他大多数我们针对这几个特殊的基础函数测试的优化算法都好的性能。这些结果表明至少BBO是比其他基于种群的优化算法更有竞争力的，并且可以为为特殊的问题提供一个解决工具。
VI.结论

我们已经展示了生物地理学，这种研究物种在地理环境中的分布的学问，可以被用于导出一种优化算法。在该算法家族中一个新的成员被叫做BBO。我们已经将BBO应用到基础函数的测试以及传感器的悬着问题中，并且结果表明它展示出的性能和其他基于种群的优化算法是同样的。我们不能一贯的人为BBO就比其他优化算法好，反之亦然，我们要意识到没有免费的午餐理论。然而，在未来的工作中去改进BBO相对于其他算法在具有特定特种的的问题中的性能是可能的。BBO在基准测试函数和传感器选择问题中表现出来的优异性能可以证明BBO理论可以成功的应用于实际问题中。自然地这篇文章是初步的，然而，却为进一步的研究打开了可能性。
证明第二部分冠以矩阵

的特征值的猜想会非常有意思的。矩阵

所具有的特殊结构显然在本文中并没有出现。

的性能会对BBO各方面的性能都有影响：稳定性、收敛性、平衡性等。
另一个重要的外延工作就是讲BBO应用到动态适应景观的优化问题中。这可以通过使用优化滤波器来评估解决方案的适应性，和在GAs中提到的建议是一样的。
探究只是在相似解决方案之间（临近的栖息地之间）进行物种信息分享的想法或许是富有成效的。物种很可能只是在和他们原来的栖息地附件相邻的岛屿之间进行迁移。这和GAs算法中放入笼龛（在这里，物种之间不存在竞争）中的概念是一样的。这也使我们想起生物岛的模型。
在图1中的生物物种模型的细节可以通过调整来提高优化的性能。我们使用了线性和对称的迁入和迁出曲线，但是或许其他类型的曲线或许在特定条件下回得到更好的性能。另外，它可以认为一个栖息地必须有一个最小非零的适宜度指数为的是支持所有的物种，这就使得物种数量下界比0要大。
我们制定的BBO用来优化离散变量的函数。如果可以通过改进BBO算法使它可以直接的优化连续变量的函数，那么这种改进是有价值的。
我们已经看到BBO和其他基于种群的方法有许多共性的特征。这些联系将进一步去探索。究竟在什么情况下，BBO才能和其他这些方法一样呢？
有个问题在本文没有被探究，那就是一个个体的复制值像形如三角函数的年龄一样。复制值在年轻的时候非常小（由于婴儿死亡率），在生育年龄的时候非常高，当老了以后又变低了（由于生育能力的丧失）。同样对于物种也是一样的。一个年轻的物种适应它的环境的能力很低，所以通过进化为新物种的概率就低很多，中年的物种却足够成熟并且动态性能足够形成物种，但是老的物种却停滞不前。这将导致把年龄标准也整合进BBO算法，和在GAs算法中使用的一样。
生物地理学的其他方法和方面，可以激发出很多本文中建议的BBO算法的变体。生物地理学是如此的丰富，在这方面有太多的可能。例如，种群数量如何被整合进BBO？捕食者和被捕食者的关系如何被整合进BBO？特殊物种的迁移率演化如何被整合进BBO？种群的模型如何被整合进BBO

[36][37]

？我们注意到CPU使用时间是许多基于种群的优化算法实现的一个瓶颈。如果一个算法不能快速的收敛，它就不是切实可行的，因为它需要花费大量的时间来找到次优解。BBO似乎不需要不合理的计算量。在本文中提到的八种优化算法，BBO在速度方面是排名第五的。然而，找到加速BBO的有效机制是未来研究的一项重要内容。例如，或许先验知识可以被整合到问题中来代替选择SIVs，这种方式可以使改进的解通常都比原始的解更好。
基于种群的优化算法的以及和计算量相关的另一个瓶颈就是产生不可行解的问题。本文中提到的BBO算法，当产生了一个新的解时无法确定该解的可行性。适宜性可行性检查不得不等到新的解决方案全部完成以后。这个过程可能导致产生许多不可行解并且会减慢大大地减慢算法的速度。我们得出这样的结论：对于未来的研究中相当重要的一个领域就是找到如何在解决方案产生之初就能够确保其可行性的机制。例如，或许知识可以被整合进来代替选择SIVs的方式这样或许可以保证改进的解都是可行的。需要注意的是一般来讲这种建议同样也适用于其他基于种群的优化算法。本文已经提出了一个新的优化工具并且它很可能被应用到许多不同的问题中。人类生活和工程中的大多数问题都可以看做是优化问题。本文介绍的新的优化算法开辟了提高生产力研究的有希望的大道。
参考文献：

[1]A. Wallace, The Geographical Distribution of Animals (Two Volumes).Boston, MA: Adamant Media Corporation, 2005.
[2]C. Darwin, The Origin of Species. New York: Gramercy, 1995.
[3]R. MacArthur and E. Wilson, The Theory of Biogeography. Princeton, NJ: Princeton Univ. Press, 1967.
[4]I. Hanski and M. Gilpin, Metapopulation Biology. New York: Academic, 1997.
[5]T. Wesche, G. Goertler, and W. Hubert, “Modified habitat suitability index model for brown trout in southeastern Wyoming,” North Amer.J. Fisheries Manage, vol. 7, pp. 232–237, 1987.
[6]A. Hastings and K. Higgins, “Persistence of transients in spatially structured models,” Science, vol. 263, pp. 1133–1136, 1994.
[7]H. Muhlenbein and D. Schlierkamp-Voosen, “Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization,” Evol. Comput, vol. 1, pp. 25–49, 1993.
[8]T. Back, Evolutionary Algorithms in Theory and Practice. Oxford, U.K.: Oxford Univ. Press, 1996.
[9]K. Parker and K. Melcher, “The modular aero-propulsion systems simulation MAPSS users’ guide,” NASA, Tech. Memo. 2004-212968, 004.
[10]D. Simon and D. L. Simon, “Kalman filter constraint switching for turbofan ngine health estimation,” Eur. J.Control, vol. 12, pp. 331–343, May 2006.
[11]D. Simon, Optimal State Estimation. New York: Wiley, 2006.
[12]R. Mushini and D. Simon, “On optimization of sensor selection for aircraft gas turbine engines,” in Proc. Int. Conf. Syst. Eng., Las Vegas, NV, Aug. 2005, pp. 9–14.
[13]C. Chuan-Chong and K. Khee-Meng, Principles and Techniques in Combinatorics. Singapore: World Scientific, 1992.
[14]M. Dorigo and T. Stutzle, Ant Colony Optimization. Cambridge, MA: MIT Press, 2004.
[15]M. Dorigo, L. Gambardella, M. Middendorf, and T. Stutzle, Eds., “Special section on ‘ant colony optimization’,” IEEE Trans. Evol. Comput, vol. 6, no. 4, pp. 317–365, Aug. 2002.
[16]C. Blum, “Ant colony optimization: Introduction and recent trends,” Phys. Life Reviews, vol. 2, pp. 353–373, 2005.
[17]G. Onwubolu and B. Babu, New Optimization Techniques in Engineering. Berlin, Germany: Springer-Verlag, 2004.
[18]K. Price and R. Storn, “Differential evolution,” Dr. Dobb’s Journal, vol. 22, pp. 18–20, 22, 24, 78, Apr. 1997.
[19]R. Storn, “System design by constraint adaptation and differential evolution,” IEEE Trans. Evol. Comput, vol. 3, pp. 22–34, Apr. 1999.
[20]Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer, 1992.
[21]H. Beyer, The Theory of Evolution Strategies. New York: Springer, 2001.
[22]E. Mezura-Montes and C. Coello, “A simple multimembered evolution strategy to solve constrained optimization problems,” IEEE Trans. Evol. Comput, vol. 9, pp. 1–17, Feb. 2005.
[23]D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
[24]I. Parmee, Evolutionary and Adaptive Computing in Engineering Design. New York: Springer, 2001.
[25]D. Dasgupta and Z. Michalewicz, Eds., Evolutionary Algorithms in Engineering Applications. New York: Springer, 2001.
[26]R. Eberhart, Y. Shi, and J. Kennedy, Swarm Intelligence. San Mateo, CA: Morgan Kaufmann, 2001.
[27]R. Eberhart and Y. Shi, “Special issue on particle swarm optimization,” IEEE Trans. Evol. Comput, vol. 8, no. 3, pp. 201–228, Jun. 2004.
[28]M. Clerc, Particle Swarm Optimization. Amsterdam, The Netherlands: ISTE Publishing, 2006.
[29]W. Khatib and P. Fleming, “The stud GA: A mini revolution?,” in Parallel Problem Solving from Nature, A. Eiben, T. Back, M. Schoenauer, and H. Schwefel, Eds. New York: Springer, 1998.
[30]X. Yao, Y. Liu, and G. Lin, “Evolutionary programming made faster,” IEEE Trans. Evol. Comput, vol. 3, pp. 82–102, Jul. 1999.
[31]Z. Cai and Y. Wang, “A multiobjective optimization-based evolutionary algorithm for constrained optimization,” IEEE Trans. Evol. Comput., vol. 10, pp. 658–675, Dec. 2006.
[32]Y. Ho and D. Pepyne, “Simple explanation of the no-free-lunch theorem and its implications,” J. Opt. Theory Appl., vol. 155, pp. 549–570, 2002.
[33]P. Stroud, “Kalman-extended genetic algorithm for search in nonstationary environments with noisy fitness evaluations,” IEEE Trans. Evol. Comput., vol. 5, pp. 66–77, 2001.
[34]S. Gustafson and E. Burke, “Speciating island model: An alternative parallel evolutionary algorithm,” Parallel and Distributed Computing, vol. 66, pp. 1025–1036, 2006.
[35]Y. Zhu, Z. Yang, and J. Song, “A genetic algorithm with age and sexual features,” in Proc. Int. Conf. Intell. Comput, 2006, pp. 634–640.
[36]H. Caswell, Matrix Population Models. Sunderland, MA: Sinauer Associates, 1989.
[37]C. Li and S. Schreiber, “On dispersal and population growth for multistate matrix models,” Linear Algebra and Its Applications, vol. 418, pp. 900–912, 2006.
[38]D. Bernstein, “Optimization r us,” IEEE Control Systems Mag., vol. 26, pp. 6–7, 2006.
[39]B. Noble and J. Daniel, Applied Linear Algebra. Englewood Cliffs, NJ: Prentice-Hall, 1987.

Dan Simon：在坦佩的亚利桑那州立大学获得了数学学位，在西雅图的华盛顿大学获得硕士学位，在锡拉丘兹纽约的锡拉丘兹大学获得博士学位都是在电气工程专业。他在工业中工作了14年，像波音、天合和几个较小的公司。他的工业经验包括在航空航天、汽车、农业、GPS、生物医学、过程控制和软件领域。1999年，他从产业转移到学术界，他现在是克里夫兰州立大学电子与计算机工程系的一个副教授。他的教学和研究包括嵌入式系统、控制系统和计算机智能。它已经出版了超过60多篇会议和期刊论文并且他是最优化状态估计的作者。

手稿收于2007 年3月28日；于2007年9月14日修订；2008年3月18日首次出版，当前版本发布于 2008年 12月2日。
作者是美国克利夫兰州立大学，电气工程系，OH44115 USA (Email地址:d.j.dimon@csuohio.edu)

		自动登录	找回密码
密码			立即注册

生物地理学优化算法及原理（Biogeography-Based ...

本帖子中包含更多资源