面向柔性作业车间调度问题的改进变邻域搜索算法

针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计3种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解的搜索过程中解的可行性以提高求解效率。针对一系列典型的柔性作业车间调度问题的实例,运用所设计的改进变邻域搜索算法进行测试求解,并将计算结果与文献中其他算法的测试结果进行比较,验证了所提出方法求解柔性作业车间调度问题的可行性和有效性。     

考虑容量约束的电缆敷设变邻域搜索优化算法

针对一类考虑容量约束的电缆敷设优化问题,提出一种新的变邻域搜索优化算法。首先,分析电缆敷设问题的优化要求,基于图论给出具有容量约束的电缆敷设优化问题的数学描述;然后,结合问题特征提出基于Dijkstra算法的初始解生成策略,构建依据解间距离的邻域结构和局部启发式搜索策略,在此基础上给出电缆敷设变邻域搜索优化算法;最后通过实例求解结果表明,该算法能在短时间内获得问题的最优解或近优解,验证了算法的有效性和优越性。     

混合流水车间调度的变邻域禁忌搜索算法

针对混合流水车间系统的最小化Makespan调度问题,提出一种基于关键路径理论的变邻域禁忌搜索算法,讨论其关键技术。在该算法中,提出基于关键路径的毗邻域概念,防止搜索算法陷入局部最优解,采用变邻域搜索策略,在无法改进解时,实现对移动毗邻域的搜索。仿真结果表明,该算法获得的调度结果优于简化禁忌搜索和启发式算法。     

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。     

求解护士排班问题的变邻域搜索算法

变邻域搜索算法是求解护士排班问题的一个有效算法,其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度,提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构,而且当使用任意的邻域都不能进一步改进当前解时,设计了一个对当前最优解进行扰动的方法,即在排班期间内随机地选择两天,在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较,在Sprint-early、Medium-early和Long-early组算例上的结果表明,IVNS算法的最优值至少不劣于HVNS,而平均值均优于HVNS;IVNS算法的最大方差为0.72,波动范围小,求解性能稳定。IVNS的扰动方案对现有方案的扰动较小,能有效跳出当前局部最优,增强变邻域搜索算法的优化能力,与HVNS算法相比,其求解性能更优。     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

基于变邻域蚁群算法的自动光学检测路径规划

在确定取像窗口最少数量及其约束移动范围的前提下,为解决蚁群算法用于自动光学检测路径规划存在的问题,提出一种基于变邻域蚁群算法的自动光学检测路径规划方法。针对蚁群算法收敛速度慢、易陷入局部最优解的问题,提出含有3种邻域结构的变邻域路径搜索方法,改进蚁群算法以快速获得质量优异的可优化路径;针对取像窗口位置可调整的问题,提出变邻域窗口位置调整方法,进一步改善可优化路径,获得最短路径。实验结果表明,该算法比基本的蚁群算法具有更高的求解效率和求解质量,有效提升了自动光学检测系统的在线检测效率。     

基于混沌序列的粒子群优化算法

提出一种改进粒子群局部搜索能力的优化算法,对于陷入局部极小点的情性粒子,引入混沌序列重新初始化,在迭代中产生局部最优解的邻域点,帮助情性粒子逃商束缚并快速搜寻到最优解．对经典函数的测试计算表明。改进的混合算法通过微粒自适应更新机制确保了全局搜索性能和局部搜索性能的动态平衡,而且保持了PSO计算简洁的特点,在收敛速度和精度上均优于普通的PSO算法.     

一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。     

基于分段混合蛙跳算法的旅行商问题求解

针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题,提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径,在搜索的后期引入邻域搜索(个体邻域,局部最优领域,全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解,进行全局更新和局部更新,避免迂回搜索。在局部更新中,每一个青蛙都有机会得到更新。实验结果表明,与遗传算法、蚁群算法、基本蛙跳算法相比,S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。     

改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。     

一种SAT邻域的快速搜索算法

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。     

A restart local search algorithm for solving maximum set k-covering problem

The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances.

     

混合粒子群算法求解带软时间窗的VRPSPD问题

针对带软时间窗的同时集配货车辆路径问题（VRPSPD）,建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型;设计混合粒子群算法进行求解,该算法结合以变邻域下降搜索为主体的适应性扰动机制,采用适应性选择邻域策略,并在每个邻域搜索中应用可变的循环次数,以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。     

A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling

This paper presents an effective heuristic algorithm based on the framework of the filter-and-fan (F&F) procedure for solving the resource-constrained project scheduling problem (RCPSP). The proposed solution methodology, called the filter-and-fan approach with adaptive neighborhood switching (FFANS), operates on four different neighborhood structures and incorporates improved local search, F&F search with multiple neighborhoods and an adaptive neighborhood switching procedure. The improved local search, in which a new insert-based move strategy and new time compression measurement of schedules having the same makespan are embedded, is utilized to identify a local optimum and a basic move list. The F&F search, aimed to further improve the local optimum, applies multi-neighborhood filter and fan strategies to generate compound moves and a neighborhood-switch list in a tree search fashion. When the current neighborhood cannot further improve the local optimum, the adaptive neighborhood switching procedure picks the most potential neighborhood for the next run of the local search procedure. The entire solution procedure is autonomous and adaptive due to its variable search range depending on the project sizes and characteristics. Computational results and comparisons with some state-of-the-art algorithms indicate the effectiveness and competence of the proposed FFANS.     

Local search of orthogonal packings using the lower bounds

Consideration was given to the problem of packing the rectangular half-infinite strip. It was suggested to solve it using a one-point evolutionary algorithm with search of the best solution in the neighborhood of the local lower bound. Proposed was an algorithm to construct this neighborhood including the packings obtained by solving a special problem of one-dimensional cutting. Its solution was shown to be the local lower bound in the considered neighborhood. An improved global lower bound was proposed. The results of numerical modeling were presented. The record value obtained was compared with the global bounds.     

JayaX: Jaya algorithm with xor operator for binary optimization

Jaya is a population-based heuristic optimization algorithm proposed for solving constrained and unconstrained optimization problems. The peculiar distinct feature of Jaya from the other population-based algorithms is that it updates the positions of artificial agent in the population by considering the best and worst individuals. This is an important property for the algorithm to balance exploration and exploitation on the solution space. However, the basic Jaya cannot be applied to binary optimization problems because the solution space is discretely structured for this type of optimization problems and the decision variables of the binary optimization problems can be element of set [0,1]. In this study, we first focus on discretization of Jaya by using a logic operator, exclusive or – xor. The proposed idea is simple but effective because the solution update rule of Jaya is replaced with the xor operator, and when the obtained results are compared with the state-of-art algorithms, it is seen that the Jaya-based binary optimization algorithm, JayaX for short, produces better quality results for the binary optimization problems dealt with the study. The benchmark problems in this study are uncapacitated facility location problems and CEC2015 numeric functions, and the performance of the algorithms is compared on these problems. In order to improve the performance of the proposed algorithm, a local search module is also integrated with the JayaX. The obtained results show that the proposed algorithm is better than the compared algorithms in terms of solution quality and robustness.     

一种结合局部搜索策略的求解TSP的演化算法

介绍了一种结合局部搜索策略的求解流动旅行商问题（TSP）的演化算法。该算法的主要思想是将局部搜索策略在邻域内搜索的快速性与演化方法在全局搜索上的鲁棒性结合起来，从而跳离局部最优。将该算法用于TSPLIB中部分TSP实例上的试验结果表明：与传统的各种求解TSP的演化方法相比，该算法在获得全局最优解的精确度上有了一定的改善。     

求解IPPS顺序柔性调度问题的模型与集成型调度算法研究

针对工艺规划与调度集成(integrated process planning and scheduling, IPPS)问题中的顺序柔性调度问题,提出了基于简单顺序关系的顺序柔性描述模型及调度模型,并改进遗传算法设计了集成型的顺序柔性调度算法。染色体编码同时采用简单顺序关系编码和基于工序的编码,并为两种编码分别设计了多种交叉和变异操作。为避免遗传算子产生违背工序顺序优先关系的不可行解,提出了顺序约束修正策略;针对遗传算法易过早收敛的缺陷,设计了自适应调节变量以强化种群多样性,并引入变邻域搜索算法改变解的搜索邻域,进一步搜索最优调度方案。三种不同规模的实验仿真验证了问题描述模型及调度算法的有效性。