A Swarm Metaphor for Multiobjective Design Optimization

This paper presents a new optimization algorithm to solve multiobjective design optimization problems based on behavioral concepts similar to that of a real swarm. The individuals of a swarm update their flying direction through communication with their neighboring leaders with an aim to collectively attain a common goal. The success of the swarm is attributed to three fundamental processes: identification of a set of leaders, selection of a leader for information acquisition, and finally a meaningful information transfer scheme. The proposed algorithm mimics the above behavioral processes of a real swarm. The algorithm employs a multilevel sieve to generate a set of leaders, a probabilistic crowding radius-based strategy for leader selection and a simple generational operator for information transfer. Two test problems, one with a discontinuous Pareto front and the other with a multi-modal Pareto front is solved to illustrate the capabilities of the algorithm in handling mathematically complex problems. Three well-studied engineering design optimization problems (unconstrained and constrained problems with continuous and discrete variables) are solved to illustrate the efficiency and applicability of the algorithm for multiobjective design optimization. The results clearly indicate that the swarm algorithm is capable of generating an extended Pareto front, consisting of well spread Pareto points with significantly fewer function evaluations when compared to the nondominated sorting genetic algorithm (NSGA).     

Scatter search heuristic for least-cost design of water distribution networks

The optimization problems of water distribution networks are complex, multi-modal and discrete-variable problems that cannot be easily solved with conventional optimization algorithms. Heuristic algorithms such as genetic algorithms, simulated annealing, tabu search and ant colony optimization have been extensively employed over the last decade. This article proposed an optimization procedure based on the scatter search (SS) framework, which is also a heuristic algorithm, to obtain the least-cost designs of three well-known looped water distribution networks (two-loop, Hanoi and New York networks). The computational results obtained with the three benchmark instances indicate that SS is able to find solutions comparable to those provided by some of the most competitive algorithms published in the literature.     

The Statistical Filter Approach to Constrained Optimization

Abstract

Expensive black box systems arise in many engineering applications but can be difficult to optimize because their output functions may be complex, multi-modal, and difficult to understand. The task becomes even more challenging when the optimization is subject to multiple constraints and no derivative information is available. In this article, we combine response surface modeling and filter methods in order to solve problems of this nature. In employing a filter algorithm for solving constrained optimization problems, we establish a novel probabilistic metric for guiding the filter. Overall, this hybridization of statistical modeling and nonlinear programming efficiently utilizes both global and local search in order to quickly converge to a global solution to the constrained optimization problem. To demonstrate the effectiveness of the proposed methods, we perform numerical tests on a synthetic test problem, a problem from the literature, and a real-world hydrology computer experiment optimization problem.     

Cutting path optimization in CNC cutting processes using a two-step genetic algorithm

This paper deals with the problem of generating 2D cutting paths for a stock plate nested with a set of regular and/or irregular parts. The objective of the problem is to minimize the total non-productive traveling distance of a cutter starting from a known depot, then cutting all the given parts, and returning back to the depot. A cutting path consists of the depot and piercing points, each of which is to be specified for cutting a part. The cutting path optimization problem is shown to be formulated as a generalized version of the standard traveling salesman problem. To solve the problem, a two-step genetic algorithm combining global search for piercing point optimization and local search for part sequencing is proposed. Traditional genetic operators developed for continuous optimization problems are modified to effectively deal with the continuous nature of piercing-point positions. A series of computational results are provided to illustrate the validity of the proposed algorithm.     

基于粒子群与聚类的多目标优化算法

针对粒子群优化算法容易陷入局部最优的问题,提出了一种基于粒子群优化与分解聚类方法相结合的多目标优化算法。算法基于参考向量分解的方法,通过聚类优选粒子策略来更新全局最优解。首先,通过每条均匀分布的参考向量对粒子进行聚类操作,来促进粒子的多样性。从每个聚类中选择一个具有最小聚合函数适应度值的粒子,以平衡收敛性和多样性。动态更新全局最优解和个体最优解,引导种群均匀分布在帕累托前沿附近。通过仿真实验,与4种粒子群多目标优化算法进行对比。实验结果表明,提出的算法在27个选定的基准测试问题中获得了20个反世代距离(IGD)最优值。     

Two efficient algorithms for constructing almost even approximations of the Pareto front in multi-objective optimization problems

In this article, two algorithms are proposed for constructing almost even approximations of the Pareto front of multi-objective optimization problems. The first algorithm is a hybrid of the ε-constraint and Pascoletti–Serafini scalarization methods for solving bi-objective problems. The second is a modification of the successive Pareto optimization (SPO) algorithm for solving three-objective problems. In these algorithms, the MATLAB fmincon solver is used to solve single-objective optimization problems, which returns a local optimal solution. Some metrics are considered to evaluate the quality of approximations obtained by the suggested algorithms on six test problems, and their results are compared with other algorithms (normal constraint, weighted constraint, SPO, differential evolution, multi-objective evolutionary algorithm/decomposition–differential evolution, non-dominated sorting genetic algorithm-II and S-metric selection evolutionary multi-objective algorithm). Experimental results show that the proposed algorithms provide almost even approximations of the whole Pareto front, and better quality of approximation and CPU time compared with established algorithms.     

A hybrid evolutionary graph-based multi-objective algorithm for layout optimization of truss structures

In this paper a new graph-based evolutionary algorithm, gM-PAES, is proposed in order to solve the complex problem of truss layout multi-objective optimization. In this algorithm a graph-based genotype is employed as a modified version of Memetic Pareto Archive Evolution Strategy (M-PAES), a well-known hybrid multi-objective optimization algorithm, and consequently, new graph-based crossover and mutation operators perform as the solution generation tools in this algorithm. The genetic operators are designed in a way that helps the multi-objective optimizer to cover all parts of the true Pareto front in this specific problem. In the optimization process of the proposed algorithm, the local search part of gM-PAES is controlled adaptively in order to reduce the required computational effort and enhance its performance. In the last part of the paper, four numeric examples are presented to demonstrate the performance of the proposed algorithm. Results show that the proposed algorithm has great ability in producing a set of solutions which cover all parts of the true Pareto front.     

A multi-phase covering Pareto-optimal front method to multi-objective parallel machine scheduling

This paper considers the problem of parallel machine scheduling with sequence-dependent setup times to minimise both makespan and total earliness/tardiness in the due window. To tackle the problem considered, a multi-phase algorithm is proposed. The goal of the initial phase is to obtain a good approximation of the Pareto-front. In the second phase, to improve the Pareto-front, non-dominated solutions are unified to constitute a big population. In this phase, based on the local search in the Pareto space concept, three multi-objective hybrid metaheuristics are proposed. Covering the whole set of Pareto-optimal solutions is a desired task of multi-objective optimisation methods. So in the third phase, a new method using an e-constraint hybrid metaheuristic is proposed to cover the gaps between the non-dominated solutions and improve the Pareto-front. Appropriate combinations of multi-objective methods in various phases are considered to improve the total performance. The multi-phase algorithm iterates over a genetic algorithm in the first phase and three hybrid metaheuristics in the second and third phases. Experiments on the test problems with different structures show that the multi-phase method is a better tool to approximate the efficient set than the global archive sub-population genetic algorithm presented previously.     

Two-dimensional phase unwrapping using a hybrid genetic algorithm

A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.     

Efficient global optimization for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method

In many engineering optimization problems, the number of function evaluations is often very limited because of the computational cost to run one high-fidelity numerical simulation. Using a classic optimization algorithm, such as a derivative-based algorithm or an evolutionary algorithm, directly on a computational model is not suitable in this case. A common approach to addressing this challenge is to use black-box surrogate modelling techniques. The most popular surrogate-based optimization algorithm is the efficient global optimization (EGO) algorithm, which is an iterative sampling algorithm that adds one (or many) point(s) per iteration. This algorithm is often based on an infill sampling criterion, called expected improvement, which represents a trade-off between promising and uncertain areas. Many studies have shown the efficiency of EGO, particularly when the number of input variables is relatively low. However, its performance on high-dimensional problems is still poor since the Kriging models used are time-consuming to build. To deal with this issue, this article introduces a surrogate-based optimization method that is suited to high-dimensional problems. The method first uses the ‘locating the regional extreme’ criterion, which incorporates minimizing the surrogate model while also maximizing the expected improvement criterion. Then, it replaces the Kriging models by the KPLS(+K) models (Kriging combined with the partial least squares method), which are more suitable for high-dimensional problems. Finally, the proposed approach is validated by a comparison with alternative methods existing in the literature on some analytical functions and on 12-dimensional and 50-dimensional instances of the benchmark automotive problem ‘MOPTA08’.     

缓冲区容量约束下发动机混流装配线排序研究

为解决缓冲区容量约束下发动机混流装配排序问题,以关键部件消耗均匀化和最大完工时间最小化为目标,建立了优化数学模型,设计了一种多目标遗传算法,采用了混合交叉算子和启发式变异方法,并设计了基于帕累托分级和共享函数的适应度函数,将多目标遗传算法和多目标模拟退火算法的优化结果进行了比较。研究结果表明,多目标遗传算法在满意度和计算效率方面均优于多目标模拟退火算法,是一种有效的混流装配线排序问题求解算法。     

Efficient Pareto Frontier Exploration using Surrogate Approximations

In this paper we present an efficient and effective method of using surrogate approximations to explore the design space and capture the Pareto frontier during multiobjective optimization. The method employs design of experiments and metamodeling techniques (e.g., response surfaces and kriging models) to sample the design space, construct global approximations from the sample data, and quickly explore the design space to obtain the Pareto frontier without specifying weights for the objectives or using any optimization. To demonstrate the method, two mathematical example problems are presented. The results indicate that the proposed method is effective at capturing convex and concave Pareto frontiers even when discontinuities are present. After validating the method on the two mathematical examples, a design application involving the multiobjective optimization of a piezoelectric bimorph grasper is presented. The method facilitates multiobjective optimization by enabling us to efficiently and effectively obtain the Pareto frontier and identify candidate designs for the given design requirements.     

Optimization of ply angles in laminated composite structures by a hybrid,asynchronous, parallel evolutionary algorithm

An evolutionary algorithm approach aimed at the global optimization of ply angles in laminated composites is proposed. The algorithm is enriched by first-order local search and a niching strategy. Genetic variation operators are tailored to the special properties of ply angle optimization problems. Cyclic box-constraints are considered in the crossover, mutation, and niching operations. All experiments on three academic benchmark problems are able to identify a global optimal solution. Two case studies illustrate the applicability of the method on typical engineering problems.     

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.     

A problem space algorithm for single machine weighted tardiness problems

We propose a problem space genetic algorithm to solve single machine total weighted tardiness scheduling problems. The proposed algorithm utilizes global and time-dependent local dominance rules to improve the neighborhood structure of the search space. They are also a powerful exploitation (intensifying) tool since the global optimum is one of the local optimum solutions. Furthermore, the problem space search method significantly enhances the exploration (diversification) capability of the genetic algorithm. In summary, we can improve both solution quality and robustness over the other local search algorithms reported in the literature.     

Experiments with hybrid Bernstein global optimization algorithm for the OPF problem in power systems

This article presents an algorithm based on the Bernstein form of polynomials for solving the optimal power flow (OPF) problem in electrical power networks. The proposed algorithm combines local and global optimization methods and is therefore referred to as a ‘hybrid’ Bernstein algorithm in the context of this work. The proposed algorithm is a branch-and-bound procedure wherein a local search method is used to obtain a good upper bound on the global minimum at each branching node. Subsequently, the Bernstein form of polynomials is used to obtain a lower bound on the global minimum. The performance of the proposed algorithm is compared with the previously reported Bernstein algorithm to demonstrate its efficacy in terms of the chosen performance metrics. Furthermore, the proposed algorithm is tested on the OPF problem for several benchmark IEEE power system examples and its performance is compared with generic global optimization solvers such as BARON and COUENNE. The test results demonstrate that the hybrid Bernstein global optimization algorithm delivers satisfactory performance in terms of solution optimality.     

Multi-objective genetic algorithm for solving N-version program design problem

N-version programming (NVP) is a programming approach for constructing fault tolerant software systems. Generally, an optimization model utilized in NVP selects the optimal set of versions for each module to maximize the system reliability and to constrain the total cost to remain within a given budget. In such a model, while the number of versions included in the obtained solution is generally reduced, the budget restriction may be so rigid that it may fail to find the optimal solution. In order to ameliorate this problem, this paper proposes a novel bi-objective optimization model that maximizes the system reliability and minimizes the system total cost for designing N-version software systems. When solving multi-objective optimization problem, it is crucial to find Pareto solutions. It is, however, not easy to obtain them. In this paper, we propose a novel bi-objective optimization model that obtains many Pareto solutions efficiently.We formulate the optimal design problem of NVP as a bi-objective 0–1 nonlinear integer programming problem. In order to overcome this problem, we propose a Multi-objective genetic algorithm (MOGA), which is a powerful, though time-consuming, method to solve multi-objective optimization problems. When implementing genetic algorithm (GA), the use of an appropriate genetic representation scheme is one of the most important issues to obtain good performance. We employ random-key representation in our MOGA to find many Pareto solutions spaced as evenly as possible along the Pareto frontier. To pursue improve further performance, we introduce elitism, the Pareto-insertion and the Pareto-deletion operations based on distance between Pareto solutions in the selection process.The proposed MOGA obtains many Pareto solutions along the Pareto frontier evenly. The user of the MOGA can select the best compromise solution among the candidates by controlling the balance between the system reliability and the total cost.     

A method for simulation based optimization using radial basis functions

We propose an algorithm for the global optimization of expensive and noisy black box functions using a surrogate model based on radial basis functions (RBFs). A method for RBF-based approximation is introduced in order to handle noise. New points are selected to minimize the total model uncertainty weighted against the surrogate function value. The algorithm is extended to multiple objective functions by instead weighting against the distance to the surrogate Pareto front; it therefore constitutes the first algorithm for expensive, noisy and multiobjective problems in the literature. Numerical results on analytical test functions show promise in comparison to other (commercial) algorithms, as well as results from a simulation based optimization problem.     

A weight-based multiobjective immune algorithm: WBMOIA

A novel immune algorithm is suggested for finding Pareto-optimal solutions to multiobjective optimization problems based on opt-aiNET, the artificial immune system algorithm for multi-modal optimization. In the proposed algorithm, a randomly weighted sum of multiple objectives is used as a fitness function, and a local search algorithm is incorporated to facilitate the exploitation of the search space. Specifically, a new truncation algorithm with similar individuals (TASI) is proposed to preserve the diversity of the population. Also, a new selection operator is presented to create the new population based on TASI. Simulation results on seven standard problems (ZDT2, ZDT6, DEB, VNT, BNH, OSY and KIT) show that the proposed algorithm is able to find a much better spread of solutions and better convergence near the true Pareto-optimal front compared to the vector immune algorithm and the elitist non-dominated sorting genetic system.