A hybrid particle swarm optimization approach for the sequential ordering problem

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost.     

A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems

In this paper, a modified particle swarm optimization (PSO) algorithm is developed for solving multimodal function optimization problems. The difference between the proposed method and the general PSO is to split up the original single population into several subpopulations according to the order of particles. The best particle within each subpopulation is recorded and then applied into the velocity updating formula to replace the original global best particle in the whole population. To update all particles in each subpopulation, the modified velocity formula is utilized. Based on the idea of multiple subpopulations, for the multimodal function optimization the several optima including the global and local solutions may probably be found by these best particles separately. To show the efficiency of the proposed method, two kinds of function optimizations are provided, including a single modal function optimization and a complex multimodal function optimization. Simulation results will demonstrate the convergence behavior of particles by the number of iterations, and the global and local system solutions are solved by these best particles of subpopulations.     

A hybrid particle swarm optimization for job shop scheduling problem

A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the particle position representation, particle movement, and particle velocity to better suit PSO for the JSP. We modified the particle position based on preference list-based representation, particle movement based on swap operator, and particle velocity based on the tabu list concept in our algorithm. Giffler and Thompson’s heuristic is used to decode a particle position into a schedule. Furthermore, we applied tabu search to improve the solution quality. The computational results show that the modified PSO performs better than the original design, and that the hybrid PSO is better than other traditional metaheuristics.     

A hybrid artificial bee colony for a nurse rostering problem

The nurse rostering problem (NRP) is a combinatorial optimization problem tackled by assigning a set of shifts to a set of nurses, each has specific skills and work contract, to a predefined rostering period according to a set constraints. The metaheuristics are the most successful methods for tackling this problem. This paper proposes a metaheuristic technique called a hybrid artificial bee colony (HABC) for NRP. In HABC, the process of the employed bee operator is replaced with the hill climbing optimizer (HCO) to empower its exploitation capability and the usage of HCO is controlled by hill climbing rate (HCR) parameter. The performance of the proposed HABC is evaluated using the standard dataset published in the first international nurse rostering competition 2010 (INRC2010). This dataset consists of 69 instances which reflect this problem in many real-world cases that are varied in size and complexity. The experimental results of studying the effect of HCO using different value of HCR show that the HCO has a great impact on the performance of HABC. In addition, a comparative evaluation of HABC is carried out against other eleven methods that worked on INRC2010 dataset. The comparative results show that the proposed algorithm achieved two new best results for two problem instances, 35 best published results out of 69 instances as achieved by other comparative methods, and comparable results in the remaining instances of INRC2010 dataset.     

Solving shortest path problem using particle swarm optimization

This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem.     

基于Lotka-Volterra 模型的双群协同竞争粒子群优化算法

针对粒子群优化算法易出现早熟收敛的问题,提出了基于Lotka-Volterra模型的双群协同竞争粒子群优化算法(LVPSO).LVPSO算法借鉴种群生态学中著名的Lotka-Volterra双群协同竞争模型,讨论了两种种群协同竞争方案,通过群内和群间竞争增加粒子的多样性,提高了种群摆脱局部极值的能力.对5个典型基准测试函数进行优化实验表明,LVPSO在收敛速度和优化精度方面均有良好的表现.     

随机权值平面选址的粒子群优化算法

将引入粒子群优化算法来解决带随机权值、服从独立均匀概率分布的极小化极大（1-中心）平面选址问题,对其进行实验模拟并得出了乐观的结果。     

A new particle swarm optimization for the open shop scheduling problem

This paper presents a new particle swarm optimization (PSO) for the open shop scheduling problem. Compared with the original PSO, we modified the particle position representation using priorities, and the particle movement using an insert operator. We also implemented a modified parameterized active schedule generation algorithm (mP-ASG) to decode a particle position into a schedule. In mP-ASG, we can reduce or increase the search area between non-delay schedules and active schedules by controlling the maximum delay time allowed. Furthermore, we hybridized our PSO with beam search. The computational results show that our PSO found many new best solutions of the unsolved problems.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

基于PSO的确定性问题优化研究

粒子群算法原理简单，易于实现，是进化算法中优化效率很高的算法。针对确定环境下的问题优化，提出采用粒子群算法对其进行优化求解。通过对确定性环境下的Benchmark函数的算法仿真研究，表明粒子群算法在确定性问题优化中具有快速收敛性和精确性的特点。     

Chaotic particle swarm optimization for assembly sequence planning

Assembly sequence planning of complex products is difficult to be tackled, because the size of the search space of assembly sequences is exponentially proportional to the number of parts or components of the products. Contrasted with the conventional methods, the intelligent optimization algorithms display their predominance in escaping from the vexatious trap. This paper proposes a chaotic particle swarm optimization (CPSO) approach to generate the optimal or near-optimal assembly sequences of products. Six kinds of assembly process constraints affecting the assembly cost are concerned and clarified at first. Then, the optimization model of assembly sequences is presented. The mapping rules between the optimization model and the traditional PSO model are given. The variable velocity in the traditional PSO algorithm is changed to the velocity operator (vo) which is used to rearrange the parts in the assembly sequences to generate the optimal or near-optimal assembly sequences. To improve the quality of the optimal assembly sequence and increase the convergence rate of the traditional PSO algorithm, the chaos method is proposed to provide the preferable assembly sequences of each particle in the current optimization time step. Then, the preferable assembly sequences are considered as the seeds to generate the optimal or near-optimal assembly sequences utilizing the traditional PSO algorithm. The proposed method is validated with an illustrative example and the results are compared with those obtained using the traditional PSO algorithm under the same assembly process constraints.     

解决约束优化问题的改进粒子群算法

针对约束优化问题的求解,提出一种改进的粒子群算法（CMPSO）。在CMPSO算法中,为了增加种群多样性,提升种群跳出局部最优解的能力,引入种群多样性阈值,当种群多样性低于给定阈值时,对全局最优粒子位置和粒子自身最优位置进行多项式变异;并根据粒子违背约束条件的程度,提出一种新的粒子间比较准则来比较粒子间的优劣,该准则可以保留一部分性能较优的不可行解;为提升种群向全局最优解飞行的概率,采取一种广义学习策略。对经典测试函数的仿真结果表明,所提出的算法是一种可行的约束优化问题的求解方法。     

解决零空闲流水线调度问题的离散粒子群算法

研究了以最大完工时间为目标的零空闲流水线调度问题.提出一种复杂度为O(nm)的最大完工时间算法和一种快速插入邻域搜索算法;提出了解决该问题的离散粒子群调度算法,并结合简化邻域搜索算法给出了提高调度算法性能的措施.仿真实验表明了所得算法的有效性.     

Multi swarm bare bones particle swarm optimization with distribution adaption

Bare bones PSO is a simple swarm optimization approach that uses a probability distribution like Gaussian distribution in the position update rules. However, due to its nature, Bare bones PSO is highly prone to premature convergence and stagnation. The characteristics of the probability distribution functions used in the update rule have a tense impact on the performance of the bare bones PSO. As a result, this paper investigates the use of different methods for estimating the probability distributions used in the update rule. Four methods or strategies are developed that are using Gaussian or multivariate Gaussian distributions. The choice of an appropriate updating strategy for each particle greatly depends on the characteristics of the fitness landscape that surrounds the swarm. To deal with issue, the cellular learning automata model is incorporated with the proposed bare bones PSO, which is able to adaptively learn suitable updating strategies for the particles. Through the interactions among its elements and the learning capabilities of its learning automata, cellular learning automata gradually learns to select the best updating rules for the particles based on their surrounding fitness landscape. This paper also, investigates a new and simple method for adaptively refining the covariance matrices of multivariate Gaussian distributions used in the proposed updating strategies. The proposed method is compared with some other well-known particle swarm approaches. The results indicate the superiority of the proposed approach in terms of the accuracy of the achieved results and the speed in finding appropriate solutions.     

A modified particle swarm optimization for aggregate production planning

Particle swarm optimization (PSO) originated from bird flocking models. It has become a popular research field with many successful applications. In this paper, we present a scheme of an aggregate production planning (APP) from a manufacturer of gardening equipment. It is formulated as an integer linear programming model and optimized by PSO. During the course of optimizing the problem, we discovered that PSO had limited ability and unsatisfactory performance, especially a large constrained integral APP problem with plenty of equality constraints. In order to enhance its performance and alleviate the deficiencies to the problem solving, a modified PSO (MPSO) is proposed, which introduces the idea of sub-particles, a particular coding principle, and a modified operation procedure of particles to the update rules to regulate the search processes for a particle swarm. In the computational study, some instances of the APP problems are experimented and analyzed to evaluate the performance of the MPSO with standard PSO (SPSO) and genetic algorithm (GA). The experimental results demonstrate that the MPSO variant provides particular qualities in the aspects of accuracy, reliability, and convergence speed than SPSO and GA.     

Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows

This study presents a new variant of the team orienteering problem with time windows (TOPTW), called the multi-modal team orienteering problem with time windows (MM-TOPTW). The problem is motivated by the development of a tourist trip design application when there are several transportation modes available for tourists to choose during their trip. We develop a mixed integer programming model for MM-TOPTW based on the standard TOPTW model with additional considerations of transportation mode choices, including transportation cost and transportation time. Because MM-TOPTW is NP-hard, we design a two-level particle swarm optimization with multiple social learning terms (2L-GLNPSO) to solve the problem. To demonstrate the applicability and effectiveness of the proposed model and algorithm, we employ the proposed 2L-GLNPSO to solve 56 MM-TOPTW instances that are generated based on VRPTW benchmark instances. The computational results demonstrate that the proposed 2L-GLNPSO can obtain optimal solutions to small and medium-scale instances. For large-scale instances, 2L-GLNPSO is capable of producing high-quality solutions. Moreover, we test the proposed algorithm on standard TOPTW benchmark instances and obtains competitive results with the state-of-art algorithms.     

Parameter optimization of sub-35 nm contact-hole fabrication using particle swarm optimization approach

The major research focus on integrated circuits (ICs) mainly deals with increasing circuit performance and functional complexity of circuit. The lithography process is the most critical step in the fabrication of nanostructure for integrated circuit manufacturing. The most important variable in the lithography process is the line-width or critical dimensions (CDs), which perhaps is one of the most direct impact variables on the device performance and speed. This study presents a hybrid approach combining Taguchi’s robust design, back-propagation neural network modeling technique and particle swarm optimization (PSO) for sub-35 nm contact-hole fabrication in the lithography process. The BP neural network is employed to model the functional relationship between the input parameters and target responses. Particle swarm optimization is adopted to optimize the parameter settings through the well-trained BP model, where each particle is assessed using fitness function. The proposed PSO algorithm applies the velocity updating and position updating formulas to the population composed of many particles such that better particles are generated. Compared with realistic fabricated and measured data, this approach can achieve the optimal parameter settings for minimized CDs or target CDs. Meanwhile, it reduces the CD variation through the design of experiment. The experimental results show that the proposed approach dealing with the process modeling and parameter optimization demonstrates its feasibility and effectiveness for sub-35 nm contact-hole fabrication.     

A perturbed particle swarm algorithm for numerical optimization

The canonical particle swarm optimization (PSO) has its own disadvantages, such as the high speed of convergence which often implies a rapid loss of diversity during the optimization process, which inevitably leads to undesirable premature convergence. In order to overcome the disadvantage of PSO, a perturbed particle swarm algorithm (pPSA) is presented based on the new particle updating strategy which is based upon the concept of perturbed global best to deal with the problem of premature convergence and diversity maintenance within the swarm. A linear model and a random model together with the initial max–min model are provided to understand and analyze the uncertainty of perturbed particle updating strategy. pPSA is validated using 12 standard test functions. The preliminary results indicate that pPSO performs much better than PSO both in quality of solutions and robustness and comparable with GCPSO. The experiments confirm us that the perturbed particle updating strategy is an encouraging strategy for stochastic heuristic algorithms and the max–min model is a promising model on the concept of possibility measure.     

A study of particle swarm optimization particle trajectories

Particle swarm optimization (PSO) has shown to be an efficient, robust and simple optimization algorithm. Most of the PSO studies are empirical, with only a few theoretical analyses that concentrate on understanding particle trajectories. These theoretical studies concentrate mainly on simplified PSO systems. This paper overviews current theoretical studies, and extend these studies to investigate particle trajectories for general swarms to include the influence of the inertia term. The paper also provides a formal proof that each particle converges to a stable point. An empirical analysis of multi-dimensional stochastic particles is also presented. Experimental results are provided to support the conclusions drawn from the theoretical findings.     

A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery

This paper proposes a formulation of the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and a particle swarm optimization (PSO) algorithm for solving it. The formulation is a generalization of three existing VRPSPD formulations. The main PSO algorithm is developed based on GLNPSO, a PSO algorithm with multiple social structures. A random key-based solution representation and decoding method is proposed for implementing PSO for VRPSPD. The solution representation for VRPSPD with n customers and m   vehicles is a (n+2m)$(n+2m)$-dimensional particle. The decoding method starts by transforming the particle to a priority list of customers to enter the route and a priority matrix of vehicles to serve each customer. The vehicle routes are constructed based on the customer priority list and vehicle priority matrix. The proposed algorithm is tested using three benchmark data sets available from the literature. The computational result shows that the proposed method is competitive with other published results for solving VRPSPD. Some new best known solutions of the benchmark problem are also found by the proposed method.