立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.     

收缩背包问题的并行分枝界限算法

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。     

一类有效的一般并行分枝界限算法

本文针对使用ｐ个处理器选出ｐ个子问题进行并行扩展的一类并行分枝界限算法,提出了一个称作双层立体堆的数据结构,给出了ＰＲＡＭ－ＣＲＥＷ模型上的并行分枝界限算法。假定在状态空间树上扩展一个结点最多生成ｒ个子结点,本文提出的并行算法最多使用ｒ个处理器,其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ）。对于ｌｏｇｈ〈ｒ〈ｈ,在系数因子ｌｏｇｈ／ｌｏｇｒ的范围内,以及对于ｌｏｇｈ〉ｒ,在系数因子ｒ／ｌｏｇ     

面向流水线结构的并行匹配算法

本文提出一种面向流水线计算机的立体视觉并行匹配算法,使立体视觉算法所需的低层视觉信息处理和特征匹配都能在具有高速视频总线的流水线计算机中完成,这样既简化了视觉系统的结构,又大大提高了处理速度.匹配中应用了排序、方向和幅度约束作为相似性判断,并根据匹配点邻域中的视差梯度,利用松弛迭代法提高匹配的可靠性.算法已在PIPE流水线计算机上实现,256×256图像的立体视觉算法可在10秒内完成.     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。     

一个并行分枝限界算法产生器的设计与实现

分枝限界算法是一种求解组合优化问题的一般性方法,并行化是提高算法性能的有效手段。文章使用［５］中提出的算法模式和结构模式的概念和思想设计并实现了一个并行分枝限界算法的产生器。该产生器通过提供并行分枝限界算法的抽象框架,将它应用于要求解的问题,可以得到问题的并行分枝限界算法。     

基于搜索空间划分的并行概念生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。本文提出了一种基于搜索空间划分的并行概念生成算法,它对整个闭包搜索空间进行划分,并引入一种有效的测试方法,只搜索那些能生成正规闭包的子搜索空间,从而有效提高搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度;由于所有子搜索空间相对独立,因此很容易得到一个井行的概念生成算法。     

并行图像处理算法的设计与实现

在并行计算机上使用并行算法对数字图像进行处理,使一些计算复杂度很高和计算量很大的计算问题得到较好解决,并获得满意的结果。     

基于交互式的并行蚁群优化算法

传统蚁群优化算法研究已经取得了很多重要的成果,但是在解决大规模组合优化问题时仍存在早熟收敛,搜索时间长等缺点.为此,将邻域搜索技术与蚁群优化算法进行融合,提出一种新的并行蚁群优化算法,实验结果表明,在解决大规模TSP问题时,该算法求解质量和稳定性更好,在短时间内即可得到较高质量的解.     

整体异步的并行转换算法

针对Fukushima提出的求解无约束最优化问题的同步并行转换算法(PVT),提出一个整体异步并行算法,该算法去除了并行计算中同步与通信的开支。在一定的条件下,证明了该算法具有全局收敛性以及线性收敛速度。数值试验结果表明,异步PVT算法优于同步PVT算法。     

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索,进行这些查询用到的算法与位置和范围查询的算法不同,需要专门进行研究,介绍了一种分支界限遍历R树算法,并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程,以减少搜索空间中需访问结点的数量,有效地进行k-NN搜索。     

基于双禁忌对象的并行禁忌搜索算法

禁忌搜索算法是解决组合优化问题的一种主要方法,是克服NP完全问题的一个有效途径。随着计算网格的发展,将禁忌搜索算法引入到这种分布式并行计算环境中,具有广泛的应用价值。提出了一个基于双禁忌对象的禁忌搜索算法,在此算法的基础上,利用并行化分散搜索策略来提高算法的求解精度。实验结果表明该并行禁忌搜索算法性能较高。     

分配问题的计算机方法

分配问题是一个组合优化问题。传统计算机求解分配问题的方法中，既有枚举法、最小元素法、行（列）扫描法和损益分析等算法，也有如分枝限界法、匈牙利算法及其改进算法。本文在对这些计算机方法进行分析和仿真的基础上，将一个随机并行算法用在解决分配问题上，并且对各种方法的运行结果进行了比较。     

基于遗传算法的故障诊断的研究

介绍了遗传算法在故障诊断中的种种应用，指出将遗传算法应用于故障诊断可减少运算量、缩短平均诊断时间、提高诊断效率和故障识别精度。     

一类One to One安排优化问题及其进化算法

针对One to One安排问题在一般情况下的优化模型。设计一个新的进化算法求解该问题。该算法采用新的启发式变异算子和局部搜索算子。理论分析表明算法以概率1收敛到全局最优解,最后进行计算机仿真,结果表明算法是有效的。     

Modeling and Optimizing Dynamic Dial-a-Ride Problems

Dial-a-ride is an emerging alternative to traditional public transportation systems. The aim of this paper is to reduce the gap between the models studied in optimization literature and the requirements of practical applications. We also describe the algorithms implemented in DARIA, a PC program for the optimization of static and dynamic dial-a-ride problems. We briefly illustrate two case studies and future developments of the DARIA project.     

基于图染色问题的混合优化算法

为了提高图染色算法的寻优能力和收敛速度,结合禁忌搜索算法和遗传算法的优缺点,提出了一种混合优化算法（GA-HM）。该算法利用遗传算法生成初始解,将染色元素分到不同的色集中,然后通过禁忌算法进行变领域搜索来更新顶点染色。实验结果表明,GA-HM对求解相同的目标解具有更好的全局最优性和收敛性。     

A new optimal algorithm for the permutation flow-shop problem and its parallel implementation

This paper describes a new parallel algorithm for solving n-job, m-machine flow-shop problems. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of all search method to keep high efficiency of parallel processing, when the sub-problem becomes smaller than certain size. It is shown that its implementation on both nCUBE2 and LUNA88k2 gives very good performance characteristics.