求解不等圆Packing问题的一个启发式算法

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.     

A Hopeful CNF-SAT─Algorithm Its High Efficiency, Industrial Application and Limitation

1IntroductionWeobtainedaphysicalmodelfortheCNF--SATproblemyearsago['--'].Fromthismodel,andbyobservationandcomputing,wegotthephysicalhypothesisPHHYsimilartothatin[3].Now,wehavearrivedatthefollowingstrictmathematicalstatement.StatemeDt.IfthehypothesisPHHYiscorrect,thentherewillbeanalgorithmAforcheckingsatisfiabilityofanygivenCNFx.Awillgiveadefiniteanswer.TheprobabilityforAtogivearightansweriswherelxlisthelengthofx,Pisanabsolute(universal)polynomialwithpositivecoefficients,tistherunning…     

利用改进的微分进化算法求解带平衡约束的圆形packing问题

提出了一种改进的微分进化算法(DE)求解二维带平衡约束的圆形packing问题．首先，构造出等价的物理模型,定义系统的能量函数,再对能量函数进行全局优化,从而间接得到问题的近似解．其中引入的参数动态调整策略在计算初期维持个体的多样性,后期加快算法的收敛速度,提高了DE算法的性能．最后，对两个算例进行了数值计算,实验结果证明了算法的有效性．此算法思路可推广应用于求解其它类型布局问题．     

蛋白质HP模型的改进和PERM算法求解

HP模型是一种被广泛研究的简化的蛋白质折叠模型.在蛋白质螺旋结构的预测上有很高的可信度.但是HP的正方格点模型存在能量计算缺陷,影响其对链上特定结构的计算.针对这一缺陷,给出一种模型上的修正,引入了三角化的格点模型.利用求解格点蛋白质模型高效的算法PERM对通用算例进行了基于2-D三角格点模型的仿真计算.得到了紧密的蛋白质链折叠构型.构型最小能量比正方格点模型更低,得到的标准算例构型比较吻合实际蛋白质折叠的直观构型.计算结果验证了改进模型的有效性.对后续的研究提出了建议.     

求解HP格点模型的最佳优先搜索算法

HP格点模型是目前预测蛋白质折叠结构的一种最简单和最流行的模型,该模型已被证明是NP完全问题。将问题的解空间组织成树型结构,利用启发式规则—k步探测法对结点的可能分支进行评估,采用最佳优先策略搜索解空间树。最后用最佳优先搜索算法(BF)对一组公认的算例进行了实算,计算结果表明,BF计算效率优于传统的遗传算法和Monte Carlo方法。     

一种基于禁忌搜索的作业车间调度算法

文章描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术和前瞻思想,为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比2004年提出的ISSB算法和另一种基于禁忌搜索的TSAB算法更好的结果。     

等球Packing问题的序列对称换位算法

为处理等球Packing问题,在基本拟物算法的基础上设计了序列对称换位策略,形成了一个启发式的序列对称换位算法。在球形容器内装填1～50个等球时,此算法改进了其中45项当前记录。特别地,此算法成功将68个半径为1的等球装进半径小于5的球形容器。此结果证否了一个猜想,该猜想认为半径为5的球形容器至多只能装下67个半径为1的等球。其结果的质量说明了序列对称换位算法的有效性。     

求解长方体Packing问题的纯粹拟人算法

对于具有NP难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空间利用率,将当今国际上的最好纪录提高了1.05个百分点.     

一种求解集装箱装载问题的启发式算法

所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积裁率.对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法.本文提出一种求解此问题的基于最大穴度优先原则的启发式算法.算法中使用了两个重要的策略:最大穴度原则和最小边度原则.用一些公开的算例对算法性能进行了实算测试,测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法.     

基于任务复制的分簇与调度算法

针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法.