Parallel global optimization with the particle swarm algorithm

Present day engineering optimization problems often impose large computational demands, resulting in long solution times even on a modern high-end processor. To obtain enhanced computational throughput and global search capability, we detail the coarse-grained parallelization of an increasingly popular global search method, the particle swarm optimization (PSO) algorithm. Parallel PSO performance was evaluated using two categories of optimization problems possessing multiple local minima-large-scale analytical test problems with computationally cheap function evaluations and medium-scale biomechanical system identification problems with computationally expensive function evaluations. For load-balanced analytical test problems formulated using 128 design variables, speedup was close to ideal and parallel efficiency above 95% for up to 32 nodes on a Beowulf cluster. In contrast, for load-imbalanced biomechanical system identification problems with 12 design variables, speedup plateaued and parallel efficiency decreased almost linearly with increasing number of nodes. The primary factor affecting parallel performance was the synchronization requirement of the parallel algorithm, which dictated that each iteration must wait for completion of the slowest fitness evaluation. When the analytical problems were solved using a fixed number of swarm iterations, a single population of 128 particles produced a better convergence rate than did multiple independent runs performed using sub-populations (8 runs with 16 particles, 4 runs with 32 particles, or 2 runs with 64 particles). These results suggest that (1) parallel PSO exhibits excellent parallel performance under load-balanced conditions, (2) an asynchronous implementation would be valuable for real-life problems subject to load imbalance, and (3) larger population sizes should be considered when multiple processors are available.     

Drilling path optimization by the particle swarm optimization algorithm with global convergence characteristics

Drilling path optimization is one of the key problems in holes-machining. This paper presents a new approach to solve the drilling path optimization problem belonging to discrete space, based on the particle swarm optimization (PSO) algorithm. Since the standard PSO algorithm is not guaranteed to be global convergent or local convergent, based on the mathematical model, the algorithm is improved by adopting the method to generate the stop evolution particle once again to obtain the ability of convergence on the global optimization solution. Also, the operators are proposed by establishing the Order Exchange Unit (OEU) and the Order Exchange List (OEL) to satisfy the need of integer coding in drilling path optimization. The experimentations indicate that the improved algorithm has the characteristics of easy realization, fast convergence speed, and better global convergence capability. Hence the new PSO can play a role in solving the problem of drilling path optimization.     

A parallel particle swarm optimization algorithm for multi-objective optimization problems

In this article, a new proposal of using particle swarm optimization algorithms to solve multi-objective optimization problems is presented. The algorithm is constructed based on the concept of Pareto dominance, as well as a state-of-the-art ‘parallel’ computing technique that intends to improve algorithmic effectiveness and efficiency simultaneously. The proposed parallel particle swarm multi-objective evolutionary algorithm (PPS-MOEA) is tested through a variety of standard test functions taken from the literature; its performance is compared with six noted multi-objective algorithms. The computational experience gained from the first two experiments indicates that the algorithm proposed in this article is extremely competitive when compared with other MOEAs, being able to accurately, reliably and robustly approximate the true Pareto front in almost every tested case. To justify the motivation behind the research of the parallel swarm structure, the computational results of the third experiment confirm the PPS-MOEA's merit in solving really high-dimensional multi-objective optimization problems.     

求解复杂优化问题的双层多种群粒子群优化算法

为解决粒子群优化算法存在的易早熟和精度低问题,提出了一种双层多种群粒子群优化算法.此算法采用上下两层,即下层N个基础种群和上层一个精英种群.各个基础种群相互独立进化,并从精英种群中得到优良信息指导自己的进化.上层精英种群首先通过接受各基础种群的当前最优粒子来更新自己的粒子集合,然后执行自适应变异操作,最后随机地向每一个基础种群输送出本次进化后的一个最优粒子来改进其下一轮搜索.该算法的并行双进化机制增加了群体的随机性和多样性,提高了全局搜索能力和收敛精度.实例仿真表明该算法具有较好的性能,尤其对于复杂多峰函数优化,成功率显著提高.     

An adaptive metamodel-based global optimization algorithm for black-box type problems

In this article, an adaptive metamodel-based global optimization (AMGO) algorithm is presented to solve unconstrained black-box problems. In the AMGO algorithm, a type of hybrid model composed of kriging and augmented radial basis function (RBF) is used as the surrogate model. The weight factors of hybrid model are adaptively selected in the optimization process. To balance the local and global search, a sub-optimization problem is constructed during each iteration to determine the new iterative points. As numerical experiments, six standard two-dimensional test functions are selected to show the distributions of iterative points. The AMGO algorithm is also tested on seven well-known benchmark optimization problems and contrasted with three representative metamodel-based optimization methods: efficient global optimization (EGO), GutmannRBF and hybrid and adaptive metamodel (HAM). The test results demonstrate the efficiency and robustness of the proposed method. The AMGO algorithm is finally applied to the structural design of the import and export chamber of a cycloid gear pump, achieving satisfactory results.     

An efficient particle swarm approach for mixed-integer programming in reliability-redundancy optimization applications

The reliability-redundancy optimization problems can involve the selection of components with multiple choices and redundancy levels that produce maximum benefits, and are subject to the cost, weight, and volume constraints. Many classical mathematical methods have failed in handling nonconvexities and nonsmoothness in reliability-redundancy optimization problems. As an alternative to the classical optimization approaches, the meta-heuristics have been given much attention by many researchers due to their ability to find an almost global optimal solutions. One of these meta-heuristics is the particle swarm optimization (PSO). PSO is a population-based heuristic optimization technique inspired by social behavior of bird flocking and fish schooling. This paper presents an efficient PSO algorithm based on Gaussian distribution and chaotic sequence (PSO-GC) to solve the reliability-redundancy optimization problems. In this context, two examples in reliability-redundancy design problems are evaluated. Simulation results demonstrate that the proposed PSO-GC is a promising optimization technique. PSO-GC performs well for the two examples of mixed-integer programming in reliability-redundancy applications considered in this paper. The solutions obtained by the PSO-GC are better than the previously best-known solutions available in the recent literature.     

A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks

The multistage hybrid flow-shop scheduling problem with multiprocessor tasks has been found in many practical situations. Due to the essential complexity of the problem, many researchers started to apply metaheuristics to solve the problem. In this paper, we address the problem by using particle swarm optimization (PSO), a novel metaheuristic inspired by the flocking behaviour of birds. The proposed PSO algorithm has several features, such as a new encoding scheme, an implementation of the best velocity equation and neighbourhood topology among several different variants, and an effective incorporation of local search. To verify the PSO algorithm, computational experiments are conducted to make a comparison with two existing genetic algorithms (GAs) and an ant colony system (ACS) algorithm based on the same benchmark problems. The results show that the proposed PSO algorithm outperforms all the existing algorithms for the considered problem.     

Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions

This article proposes the hybrid Nelder–Mead (NM)–Particle Swarm Optimization (PSO) algorithm based on the NM simplex search method and PSO for the optimization of multimodal functions. The hybrid NM–PSO algorithm is very easy to implement, in practice, since it does not require gradient computation. This hybrid procedure performed the exploration with PSO and the exploitation with the NM simplex search method. In a suite of 17 multi-optima test functions taken from the literature, the computational results via various experimental studies showed that the hybrid NM–PSO approach is superior to the two original search techniques (i.e. NM and PSO) in terms of solution quality and convergence rate. In addition, the presented algorithm is also compared with eight other published methods, such as hybrid genetic algorithm (GA), continuous GA, simulated annealing (SA), and tabu search (TS) by means of a smaller set of test functions. On the whole, the new algorithm is demonstrated to be extremely effective and efficient at locating best-practice optimal solutions for multimodal functions.     

Solving constrained optimization problems with a hybrid particle swarm optimization algorithm

This article presents a particle swarm optimization algorithm for solving general constrained optimization problems. The proposed approach introduces different methods to update the particle's information, as well as the use of a double population and a special shake mechanism designed to avoid premature convergence. It also incorporates a simple constraint-handling technique. Twenty-four constrained optimization problems commonly adopted in the evolutionary optimization literature, as well as some structural optimization problems are adopted to validate the proposed approach. The results obtained by the proposed approach are compared with respect to those generated by algorithms representative of the state of the art in the area.     

Hybrid metamodel-based design space management method for expensive problems

Metamodel-based global optimization methods have been extensively studied for their great potential in solving expensive problems. In this work, a design space management strategy is proposed to improve the accuracy and efficiency of metamodel-based optimization methods. In this strategy, the whole design space is divided into two parts: the important region constructed using several expensive points and the other region. Combined with a previously developed hybrid metamodel strategy, a hybrid metamodel-based design space management method (HMDSM) is developed. In this method, three representative metamodels are used simultaneously in the search of the global optimum in both the important region and the other region. In the search process, the important region is iteratively reduced and the global optimum is soon captured. Tests using a series of benchmark mathematical functions and a practical expensive problem demonstrate the excellent performance of the proposed method.     

A new images segmentation method based on modified particle swarm optimization algorithm

The partitioning of an image into several constituent components is called image segmentation. Many approaches have been developed; one of them is the particle swarm optimization (PSO) algorithm, which is widely used. PSO algorithm is one of the most recent stochastic optimization strategies. In this article, a new efficient technique for the magnetic resonance imaging (MRI) brain images segmentation thematic based on PSO is proposed. The proposed algorithm presents an improved variant of PSO, which is particularly designed for optimal segmentation and it is called modified particle swarm optimization. The fitness function is used to evaluate all the particle swarm in order to arrange them in a descending order. The algorithm is evaluated by performance measures such as run time execution and the quality of the image after segmentation. The performance of the segmentation process is demonstrated by using a defined set of benchmark images and compared against conventional PSO, genetic algorithm, and PSO with Mahalanobis distance based segmentation methods. Then we applied our method on MRI brain image to determinate normal and pathological tissues. © 2013 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 23, 265–271, 2013     

Mode-pursuing sampling method for global optimization on expensive black-box functions

The presence of black-box functions in engineering design, which are usually computation-intensive, demands efficient global optimization methods. This article proposes a new global optimization method for black-box functions. The global optimization method is based on a novel mode-pursuing sampling method that systematically generates more sample points in the neighborhood of the function mode while statistically covering the entire search space. Quadratic regression is performed to detect the region containing the global optimum. The sampling and detection process iterates until the global optimum is obtained. Through intensive testing, this method is found to be effective, efficient, robust, and applicable to both continuous and discontinuous functions. It supports simultaneous computation and applies to both unconstrained and constrained optimization problems. Because it does not call any existing global optimization tool, it can be used as a standalone global optimization method for inexpensive problems as well. Limitations of the method are also identified and discussed.     

Constrained optimization by radial basis function interpolation for high-dimensional expensive black-box problems with infeasible initial points

This article develops two new algorithms for constrained expensive black-box optimization that use radial basis function surrogates for the objective and constraint functions. These algorithms are called COBRA and Extended ConstrLMSRBF and, unlike previous surrogate-based approaches, they can be used for high-dimensional problems where all initial points are infeasible. They both follow a two-phase approach where the first phase finds a feasible point while the second phase improves this feasible point. COBRA and Extended ConstrLMSRBF are compared with alternative methods on 20 test problems and on the MOPTA08 benchmark automotive problem (D.R. Jones, Presented at MOPTA 2008), which has 124 decision variables and 68 black-box inequality constraints. The alternatives include a sequential penalty derivative-free algorithm, a direct search method with kriging surrogates, and two multistart methods. Numerical results show that COBRA algorithms are competitive with Extended ConstrLMSRBF and they generally outperform the alternatives on the MOPTA08 problem and most of the test problems.     

A framework for parallelized efficient global optimization with application to vehicle crashworthiness optimization

This article presents a framework for simulation-based design optimization of computationally expensive problems, where economizing the generation of sample designs is highly desirable. One popular approach for such problems is efficient global optimization (EGO), where an initial set of design samples is used to construct a kriging model, which is then used to generate new ‘infill’ sample designs at regions of the search space where there is high expectancy of improvement. This article attempts to address one of the limitations of EGO, where generation of infill samples can become a difficult optimization problem in its own right, as well as allow the generation of multiple samples at a time in order to take advantage of parallel computing in the evaluation of the new samples. The proposed approach is tested on analytical functions, and then applied to the vehicle crashworthiness design of a full Geo Metro model undergoing frontal crash conditions.     

基于微粒群优化的模型参考自适应控制

针对复杂非线性对象提出了一种基于微粒群优化(PSO)的PID自适应控制方法.通过运用PSO算法对PID控制器参数进行在线调整,使模型参考自适应控制达到理想的控制效果.将该方法引入到连续搅拌反应釜这一复杂的非线性系统,仿真结果表明了该方法的良好性能.     

A global optimization algorithm for simulation-based problems via the extended DIRECT scheme

This article presents a global optimization algorithm via the extension of the DIviding RECTangles (DIRECT) scheme to handle problems with computationally expensive simulations efficiently. The new optimization strategy improves the regular partition scheme of DIRECT to a flexible irregular partition scheme in order to utilize information from irregular points. The metamodelling technique is introduced to work with the flexible partition scheme to speed up the convergence, which is meaningful for simulation-based problems. Comparative results on eight representative benchmark problems and an engineering application with some existing global optimization algorithms indicate that the proposed global optimization strategy is promising for simulation-based problems in terms of efficiency and accuracy.     

采用混合粒子群算法实现匹配追踪算法

针对匹配追踪信号稀疏分解的巨大计算量问题,在具有全局优化能力的粒子群算法基础上,提出了一种结合BFGS(Broyden、Fletcher、Goldfarb和Shanno)方法和变异操作的混合粒子群算法实现信号匹配追踪分解。利用BFGS方法增强了算法的局部开发能力,加快了信号特征提取速度;通过变异操作控制种群多样性以避免早熟收敛,增强了算法全局探测能力,提高了信号特征提取精度。通过与单一粒子群算法和遗传算法实现仿真信号匹配追踪分解的结果进行对比,证明了使用混合粒子群算法的匹配追踪分解能够快速准确提取信号特征参数。最后,将该算法应用于某内圈损伤轴承振动信号中的冲击特征提取,结果表明该算法在工程应用中具有一定的准确性和实用性。     

基于粒子群算法多目标优化液压支架四连杆

针对煤矿液压支架四连杆受力计算较为复杂,简化计算时易出现较大误差且稳定性较差的问题,提出从四连杆机构的空间受力出发并结合支架的运动轨迹,采用粒子群优化算法对四连杆机构展开优化研究。首先建立了四连杆优化模型,在优化模型中选取对结果影响较大的参数作为优化变量,以轨迹偏差、连杆长、连杆力之和作为目标函数,根据液压支架设计规范确定约束条件。然后使用粒子群算法对目标函数进行迭代求解并在求解过程中采用惩罚函数法解决优化模型中不等式约束问题。对比优化前后连杆的杆长、受力和稳定性数据,发现优化后的四连杆实现了轻量化,且受力较小,稳定性提高。研究结果对四连杆的设计有实际参考价值。     

Enhanced particle swarm optimization for size and shape optimization of truss structures

This article presents an enhanced particle swarm optimization (EPSO) algorithm for size and shape optimization of truss structures. The proposed EPSO introduces a particle categorization mechanism into the particle swarm optimization (PSO) to eliminate unnecessary structural analyses during the optimization process and improve the computational efficiency of the PSO-based structural optimization. The numerical investigation, including three benchmark truss optimization problems, examines the efficiency of the EPSO. The results demonstrate that the particle categorization mechanism greatly reduces the computational requirements of the PSO-based approaches while maintaining the original search capability of the algorithms in solving optimization problems with computationally cheap objective function and expensive constraints.     

A comparative study of expected improvement-assisted global optimization with different surrogates

Efficient global optimization (EGO) uses the surrogate uncertainty estimator called expected improvement (EI) to guide the selection of the next sampling candidates. Theoretically, any modelling methods can be integrated with the EI criterion. To improve the convergence ratio, a multi-surrogate efficient global optimization (MSEGO) was suggested. In practice, the EI-based optimization methods with different surrogates show widely divergent characteristics. Therefore, it is important to choose the most suitable algorithm for a certain problem. For this purpose, four single-surrogate efficient global optimizations (SSEGOs) and an MSEGO involving four surrogates are investigated. According to numerical tests, both the SSEGOs and the MSEGO are feasible for weak nonlinear problems. However, they are not robust for strong nonlinear problems, especially for multimodal and high-dimensional problems. Moreover, to investigate the feasibility of EGO in practice, a material identification benchmark is designed to demonstrate the performance of EGO methods. According to the tests in this study, the kriging EGO is generally the most robust method.