认知Wi-Fi 2.0 无线网络多用户动态分层功率控制算法

具有认知性、自主性和适变性等特点的认知Wi-Fi 2.0无线网络技术,作为提高无线网络容量的重要技术不断引起学术界、标准组织和工业界的关注.针对现有功率控制技术不能刻画多个认知节点存在分层决策的现象,提出一种认知Wi-Fi 2.0无线网络中多用户动态分层功率控制算法.基于提出的斯坦科尔伯格(Stackelberg)容量最大化博弈模型,为认知Wi-Fi 2.0无线网络中感知信息不对称的多用户分别设计了分布式功率控制方法,实现领导者用户和跟随者用户的多阶段动态交互在保证个体效用的同时实现网络整体性能.该算法根据当前认知Wi-Fi 2.0无线网络中多个认知节点接入频谱顺序的不同,确定领导者用户和跟随者用户;然后,对于领导者和跟随者分别采用不同的功率控制策略,并多次交互实现多用户分层算法的动态交互收敛.蒙特卡洛仿真验证了算法的有效性.     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

求解TSP的启发式顺序交叉算子

旅行商问题是经典的NP难组合优化问题之一.在用遗传算法求解旅行商问题时,顺序交叉算子是一种较为常用的遗传交叉算子.使用顺序交叉算子时的交叉点位置是随机指定的,不能反映关键遗传信息,导致算法执行效率较低.在顺序交叉算子的基础上,提出了一种启发式顺序交叉算子.该算子结合顺序交叉算子和启发式算法以得到双亲中交叉点位置,保留了双亲中关键的城市顺序信息.该算子改善了使用顺序交叉算子执行效率低的问题.实验结果表明了该算子的有效性.     

稀疏有限元线性系统的并行算法实现

在对称多处理机系统上,提出了一种求解稀疏对称有限元线性系统的正规化精确并行逆算法。该算法以一种避免数据依赖的反对角运动方法为基础,使用OpenMP编译指导来实现。诸如加速比和效率等数值实验结果的推出,说明在一个对称多处理机系统上,所提出的算法求解方法能更好地提高性能,获得更大的加速。     

基于混合负载平衡的并行启发式搜索算法

在分析了迭代加深启发式搜索(Iterative Deepening A*)算法及其可并行性后,提出了一种新的基于混合负载平衡的并行迭代加深启发式搜索算法。该算法综合了静态负载平衡和动态负载平衡的优点,可以在多结点的并行搜索计算中获得很高的加速比和效率。给出了该算法的Java RMI实现。通过在72个结点的并行机上的试验表明,该算法可以极大地提高并行搜索算法的加速度和效率。     

FPGA架构上面向稀疏矩阵求解的静态调度算法

在电力系统仿真中,大型稀疏矩阵的求解会消耗大量存储和计算资源,未有效利用矩阵的稀疏性将导致存储空间浪费以及计算效率低下的问题。当前关于稀疏矩阵求解算法的研究主要针对众核加速硬件,聚焦于挖掘层次集合的并行度以提升算法的并行效率,而在众核处理器架构上频繁地进行缓存判断及细粒度访问可能导致潜在的性能问题。针对基于现场可编程门阵列（FPGA）的下三角稀疏矩阵求解问题,在吴志勇等设计的FPGA稀疏矩阵求解器硬件结构的基础上,提出一种静态调度求解算法。通过对稀疏矩阵进行预处理,设计数据分布和指令排布流程,将下三角稀疏矩阵的求解过程静态映射到多个FPGA片上的处理单元,以实现下三角稀疏矩阵在FPGA上的并行高速求解。将串行算法中所有的隐式并行关系排布到缓冲中,使得所有计算单元都能实现计算、访存和单元间通信的高效并行,从而最大限度地利用FPGA的硬件资源。典型算例上的测试结果表明,相较传统的CPU/GPU求解算法,该算法能够实现5~10倍的加速效果。     

智能搜索算法求解最大团问题研究

最大团问题MCP（Maximum Clique Problem）在国外得到了广泛的研究,在国内刚起步,是一类NP完全问题。传统的确定性算法不能有效地进行求解。定义了MCP;介绍了使用启发式算法求解MCP的研究进展;综述了几种典型的智能搜索算法;分析了使用这些典型算法求解MCP的基本思想;研究了这些智能算法在求解MCP时的特点及性能。     

杂合启发式在线POMDP 规划

许多不确定环境下的自主机器人规划任务都可以用部分可观察的马氏决策过程(partially observableMarkov decision process,简称POMDP)建模.尽管研究者们在近似求解技术的设计方面已经取得了显著的进展,开发高效的POMDP 规划算法依然是一个具有挑战性的问题.以前的研究结果表明:在线规划方法能够高效地处理大规模的POMDP 问题,因而是一类具有研究前景的近似求解方法.这归因于它们采取的是“按需”作决策而不是预前对整个状态空间作决策的方式.旨在通过设计一个新颖的杂合启发式函数来进一步加速POMDP 在线规划过程,该函数能够充分利用现有算法里一些被忽略掉的启发式信息.实现了一个新的杂合启发式在线规划(hybrid heuristiconline planning,简称HHOP)算法.在一组POMDP 基准问题上,HHOP 有明显优于现有在线启发式搜索算法的实验性能.     

风暴潮数值模式的并行化

实现了风暴潮数值模式基于MPI的并行化;根据该模式数值计算的特点提出了一种并行求解三对角方程组的新方法,相对于传统算法编程简单而且并行效率更高;负载平衡是并行程序性能优化首先要解决的问题,以水格点的个数作为任务分解的标准,实现了较好的负载平衡,相比水陆格点不作区分的分解方法性能有明显的提高;在SMP平台上使用8个CPU时加速比可以达到7.0,在集群平台上为6.5。     

基于功能和数据划分的H.264并行解码算法

针对H.264视频解码算法的并行模块选择、划分及解码速度优化等问题,面向TilePro64多核平台,提出一种可扩展的H.264并行解码算法。对该算法的内部功能模块进行整合和划分,根据核间数据的依赖关系,动态分配功能模块及优化算法并行效率。实验结果表明,该算法在解码效率、多核并行程度、解码时延等方面均有较好性能,相比传统并行解码算法,其并行加速比提高约25%。     

求解最大割问题的交叉熵算法

交叉熵方法（Cross Entropy）是近几年发展而来的一种启发式方法,在求解组合优化问题中显示出其简单有效的特点,将运用交叉熵方法（CE）寻求图论中一个典型的NP困难问题—最大割问题的最优解。为了解决最大割问题,CE方法借助Bernoulli分布的思想,将一个确定性的网络转换成一个具有一定随机性的关联网络,接下来首先按照一个多维的Bernoulli概率分布生成样本,同时计算出随机割;其次,基于前一步的数据,更新Bernoulli概率分布P参数,使得分布参数逐步逼近最优值产生最大割的稳定估计值。数值实验表明,CE方法具有很好的稳定性和收敛性,最终也获得了比较好的近似解。     

GACE: A meta-heuristic based in the hybridization of Genetic Algorithms and Cross Entropy methods for continuous optimization

Metaheuristics have proven to get a good performance solving difficult optimization problems in practice. Despite its success, metaheuristics still suffers from several problems that remains open as the variability of their performance depending on the problem or instance being solved. One of the approaches to deal with these problems is the hybridization of techniques. This paper presents a hybrid metaheuristic that combines a Genetic Algorithm (GA) with a Cross Entropy (CE) method to solve continuous optimization functions. The algorithm divides the population into two sub-populations, in order to apply GA in one sub-population and CE in the other. The proposed method is tested on 24 continuous benchmark functions, with four different dimension configurations. First, a study to find the best parameter configuration is done. The best configuration found is compared with several algorithms in the literature in order to demonstrate the competitiveness of the proposal. The results shows that GACE is the best performing method for instances with high dimensionality. Statistical tests have been applied, to support the conclusions obtained in the experimentation.     

基于结构并行的MRBP算法

BP(back propagation)算法是一种常用的神经网络学习算法,而基于Hadoop集群MapReduce编程模型的BP(MapReduce back propagation, MRBP)算法在处理大数据问题时,表现出良好的性能,因而得到了广泛应用.但是,由于该算法缺乏神经节点之间细粒度结构并行的能力,当遇到数据维度较高、网络节点较多时,性能还显不足.另一方面,Hadoop集群计算节点通信不能由用户直接控制,现有基于集群系统的结构并行策略不能直接用于MRBP算法.为此,提出一种适合于Hadoop集群的结构并行MRBP (structure parallelism based MapReduce back propagation, SP-MRBP)算法,该算法将神经网络各层划分为多个结构,通过逐层并行-逐层集成(layer-wise parallelism,layer-wise ensemble, LPLE)的方式,实现了MRBP算法的结构并行.同时,推导出了SP-MRBP算法和MRBP算法计算时间解析表达式,以此分析了2种算法时间差和SP-MRBP算法最优并行规模.据了解,这是首次将结构并行策略引入MRBP算法中.实验表明,当神经网络规模较大时,SP-MRBP较之原算法,具有较好的性能.     

动态权重的蝙蝠算法在图像分割中的应用研究

传统的最小交叉熵阈值分割法（MCET）采用穷举的搜索形式，存在计算复杂度大、分割效率低的缺点，在很大程度上限制了该方法的应用。针对最小交叉熵分割法存在的不足，提出采用改进蝙蝠算法（BA）来搜索阈值的最优解。对BA算法中的权重参数做自适应调整，将随着迭代次数变化而变化的时变惯性权重策略应用于BA算法更新公式，给出三种不同的改进策略解决原始BA算法在靠近最优解时收敛速度下降的问题。将改进后的最优BA算法（IBA）应用于最小交叉熵多阈值图像分割中，与基本BA算法、改进的粒子群优化算法（IPSO）、模糊聚类方法（FC）三种方法进行对比性实验。实验结果表明，提出的IBA算法运算速度和分割精度效果明显提升。     

LSA_IT:一种In-Tree任务图的分层调度算法

In-Tree任务图可用来求解归并排序、求和等分治问题的并行。针对该类任务图,提出了一种分层调度算法——LSA_IT。它对任务图逐层调度。调度中,根据优先级,保证任务的最优前驱被优先调度,并在不影响调度长度的同时,将任务尽可能地调度到其已调度兄弟所在处理器上。实验表明,与TDS、DCP、MCP算法相比,LSA_IT的调度性能最优。     

A cooperative parallel meta-heuristic for the vehicle routing problem with time windows

This paper presents a parallel cooperative multi-search method for the vehicle routing problem with time windows. It is based on the solution warehouse strategy, in which several search threads cooperate by asynchronously exchanging information on the best solutions identified. The exchanges are performed through a mechanism, called solution warehouse, which holds and manages a pool of solutions. This enforces the asynchronous strategy of information exchanges and ensures the independence of the individual search processes. Each of these independent processes implements a different meta-heuristic, an evolutionary algorithm or a tabu search procedure. No attempt has been made to calibrate the individual procedures or the parallel cooperative method. The results obtained on an extended set of test problems show that the parallel procedure achieves linear accelerations and identifies solutions of comparable quality to those obtained by the best methods in the literature.     

基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

基于多策略的多目标粒子群优化算法

针对目前多目标粒子群优化算法的收敛性能和非劣解的多样性不能同时得到满足等缺陷,提出一种基于多策略的多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization algorithm for Multi-Strategy,MS-MOPSO）。采用非支配排序和拥挤距离排序相结合策略,重新划分外部种群和进化种群;采用小生境选择策略,在外部种群中选择最佳粒子作为领导粒子,用于领导进化种群中粒子的进化;在进化种群中利用多尺度高斯变异策略,平衡算法的全局搜索和局部精确搜索;采用邻域认知个体极值更新策略,不断更新个体极值。将该算法应用到典型的多目标测试函数,并与其他多目标优化算法进行对比分析,测试结果表明该算法中四个策略的有效性和互补性,同时验证了该算法不但具有较好的收敛性和收敛速度,而且该算法最优解的分布具有良好的均匀性和多样性。     

An enhanced pathfinder algorithm for engineering optimization problems

The pathfinder algorithm (PFA) is a new population-based optimizer, it divides the search agents of the algorithm into leaders and followers, imitating the leadership level of the group movement to find the best food area or prey. In PFA, followers follow the new position according to the position of the leader and their own consciousness makes the algorithm easy to fall into local optimum. To overcome this shortcoming, the following stage is complicated in this paper, and the acceptance operator, the exchange operator and the mutation mechanism are introduced into the algorithm. To further balance the mining ability and exploration ability of the algorithm, the article regards the leader as a guide and introduces a guide mechanism. To verify the performance of the improved algorithm, it is applied to nine real-life engineering case problems. The simulation results of the real-life engineering design problems exhibit the superiority of the improved PFA (IMPFA) algorithm in solving challenging problems with constrained and unknown search spaces when compared to the basic PFA algorithm or other available solutions.

     

Dynamic partition search algorithm for global numerical optimization

This paper presents a novel evolutionary algorithm entitled Dynamic Partition Search Algorithm (DPSA) for global optimization problems with continuous variables. The DPSA is a population-based stochastic search algorithm in nature, which mainly consists of initialization process and evolution process. In the initialization process, the DPSA randomly generates an initial population of members from a specific search space and finds a leader. In the evolution process, the DPSA applies two groups to balance exploration ability and exploitation ability, in which one group is in charge of exploring new region via a dynamic partition strategy, and the other group relies on Cauchy distributions to exploit the region around the best member. Later, numerical experiments are conducted for 24 classical benchmark functions with 100, 1000 or even 10000 dimensions. And the performance of the proposed DPSA is compared with a state-of-the-art cooperative coevolving particle swarm optimization (CCPSO2), and two existing differential evolution (DE) algorithms. The experimental results show that DPSA has a better performance than the algorithms used for comparison, especially for high dimensional optimization problems. In addition, the numerical computational results also demonstrate that the DPSA has good scalability, and it is an effective evolutionary algorithm for solving large-scale global optimization problems.