Niching Without Niching Parameters: Particle Swarm Optimization Using a Ring Topology

Niching is an important technique for multimodal optimization. Most existing niching methods require specification of certain niching parameters in order to perform well. These niching parameters, often used to inform a niching algorithm how far apart between two closest optima or the number of optima in the search space, are typically difficult to set as they are problem dependent. This paper describes a simple yet effective niching algorithm, a particle swarm optimization (PSO) algorithm using a ring neighborhood topology, which does not require any niching parameters. A PSO algorithm using the ring topology can operate as a niching algorithm by using individual particles' local memories to form a stable network retaining the best positions found so far, while these particles explore the search space more broadly. Given a reasonably large population uniformly distributed in the search space, PSO algorithms using the ring topology are able to form stable niches across different local neighborhoods, eventually locating multiple global/local optima. The complexity of these niching algorithms is only $ {cal O}(N)$, where $N$ is the population size. Experimental results suggest that PSO algorithms using the ring topology are able to provide superior and more consistent performance over some existing PSO niching algorithms that require niching parameters.      

基于小生境粒子群算法的图像分割方法

为了得到分割图像的最佳阈值,提出了一种基于小生境粒子群算法的图像分割方法。小生境粒子群算法通过划分小生境的方法,保持了物种的多样性,克服了粒子群算法容易陷入局部解,后期收敛速度慢的缺点,提高了算法的全局寻优能力。该方法基于最大类间方差阈值分割技术,用小生境粒子群算法对适应度函数进行优化,得到最佳阈值,并用该阈值对图像进行分割。实验结果表明,与最大类间方差法,基于基本粒子群算法的最大类间方差分割法相比,所提出的方法不仅能得到理想的分割结果,而且分割速度也得到了提高。     

A novel particle swarm niching technique based on extensive vector operations

Several techniques have been proposed to extend the particle swarm optimization (PSO) paradigm so that multiple optima can be located and maintained within a convoluted search space. A significant number of these implementations are subswarm-based, that is, portions of the swarm are optimized separately. Niches are formed to contain these subswarms, a process that often requires user-specified parameters. The proposed technique, known as the vector-based PSO, uses a novel approach to locate and maintain niches by using additional vector operations to determine niche boundaries. As the standard PSO uses weighted vector combinations to update particle positions and velocities, the niching technique builds upon existing knowledge of the particle swarm. Once niche boundaries have been calculated, the swarm can be organized into subswarms without prior knowledge of the number of niches and their corresponding niche radii. This paper presents the vector-based PSO with emphasis on its underlying principles. Results for a number of functions with different characteristics are reported and discussed. The performance of the vector-based PSO is also compared to two other niching techniques for particle swarm optimization.     

A hybrid niching PSO enhanced with recombination-replacement crowding strategy for multimodal function optimization

This paper presents a hybrid niching algorithm based on the PSO to deal with multimodal function optimization problems. First, we propose to evolve directly both the particle population and memory population (archive population), called the P&A pattern, to enhance the efficiency of the PSO for solving multimodal optimization functions, and investigate illustratively the niching capability of the PSO and the PSO_P&A. It is found that the global version PSO is disable, but the local version PSO_P&A is able, to niche multiple species for locating multiple optima. Second, the recombination-replacement crowding strategy that works on the archive population is introduced to improve the exploration capability, and the hybrid niching PSO_P&A (HN-PSO_P&A) is developed. Finally, experiments are carried out on multimodal functions for testing the niching efficiency and scalability of the proposed method, and it is verified that the proposed method has a sub-quadratic scalability with dimension in terms of fitness function evaluations on specific MMFO problems.     

Multimodal optimization using a bi-objective evolutionary algorithm

In a multimodal optimization task, the main purpose is to find multiple optimal solutions (global and local), so that the user can have better knowledge about different optimal solutions in the search space and as and when needed, the current solution may be switched to another suitable optimum solution. To this end, evolutionary optimization algorithms (EA) stand as viable methodologies mainly due to their ability to find and capture multiple solutions within a population in a single simulation run. With the preselection method suggested in 1970, there has been a steady suggestion of new algorithms. Most of these methodologies employed a niching scheme in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different strategy in which the single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all optimal solutions become members of the resulting weak Pareto-optimal set. With the modified definitions of domination and different formulations of an artificially created additional objective function, we present successful results on problems with as large as 500 optima. Most past multimodal EA studies considered problems having only a few variables. In this paper, we have solved up to 16-variable test problems having as many as 48 optimal solutions and for the first time suggested multimodal constrained test problems which are scalable in terms of number of optima, constraints, and variables. The concept of using bi-objective optimization for solving single-objective multimodal optimization problems seems novel and interesting, and more importantly opens up further avenues for research and application.     

用于多峰函数优化的改进小生境微粒群算法

针对小生境微粒群算法在处理复杂多峰函数优化问题中存在的一些缺陷,提出一种改进的小生境SNPSO算法。SNPSO算法将顺序小生境的思想引入其中,首先在主群体中应用Stretching技术,其次对子群体采用解散策略,即当在子群体中找到一个极值点后把子群体解散回归主群体,最后设置子群体创建时的半径阈值,避免子群体半径过大。该算法解决了标准的NichePSO算法在处理多峰函数时,极值点的个数依赖于子群体个数及极值点容易出现重复、遗漏等问题。对3个常用的基本测试函数的实验表明,新算法（SNPSO）在多峰函数寻优中解的稳定性、收敛性和覆盖率均优于标准NichePSO。     

Accurate sub-swarms particle swarm optimization algorithm for service composition

Service composition (SC) generates various composite applications quickly by using a novel service interaction model. Before composing services together, the most important thing is to find optimal candidate service instances compliant with non-functional requirements. Particle swarm optimization (PSO) is known as an effective and efficient algorithm, which is widely used in this process. However, the premature convergence and diversity loss of PSO always results in suboptimal solutions. In this paper, we propose an accurate sub-swarms particle swarm optimization (ASPSO) algorithm by adopting parallel and serial niching techniques. The ASPSO algorithm locates optimal solutions by using sub-swarms searching grid cells in which the density of feasible solutions is high. Simulation results demonstrate that the proposed algorithm improves the accuracy of the standard PSO algorithm in searching the optimal solution of service selection problem.     

A modified particle swarm optimization for economic dispatch with non-smooth cost functions

This paper presents a new approach to economic dispatch (ED) problems with non-smooth cost functions using a particle swarm optimization (PSO) technique. The practical ED problems have non-smooth cost functions with equality and inequality constraints, which makes the problem of finding the global optimum difficult when using any mathematical approaches. Since, standard PSO may converge at the early stage, in this paper, a modified PSO (MPSO) mechanism is suggested to deal with the equality and inequality constraints in the ED problems. To validate the results obtained by MPSO, standard particle swarm optimization (PSO) and guaranteed convergence particle swarm optimization (GCPSO) are applied for comparison. Also, the results obtained by MPSO, PSO and GCPSO are compared with the previous approaches reported in the literature. The results show that the MPSO produces optimal or nearly optimal solutions for the study systems.     

Handling multi-objective optimization problems with a multi-swarm cooperative particle swarm optimizer

This paper presents a new multi-objective optimization algorithm in which multi-swarm cooperative strategy is incorporated into particle swarm optimization algorithm, called multi-swarm cooperative multi-objective particle swarm optimizer (MC-MOPSO). This algorithm consists of multiple slave swarms and one master swarm. Each slave swarm is designed to optimize one objective function of the multi-objective problem in order to find out all the non-dominated optima of this objective function. In order to produce a well distributed Pareto front, the master swarm is developed to cover gaps among non-dominated optima by using a local MOPSO algorithm. Moreover, in order to strengthen the capability locating multiple optima of the PSO, several improved techniques such as the Pareto dominance-based species technique and the escape strategy of mature species are introduced. The simulation results indicate that our algorithm is highly competitive to solving the multi-objective optimization problems.     

Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem

The studied resource-constrained project scheduling problem (RCPSP) is a classical well-known problem which involves resource, precedence, and temporal constraints and has been applied to many applications. However, the RCPSP is confirmed to be an NP-hard combinatorial problem. Restated, it is hard to be solved in a reasonable time. Therefore, there are many metaheuristics-based schemes for finding near optima of RCPSP were proposed. The particle swarm optimization (PSO) is one of the metaheuristics, and has been verified being an efficient nature-inspired algorithm for many optimization problems. For enhancing the PSO efficiency in solving RCPSP, an effective scheme is suggested. The justification technique is combined with PSO as the proposed justification particle swarm optimization (JPSO), which includes other designed mechanisms. The justification technique adjusts the start time of each activity of the yielded schedule to further shorten the makespan. Moreover, schedules are generated by both forward scheduling particle swarm and backward scheduling particle swarm in this work. Additionally, a mapping scheme and a modified communication mechanism among particles with a designed gbest ratio (GR) are also proposed to further improve the efficiency of the proposed JPSO. Simulation results demonstrate that the proposed JPSO provides an effective and efficient approach for solving RCPSP.     

Formulation and parameter selection of multi-objective deterministic particle swarm for simulation-based optimization

Global derivative-free deterministic algorithms are particularly suitable for simulation-based optimization, where often the existence of multiple local optima cannot be excluded a priori, the derivatives of the objective functions are not available, and the evaluation of the objectives is computationally expensive, thus a statistical analysis of the optimization outcomes is not practicable. Among these algorithms, particle swarm optimization (PSO) is advantageous for the ease of implementation and the capability of providing good approximate solutions to the optimization problem at a reasonable computational cost. PSO has been introduced for single-objective problems and several extension to multi-objective optimization are available in the literature. The objective of the present work is the systematic assessment and selection of the most promising formulation and setup parameters of multi-objective deterministic particle swarm optimization (MODPSO) for simulation-based problems. A comparative study of six formulations (varying the definition of cognitive and social attractors) and three setting parameters (number of particles, initialization method, and coefficient set) is performed using 66 analytical test problems. The number of objective functions range from two to three and the number of variables from two to eight, as often encountered in simulation-based engineering problems. The desired Pareto fronts are convex, concave, continuous, and discontinuous. A full-factorial combination of formulations and parameters is investigated, leading to more than 60,000 optimization runs, and assessed by three performance metrics. The most promising MODPSO formulation/parameter is identified and applied to the hull-form optimization of a high-speed catamaran in realistic ocean conditions. Its performance is finally compared with four stochastic algorithms, namely three versions of multi-objective PSO and the genetic algorithm NSGA-II.     

Force-imitated particle swarm optimization using the near-neighbor effect for locating multiple optima

Multimodal optimization problems pose a great challenge of locating multiple optima simultaneously in the search space to the particle swarm optimization (PSO) community. In this paper, the motion principle of particles in PSO is extended by using the near-neighbor effect in mechanical theory, which is a universal phenomenon in nature and society. In the proposed near-neighbor effect based force-imitated PSO (NN-FPSO) algorithm, each particle explores the promising regions where it resides under the composite forces produced by the “near-neighbor attractor” and “near-neighbor repeller”, which are selected from the set of memorized personal best positions and the current swarm based on the principles of “superior-and-nearer” and “inferior-and-nearer”, respectively. These two forces pull and push a particle to search for the nearby optimum. Hence, particles can simultaneously locate multiple optima quickly and precisely. Experiments are carried out to investigate the performance of NN-FPSO in comparison with a number of state-of-the-art PSO algorithms for locating multiple optima over a series of multimodal benchmark test functions. The experimental results indicate that the proposed NN-FPSO algorithm can efficiently locate multiple optima in multimodal fitness landscapes.     

Novel hybrid optimization algorithm using PSO and MADS for the trajectory estimation of a four track wheel skid-steered mobile robot

Several optimization algorithms, such as the particle swarm optimization (PSO), genetic algorithm (GA), and ant colony optimization, have previously been applied in order to reliably obtain more accurate trajectory estimation for mobile robot. However, these optimization algorithms can get easily trapped in local optima when solving a complex system, which has many local optima and many input variables. This paper proposes a novel hybrid optimization algorithm-based tuning of the extended Kalman filter, which involves the PSO and mesh adaptive direct search algorithms, prior to operation. As demonstrated by our experimental results, the advantages of the novel hybrid optimization algorithm resolve the limitations of other algorithms in the trajectory estimation of a four track wheel skid-steered mobile robot (4-TW SSMR).     

Distributed learning particle swarm optimizer for global optimization of multimodal problems

Particle swarm optimizer (PSO) is an effective tool for solving many optimization problems. However, it may easily get trapped into local optimumwhen solving complex multimodal nonseparable problems. This paper presents a novel algorithm called distributed learning particle swarm optimizer (DLPSO) to solve multimodal nonseparable problems. The strategy for DLPSO is to extract good vector information from local vectors which are distributed around the search space and then to form a new vector which can jump out of local optima and will be optimized further. Experimental studies on a set of test functions show that DLPSO exhibits better performance in solving optimization problems with few interactions between variables than several other peer algorithms.     

An Efficient Hybrid Particle Swarm Optimization Algorithm for Solving the Uncapacitated Continuous Location-Allocation Problem

Location-allocation problems are a class of complicated optimization problems that determine the location of facilities and the allocation of customers to the facilities. In this paper, the uncapacitated continuous location-allocation problem is considered, and a particle swarm optimization approach, which has not previously been applied to this problem, is presented. Two algorithms including classical and hybrid particle swarm optimization algorithms are developed. Local optima of the problem are obtained by two local search heuristics that exist in the literature. These algorithms are combined with particle swarm optimization to construct an efficient hybrid approach. Many large-scale problems are used to measure the effectiveness and efficiency of the proposed algorithms. Our results are compared with the best algorithms in the literature. The experimental results show that the hybrid PSO produces good solutions, is more efficient than the classical PSO, and is competitive with the best results from the literature. Additionally, the proposed hybrid PSO found better solutions for some instances than did the best known solutions in the literature.     

GA与PSO解DE与LP问题的效率比较

遗传算法和粒子群算法都具有很强的搜索能力,在最优化问题中有着极其广泛的应用.文章针对常微分方程(DE)近似解和一般线性规划(LP)问题的解利用遗传算法和粒子群算法求解,深入的比较和分析了GA与PSO在这两种优化问题中的效率.在固定其他参数而调整群体数量的基础上比较了GA与PSO在微分方程近似解和LP问题解的优化能力.     

An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem

Hybrid flow shops (HFS) are common manufacturing environments in many industries, such as the glass, steel, paper and textile industries. In this paper, we present a particle swarm optimization (PSO) algorithm for the HFS scheduling problem with minimum makespan objective. The main contribution of this paper is to develop a new approach hybridizing PSO with bottleneck heuristic to fully exploit the bottleneck stage, and with simulated annealing to help escape from local optima. The proposed PSO algorithm is tested on the benchmark problems provided by Carlier and Néron. Experimental results show that the proposed algorithm outperforms all the compared algorithms in solving the HFS problem.     

一种基于聚类的小生境微粒群算法

在小生境微粒群算法中引入一种简单的聚类算法，替换了原算法中依赖于圆形拓扑领域的小生境产生方法，构建出一种基于聚类的小生境微粒群算法．该算法在对主微粒群进行l best PSO寻优的同时对其中的微粒进行聚类，当聚类簇中的个体数目达到规定的子微粒群最小规模时形成一个小生境．用这种算法能够产生大小和形状不同的小生境，克服了NichePSO算法的不足．     

A two-stage quantum-behaved particle swarm optimization with skipping search rule and weight to solve continuous optimization problem

Quantum-behaved particle swarm optimization (QPSO) is a recently developed heuristic method by particle swarm optimization (PSO) algorithm based on quantum mechanics, which outperforms the search ability of original PSO. But as many other PSOs, it is easy to fall into the local optima for the complex optimization problems. Therefore, we propose a two-stage quantum-behaved particle swarm optimization with a skipping search rule and a mean attractor with weight. The first stage uses quantum mechanism, and the second stage uses the particle swarm evolution method. It is shown that the improved QPSO has better performance, because of discarding the worst particles and enhancing the diversity of the population. The proposed algorithm (called ‘TSQPSO’) is tested on several benchmark functions and some real-world optimization problems and then compared with the PSO, SFLA, RQPSO and WQPSO and many other heuristic algorithms. The experiment results show that our algorithm has better performance than others.     

基于函数变换的改进混沌粒子群优化*

粒子群在搜索过程中容易陷入局部而无法找到全局最优值,为了解决此早熟问题,提出基于函数变换的改进混沌粒子群优化算法。此方法将Logistic映射和改进的Tent映射引入到粒子群中代替随机数;将函数变换引入到粒子的速度、位置更新过程中以凸显全局最优值与局部极优值的差异,从而使粒子跳出局部极优值点,加细搜索进而找到全局最优值点。数值实验表明,基于函数变换的改进混沌粒子群在搜索时间和效率上要优于标准粒子群和基于Logistic映射的混沌粒子群。改进的算法是可行而有效的。