具有广泛学习策略的回溯搜索优化算法

回溯搜索优化算法(backtracking search optimization algorithm, BSA)是一种新型的进化算法。同其他进化算法类似,该算法仍存在收敛速度较慢的缺点。针对这一问题,在详细分析该算法原理的基础上,提出了具有广泛学习策略的改进算法。为了充分利用种群搜索到的较优位置,该策略首先利用提出的最优学习进化方程,通过与引入的随机进化方程之间随机选择来提高算法的收敛速度和搜索精度;另一方面,该策略利用提出的最优学习搜索方程,通过控制种群的搜索方向,促使种群尽快收敛至全局最优解。最后对20个复杂测试函数进行了仿真实验,并与其他3种目前流行的算法进行了比较,统计结果和Wilcoxon符号秩检验结果均表明,所提出的改进算法在收敛速度以及搜索精度方面具有明显优势。     

SOLVING RESOURCE—CONSTRAINED PROJECT SCHEDULING PROBLEMS WITH BI—CRITERIA HEURISTIC SEARCH TECHNIQUES

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm forsolving multiple resource-constrained project scheduling problems. The heuristic solves problems intwo phases. In the pre-processing phase, the algorithm estimates distance between a state and the goalstate and measures complexity of problem instances. In the search phase, the algorithm uses estimatesof the pre-processing phase to further estimate distances to the goal state. The search continues in astepwise generation of a series of intermediate states through search path evaluation process withbacktracking. Developments of intermediate states are exclusively based on a bi-criteria new stateselection technique where we consider resource utilization and duration estimate to the goal state. Wealso propose a variable weighting technique based on initial problem complexity measures.Introducing this technique allows the algorithm to efficiently solve complex project schedulingproblems. A numerical example illustra     

雷达海杂波反演大气波导的改进回溯搜索算法

了克服基本回溯搜索算法在大气波导反演问题中出现的收敛速度慢、容易陷入局部最优的缺点,提出一种基于反向学习机制和正交交叉机制的改进回溯搜索优化算法。该算法利用反向学习机制来选择较好的初始化种群,而正交交叉机制用来帮助算法加强全局搜索能力,避免算法陷入局部最优,从而提高算法的精度。通过常见测试函数的优化问题以及大气波导的反演问题来检验算法的性能。结果表明,所提算法具有较高的精度和较快收敛速度。     

带部分回溯的过滤束搜索算法及其在Job Shop 问题中的应用

束搜索(Beam search)方法是在分枝定界方法基础上发展起来的一种启发式优化方法,由于这类方法在确定分枝搜索方向时仅考虑了当前的局部信息,因此易陷入局部极值.在过滤束搜索(filteredbeam search)方法的基础上提出了一种改进思路,即在局部评价和全局评价的基础上增加部分回溯.通过引入有效的部分回溯策略,部分被舍弃的结点被重新评估并最终找到更好的解,从而可避免过早陷入局部极值.通过对48个标准问题的计算和比较,结果显示改进后的方法能有效提高解的质量.     

利用深度优先搜索方法求解作业排序

作业排序通常是在一定的限制条件和优化目标的约束下，对有限的资源进行分配。采用搜索方法求解这类问题常会遇到冲突的状态结点，引起多次回溯。同时，由于问题状态空间庞大，搜索过程相当费时。本文通过研究作业排序问题状态空间的特点，引入冲突指派集的概念，提出了基于冲突指派集的深度优先搜索方法，缩小了搜索范围，提高了搜索效率。     

带硬时间窗的战场物资配送车辆路径优化

针对战场物资配送中带硬时间窗车辆路径问题的多重模糊性,基于模糊可信性理论建立了多目标模糊期望值模型,提出了一种改进的约束多目标粒子群优化算法。算法采用基于相位空间思想的实数编码方式,提出了带优秀不可行解动态记忆机制的非支配解构造方法,基于自适应栅格和拥挤距离的混合多样性策略维护非支配解集,改进了个体向导更新方式,提高了算法的收敛性能,同时引入局部搜索和变异算子避免算法早熟。仿真实验表明了模型的合理性和算法的有效性。     

带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究

对另一种类型的车辆路径问题——开放式车辆路径问题进行了研究 .提出了一种用于求解带装载能力约束的开放式车辆路径问题的禁忌搜索算法 .给出了算法对测试算例的运算结果 ,并与文献中目前最好的结果进行比较 .比较结果表明 ,在绝大多数情况下 ,该算法能求出更好的解 .     

A line search filter secant method for nonlinear equality constrained optimization

<正> This paper formulates and analyzes a line search method for general nonlinear equalityconstrained optimization based on filter methods for step acceptance and secant methods for searchdirection.The feature of the new algorithm is that the secant algorithm is used to produce a searchdirection,a backtracking line search procedure is used to generate step size,some filtered rules areused to determine step acceptance,second order correction technique is used to reduce infeasibility andovercome the Maratos effect.Global convergence properties of this method are analyzed:under mildassumptions it is showed that every limit point of the sequence of iterates generated by the algorithmis feasible,and that there exists at least one limit point that is a stationary point for the problem.Moreover,it is also established that the Maratos effect can be overcome in our new approach by addingsecond order correction steps so that fast local superlinear convergence to a second order sufficient localsolution is achieved.Finally,the results of numerical experiments are reported to show the effectivenessof the line search filter secant method.     

基于邻域搜索的成品油多舱多目标配送路径优化算法研究

针对成品油配送中多车型,多车舱的优化调度难题,综合考虑路径安排,舱位指派及车辆指派等决策.以配送成本最小,路径风险最小以及油品准时送达为目标,建立了成品油配送多目标路径优化模型.基于邻域搜索的基本思想,提出求解成品油配送多目标路径优化问题的MOVNS算法框架,并结合不同的可行解运行策略和比较准则,衍生出三类MOVNS算法(MOVNS-1、MOVNS-2、MOVNS-3).采用12组算例进行数值实验,结果表明,三种算法均能有效的求解配送模型,提升成品油多舱配送问题的解决效率;且MOVNS-2算法具有较强的局部搜索能力,MOVNS-3算法容易跳出局部最优:同时,考虑节点关联性的可行解构造策略和并行邻域搜索策略能够增强算法的寻优能力.     

面向应急需求的成像卫星单任务综合规划

针对应急条件下成像卫星任务规划问题,在分析任务响应过程的基础上建立了面向任务需求的应急条件下单任务综合规划模型,模型以完成任务需求最早为优化目标,综合考虑了任务规划过程中卫星、测控及数传资源的分配,并提出了基于深度优先搜索的模型求解算法。算例分析结果表明,所提出的模型及算法有效,规划结果能够就现有卫星、测控及数传资源条件下,为应急成像任务需求提供星地资源调度解决方案。     

面向任务的拼修策略问题及求解算法

研究了一种面向任务的拼修策略问题, 建立了该问题的多维背包问题模型,提出了基于遗传算法的求解方案.然后设计了一种求解效果较好的两阶段遗传算法, 进行了包括编码, 交叉,变异, 最优前沿限定算法, 适应度函数,选择策略和退火局部搜索算法在内的全面的分析和设计. 最后,给出了一个算例,检验了求解方案的实用性,并且通过计算实验分析了遗传算法的有效性.     

基于改进遗传算法的流水车间调度求解方法

流水车间调度问题是一类经典的NP完全问题,为此提出了一种求解极小化总完工时间的流水车间调度问题的改进遗传算法.该算法采用构造型启发式算法和随机方法共同产生初始种群,结合禁忌搜索算法的局部搜索性能和遗传算法的全局搜索性能.仿真实例的结果表明该算法对问题求解的可行性和有效性.     

An affine scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming

This paper proposes an arlene scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming. This method is designed to get a stationary point for such a problem with polynomial interpolation models instead of the objective function in trust region subproblem. Combined with both trust region strategy and line search technique, at each iteration, the affine scaling derivative-free trust region subproblem generates a backtracking direction in order to obtain a new accepted interior feasible step. Global convergence and fast local convergence properties are established under some reasonable conditions. Some numerical results are also given to show the effectiveness of the proposed algorithm.     

考虑行为主体的置换流水车间干扰管理研究

针对置换流水车间计划外新工件到达干扰问题,研究从加工系统参与主体:企业管理者、车间工人和客户三方进行基于前景理论的扰动度量,并建立同时考虑初始成本目标和基于行为运筹扰动目标的干扰管理模型.经分析发现问题复杂度为NP-难,为了弥补单一元启发式算法具有求解性能依赖于初始解的质量以及局部搜索不足等缺陷,从初始解改进和加强局部搜索两个角度,提出一种具有一般通用性的元启发式算法混合策略,分别基于量子计算、粒子群搜索和模拟退火设计了四种具体混合算法.为验证该混合策略的有效性,基于置换流水车间Taillard(Ta)标准测试集设计干扰算例并应用算法进行求解,验证了基于前景理论的扰动度量的优势,通过输出有效前沿多样性和收敛性分析证明了所提算法混合策略求解问题的有效性.     

递进多目标遗传算法

在现有算法研究基础上,提出了一种递进多目标遗传算法,该方法每进化一定代数后以一定策略对群体进行重构,以提高算法对解空间的遍历性,从而较大程度上避免算法的早熟.该算法采用非劣解等级优先的选择方式复制后代,降低算法的时间复杂性;通过递进层次间对部分非劣解个体执行局部搜索,加快全局非劣解集的进化.采用递进算法与现有两种典型多目标遗传算法NSGA、MOGLS算法对一些典型优化问题进行对比分析,验证了算法求解多目标函数优化问题的有效性;通过调整算法递进层次与每层进化代数的参数设置,进一步研究了参数选取对算法性能的影响.     

求解Job Shop调度问题的粒子群算法研究

为解决单一粒子群算法求解Job shop调度问题存在的不足,提出一种基于交换序的混合粒子群算法,提高了这类问题的求解质量.在混合粒子群算法中,采用粒子群算法进行大范围全局搜索.根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种方法的禁忌搜索算法作为局部搜索算法,增强了粒子群算法的搜索能力.采用混合粒子群算法对13个难解的benchmark问题进行求解,在较短的时间内,得到的最优解和10次求解的平均值优于并行遗传算法和粒子群算法.由此说明本文所提出的混合粒子群算法是有效的.     

Solving DCLAP-MSN based on hybrid genetic algorithm

The dynamic capacitated location allocation problem in the military supportive network (DCLAP-MSN) is a representative of combinative optimization problems, and its optimization process is complicated. For this reason, a dynamic capacitated location allocation model is provided firstly. Then, a hybrid heuristic algorithm which combines genetic algorithm, repair algorithm of solutions and greedy search, is proposed as the solving method.The optimization performance is improved by effectively integrating the repair algorithm of solutions and greedy search with genetic optimization. The experiment results indicate that the proposed algorithm is a feasible and effective method for the problem.     

带振荡策略的启发式算法求解一类新型分配问题

提出了一种新型的分配问题,该问题来源于钢铁企业中的板坯优化管理.与一般分配问题相比,该问题在将物品分配给背包时,除了需满足背包的容量限制外,还需满足流向限制.此问题可归结为 一般分配问题,因此为NP难问题.针对该问题,提出了带有振荡策略和长期表的启发式算法求解.振荡策略使局部搜索算法在可行区域和不可行区域间振荡,以获得更好的近优解;其次,在算法中引入了禁忌搜索的长期表,根据频率鼓励物品的多样性移动,提高算法的分散搜索能力.为验证算法有效性, 对随机产生的23种规模的数据进行了实验.实验结果表明：对于小规模数据,算法结果与最优解的最大偏差为0.55{\%};在大规模情况下,算法能在快速的时间内获得问题的近优解.     

基于免疫遗传算法的双向车辆调度问题实现

在对双向车辆路径问题(DVSP)简要叙述的基础上建立了DVSP数学模型.针对DVRP,构造一种的免疫遗传算法来求解DVSP,提出了一种自然数编码方法、交叉算子的自适应机制.并将求解结果与其它启发式算法比较.比较结果表明,该算法对于求解DVSP问题具有较好的性能和更好的鲁棒性.     

带时间窗车辆路径问题的量子蚁群算法

带时间窗的车辆路径问题(VRPTW)是VRP的一种重要扩展类型, 是组合优化中的一个NP难题, 针对蚁群算法在求解VRPTW问题时易陷入局部最优和收敛速度慢的问题, 本文结合量子计算提出一种求解VRPTW的量子蚁群算法(QACA). 通过定义人工蚂蚁的转移概率, 增加量子比特启发式因子, 以及用量子旋转门实现信息素更新, 从而提高算法的全局搜索能力, 有效避免了算法陷入局部最优. 经一系列VRPTW的仿真实验表明, 量子蚁群算法较蚁群算法在求解VRPTW问题上具有更好的性能, 通过与其他算法的比较, 进一步说明量子蚁群算法是可行有效的.