A single front genetic algorithm for parallel multi-objective optimization in dynamic environments

This paper proposes a new parallel evolutionary procedure to solve multi-objective dynamic optimization problems along with some measures to evaluate multi-objective optimization in dynamic environments. These dynamic optimization problems appear in quite different real-world applications with actual socio-economic relevance. In these applications, the objective functions, the constraints, and hence, also the solutions, can change over time and usually demand to be solved online whilst the size of the changes is unknown. Although parallel processing could be very useful in these problems to meet the solution quality requirements and constraints, to date, not many parallel approaches have been reported in the literature. Taking this into account, we introduce a multi-objective optimization procedure for dynamic problems that are based on PSFGA, a parallel evolutionary algorithm previously proposed by us for multi-objective optimization. It uses an island model where a process divides the population among the remaining processes and allows the communication and coordination among the subpopulations in the different islands. The proposed algorithm makes an exclusive use of non-dominating individuals for the selection and variation operator and applies a crowding mechanism to maintain the diversity and the distribution of the solutions in the Pareto front. We also propose a model to understand the benefits of parallel processing in multi-objective problems and the speedup figures obtained in our experiments.     

Communication latency tolerant parallel algorithm for particle swarm optimization

Particle swarm optimization (PSO) algorithm is a population-based algorithm for finding the optimal solution. Because of its simplicity in implementation and fewer adjustable parameters compared to the other global optimization algorithms, PSO is gaining attention in solving complex and large scale problems. However, PSO often requires long execution time to solve those problems. This paper proposes a parallel PSO algorithm, called delayed exchange parallelization, which improves performance of PSO on distributed environment by hiding communication latency efficiently. By overlapping communication with computation, the proposed algorithm extracts parallelism inherent in PSO. The performance of our proposed parallel PSO algorithm was evaluated using several applications. The results of evaluation showed that the proposed parallel algorithm drastically improved the performance of PSO, especially in high-latency network environment.     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

基于杂合机制的免疫遗传算法在动态问题中的应用

针对遗传算法在求解动态问题时存在多样性缺失,无法快速响应环境变化的问题,提出一种基于杂合子机制的免疫遗传算法．该算法借鉴免疫系统中多样性与记忆机理,从保持等位基因多样性出发,在免疫变异中引入杂合映射机制,使种群能够探索更大的解空间．同时,通过引入记忆策略,使算法迅速跟踪最优解变化轨迹．该方法在动态０-１优化问题的求解中取得了较好的效果．     

并行多目标遗传算法在控制系统优化中的应用

为了提高复杂控制系统设计问题中的效率,提出了一种基于主从模型的并行多目标遗传算法的优化器模型。主进程进行各类遗传操作和最优排序操作,所有进程都进行目标函数值和约束函数值的运算操作,并采用动态负载平衡策略。将该优化器应用在飞行器控制系统设计中,显示出了该算法的优良效果。     

Interweaving genetic programming and genetic algorithm for structural and parametric optimization in adaptive platform product customization

An adaptive product platform offers high customizability for generating feasible product variants for customer requirements. Customization takes place not only to product platform structure but also to its relevant parameters. Structural and parametric optimization processes are interwoven with each other to achieve the total optimality. This paper presents an evolutionary method dealing with interwoven structural and parametric optimization of adaptive platform product customization. The method combines genetic programming and genetic algorithm for handling structural and parametric optimization, respectively. Efficient genetic representation and operation schemes are carefully adapted. While designing these schemes, features specific to structural and parameter customization are considered for the simplification of platform product management. The experimental results show that the performance of the proposed algorithm outperforms that of the tandem evolutionary algorithm in which a genetic algorithm for parametric optimization is totally nested in a genetic programming for structural optimization.     

A permutation-based dual genetic algorithm for dynamic optimization problems

Adaptation to dynamic optimization problems is currently receiving growing interest as one of the most important applications of genetic algorithms. Inspired by dualism and dominance in nature, genetic algorithms with the dualism mechanism have been applied for several dynamic problems with binary encoding. This paper investigates the idea of dualism for combinatorial optimization problems in dynamic environments, which are also extensively implemented in the real-world. A new variation of the GA, called the permutation-based dual genetic algorithm (PBDGA), is presented. Within this GA, two schemes based on the characters of the permutation in group theory are introduced: a partial-dualism scheme motivated by a new multi-attribute dualism mechanism and a learning scheme. Based on the dynamic test environments constructed by stationary benchmark problems, experiments are carried out to validate the proposed PBDGA. The experimental results show the efficiency of PBDGA in dynamic environments.     

基于自适应递阶遗传算法的神经网络优化策略

基于递阶结构的遗传算法可以同时对多层前向神经网络进行结构优化和权重求解。与基本的遗传算法相比，这种算法不仅在权重训练方面更加快速稳定，而且能在学习过程中确定网络的拓扑结构，具有较高的学习效率，而在遗传过程中采用自适应的交叉和变异概率能有效加快遗传速度和避免早熟现象的出现。     

A self-organizing random immigrants genetic algorithm for dynamic optimization problems

In this paper a genetic algorithm is proposed where the worst individual and individuals with indices close to its index are replaced in every generation by randomly generated individuals for dynamic optimization problems. In the proposed genetic algorithm, the replacement of an individual can affect other individuals in a chain reaction. The new individuals are preserved in a subpopulation which is defined by the number of individuals created in the current chain reaction. If the values of fitness are similar, as is the case with small diversity, one single replacement can affect a large number of individuals in the population. This simple approach can take the system to a self-organizing behavior, which can be useful to control the diversity level of the population and hence allows the genetic algorithm to escape from local optima once the problem changes due to the dynamics.     

What is ahead for parallel computing

With the industry-wide switch to multicore and manycore architectures, parallel computing has become the only venue in sight for continued growth in application performance. In order for the performance of an application to grow with future generations of hardware, a significant portion of its computation must be done with scalable parallel algorithms. It is therefore important to develop and deploy as many scalable parallel algorithms as possible. This paper takes a critical look at the major challenges involved in the development of scalable parallel algorithms and points to needs for compiler tool innovations to help address these challenges.     

A novel parallel hybrid intelligence optimization algorithm for a function approximation problem

A novel parallel hybrid intelligence optimization algorithm (PHIOA) is proposed based on combining the merits of particle swarm optimization with genetic algorithms. The PHIOA uses the ideas of selection, crossover and mutation from genetic algorithms (GAs) and the update velocity and situation of particle swarm optimization (PSO) under the independence of PSO and GAs. The proposed algorithm divides the individuals into two equation groups according to their fitness values. The subgroup of the top fitness values is evolved by GAs and the other subgroup is evolved by the PSO algorithm. The optimal number is selected as a global optimum at every circulation which shows better results than both PSO and GAs, then improves the overall performance of the algorithm. The PHIOA is used to optimize the structure and parameters of the fuzzy neural network. Finally, the experimental results have demonstrated the superiority of the proposed PHIOA to search the global optimal solution. The PHIOA can improve the error accuracy while speeding up the convergence process, and effectively avoid the premature convergence to compare with the existing methods.     

基于锦标赛选择遗传算法的随机微粒群算法

以保证全局收敛的随机微粒群算法SPSO为基础。提出了一种改进的随机微粒群算法-GAT-SPSO。该方法是在SPSO的进化过程中．以锦标赛选择机制下的遗传算法所产生的最优个体来代替SPSO中停止的微粒,参与下一代的群体进化。通过时三个多峰的测试函数进行仿真,其结果表明：在搜索空间维数相同的情况下,GAT-SPSO的收敛率厦收敛速度均大大优于SPSO。     

一种基于GPU加速的细粒度并行蚁群算法

为改善蚁群算法对大规模旅行商问题的求解性能,提出一种基于图形处理器(GPU)加速的细粒度并行蚁群算法.将并行蚁群算法求解过程转化为统一计算设备架构的线程块并行执行过程,使得蚁群算法在GPU中加速执行.实验结果表明,该算法能提高全局搜索能力,增大细粒度并行蚁群算法的蚂蚁规模,从而提高了算法的运算速度.     

动态环境下的免疫优化

生物免疫系统面对复杂的外部环境能够产生相应抗体,快速消除对肌体的威胁,在变化的环境中体现出强大的优化能力和自适应能力。论文借鉴免疫反应机理,提出一种用于求解动态环境下函数优化问题的免疫算法。仿真结果表明该算法全局搜索能力强、优化速度快、能够较好地处理动态环境中的优化问题。     

A distributed hierarchical genetic algorithm for efficient optimization and pattern matching

In this paper we propose a new approach in genetic algorithm called distributed hierarchical genetic algorithm (DHGA) for optimization and pattern matching. It is eventually a hybrid technique combining the advantages of both distributed and hierarchical processes in exploring the search space. The search is initially distributed over the space and then in each subspace the algorithm works in a hierarchical way. The entire space is essentially partitioned into a number of subspaces depending on the dimensionality of the space. This is done in order to spread the search process more evenly over the whole space. In each subspace the genetic algorithm is employed for searching and the search process advances from one hypercube to a neighboring hypercube hierarchically depending on the convergence status of the population and the solution obtained so far. The dimension of the hypercube and the resolution of the search space are altered with iterations. Thus the search process passes through variable resolution (coarse-to-fine) search space. Both analytical and empirical studies have been carried out to evaluate the performance between DHGA and distributed conventional GA (DCGA) for different function optimization problems. Further, the performance of the algorithms is demonstrated on problems like pattern matching and object matching with edge map.     

混合混沌优化方法及其在非线性规划问题中的应用

结合逐次优化、禁忌搜索和变尺度混沌优化方法的优点,提出了一种混合混沌优化方法。该方法具有逐次优化算法的隐性并行性和收敛性,禁忌搜索的智能性和变尺度混沌优化方法的快速性。仿真计算表明,该方法具有实现简单,优化效率高,鲁棒性强等特点。     

Dynamic optimal reactive power dispatch based on parallel particle swarm optimization algorithm

In this paper, Message Passing Interface (MPI) based parallel computation and particle swarm optimization (PSO) algorithm are combined to form the parallel particle swarm optimization (PPSO) method for solving the dynamic optimal reactive power dispatch (DORPD) problem in power systems. In the proposed algorithm, the DORPD problem is divided into smaller ones, which can be carried out concurrently by multi-processors. This method is evaluated on a group of IEEE power systems test cases with time-varying loads in which the control of the generator terminal voltages, tap position of transformers and reactive power sources are involved to minimize the transmission power loss and the costs of adjusting the control devices. The simulation results demonstrate the accuracy of the PPSO algorithm and its capability of greatly reducing the runtimes of the DORPD programs.     

Orthogonal parallel MCMC methods for sampling and optimization

Monte Carlo (MC) methods are widely used for Bayesian inference and optimization in statistics, signal processing and machine learning. A well-known class of MC methods are Markov Chain Monte Carlo (MCMC) algorithms. In order to foster better exploration of the state space, specially in high-dimensional applications, several schemes employing multiple parallel MCMC chains have been recently introduced. In this work, we describe a novel parallel interacting MCMC scheme, called orthogonal MCMC (O-MCMC), where a set of “vertical” parallel MCMC chains share information using some “horizontal” MCMC techniques working on the entire population of current states. More specifically, the vertical chains are led by random-walk proposals, whereas the horizontal MCMC techniques employ independent proposals, thus allowing an efficient combination of global exploration and local approximation. The interaction is contained in these horizontal iterations. Within the analysis of different implementations of O-MCMC, novel schemes in order to reduce the overall computational cost of parallel Multiple Try Metropolis (MTM) chains are also presented. Furthermore, a modified version of O-MCMC for optimization is provided by considering parallel Simulated Annealing (SA) algorithms. Numerical results show the advantages of the proposed sampling scheme in terms of efficiency in the estimation, as well as robustness in terms of independence with respect to initial values and the choice of the parameters.     

An adaptive single-point algorithm for global numerical optimization

This paper describes a novel algorithm for numerical optimization, called Simple Adaptive Climbing (SAC). SAC is a simple efficient single-point approach that does not require a careful fine-tunning of its two parameters. SAC algorithm shares many similarities with local optimization heuristics, such as random walk, gradient descent, and hill-climbing. SAC has a restarting mechanism, and a powerful adaptive mutation process that resembles the one used in Differential Evolution. The algorithms SAC is capable of performing global unconstrained optimization efficiently in high dimensional test functions. This paper shows results on 15 well-known unconstrained problems. Test results confirm that SAC is competitive against state-of-the-art approaches such as micro-Particle Swarm Optimization, CMA-ES or Simple Adaptive Differential Evolution.     

Polynomial genetic programming for response surface modeling Part 2: adaptive approximate models with probabilistic optimization problems

This is the second in a series of papers. The first deals with polynomial genetic programming (PGP) adopting the directional derivative-based smoothing (DDBS) method, while in this paper, an adaptive approximate model (AAM) based on PGP is presented with the partial interpolation strategy (PIS). The AAM is sequentially modified in such a way that the quality of fitting in the region of interest where an optimum point may exist can be gradually enhanced, and accordingly the size of the learning set is gradually enlarged. If the AAM uses a smooth high-order polynomial with an interpolative capability, it becomes more and more difficult for PGP to obtain smooth polynomials, whose size should be larger than or equal to the number of the samples, because the order of the polynomial becomes unnecessarily high according to the increase in its size. The PIS can avoid this problem by selecting samples belonging to the region of interest and interpolating only those samples. Other samples are treated as elements of the extended data set (EDS). Also, the PGP system adopts a multiple-population approach in order to simultaneously handle several constraints. The PGP system with the variable-fidelity response surface method is applied to reliability-based optimization (RBO) problems in order to significantly cut the high computational cost of RBO. The AAMs based on PGP are responsible for fitting probabilistic constraints and the cost function while the variable-fidelity response surface method is responsible for fitting limit state equations. Three numerical examples are presented to show the performance of the AAM based on PGP.