基于MAC的动态回溯算法优化

针对基于MAC的动态回溯算法在求解约束满足问题时, 不仅需要大量空间存储删除解释, 而且回溯机制过于复杂, 对经典的删除解释及动态回溯算法的回溯机制进行优化, 优化后的动态回溯算法减少了存储删除解释的空间, 并可仅使用一次回溯操作返回到可能导致冲突的关键变量. 在最差情况下, 存储删除解释的空间复杂度由O(n²d)改进为O(nd+n²). 通过结合restart技术使优化后的动态回溯算法成为完备算法. 实验结果表明, 优化后的完备动态回溯算法在大部分问题求解中, 整体效率明显优于标准回溯算法.     

求解随机型双边装配线平衡问题的混合回溯搜索优化算法

针对现实生产中普遍存在的操作时间为随机的双边装配线平衡问题,提出一种混合回溯搜索优化算法。该算法将变邻域搜索算法的局部搜索能力融入到回溯搜索优化算法的全局搜索中,从而实现广度搜索和深度搜索的平衡。运用基于随机键的编码将用于求解连续问题的回溯搜索优化算法应用于离散组合优化问题,同时提出一种基于均衡双边负载的边选择策略和减少工位空闲时间的任务选择策略的解码方法,并将该方法同另外4种解码方法进行对比,以验证其优越性。标杆算例测试表明,所提出的算法具有可行性和有效性。     

利用回溯搜索优化算法(BSA)测量圆度误差

由于圆度误差的评定方法结构复杂且求解精度比较低,因此提出了利用回溯搜索优化算法(BSA)来解决圆度误差问题.首先,简要介绍了圆度误差的评定方法以及数学模型,进而确定了圆度误差的目标函数;并对BSA的基本原理进行了详细地分析,在此基础上,给出了基于BSA评定圆度误差的方法和具体步骤;最后,通过仿真实验来检测回溯搜索优化算法的准确性,仿真实验结果显示,通过回溯搜索优化算法可以正确、快速地测量圆度误差.     

基于CSP方法的经济学实验分组问题的设计与实现

在基于oTree框架的经济学实验中,为解决相同几个参与者被分在同一组的情况重复出现的问题,按照约束满足类型问题(CSP)的分析方法对分组问题进行拆解分析,然后通过回溯算法实现分组,同时利用最少剩余值(MRV)方法对回溯算法进行优化.使用Python语言编写程序进行实验,实验结果验证了所提算法的有效性.     

一种混合蚁群算法在JSP问题中的应用研究

作业车间调度问题（JSP）是最困难的组合优化问题之一,也是目前管理科学领域的热点研究问题。针对JSP问题,利用回溯相邻交换方法对传统的蚁群优化算法进行改进,同时对蚁群优化算法中的全局信息素更新规则进行调整,求解生产周期最小的排程方案。最后通过仿真实验,验证了该算法的有效性。     

基于基因表达式编程的终端区飞机优化排序模型设计

终端区飞机排序是空中交通流量管制部门关注的热点问题,通过研究基因表达式编程在终端区飞机排序中的应用,设计了可回溯基因表达式编程的优化排序算法。该算法在染色体进化时使用改进的操作算子——最大区间约束倒置操作符,解决进化中出现的无效解和无用解问题;在种群繁衍时采用了回溯进化技术,为较优种群更好地保存,对回溯栈的操作改进为不...     

九位不同数字乘法等式的递归与非递归回溯算法

对"九位不同数字构成乘法等式"的问题进行分析,设计了递归回溯算法和非递归回溯算法,给出NP问题穷举算法设计的一般思路,同时比较两种算法的特点,并进行实验测试.     

多LNG点供企业联合配送的半开放式车辆路径问题

为解决多家LNG点供企业联合配送的路径优化问题,构建带时间窗的半开放式多中心车辆路径模型.考虑到LNG具有危险化学品特性,限制了 LNG槽车的通行路段,为求解该问题,设计改进的回溯搜索优化算法,提出客户信息与配送中心信息相对独立的新型编码方式,有效解决了车辆容量限制可能会导致传统自然数编码长度不一致,进而影响种群交叉、变异的问题.最后,利用Cplex和改进回溯搜索优化算法求解算例,结果验证了数学模型的正确性及算法的有效性,证明该联合配送模式可以有效降低运输成本及LNG槽车的运输风险.     

基于回溯法油管传输射孔排炮算法研究

根据油管传输射孔特点,为减少射孔枪串接时在射孔井段产生的接头总长度,对如何得到油管传输射孔最优射孔枪串接方案进行了理论分析。采用多叉树对问题进行了数学建模,为减少对多叉树的遍历次数,减少计算机运算时间,采用回溯法搜索最优解,并在回溯法的基础上对算法进行了优化。测试结果表明,油层数据简单时,回溯法与遍历法频率相当;而当油层数据复杂时,回溯法频率变高,最后设计实现了基于回溯法的排炮软件。     

基于启发式搜索算法的无人机航迹快速规划

基于无人机导航系统的自身特点,无人机在导航过程中会出现无法精确定位的情况,从而产生定位误差。如果不能及时校正随时间累积的定位误差,会使无人机无法到达预定目的地,从而导致飞行任务失败。为避免这种情况的发生,本文研究了考虑定位误差的无人机航迹快速规划问题。以航迹距离最短为目标,考虑定位误差校正约束与航迹约束,建立了混合整数规划模型。根据深度优先搜索算法与回溯算法的特点,设计了启发式深度优先搜索+回溯算法来求解问题,并在此算法基础上加入模拟退火机制对解的质量进行优化。以某飞行区域的数据为例进行仿真实验,结果表明启发式深度优先搜索+回溯算法可以快速有效地求解考虑定位误差的无人机航迹规划问题。     

自由边界问题的自适应预测-校正算法

对一类自由边界问题,提出了基于线性互补问题的自适应预测-校正算法.用有限差分对微分模型离散化后得到一个正定线性互补问题,该问题等价于一个不动点问题,从而得到求解线性互补问题的自适应预测-校正算法.用正定性及投影基本性质可证明算法收敛性.给出了具体的算法过程,数值结果表明了算法的可行性和有效性.     

渗流问题反分析的最优化方法

采用量优化方法中的逐个修正法,将反问题化为一系列的正问题进行求解;利用正问题的解是适定的这一性质,克服了反问题是不适定的问题;编制了渗流正问题的有限元程序和求解反问题的叠代格式;数值计算结果表明,此种方法有较快的收敛速度和非常强的稳定性。     

一类带约束运输问题的数学模型及其研究

提出了一类带约束运输问题的数学规划模型.证明了如果该类运输问题有可行解,那么它一定有最优解,且存在一个最优解,该最优解对应无约束运输问题的一个基础可行解.     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

基于独立性参数的无导师图象变形校正

从描述一幅图象变形程度的独立性参数入手，将图象变形校正问题转化为优化问题，并用单纯搜寻法进行优化参数搜寻。这种方法的优点在于其无需导师和对各种变形校正的通用性。文中给出了对线性变形和双线性变形校正的结果。     

一类多维卷积型积分方程的求解

对于热扩散问题和波场传播问题常常归结为二维或三维卷积型积分方程的求解．文献［1］解决了该类问题的一维求解，本文在二维情形下解决了指数衰减卷积型积分方程的求解，得到了求解的迭代格式，具有直接的应用价值．     

隐性目标决策问题的IDSS结构模型研究

研究一类复杂的隐性目标决策问题,它具有“决策目标难以完全数量化、结构化表示”、“决策者的偏好随决策分析进行而改变”、“决策问题常常具有NP难性质”等特征,并对问题的求解方法进行了讨论。基于交互式进化计算,建立处理该类决策问题的IDSS结构模型,讨论了各个模块的处理功能;最后以产品创新设计系统验证所提出模型的合理性。     

基于进化规划算法的背包问题求解研究

背包问题是一个具有较强应用价值的NP完全问题.如何设计求解此类问题的算法,则具有很强的实用价值和理论意义.目前已有很多的求解方法,但背包问题并没有完全解决.本文在启发式算法的理论基础上,改进了进化规划算法求解背包问题,此方法简单通用、易于操作.数值实验表明该方法具有较高的准确率,能较快的收敛到全局最优点.     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题，给出了求解柔性流水作业排序问题近似解的贪心算法，并对其性能进行了分析测试。结果表明，虽然该贪心算法求出的近似解与最优解相比有一定误差，但由于其时间复杂度较小，因此对求解车间作业调度问题仍有一定的现实意义。     

一类非线性问题迭代算法的求解

用一种简单可行的迭代方法求解一类有限维非线性问题.该方法是求解线性问题的高斯赛德尔迭代方法在非线性问题上的推广，且此迭代方法具有几何收敛性质.