An Efficient Optimization Procedure for Tetrahedral Meshes by Chaos Search Algorithm

A simple and efficient local optimization-based procedure for node reposition-ing/smoothing of three-dimensional tetrahedral meshes is presented.The initial tetrahedral mesh is optimized with respect to a specified element shape measure by chaos search algorithm,which is very effective for the optimization problems with only a few design variables.Examples show that the presented smoothing procedure can provide favorable conditions for local transformation approach and the quality of mesh can be significantly improved by the combination of these two procedures with respect to a specified element shape measure.Meanwhile,several commonly used shape measures for tetrahedral element,which are considered to be equivalent in some weak sense over a long period of time,are briefly re-examined in this paper.Preliminary study indicates that using different measures to evaluate the change of element shape will probably lead to inconsistent result for both well shaped and poorly shaped elements.The proposed smoothing approach can be utilized as an appropriate and effective tool for evaluating element shape measures and their influence on mesh optimization process and optimal solution.     

An Optimum Placement Search Algorithm Based on Extended Corner Block List

A non-slicing approach,Corner Block List(CBL),has been presented recently.Since CBL only can represent floorplans without empty rooms,the algorithm based on CBL cannot get the optimum placement.In this paper,an extended corner block list,ECBLλ,is proposed.It can represent non-slicing floorplan including empty rooms.Based on the optimum solution theorem of BSG(bounded-sliceline grid),it is proved that the solution space of ECBLn,where n is the number of blocks,contains the optimum block placement with the minimum area.A placement algorithm based on ECBLλ,whose solution space can be controlled by setting λ,the extending ratio,is completed.Whenλ is set as n,the algorithm based on ECBLn is the optimum placement search algorithm.Experiments show that λ has a reasonable constant range for building block layout problem,so the algorithm can translate an ECBLλ representation to its corresponding placement in O(n) time,Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorthms based on CBL.Meanwhile,compared with other algorithms,the proposed algorithm can get better results with less runtime.     

求解难可满足性问题的混合算法

提出了一个求解难可满足性问题的简单混合算法．拟人和禁忌表两个策略被给出．数值实验表明，对于一类公认比较难的可满足性问题，该算法胜过目前据认为是最好方法之一的NOVELTY算法．     

A Practical Propositional Knowledge Base Revision Algorithm

This paper gives an outline of knowledge base revision and some recently presented complexity results about propostitional knowledge base revision.Different methods for revising propositional knowledge base have been proposed recently by several researchers,but all methods are intractable in the general case.For practical application,this paper presents a revision method for special case,and gives its corresponding polynomial algorithm.     

一种改进的警示传播算法求解Max-SAT问题

Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。     

Tabu Search集中性和多样性自动平衡下的增强搜索策略

在禁忌搜索算法中,集中性搜索与多样性搜索是缺一不可但又相互矛盾的两个方面。本文提出了一种在禁忌搜索集中性和多样性自动平衡下的增强搜索策略算法,这种算法在集中性搜索与多样性搜索之间保持合理平衡的同时,又进一步对结果加强集中性搜索或者多样性搜索,以获全局最优解。以组合优化中的典型难题TSP为例,通过自动更换邻域、候选集,较好地解决了集中性搜索与多样性搜索的冲突。仿真实验表明,解的质量提高了,验证该算法有效。     

On optimizing the satisfiability (SAT) problem

1IntroductionThesatisfiability(SAT)problemistodeterminewhetherthereexistsanassignmentofvaluesin{0,1}toasetofBooleanvariables{x1,xm}thatmakesaconjunctivenormalform(CNF)formulatrue.ThesatisfiabilityproblemofaCNFformulawithatmostlliteralsineachclauseiscalledthel-SATproblem.Theoretically,for>3,theSATproblemisawell-knownNP-completeproblem.Andthus,thereexistsnopolynomialtimealgorithmfortheSATproblemontheassumptionthatPNP.Ontheotherhand,theSATproblemisfundamentalinsolvingmanypracticalprob…     

命题逻辑可满足性问题的算法分析

1 引言可满足性问题(以下简称SAT)是问:对于一个命题逻辑公式,是否存在对其变元的一个真值赋值使之成立?这个问题在许多领域都有非常重要的意义,其快速求解算法的研究成为计算机科学的中心课题之一。例如在机器定理证明领域,某命题是否是一个和谐的公理集合的推论,这个问题归结为该命题的反面与该公理集合一起是否是不可满足的。通过量词消去技术和Herbrand定理的作用,谓词逻辑公式的不可满足性可以归结为命题逻辑公式的不可满足性。在知识库维护中,当知识以逻辑公式的形式表达时,知识库的一致性检查可以归结为命题逻辑公式的可满足性。在开放逻辑中,新事实是否与已有的知识矛盾,当遇到事实反驳时如何求得最大和谐的知识集,这些问题最后都要归结为命题逻辑公式的可满足性。1971年Cook首次证明了SAT是NP-完全的,从而大量的计算问题都可以归约到SAT。正是由于SAT的重要地位,各国学者对它进行了广泛而深入的研究。     

Deductive Fault Simulation Algorithm Based on Fault Collapsing

The true value simulation is necessary in the critical path tracing fault simulation algorithm.The critical and non-critical inputs can be known after the number of controlling and non-controlling inputs and the criticality of output of every gate are determined.Single output region(SOR)is defined for non-critical lines,so many other non-critical lines can be obtained before fault simulation.The deductive fault simulation algorithm is used to compute the fault list for every possible critical line from bottom to top,which can greatly decrease the length of fault list and simulation time.The cross-sectios is defined to reduce the storage space.The experimental results are given at the end of the paper.     

Functional Knowledge Representation Based on Problem Reduction

This paper proposes an approach for functional knowledge representation based on problem reuction,which represents the organization of problem-solving activities in two levels:reduction and reasoning.The former makes the functional plans for problem-solving while the latter constructs functional units, called handlers,for executing subproblems designated by these plans.This approach emphasizes that the representation of domain knowledge should be closely combined with(rather than separated from)its use,therefore provides a set of reasoning-level primitives to construct handlers and formulate the control strategies for executing them,As reduction-level primitives,handlers are used to construct handler-associative networks,which become the executable representation of problem-reduction graphs,in order to realize the problem-solving methods suited to domain features.Besides,handlers and their control slots can be used to focus the attention of knowledge acquisition and reasoning control.     

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

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

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

基于遗传算法和禁忌搜索的混合优化策略

将禁忌搜索和遗传算法相结合,给出了一种求解优化问题的混合策略--禁忌遗传优化算法.该算法一方面为禁忌搜索找到了较好的初始点,减少了调用禁忌搜索的次数,另一方面也可以克服遗传算法爬山能力差的缺点,从而加快了收敛速度,提高了解的质量.通过实例验证了该优化算法的有效性和可靠性,并将其用于网络拥塞控制的研究中,为进一步实施网络拥塞控制提供了一种有效的途径.     

基于单亲遗传禁忌搜索算法的手术排程问题研究

针对规模较大的手术排程问题,分别以所有病人完成手术过程的最长时间和平均时间最小化为目标,构建了手术排程问题的数学模型。在分析解的最优化条件基础上,设计了一种将单亲遗传算法与禁忌搜索算法相结合的混合优化算法。按照个体的优劣及算法迭代情况设计了一种自适应选择机制,使个体自适应地选择执行变异操作或禁忌搜索算法。最后,仿真实验结果表明了所提算法的有效性和自适应选择机制的可行性。     

多箱型三维装箱问题及其优化研究

对多箱型三维装箱问题进行了描述,提出了求解该问题的禁忌算法。算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用三种邻域,利用邻域操作控制集装箱数量限制,采用惩罚函数处理集装箱重量约束和重心约束。介绍了算法的原理,给出了具有代表性算例实验结果并且进行了分析。实验结果表明了提出的禁忌算法对优化多箱型三维装箱问题的有效性。     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

基于禁忌搜索的人工蜂群算法及其应用

人工蜂群算法(artificial bee colony algorithm,ABC)是一种简单有效的群智能算法,通过蜜蜂之间的相互合作寻找最优解.禁忌搜索算法(tabu search algorithm,TS)是人工智能与局部邻域搜索算法的结合,具有非常好的全局寻优能力.为了提高ABC的搜索效率和全局寻优能力,结合TS,在ABC中增加一个禁忌表,提出了一种基于禁忌搜索的人工蜂群算法(artificial bee colony algorithm based on tabu search,TSABC).通过对10个常用的标准测试函数进行实验,对TSABC算法进行了验证,并将其应用于图像边缘检测中.实验结果表明,TSABC取得了较好的优化效果,提高了寻优精度和收敛速度,边缘检测结果也更理想.     

基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法,通过对不同重要程度的任务进行分层调度,得到较为满意的决策结果.该算法具有搜索空间小、求解速度快的优点.仿真结果验证了算法的有效性.     

基于禁忌搜索的复合嵌套分割算法*

本文介绍了嵌套分割算法（NP）的基本思想,提出了提高其优化效率的途径。介绍了禁忌搜索算法（TS）,并将禁忌搜索的思想引入嵌套分割算法的抽样和选取算子中,提出了一种复合优化算法(TSNP)来解决函数优化问题。TSNP算法结合了嵌套分割算法和禁忌搜索算法的优点,使其在优化性能、优化效率和可靠性方面具有明显的优越性。通过对几个函数优化实例的测试,并和其他算法进行了比较,结果表明该算法具有较好的计算效率和较快的全局寻优能力。     

物流动态车辆调度问题的混合禁忌搜索算法

在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。