博弈树启发式搜索的α-β剪枝技术研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。

定位-车辆路径问题的两阶段混合启发式算法

定位-车辆路径问题(LRP)集成了设施定位分配和车辆路径决策,属于NP-hard难题.为有效求解实际大规模的具有设施容量约束和车辆容量约束的LRP问题,设计了基于禁忌搜索及双种群蚁群算法的两阶段混合启发式算法.算法第1阶段采用禁忌搜索算法确定设施定位及客户分配,算法第2阶段采用双种群蚁群算法优化车辆路径,蚁群间的通信与协调通过信息素共享来实现.通过仿真试验并与其他启发式算法进行对比,结果表明,该算法是可行和有效的.

一类最小-最大车辆路线问题的启发式算法研究

针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型,并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。

启发式搜索算法的面向对象设计实现

描述了如何使用面向对象语言Java来设计启发式搜索算法。该设计充分利用Java语言的继承、封装和多态等特征,遵循开-闭原则、里氏替换原则等重要面向对象的设计原则,抽象化了启发式搜索算法,使得启发式搜索算法成为一个可复用构件。最后,演示了如何使用该可复用构件求解八数码问题。

求解0-1二次规划问题的迭代禁忌搜索算法

提出迭代禁忌算法求解0-1二次规划问题。在局部搜索过程中,使用禁忌搜索贪心跳坑策略,能够使算法有效跳出局部最优值的陷阱。采用国际上公认的30个算例作为算法测试实验集,与传统的禁忌搜索、模拟退火算法以及混合算法进行比较。实验结果表明,该算法在所有算例上都能够得到文献中报告的最优解,且计算效率明显优于其他算法。

最小-最大车辆路径问题的禁忌搜索算法

在对最小-最大车辆路径问题进行描述的基础上,建立了该问题的基本数学模型。针对最小-最大车辆路径问题的目标是最小化整个线路的最长子线路,本文提出了改进的禁忌搜索算法,并用一些典型算例进行了验证。计算结果表明,用该算法求解最小-最大车辆路径问题,不仅可以取得较好的计算结果,而且算法的计算效率较高,收敛速度较快。

UIO序列的启发式算法

UIO序列是对有限状态机进行功能测试的有效手段 ,在 VLSI设计、通信协议等时序系统中有很强的实际应用背景。文章基于可区分状态组这一概念设计了一个搜索算法 ,进一步利用搜索信息建立了一个基于“小于”关系的启发策略 ,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝 ,新设计出的多路 OPEN/CLOSED表存储机制也加快了相关的判别和处理过程。这些措施改进了搜索过程 ,减少了搜索信息的产生 ,提高了搜索速度。该算法与以往的算法相比 ,在时间和空间两方面都得到了很大改进。

博弈树启发搜索算法在五子棋游戏中的应用研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,结合五子棋游戏特征,设计了五成/双三、估值函数和α-β剪枝算法相结合的改进博弈树搜索算法,实现了人机智能对弈的五子棋游戏。

面向智能工厂应用的启发式板材排样优化算法

为给出企业合理的订购原材料方案,需要使得板材的利用率达到最大化.针对智能工厂应用场景,构建了二维规则板材的排料优化问题,并在此基础上提出了一种启发式的板材排样优化算法.该算法利用板材原料的基础信息,进行剪枝搜索排样.通过仿真实验结果表明:该算法具有较高的利用率以及时效性,较好地满足实际生产中的需求.

城市轨道交通列车加开计划编制模型研究

本文主要研究城市轨道交通在计划编制阶段由于客流不均衡需要在初始运行图加开列车的问题,在确保列车运行安全降低运营成本的前提下合理地加开列车实现运输能力的灵活配置。将列车运行过程形式化描述为事件-活动网络,构建了分时段多目标优化列车加开计划编制模型,提出了启发式决策规则与禁忌搜索算法相结合的两阶段求解算法。结合地铁运行实际数据,在高峰时段和平峰时段分别构建不同算例场景,验证了模型和算法的可行性和有效性。

同时配集货定位—路线问题的变邻域分散搜索算法

针对同时配集货的定位—路线问题,建立了三维指数混合整数规划模型,并设计了变邻域分散搜索求解算法,即在基本分散搜索算法的基础上保留参考集更新和组合策略的全局搜索能力。针对组合后的解可能是不可行解的问题,利用插入法将其改进为可行解,再运用变邻域搜索进行局部开发以提高可行解质量。为保证算法的多样性以进一步扩大搜索空间,初始种群采用两阶段混合多随机法构造。通过采用Lingo求解简单算例验证了模型的正确性,采用设计的变邻域分散搜索算法仿真已有算例并与其他算法比较,证明了该算法的有效性。

一种高质量的领域无关前向规划剪枝策略

前向启发式搜索和放宽规划方法被很多领域无关的规划器所采用,被认为是一种有效的规划范型.FF规划器利用放宽规划图计算状态的启发式估值,并提取有利动作集合进行前向搜索的剪枝.但过大的有利动作集合造成了过多的消耗.文中提出了一种新的高质量的领域无关剪枝策略.该策略根据放宽规划图的动作层和命题层之间的关系,提取出所谓的直接效用动作集合,此集合之外的其它动作都被剪枝.直接效用动作集合比FF的有利动作集合更加精简,更具启发性,能指导前向搜索集中在那些离目标更近的状态.根据直接效用动作作者开发了一种新的lookahead搜索邻居,并应用在改进后的增强型爬山搜索算法中,使得前向搜索具备良好的前瞻性.当增强型爬山法失败时,采取一种从局部极小值重启完备搜索的策略以保持系统完备性.通过对国际规划大赛基准问题的测试表明,基于该剪枝策略及前向搜索算法实现的前向规划系统有效地缩小了搜索空间,搜索的节点数目比FF的有利动作策略明显要少,搜索效率有显著的提升.

搜索算法在计算机程序设计竞赛中的研究

搜索算法是计算机技术在解决复杂问题时的一种重要策略,也是计算机程序设计竞赛中考核的主要知识点之一.首先分析了两种基础搜索策略(深度优先搜索和广度优先搜索)和相应的优化策略(剪枝优化和启发式搜索),然后讨论对于搜索策略的若干选择原则,得出针对不同问题应采用的搜索方案,最后结合计算机程序设计题目和经典搜索问题进行了相应验证.

捕食-被食动力学优化算法

为了解决复杂函数优化问题,提出了捕食-被食动力学优化算法。该算法假设在某生态系统中有捕食者和被食者两个种群。两类种群内部有竞争,种群内部密度越高竞争越激烈,种群特征更容易产生变化;强壮种群更容易在竞争中战胜弱势种群,从而使得自身特征发生较大改变。捕食者种群食用被食者种群后,其特征也发生变化。根据上述特点构造出了竞争算子、捕食-被食算子和生长算子,这些算子有利于使搜索跳出局部陷阱。本算法具有全局收敛性的特点,可求解一类极复杂优化问题。

一种用于求解0-1背包问题的动态伸缩算法

针对0-1背包这个非确定多项式(NP)完全难题,提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好的稳定性。

时空限制与任务复杂度对搜索结果的影响:跨设备实验研究

[目的/意义]以启发式-系统式模型为基础,将时空限制与任务复杂度分别作为启发式与系统式线索构建理论模型,探究影响搜索结果的关键因素,并对比不同搜索设备的影响差异。[研究设计/方法]设计2(时空限制:强/弱)×2(任务复杂度:高/低)×2(搜索设备:只能用手机/手机和PC都可使用)的多因素实验,构造8个不同的搜索情境,将使用过手机搜索和PC搜索的200名在校大学生作为被试对象,探索不同搜索情境下启发式和系统式线索对搜索结果行为与结果的影响。[结论/发现]根据搜索用时长短将搜索行为划分为启发式和系统式搜索行为:对于启发式搜索行为,搜索结果匹配度仅受搜索时空限制影响;对于系统式搜索行为,搜索结果匹配度则同时受搜索时空限制和任务复杂度影响。此外,使用不同的搜索设备(只有手机可用、手机与PC都可用)时,时空限制和任务复杂度对搜索结果匹配度的影响存在差异。[创新/价值]揭示了启发式与系统式搜索行为模式以及两种行为的重要影响因素,有助于改进搜索产品与服务。

结合硬斑块特征的心血管内超声图像中-外膜边缘检测

针对心血管内超声(IVUS)图像中-外膜(media-adventitia)边缘检测中,硬斑块和声影等造成中-外膜边缘难以准确检测的问题,提出一种结合硬斑块特征的中-外膜边缘检测方法。首先,采用k均值聚类分割IVUS图像,根据图像中不同类型斑块的成像特点检测硬斑块位置;然后,计算IVUS图像方向梯度,结合斑块位置和图像灰度,获得代价矩阵;最后,利用启发式图搜索方法,实现IVUS图像的中-外膜边缘检测。对临床图像的实验结果表明,本方法能克服图像中声影和斑块干扰等问题,使检测正确率达到95.57%,提高了IVUS图像中-外膜边缘检测的准确性。

文化基因算法求解多工艺路线炼钢-连铸生产调度问题

针对包含多工艺路线的炼钢-连铸生产调度问题,综合考虑生产过程中的多种约束条件,以文化基因算法为基础提出一种新的求解方法。在文化基因算法设计过程中,对于不同工艺路径的机器选择,采用启发式规则指导的机器指派方法;在算法优化中,通过引入基于连接矩阵的相似工件块交叉方法和基于基因位全插入的邻域搜索算子,从全局和局部搜索角度全面提高算法性能。最后,通过对多组算例进行对比分析,验证了本文算法的可行性和优越性。

面向订单的炼钢-连铸计划优化模型与算法研究

编制高效的炼钢-连铸计划是现代钢铁企业提高生产率和降低成本的有效手段。以转炉、精炼和板坯连铸生产工艺为研究对象,建立了面向订单的炼钢-连铸计划优化数学模型,并设计了二阶段启发式方法对模型进行了求解。

一种改进的威胁空间搜索算法

研究了五子棋游戏开发中极大极小搜索框架计算量太大,无用计算太多等问题.在传统经典极大极小搜索和alpha-beta剪枝基础上采用了判重,加入启发式的优化,每次选择最有"前途"的若干个决策搜索以减少搜索量,再加入基于五子棋专业棋手下棋策略,改进威胁空间搜索算法.使得计算机的搜索过程更像人的思考过程,算法复杂度大幅降低.经过测试最终编写的程序具备高响应度和智能性.