自适应Otsu算法

自适应Otsu算法（精选十篇）

自适应Otsu算法 篇1

关键词：CDF9-7小波,自适应Otsu算法,视频字幕,图像分割

0 引言

视频是依据人眼视觉暂留原理, 存储的看上去平滑连续而实际上动态捕捉的一系列的静态照片, 已经成为互联网上除文字、声音之外最重要的媒体形式, 对其自动分析与理解已经成为当前网络监管的重要研究内容。视频图像中的文字隐含了非常丰富的高层语义信息, 对其分割、定位、识别、理解和检索具有重要的现实意义。从这些处理步骤来讲, 分割和定位操作是字符识别、理解和检索等高层处理的基础, 直接影响着高层处理的成功率和精确度。字幕作为视频中最重要的文字, 有的以独立的字幕文件存在, 而有的被嵌入在视频图像中。独立存在的字幕文件往往仅包含时间区间和文本信息, 比较容易处理, 而嵌入在视频图像中的字幕就必须首先进行图像分割操作, 然后采用适当算法定位这些文字的区域。

图像分割就是把图像分解成有限个感兴趣的和特质相关的区域的一种操作, 是图像分析、理解和识别操作的基础, 因此研究人员从各个学科出发, 提出并不断改进了很多图像分割方法。目前主要的分割方法有基于阈值设定、基于边缘检测、基于区域、基于聚类分析、基于模糊集理论[1], 以及基于群体智能[2]等众多分割方法。这些算法各有优缺点, 存在的主要问题是适用范围的局限性和较低的准确性及鲁棒性。本文提出的CDF9-7小波变换结合自适应Otsu算法的视频图像分割方法, 对于视频图像中字幕区域的分割效果良好。

1 视频图像分割步骤

本文给出的分割方法总体来说有三步。首先, 先从视频中获取视频图像, 对彩色图像则要进行去噪和灰度化等预处理。目的在于尽可能削弱图像背景级噪声对字幕文字的相关性。 然后, 对预处理后的图像进行CDF9-7 小波变换, 获取其水平和垂直方向的高频分量HH。因为CDF9-7 小波是满足线性相位要求的非常适用于图像处理的双正交小波, 而视频字幕区域背景和字幕颜色往往对比度高, 边缘信息和高频分量丰富。最后, 使用自适应Otsu算法找出该高频分量中的最佳阈值, 分割出图像中包含字幕文字的有效区域。

1.1 CDF9-7 小波

9-7小波是一个双正交小波[3], 其正交性体现在母小波ψ及其对偶母小波之间, ψ和本身没有正交性, 即, 对应地其尺度函数Φ及其对偶尺度函数也满足正交关系, 即, ψ和构成一对L2 (R) 空间的双正交小波基。正交小波可视为是在时的双正交小波的特例。虽然相对正交小波, 9-7双正交小波正交性放宽或者说变弱, 但是它具有很好的对称性和线性相位特性。其滤波器系数获取可以通过求解约束PR条件得到。但约束条件毕竟只是必要条件, 为使无穷乘积收敛, Cohen、Daubechies和Feauveau提出了以它们名字首字母命名的CDF方法, 在求解时增加了新的消失矩条件, 求解出了系数和没有消失矩条件略有不同的9-7小波, 可记为CDF9-7小波。这种小波除了原有的对称性和线性相位这些优点外, 支撑区间变小且收敛更快, 正是由于CDF9-7小波的这些优秀特征, 因而被广泛用于图像处理等领域, 目前已经成为了JPEG 2000有损图像压缩标准中的默认小波。但在具体实现中, 由于图像数据量往往很大, 为提高运行效率, 往往并不直接采用离散小波变换的快速算法 (MALLAT算法) , 而是对CDF9-7小波进行提升实现, 在同等条件下, 运算速度和效率较MALLAT算法提高2倍。

CDF9-7小波对二维图像变换的步骤是, 首先用分析滤波器对图像 (记为cj+1l, n) 的列做小波变换, 得到低频部分和高频部分。然后对低频部分的行做小波变换, 得到低频中的低频分量cjk, m (记为LL) 和低频中的高频分量dj, 1k, m (记为HL) ;对高频部分的行做小波变换, 得到高频中的低频分量dj, 2k, m (记为LH) 和高频中的高频分量dj, 3k, m (记为HH) 。以上分解也可以先做行小波变换再做列小波变换, 结果相同。最后, 图像经一级分解后由如下4块区域组成:

多级分解可以持续对LL分量 (图像概貌) 进行, 最终图像变成塔式结构, 为区分每个小块, 一般需要对LL等块添加代表分解级数的下标。由于一般的视频字幕文字区域与背景 (往往纯色) 存在比较强的边缘, 对比度高, 边缘信息和高频分量本身非常丰富, 因此, 经过分解后, 利于图像分割的信息主要集中在高频中的高频分量HH中;多级分解必然是对上次分解的低频分量LL进行, 本身隐含的视频字幕文字区域信息很少。经过多种条件下的反复测试, 在准确率基本一致的情况下, 多级分解运算量大幅度提高, 并无必要, 对预处理后的图像只需要使用CDF9-7 小波变换进行了一级分解即可。即完成一级分解得到的HH1送做后续处理, 其他3 块数据暂时不用。

1.2 自适应Otsu算法

经过CDF9-7 小波分解后的图像区域HH1滤除了原视频图像中的低频信息, 隐含了大量视频图像的高频边缘信息, 但并没有对图像进行分割, 同时由于图像背景的复杂性, 视频图像字幕区域之外的部分仍然存在很多对比度高的边缘信息, 因而必须采用相应的方法进行分割和判定。

传统的Otsu算法一般被认为是图像阈值方式分割中阈值选取的“最佳算法”, 也可以称为最大类间差法或大津算法[4]。这种算法计算简单, 受图像对比度和亮度影响较小, 因而在图像分割领域应用广泛。其基本理论是按图像的灰度特性, 寻找出灰度范围在0~ L- 1 之间共L个灰度级的图像的使得类间方差d最大的最佳阈值t , 小于t的像素集归为背景, 大于t的像素集归为前景。 用数学方法描述即为: t = max (d) , d = bp (t) * (be (t) - u) 2+ fp (t) * ( fe (t) - u) 2, 其中变量:bp为取最佳阈值时背景总的像素点占整幅图像的比例 (概率) ;be为取最佳阈值时背景总的像素点灰度值的均值;fp为取最佳阈值时前景总的像素点占整幅图像的比例 (概率) ;fe为取最佳阈值时前景总的像素点灰度值的均值;u为整幅图像像素点灰度值的均值。使以上表达式值最大的t , 即为分割图像的最佳阈值。类间方差越大, 则背景和前景的差别越大, 类间方差越小, 则背景和前景的差别越小。造成类间方差变小的原因主要是阈值计算不当, 使得部分背景错分为前景或部分前景错分为背景, 因此, 最佳阈值的选择至关重要。

这种算法虽然简单且效果较好, 但是也有一些显著缺陷。主要有:

(1) 最佳阈值的选取必须遍历图像整个灰度范围0~L - 1 内的所有像素, 逐个计算类间方差d并找出使类间方差最大的t, 运算量大, 难以满足视频图像中字幕区域的分割这样的实时系统应用;

(2) 阈值选取是在整个视频图像范围进行计算, 而实际视频帧图像本身灰度分布动态变化且受到各种噪声的干扰, 仅利用灰度直方图得到的阈值难以得到满意的图像字幕区域分割结果。

为此, 在视频图像中字幕区域图像分割这样的实时应用中, 针对以上两点不足, 考虑到视频图像字幕区域往往集中在视频图像下部, 甚至有的字幕区域背景还是纯色或少量噪声的实际, 提出了一种自适应的Otsu算法。设某视频图像分辨率 (宽×高) 为m× n (如640×480, 1 280×720 等) , 共L个灰度级, 其基本方法步骤是:首先, 根据图像高度, 自适应地确定字幕区域的高度范围, 截取字幕区域子图像并结合根据sum (第k行像素值) 等于或约等于m × L, 用软件简单计算, 自适应地判别上述字幕区域背景是否为纯色 (如白和黑) 或近似纯色。好处是, 最佳阈值t的选取局限在较小区域, 大幅度降低了运算量;然后, 选择字幕区域子图像灰度值中位数作为“最佳阈值”或传统的Otsu算法遍历出最佳阈值。特别地, 对字幕区域中字符和背景为纯色或近似纯色的情况, 即使有噪声, 灰度个数或灰度级L也非常小, 传统的Otsu算法可以极快找出最佳阈值, 甚至可以直接灰度值中位数作为“最佳阈值”, 两种方案都可以进一步降低运算量, 真正满足实时系统要求;最后, 使用上述最佳阈值对整幅视频图像进行分割。

2 实验及结果

实验全部在Matlab 2009b下编程完成, 数据为常见的电影、新闻和动画。目前, 对于图像分割效果的评价, 没有统一的客观数量指标[5], 本文的评价指标设定为传统的Otsu算法求出的最佳阈值和自适应Otsu算法求出的最佳阈值之间的差值td, 传统的Otsu算法耗时减去自适应Otsu算法耗时的时间差jl。以从电影《第五元素》中截取的一个视频图像为实例, 其分辨率为560×315, 宽高比为16∶9, 经过对比计算td等于3, 可见阈值差别很小;jl等于80 ms, 如果将整个2 小时5 分钟的整个视频累积, 则总的jl近590 s, 可见自适应Otsu算法效率和实时性显著提升。作为实例的视频图像按自适应Otsu算法所得阈值进行图像分割的结果如图1 所示。从实验结果看出, 改进的算法令人满意。

3 结语

本研究提出的基于CDF9-7 小波分析和自适应Otsu算法的视频图像分割方法, 较其他分割方法大幅度降低了运算量, 高效易行, 满足实时性需求并具有一定的鲁棒性。以这些区域为基础, 可以进一步完成诸如视频文字区域定位等图像分析、理解和识别操作。但由于视频图像背景的复杂性, 算法的准确性及鲁棒性仍需进一步提升。

参考文献

[1]何俊, 葛红.王玉峰.图像分割算法研究综述[J].计算机工程与科学, 2009 (12) :58-61.

[2]马苗, 刘艳丽.图像分割背景下群体智能优化算法的性能对比[J].云南大学学报:自然科学版, 2012 (4) :401-407.

[3]刘在德, 常晋义, 沈钧毅.一类双正交插值小波的参数化构造及图像编码应用[J].中国图象图形学报, 2010 (4) :557-564.

[4]胡敏, 宋银龙.基于二维Otsu和模糊聚类的图像分割算法[J].计算机应用研究, 2012 (4) :1563-1565.

[5]邓廷权, 焦颖颖.图像分割质量评价的二型模糊集方法[J].计算机工程与应用, 2011 (32) :217-220.

自适应Otsu算法 篇2

空间实体碰撞预报算法及其自适应步长设计

为避免空间飞行实体碰撞漏报并提高计算效率,提出了通用性的基于仿真的多空间飞行实体碰撞预报方法.采用自适应调整仿真计算步长,给出了相应算法,并通过典型算例验证了其正确性和有效性.

作 者：王晓宇 WANG Xiao-yu 作者单位：空军工程大学,导弹学院,陕西,三原,713800刊 名：空军工程大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY (NATURAL SCIENCE EDITION)年，卷(期)：7(6)分类号：V448关键词：空间系统 碰撞预报 仿真 步长 自适应

自适应Otsu算法 篇3

关键词： 农业图像；自适应维纳滤波算法；中值滤波算法；非局部均值滤波算法；噪声；清晰度

中图分类号：S126；TP391 文献标志码： A

文章编号：1002-1302（2015）08-0424-02

随着农业智能化水平的快速发展，各类农业图像提供的大量信息已经成为农产品果实自动采摘 [1]、农作物长势、病害分析 [2]、农作物产量估算 [3]的重要依据，因此农业图像的处理和分析已经成为农业智能化发展的一个重要研究方向。近年来，小波变换 [4-5]、轮廓波变换 [6]、中值滤波 [7]、自适应维纳滤波 [8]、非局部均值滤波 [9-10]等算法相继被用于图像去噪处理，并取得了较好的效果；但对于细节信息复杂的农业图像而言，去噪效果往往不尽如人意。笔者在对该领域已有成果充分分析的基础上提出了一种农业图像自适应混合滤波算法，该算法对质量不高的农业图像采用改进型中值滤波算法和自适应维纳滤波算法进行处理，充分发挥2类算法的滤波优势，从而获得高质量的农业图像。

1 改进型中值滤波算法

中值滤波算法在对图像进行处理时，通过预先设定一定大小的窗口，这样的窗口尺寸可以是3×3或者5×5，将该类窗口在图像上按照一定的顺序进行滑动，当窗口中心点处于图像中某一像素点时，如果窗口尺寸为3×3，那么该像素点的滤波值可以表示成：

f=Median{f1，f2，f3，…，f8}。 （1）

其中：f为窗口中心点像素滤波后的灰度值；f1～f8为窗口中除中心点外的其余8个像素点的灰度值；Median{}为取中间值计算方式。大量试验结果表明，该算法对于普通的数字图像滤波效果较好；但一般来说农业图像细节信息比较多，因此为了将该算法应用于处理农业图像，有必要对其进行适当改进。其步骤如下：步骤1，统计（1）式中的最大值fmax和最小值 fmin；步骤2，在尺寸为3×3窗口中提出fmax和fmin，组成集合Q= {f1，f2，f3，…，f6}；步骤3，求取集合Q={f1，f2，f3，…，f6}的平均值faverage；步骤4，将fmax、fmin以及faverage组成一新的集合Q′={fmax，fmin，faverage}；步骤5，求取集合Q′的中间值f′=Median{Q′}，从而获得窗口中心点滤波后的灰度值。

2 自适应维纳滤波算法

3 试验仿真与结果分析

本研究算法基本思路是：（1）采用“1”节中提出的改进中值滤波算法对含有噪声的农业图像进行预处理；（2）采用“2”节所描述的自适应维纳滤波算法对经过改进中值滤波算法处理后的图像进一步进行噪声抑制。

对本研究算法采用Matlab软件进行编程，试验数据为一幅处于成熟期的桃子图像。为了对该算法的性能进行全面了解：一方面引入中值滤波算法、自适应维纳滤波算法、非局部均值滤波算法与本研究算法进行试验对比；另一方面对上述几类算法的试验结果采用峰值信噪比（peak signal noise to ratio，PSNR）进行定量分析与评估。相关试验结果分别如图1至图6所示，PSNR评价结果如表1所示。

由图1至图6可知，对于受到方差为15%的高斯噪声污染的农业图像（图2）而言，采用中值滤波去噪后，结果如图3所示，由此可以看出，图中的果实边缘基本能辨认出来，但桃子果实表面噪声依然较大，这说明单纯采用该算法无法有效去除图像中的噪声。中值滤波算法处理后结果见图4，图中噪声被抑制的程度要高于图3，总体而言图4的清晰度与图5比较接近，这说明非局部均值滤波算对于受到高强度噪声污染的图像而言去噪效果并不理想，不适合处理农业图像。本研究算法处理结果如图6所示，图中的噪声基本得到消除，果实、叶片边缘基本从噪声中恢复出来，果实表面残留的噪声比较少，视觉效果整体上与图1最接近。由表1可知，4种算法对农业图像的去噪效果随着噪声强度的提高而降低，并且当噪声方差为15%时，本研究算法的PSNR值明显高于其余3种算法，这说明本研究算法对农业图像的处理是有效的。

4 结语

为了实现对农业图像的有效滤波，将改进中值滤波与自适应维纳滤波这2类算法有机结合提出了一种针对该类图像的自适应混合滤波算法。仿真试验结果表明，本研究提出的滤波算法基本适合于处理农业图像，其效果稍稍优于已有的同类型图像，对农业图像的处理具有一定的参考价值。

参考文献：

[1] 吕继东，赵德安，姬 伟 苹果采摘机器人目标果实快速跟踪识别方法[J] 农业机械学报，2014，45（1）：65-72

[2]彭占武，司秀丽，王 雪，等 基于计算机图像处理技术的黄瓜病害特征提取[J] 农机化研究，2014，36（2）：179-182，187

[3]李 红 基于CBERS-2卫星图像的石河子地区棉花产量遥感监测研究[J] 石河子科技，2007（6）：28-31

[4]王小兵，孙久运，汤海燕 一种基于数学形态学与小波域增强的滤波算法[J] 微电子学与计算机，2012，29（7）：64-67

[5]赵 辉，刘文明，岳有军，等 一种新的去噪算法在农作物图像处理中的应用[J] 江苏农业科学，2014，42（1）：371-373

[6]刘 悦，李一兵，李 骜 联合双重滤波的水下图像NSCT阈值去噪算法[J] 哈尔滨工程大学学报，2013，34（2）：251-255

[7]晏资余，罗 杨，杨 浩 图像椒盐噪声的分阶段中值滤波算法[J] 南华大学学报：自然科学版，2013，27（3）：66-70，77

[8]张 东，覃凤清，曹 磊，等 基于维纳滤波的高斯含噪图像去噪[J] 宜宾学院学报，2013，13（12）：60-63

[9]张 宇，王向阳 频域小波矩的非局部均值图像去噪[J] 小型微型计算机系统，2012，33（9）：2079-2082

[10] 张 权，桂志国，刘 祎，等 医学图像的自适应非局部均值去噪算法[J] 计算机工程，2012，38（7）：182-184，187

自适应Memetic算法 篇4

遗传算法是一种全局优化算法, 是模拟生物在自然界中的进化过程而形成的, 已在机器学习、组合优化、图像处理和自适应控制等领域中广泛应用。然而大量研究与实践显示, 遗传算法全局搜索能力很强而局部搜索能力不是很强, 且容易过早地收敛, 相反, 局部搜索算法搜索目的性很强, 能够很快收敛到局部最优解, 因此将局部搜索算法与遗传算法相结合, 可以提高遗传算法的优化性能。我们称这种混合算法为遗传局部搜索算法, 也可称作Memetic算法。

Memetic算法是一种局部搜索侧略与全局搜索策略相结合的算法[1]。相比传统的遗传算法, 这种结合机制使其在某些问题优化中的搜索效率快很多。Memetic算法提出的是一个概念, 一种框架, 不只是混合遗传算法或拉马克进化算法。在这种框架下, 不同搜索策略的选取可以形成不同的Memetic算法, 比如局部搜索算法可以选取模拟退火、爬山搜索、禁忌搜索、贪婪算法等, 全局搜索算法可以选取进化规划、进化策略、遗传算法等。

全局搜索策略与局部搜索策略耦合的过程中有以下6个方面[2]需要注意: (1) 局部搜索的频率; (2) 个体进行局部搜索的概率; (3) 种群中可进行局部搜索的范围; (4) 局部搜索的强度; (5) 局部搜索方法的选择; (6) 如何减小通过引入局部搜索算子而增加的计算时间。

局部搜索算法有很多, 不同的局部搜索算法对特定优化问题的优化效率差别很大。自适应Memetic算法, 即可以根据优化问题的不同自适应的选取局部搜索算子的Memetic算法, 成为优化算法领域新的研究方向。Krasnogor在文献[3]中提出了对多种局部搜索算法进行整合, 并依据局部搜索邻域的选择函数与当前算子的搜索情况来选取局部搜索算法的策略。文献[4]中用“hyperheuristic”一词来描述将多个局部搜索算法整合, 不同个体采取不同局部搜索算法的策略。Smithz提出了Coevolving Memetic算法, 采用某种策略选择局部搜索算法[5]。这种策略, Ong and Keane描述为“meta-Lamarckian learning”[6]。文献[7]总结了自适应Memetic算法的研究现状。

局部搜索个体的选择策略同样是Memetic算法的研究重点。文献[8]中提到了基于离散度的策略来确定局部搜索点。文献[9]中提到了基于适应值、空间分布及精英保留等策略来确定局部搜索点。

本文选取基于离散度的策略来确定局部搜索点, 并且将多种局部搜索算法与遗传算法结合, 形成多种Memetic算法。将这些算法应用于基准函数优化中, 通过对每种算法的优化特性进行观察, 进一步提出了基于离散度的自适应Memetic算法 (DAMA, 即Diversity-based Adaptive Memetic Algorithm) 。通过将该种算法与传统Memetic算法作对比, 表明该算法具有更强的通用性, 更高的效率和更好的鲁棒性。

1 基于离散度的自适应Memetic算法

1.1 耦合策略及参数设置

(1) 局部搜索算法的选取策略:局部搜索算法的效率。局部搜索算法的选取策略在自适应Memetic算法中有很多。相比排序法、随机法、经验法, 本文通过局部搜索算法的搜索效率来选择局部搜索算法。单纯形搜索法、方向加速法、拉格朗日搜索法与模式搜索法组成了局部搜索算法库。对前面的局部搜索点随机选择局部搜索算法, 组建局部搜索算法的优化效率库, 然后, 后面的局部搜索点根据前面局部搜索算法在周围已搜索点的优化效率选择局部搜索算法。

下式用于计算局部搜索算法的优化效率:

上式中:

i———优化代数;

bestvars———最优点变量;

bestfitness———最优点适应度。

(2) 局部搜索点集的选取策略:离散度原则。为求得最优解, 种群中的个体最好每个都进行局部搜索, 然而为了提高优化效率, 在实际问题优化中, 不能对每个个体都进行搜索。在局部搜索点的选取上有很多算法, 比如适应值法、随机法、离散度法等[5,6]。本文在局部搜索点的选择上选取基于离散度的策略, 具体策略如下: (1) 将种群中的最优点确定为局部搜索点; (2) 单位化其他搜索点到最优点的距离; (3) 去掉种群中距离最优点相对距离较小的点; (4) 当局部搜索点的个数满足要求时, 停止搜索, 否则转步骤 (1) , 继续搜索。

(3) 局部搜索点选取搜索邻域的策略。不同的搜索邻域对算法的优化效率具有很大的影响。搜索邻域的选取取决于个体的不同类型:对种群中的最优个体选取小的搜索领域, 进行精确搜索;为使其他局部搜索点共享最优个体的搜索信息, 其它局部搜索点的搜索邻域半径定为搜索点到最优个体的距离 (见图1) 。

(1、2、3、4、5为局部搜索点, 1是种群中的最优点)

(4) 局部搜索点选取搜索强度策略。需要进行深度搜索的点, 如每代种群中的最优点, 搜索强度高, 搜索次数可设置相对较多, 如8倍变量个数, 其他局部搜索点不需要进行深度搜索, 搜索次数可设置相对低一些, 如4倍变量个数。

1.2 算法流程

算法流程见图2。

2 数值实验

Ackey、Sphere、Rastrigin和Griewank[10]等测试函数组成数值试验的测试函数集, 具体函数特性见表1。为体现DAMA算法的优越性, GA及传统Memetic算法 (MA-POWE, MA-SIMP, MA-HOJE, MA-LAGRH) 共同参与数值实验, 进行对比。各算法的参数设置如表2。对所有函数在20维的情况下进行测试, 中止条件为运算5 000次, 各实验均独立运行20次, 选函数最优点的平均值及方差来确定算法的效率和鲁棒性, 结果见图1、表3。

GA遗传算法;

MA-POWE方向加速法与遗传算法结合的Memetic算法;

MA-HOJE模式搜索法与遗传算法结合的Memetic算法;

MA-SIMP单纯形搜索法与遗传算法结合的Memetic算法;

MA-LAGRH拉格朗日法与遗传算法结合的Memetic算法;

DAMA自适应Memetic算法。

以上测试表明, 与其它5种算法相比, DAMA在Rastrigin与Ackey测试函数的优化中效率最高, 在Rastrigin与Sphere测试函数的优化中效率较高。对不同的局部搜索算法, DAMA需要进行优化效率的评估, 导致DAMA在某些问题领域上的优化效率不如传统Memetic算法。为提高DAMA的优化效率, 在实际问题的优化中需要优化人员根据优化问题的特性自行设置DAMA中局部搜索算法的数量与种类。测试结果表明, DAMA算法相比其它5个算法, 具有更强的通用性。

3 结语

针对遗传算法局部搜索能力差且易过早收敛的缺点, 本文提出了一种基于离散度的自适应Memetic算法 (DAMA) , 该算法通过离散度来确定局部搜索点, 然后根据局部搜索算法的效率自动选择局部搜索算法。数值试验表明, DAMA比遗传算法 (GA) 及4种传统Memetic算法 (MA-POWE, MA-SIMP, MA-HOJE, MA-LAGRH) 更具通用性, 效率也更高。

摘要：在处理多峰函数的优化问题时, 遗传算法局部搜索能力差, 并且容易早熟。针对这种问题, 将遗传算法与多种局部搜索算法相结合, 形成多种Memetic算法。通过进行数值优化实验, 发现算法的优化效率有所提高, 但是局部搜索算法的不同对优化性能影响很大。为解决这种问题, 在传统Memetic算法的基础上提出了一种使每代个体根据局部搜索算法的搜索效率自适应选取局部搜索算法的Memetic算法, 即基于离散度的自适应Memetic算法。通过测试函数测试, 这种算法具有更高的效率和更强的通用性。

关键词：多峰函数优化,遗传算法,局部搜索算法,离散度,自适应Memetic算法

参考文献

[1]P MOSCATO.On evolution, search, optimization, genetic algorithms and martial arts:towards memetic algorithms, publication report 790[J].Caltech Concurrent Computation Program, 1989.

[2]YEW-SOON ONG, MENG HIOT LIM, XIANSHUN CHEN.Research frontier:memetic computation-past[Z].Present&Future.

[3]N KRASNOGOR, B BLACKBURNE, J D HIRST, et al.Multimeme algorithms for the structure prediction and structure comparison of proteins, in parallel problem solving from nature[J].Lecture Notes in Computer Science, 2002.

[4]P COWLING, G KENDALL, E SOUBEIGA.A hyperheuristic approach to scheduling a sales summit[C]//PATAT 2000, Springer Lecture Notes in Computer Science.Konstanz, Germany, Aug.2000:176-190.

[5]J E SMITH ET AL.Co-evolution of memetic algorithms:initial investigations, in parallel problem solving from nature—PPSN VII, G.Guervos et al., Eds.Berlin, Germany[J].Springer, Lecture Notes in Computer Science, 2002:537-548.

[6]Y S ONG, A J Keane.Meta-Lamarckian in memetic algorithm[J].IEEE Trans.Evol.Comput, vol.8, pp.99-110, Apr.2004.

[7]ONG Y-S, LIM M-H, ZHU N, et al.Classification of adaptive memetic algorithms:a comparative study[J].IEEE Trans Syst Man Cybern Part B.

[8]M W S LAND.Evolutionary algorithms with local search for combinatorial optimization.Ph.D.Thesis[J].University of California, San Diego, 1998.

[9]W E HART.Adaptive global optimization with local search[D].PhD thesis:University of California, 1997.

自适应Otsu算法 篇5

二维自适应非结构网格DSMC并行算法研究

研究了二维自适应非结构网格DSMC并行算法实现的过程.首先提出了一类非结构网格自适应策略,有效降低了网格尺度对计算结果的影响,提高了流场的.分辨率;然后基于PC-CLUSTER群机并行体系结构与消息传递库MPI并行环境,利用分区并行思想,设计了非结构网格DSMC并行算法,节约了计算时间.利用For-tran90的动态分配内存技术编制了通用计算程序;最后对过渡流域高超声绕流进行了数值模拟,计算结果初步验证了算法的可行性与有效性.

作 者：王学德 伍贻兆 夏健 林晓宏 WANG Xue-de WU Yi-zhao XIA Jian LIN Xiao-hong  作者单位：王学德,林晓宏,WANG Xue-de,LIN Xiao-hong(南京理工大学动力工程学院,南京,210094)

伍贻兆,夏健,WU Yi-zhao,XIA Jian(南京航空航天大学,航空宇航学院,南京,210016)

刊 名：计算力学学报  ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS 年，卷(期)：2009 26(2) 分类号：V211.3 关键词：自适应非结构网格   DSMC   并行算法   MPI  

自适应Otsu算法 篇6

关键词：自适应蚁群算法；迭代次数；收敛速度；最优路径

中图分类号：TP312 文献标识码：A

Abstract：In view of the defects from the basic ant colony algorithm frequent iterations and slow speed in convergence，the solution in this paper are using improved adaptive ant colony algorithm，setting up mathematical model，simulating out the optimal path through improved adaptive ant colony algorithm and applying to the choice of the optimal path between emergency dispatching station and the patients' position.The results show that the model and algorithm in convergence speed and the number of iterations are better than the basic ant colony algorithm.

Keywords：adaptive ant colony algorithm；iterations；the rate of convergence；the optimal path

1 引言（Introduction）

120急救指挥系统在城市应急指挥体系中具有非常关键的作用，当患者拨入急救电话或者遇到重大事故和突发事件时，指挥中心需要根据患者位置或者事故位置选择最优路径快速将患者送往医院进行急救[1]。最优路径的选择需要考虑起点和终点之间的总里程数，人流量及客流量等外界因素。基本蚁群算法搜索时间较长，而且容易出现停滞，易陷入局部最优解等缺陷[2]。此次设计的自适应蚁群算法主要根据全局最优解的分布情况，通过计算得出迭代次数不断增加的同时，自适应地减小蚁群觅食过程中的视野范围，提高获取最优解的速度，从而动态地获取各路径上的信息量强度，提高了全局搜索能力，避免了局部收敛和早熟现象。在模拟寻找最优路径过程中，设置多个节点模拟起点和终点之间的障碍物，以类似蚂蚁觅食的方式在求解复杂组合优化的问题上取得了良好的仿真效果，能够对急救车辆到达患者位置之间的多条路径进行模拟和优化。

2 基本蚁群算法（The basic ant colony algorithm ）

基本蚁群算法是20世纪90年代由意大利学者M.Dorigo等人首先提出来的一种新型的模拟进化算法，称之为蚁群系统[3]。基本蚁群算法主要解决TSP（Traveling Salesman Problem）旅行商问题，QAP（quadratic Assignment Problem）分配问题、JSP（Job-shop Scheduling Problem）调度问题等，取得了一系列较好的实验结果。基本型蚁群算法分为正反馈以及分布式计算。正反馈过程的优势是能较快的找到问题的较好解；分布式的优势是易于并行实现，同时与启发式算法相结合，能使该方法易于找到更好的解，最后达到最优解[4]。基本蚁群算法的原理图如图1所示。

3 改进的自适应蚁群算法模型（Improved adaptiveant colony algorithm model）

从基本蚁群算法中发现，参数视野值对最优解的影响比较大，经过多次实验发现，在视野范围不变的情况下，算法后期的收敛速度较慢，迭代次数逐渐增加，并且当起点与终点之间节点越多，越容易陷入局部最优，无法达到全局最优；但是如果给定视野范围过小，收敛速度会有适当加快，但是更容易陷入局部最优。经过多次论证，当参数视野值为原始视野值60%时，收敛速度最快，且迭代次数最少，最接近全局最优解值。算法表达式为

算法实现的流程图如图2所示。其中，输入原始数据后会获取路网节点数、各节点的具体坐标位置，节点的权值矩阵、自适应蚁群的群体规模、最大迭代次数、蚁群的最大移动步长、拥挤度因子等参数。

4 算法的仿真（The simulation algorithm）

现将改进的自适应蚁群算法与基本蚁群算法求解最优路径进行仿真，并将两者结果进行对比，仿真工具为MATLAB 2010a，蚁群规模n=50，留在每个节点上的信息受重视程度α=0.1，启发式信息受重视程度β=0.5，蚂蚁数目20个，最大迭代次数100次。图3为起点与终点之间有七个信息节点，利用自适应蚁群算法得到的最优路径仿真示意图，得出的路径为1—2—3—5—9—8—4—6—7，其中最短路径为1—2—3—5—9。图4为自适应算法与基本型蚁群算法在寻优过程中的对比，两种算法分别在第二次和第五次迭代后搜索到全局最优解。

5 结论（Conclusion）

针对基本蚁群算法收敛速度慢，运算量大，陷入局部最优的缺陷，本文提出一种自适应蚁群算法，使其随着全局最优解的变化而适当的改变视野范围的值。实验结果表明，改进的自适应蚁群算法在收敛速度、迭代次数、计算量，寻优精度均优于基本型蚁群算法，适用于在急救车辆调度过程中实现最优路径的规划，为急救车选择最优路径到达患者位置提供了有利依据。

参考文献（References）

[1] 杨丽锦.浅析蚁群算法的原理及应用方向[J].电脑知识与技术，2009（6）：12-14.

[2] 杨琼.具有感知觉特征的蚁群算法在连续函数优化中的应用[D].四川师范大学，2009.

[3] 马宪民，刘妮.自适应视野的人工鱼群算法求解最短路径问题[J].通信学报，2014（1）：16-17.

[4] 蒋艳玲，张军.蚁群算法的参数分析[J].计算机工程与应用，2007（20）：34-35.

自适应重生鱼群优化算法 篇7

人工鱼群算法[1]是李晓磊等人于2002年提出的一种基于动物自治体的新型寻优策略。该算法模拟了自然界中鱼群的觅食、聚群和追尾行为。为了突出人工鱼群算法的全局寻优能力,李晓磊等[2]将人工鱼群算法与遗传算法进行对照,测试后得到其效果更佳,且人工鱼群算法具有集群智能、良好的并行性、参数和初值的鲁棒性强等优点,在工程上已得到广泛使用[3,4,5,6,7,8]。李亮等[4]于2006年构造了一种两点禁忌寻优算子以避免寻优过程中的迂回搜索,并将其应用到两个复杂土坡的最小安全系数搜索中;方金城等[5]于2011年引入实数编码对鱼群算法进行改进,并将其应用于配送决策问题中;陈安华等[7]于2012年通过定义相似度因子和聚类判别因子,建立了模拟人工鱼群追尾行为的机械故障聚类诊断模型,并将之应用于机械故障特征信息的聚类分析。

通过反复实验发现人工鱼群算法设计思路简单,求解低维优化函数时能够保持较高的精度,且能够较快地获取全局最优解。但我们在实际中遇到的往往是庞大的工程问题,决策变量的维数较高,导致搜索范围的空间复杂度大大增加。这时应用传统的人工鱼群算法很容易陷入局部最优,算法的精度和收敛速度也随之下降。针对以上的不足,本文对人工鱼群算法进行改进,给鱼群注入“新生命”和引入动态拥挤度因子,使其在处理高维优化函数时仍能保持较高的精度。主要思想是在算法迭代过程中,一方面给种群注入“新生命”,丰富了种群的多样性;另一方面通过控制拥挤度因子的值及时地调整鱼群的行为,这样扩大了鱼群的搜索范围,有效地避免算法陷入局部最优。同时,利用仿真实验研究了该方法的有效性。

1 自适应重生鱼群优化算法

1.1 优化问题的描述

一个优化问题描述如下:

式中,f(X)表示目标函数,X表示决策变量,S表示可行域。

1.2 传统人工鱼群算法的描述

鱼群搜索食物的过程主要包括觅食、聚群和追尾三种行为。觅食表现在当鱼在它的视野范围内发现食物时,则朝该方向游动;聚群是每条鱼在游动过程中尽量地朝邻近伙伴的中心游动,并避免过分拥挤;追尾是指当某条鱼发现该处食物丰富时,其他鱼会快速尾随至此。

在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质比较丰富的地方,因而鱼聚集数目最多的地方往往是水域中营养丰富的地方。人工鱼群智能算法求解最优化问题就是模拟鱼群搜索食物过程的特点,把可行解域看成一片水域,函数在可行解域中的极值点视为水域中鱼群的食物源,函数值视为食物源的食物浓度。然后从构造单条人工鱼开始,通过模拟鱼的觅食、聚群和追尾行为,实现所有人工鱼聚集在食物源中心的附近,再比较相应食物源的浓度值,得出最优食物源,其对应位置的坐标就是最优化问题的解。

鱼的视野范围(记为Visual)是有限的。它在水域中随机游动,若在其视野范围内发现某点的食物浓度大于当前位置的食物浓度,则它会朝食物浓度大的点方向进行移动,移动的步长用step表示。游动到一定的程度,鱼在它的视野范围内可能有多条鱼,此时会产生聚群现象。若每一条鱼当前位置的食物浓度低于视野范围内鱼群的中心位置的浓度,鱼群的拥挤度不是太大,则鱼会朝中心位置移动;同时鱼群中的鱼还会有追尾现象发生,每一条鱼会探索其视野范围内最大食物浓度位置中的鱼,若拥挤度还没有达到极限位置,则鱼会朝最大食物浓度位置游动。

传统的人工鱼群算法经反复实验发现:决策变量X的维数增多时,算法的精度和收敛速度大大地降低了,无法得到全局最优解。实际问题中的许多待优化问题往往是高维的,如资源配送问题、线路设计问题等。因此本文在传统的鱼群算法基础上不断地给鱼群注入新的“生命”,动态修订鱼群拥挤度因子的上限值,更加符合自然界中鱼群的搜索食物的过程。改进后的鱼群算法称为自适应重生鱼群优化算法,适合大规模的优化问题的求解。

1.3 反向学习的基本概念

反向学习是智能搜索中的一种方法,已经被证明是随机搜索算法中的一种有效方法[14,15]。下面介绍反向学习中几个基本的概念。

1.3.1 反向数

定义1若x∈[a,b]是一维实空间R1中的点,则x的反向数x*=a+b-x。

1.3.1 反向点

定义2若p=(x1,x2,…,xn)是n维实空间上的一点,且xi∈[ai,bi],i=1,2,…,n,则p所对应的反向点p*(x1*,x2*,…,xn*),其中xi*=ai+bi-xi,i=1,2,…,n。

1.4 自适应重生鱼群优化算法

1.4.1 鱼群重生

鱼群重生是指每次迭代的开始根据上轮迭代所得的N个位置,生成这N个位置分别对应的反向点,重新得到N条人工鱼,给人工鱼注入新的生命,相当于产生新的N个位置。然后把N个位置与上轮迭代所得N个位置的食物浓度进行比较,选取食物浓度最大的前N个位置作为人工鱼的现处位置来参与进化,是对人工鱼的一种更佳的估计。每次迭代通过不断地给人工鱼注入“新生命”,丰富了种群的多样性,人工鱼的搜索范围扩大,跳出局部最优的机会增大,提高了算法获得全局最优的可能性。

1.4.2 动态拥挤度因子

拥挤度因子是用来刻画人工鱼群聚集的规模,拥挤度因子δ的设定是避免人工鱼过分地聚集在某个极值点的周围,使得人工鱼能够更广泛的寻优。传统的人工鱼群算法中把δ设定为一个常数,这样设计会影响算法的性能。若δ选取偏小,人工鱼在逼近极值的同时会避免过分拥挤而随机走开,或者受其他人工鱼的排斥作用,不能精确逼近极值点,且导致收敛速度很慢;若δ选取过大,容易陷入局部最优,致使算法出现停滞现象。

现引入动态拥挤度因δk来更加确切地模拟鱼搜索食物的过程。事实上,鱼群在寻找食物开始时,每条鱼在其视野范围内并不拥挤,为更广泛地搜索,避免鱼群过度集中,拥挤度因子δ应该取较小的值;随着鱼群搜索过程的继续,鱼群就会进行聚群和追尾行为,这时鱼的周围变得越来越拥挤,这时为保证最优食物源的周围有更多的鱼,避免因拥挤限制鱼群的聚集,δ应随着搜索的进行而增加。但是迭代后期,鱼群趋于成熟和稳定,鱼群容易陷入局部最优,致使算法停滞不前。这时为了提高人工鱼跳出局部最优的能力,我们应抑制鱼群的聚群和追尾行为,鼓励其进行觅食行为和随机游动,这时我们就要抑制δ的值并适当地降低。鉴于此,随着迭代次数k的不同,拥挤度因子δ也不同,即鱼群算法的拥挤度因子δ应该是迭代次数k的函数δk=δ(k)(δk称为动态拥挤度因子),且两者的函数关系大致如图1所示。

由此,鱼群算法中拥挤度因子的上限值δ修正为动态值δk。利用Matlab软件进行拟合,得到其变化规律可以利用正态分布来刻画,且拟合函数为:

其中m代表最大迭代次数。

鱼群算法经过上面两个方面的改进就称为自适应重生鱼群算法,其算法步骤为:

步骤1

设定每条人工鱼的视野范围为Visual,移动步长恒定为step,拥挤度因子为δ,最大迭代次数为m。

步骤2

初始化鱼群。在可行域S内随机生成N条人工鱼。第i条人工鱼的当前位置为Xi,其对应的食物浓度Yi(=-f(Xi))(i=1,2,…,N)。

步骤3

测定N条人工鱼在当前位置下的食物浓度Yi(1≤i≤N),记录食物浓度最大值Ymax和相应的位置Xmax,即作为公告板的初始记录(Xmax,Ymax)。

步骤4

鱼群重生。设这N条人工鱼当前位置为{X1,X2,…,XN},反向生成另外N条人工鱼的位置{X'1,X'2,…,X'N},且计算相应的食物浓度{Y1,Y2,…,YN}和{Y'1,Y'2,…,Y'N}。将{Y1,Y2,…,YN}和{Y'1,Y'2,…,Y'N}合在{Y1,Y2,…,YN,Y'1,Y'2,…,Y'N}进行比较,并取出其中前N个较大的食物浓度{Y1max,Y2max,…,YNmax}及它们所对应的人工鱼的位置{X1max,X2max,…,XNmax}。最后Ximax代替Xi即可(i=1,2,…,N)。

步骤5

动态拥挤度因子δk:

步骤6

聚群。设第i条人工鱼当前位置为Xi,探索其视野范围内的人工鱼的数目nif及中心位。如果(δk为拥挤度的上限值),则朝中心位置的方向按照式(1)前进一步,否则执行步骤8。

步骤7

追尾。设第i条人工鱼当前位置为Xi,探索其视野范围内的人工鱼中食物浓度最大的人工鱼Xj。如果Yj>Yi且,则朝人工鱼Xj的方向按照式(1)中的方法前进一步,否则执行步骤8。

步骤8

觅食。在人工鱼Xi的视野范围内随机选择一个位置Xj。若Yj>Yi,则朝Xj的方向按照式(1)中的方法前进一步,否则重新随机选择位置Xj,判断是否满足前进条件。若尝试Try_number次后仍不满足前进条件,则执行步骤9。

步骤9

随机移动。人工鱼在其可行域S内按照式(2)随机移动一步,产生一个新的位置Xnext。

步骤10

评估N条人工鱼现处位置下的食物浓度Y',并与公告板的初始记录进行比较。若Y'max≥Ymax,则更新公告板,否则不更新。

步骤11

用新确定的人工鱼位置,从步骤4开始重新搜索,直到迭代结束。

2 实验与仿真

2.1 高维优化函数极值问题

选择以下非线性优化函数来验证自适应重生鱼群优化算法的性能:

该非线性优化函数的全局最优解的周围分布着很多局部最优解。且容易看出,对任意的自然数n,该优化问题的最优解为X=0,最优值为1。

下面的仿真实验中,算法参数设置如下:人工鱼的数量为50,视野范围为1,移动步长为0.05,最大试探次数为50,最大迭代次数的设定:实验1为500次,实验2和3为50次。

实验1

图2为采用传统人工鱼群算法求解式(3)所得的最优值随维数n的变化曲线;图3为维数n=11时传统人工鱼群算法的寻优曲线。从图2可以看出随着维数n的增大,传统人工鱼群算法的最优值越来越偏离1,精度大大地降低。当维数n>5时,传统人工鱼群算法的求解误差≥0.25,所以其适用范围受到一定的局限性。且从图3中可以看出当维数n=11时,传统人工鱼群算法在迭代初期就陷入局部最优,始终无法跳出,所得的最优值0.366与1相差很大。

通过实验1可以得出:如果问题(3)要求求解误差≤0.25,则传统人工鱼群算法的适用范围为维数n≤5。但是实际的工程问题很复杂,所对应的优化问题的维数往往不止5。

实验2

图4-图6为自适应重生鱼群优化算法与传统的人工鱼群算法维数不同比较的仿真结果。图4表示当维数为2时,两种算法寻优曲线的比较。从图4可以看出虽然两种算法都能得到最优值,但改进后的人工鱼群算法比传统的人工鱼群算法的收敛速度快。图5表示当维数为5时,两种算法寻优曲线的比较。从图5可以看出当迭代次数为40次时,传统的人工鱼群算法已经陷入局部最优,并且所得的最优值0.87。但是自适应重生鱼群算法所得的最优值仍能逼近于1,求解精度比传统的人工鱼群算法高,且收敛速度快。图6表示当维数为11时,两种算法寻优曲线的比较。从图6可以看出传统的人工鱼群算法所求的最优值在0.4左右,与式(3)的最优值偏离很大,已经无法适用。但是自适应重生鱼群算法所得最优值仍保持在0.75以上,求解精度仍比传统的人工鱼群算法高。

通过实验2可以得出:本文自适应重生鱼群优化算法在收敛速度和全局寻优能力上都比传统的人工鱼群算法更佳,大大拓宽了人工鱼群算法的适用范围,在解决复杂的工程问题上更胜一筹。

实验3

图7为两种算法运行时间的比较结果。从图7可以看出在相同的迭代次数内,当维数n≥6时,两种算法的运行时间相当,也就是说,与传统人工鱼群算法相比,本文算法的复杂度并没有增加,说明本文提出的算法不仅复杂度没有增加,且各项性能都有大幅度的提高,在工程上适用范围广。

由此可以得出结论:处理高维优化函数问题时,自适应重生鱼群优化算法与传统人工鱼群算法相比,具有寻优速度快、精度高、复杂度相当等优点,成功地拓宽了其在工程上的应用。

2.2 旅行线路的优化

旅游线路的优化的问题是旅行商(TSP)问题的一种典型代表。近几年来对于TSP问题的求解提出了许多优化算法,其中仿生算法是研究的热点[9,10,11,12]。它具有传统算法不可替代的优势,如:非线性性、自组织性和并行性等。本文引用文献[13]中设计旅行线路为例,来直观地反映自适应重生鱼群优化算法与其他算法的优劣。

按照实数编码的原理,对各个城市进行重新编号。为验证本文算法的性能,同时引入遗传算法和传统的人工鱼群算法进行求解。此时的优化函数为城市之间的欧氏距离之和。相关参数设置如下:人工鱼数目为10;最大迭代次数:遗传算法为1500,传统和改进后的人工鱼群算法为500;最多试探次数为100;视野范围为6;移动步长为2;拥挤度因子为0.8(遗传算法与文献[13]的参数设置一致)。现设置出发点都为重庆,且必须经过每一个城市且仅一次,最后回到重庆。

由文献[13]可知,利用遗传算法得出的最优路线,所对应的最优值为18 997.8 km。采用传统的人工鱼群算法设计旅行路径的结果,其对应的最优值为18 596.9 km。从优化效果来看,传统人工鱼群算法的寻优效果比遗传算法的效果更好些。采用自适应重生鱼群优化算法设计旅行路径的结果。对应的线路安排如下:重庆—>贵州—>南宁—>海口—>澳门—>香港—>广州—>长沙—>合肥—>南京—>上海—>杭州—>台北—>福州—>南昌—>武汉—>郑州—>太原—>石家庄—>济南—>哈尔滨—>长春—>沈阳—>天津—>北京—>呼和浩特—>西安—>银川—>兰州—>西宁—>乌鲁木齐—>拉萨—>昆明—>成都—>重庆;所对应的最优值为17 595.3 km。从优化效果来看,自适应重生鱼群优化算法的寻优效果比遗传算法和传统的人工鱼群算法的效果都更佳。图8为自适应重生鱼群算法的寻优效果图。从寻优的速度来看,本文算法能够快速地找到较优路径,并且运行时间短。

通过三种算法的比较可以得出:本文在迭代过程中采用鱼群重生和利用正态分布调整拥挤度因子的思想设计所得的自适应重生鱼群优化算法,在实际的应用中能够得到更佳的效果,并且求解精度高,收敛速度快,成功地拓宽了传统的人工鱼群算法在工程上的应用。

3 结语

本文针对人工鱼群算法在处理高维优化函数时的缺点,提出了自适应重生鱼群算法。通过鱼群重生和利用正态分布动态调整拥挤度因子的结合,不仅每次迭代都给鱼群注入“新生命”,使鱼群得以重生,而且能自适应地调整鱼群的行为。实验表明:经自适应重生鱼群优化算法提高了求解高维优化函数的收敛速度和精度。最后为验证本文算法的有效性,将其用于34个城市旅游线路的优化,并与传统的人工鱼群算法和遗传算法相比。结果表明:本文算法寻优精度高,得到的线路最优,成功地拓宽了其在工程上的应用。

摘要：针对传统人工鱼群算法求解高维优化问题收敛速度较慢,易于陷入局部最优,提出自适应重生鱼群优化算法。首先在每次迭代过程中,不断地给鱼群注入“新生命”使鱼群得以重生;然后采用正态分布动态调整拥挤度因子的上限值使得算法更贴近于鱼群搜索食物的过程。实验结果表明,改进后的算法既保证收敛速度、增加算法获得全局最优的可能性,又适用于求解大规模的优化问题。其中的两个算例采用改进的鱼群算法进行优化,优化结果与实际具有良好的一致性,说明了改进算法的有效性和实用性。

自适应二阶震荡粒子群算法 篇8

关键词：粒子群优化算法,惯性权重,学习因子

粒子群算法是一种元启发式智能算法, 是由心理学家Kenndy和电气工程师Eberhart在1995年首次提出来的一种新型智能算法。它是受自然界中鸟群的群觅食行为的启发提出的进化计算技术。由于它概念简单、需要调节的参数少、容易实现, 已经受到了国内外学者的广泛关注, 并形成了一个研究热点。然而, 粒子群算法也有着对参数依赖性强、在搜索后期易陷入局部最优、寻优精度不高等缺点。文献将粒子群方程进行简化并添加了极值扰动算子, 极大的提高了收敛速度和收敛精度、有效摆脱局部极值点, 使得粒子群算法更加适实用。文献为了求解高维的复杂多峰值函数优化问题, 将审敛因子引入变邻域粒子群算法中, 有效地避免了标准粒子群算法在求解高维问题易陷入局部最优的缺, 提高了解的精度和收敛速度。文献针对标准粒子群算法易陷入局部最优、收敛精度差等缺点, 将所有粒子的个体最优位置进行选择、交叉、变异操作, 结果表明, 新算法提高了求解精度和求解效率。文献提出了一种新的惯性权重更新方式, 改善了算法的收敛速度和寻优精度, 并在位置更新后对最优粒子微扰, 防止陷入局部最优。我们在二阶震荡粒子群算法的基础上, 对算法的惯性权重、学习因子做了改进, 并在粒子群算法中省略了速度更新公式, 使得迭代方程由原来的二阶降为一阶, 粒子的迭代过程更为简单有效, 便于搜索和寻优。

1 基本粒子群算法

式中, ω为粒子更新的惯性权重值, 决定了上次飞行速度保留的程度。c1和c2为粒子的学习因子, 决定了粒子和个体最优位置和群体最优位置信息交流的程度。r1和r2是介于[0, 1]之间的随机数。

2 自适应二阶震荡粒子群算法

2.1 基于二阶震荡的简化粒子群算法

标准粒子群算法中所有粒子的更新仅仅依靠它的个体最优位置Pbest和全局最优位置Gbest, 并没有考虑到粒子个体之间及粒子位置变化对它自身的影响, 这样就使得粒子没有充分利用有效信息。因此, 我们提出了一种简化的二阶震荡粒子群更新方式:

改进后的二阶震荡粒子群算法省略了速度更新部分, 迭代方程由原来的二阶降为了一阶, 使得算法更加简单高效。并充分利用了所有粒子的个体最优位置的有效信息及同一粒子的位置变化信息, 进一步提高了算法的优化性能。

2.2 自适应调节的惯性权重

在粒子群算法中, 惯性权重ω是调整和平衡算法全局搜索能力和局部搜索能力的重要参数之一。若在算法的整个进化过程中ω取相同的值, 则算法很难平衡全局搜索和局部搜索之间的矛盾。而当ω在算法的不同阶段取合适的值时, 可以有效的平衡算法的局部和全局搜索能力。以前的研究表明, 如果惯性权重取较大的值, 则有助于提高算法的全局寻优能力, 不利于局部搜索;而如果惯性权重取较小的值, 则有利于算法的局部精细搜索, 提高算法的收敛精度, 但很容易陷入局部最优。线性递减的惯性权重虽然可以平衡算法全局搜索和局部搜索的矛盾, 但随着迭代次数的增加, 会造成算法后期局部搜索能力变差。因此, 在实际问题中, 如何选择合适的惯性权重, 是防止陷入局部最优且高效搜索的关键。这里, 我们提出了一种自适应的随机惯性权重, 即:

2.3 学习因子的自适应调节

在标准粒子群算法中, 两个学习因子的取值大小分别决定着粒子的“自身认知”和粒子群体的“社会认知”对粒子飞行轨迹的影响程度, 反映了种群中不同粒子之间的信息交流程度。若c1的值设置较大, 会使得所有粒子一直在自身的小范围内徘徊搜索;而c2的值设置较大, 则会使得粒子在迭代初期便已经陷入局部极值, 不利于算法的全局搜索。本文采用如下的更新方式:

3 算法流程

自适应二阶震荡粒子群算法的流程如下:

(1) 给定种群的规模ps, 最大迭代次数maxgen等参数, 随机初始化各粒子的位置;

(5) 判断给出的终止条件是否满足。若满足, 停止搜索, 输出需要的结果, 否则返回步骤 (3) 继续迭代。

4 仿真实验与性能分析

结合以上数值实验分析可知, APSO算法结构简单, 收敛速度快, 收敛精度高, 可以很好的寻找到最优解, 充分体现了APSO算法的优势。

5 结论

针对标准粒子群算法早熟、容易陷入局部最优位置、收敛精度差等缺点, 提出了自适应二阶震荡粒子群算法。在二阶震荡粒子群算法的基础上, 对算法的惯性权重、学习因子做了改进, 并在粒子群算法中省略了速度更新公式, 使得粒子的迭代过程更为简单高效, 便于搜索和寻优。最后, 通过实验证明了APSO算法的可行性和有效性。

参考文献

[1]Pan T S, Dao T K, Chu S C.Hybrid Particle Swarm Optimization with Bat Algorithm[M].Switzerland:Springer International Publishing, 2015:37-47.

[2]BAI Qinghai.Analysis of particle swarm optimization algorithm[J].Computer and Information Science, 2010, 3 (1) :p180.

[3]胡旺, 李志蜀.一种更简化而高效的粒子群优化算法[J]软件学报, 2007, 18 (4) :861-868.

自适应波束形成的SARLS算法 篇9

随着通信技术的不断发展和无线频带的拥挤,通信系统中的抗干扰问题变得越来越倍受人们的关注。自适应阵列由于具有自动感知干扰源的存在并可以自动抑制干扰,同时又具有增强有用信号的能力,因此在通信等方面作为降低干扰的一种手段被广泛研究[1]。智能天线(Smart Antenna)源于自适应阵列天线(AAA),最初应用于雷达、声纳、军事方面,主要用来完成空间滤波和定位,相控阵雷达就是一种自适应天线阵。另外,智能天线在移动通信系统中可以减小用户越区切换时发生强迫中断的概率,在CDMA通信系统中使用智能天线还可以进行智能功率控制。

自适应波束形成技术是智能天线的关键技术之一。目前,关于自适应波束形成已提出很多著名的算法,归纳起来,有最小均方算法(LMS)、直接矩阵求逆算法(DMI)、递归最小二乘(RLS)算法、遗传算法、方向图拓展和FFT结合的方法等。其中RLS算法兼有LMS算法和DMI算法的优点,有广泛的应用前景[2]。特别在CDMA通信系统中,通常为了使智能天线获得更好的分辨率和干扰对消效果,从而增大阵列的规模,但由此而带来计算量增加和收敛速度变慢成为2个突出的问题。因此,在保持自适应波束形成的优良性能的前提下,为了减少由阵列规模增加带来的计算量,寻找更快、更准确的自适应波束形成算法成为学者们研究的热点问题。本文给出了一种改进的RLS算法——子阵异步RLS算法(SARLS)。该方法可应用于基于广义旁瓣对消结构的智能天线波束形成结构,无需遵守每个子权矢量的维数必须大于信号源个数的限制。与文献[3]和[4]算法相比,本文提出的SARLS算法具有相近的自适应波束形成效果和收敛速度,但具有更简单明了的形式和更小的运算量。当总权系数的维数为N,标准的RLS的运算量为O(N2),而当子权矢量的维数较小时,本文提出的SARLS运算量为O(N),同时它具有更快的收敛速度。更值得一提的是,本文的算法在保持对期望信号良好接收的同时,能够很好地抑制到达方向与期望信号不同的干扰信号。

1 基于广义旁瓣对消结构波束形成系统

对于全自适应波束形成,简单起见,考虑阵元为无方向性天线,阵元总数为N的天线阵,其最优加权矢量$\stackrel{\rightharpoonup }{W}{}_{\text{o}\text{p}\text{t}}$由满足L维线性约束条件而使天线阵列输出功率最小的最优解确定。其数学模型为[4]:

式中,$\stackrel{\rightharpoonup }{W}$为权重向量,$\stackrel{\rightharpoonup }{X}(t)$为N维输入数据矢量,$Y(t)=\stackrel{\rightharpoonup }{W}{}^{\text{Τ}}\stackrel{\rightharpoonup }{X}(t)$为阵列输出,$\mathit{R}{}_{xx}=E[\stackrel{\rightharpoonup }{X}(t)\cdot \stackrel{\rightharpoonup }{X}{}^{\text{Η}}(t)]$为N×N维输入信号自相关矩阵,C为N×L维约束矩阵。$\stackrel{\rightharpoonup }{f}$为L个约束条件对应的L维响应矢量。这个问题的最优解为:

$\stackrel{\rightharpoonup }{W}{}_{\text{o}\text{p}\text{t}}=\mathit{R}{}_{xx}^{-1}\mathit{C}(\mathit{C}{}^{\mathbf{{\rm H}}}\mathit{R}{}_{xx}^{-1}\mathit{C}){}^{-1}\stackrel{\rightharpoonup }{f}$。 (2)

对于基于广义旁瓣对消结构的智能天线波束形成如图1所示,其阵列加权矢量为:

$\stackrel{\rightharpoonup }{W}=\stackrel{\rightharpoonup }{W}{}_{\text{q}}-B\stackrel{\rightharpoonup }{W}{}_{\text{a}}$。 (3)

当输入数据仅含有期望信号时,Rxx=K2I,I为单位阵,K为期望信号幅度,则由式(2)得:$\stackrel{\rightharpoonup }{W}{}_{\text{o}\text{p}\text{t}}=\mathit{C}(\mathit{C}{}^{\text{Η}}\cdot \mathit{C}){}^{-1}\stackrel{\rightharpoonup }{f}$。为使期望信号的归一化增益为1,静态N维权矢量为$\stackrel{\rightharpoonup }{W}{}_{\text{q}}=\mathit{C}(\mathit{C}{}^{\text{Η}}\mathit{C}){}^{-1}\stackrel{\rightharpoonup }{f}‚\mathit{B}$为N×(N-L)维信号阻塞矩阵,且满足BHC=0。这样,$\stackrel{\rightharpoonup }{W}{}_{\text{a}}$的选择只需满足:

$\min (\stackrel{\rightharpoonup }{W}{}_{\text{q}}-\mathit{B}\stackrel{\rightharpoonup }{W}{}_{\text{a}}){}^{\text{Η}}\mathit{R}{}_{xx}(\stackrel{\rightharpoonup }{W}{}_{\text{q}}-\mathit{B}\stackrel{\rightharpoonup }{W}{}_{\text{a}})$。 (4)

这样去掉了式(1)中的限制条件。则由式(4)得:$\stackrel{\rightharpoonup }{W}{}_{\text{a}\text{o}}=\mathit{R}{}_{\text{u}\text{u}}^{-1}\stackrel{\rightharpoonup }{{\rm P}}‚$其中$R{}_{\text{u}\text{u}}=\mathit{B}{}^{\text{Η}}\mathit{R}{}_{xx}\mathit{B}‚\stackrel{\rightharpoonup }{{\rm P}}=\mathit{B}{}^{\text{Η}}\mathit{R}{}_{xx}\stackrel{\rightharpoonup }{W}{}_{\text{q}}$。

2 RLS算法与SARLS算法

2.1RLS算法

递推最小二乘(RLS)算法是为了实现快速收敛,而使用了含有附加参数的算法,与LMS算法使用统计逼近相比,使用最小平方逼近将会获得更快的逼近。也就是说,快速的收敛算法依赖于实际收到信号的时间平均的误差表达式,而不是统计平均的误差表达式。

基于时间平均的最小平方误差被定义如下:$J(n)={\displaystyle \sum _{i=1}^n\lambda }{}^{n-i}e{}^{*}(i)e(i)$,式中,n为时间采样数,λ为接近1,但小于1的加权因子,e(i)为误差信号在i时刻的值,e*(i)是e(i)的共轭复数。为使J(n)的值最小,则有:$\partial J(n)/\partial \stackrel{\rightharpoonup }{W}(n)=0$,从而可得:

$[{\displaystyle \sum _{i=1}^n\lambda }{}^{n-i}\stackrel{\rightharpoonup }{x}(i)\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(i)]\stackrel{\rightharpoonup }{W}(n)={\displaystyle \sum _{i=1}^n\lambda }{}^{n-i}\gamma (i)\stackrel{\rightharpoonup }{x}(i)$。 (5)

定义输入自相关矩阵Rxx和互相关向量$\stackrel{\rightharpoonup }{r}{}_{x\gamma }$在某一时刻n分别为:

$\begin{array}{l}\mathit{R}{}_{xx}(n)={\displaystyle \sum _{i=1}^n\lambda }{}^{n-i}\stackrel{\rightharpoonup }{x}(i)\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(i),\\ \stackrel{\rightharpoonup }{r}{}_{x\gamma }(n)={\displaystyle \sum _{i=1}^n\lambda }{}^{n-i}\gamma (i)\stackrel{\rightharpoonup }{x}(i)。(6)\end{array}$

则式(5)可写为:

$\stackrel{\rightharpoonup }{W}(n)=[\mathit{R}{}_{xx}(n)]{}^{-1}$r$\stackrel{\rightharpoonup }{{\displaystyle }}{}_{x\gamma }(n)$。 (7)

另外,由式(6)可得Rxx(n)的递推公式为:

$\mathit{R}{}_{xx}(n)=\lambda \mathit{R}{}_{xx}(n-1)+\stackrel{\rightharpoonup }{x}(n)\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)$,利用方阵求逆引理可得:

$\mathit{R}{}_{xx}^{-1}(n)=\frac{1}{\lambda }\left[\mathit{R}{}_{xx}^{-1}(n-1)-\frac{\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\mathit{R}{}_{xx}^{-1}(n-1)}{\lambda +\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)}\right]$。 (8)

根据上述递推公式,可知:

$\stackrel{\rightharpoonup }{W}(n)=\stackrel{\rightharpoonup }{W}(n-1)+\stackrel{\rightharpoonup }{k}(n)e{}^{*}(n-1)$。 (9)

式中,$\stackrel{\rightharpoonup }{k}(n)=\frac{\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)}{\lambda +\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)}$。

因此,RLS算法可以总结如下:① 初始化:$\stackrel{\rightharpoonup }{W}(0)=\stackrel{\rightharpoonup }{k}(0)=\stackrel{\rightharpoonup }{x}(0)=0‚\mathit{R}{}_{xx}^{-1}(0)=\delta \mathit{{\rm I}}{}_{{\rm N}{\rm N}}$,式中,INN是N×N单位矩阵,且δ是一个数值很大的正常数;② 按下列方程进行递推计算:

$e(n)=\gamma (n)-\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\stackrel{\rightharpoonup }{W}(n-1)$, (10)

$\stackrel{\rightharpoonup }{k}(n)=\frac{\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)}{\lambda +\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\mathit{R}{}_{xx}^{-1}(n-1)\stackrel{\rightharpoonup }{x}(n)}$, (11)

$\mathit{R}{}_{xx}^{-1}(n)=\frac{1}{\lambda }\left[\mathit{R}{}_{xx}^{-1}(n-1)-\stackrel{\rightharpoonup }{k}(n)\stackrel{\rightharpoonup }{x}{}^{\text{Η}}(n)\mathit{R}{}_{xx}^{-1}(n-1)\right]$, (12)

$\stackrel{\rightharpoonup }{W}(n)=\stackrel{\rightharpoonup }{W}(n-1)+\stackrel{\rightharpoonup }{k}(n)e{}^{*}(n)$。 (13)

迭代式中的λ是一个反映算法性质的参量,称之为遗忘因子,其作用是削弱旧的数据点对后期计算的影响。通常0.8≤λ≤1,其物理意义是在求权重向量时所用到的输入信号中,对时间较近的数据加以较大的权来考虑,时间较前的数据,其权按指数律减小,从而加强对非平稳信号的适应性。

2.2SARLS算法

对RLS算法的原始公式(10)～(13)稍作改变得:

$e(n)=\gamma (n)-[d(n)-\stackrel{\rightharpoonup }{W}{}^{\text{Η}}(n-1)\stackrel{\rightharpoonup }{u}(n)]$, (14)

$\stackrel{\rightharpoonup }{k}(n)=\frac{\mathit{R}{}_{\text{u}\text{u}}^{-1}(n-1)\stackrel{\rightharpoonup }{u}(n)}{\lambda +\stackrel{\rightharpoonup }{u}{}^{\text{Η}}(n)\mathit{R}{}_{\text{u}\text{u}}^{-1}(n-1)\stackrel{\rightharpoonup }{u}(n)}$, (15)

$\mathit{R}{}_{\text{u}\text{u}}^{-1}(n)=\frac{1}{\lambda }\left[\mathit{R}{}_{\text{u}\text{u}}^{-1}(n-1)-\stackrel{\rightharpoonup }{k}(n)\stackrel{\rightharpoonup }{u}{}^{\text{Η}}(n)\mathit{R}{}_{\text{u}\text{u}}^{-1}(n-1)\right]$, (16)

$\stackrel{\rightharpoonup }{W}(n)=\stackrel{\rightharpoonup }{W}(n-1)+\stackrel{\rightharpoonup }{k}(n)e{}^{*}(n)$, (17)

式中,n为迭代时间步,λ为接近1、但小于1的加权因子。则计算子权矢量的RLS算法(SARLS)为:

$\stackrel{\rightharpoonup }{W}{}_i(n)=\stackrel{\rightharpoonup }{W}{}_i(n-1)+\stackrel{\rightharpoonup }{k}{}_i(n)e{}_i^{*}(n)$; (18)

$\begin{array}{l}\text{式}\text{中}‚e{}_i(n)=\gamma {}_i(n)-[d{}_i(n)-\\ \stackrel{\rightharpoonup }{W}{}_i{}^{\text{Η}}(n-1)\stackrel{\rightharpoonup }{u}{}_i(n)]。\end{array}$

实际中求解的困难在于γi(n)-di(n)是未知的。真正的γi(n)-di(n)为[3]:

$\gamma {}_i(n)-d{}_i(n)=\gamma (n)-[d(n)-{\displaystyle \sum _{j=1,j\ne i}^{{\rm M}}\stackrel{\rightharpoonup }{W}}{}_j{}^{\text{Η}}\stackrel{\rightharpoonup }{u}{}_j(n)],$

则有:

$e{}_i(n)=\gamma (n)-d(n)+{\displaystyle \sum _{j=1,j\ne i}^{{\rm M}}\stackrel{\rightharpoonup }{W}}{}_j{}^{\text{Η}}\stackrel{\rightharpoonup }{u}{}_j(n)+\stackrel{\rightharpoonup }{W}{}_i{}^{\text{Η}}(n-1)\stackrel{\rightharpoonup }{u}{}_i(n)$。 (19)

式中,$\stackrel{\rightharpoonup }{W}{}_j$为稳态权矢量的第j个子权矢量。考虑到在实际递推过程中,用瞬时权矢量代替稳态权矢量,则有:

$\begin{array}{l}e{}_i(n)=\gamma (n)-d(n)+{\displaystyle \sum _{j=1}^{i-1}\stackrel{\rightharpoonup }{W}}{}_j{}^{\text{Η}}(n)\stackrel{\rightharpoonup }{u}{}_j(n)+\\ {\displaystyle \sum _{j=i}^{{\rm M}}\stackrel{\rightharpoonup }{W}}{}_j{}^{\text{Η}}(n-1)\stackrel{\rightharpoonup }{u}{}_j(n),(20)\end{array}$

从而可以得出SARLS算法的迭代形式为:

$\stackrel{\rightharpoonup }{k}{}_i(n)=\frac{\mathit{R}{}_{ii}^{-1}(n-1)\stackrel{\rightharpoonup }{u}{}_i(n)}{\lambda +\stackrel{\rightharpoonup }{u}{}_i{}^{\text{Η}}(n)\mathit{R}{}_{ii}^{-1}(n-1)\stackrel{\rightharpoonup }{u}{}_i(n)}$。 (21)

$\mathit{R}{}_{ii}^{-1}(n)=\frac{1}{\lambda }\left[\mathit{R}{}_{ii}^{-1}(n-1)-\stackrel{\rightharpoonup }{k}{}_i(n)\stackrel{\rightharpoonup }{u}{}_i{}^{\text{Η}}(n)\mathit{R}{}_{ii}^{-1}(n-1)\right]$。 (22)

$e{}_1(n)=\gamma (n)-d(n)+{\displaystyle \sum _{j=1}^{{\rm M}}\stackrel{\rightharpoonup }{W}}{}_j{}^{\text{Η}}(n-1)\stackrel{\rightharpoonup }{u}{}_j(n)\cdots \cdots$;

$e{}_{i+1}(n)=e{}_i(n)+[\stackrel{\rightharpoonup }{W}{}_i(n)-\stackrel{\rightharpoonup }{W}{}_i(n-1)]{}^{\text{Η}}\stackrel{\rightharpoonup }{u}{}_i(n)$; (23)

$\stackrel{\rightharpoonup }{W}{}_i(n)=\stackrel{\rightharpoonup }{W}{}_i(n-1)+\stackrel{\rightharpoonup }{k}{}_i(n)e{}_i^{*}(n)$。 (24)

通常0.8≤λ≤1。相对于文献[3]和[4]的递推算式,这里的算法形式相对简单,易于理解。

2.3RLS算法与SARLS算法的计算复杂度对比

计算式(21)和(22)的运算量分别为${\displaystyle \sum _{i=1}^{{\rm M}}(}{\rm N}{}_i^2+2{\rm N}{}_i)$和${\displaystyle \sum _{i=1}^{{\rm M}}(}{\rm N}{}_i^2+{\rm N}{}_i)$次的复数乘法(CM);计算式(23)的运算量为${\displaystyle \sum _{i=1}^{{\rm M}}{\rm N}}{}_i+{\displaystyle \sum _{i=2}^{{\rm M}}{\rm N}}{}_i=2({\rm N}-L)-{\rm N}{}_1$次CM;计算式(24)的运算量为${\displaystyle \sum _{i=1}^{{\rm M}}{\rm N}}{}_i=({\rm N}-L)$次CM;总共计算量为${\displaystyle \sum _{i=1}^{{\rm M}}2}{\rm N}{}_i^2+6({\rm N}-L)-{\rm N}{}_1$次CM。Kalman准RLS算法的运算量为2.5(N-L)2+4.5(N-L)[5],文献[3]算法的运算量为${\displaystyle \sum _{i=1}^{{\rm M}}2}{\rm N}{}_i^2+6({\rm N}-L)+{\rm M}$,文献[4]算法的运算量为${\displaystyle \sum _{i=1}^{{\rm M}}2}{\rm N}{}_i^2+6({\rm N}-L)+{\rm M}{}^3/2+{\rm M}{}^2$。假设对N进行均匀分解,即Ni=(N-L)/m,i=1,2,…,M,本算法的运算量为$\frac{2({\rm N}-L){}^2}{{\rm M}}+6({\rm N}-L)-\frac{{\rm N}-L}{{\rm N}}$,文献[3]算法为$\frac{2({\rm N}-L){}^2}{{\rm M}}+6({\rm N}-L)+{\rm M}$,文献[4]算法运算量为$\frac{2({\rm N}-L){}^2}{{\rm M}}+6({\rm N}-L)+{\rm M}{}^3/2+{\rm M}{}^2$。当N-L=48时,以上各算法的运算量随M的变化如图2所示。其中本算法的运算量除了比文献[3]少${\rm M}+\frac{{\rm N}-L}{{\rm M}}$次外,随着M的增大,运算量要远远小于其他2种算法。

3实例仿真

实验1:采用图1所示的基于广义旁瓣对消结构的智能天线波束形成结构,线性均匀分布阵列,阵元间距半个波长,总阵元数为N=16,自适应权矢量维数为N-L=15。信号阻塞矩阵B的取值为:

各阵元噪声为加性高斯白噪声。期望信号的入射方向为0°,信噪比为0 dB,对应的方向矢量为Sd=[1,1,1,…1] T,要求对期望信号方向的接收增益(归一化值)为1。初始值$\stackrel{\rightharpoonup }{W}{}_i(1)$和R${}_{ii}^{-1}$分别为零矢量和δI,δ为10 000,I为Ni×Ni维单位阵,遗忘因子λ为0.99。实验中采用均匀分解,各子阵的维数相同,其中M=3、Ni=5。

情况1:只有一个干扰信号,其入射角度为54°,INR为20 dB。图3给出了采用Kalman RLS算法和SARLS算法的方向图。

情况2:同时有3个干扰信号,其入射角度分别为14°、22°和44°。INR分别为20 dB、20 dB和60 dB。图4为采用Kalman RLS算法和SARLS算法的方向图。

实验2:采用圆形均匀分布阵列,总阵元数为N=16,自适应权矢量维数为N-L=15,圆阵周长与波长之比为2πr/λ=8。各阵元噪声为加性高斯白噪声。期望信号的入射方向为φ=90°、θ=0°,即高低角与方位角均为0°,信噪比为0 dB,要求对期望信号方向的接收增益(归一化值)为1。则期望信号对应的方向矢量为:

式中,$\theta {}_i=\frac{2(i-1)\text{π}}{16}$,初始值$\stackrel{\rightharpoonup }{W}{}_i(1)$和R${}_{ii}^{-1}$分别为零矢量和δI,δ为10 000,I为Ni×Ni维单位阵,遗忘因子λ为0.99。实验中采用均匀分解,各子阵的维数相同,其中M=3,Ni=5。

情况1:只有1个干扰信号,其入射角度为-55°,INR为20 dB。图5给出了采用Kalman RLS算法和SARLS算法的零方向图。

情况2:同时有3个干扰信号,其入射角度分别为80°、35°和-40°。INR分别为20 dB、40 dB和60 dB。图6为采用Kalman RLS算法和SARLS算法的方向图。

4结束语

本文利用子阵异步递推处理的思想,给出了用于自适应波束形成的SARLS算法。该算法不但具有计算量小、收敛快的优点,而且对干扰的抑制效果也明显优于传统的Kalman RLS算法,在阵列规模较大时,应用SARLS算法将具有明显的优势。

参考文献

[1]葛利嘉.智能天线及其在军用软件无线电中的应用[J].军事通信技术,1995,18(2):1-16.

[2]盛严慈,金荣洪.基于方向图拓展和FFT的阵列快速综合法[J].电波科学学报,2003,18(5):540-544.

[3]汤俊,彭应宁.一种RLS型快速波束形成算法[J].信号处理,1999,15(4):341-345.

[4]YUShiann-jeng,LEE Ju-hong.Adaptive array beamforming based on an efficient technique[J].IEEE Trans.Antennas Propagation,1996,AP-44(8):1094-1101.

盲源分离自适应算法的改进 篇10

盲源分离技术是指在不知道源信号的分布,又不知道源信号的混合模型的情况下,利用一组已知的源信号的混合模型来恢复或提取独立的源信号的技术。通常,信号源盲分离算法[1,2,3]是按照以下步骤 :首先,将观测到的混迭语音信号进行解相关,通常由主分量分析(PCA)来实现;然后,通过独立分量分析(ICA)算法找到合适的旋转矩阵,再将解相关后的数据旋转到正确的方向上去。这种算法往往要通过信号源概率密度函数定义函数评价,由于信号源未知,只能采取非线性函数代替信号的评价函数。理想的非线性函数取决于未知信号源的统计特性,主要是信号的峭度[4],把峭度小于和大于零的信号分别称为亚高斯信号和超高斯信号,然而这两种函数需要选取不同的非线性函数,所以对混合信号中同时存在亚高斯和超高斯的杂系混合情况时,简单利用非线性函数代替信号评价函数的算法就无法实现盲分离。

本文统一了不同盲源分离自适应算法,并采用该统一形式中的非线性函数的稳定性原则[5],兼顾算法分离性能、鲁棒性及收敛速率等择优准则,选取三种不同的非线性函数[6]分离两个混叠语音信号进行实验,并对其中一种函数进行算法上的改进。

1 盲分离问题描述

设n个相互独立的原始信号向量s(t)=[s1(t),s2(t),…,sn(t)]T,m个传感器的测量信号为x(t)=[x1(t),x2(t),…,xm(t)]T,则盲信号的混合模型可以表示为:

x(t)=As(t)+n(t) (1)

式中A为未知瞬态线形混合矩阵,n(t)=[n1(t),n2(t),…,nm(t)]T为附加噪声,盲分离的目的是从混合信号x(t)中恢复原信号s(t),即计算分离矩阵W,使其输出:

y(t)=Wx(t) (2)

为原始信号矢量s(t)的一个估计。

2 盲分离自适应算法

常见的盲分离算法, 通常提出以分离矩阵W为因变量的对照函数 , 对照函数反映了输出随机矢量的各分量之间的独立性[7]。通过对函数最大化或最小化就可以求解分离矩阵W。

设y(t)=Wx(t)为对原始信号的估计, 并设q(y)为与W有关的概率密度函数, 选取独立的概率密度函数:

q(y)=∏q(yi) (3)

信号源盲分离的极大似然法采用如下定义的对照函数:

$L(y,W)=-0.5\log [\det (W){}^{{\rm T}}]-{\displaystyle \sum _{i=1}^m\log }q(y{}_i)(4)$

研究表明许多基于对照函数的信号源盲分离方法, 包括累积量最小化法和熵最大化法都可以看作是极大似然法的特例。信号源盲分离问题存在两个内在的解的不确定性,一个是排列顺序的不确定性, 即无法了解所抽取的信号是原始信号矢量中的哪一个分量,另一个是信号幅度的不确定性, 即无法恢复信号波形的真实幅值。但由于信息主要包含在信号的波形中,所以这两种不确定性并不影响盲分离技术的应用。

混合信号的评价函数定义为:

$\phi (y{}_i)=\frac{-d\text{l}\text{o}\text{g}p(y{}_i)}{dy{}_i}(5)$

其中p(yi)为概率密度函数,利用相对梯度的概念对式(4)的对照函数进行优化,可以得到如下著名的EASI算法:

ΔW=η{I-yyT-φ(y)yT+yφ(y)}W (6)

其中η为学习常数,I为单位矩阵,分离矩阵W一般初始化为单位矩阵。评价函数φ(yi)在实际计算时用适当的非线性函数代替。式(6)是一种随机梯度算法,可以用样本平均代替瞬时相对梯度, 得到如下的样本平均EASI算法:

ΔW=η{I-〈yy〉T-〈φ(y)yT〉+〈yφ(y)〉}W (7)

其中〈·〉表示样本平均运算。这类算法的分离能力与混合矩阵无关, 具有非常良好的特性。

2.1 概率密度函数的非参数估计方法

在EASI算法中, 需要根据源信号是超高斯信号还是亚高斯信号来选择不同的评价函数,由于不存在同时适用于两种类型信号的评价函数,因此,算法无法分离同时存在超高斯信号和亚高斯信号的杂系混合信号。为解决这一问题,可以直接对源信号的概率密度函数进行估计,并用对概率密度函数的估计结果来替代EASI算法中的评价函数,成功地实现了杂系混合信号的分离[8]。概率密度函数估计的常用方法是参数化的方法,但是由于这种方法要求知道待估计函数的参数模型,因此不适用于信号源未知的盲分离问题。而采用另外一种密度函数的估计方法,即非参数估计的方法解决此问题。

给定独立同分布随机变量X的一组实现X1,X2,…,Xn,则X的概率密度函数可以由下式估计:

$\stackrel{\wedge }{{\displaystyle p{}_h(x)}}=(nh){}^{-1}{\displaystyle \sum _{i=1}^n{\rm K}}[(x-X{}_i)/h](8)$

其中,h称为“带宽”, K称为核函数。

若将概率密度函数估计的导数作为概率密度函数导数的估计, 即:

$\stackrel{\wedge }{{\displaystyle p}}{}_{h^{\prime }}(x)=[\stackrel{\wedge }{{\displaystyle p}}{}_h(x){]}^{\prime }(9)$

对常见的核函数, 包括高斯核函数, 式(8)和式(9)的估计都是一致和渐进无偏的。

式(8)和式(9)的方法称为概率密度函数估计的核函数方法,在这种估计方法中,带宽的选择比核函数的选择重要得多。若带宽选择过小,则估计出的概率密度函数图线将会出现伪峰,若带宽过大则会使估计结果过于平滑而掩盖掉某些重要的特征。

2.2 盲源分离自适应算法的统一形式

信息最大化法(Infomax)是Bell 和BSejnowski基于Linskers的信息最大化理论提出的一种盲源分离方法[9]。该方法的主要思路是寻找分离矩阵W,使得以u(t)为输入的非线性函数g(u)的输出y=g(u)的联合熵H(Y)最大,计算矩阵W的自适应算法如下:

$\Delta W\propto \left(W{}^{{\rm T}}\right){}^{-1}-2yx{}^{{\rm T}}(10)$

式中非线性函数为y=g(u)=tanh(u),由于该非线性函数与超高斯型源信号的累积分布相匹配,所以适于分离超高斯型源信号。

Amari提出了自然梯度,应用自然梯度优化后的 Infomax 算法如下:

$\Delta W\propto [\left(W{}^{{\rm T}}\right){}^{-1}-2yx{}^{{\rm T}}]\cdot W{}^{{\rm T}}W=({\rm I}-2yu{}^{{\rm T}})W(11)$

若记:

φ(u)=2y=2tanh(u) (12)

则式(11)可以表示为:

ΔW∝[I-φ(u)uT]W (13)

称式(13)为盲源分离自适应学习算法的统一形式。该统一形式具有优秀的等变性,即算法的分离性能与混合矩阵A无关。

尽管不同的盲源分离自适应算法的基本原理和出发点不同,但它们之间具有非常密切的联系。它们的区别在于不同的算法选取了不同的非线性函数φ(u),或者分离的对象有所不同。盲源分离算法的主要目标是能够得到正确的分离结果。因此,如何选取算法中的非线性函数φ(u)是极为重要的问题。

2.3 非线性函数的选取

对于盲源分离自适应算法的统一形式,非线性函数φ(u)不必与原信号的概率密度分布精确匹配,当二者存在一定的误差时,这样的φ(u)仍能保证算法的稳定性。但是,非线性函数φ(u)与源信号分布的不匹配程度存在一个限度。

在实际应用中,通常要求算法不但具有良好的分离性能,而且要有较好的抗干扰性和实时性。因此,选取最佳非线性函数时,除了考虑算法的分离性能外,还需兼顾算法的鲁棒性和收敛速率等其他因素,即要采取非线性函数的综合择优准则。

2.4 非线性函数的改进

语音信号属于超高斯型信号的情况下,满足稳定性条件的非线性函数φ(u),或者说与超高斯型源信号的分布基本匹配的φ(u)为S形函数。

一般有以下3种不同的S形函数:

$\phi (u)=\tanh (u)\phi (u)=\frac{1}{1+e{}^{-u}}\phi (u)=\arctan (u)$

不同算法的分离性能可通过噪信比来比较,噪信比的定义式如下:

${\rm N}SR=\frac{[(WA){}_{ij}]{}^{2}E[S{}_j^2]}{[(WA){}_{ii}]{}^{2}E[S{}_i^2]}i\ne j(14)$

假设信号源为单位方差,则有:

${\rm N}SR=\frac{[(WA){}_{ij}]{}^2}{[(WA){}_{ii}]{}^2}i\ne j(15)$

在分别选取不同的非线性函数的情况下,盲源分离自适应法的统一形式均能够正确分离两路混叠的语音,只是算法的分离性能和收敛时间有所区别。

为了获得更优的性能,对于最后选定的非线性函数,可进行参数细调,将arctan(u)修正为arctan(uα),即将非线性函数改为:

φ(u)=arctan(uα) (16)

改变α,再测试性能,根据语音分离的通道均衡性好坏程度决定α,使得语音信号分离噪信比较好。

3 实验结果及分析

应用统一形式的盲源分离自适应算法,进行两路混叠语音信号的分离实验。两个实验采用纯净语音源信号,语音的采样率取为11kHz,每路语音各取50000点数据。混合矩阵A选取为[-1,1]均匀分布的随机矩阵。

实验主要测试并比较了在不同的非线性函数下算法的分离噪信比和算法收敛时间,测试结果见表1,表1的数据表明,在分别选取 3种不同的非线性函数的情况下,盲源分离自适应算法的统一形式均能够正确分离两路混叠的语音信号,只是算法的分离性能和收敛时间有所区别。

在所选取的 3 种非线性函数中,只有φ(u)=tanh(u)符合算法的推导关系,其他非线性函数均已打破与 Infomax 算法中目标函数的因果关系,这就验证了不必与源分布精确匹配。在满足稳定性的前提下,选取最佳的非线性函数。从表1可以看出,φ(u)=arctan(u)为这三种函数中的最优函数。

对函数φ(u)=arctan(uα)进行微调,测试在α取不同值的条件下噪信比及分离时间,实验结果如表2所示。

实验结果表明,在选择非线性函数φ(u)=arctan(uα)的情况下,信号分离的噪信比都比较好,收敛时间的差别也不大,所以在语音分离通道均衡性好时,可将arctan(u2.3)作为最佳选择。

4 结 论

本文采用统一的盲源分离自适应算法,为保证算法统一形式的稳定性,选取和调整非线性函数, 使其满足稳定性原则。实验证明,打破原有算法中非线性函数与目标函数之间的因果关系,按照算法分离性能和分离时间进行非线性函数的综合择优,经参数细调所得到的分离效果更好。

摘要：指出了盲源分离自适应算法之间的联系,在满足多种性能择优标准前提下,引入了改进的非线性函数,该函数有效地实现了语音信号的盲分离,同时也提高了算法的收敛速度,实验表明该方法能够更快速地分离混迭语音。

关键词：自适应算法,盲源分离,非线性函数,算法的稳定性

参考文献

[1] Arie Yeredor. Blind source separation via the second characteristic function [J]. Signal Processing, 2000,80:897-902.

[2] Hyva Rinen A,Karhunen J.Independent Component Analysis [M].New York:Wiley,2001.

[3]Aykin HS.Unsupervised Adaptive Filtering,vol I:Blind Source Sepa-ration M.New York:Wiley,2000.

[4]Erdogmus D,Rao Y N,Priciple J C.Simultaneos extraction of pricinple components Using givens rotations and output variances[A].IEEE In-ternational Conferance on Acoustic,SpeechandSignalProcessing,Orlan-do,FL USA:IEEE,2002,1:121069-121072.

[5] Leetw,Girolamim,Bell A J,et al.A unifying information theoretic framework for independent component analysis [J].Comput &Math Appl,2000(39):1-21.

[6]Cardoso J F.The three easy routes to independent component analysis;contrasts and Geometry[A].Proceedings of the3rd International Con-ference on Inerpendent Component Analysis and BL IND Signal Sepa-ration,San Diego:[s,n],2001.

[7] Parra L,Spence C.Convolutive blind separation of non-stationary sources[J].IEEE Trans.Speech Audio Processing,2000(893):320-327.

[8] ICA-CNL.http://www.cnl.salk.edu/～tewon,2004,5.