2011年 第37卷 第3期
2011, 37(3): 257-269.
doi: 10.3724/SP.J.1004.2011.00257
摘要:
骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.
骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.
2011, 37(3): 270-275.
doi: 10.3724/SP.J.1004.2011.00270
摘要:
提出一种新的基于均匀非周期B样条曲线模型的结构化道路检测算法. 算法首先利用Canny边缘检测算法提取道路边缘, 然后使用最小二乘法拟合道路标识线, 最后利用所提取的道路标识线求取道路中央线, 进而完成道路拟合. 为了准确定位道路弯道位置, 算法运用最大转向偏差定位(Maximum deviation of position shift, MDPS)方法求解道路模型控制点. 实验证明该算法快速、稳定、灵活, 可以满足智能导航的要求.
提出一种新的基于均匀非周期B样条曲线模型的结构化道路检测算法. 算法首先利用Canny边缘检测算法提取道路边缘, 然后使用最小二乘法拟合道路标识线, 最后利用所提取的道路标识线求取道路中央线, 进而完成道路拟合. 为了准确定位道路弯道位置, 算法运用最大转向偏差定位(Maximum deviation of position shift, MDPS)方法求解道路模型控制点. 实验证明该算法快速、稳定、灵活, 可以满足智能导航的要求.
2011, 37(3): 276-282.
doi: 10.3724/SP.J.1004.2011.00276
摘要:
针对压缩传感(Compressed sensing, CS)理论中迭代硬阈值(Iterative hard thresholding, IHT)算法迭代次数多和时间长的问题, 提出基于回溯的迭代硬阈值算法(Backtracking-based iterative hard thresholding, BIHT), 该算法通过加入回溯的思想, 优化了IHT算法迭代支撑的选择, 减少支撑被反复选择的次数. 模拟实验表明, 在保证重建质量的前提下, 相比较于IHT和正规化迭代硬阈值(Normalized IHT, NIHT)算法, BIHT算法的重建时间降低了2个数量级. 用本身稀疏的0-1随机信号的重建实验表明, 若测量次数和稀疏度相同, BIHT算法的重建概率高于IHT算法.
针对压缩传感(Compressed sensing, CS)理论中迭代硬阈值(Iterative hard thresholding, IHT)算法迭代次数多和时间长的问题, 提出基于回溯的迭代硬阈值算法(Backtracking-based iterative hard thresholding, BIHT), 该算法通过加入回溯的思想, 优化了IHT算法迭代支撑的选择, 减少支撑被反复选择的次数. 模拟实验表明, 在保证重建质量的前提下, 相比较于IHT和正规化迭代硬阈值(Normalized IHT, NIHT)算法, BIHT算法的重建时间降低了2个数量级. 用本身稀疏的0-1随机信号的重建实验表明, 若测量次数和稀疏度相同, BIHT算法的重建概率高于IHT算法.
2011, 37(3): 283-289.
doi: 10.3724/SP.J.1004.2011.00283
摘要:
提出一种新的基于提升Directionlet变换的图像压缩算法, 能有效捕捉图像中的多方向各向异性特征, 并具备格形可分离的滤波和采样结构. 利用四叉树分块寻找局部最优的变换方向, 针对Directionlet变换系数分布构造了块集合分裂嵌入编码, 并通过改进链表排序方式和设计新的上下文算术编码器, 进一步提高压缩性能. 仿真实验结果表明, 与基于原始Directionlet变换的压缩算法和基于小波变换的SPECK, SPIHT, JPEG 2000等经典算法相比, 本文算法在性能参数和视觉效果方面均有较大提高, 且在低比特率下仍能较完整地保留图像中的边缘和细节信息.
提出一种新的基于提升Directionlet变换的图像压缩算法, 能有效捕捉图像中的多方向各向异性特征, 并具备格形可分离的滤波和采样结构. 利用四叉树分块寻找局部最优的变换方向, 针对Directionlet变换系数分布构造了块集合分裂嵌入编码, 并通过改进链表排序方式和设计新的上下文算术编码器, 进一步提高压缩性能. 仿真实验结果表明, 与基于原始Directionlet变换的压缩算法和基于小波变换的SPECK, SPIHT, JPEG 2000等经典算法相比, 本文算法在性能参数和视觉效果方面均有较大提高, 且在低比特率下仍能较完整地保留图像中的边缘和细节信息.
2011, 37(3): 290-302.
doi: 10.3724/SP.J.1004.2011.00290
摘要:
偏好处理是人工智能中的一个重要研究内容, 它的4个研究热点是偏好的表示、 提取、 聚合和推理. 条件偏好网(Conditional preference networks, CP-nets)是一种简单直观的偏好表示的图形工具, 但很少有工作研究CP-nets的表达能力. 本文研究CP-nets的表达能力, 详细研究了CP-nets表达偏好的完备性, 其上构造的运算复杂度以及适用的场合. 首先给出了CP-nets模型上的几个运算, 利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n). 其次通过构造CP-nets导出图及其性质的研究, 得出CP-nets特别适合不完全信息下的多属性定性偏好决策. 当需要处理更完全信息时, 可借助于与Agent的交互来完成. 虽然我们给出了CP-nets的强占优测试的理论解, 但其理论上可解, 实际上不可解. 为了解决强占优测试的指数级复杂度问题, 本文最后给出了一种带有软约束的满足问题(Soft constraint satisfaction problem, SCSP)的求解方法. 它把CP-nets中的定性运算转为约束半环中的定量运算, 从而将指数级的复杂度转化为多项式的复杂度, 间接提高了部分CP-nets的表达能力. 本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.
偏好处理是人工智能中的一个重要研究内容, 它的4个研究热点是偏好的表示、 提取、 聚合和推理. 条件偏好网(Conditional preference networks, CP-nets)是一种简单直观的偏好表示的图形工具, 但很少有工作研究CP-nets的表达能力. 本文研究CP-nets的表达能力, 详细研究了CP-nets表达偏好的完备性, 其上构造的运算复杂度以及适用的场合. 首先给出了CP-nets模型上的几个运算, 利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n). 其次通过构造CP-nets导出图及其性质的研究, 得出CP-nets特别适合不完全信息下的多属性定性偏好决策. 当需要处理更完全信息时, 可借助于与Agent的交互来完成. 虽然我们给出了CP-nets的强占优测试的理论解, 但其理论上可解, 实际上不可解. 为了解决强占优测试的指数级复杂度问题, 本文最后给出了一种带有软约束的满足问题(Soft constraint satisfaction problem, SCSP)的求解方法. 它把CP-nets中的定性运算转为约束半环中的定量运算, 从而将指数级的复杂度转化为多项式的复杂度, 间接提高了部分CP-nets的表达能力. 本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.
2011, 37(3): 303-308.
doi: 10.3724/SP.J.1004.2011.00303
摘要:
基于传统粗糙集理论的方法不能有效地处理含噪音的不完备信息系统. 根据集对分析理论, 提出(α, λ)联系度容差关系. 将(α, λ)联系度容差关系与Ziarko提出的多数包含关系相结合, 提出变精度(α, λ)联系度粗糙集模型. 给出了该模型下基于正域相似度的启发式属性约简算法, 分析了算法的时间复杂度, 通过仿真实验验证了所提方法处理含噪音的不完备信息系统的有效性.
基于传统粗糙集理论的方法不能有效地处理含噪音的不完备信息系统. 根据集对分析理论, 提出(α, λ)联系度容差关系. 将(α, λ)联系度容差关系与Ziarko提出的多数包含关系相结合, 提出变精度(α, λ)联系度粗糙集模型. 给出了该模型下基于正域相似度的启发式属性约简算法, 分析了算法的时间复杂度, 通过仿真实验验证了所提方法处理含噪音的不完备信息系统的有效性.
2011, 37(3): 316-321.
doi: 10.3724/SP.J.1004.2011.00316
摘要:
基于有监督学习的射频指纹定位方法是室内高精度无线定位技术的一个研究热点. 针对有监督学习方法存在训练数据集采集代价较高的问题, 本文提出了一种基于半监督学习的室内无线定位算法. 该算法采用基于Laplacian矩阵谱分解的方法获取训练数据在特征向量空间上的表示, 然后通过有标记数据在特征向量空间上的标记对齐, 实现对未标记数据的标记. 实验结果表明, 仅需少量的有标记数据(20%左右), 便能以较高的精度(80%左右)实现对未标记数据的标记, 从而有效降低了训练开销.
基于有监督学习的射频指纹定位方法是室内高精度无线定位技术的一个研究热点. 针对有监督学习方法存在训练数据集采集代价较高的问题, 本文提出了一种基于半监督学习的室内无线定位算法. 该算法采用基于Laplacian矩阵谱分解的方法获取训练数据在特征向量空间上的表示, 然后通过有标记数据在特征向量空间上的标记对齐, 实现对未标记数据的标记. 实验结果表明, 仅需少量的有标记数据(20%左右), 便能以较高的精度(80%左右)实现对未标记数据的标记, 从而有效降低了训练开销.
2011, 37(3): 322-330.
doi: 10.3724/SP.J.1004.2011.00322
摘要:
提出了一种基于多特征融合的视频交通数据采集方法, 核心思想是: 在图像中设置虚拟线圈, 假设车辆从虚拟线圈上驶过时引起像素变化, 通过识别这种像素变化来检测车辆并估计车速. 与现有技术相比, 本文的贡献在于: 1) 综合利用虚拟线圈内的前景面积、纹理变化、像素运动等特征来检测车辆, 提出了有效的多特征融合方法, 显著提高了车辆检测精度; 2) 根据单个虚拟线圈内的像素运动向量来估计车速, 避免了双线圈测速法的错误匹配问题. 算法测试结果表明本文算法能够在复杂多样的交通场景和天气条件下, 准确地检测车辆和估计车速. 在算法研究的基础上, 研制了一款嵌入式交通视频检测器, 在路口长期采集交通数据, 为交通信号控制和交通规律分析提供决策依据.
提出了一种基于多特征融合的视频交通数据采集方法, 核心思想是: 在图像中设置虚拟线圈, 假设车辆从虚拟线圈上驶过时引起像素变化, 通过识别这种像素变化来检测车辆并估计车速. 与现有技术相比, 本文的贡献在于: 1) 综合利用虚拟线圈内的前景面积、纹理变化、像素运动等特征来检测车辆, 提出了有效的多特征融合方法, 显著提高了车辆检测精度; 2) 根据单个虚拟线圈内的像素运动向量来估计车速, 避免了双线圈测速法的错误匹配问题. 算法测试结果表明本文算法能够在复杂多样的交通场景和天气条件下, 准确地检测车辆和估计车速. 在算法研究的基础上, 研制了一款嵌入式交通视频检测器, 在路口长期采集交通数据, 为交通信号控制和交通规律分析提供决策依据.
2011, 37(3): 331-341.
doi: 10.3724/SP.J.1004.2011.00331
摘要:
研究干扰观测器的鲁棒优化设计方法, 应用H∞范数定义干扰观测器的优化性能评价函数, 把低通滤波器的设计问题转换为H∞闭环回路成形问题. 通过适当处理相对阶次条件等约束, 把带有约束的回路成形问题转换成无约束的H∞标准问题, 然后利用H∞标准问题的求解算法设计滤波器. 此外, 探讨了性能与频率加权函数的关系, 并在此基础上提出了加权函数的选取方法. 实验结果证明该方法设计简单, 且具有最优性和系统性.
研究干扰观测器的鲁棒优化设计方法, 应用H∞范数定义干扰观测器的优化性能评价函数, 把低通滤波器的设计问题转换为H∞闭环回路成形问题. 通过适当处理相对阶次条件等约束, 把带有约束的回路成形问题转换成无约束的H∞标准问题, 然后利用H∞标准问题的求解算法设计滤波器. 此外, 探讨了性能与频率加权函数的关系, 并在此基础上提出了加权函数的选取方法. 实验结果证明该方法设计简单, 且具有最优性和系统性.
2011, 37(3): 342-353.
doi: 10.3724/SP.J.1004.2010.00342
摘要:
针对海流扰动及姿态、航向误差角引起的无法确知的导航系统模型误差, 设计了一种带模型误差的自适应无迹卡尔曼滤波器(Adaptive unscented Kalman filter, AUKF)用于小型水下机器人(Small autonomous underwater vehicle, SAUV)推位导航系统. 首先提出了小型水下机器人三维运动连续时间模型; 然后针对该模型特点, 基于极大后验估值原理推导了AUKF算法. 仿真结果说明该算法能够克服海流扰动及姿态和航向误差引起的模型误差. 对比经典无迹卡尔曼滤波器算法, 采用该算法的小型水下机器人推位导航系统在复杂海况下的滤波精度显著提高.
针对海流扰动及姿态、航向误差角引起的无法确知的导航系统模型误差, 设计了一种带模型误差的自适应无迹卡尔曼滤波器(Adaptive unscented Kalman filter, AUKF)用于小型水下机器人(Small autonomous underwater vehicle, SAUV)推位导航系统. 首先提出了小型水下机器人三维运动连续时间模型; 然后针对该模型特点, 基于极大后验估值原理推导了AUKF算法. 仿真结果说明该算法能够克服海流扰动及姿态和航向误差引起的模型误差. 对比经典无迹卡尔曼滤波器算法, 采用该算法的小型水下机器人推位导航系统在复杂海况下的滤波精度显著提高.
2011, 37(3): 354-359.
doi: 10.3724/SP.J.1004.2011.00354
摘要:
针对复杂工业生产过程中常常出现的输入与输出变量数目不相等的非方系统, 首次提出一种基于奇异值分解(Singular value decomposition, SVD)的内模控制(Internal model control, IMC)新方法. 该方法通过添加补偿项实现对非方系统的解耦并消除不可实现因素, 并应用SVD矩阵理论设计一种非对角型滤波器, 使控制系统不仅具备良好的高维解耦能力和响应速度快的优点, 而且因设置新型滤波结构而具备极强的鲁棒性. 仿真结果表明了这种方法的有效性和可靠性.
针对复杂工业生产过程中常常出现的输入与输出变量数目不相等的非方系统, 首次提出一种基于奇异值分解(Singular value decomposition, SVD)的内模控制(Internal model control, IMC)新方法. 该方法通过添加补偿项实现对非方系统的解耦并消除不可实现因素, 并应用SVD矩阵理论设计一种非对角型滤波器, 使控制系统不仅具备良好的高维解耦能力和响应速度快的优点, 而且因设置新型滤波结构而具备极强的鲁棒性. 仿真结果表明了这种方法的有效性和可靠性.
2011, 37(3): 360-370.
doi: 10.3724/SP.J.1004.2011.00360
摘要:
为了解决工程中数据样本较少情况下的准确建模问题, 提出了一种集成先验知识的多核线性规划支持向量回归算法. 该算法首先通过修改优化目标和不等式约束条件, 把来自仿真模型具有偏差的先验知识数据集成到现有的线性规划支持向量回归的学习框架中. 然后, 引入多核到集成先验知识的线性规划支持向量回归中以实现复杂规律的准确建模. 最后, 将算法推广到多输入多输出的数据建模中. 仿真案例以及在天线和滤波器的实际应用表明: 该算法求解简单, 具有较好的模型稀疏和准确性.
为了解决工程中数据样本较少情况下的准确建模问题, 提出了一种集成先验知识的多核线性规划支持向量回归算法. 该算法首先通过修改优化目标和不等式约束条件, 把来自仿真模型具有偏差的先验知识数据集成到现有的线性规划支持向量回归的学习框架中. 然后, 引入多核到集成先验知识的线性规划支持向量回归中以实现复杂规律的准确建模. 最后, 将算法推广到多输入多输出的数据建模中. 仿真案例以及在天线和滤波器的实际应用表明: 该算法求解简单, 具有较好的模型稀疏和准确性.
2011, 37(3): 371-379.
doi: 10.3724/SP.J.1004.2011.00371
摘要:
由于现有的工序间存在紧密衔接条件的复杂产品综合调度问题, 采用的移动交换算法不易于软件实现且没有考虑移动工序后产生的连锁反应引起较高算法复杂度的问题, 提出将具有紧密衔接约束条件的工序组进行统一联动的综合调度算法.该算法利用将具有紧密衔接约束条件的工序分组的扩展加工工艺树模型, 按路径上属于工序组的工序个数多少确定所在路径工序组调度的次序, 通过降低对工序组的限制要求降低算法复杂度; 对于被调度工序组中各工序的前序工序, 按工序组中工序的加工顺序确定调度次序, 对某个工序的前序工序采用复杂度较低的拟关键路径法确定工序的调度次序; 调度完所有紧密衔接工序组后, 剩余的标准工序按拟关键路径法确定调度顺序; 采取工序首次适应调度算法调度标准工序和工序组, 由于工序组中工序采取按序紧密衔接的联动调度方式确定工序组的开始时间, 避免了二次调整, 进一步降低了算法复杂度. 分析和实例表明, 所提出的综合算法比以往算法复杂度更低, 调度结果更优且更易于实现.
由于现有的工序间存在紧密衔接条件的复杂产品综合调度问题, 采用的移动交换算法不易于软件实现且没有考虑移动工序后产生的连锁反应引起较高算法复杂度的问题, 提出将具有紧密衔接约束条件的工序组进行统一联动的综合调度算法.该算法利用将具有紧密衔接约束条件的工序分组的扩展加工工艺树模型, 按路径上属于工序组的工序个数多少确定所在路径工序组调度的次序, 通过降低对工序组的限制要求降低算法复杂度; 对于被调度工序组中各工序的前序工序, 按工序组中工序的加工顺序确定调度次序, 对某个工序的前序工序采用复杂度较低的拟关键路径法确定工序的调度次序; 调度完所有紧密衔接工序组后, 剩余的标准工序按拟关键路径法确定调度顺序; 采取工序首次适应调度算法调度标准工序和工序组, 由于工序组中工序采取按序紧密衔接的联动调度方式确定工序组的开始时间, 避免了二次调整, 进一步降低了算法复杂度. 分析和实例表明, 所提出的综合算法比以往算法复杂度更低, 调度结果更优且更易于实现.
2011, 37(3): 380-384.
doi: 10.3724/SP.J.1004.2011.00380
摘要:
针对热连轧活套高度和张力的双输入双输出强耦合系统, 文中提出一类基于滚动时域优化原理的多路控制策略. 基于滚动优化原理, 在每一个周期内, 顺序求解子系统的控制律后及时更新系统. 从H∞观点出发, 将解耦问题转化为干扰抑制和多目标优化问题, 能够减轻计算机的负担, 提高控制系统的性能. 仿真结果证实了该方法具有良好的解耦效果和控制性能.
针对热连轧活套高度和张力的双输入双输出强耦合系统, 文中提出一类基于滚动时域优化原理的多路控制策略. 基于滚动优化原理, 在每一个周期内, 顺序求解子系统的控制律后及时更新系统. 从H∞观点出发, 将解耦问题转化为干扰抑制和多目标优化问题, 能够减轻计算机的负担, 提高控制系统的性能. 仿真结果证实了该方法具有良好的解耦效果和控制性能.
2011, 37(3): 385-388.
doi: 10.3724/SP.J.1004.2011.00385
摘要:
针对一阶不稳定加延迟对象, 基于传统稳定裕度定义的PI控制整定方法缺乏对幅值裕度下边界的考虑, 使得结果与实际有一定偏差. 通过对延迟环节的逼近, 得到更精细的可达稳定裕度区域. 利用多项式方程数值求解算法, 同时获得了另一种以幅值裕度下边界为基准的控制参数整定方法. 所得结果显示, 按照严格稳定裕度定义所得到的可达区域明显减小. 数值实例验证了本文方法的有效性.
针对一阶不稳定加延迟对象, 基于传统稳定裕度定义的PI控制整定方法缺乏对幅值裕度下边界的考虑, 使得结果与实际有一定偏差. 通过对延迟环节的逼近, 得到更精细的可达稳定裕度区域. 利用多项式方程数值求解算法, 同时获得了另一种以幅值裕度下边界为基准的控制参数整定方法. 所得结果显示, 按照严格稳定裕度定义所得到的可达区域明显减小. 数值实例验证了本文方法的有效性.
