基于CUR矩阵分解的多核学习正则化路径近似算法

多核学习在解决不规则、大规模数据问题时表现出良好的优越性。正则化路径是一种多次求解多核学习,选择最优模型的措施。针对多核学习正则化路径算法处理大规模数据时,核矩阵规模较大,计算代价高,影响优化模型效率的问题,提出一种基于CUR矩阵分解的多核学习正则化路径近似算法(Multiple kernel learning regularization path approximation algorithm with CUR, MKLRPCUR)。该算法首先采用CUR算法获得核矩阵的低秩近似矩阵的多个分解矩阵,然后在求解过程中利用低维的分解矩阵相乘替代核矩阵,调整相关矩阵计算的顺序,从而简化算法中核矩阵和拉格朗日乘子向量乘积的计算。 MKLRPCUR算法降低了矩阵的计算规模,优化了矩阵计算,提高了精确算法的计算效率。 从理论上分析低秩近似矩阵的相对误差和算法的时间复杂度,验证了近似算法的合理性。同时,在UCI数据集、ORL和COIL图像数据库上的实验结果表明,本文提出的近似算法不仅保证了学习的准确率,并且降低了算法的运行时间,提高了模型的效率。     

微电子生产过程调度问题基于指标快速预报的分解算法

微电子生产过程调度问题具有规模大和约束复杂等特点,如菜单、Setup时间和组批约束等,其优化调度具有一定难度.针对以最小化平均流经时间为调度目标的较大规模微电子生产过程调度问题,提出一种基于指标快速预报的分解方法(DM-IFP).首先,通过松弛不可中断约束,设计一种代理方法,即基于机器负载的操作完工时间快速预测方法(CTP-ML);其次,设计基于CTP-ML的问题分解方法,将原问题迭代分解为多个连续交迭的子问题;然后,提出一种基于双信息素的蚁群算法(ACO-D)用于求解分解后的子问题,其全局调度目标采用CTP-ML获取,有效保证了全局优化性能;最后,针对一些不同规模的仿真数据,将所提出方法与一些代表性的算法进行详尽的数值对比,计算结果表明所提出方法在所获解的质量和收敛性上均有改善.     

基于聚类分解的WCDMA基站布局规划算法

针对大规模WCDMA无线网络基站布局规划问题,提出一种基于聚类分解的分层算法．在聚类分解中,以测试点信号增益矩阵构造聚类分解数据,并给出了收敛判定函数和相似度计算方法．在分层算法中,首先用K均值聚类将原问题分解为K个子规划问题,然后对各子问题求解整数规划问题,最后对各子问题的基站布局结果进行全局调整．仿真计算验证了该算法的有效性．     

一种自适应闭值的简洁性约束频繁项目集挖掘算法

基于约束关联挖掘,近几年在国际上受到较大关注。从许多约束的关联挖掘算法中发现,传统的约束阂值大多是通过专家给定或经过反复试验得出的,缺乏用户反馈与客观依据的支持。为了解决此问题,提出一种面向用户需求的阂值构造方法,该方法引用正态分布理论获得自适应约束阂值,并应用简洁性约束对FGC算法进行改进;同时提出一种快速、直观、有效的频繁项目集挖掘算法。实验证明,该算法在增强系统可用性的同时降低了算法运行时间。     

多元时间序列的子空间回声状态网络预测模型

针对采用回声状态网络预测多元混沌时间序列时储备池学习算法可能存在的病态解问题,该文提出了一种基于快速子空间分解方法的回声状态网络预测模型.所提模型利用Krylov子空间分解方法提取储备池状态矩阵的子空间,子空间代替原状态矩阵进行输出权值求解,可以消除储备池状态矩阵的冗余信息,有效地解决伪逆算法存在的病态解问题,并且降低计算复杂度,提高泛化性能和预测精度.基于两组多元混沌时间序列的仿真结果验证了该文所提模型的有效性和实用性.     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

大型网络的SKT可靠性的分散计算法

提出了一种基于分解法的计算大型网络从源点到特定节点集K(即SKT)可靠性的算法。按照一定的分解规则将大型网络划分为若干较小规模的子网络，从而最终将枚举原网络的K树这一复杂问题转化为计算这些子网络的最小路。对求得的K树进行不交化运算，最终得到网络的SKT可靠性。     

基于预测与分解策略的大规模炼油过程生产调度算法

炼油生产调度为混合整数规划问题,随着规模的增大,其求解时间随问题规模呈指数增加,使得大规模长周期炼油生产调度问题难以在合理的时间内求解.针对该问题,本文提出了一种基于生产任务预测与分解策略的炼油生产调度算法,该算法能在短时间内获得大规模调度问题的满意解.所提算法将原问题沿时间轴分解为若干个调度时长相同的单时间段子问题,并设计了基于深度学习的单时间段生产任务(组分油产量)预测模型,用于协调子问题的求解.其中,生产任务预测模型通过易于获得的小规模问题的全局最优调度方案训练得到.最后,通过与商业求解器Cplex以及现有算法的对比,实验结果表明了所提算法的有效性.     

Apriori算法用于频繁子图挖掘的改进方法

AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。     

平面区域几何划分的拓扑算法研究

给定一个任意形状的平面区域,用若干条折线将该平面区域划分成若干子区域,针对如何能将各子区域识别输出,提出了一种平面区域几何划分的拓扑算法。根据各子区域之间的拓扑关系,选取了合理的数据结构,并利用最佳路径选择方法,最终将所有子区域准确输出。其中判断和计算交点也是该算法中的主要工作,通过改进一个现有的求交计算方法,进一步加快了算法的运行速度。实验结果表明,算法的效果很好。     

基于遗传算法的多处理器系统任务调度

用一种遗传算法的调度策略,以大维度矩阵求逆为实验对象,探索在多核中如何完成任务的均衡分配问题,以达到加速效果.算法利用系统资源的弹性,自动搜寻可以并行的子任务并将其合理地分配到相应计算节点中,提高了多核系统资源调度性能,实现了对用户提交的任务的优化调度,达到了均衡系统各处理器计算负载和提高多核系统的总体性能的目标.     

基于粒子群优化的异构多处理器任务调度算法

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题;同时通过引入禁忌算法进行局部搜索,克服粒子群算法的早熟收敛现象,避免陷入局部最优。实验结果表明,FPSOTTS算法的执行效率优于Min-min算法和遗传算法,有效地降低任务的执行时间。FP-SOTTS算法很好地解决了异构多处理器任务调度问题,并且适合于大规模并行任务调度。     

集群系统中的FP-Growth并行算法

针对FP-Growth算法面临大规模数据库时空效率不高的问题,提出一种面向计算机集群的并行算法。采用投影方法直接寻找频繁项的条件数据库,将挖掘条件数据库的工作分化成若干独立的子任务,分配到集群中的节点上并行实现,由中央节点汇总结果并输出。结果证明,该算法不仅能够提高计算速度,解决数据库规模过大时内存溢出的情况,且具有良好的延展性。     

智能建筑室内环境分布式可计算WSN任务调度研究

针对智能建筑室内环境下并行计算的动态任务调度问题,构建了基于分布式CPS思想的无线传感器网络(WSN)模型,并分别设计了基于可计算复杂性的任务分配策略和基于动态调度算法的任务调度策略。通过先将任务分配成若干个子任务,采用多带图灵机输入任务,由合适的计算节点进行计算,形成有向无环图,再按调度优先级排列任务,形成任务调度序列表,依序处理任务,从而达到了将任务分配、调度和执行相结合的目的。实验结果表明该策略可有效减少智能建筑室内环境分布式可计算WSN分布运行时任务之间的通讯时间和等待时间,同时提高了任务调度的成功率,最终优化系统的运行效率。     

自适应区间配置在关联规则并行采掘中的作用

现行的采掘关联规则的并行算法基于经典的层次算法.该方法在每一次重复扫描数据库时都需要一次同步,这种同步运算对于共享内存多处理器并行机来说极大地降低了采掘性能,这种低效主要源于对共享的I/O通道的竞争.该文提出了在共享内存多处理机上采掘关联规则的异步算法APM.在APM中,所有参与计算的处理器能独立地产生备选集和计算支持度.而且,APM所需的扫描数据库的次数比层次方法所需的更少.该文还提出了一种增强APM的技术,使得该算法的性能对于数据分布更具有鲁棒性.文中实现了APM的变种算法,还实现了Apriori的并行版本Count Distribution算法.在SGI Power Challenge SMP并行机上,进行了性能分析,结果表明所提出的异步算法APM具有更好的性能和可扩展性.     

基于蚁群算法的移动边缘服务器收益优化策略

移动边缘计算(Mobile Edge Computing,MEC)是5G的关键技术。由于MEC服务器的计算资源有限,如何对其计算资源分配以提高收益至关重要。为此,提出一种边缘服务器收益优化策略。将MEC服务器收益最大化问题建模为以服务器端任务执行次序为优化变量的最优化问题。在用户对时延和金钱偏好程度不同及子任务具有顺序执行关联性的情况下,提出基于蚁群算法的任务最优执行次序求解算法。仿真结果表明,同等条件下采用该算法获得的收益比SearchAdjust算法提高了33.6%。     

A dynamic texture based segmentation method for ultrasound images with Surfacelet,HMT and parallel computing

To segment regions of interest (ROIs) from ultrasound images, one novel dynamic texture based algorithm is presented with surfacelet transform, hidden Markov tree (HMT) model and parallel computing. During surfacelet transform, the image sequence is decomposed by pyramid model, and the 3D signals with high frequency are decomposed by directional filter banks. During HMT modeling, distribution of coefficients is described with Gaussian mixture model (GMM), and relationship of scales is described with scale continuity model. From HMT parameters estimated through expectation maximization, the joint probability density is calculated and taken as feature value of image sequence. Then ROIs and non-ROIs in collected sample videos are used to train the support vector machine (SVM) classifier, which is employed to identify the divided 3D blocks from input video. To improve the computational efficiency, parallel computing is implemented with multi-processor CPU. Our algorithm has been compared with the existing texture based approaches, including gray level co-occurrence matrix (GLCM), local binary pattern (LBP), Wavelet, for ultrasound images, and the experimental results prove its advantages of processing noisy ultrasound images and segmenting higher accurate ROIs.

     

Modeling and Control of Head Raising Snake Robots by Using Kinematic Redundancy

In this paper, we consider trajectory tracking control of a head raising snake robot on a flat plane by using kinematic redundancy. We discuss the motion control requirements to accomplish trajectory tracking and other tasks, such as singular configuration avoidance and obstacle avoidance, for the snake robot. The features of the internal motion caused by kinematic redundancy are considered, and a kinematic model and a dynamic model of the snake robot are derived by introducing two types of shape controllable point. The first is the head shape controllable point, and the other is the base shape controllable point. We analyzed the features of the two kinds of shape controllable point and proposed a controller to accomplish the trajectory tracking of the robot’s head as its main task along with several sub-tasks by using redundancy. The proposed method to accomplish several sub-tasks is useful for both the kinematic model and the dynamic model. Experimental results using a head raising snake robot which can control the angular velocity of its joints show the effectiveness of the proposed controller.     

A network based mechanism for managing decomposable tasks via crowdsourcing

If a task is decomposable in a competitive crowdsourcing environment, thereby allowing collaboration, rational workers may choose to divide it into multiple sub-tasks among themselves. But as the winners are selected independently, there is no benefit out of this decomposition. We show that by the appropriate combination of such decomposed solutions, obtained from multiple workers, we can achieve a better solution for a given task. We present a network based mechanism to choose the best mixture of sub-tasks in a competitive environment for selecting collaborating winners.     

基于人工免疫的入侵检测系统负选择并行算法

基于人工免疫的入侵检测技术是网络安全的一个新兴研究领。运用人体免疫系统的出色功能,对负选择算法进行并行化设计,根据程序并行性的条件将串行的负选择算法中的任务进行划分,由多个处理机并行求解子任务,并将子解合并获得问题的解。分析表明,基于人工免疫的入侵检测系统负选择并行算法获得线性加速。