一种改进的双向singleton弧相容算法

在现有相容性算法研究的基础上,提出了一种在约束网络中确立双向singleton弧相容的新算法——BiSAC-2,并给出了其正确性和完备性证明。该算法与原有算法BiSAC-1具有相同的化简问题能力,但BiSAC-2能够减少弧相容维护的次数,避免冗余约束传播过程的产生,从而可以快速地到达稳定点,进而实现高效的目的。对随机约束满足问题的测试结果表明,算法BiSAC-2比原始算法BiSAC-1具有更明显的性能优势。     

基于论域折半的最大限定路径相容算法

针对绝大多数不可满足问题的特点,提出了一种将弧相容算法与最大限定路径相容算法相结合的相容性算法——基于论域折半的最大限定路径相容的算法。该算法充分利用了弧相容计算开销小和最大限定相容删值能力强的优点,可以减少在求解不可满足问题中生成的结点数,进而提高求解效率。实验结果表明,本文算法在处理不可满足问题时的求解效率明显优于传统的维持弧相容算法。     

贪婪的Singleton弧相容算法的优化

通过记录搜索过程中的有用信息避免了一些无用的约束传播,从而对预处理阶段的Singleton弧相容算法进行了改进,提出了改进的Singleton弧相容算法———SAC3-Revised,它能够减少约束传播的次数和时间。实验结果表明:对于随机问题,当p2在一定范围内取值时,算法效率可提高两倍以上;对于标准测试用例,算法SAC3_Revised的效率也优于SAC-3。     

基于AC-4的动态值启发式约束满足问题求解算法

通过对弧相容算法AC-4的研究,提出了基于AC-4的动态值启发式约束满足问题求解算法MAC-DMSV。算法充分利用AC-4在初始化阶段建立的计数器信息,选择计数最大者为优先实例化的值。将此值启发式加入MAC算法之中,在MAC的相容性检查时,更新计数器的值,实现了动态值启发式。实验结果表明,MAC-DMSV算法比MAC和BT+MPAC算法具有更高的求解效率。     

等离子体弧流数值模拟的研究进展

等离子体弧流的数值模拟研究对其在工业中的应用有重要的意义。详细阐述了等离子体弧流数值模拟研究的发展过程,主要包括自由等离子体弧流和约束等离子体弧流2方面的研究进展,对应用ANSYS等数值分析软件建立等离子体弧流数学模型求解流体的温度场和速度场的方法进行了描述,综合考虑等离子体弧流的流动状态和三维约束等离子体弧流的数值模拟可能是未来的重要研究方向。     

边缘分类SIFT算法

针对经典SIFT算法的实时性较差和其在图像拼接应用时特征点冗余的问题,研究了其在整个尺度空间搜索极值点步骤后,利用图像几何不变矩理论结合图像边缘提取技术提取了图像的边缘类,并在边缘类对应的尺度空间中提取特征点,从而给出了一种改进的SIFT算法.经过多组实验后,结果显示改进后算法可以使图像的冗余特征点减少20%～50%,从而大大减少经典SIFT特征点冗余性并提高了算法的运行速度.     

细胞元特征模型中操作局部化方法的研究

提出一种直接操作特征过程中将操作局部化的方法,该方法利用语义造型系统中特征依赖图及细胞表示特征的高效性,将发生变化的区域从特征模型中分离出来．利用该方法使得直接操作特征时缩小了对模型进行约束求解的范围,从而满足了直接操作特征时对约束求解的速度要求．同时,通过对数据结构的分析,给出两个相应的分离算法．     

Sutherland-Hodgman裁剪算法的改进

针对经典Sutherland-Hodgman裁剪算法存在冗余操作并可能产生重复图元,从而造成不必要扫描处理的问题,尝试通过在两重循环的过程中增加必要的判断和出口,以实现对经典算法的改进。改进算法的合理性可从理论上获得证明。仿真结果表明改进算法能够达到减少操作次数和避免重复图元产生的目的。     

弧底梯形渠道收缩水深计算方法的简化

弧底梯形断面明渠收缩水深的计算需完成超越方程求解,针对传统算法(图解法、试算法)存在的计算过程繁琐、成果精度不高等问题,对弧底梯形断面明渠收缩水深基本计算方程变形、整理后的超越函数进行优化拟合替代,以最小标准剩余差为目标函数,在工程适用的参数范围内,经逐次逼近拟合分析及计算得到了表达形式简单、求解精度较高的近似公式.利用该公式计算弧底梯形断面明渠收缩水深,明显提高了工作效率,进一步提高了计算精度.     

求解含负权弧的网络最小截问题

对于经典网络最小截问题,所有弧权数非负,可运用最大流算法求解。但是对于广义最小截问题,若某些弧权数为负,则运用算法难以求解。针对含负权弧网络最小截问题,通过与经典最小截问题的对比,提出简单截集和复合截集概念,并给出广义网络最小截概念——截量最小的简单截集;引入负容量和负流量,给出求解含负权弧网络最小截问题的原理,并设计求解含负权网络最小截问题的网络流算法;最后,通过应用举例对算法进行演示。     

基于KMP算法的next函数理解与分析

在字符串模式匹配算法的研究过程中,KMP算法是基于常规的BF算法的一种改进算法,而其中next函数值的求解过程更是该算法的重要内容.本文以原算法的求解过程作为基础,通过对next函数值求解过程的算法改进和模式字符匹配串匹配过程的描述,从而增强对KMP算法的理解.本文利用C语言实现了改进后的next函数值求解算法.     

基于可靠性约束的工作流调度算法

移动边缘计算(Mobile Edge Computing, MEC)环境中,工作流调度算法存在可靠性约束的问题,为此,提出一种基于可靠性约束的工作流调度算法。首先,根据工作流子任务依赖关系生成优先级就绪队列;其次,根据不同服务器的故障率建立可靠性模型,保证工作流调度方案满足工作流可靠性的要求;然后,针对未分配调度位置的任务,根据服务器可靠性信息,按照执行队列顺序进行初始化,得到满足可靠性约束的初始种群;最后,采用改进的非支配排序遗传算法(Non-dominated Sorting Genetic AlgorithmⅡ,NSGA-Ⅱ)求解工作流的最优卸载位置,并生成调度方案。仿真实验表明,相较于轮询调度算法、贪心算法和粒子群算法,提出算法降低了移动设备的能耗,减少了任务时延,提高了工作流执行可靠性。     

基于比特位操作的自适应约束传播算法

在现有约束传播算法研究的基础上,提出了一种基于比特位操作的自适应约束传播算法AC_MaxRPC_Bitwise。该算法在寻找AC支持及PC支持中引入基于比特位的数据结构,并利用比特位操作加速AC支持和PC证据搜索,从而提高自适应约束传播的效率。对几类典型benchmark问题的测试结果表明,算法AC_MaxRPC_Bitwise在总体性能上明显优于AC及原自适应约束传播算法。     

采用混合遗传算法的敏捷卫星自主观测任务规划

为改进敏捷卫星观测大规模地面目标点时传统的遗传算法求解效率低下的问题,提高智能优化算法的求解效率,改进了传统的遗传算法,提出了禁忌退火遗传混合算法。首先,考虑到航天器在观测地面目标点的过程中所面临的时间约束、姿态轨道动力学约束等多种约束条件,建立了相应的适应度函数。所提出的适应度函数能够兼顾高观测收益与低观测能耗,反应了实际工程问题的观测需求。随后,为改进传统遗传算法的变异过程,提出了禁忌退火变异方法。这一变异方法在个体变异寻优的过程中,引入了禁忌搜索方法与Metropolis法则,提高了算法搜寻到全局最优解的概率,加快了算法的收敛速度。研究结果表明,与传统的遗传算法相比,禁忌退火遗传混合算法节省了约40%的算法运行时间,该算法的运行效率也高于退火遗传算法、禁忌遗传算法等其他种类改进的遗传算法,从而验证了禁忌退火遗传混合算法求解敏捷观测卫星任务规划问题的高效性。     

一种任务分配问题的快速剪枝优化算法

任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高。文章提出了一种新的求解任务分配问题的方法——剪枝优化算法。算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题。对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解。论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较。仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度。     

改进人工势场法的冗余机械臂避障算法

针对传统人工势场法应用于串联型冗余机械臂避障时无法约束各关节位姿、陷入局部极小后难以逃离的问题,提出一种改进人工势场法.建立冗余机械臂运动学模型,采用线段球体包络盒模型进行碰撞检测.在笛卡尔空间内建立末端引力势场和障碍物斥力势场,在关节空间内建立目标角度引力势场,所有势场共同作用引导机械臂运动.在关节空间内求解虚拟目标角度并采用高斯函数建立虚拟引力势场处理局部极小问题.利用七自由度冗余机械臂进行仿真和实验,结果表明:算法可约束各关节位姿,陷入局部极小后可引导机械臂逃离局部极小,最终完成避障;避障结束时各关节角度最大误差为0.8°,末端平均位置误差和平均姿态误差分别为0.010 m和2.40°,均小于传统算法;避障过程中各关节运动幅度小于传统算法.改进算法可引导机械臂逃离局部极小并完成避障,同时提高避障结束时各关节及末端的定位精度,对冗余机械臂的避障研究及应用具有一定的指导意义.     

基于改进混合蛙跳算法的多约束车辆路径优化

针对多中心分布式企业存在的产品成本差异化问题,建立包括产品成本、多车场、多车型在内的多约束车辆路径模型,并设计求解该模型的改进混合蛙跳算法. 根据问题特性,改进聚类算法并结合邻近矩阵构造初始青蛙种群;提出子群概念,设计自内而外的交流演化模式;定义远离矩阵,对青蛙进行引导性邻域搜索. 将所设计的算法进行多组不同的对比实验,结果表明,所设计的算法通用性强,实用性高,与遗传算法、蚁群算法这类传统经典算法相比,具有更好的收敛速度与求解精度,可以有效解决此类问题;考虑产品成本的调度方案总成本平均减少6%,占产品总成本的13%,可以为企业提供更合理的车辆配送方案.     

几何约束多解问题

针对几何约束求解的多解性问题,将约束分成两个集合:原约束集合和增加的额外约束集合。用求解器求解出全部解后,利用提出的混合遗传蚂蚁算法,搜索全部解空间,在算法的初始阶段采用遗传算法,产生信息素的初始分布;在算法的后期采用蚂蚁算法。由于在遗传算法中使用随机的种群,不仅提高了蚂蚁算法的速度,而且在求解时能避免陷入局部最优解。通过启发式搜索算法使增加的额外约束得到最大化满足,从而寻找到符合用户意图的解。     

基于成功回溯的约束推理技术

提出了基于成功回溯的约束推理技术及其相应的约束求解算法MAC_BTS,并证明了该算法在一条分枝上回溯到网络相容状态的最坏时间复杂度是O(ned3)。实验结果表明:新的MAC_BTS算法在大多数问题的求解上较国际上流行的MAC3rm算法以及MAC_LC算法取得了10%~20%的加速,甚至在某些问题上达到50%,可见该算法在效率上更优。     

启发式学习自动化程序指令的可达性测试

为了测试程序指令的可达性,需要搜索可触发包含该指令的控制流路径执行的测试用例。该问题可等价为路径约束满足问题的自动求解,求解结果即为验证指令可达的测试用例。为了提高自动求解的性能,在前向检测算法基础上改进设计了R_BinSearchFC算法,算法结合了边界测试数据选取和二叉树搜索技术,可有效提高对数据空间的搜索速度,并可扩展到在实数域空间的求解搜索。实验结果表明,采用了启发式学习的R_BinSearch算法可自动生成有效的测试用例,完成对指令的可达性测试。