一种不规则零件排样的新粒子群优化策略

基于图形扫描转换的启发式底左（Heuristic Bottom-Left,HBL）算法,把一种最大速度收缩策略（Maximal Velocity Contractile Strategy,MVCS）的粒子群优化（Particle Swarm Optimization,PSO）算法应用于不规则零件的优化排样,给出了新的排样组合优化算法（MVCS-PSO）的粒子构造方法和零件排样过程,通过实例把该算法与模拟退火遗传算法（Simulated Annealing Genetic Algorithms,SAGA）进行优化排样比较,实验结果表明,具有良好的非线性和动态搜索性能的MVCS-PSO算法是求解排样问题的一种高效算法。     

基于自动碰撞技术的最优排样算法

提出一种针对不规模形状冲压零件排样的智能化算法。该算法利用了一种新的自动碰撞技术以寻求尽可能多的可行排样,并自动计算碰撞零件和固定（被撞）零件之间的动态距离。     

矩形件带排样的一种遗传算法

采用遗传算法解决矩形件带排样问题,用带符号的有序整数串作为初始种群个体,改善了初始个体解的质量．提出基于最低水平线的择优插入算法,在解码过程中动态地调整个体中的零件顺序,选取最适合的零件进行填充,使零件排放紧凑,提高了材料的利用率．对20多道基准排样例题的实验计算结果表明,文中算法速度快,所得排样方案的材料利用率高．最后提出利用该算法解决VLSI模块布局问题的方法框架．     

基于SPEA2+算法的Web服务选择研究

服务选择算法是影响组合服务的QoS和服务组合性能高低的关键因素。针对将多维QoS属性加权聚合为一个目标函数进行优化的选择算法不能实质性地解决基于QoS的Web服务选择问题,采用改进的强度Pareto进化算法（SPEA2+）多目标优化求解该问题,设计了一种Web服务选择算法。该算法在满足声誉、可靠性和可利用性属性的约束下,同时最小化服务时间T和服务费用C,以产生Pareto最优解集。通过与运用SPEA2算法求解该问题的实验对比,表明了两算法所获取的Pareto最优解集中QoS属性T和C各均值各有优劣,用户可依据对T或C的偏好择优选择。     

基于差分有序数组的图像匹配快速算法

本文提出了一种对模板匹配算法进行改进的快速算法。首先，对模板内所有像素进行排序并差分变换为函数F1（），将模板覆盖下的子图像函数f（x，y）累进求和变换为函数F2（），然后求取F1（）与F2（）乘积的最大值。由于模板存在大量灰度值相同的像素，经排序差分后F1（）中会有很多0和1，乘1和0的运算可以不做，从而消去了模板运算中的大量乘法和加法运算，同时在模板匹配移动过程中利用相邻窗口间的数据相关性，减少重复运算，和传统匹配算法相比，计算复杂度大大降低。     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

面向工业零件的机器人单目立体匹配与抓取

为实现通用性强、快速、准确的工业机器人6自由度零件抓取,提出了一种基于单目视觉引导的零件3维抓取方法．首先,采用按倾角分层的Chamfer距离匹配算法建立图像与待匹配模板的相似度函数,并运用爬山法局部优化的遗传算法搜索最优匹配结果;然后,通过CAD（计算机辅助设计）模型建立离线3D模板库,将匹配算法拓展到适用于复杂结构零件的空间6自由度位姿检测;最后,由各坐标系间的矩阵转换和系统标定得到机器人的抓取信息,从而实现零件的3维抓取．实验结果表明,优化后的位姿检测算法在匹配速度和准确性上均有所提升,且基于该检测算法的机器人3维抓取实验的位置误差在2 mm以内、转角误差在2°以内,可用于工业智能机器人的零件抓取．     

基于联合优化的强耦合孪生区域推荐网络的目标跟踪算法

针对区域推荐网络（RPN）在目标跟踪任务中出现的最大分类分数与最佳边框不匹配的问题,提出一种基于联合优化的强耦合孪生区域推荐跟踪算法（SCSiamRPN）。首先,采用Bounded IoU方法来优化正样本交并比（IoU）值的计算,通过分解公式、固定变量、替换差值和约束近似的操作来简化计算过程。然后,优化损失函数结构,通过在分类损失函数中添加以IoU值为纽带的耦合因子来联合分类任务和边框回归任务,以提升高IoU样本的损失值;通过在边框回归损失函数中添加以IoU为主变量的加权系数来提高目标中心样本的贡献,以提升边框定位精度。仿真结果显示：SCSiamRPN算法在OTB100数据集上的精度和成功率为0.86和0.64;同基于孪生区域推荐候选网络的高性能单目标跟踪（SiamRPN）算法相比,均有3%的提升。实验结果表明：SCSiamRPN算法解决了最大分类分数与最佳边框不匹配的问题,增强了分类和边框回归任务的耦合性,且在不损失跟踪速度的前提下实现了跟踪精度的较大幅度提升。     

基于CUDA架构的三维CPML-FDTD并行方法

为解决时域有限差分（FDTD）算法应用于电大尺寸目标仿真的巨大耗时问题,应用FDTD算法的并行特性和通用图形处理器（GPGPU）技术,实现了一种基于计算统一设备架构（CUDA）的三维FDTD并行计算方法,采用了时域卷积完全匹配层（CPML）吸收边界条件模拟开域空间,对不同网格数目标仿真计算。进一步结合FDTD算法和CUDA的特点进行了优化,当计算空间元胞数在十万数量级及以上时,优化前后GPU运算相对于同时期的CPU分别可获得10和25倍以上的加速,结果表明该方法较适合用于实际电磁问题的仿真。     

基于神经网络的3D打印批次排样研究

针对3D打印批次排样是一个建立在多约束条件下的复杂优化问题,本文提出一种基于Hopfield人工神经网络的3D打印批次排样方法。通过对3D打印批次排样目标的设定,建立了Hopfield人工神经网络的能量函数。通过神经网络优化计算,实现了将3D打印工件在三维空间的排布问题转化为二维图形的输出。该算法实用性强,提高了工件的加工效率。     

FFD算法的研究与应用

排课问题是一个有约束的、多目标的组合优化问题,而FFD（First Fit Decreasing）算法是计算机数学组合优化的近似算法。文中针对排课中教室分配问题,引入FFD算法,采用首次适应贪婪思想,先将教室和课程按容量和上课人数从大到小排序,然后依次从前往后选择最先适合教室分配给课程。以国际自动排课问题研究团队（WATT）组织的第二次国际竞赛数据和规则为基准,通过与二部匹配算法、NFD（Next Fit Decreasing）和NF（NextFit）策略进行比较,FFD算法能在最优安排全部课程的上课教室前提下,对于竞赛给定的惩罚函数,所得惩罚值最小,并且教室利用率最高。     

List’s worst-average-case or WAC ratio

We analyze the List scheduling algorithm for the problem of minimizing makespan using a worst-average-case or wac analysis technique, previously used by Kenyon for analyzing the Best Fit bin packing algorithm. We show that List’s worst-average-case or wac ratio asymptotically approaches 2, as m→∞. Thus, List’s worst-case behavior is not overly dependent on the order of job arrivals. C.J. Osborn is supported in part by NSF grant CCR 0105283. This work was done while the author was an undergraduate student at Michigan State University. E. Torng is supported in part by NSF grant CCR 0105283.     

动态分区分配与回收算法的模拟

为了探索和改进操作系统课程的教学方法,加强学生对动态分区的深入理解,采用C语言中的链表模拟实现了动态分区中的两种分配算法:首次适应算法(First Fit)、最佳适应算法(Best Fit),以及内存回收算法。模拟结果表明:这种理论加实践的教学不仅有助于学生掌握操作系统的理论知识,使抽象内容具体化,而且有助于提高学生分析数据、选择数据结构以及综合编程的能力。     

二维矩形条带装箱问题的底部左齐择优匹配算法

针对二维矩形条带装箱问题提出了一种启发式布局算法,即底部左齐择优匹配算法(lowest-level left align best fit,简称LLABF). LLABF算法遵循最佳匹配优先原则,该原则综合考虑完全匹配优先、宽度匹配优先、高度匹配优先、组合宽度匹配优先及可装入优先等启发式规则.与BL(bottom-left),IBL(improved-bottom-left)与BLF(bottom-left-fill)等启发算法不同的是,LLABF能够在矩形装入过程中自动选择与可装区域匹配的下一个待装矩形     

Average Case Analysis of Bounded Space Bin Packing Algorithms

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.     

Bounded Space On-Line Bin Packing: Best Is Better than First

We present a sequence of new linear-time, bounded-space, on-line bin packing algorithms, the K -Bounded Best Fit algorithms (BBF _K ). They are based on the Θ(n log n) Best Fit algorithm in much the same way as the Next-K Fit algorithms are based on the Θ(n log n) First Fit algorithm. Unlike the Next-K Fit algorithms, whose asymptotic worst-case ratios approach the limiting value of \frac 17 10 from above as K \rightarrow ∈fty but never reach it, these new algorithms have worst-case ratio \frac 17 10 for all K \geq 2 . They also have substantially better average performance than their bounded-space competition, as we have determined based on extensive experimental results summarized here for instances with item sizes drawn independently and uniformly from intervals of the form (0, u] , 0 < u ≤ 1 . Indeed, for each u < 1 , it appears that there exists a fixed memory bound K(u) such that BBF _K(u) obtains significantly better packings on average than does the First Fit algorithm, even though the latter requires unbounded storage and has a significantly greater running time. For u = 1 , BBF _K can still outperform First Fit (and essentially equal Best Fit) if K is allowed to grow slowly. We provide both theoretical and experimental results concerning the growth rates required. Received November 30, 1992; revised November 5, 1999.     

潜水器舱室空间布局的多学科设计方法研究

载人潜水器舱室空间布局涉及到多目标、多学科问题,通过对潜水器舱室空间的分析,研究了多学科设计优化方法对于这类多目标、多学科问题求解的有效性。建立潜水器多学科设计优化方法和协同优化思路,分解潜水器舱室并对潜水器舱室空间进行详细描述,构建基于Pareto的多目标遗传算法,对潜水器舱室空间进行多学科分解和计算,最终获得潜水器舱室空间设计方案。     

一种基于粒子群算法的改进多目标文化算法

提出一种基于粒子群算法的改进多目标文化算法并用于求解多目标优化问题.算法中群体空间采用多目标粒子群优化算法进行演化;信念空间通过对形势知识、规范化知识和历史知识的重新定义使之符合多目标优化问题;信念空间和群体空间的交互通过自适应的接受操作和影响操作来实现.若干多目标标准测试函数的仿真结果表明,改进多目标文化算法能够在保持Pareto解集多样性的同时具有较好的均匀性和收敛性.     

A multi-objective differential evolutionary algorithm for constrained multi-objective optimization problems with low feasible ratio

Most current evolutionary multi-objective optimization (EMO) algorithms perform well on multi-objective optimization problems without constraints, but they encounter difficulties in their ability for constrained multi-objective optimization problems (CMOPs) with low feasible ratio. To tackle this problem, this paper proposes a multi-objective differential evolutionary algorithm named MODE-SaE based on an improved epsilon constraint-handling method. Firstly, MODE-SaE self-adaptively adjusts the epsilon level in line with the maximum and minimum constraint violation values of infeasible individuals. It can prevent epsilon level setting from being unreasonable. Then, the feasible solutions are saved to the external archive and take part in the population evolution by a co-evolution strategy. Finally, MODE-SaE switches the global search and local search by self-switching parameters of search engine to balance the convergence and distribution. With the aim of evaluating the performance of MODE-SaE, a real-world problem with low feasible ratio in decision space and fourteen bench-mark test problems, are used to test MODE-SaE and five other state-of-the-art constrained multi-objective evolution algorithms. The experimental results fully demonstrate the superiority of MODE-SaE on all mentioned test problems, which indicates the effectiveness of the proposed algorithm for CMOPs which have low feasible ratio in search space.     

基于偏好的多目标遗传算法

多目标优化问题中,人们往往只是对目标空间的某一区域感兴趣,因此这就需要在这一特定的区域能够得到比较稠密的Pareto解,但传统的方法权值法无法满足这种需求而且不能处理目标空间是非凸的情况,遗传算法虽然是现在公认的处理多目标优化问题比较有效的方法,但遗传算法是在目标空间内进行全空间寻优,因此最终得到的Pareto解是均匀分布的,这样遗传算法也不能满足人们的这一要求。针对这个问题提出了基于偏好的多目标遗传算法,把个人偏好加到优化过程中,利用偏好信息来引导优化方向,通过仿真把该算法和权值法、NSGA-II进行比较,结果证明了该算法的可行性和有效性。