An improved vector particle swarm optimization for constrained optimization problems

Increasing attention is being paid to solve constrained optimization problems (COP) frequently encountered in real-world applications. In this paper, an improved vector particle swarm optimization (IVPSO) algorithm is proposed to solve COPs. The constraint-handling technique is based on the simple constraint-preserving method. Velocity and position of each particle, as well as the corresponding changes, are all expressed as vectors in order to present the optimization procedure in a more intuitively comprehensible manner. The NVPSO algorithm [30], which uses one-dimensional search approaches to find a new feasible position on the flying trajectory of the particle when it escapes from the feasible region, has been proposed to solve COP. Experimental results showed that searching only on the flying trajectory for a feasible position influenced the diversity of the swarm and thus reduced the global search capability of the NVPSO algorithm. In order to avoid neglecting any worthy position in the feasible region and improve the optimization efficiency, a multi-dimensional search algorithm is proposed to search within a local region for a new feasible position. The local region is composed of all dimensions of the escaped particle’s parent and the current positions. Obviously, the flying trajectory of the particle is also included in this local region. The new position is not only present in the feasible region but also has a better fitness value in this local region. The performance of IVPSO is tested on 13 well-known benchmark functions. Experimental results prove that the proposed IVPSO algorithm is simple, competitive and stable.     

Non-parametric particle swarm optimization for global optimization

In recent years, particle swarm optimization (PSO) has extensively applied in various optimization problems because of its simple structure. Although the PSO may find local optima or exhibit slow convergence speed when solving complex multimodal problems. Also, the algorithm requires setting several parameters, and tuning the parameters is a challenging for some optimization problems. To address these issues, an improved PSO scheme is proposed in this study. The algorithm, called non-parametric particle swarm optimization (NP-PSO) enhances the global exploration and the local exploitation in PSO without tuning any algorithmic parameter. NP-PSO combines local and global topologies with two quadratic interpolation operations to increase the search ability. Nineteen (19) unimodal and multimodal nonlinear benchmark functions are selected to compare the performance of NP-PSO with several well-known PSO algorithms. The experimental results showed that the proposed method considerably enhances the efficiency of PSO algorithm in terms of solution accuracy, convergence speed, global optimality, and algorithm reliability.     

Instance variant nearest neighbor using particle swarm optimization for function approximation

In this paper, a new approach called ‘instance variant nearest neighbor’ approximates a regression surface of a function using the concept of k nearest neighbor. Instead of fixed k neighbors for the entire dataset, our assumption is that there are optimal k neighbors for each data instance that best approximates the original function by fitting the local regions. This approach can be beneficial to noisy datasets where local regions form data characteristics that are different from the major data clusters. We formulate the problem of finding such k neighbors for each data instance as a combinatorial optimization problem, which is solved by a particle swarm optimization. The particle swarm optimization is extended with a rounding scheme that rounds up or down continuous-valued candidate solutions to integers, a number of k neighbors. We apply our new approach to five real-world regression datasets and compare its prediction performance with other function approximation algorithms, including the standard k nearest neighbor, multi-layer perceptron, and support vector regression. We observed that the instance variant nearest neighbor outperforms these algorithms in several datasets. In addition, our new approach provides consistent outputs with five datasets where other algorithms perform poorly.     

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.     

Penalty function approach for the mixed discrete nonlinear problems by particle swarm optimization

In this paper, the basic characteristics of particle swarm optimization (PSO) for the global search are discussed at first, and then the PSO for the mixed discrete nonlinear problems (MDNLP) is suggested. The penalty function approach to handle the discrete design variables is employed, in which the discrete design variables are handled as the continuous ones by penalizing at the intervals. As a result, a useful method to determine the penalty parameter of penalty term for the discrete design variables is proposed. Through typical mathematical and structural optimization problems, the validity of the proposed approach for the MDNLP is examined.     

A discrete version of particle swarm optimization for flowshop scheduling problems

Particle swarm optimization (PSO) is a novel metaheuristic inspired by the flocking behavior of birds. The applications of PSO to scheduling problems are extremely few. In this paper, we present a PSO algorithm, extended from discrete PSO, for flowshop scheduling. In the proposed algorithm, the particle and the velocity are redefined, and an efficient approach is developed to move a particle to the new sequence. To verify the proposed PSO algorithm, comparisons with a continuous PSO algorithm and two genetic algorithms are made. Computational results show that the proposed PSO algorithm is very competitive. Furthermore, we incorporate a local search scheme into the proposed algorithm, called PSO-LS. Computational results show that the local search can be really guided by PSO in our approach. Also, PSO-LS performs well in flowshop scheduling with total flow time criterion, but it requires more computation times.     

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

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

An improved quantum-behaved particle swarm optimization for multi-peak optimization problems

In this paper, we propose an improved quantum-behaved particle swarm optimization (QPSO), namely species-based QPSO (SQPSO), using the notion of species for solving multi-peak optimization problems. In the proposed SQPSO, the population is divided into subpopulations (species) based on their similarities. Each species is grouped around a dominating particle called the species seed. During the process of iterations, species are able to simultaneously optimize towards multiple optima by using QPSO, so each peak will definitely be searched in parallel, regardless of whether it is global or local optima. Further, SQPSO is applied to solve systems of nonlinear equations describing certain fitness functions, which are multi-peak functions. Our experiments demonstrate that SQPSO is able to search multiple peaks of a given function as accurate and efficient as possible. Finally the experiments for the solutions of systems of nonlinear equations show that the algorithm is successful in locating multiple solutions with better accuracy.     

Cellular particle swarm optimization

This paper proposes a cellular particle swarm optimization (CPSO), hybridizing cellular automata (CA) and particle swarm optimization (PSO) for function optimization. In the proposed CPSO, a mechanism of CA is integrated in the velocity update to modify the trajectories of particles to avoid being trapped in the local optimum. With two different ways of integration of CA and PSO, two versions of CPSO, i.e. CPSO-inner and CPSO-outer, have been discussed. For the former, we devised three typical lattice structures of CA used as neighborhood, enabling particles to interact inside the swarm; and for the latter, a novel CA strategy based on “smart-cell” is designed, and particles employ the information from outside the swarm. Theoretical studies are made to analyze the convergence of CPSO, and numerical experiments are conducted to compare the proposed algorithm with different variants of PSO. According to the experimental results, the proposed method performs better than other variants of PSO on benchmark test functions.     

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.     

Unified particle swarm delivers high efficiency to particle swarm optimization

This paper suggests integrating a unification factor into particle swarm optimization (PSO) to balance the effects of cognitive and social terms. The resultant unified particle swarm (UPS) moves particles toward the center of its personal best and the global best. This improves on PSO, which moves particles far beyond the center. Widely used benchmark functions and four types of experiments demonstrate that the proposed UPS uses slightly more computational time than PSO to attain significantly higher efficiency and, usually, better solution effectiveness and consistency than PSO. Robust performance was further demonstrated by the significantly higher efficiency and better solution effectiveness and stability achieved by the UPS, as compared to the PSO and its variants. Outstandingly, convergence speeds for the proposed UPS were very good on the 13 benchmark functions examined in experiment 1, demonstrating the correct movement of UPS particles toward convergence.     

Improved global-best-guided particle swarm optimization with learning operation for global optimization problems

In this paper, an improved global-best-guided particle swarm optimization with learning operation (IGPSO) is proposed for solving global optimization problems. The particle population is divided into current population, historical best population and global best population, and each population is assigned a corresponding searching strategy. For the current population, the global neighborhood exploration strategy is employed to enhance the global exploration capability. A local learning mechanism is used to improve local exploitation ability in the historical best population. Furthermore, stochastic learning and opposition based learning operations are employed to the global best population for accelerating convergence speed and improving optimization accuracy. The effects of the relevant parameters on the performance of IGPSO are assessed. Numerical experiments on some well-known benchmark test functions reveal that IGPSO algorithm outperforms other state-of-the-art intelligent algorithms in terms of accuracy, convergence speed, and nonparametric statistical significance. Moreover, IGPSO performs better for engineering design optimization problems.     

Co-evolutionary particle swarm optimization to solve constrained optimization problems

This paper presents a co-evolutionary particle swarm optimization (CPSO) algorithm to solve global nonlinear optimization problems. A new co-evolutionary PSO (CPSO) is constructed. In the algorithm, a deterministic selection strategy is proposed to ensure the diversity of population. Meanwhile, based on the theory of extrapolation, the induction of evolving direction is enhanced by adding a co-evolutionary strategy, in which the particles make full use of the information each other by using gene-adjusting and adaptive focus-varied tuning operator. Infeasible degree selection mechanism is used to handle the constraints. A new selection criterion is adopted as tournament rules to select individuals. Also, the infeasible solution is properly accepted as the feasible solution based on a defined threshold of the infeasible degree. This diversity mechanism is helpful to guide the search direction towards the feasible region. Our approach was tested on six problems commonly used in the literature. The results obtained are repeatedly closer to the true optimum solution than the other techniques.     

A hybrid particle swarm optimization algorithm for high-dimensional problems

In recent years, particle swarm optimization (PSO) emerges as a new optimization scheme that has attracted substantial research interest due to its simplicity and efficiency. However, when applied to high-dimensional problems, PSO suffers from premature convergence problem which results in a low optimization precision or even failure. To remedy this fault, this paper proposes a novel memetic PSO (CGPSO) algorithm which combines the canonical PSO with a Chaotic and Gaussian local search procedure. In the initial evolution phase, CGPSO explores a wide search space that helps avoid premature convergence through Chaotic local search. Then in the following run phase, CGPSO refines the solutions through Gaussian optimization. To evaluate the effectiveness and efficiency of the CGPSO algorithm, thirteen high dimensional non-linear scalable benchmark functions were examined. Results show that, compared to the standard PSO, CGPSO is more effective, faster to converge, and less sensitive to the function dimensions. The CGPSO was also compared with two PSO variants, CPSO-H, DMS-L-PSO, and two memetic optimizers, DEachSPX and MA-S2. CGPSO is able to generate a better, or at least comparable, performance in terms of optimization accuracy. So it can be safely concluded that the proposed CGPSO is an efficient optimization scheme for solving high-dimensional problems.     

An interval space reducing method for constrained problems with particle swarm optimization

In this paper, we propose a method for solving constrained optimization problems using interval analysis combined with particle swarm optimization. A set inverter via interval analysis algorithm is used to handle constraints in order to reduce constrained optimization to quasi unconstrained one. The algorithm is useful in the detection of empty search spaces, preventing useless executions of the optimization process. To improve computational efficiency, a space cleaning algorithm is used to remove solutions that are certainly not optimal. As a result, the search space becomes smaller at each step of the optimization procedure. After completing pre-processing, a modified particle swarm optimization algorithm is applied to the reduced search space to find the global optimum. The efficiency of the proposed approach is demonstrated through comprehensive experimentation involving 100 000 runs on a set of well-known benchmark constrained engineering design problems. The computational efficiency of the new method is quantified by comparing its results with other PSO variants found in the literature.     

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.     

Genetic particle swarm optimization for polygonal approximation of digital curves

Polygonal approximation is an important technique in image representation which directly impacts on the accuracy and efficacy of the subsequent image analysis tasks. This paper presents a new polygonal approximation approach based on particle swarm optimization (PSO). The original PSO is customized to continuous function value optimization. To facilitate the applicability of PSO to combinatorial optimization involving the problem in question, genetic reproduction mechanisms, namely crossover and mutation, are incorporated into PSO. We also propose a hybrid strategy embedding a segment-adjusting-and-merging optimizer into the genetic PSO evolutionary iterations to enhance its performance. The experimental results show that the proposed genetic PSO significantly improves the search efficacy of PSO for the polygonal approximation problem, and the hybrid strategy can accelerate the convergence speed but still with good-quality results. The performance of the proposed method is compared to existing approaches on both synthesized and real image curves. It is shown that the proposed hybrid genetic PSO outperforms the polygonal approximation approaches based on genetic algorithms and ant colony algorithms. The text was submitted by the author in English. Peng-Yeng Yin was born in 1966 and received his B.S., M.S. and Ph.D. degrees in Computer Science from National Chiao Tung University, Hsinchu, Taiwan, in 1989, 1991 and 1994, respectively. From 1993 to 1994, he was a visiting scholar at the Department of Electrical Engineering, University of Maryland, and the Department of Radiology, Georgetown University. In 2000, he was a visiting Associate Professor in the Visualization and Intelligent Systems Lab (VISLab) at the Department of Electrical Engineering, University of California, Riverside (UCR). He is currently a Professor at the Department of Information Management, National Chi Nan University, Nantou, Taiwan. His current research interests include image processing, pattern recognition, machine learning, computational biology, and evolutionary computation. He has published more than 70 articles in refereed journals and conferences. Dr. Yin received the Overseas Research Fellowship from the Ministry of Education in 1993 and Overseas Research Fellowship from the National Science Council in 2000. He is a member of the Phi Tau Phi Scholastic Honor Society and listed in Who’s Who in the World.     

A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems

In the real-world applications, most optimization problems are subject to different types of constraints. These problems are known as constrained optimization problems (COPs). Solving COPs is a very important area in the optimization field. In this paper, a hybrid multi-swarm particle swarm optimization (HMPSO) is proposed to deal with COPs. This method adopts a parallel search operator in which the current swarm is partitioned into several subswarms and particle swarm optimization (PSO) is severed as the search engine for each sub-swarm. Moreover, in order to explore more promising regions of the search space, differential evolution (DE) is incorporated to improve the personal best of each particle. First, the method is tested on 13 benchmark test functions and compared with three stateof-the-art approaches. The simulation results indicate that the proposed HMPSO is highly competitive in solving the 13 benchmark test functions. Afterward, the effectiveness of some mechanisms proposed in this paper and the effect of the parameter setting were validated by various experiments. Finally, HMPSO is further applied to solve 24 benchmark test functions collected in the 2006 IEEE Congress on Evolutionary Computation (CEC2006) and the experimental results indicate that HMPSO is able to deal with 22 test functions.     

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.     

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.