在人类开发利用海洋的过程中,海底地形必须认真勘测。由于海洋环境变化多端,以及人类自身身体条件的限制,很多工作必须借助其他工具完成,水下潜器就是人类开发利用海洋的一种重要辅助工具。在水下潜器的诸多功能中,地形匹配系统主要用于控制导航和寻找、跟踪、记录目标,从而绘制精确的海底地形[1]。但由于图形匹配一直以来属于超密集型运算,匹配过程中的可靠性、及时稳定性以及可嵌入性便成为技术攻克的重点。
PSO即粒子群优化算法,是一种新兴的模仿鸟兽鱼虫种群行为的智能化搜索算法,所谓智能化指的是此种算法模拟种群个体间相互辅助相互制约关系来指导个体行为,最终寻找到空间中的最优点。粒子群优化算法的信息共享机制与遗传算法迥异,传统遗传算法中,染色共用信息,种群移动偏于匀速,而粒子群优化算法中,信息在粒子间单向流动,各粒子可基于其他粒子的“经验”改变搜索路径,因此,所有的粒子可能更快向最优点移动。
本文研究了PSO算法,为解决算法存在的早熟及易陷于局部最优解的问题,对PSO算法进行了改进,在此基础上,提出了基于改进PSO的水下潜器地形匹配算法,最后,进行了仿真实验。
1 PSO算法及其改进 1.1 PSO算法PSO算法流程如图 1所示,具体描述如下:
1)对学习因子c1c2、最大迭代次数Tmax等参数进行初始化,随机生成粒子的速度和位置,将当前位置赋值给粒子极值,将个体极值中的最优值赋值给全局极值。
2)计算所有粒子的适应度值,并和自身历史最优位置进行比较,如果优于历史最优值,则替换历史最优值,反之,则保留原历史最优值。将每个粒子的历史最优值与全局最优值进行比较,如果优于全局最优值,则替换全局最优值,反之,则保留原全局最优值。
3)根据公式1、2更新所有粒子当前时刻的速度
$\begin{array}{l} {v_{id}}\left( {k + 1} \right) = {v_{id}}\left( k \right) + {c_1}{r_1}\left( {pbes{t_i}\left( k \right) - {x_{id}}\left( k \right)} \right)\\ + {c_2}{r_2}\left( {gbes{t_g}\left( k \right) - {x_{id}}\left( k \right)} \right), \end{array}$ | (1) |
${x_{id}}\left( {k + 1} \right) = {x_{id}}\left( k \right) + {v_{id}}\left( {k + 1} \right)。$ | (2) |
4)判断是否满足终止条件,如果达到最小误差或者最大迭代次数Tmax,则输出最优解,停止迭代,反之,则执行步骤2。
1.2 改进的PSO算法惯性权重值较大时,PSO算法的全局搜索能力和搜索区域都较大,能够较快确定最优解位置的范围;惯性权重值较小时,PSO算法的局部搜索能力较大,能够对局部进行精细搜索。由于标准PSO算法易受到最大迭代次数Tmax的限制,对于无法确定迭代次数的问题,会导致误差的出现[2]。为此,本文提出了非线性惯性权重改进策略,惯性权重构造如公式3所示:
$\omega \left( t \right) = {\omega _{\min }} + \left( {{\omega _{\max }} - {\omega _{\min }}} \right)/{t^2},$ | (3) |
${V_{ij}}\left( {t + 1} \right) = \omega {V_{ij}}\left( t \right) + {c_1}{r_1}\left( {{p_{ij}} - {x_{ij}}} \right) + {c_2}{r_2}\left( {{p_{gj}} - {x_{ij}}} \right)。$ | (4) |
从标准的PSO算法的速度更新方程可知,如公式4所示,粒子只是利用了群体极值pg和个体极值pi信息,其他粒子信息没有得到有效利用。本文在改进的PSO算法引入信息共享机制,使粒子能够通过学习来丰富自身经验。
改进的PSO算法流程描述如下:
1)求得PSO算法的所有个体的适应度值,然后进行比较。
2)按照降序对适应度值进行排列。
3)选择种群中一半的优秀个体,求得位置向量平均值,根据公式5更新粒子速度。
$\begin{array}{l} \!\!\!\!\!\!\!\!{V_{ij}}\left( {t + 1} \right) = \omega {V_{ij}}\left( t \right) + {c_1}{r_1}\left( {{p_{ij}} - {x_{ij}}} \right) + {c_2}{r_2}\left( {{p_{gj}} - {x_{ij}}} \right)\\ \!\!\!\!\!\!\!+ {c_3}{r_3}\left( {{p_{rj}} - {x_{ij}}} \right) 。 \end{array}$ | (5) |
其中,
${p_{rj}} = \sum\limits_{i = 1}^{N/2} {{P_{ij}}} /N/2。$ | (6) |
改进的PSO算法中的所有粒子利用优秀粒子经验、粒子极值、种群极值以及种群共享位置信息指导自身的搜索方向。算法利用非线性惯性权值增加了收敛速度,利用共享极值增加种群多样性,从而避免陷入局部最优解。
2 水下潜器地形匹配算法 2.1 地形匹配原理基于灰度的水下潜器地形匹配算法利用不同图像中的相同景物来确定图像间的相对位移[3]。算法过程是将实时图在基准图中从上至下,从左至右进行卷积遍历。其中,卷积操作是在基准图和实时图中对相同区域的像素进行MAC操作。
基于灰度的水下潜器地形匹配算法主要采用相关度量方法及最小距离度量方法2种相似度量法[4]。假设二维n ×n实时图和m ×m基准图子图表示成一维矢量,记为X和Yu, v,如果矢量X和Yu, v间的距离ε或夹角θ越小,则越相似。因此,利用ε和θ描述图像的相似度。
1)相关度量法。该方法采用两图像的矢量X和Yu, v间的夹角θ来表示图像相似度,通常为了计算方便,用夹角θ的余弦函数来表示。当2幅图像相互匹配时,相关度量法的相似度值出现极大值,所以,可以利用该性质确定图像间的匹配位置。
2)最小距离法。该方法采用两图像的矢量X和Yu, v间的距离ε的范数
根据地形匹配的原理,选取图像间互相关系值计算公式作为水下潜器地形匹配算法的适应度函数,如式(7)所示:
$R\left( {u,v} \right) = \frac{{\frac{1}{{{n^2}}}\sum\limits_{i = 0}^{n - 1} {\sum\limits_{j = 0}^{n - 1} {{x_{ij}}{y_{i + u,j + v}} - \bar X{{\bar Y}_{u,v}}} } }}{{\sqrt {\frac{1}{{{n^2}}}\sum\limits_{i = 0}^{n - 1} {\sum\limits_{j = 0}^{n - 1} {x_{ij}^2 - {{\bar X}^2}} } } \sqrt {\frac{1}{{{n^2}}}\sum\limits_{i = 0}^{n - 1} {\sum\limits_{j = 0}^{n - 1} {y_{ij}^2 - \bar Y_{u,v}^2} } } }}。$ | (7) |
式中:
假设基准图大小为m ×m,实时图大小为n ×n,基于改进PSO的地形匹配算法过程如下:
1)读取并保存实时图及基准图数据,包括图像的尺寸、像素等信息,对需要预处理的数据进行计算并存储。
2)参数设置,包括种群规模N,权重上下限
3)随机生成粒子素的和位置,根据式(7)计算粒子适应度值,计算粒子个体最优值和种群最优值。
4)根据粒子所在位置计算误差值ε,如果ε > Ts,则执行步骤5,否则,执行步骤6。
5)根据改进的PSO算法更新粒子速度。
6)更新粒子位置、粒子最优值及全局最优值,判断是否完成全部粒子的遍历,如果完成,执行步骤7,否则,执行步骤4。
7)判断是否满足终止条件,如果满足,则输出最优解,停止算法,否则,根据式(3)更新权重系数,然后执行步骤4。
3 仿真实验本文在Matlab平台对基于改进PSO算法的水下潜器地形匹配算法进行了对比仿真实验,实验结果如图 2所示。
从实验结果可知,本文提出的算法在时间和正确率方面明显好于标准PSO算法,由于算法改进了PSO寻优策略和适应度函数,避免了大量不必要的运算,在加快收敛速度的同时,也提高了算法稳定性。本文提出的算法,在匹配精度和收敛速度方面都得到了提升,在保证较高正确率的前提下,具有稳定性高和匹配效率高的优势。
4 结语在人们逐渐从陆地资源利用向海洋资源开发和探索转变的背景下,地形匹配算法在水下潜器自主导航及智能控制中发挥着越来越重要的作用,如何利用PSO算法提高水下潜器地形匹配的性能是本文研究的重点。本文利用SBD技术和IPSO算法对船舶性能方案进行寻优,最后,进行了仿真实验,实验结果达到预期。
[1] | 李俊, 徐德民, 宋保维, 等. 自主式水下潜器导航技术发展现状与展望[J]. 中国造船, 2004, 45 (3): 70–77. |
[2] | 张丽平, 俞欢军, 陈德钊, 等. 粒子群优化算法的分析与改进[J]. 信息与控制, 2004, 33 (5): 513–517. |
[3] | CLERC M J, KENNEDY. The Particle swarm-explosion, stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (1): 58–73. DOI: 10.1109/4235.985692 |
[4] | CHALERMWAT P, EL-GHAZAWI T, LE MOIGNE J. Two-phase genetic algorithm-based image registration on parallel cluster[J]. Journal of Future Generation Computing Systems, 2001, 17 (3): 467–476. |