作者：张毅
本文针对图像多阈值分割问题，引入多源迁移算子和创建一种新型的动态变异算子，提高了算法的运算效率，使算法能够快速收敛到全局最优解，并且将这种改进的生物地理学算法( IBBO)应用到基于一维灰度直方图的最大熵多阈值分割中，以便获得一种高效的适用于多阈值分割的优化算法。
1 基本生物地理学算法
在BBO中，每个个体称为一个栖息地，每个栖息地用适宜度指数( HSI)衡量其好坏，栖息地的HSI与生物多样性成正比。描述栖息地适于居住程度的特征变量组成的D维实数向量称为适宜度向量（SIV，公式中用vsIV表示）。栖息地之间通过迁移和突变进行物种之间信息的交换与共享，提高物种多样性。
在生物地理学算法中，每个栖息地的迁入率和迁出率是该栖息地物种数量的函数，用于栖息地之间信息的分享。迁入率λi和迁出率μi的算式为
式中：I，E分别表示最大迁入率和最大迁出率；Si表示当前种群数；Smax表示最大种群数。
BBO包含两大基本的操作即迁移和变异。迁移操作通过分享栖息地之间的特征值改变选中的栖息地的SIV。迁移操作可以表示为
式中：Hi是准备迁入的栖息地：He是准备迁出的栖息地。迁移操作的伪代码如算法1所示。其中，X表示栖息地的数量，rand(0，1)表示均匀分布在（0.1 ）之间的随机实数。
变异操作模拟了栖息地生态环境的突变，用于增加种群的多样性。在BBO算法中，栖息地Hi中的一个SIV被选中用随机生成的SIV代替，其变异概率m，与它的物种数量的先验概率Pi有关。变异概率的算式为
式中：mmax是自定义参数，代表最大变异概率；Pmax=max Pi。变异算子伪代码如算法2所示。
2 改进的生物地理学优化算法
2.1多源迁移算子
BBO具有较好的开采能力，是因为迁移算子使得BBO能够在栖息地之间分享信息。然而，从式(3)中可以看出，这个算子仅仅通过直接复制原有的特征来生成新解，不能从未开采的搜索空间中生成新解，导致搜索过程可能陷入局部最优，造成BBO算法缺乏探索能力。为了增强算法的探索能力，引入了多源迁移算子，其表示为
Hi( VSIV)←He（VSIV）+Φi,SIV(He(VSIV)- Hr(VSIV))(5)式中：Hi是选定的要进行迁移的栖息地；He是随机选择的一个HSI较高的栖息地；Hi是一个随机选择的栖息地，且r，i，e三者应互不相等；Φi,SIV是服从[ -1，1]之间均匀分布的随机数。多源迁移算子的伪代码如算法3所示，通过多达4个栖息地（Hi，He，Hr，Hs）的特征来组成新的候选解Vi。
多源迁移算子用相对较好的栖息地作为基础，通过随机选择的栖息地Hr产生对称干扰，带来更多新的信息，借此开发未探索到的可行空间，扩大搜索范围。如果条件ran,d(O，1)<μe没有满足，则说明选择的He不够好，须从其他的栖息地迁入特征。栖息地He的作用在于增强算法的开采能力，而其他两个从当前种群中随机选取的栖息地Hr和Hs的作用在于强调算法的探索能力，如此使算法在开采和探索之间取得适当的平衡。
2.2动态变异算子
在标准BBO算法中，用随机生成的一个特征值替换选中的要进行变异的栖息地特征值，以此提供更多的搜索目标，但是这种随机的变异算子会导致BBO收敛速度慢。为此，提出了一种动态变异算子，在原特征值的基础上，增加一个变异因子，随着迭代次数的改变动态地改变变异的幅度，使算法能够快速收敛到全局最优解。动态变异算子表示为
式中：Hk（VSIVd）表示第k个候选解的第d个特征值被选中进行变异操作；G表示当前种群的迭代次数；M表示最大迭代次数。候选解随迭代次数的增加逐渐收敛于全曷最优解附近，因此，使变异幅度随迭代次数的增加逐渐减小，避免出现偏离最优解太多的变异值，快
了算法的收敛速度。Sstep也是动态变化的，其取值范围为[1,4],其值随着迭代次数的增加逐渐减小。Sstep的值不仅保证了产生的变异的变化量不为零，而且也起到了动态调整的作用。Hk（VSIVD）在多阈值分割中表示为解向量中的第d个阈值分量，随着d的增加，Hk（vSIVD）也增大。式(6)产生的变化量随着d的增大而减小，可以有效地平衡各个特征值的变化。
2.3贪婪选择算子
在标准BBO算法中，采用精英保留策略保留每一代群体中最优的解。一般选择保留每一代群体中前两个最优解，用以替换下一代群体中最差的两个解。本采用贪婪选择策略保留每一代的最优解，即将经过迁移和变异操作产生的新一代解集与上一代解集进行比较，若新解优于旧解，就用新解替代旧解；否则，保留旧解，以此加快算法的收敛速度。贪婪选择算子伪代码表示为算法4，其中，N代表种群总数，vadue指解的适宜度值( HSI)。
最大熵公式为
使得式(9)取得最大值的一组阈值[x1，x2，…，xD]即为最优的阈值向量。为了取得最优的阈值向量，必须对解空间进行遍历搜索（穷举搜索），但是这种方法计算量非常大，浪费时间和资源。为此，需要引入智能优化算法。
3.2 IBBO算法应用到图像多阈值分割中
假设对图像进行D阈值分割，则解向量为X=[x1，x2，…，xD]。以最大熵法作为分割准则，在解空间0～255灰度级之间采用IBBO算法进行优化选择，使得式(9)取得最大值的解向量即为最优解。将式(9)作为衡量各个解的HSI的目标函数，候选解相当于BBO算法中的栖息地，解向量中的阈值相当于栖息地的特征向量。基于IBBO算法的图像多阈值分割法的
步骤如下所述：
1)读入图片，建立一维直方图，初始化参数，设最大迭代次数为M，种群数量为N，阈值个数为D；
2)随机生成初始化种群X，X为N行D列矩阵，并对每一个解的分量由小到大排序；
3)用式(9)评估每个栖息地Xi的HSI，j=1，…，N，按照HSI值的降序对Xi排序；
4)根据式(1)和式(2)计算迁入率、迁出率；
5)执行算法3多源迁移操作；
6)根据式(6)执行动态变异操作；
7)用式(9)评估每个栖息地Xi的HSI，j=1，…，N;
8)执行算法4贪婪选择算子，保留较优的解，并按照HSI值的降序对Xj排序；
9)若没有达到停止准则，转到4），否则，循环停止，获得最优阈值向量；
10)用求得的最优阈值向量进行图像分割，输出分割后的图像。
4 实验结果与分析
为了检验IBBO算法的有效性，将IBBO算法与最大熵分割法则结合，进行图像多阈值分割的实验。将实验结果与BBO算法、PSO算法的图像分割结果进行比较，并与穷举算法的运行速度比较。使用Cameraman. tif( 256×256)，Lena．png(512×512)两幅图片作为示例说
明。IBBO，BBO和PS0 3种算法分别独立运行30次，穷举算法运行1次。所有实验均在主频3. 10 GHz的CPU和内存为4 GB的PC上进行，采用Matlab R2014a编程语言实现。为了公平起见，BBO算法、PSO算法和IBBO算法的种群大小Ⅳ都设为50，最大迭代次数M也设置相同，为了满足不同阈值选择的需要，M随着阈值的增加而增加，表示为M =3 x2D+(D-l)×20。PSO算法参数设置如下：学习因子c，和c：均为2.1，惯性权重为0. 629 9。BBO和IBBO算法的参数设置相同：初始变异率为0.4，最大迁入率(，)为1，最大迁出率(E)为1。
用4种算法分别对图像进行2、3、4、5阈值搜索，搜索所得的最优阈值( OT)向量及其运行时间(time)如表1所示，其中，time指算法独立运行30次的平均时间，T指阈值数，Exh指穷举算法，VOT是指30次运行中使最大熵值最大的阈值向量。表2列出了3种算法运行30次获得最优值的均值( mean)、最小值(min)，以及成功率(SR)，SR是寻得最优解的次数与算法运行总次数之比，其中最优解的次数为获得的最大熵值等于穷举算法获得的最大熵值的次数。表1和表2中加黑的值均为较优的值。图1、图2分别显示Cameraman和Lena的原始图像及其用IBBO算法分割后的图像。
从表1可以看出，IBBO算法运行速度最快，其次是BBO算法，再次是PSO算法，穷举搜索算法运行最慢；并且随着阈值数的增加，4种算法运行的时间增加，这是因为随着阈值数的增加，寻优难度增加，需要的迭代次数增加。另外，因为穷举搜索算法的计算复杂度为O(/D)，所以耗费时间很长，但其得到的分割阈值一定是准确的。相比于BBO算法，IBBO算法更能够准确寻到最优阈值，这说明算法的改进是有效的。与PSO算法比，IBBO算法运行的时间少，这是由于在PSO算法中解向量的适宜度值计算及其比较通过循环语句实现；而在IBBO算法中先对解向量集中处理，再通过矩阵运算比较适宜度值；在Matlab运算环境中矩阵的运算速度快于基于循环的单个运算，所以IBBO算法的运算速度快于PSO算法。
从表2可以看出，对于图像Cameraman，IBBO算法在图像的2、3、4、5阈值分割中都能够准确地取得最优阈值，并且成功率都能够达到100%。其次是PSO算法．虽然能够获得最优解，但不是每一次都能成功获得最优解：BBO算法成功率非常低，在2阈值分割中成功率仅为47%．在3、4、5阈值分割中成功率甚至为0。这说明BBO算法的优化性能性远远劣于IBBO算法。对于图像Lena.IBBO算法和PSO算法对2、3、4阈值分割的成功率都达到100%，而对5阈值分割，PSO算法成功率约为96. 66%，这说明PSO算法在阈值数较大的情况下，搜索能力下降，劣于IBBO算法。另外，从均值和最小值（见表2的4和5两行）看出，IBBO算法优于PSO算法和BBO算法。
综上所述，基于改进的生物地理学算法寻优速度远远快于穷举算法，且快于BBO算法和PSO算法，稳定性好，应用于图像分割中能够得到较好的分割效果。这说明本文所做的改进是有效的。
5 总结
本文提出了一种改进的生物地理学算法，采用多源迁移算子、动态变异算子和不同的精英选择算子，增强了算法的全局搜索能力，提高了优化性能。并将改进的BBO算法应用于图像多阈值分割中，实验结果表明，基于改进的生物地理学算法的图像多阈值分割法分割速度快、稳定性好，能够取得较好的分割效果。
6摘要：为了增强生物地理学优化算法( BBO)在图像多阈值分割应用中的全局搜索能力，提高其优化性能，提出一种改进的生物地理学算法( IBBO)。首先，引入多源迁移算子，该算子能更好地从搜索空间中生成新特征值，有效提高种群的多样性；其次，创建一种新型的动态变异算子，该算子能够动态地改变变异幅度，提高算法运算效率，使算法快速收敛到全局最优解；随后，将原来的精英选择算子改为贪婪选择算子，即采用优胜劣汰的策略加快算法收敛速度；最后将其应用到基于最大熵的多阈值分割中 图像分割实验结果表明，IBBO算法运行速度远远快于穷举算法，优化性能优于标准BBO算法和PSO算法。
下一篇:返回列表
