嵌套分割算法：一种新的并行随机优化算法*

嵌套分割算法是一种新的系统优化计算方法,它可以应用于确定型和随机型、离散系统和连续系统的优化问题.综述了嵌套分割算法的概念原理、方法步骤,介绍了算法的应用情况,并探讨了算法未来的研究方向.     

改进的嵌套分区算法求解旅行商问题

嵌套分区算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分区算法（NPM）的基本思想,将其应用于求解旅行商问题。分析确定了嵌套分区算法各个算子的策略,提出了一种改进的嵌套分区算法。该算法采用加权抽样法求得初始最可能域,用全局数组记录下每个区域的历史最优解,用3-opt局部搜索算法改进每个区域解的质量。对TSPLIB中部分实例仿真结果表明,所提出的结合3-opt算法的改进嵌套分区算法在求解 TSP问题时可以获得高质量的解。     

Tree based searching approaches for integrated vehicle dispatching and container allocation in a transshipment hub

This study addresses the integration of Vehicle dispatching and container storage location problem with consideration of loading and unloading activities simultaneously. A MIP model is formulated to describe the interrelation between vehicle scheduling, yard crane scheduling and container storage location. A tree structure is used to represent the whole solution space. This representation has a good property as it captures the neighborhood structure and enhances the performance of local search and adaptive searching algorithms. Three variants of tree based searching approaches are developed, namely, the Nested Partitions method (NP), the Beam Search method (BS), and Stochastic Beam Search method (SBS). Extensive experiments show that these proposed methods can find a promising solution in matter of seconds for a practical problem and the Stochastic Beam Search method (SBS) method performs nearly as well as Nested Partitions method (NP) while gaining great computational efficiency. Due to this merit, SBS method is suggested to solve real time integrated vehicle dispatching problem in a relative large scale and may applied in other real time complex system scheduling.     

求解作业车间调度问题的微粒群遗传退火算法

标准微粒群算法（PSO）通常被用于求解连续优化的问题,很少被用于离散问题的优化求解,如作业车间调度问题（JSP）。因此,针对PSO算法易早熟、收敛慢等缺点提出一种求解作业车间调度问题（JSP）的混合微粒群算法。算法将微粒群算法、遗传算法（GA）、模拟退火（SA）算法相结合,既增强了算法的局部搜索能力,降低了算法对参数的依赖,同时改善了PSO算法和GA算法易早熟的缺点。对经典JSP问题的仿真实验表明：与标准微粒群算法相比,该算法不仅能有效避免算法中的早熟问题,并且算法的全局收敛性得到了显著提高。     

面向产品优化配置的粒子群优化算法

针对产品配置大规模、多约束、多目标及组合优化等特性,建立一种有效的配置模型,将复杂的产品优化配置问题转化为图的路径寻优问题。针对基本粒子群算法(PSO)的缺陷,将遗传原理、蚁群机制和模拟退火理论引入PSO算法,提出一种改进的PSO算法。根据产品优化配置问题的离散特点,对PSO算法进行离散化处理,重新定义粒子的位置和速度表示,确立这些量的运算规律和粒子运动方程。典型产品配置实例验证了提出的模型和算法的可行性。     

A hybrid Improved Quantum-behaved Particle Swarm Optimization–Simplex method (IQPSOS) to solve power system load flow problems

This study proposes a new approach, based on a hybrid algorithm combining of Improved Quantum-behaved Particle Swarm Optimization (IQPSO) and simplex algorithms. The Quantum-behaved Particle Swarm Optimization (QPSO) algorithm is the main optimizer of algorithm, which can give a good direction to the optimal global region and Nelder Mead Simplex method (NM) which is used as a local search to fine tune the obtained solution from QPSO. The proposed improved hybrid QPSO algorithm is tested on several benchmark functions and performed better than particle swarm optimization (PSO), QPSO and weighted QPSO (WQPSO). To assess the effectiveness and feasibility of the proposed method on real problems, it is used for solving the power system load flow problems and demonstrated by different standard and ill-conditioned test systems including IEEE 14, 30 and 57 buses test systems, and compared with the conventional Newton–Raphson (NR) method, PSO and some versions of QPSO algorithms. Furthermore, the proposed hybrid algorithm is proposed for solving load flow problems with considering the reactive limits at generation buses. Simulation results prove the robustness and better convergence of IQPSOS under normal and critical conditions, when conventional load flow methods fail.     

一种新的混合优化算法及其在车间调度中的应用

提出了一种解决车间调度问题的新方法, 该方法将序优化思想融入巢分区算法框架, 采用"序比较"的方法进行算法的局部寻优. "序"的指数收敛性加快了巢分区算法的局部收敛速度, 从而提高了算法整体的优化效率. 最优计算量分配技术则依据在线数据对计算量进行合理的分配, 进一步提高算法的收敛速度和结果的可靠性. 混合算法继承了巢分区算法的全局搜索特性以及序优化的快速收敛性. 用该算法解决标准 Jobshop 调度问题, 并与序优化方法和模拟退火算法进行比较, 发现本文算法在收敛速度与优化质量方面均优于这些算法.     

嵌入极值优化的混合粒子群优化算法

针对标准粒子群算法容易陷入局部极值和精度低的问题,提出一种嵌入极值优化算法的粒子群优化算法。在线性下降的惯性权重粒子群算法运行过程中,间隔一定迭代次数与极值优化算法相结合,利用其波动性增加种群的多样性,并有效结合粒子群算法较强的全局探索能力和极值优化算法精细的局部搜索性能,以较高精度收敛到全局极值。仿真实验结果表明,该混合算法是一种求解高维多峰连续函数极值的有效方法。     

求解独立任务调度的离散粒子群优化算法

针对独立任务调度问题,提出一种改进的离散粒子群算法,采用基于任务的编码方式,对粒子的位置和速度更新方法进行重新定义。为防止粒子群算法的早熟收敛,给出利用模拟退火算法的局部搜索能力在最优解附近进行精细搜索,以改善解的质量。仿真结果表明,与遗传算法和基本粒子群算法相比,该混合算法具有较好的优化性能。     

模糊离散粒子群优化算法求解旅行商问题

粒子群优化算法已经成功地应用于求解连续域问题，但是对于离散域问题特别是路由问题的求解研究还很少．本文提出了一种改进的粒子群优化算法，用于求解旅行商问题．采用模糊矩阵来表示粒子的位置和速度，并重新定义其更新公式，最后对TSPLIB中的具体算例进行测试，实验结果表明该算法能够得到较好的结果．     

基于PSO信息传递模式的混合算法

粒子群优化算法（Particle Swarm Optimization,PSO）是一种基于群智能（Swarm Intelligence）的随机优化计算技术。PSO和遗传算法这两种算法相比较,PSO收敛快速准确,但编码形式单一,局限于解决实优化问题,而遗传算法编码形式灵活,解决问题广泛,但执行效率低于PS00。将粒子群算法的信息传递模式与遗传算法的编码和遗传操作相结合,提出一种混合算法。并推导了两个算法之间的密切联系。并通过组合优化和函数优化的基准测试集对算法进行测试,试验结果表明,该算法在收敛精度和速度优于传统遗传算法。同时,也观察到该算法取得了与粒子群算法一致的收敛现象。     

随机装卸工问题的新型混合粒子群算法

提出随机装卸工问题并将其转化为确定性问题,给出了其求解策略。针对粒子群算法简便实用但易过早收敛的问题,提出了一种结合人工免疫算法的新型混合粒子群算法,将该算法运用于求解随机装卸工问题。数值算例的计算结果表明：与基本粒子群算法相比,改进的粒子群算法在求解随机装卸工问题上表现出的求解精度和速度都十分理想。     

基于粒子群与模拟退火算法的板材优化下料

提出一种用于处理板材下料问题的粒子群与模拟退火混合算法。同时,在把下料模式转化为实际设计时,提出了一种类似于Bottom Left（BL）算法的转换方法。模拟实验结果表明这种混合方法的性能明显优于粒子群算法。     

改进的细菌觅食优化算法求解0-1背包问题

细菌觅食优化算法作为一种新兴的智能优化算法,一般用来解决连续域的问题。为了解决离散域问题,提出了一种改进的细菌觅食优化算法。采用线性递减的思想和随机的游动长度代替固定步长和随机游动方向,改进了趋向性操作方案,并将其应用于解决0-1背包问题。将改进的细菌觅食优化算法与遗传算法、离散粒子群优化算法及基本的离散化细菌觅食优化算法分别在小规模和大规模的0-1背包问题上进行了仿真比较,表明了改进的细菌觅食优化算法能取得较好的效果,寻优能力强。     

Nested partitions for global optimization in nonlinear model predictive control

In Nonlinear Model Predictive Control (NMPC), the optimization problem may be nonconvex. It is important to find a global solution since a local solution may not be able to operate the process at desired setpoints. Also the solution must be available before the control input has to be applied to the process. In this paper, a stochastic algorithm called the Nested Partitions Algorithm (NPA) is used for global optimization. The NPA divides the search space into smaller regions and either concentrates search in one of these regions called the most promising region or backtracks to a larger region in the search space based on a performance index. To adapt the NPA to solve dynamic NMPC with continuous variables, a new partitioning scheme is developed that focuses on the first few control moves in the control horizon. The expected number of iterations taken by the NPA is presented. Convergence speed is improved by reducing the size of the starting most promising region based on a good starting point. The discrete sampling nature of the NPA may cause difficulty in finding the global solution in a continuous space. A gradient-based search is used with the NPA to overcome this difficulty. The solution quality is assessed in terms of the error from the actual global minimum. The algorithm is shown to give a feasible solution that provides asymptotic stability. Case studies are used to show the algorithm performance in terms of tracking setpoints, cost, solution quality and convergence time.     

基于混合粒子群算法的列车停站方案优化

列车停站方案影响着旅客服务质量和运行效率,是列车开行方案的重要环节.本文建立了旅客列车停站方案的多目标规划模型以最大化区段可达性从而减少旅客旅行时间.针对传统的粒子群优化算法在处理复杂多维问题时,算法效率不高,易陷进局部最优,且无法有效处理离散问题等缺点,提出了一种将量子遗传算法引入到MPSO中的方法.算法整体采用粒子群算法,结合量子遗传算法的概率幅编码,并使用粒子群的速度更新公式来更新量子旋转门.算法引入量子遗传算法的全局探索和粒子群算法的种群智能体系,不仅提高了算法的收敛速度,同时增加了粒子多样性.最后,将改进的量子遗传粒子群算法（QGA_PSO）应用于ZDT函数优化和停站方案模型优化,证明了算法的有效性.     

Disassembly sequence planning using a Simplified Teaching–Learning-Based Optimization algorithm

Disassembly Sequence Planning (DSP) is a challenging NP-hard combinatorial optimization problem. As a new and promising population-based evolutional algorithm, the Teaching–Learning-Based Optimization (TLBO) algorithm has been successfully applied to various research problems. However, TLBO is not capable or effective in DSP optimization problems with discrete solution spaces and complex disassembly precedence constraints. This paper presents a Simplified Teaching–Learning-Based Optimization (STLBO) algorithm for solving DSP problems effectively. The STLBO algorithm inherits the main idea of the teaching–learning-based evolutionary mechanism from the TLBO algorithm, while the realization method for the evolutionary mechanism and the adaptation methods for the algorithm parameters are different. Three new operators are developed and incorporated in the STLBO algorithm to ensure its applicability to DSP problems with complex disassembly precedence constraints: i.e., a Feasible Solution Generator (FSG) used to generate a feasible disassembly sequence, a Teaching Phase Operator (TPO) and a Learning Phase Operator (LPO) used to learn and evolve the solutions towards better ones by applying the method of precedence preservation crossover operation. Numerical experiments with case studies on waste product disassembly planning have been carried out to demonstrate the effectiveness of the designed operators and the results exhibited that the developed algorithm performs better than other relevant algorithms under a set of public benchmarks.     

A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

The Glowworm Swarm Optimization (GSO) algorithm is a relatively new swarm intelligence algorithm that simulates the movement of the glowworms in a swarm based on the distance between them and on a luminescent quantity called luciferin. This algorithm has been proven very efficient in the problems that has been applied. However, there is no application of this algorithm, at least to our knowledge, in routing type problems. In this paper, this nature inspired algorithm is used in a hybrid scheme (denoted as Combinatorial Neighborhood Topology Glowworm Swarm Optimization (CNTGSO)) with other metaheuristic algorithms (Variable Neighborhood Search (VNS) algorithm and Path Relinking (PR) algorithm) for successfully solving the Vehicle Routing Problem with Stochastic Demands. The major challenge is to prove that the proposed algorithm could efficiently be applied in a difficult combinatorial optimization problem as most of the applications of the GSO algorithm concern solutions of continuous optimization problems. Thus, two different solution vectors are used, the one in the continuous space (which is updated as in the classic GSO algorithm) and the other in the discrete space and it represents the path representation of the route and is updated using Combinatorial Neighborhood Topology technique. A migration (restart) phase is, also, applied in order to replace not promising solutions and to exchange information between solutions that are in different places in the solution space. Finally, a VNS strategy is used in order to improve each glowworm separately. The algorithm is tested in two problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Stochastic Demands in a number of sets of benchmark instances giving competitive and in some instances better results compared to other algorithms from the literature.     

Effect of hybridizing Biogeography-Based Optimization (BBO) technique with Artificial Immune Algorithm (AIA) and Ant Colony Optimization (ACO)

Hybridization in optimization methods plays a very vital role to make it effective and efficient. Different optimization methods have different search tendency and it is always required to experiment the effect of hybridizing different search tendency of the optimization algorithm with each other. This paper presents the effect of hybridizing Biogeography-Based Optimization (BBO) technique with Artificial Immune Algorithm (AIA) and Ant Colony Optimization (ACO) in two different ways. So, four different variants of hybrid BBO, viz. two variants of hybrid BBO with AIA and two with ACO, are developed and experimented in this paper. All the considered optimization techniques have altogether a different search tendency. The proposed hybrid method is tested on many benchmark problems and real life problems. Friedman test and Holm–Sidak test are performed to have the statistical validity of the results. Results show that proposed hybridization of BBO with ACO and AIA is effective over a wide range of problems. Moreover, the proposed hybridization is also effective over other proposed hybridization of BBO and different variants of BBO available in the literature.     

基于遗传算法的混合优化策略研究

最优化问题是工程设计、科学研究、经济管理等众多领域经常遇到的一类问题。随着待解决问题范围的不断扩大以及优化算法研究的不断深入,混合优化策略已成为解决大规模、高复杂度优化问题的一种重要而有效的方法。介绍了遗传算法、贪婪法、模拟退火算法、禁忌搜索的基本原理,阐述了各种算法的优缺点;针对各单一算法存在的缺陷和不足,对三种以遗传算法为主体框架的混合优化算法进行了分析;最后,指出了混合优化算法存在的问题及今后的发展方向。