启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

求解带动不平衡约束的卫星舱布局问题的启发式算法

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.     

基于蚁群算法的带平衡约束矩形布局问题的启发式求解

以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。采用启发式策略设计了分区域分步布局法,该策略将圆形卫星舱承重板分成4个区域,分区域同步进行布局。当所布矩形和区域都确定时,采用最左最底填充策略进行布局。该方法通过不干涉约束,使布局紧凑,通过控制系统质心的位置,使系统保持平衡。在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

基于启发式的约束满足问题AC系列算法改进研究

约束满足问题是人工智能领域中一个重要的研究方向,其研究结果在符号推理、系统诊断、真值维护系统、资源分配和产品配置等问题中有广泛的应用。局部相容性定义了约束满足问题在约束传播过程中必须满足的性质,是约束传播发展的主要方向。而对于较为复杂的相容性问题中的AC系列算法的改进可谓难上之难。本文围绕着以弧相容、Singleton弧相容为代表的相容性技术和求解算法展开,主要针对AC-2001算法、SAC算法等进行优化改进,重点基于启发式进行改进,使之获得了更快的筛选速度。尤其对于SAC算法,大大减少了约束检查次数,获得了较为成功的基于启发式的改进结果。     

求解平衡约束圆形Packing问题的快速启发式并行蚁群算法

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1~3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.     

启发式算法在网络计划多资源平衡中的应用

多资源平衡问题是项目管理网络资源优化的一个基本问题,论文提出一种在工期一定的情况下多资源平衡问题的启发式算法。由于项目的某项活动总是可以在最早开始时间和最晚开始时间确定的范围内开始,所以,通过时差管理采用不同的分配方式,就可以达到较高的资源利用率和降低项目的成本支出。论文编制了相应的程序并进行了仿真,得到了较优的结果。     

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

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

战时舰船抢修任务规划模型及启发式构造算法

针对战时舰船抢修问题,研究在维修资源有限的情况下,如何合理地安排维修活动,以最短的时间、最少的手段使装备至少具有完成部分任务的能力,其目标是从整体上高效分配资源,缩短维修所需的时间。根据规划调度理论,采用基于人工智能的规划调度方法,提出了贪婪随机变邻域搜索算法,该算法求解速度快、解质量稳定。在此基础上建立了舰船抢修任务规划约束优化模型,并研究了战时舰船抢修任务的启发式求解框架和启发式构造规则。模型及算法在战时维修保障决策支持系统得到了实际应用,经证明该算法是一种非常实用的求解途径。     

用约束满足自适应神经网络和有效的启发式算法解Job-shop调度问题

提出一种用约束满足自适应神经网络结合有效的启发式算法求解Ｊｏｂ－ｓｈｏｐ调度问题．在混合算法中,自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性,被用来求得调度问题的可行解,启发式算法分别被用来增强神经网络的性能、获得确定排序下最优解和提高可行解的质量．仿真表明了本文提出的混合算法的快速有效性．     

MOHHA求解不可靠生产线多目标缓冲区分配问题

研究含有可失效机器的不可靠串行生产线上缓冲区容量分配问题,以最大化生产线生产率和最小化生产线缓冲区总量为多目标,提出一种多目标混合启发式算法（MOHHA）。采用了离散事件仿真方法,建立生产率与缓冲区容量分配的仿真模型作为算法的评价工具。算法第一步求得生产线最大生产率,并作为目标生产率进一步求解最小化缓冲区总量。通过三组测试算例,与以往研究结果作对比验证了算法的有效性和优越性。     

Hybrid heuristic algorithm for two-dimensional steel coil cutting problem

This paper is concerned with the problem of two-dimensional cutting of small rectangular items, each of which has its own deadline and size, from a large rectangular plate, whose length are more than one thousand times its width, so as to minimize the trim loss and the reduction of the times of clamping and changing speed are also concerned. This problem is different with the classical two-dimensional cutting problem. In view of the distinguishing features of the problem proposed, we put forward the definition of non-classical cutting, that is to say, put a series of items on the rectangular plates in their best layout, so as to enhance utility and efficiency at the same time. These objectives may be conflicting and a balance should be necessary, so we present a Hybrid Heuristic Algorithm (HHA), consisting of clustering, ordering, striping and integer programming etc. We demonstrate the efficiency of the proposed algorithm through the comparison with the algorithm we studied before.     

Gout-ITS系统的正向启发式推理算法

分析了痛风临床诊治智能教学系统（intelligent tutoring system for instruction of gout clinical diagnosis and treatment,Gout-ITS）要像人类医疗专家那样进行临床诊治推理所需的领域知识及其特点,提出了知识库的层次结构模型和正向启发式推理算法。该算法不仅能够对病例做出正确的诊断和有效的治疗,而且还能够使诊治代价降至最小。最后将该算法与一般产生式系统的正向推理算法进行了比较,阐述了该算法的优点。     

钢铁企业生产资源平衡计划系统分析与设计

针对市场需求剧烈变动环境下,钢铁企业如何利用有限产能、平衡资源分配、优化产品组合的问题,提出了通过生产资源平衡计划系统来解决的方法.在系统功能需求分析的基础上,通过数据流图、实体关系图、用例图及时序图构建钢铁生产资源平衡计划系统模型,详细描述系统的设计目标、业务流程及子模块协作机制.该系统以基于数学优化和智能计算的优化计算引擎为核心,综合考虑盈利指标、市场需求、生产能力等因素进行资源平衡,为生产与销售提供决策支持.     

一种面向柔性生产的动态调度模型*

为解决柔性生产中两个生产单元与多作业对象的优化调度问题,提出一种基于能力平衡的动态调度模型。将生产单元模型化为一种容器,把生产能力视为容积,并划分为设定能力和机动能力。通过建立两单元的机动能力连通模型,根据流体力学原理提出了一组动态调度规则,并开发了可用于现场调度的高效的启发式优化算法。在滚装运输企业进行的案例研究表明,该模型及其算法在实际生产运作中具有切实的可行性和有效性。     

A heuristic algorithm for group scheduling

Group technology is a rapidly developing productivity improvement tool that can have a significant impact on the development of totally integrated manufacturing facilities and flexible manufacturing systems. Production scheduling associated with group technology is called “Group Scheduling”. There are many heuristic algorithms developed for general job shop applications based on unrealistic hypothesis, complicated computations etc., which are not addressed to group scheduling. In this paper, from the existing algorithms for group scheduling, a heuristic algorithm has been developed and programmed for computer/microcomputer applications. The developed algorithm has been used to determine the optimal group and the optimal job sequence for a batch type production process with functional layout. The developed algorithm is far simpler and easier to compute, compared to the other similar heuristic algorithms and certainly in comparison to other optimization methods such as branch and bound method.     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes

A fault-tolerant and heuristic routing algorithm for faulty hypercube systems is described.To improve the efficiency,the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors‘ faulty link information to avoid unnecessary searching for the known faulty links.Furthermore,the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used.The algorithm routes messages through the minimum feasible path between the sender and receiver if at least one such path exists,and takes the optimal path with higher probability when faulty links exist in the faulty hypercube.