Hybrid multi-objective Bayesian estimation of distribution algorithm: a comparative analysis for the multi-objective knapsack problem

Nowadays, a number of metaheuristics have been developed for efficiently solving multi-objective optimization problems. Estimation of distribution algorithms are a special class of metaheuristic that intensively apply probabilistic modeling and, as well as local search methods, are widely used to make the search more efficient. In this paper, we apply a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA) in multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and the configuration parameters of an embedded local search (LS). We analyze the benefits of the online configuration of LS parameters by comparing the proposed approach with LS off-line versions using instances of the multi-objective knapsack problem with two to five and eight objectives. HMOBEDA is also compared with five advanced evolutionary methods using the same instances. Results show that HMOBEDA outperforms the other approaches including those with off-line configuration. HMOBEDA not only provides the best value for hypervolume indicator and IGD metric in most of the cases, but it also computes a very diverse solutions set close to the estimated Pareto front.     

MB-GNG: Addressing drawbacks in multi-objective optimization estimation of distribution algorithms

We examine the model-building issue related to multi-objective estimation of distribution algorithms (MOEDAs) and show that some of their, as yet overlooked, characteristics render most current MOEDAs unviable when addressing optimization problems with many objectives. We propose a novel model-building growing neural gas (MB-GNG) network that is specially devised for properly dealing with that issue and therefore yields a better performance. Experiments are conducted in order to show from an empirical point of view the advantages of the new algorithm.     

Portfolio optimization with an envelope-based multi-objective evolutionary algorithm

The problem of portfolio selection is a standard problem in financial engineering and has received a lot of attention in recent decades. Classical mean–variance portfolio selection aims at simultaneously maximizing the expected return of the portfolio and minimizing portfolio variance. In the case of linear constraints, the problem can be solved efficiently by parametric quadratic programming (i.e., variants of Markowitz’ critical line algorithm). However, there are many real-world constraints that lead to a non-convex search space, e.g., cardinality constraints which limit the number of different assets in a portfolio, or minimum buy-in thresholds. As a consequence, the efficient approaches for the convex problem can no longer be applied, and new solutions are needed.In this paper, we propose to integrate an active set algorithm optimized for portfolio selection into a multi-objective evolutionary algorithm (MOEA). The idea is to let the MOEA come up with some convex subsets of the set of all feasible portfolios, solve a critical line algorithm for each subset, and then merge the partial solutions to form the solution of the original non-convex problem. We show that the resulting envelope-based MOEA significantly outperforms existing MOEAs.     

Hybrid immune algorithm with Lamarckian local search for multi-objective optimization

Lamarckian learning has been introduced into evolutionary computation as local search mechanism. The relevant research topic, memetic computation, has received significant amount of interests. In this study, a novel Lamarckian learning strategy is designed for improving the Nondominated Neighbor Immune Algorithm, a novel hybrid multi-objective optimization algorithm, Multi-objective Lamarckian Immune Algorithm (MLIA), is proposed. The Lamarckian learning performs a greedy search which proceeds towards the goal along the direction obtained by Tchebycheff approach and generates the improved progenies or improved decision vectors, so single individual will be optimized locally and the newcomers yield an enhanced exploitation around the nondominated individuals in less-crowded regions of the current trade-off front. Simulation results based on twelve benchmark problems show that MLIA outperforms the original immune algorithm and NSGA-II in approximating Pareto-optimal front in most of the test problems. When compared with the state of the art algorithm MOEA/D, MLIA shows better performance in terms of the coverage of two sets metric, although it is laggard in the hypervolume metric.     

An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.     

Multi-strategy ensemble evolutionary algorithm for dynamic multi-objective optimization

Dynamic optimization and multi-objective optimization have separately gained increasing attention from the research community during the last decade. However, few studies have been reported on dynamic multi-objective optimization (dMO) and scarce effective dMO methods have been proposed. In this paper, we fulfill these gabs by developing new dMO test problems and new effective dMO algorithm. In the newly designed dMO problems, Pareto-optimal decision values (i.e., Pareto-optimal solutions: POS) or both POS and Pareto-optimal objective values (i.e., Pareto-optimal front: POF) change with time. A new multi-strategy ensemble multi-objective evolutionary algorithm (MS-MOEA) is proposed to tackle the challenges of dMO. In MS-MOEA, the convergence speed is accelerated by the new offspring creating mechanism powered by adaptive genetic and differential operators (GDM); a Gaussian mutation operator is employed to cope with premature convergence; a memory like strategy is proposed to achieve better starting population when a change takes place. In order to show the advantages of the proposed algorithm, we experimentally compare MS-MOEA with several algorithms equipped with traditional restart strategy. It is suggested that such a multi-strategy ensemble approach is promising for dealing with dMO problems.     

Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest and evaluate an optimization procedure which specializes in solving a wide variety of optimization problems. The proposed algorithm is designed as a generic multi-objective, multi-optima optimizer. Care has been taken while designing the algorithm such that it automatically degenerates to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-optimal problems, single-objective multi-optima problems and multi-objective uni-optimal problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems chosen from the literature. Because of its efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.     

Stochastic comparison algorithm for continuous optimization with estimation

The problem of stochastic optimization for arbitrary objective functions presents a dual challenge. First, one needs to repeatedly estimate the objective function; when no closed-form expression is available, this is only possible through simulation. Second, one has to face the possibility of determining local, rather than global, optima. In this paper, we show how the stochastic comparison approach recently proposed in Ref. 1 for discrete optimization can be used in continuous optimization. We prove that the continuous stochastic comparison algorithm converges to an -neighborhood of the global optimum for any >0. Several applications of this approach to problems with different features are provided and compared to simulated annealing and gradient descent algorithms.This work was supported in part by the National Science Foundation under Grants EID-92-12122 and ECS-88-01912, and by a Grant from United Technologies/Otis Elevator Company.     

Improving the non-dominated sorting genetic algorithm using a gene-therapy method for multi-objective optimization

The non-dominate sorting genetic algorithmic-II (NSGA-II) is an effective algorithm for finding Pareto-optimal front for multi-objective optimization problems. To further enhance the advantage of the NSGA-II, this study proposes an evaluative-NSGA-II (E-NSGA-II) in which a novel gene-therapy method incorporates into the crossover operation to retain superior schema patterns in evolutionary population and enhance its solution capability. The merit of each select gene in a crossover chromosome is estimated by exchanging the therapeutic genes in both mating chromosomes and observing their fitness differentiation. Hence, the evaluative crossover operation can generate effective genomes based on the gene merit without explicitly analyzing the solution space. Experiments for nine unconstrained multi-objective benchmarks and four constrained problems show that E-NSGA-II can find Pareto-optimal solutions in all test cases with better convergence and diversity qualities than several existing algorithms.     

A new multi-objective discrete robust optimization algorithm for engineering design

This paper proposes a novel multi-objective discrete robust optimization (MODRO) algorithm for design of engineering structures involving uncertainties. In the present MODRO procedure, grey relational analysis (GRA), coupled with principal component analysis (PCA), was used as a multicriteria decision making model for converting multiple conflicting objectives into one unified cost function. The optimization process was iterated using the successive Taguchi approach to avoid the limitation that the conventional Taguchi method fails to deal with a large number of design variables and design levels. The proposed method was first verified by a mathematical benchmark example and a ten-bar truss design problem; and then it was applied to a more sophisticated design case of full scale vehicle structure for crashworthiness criteria. The results showed that the algorithm is able to achieve an optimal design in a fairly efficient manner attributable to its integration with the multicriteria decision making model. Note that the optimal design can be directly used in practical applications without further design selection. In addition, it was found that the optimum is close to the corresponding Pareto frontier generated from the other approaches, such as the non-dominated sorting genetic algorithm II (NSGA-II), but can be more robust as a result of introduction of the Taguchi method. Due to its independence on metamodeling techniques, the proposed algorithm could be fairly promising for engineering design problems of high dimensionality.     

A new multi-objective self-organizing optimization algorithm (MOSOA) for spatial optimization problems

Spatial planning is an important and complex activity. It includes land use planning and resource allocation as basic components. An abundance of papers can be found in the literature related to each one of these two aspects separately. On the contrary, a much smaller number of research reports deal with both aspects simultaneously. This paper presents an innovative evolutionary algorithm for treating combined land use planning and resource allocation problems. The new algorithm performs optimization on a cellular automaton domain, applying suitable transition rules on the individual neighbourhoods. The optimization process is multi-objective, based on non-domination criteria and self-organizing. It produces a Pareto front thus offering an advantage to the decision maker, in comparison to methods based on weighted-sum objective functions. Moreover, the present multi-objective self-organizing algorithm (MOSOA) can handle both local and global spatial constraints. A combined land use and water allocation problem is treated, in order to illustrate the cellular automaton optimization approach. Water is allocated after pumping from an aquifer, thus contributing a nonlinearity to the objective function. The problem is bi-objective aiming at (a) the minimization of soil and groundwater pollution and (b) the maximization of economic profit. An ecological and a socioeconomic constraint are imposed: (a) Groundwater levels at selected places are kept above prescribed thresholds. (b) Land use quota is predefined. MOSOA is compared to a standard multi-objective genetic algorithm and is shown to yield better results both with respect to the Pareto front and to the degree of compactness. The latter is a highly desirable feature of a land use pattern. In the land use literature, compactness is part of the objective function or of the constraints. In contrast, the present approach renders compactness as an emergent result.     

A green train scheduling model and fuzzy multi-objective optimization algorithm

Train scheduling model is traditionally formulated to minimize the energy consumption for reducing the operation cost. As the European Union formulates the first carbon emission trading scheme in the world, it is necessary to extend the operation cost to include the expenses for buying/selling the carbon emission allowances. In this paper, we propose a multi-objective train scheduling model by minimizing the energy and carbon emission cost as well as the total passenger-time, and named it as green train scheduling model. For obtaining a non-dominated timetable which has equal satisfactory degree on both objectives, we apply a fuzzy multi-objective optimization algorithm to solve the model. Finally, we perform two numerical examples to illustrate the efficiency of the proposed model and solution methodology.     

A multi-objective memetic algorithm based on decomposition for big optimization problems

When solving multi-objective optimization problems (MOPs) with big data, traditional multi-objective evolutionary algorithms (MOEAs) meet challenges because they demand high computational costs that cannot satisfy the demands of online data processing involving optimization. The gradient heuristic optimization methods show great potential in solving large scale numerical optimization problems with acceptable computational costs. However, some intrinsic limitations make them unsuitable for searching for the Pareto fronts. It is believed that the combination of these two types of methods can deal with big MOPs with less computational cost. The main contribution of this paper is that a multi-objective memetic algorithm based on decomposition for big optimization problems (MOMA/D-BigOpt) is proposed and a gradient-based local search operator is embedded in MOMA/D-BigOpt. In the experiments, MOMA/D-BigOpt is tested on the multi-objective big optimization problems with thousands of variables. We also combine the local search operator with other widely used MOEAs to verify its effectiveness. The experimental results show that the proposed algorithm outperforms MOEAs without the gradient heuristic local search operator.     

An efficient Differential Evolution based algorithm for solving multi-objective optimization problems

In the present study, a modified variant of Differential Evolution (DE) algorithm for solving multi-objective optimization problems is presented. The proposed algorithm, named Multi-Objective Differential Evolution Algorithm (MODEA) utilizes the advantages of Opposition-Based Learning for generating an initial population of potential candidates and the concept of random localization in mutation step. Finally, it introduces a new selection mechanism for generating a well distributed Pareto optimal front. The performance of proposed algorithm is investigated on a set of nine bi-objective and five tri-objective benchmark test functions and the results are compared with some recently modified versions of DE for MOPs and some other Multi Objective Evolutionary Algorithms (MOEAs). The empirical analysis of the numerical results shows the efficiency of the proposed algorithm.     

A new orthogonal evolutionary algorithm based on decomposition for multi-objective optimization

The diversity of solutions is very important for multi-objective evolutionary algorithms to deal with multi-objective optimization problems (MOPs). In order to achieve the goal, a new orthogonal evolutionary algorithm based on objective space decomposition (OEA/D) is proposed in this paper. To be specific, the objective space of an MOP is firstly decomposed into a set of sub-regions via a set of direction vectors, and OEA/D maintains the diversity of solutions by making each sub-region have a solution to the maximum extent. Also, the quantization orthogonal crossover (QOX) is used to enhance the search ability of OEA/D. Experimental studies have been conducted to compare this proposed algorithm with classic MOEA/D, NSGAII, NICA and D2MOPSO. Simulation results on six multi-objective benchmark functions show that the proposed algorithm is able to obtain better diversity and more evenly distributed Pareto fronts than other four algorithms.     

FEMOEA: a fast and efficient multi-objective evolutionary algorithm

A multi-objective evolutionary algorithm which can be applied to many nonlinear multi-objective optimization problems is proposed. Its aim is to quickly obtain a fixed size Pareto-front approximation. It adapts ideas from different multi-objective evolutionary algorithms, but also incorporates new devices. In particular, the search in the feasible region is carried out on promising areas (hyperspheres) determined by a radius value, which decreases as the optimization procedure evolves. This mechanism helps to maintain a balance between exploration and exploitation of the search space. Additionally, a new local search method which accelerates the convergence of the population towards the Pareto-front, has been incorporated. It is an extension of the local optimizer SASS and improves a given solution along a search direction (no gradient information is used). Finally, a termination criterion has also been proposed, which stops the algorithm if the distances between the Pareto-front approximations provided by the algorithm in three consecutive iterations are smaller than a given tolerance. To know how far two of those sets are from each other, a modification of the well-known Hausdorff distance is proposed. In order to analyze the algorithm performance, it has been compared to the reference algorithms NSGA-II and SPEA2 and the state-of-the-art algorithms MOEA/D and SMS-EMOA. Several quality indicators have been considered, namely, hypervolume, average distance, additive epsilon indicator, spread and spacing. According to the computational tests performed, the new algorithm, named FEMOEA, outperforms the other algorithms.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

A multi-objective optimization evolutionary algorithm incorporating preference information based on fuzzy logic

A multi-objective optimization evolutionary algorithm incorporating preference information interactively is proposed. A new nine grade evaluation method is used to quantify the linguistic preferences expressed by the decision maker (DM) so as to reduce his/her cognitive overload. When comparing individuals, the classical Pareto dominance relation is commonly used, but it has difficulty in dealing with problems involving large numbers of objectives in which it gives an unmanageable and large set of Pareto optimal solutions. In order to overcome this limitation, a new outranking relation called “strength superior” which is based on the preference information is constructed via a fuzzy inference system to help the algorithm find a few solutions located in the preferred regions, and the graphical user interface is used to realize the interaction between the DM and the algorithm. The computational complexity of the proposed algorithm is analyzed theoretically, and its ability to handle preference information is validated through simulation. The influence of parameters on the performance of the algorithm is discussed and comparisons to another preference guided multi-objective evolutionary algorithm indicate that the proposed algorithm is effective in solving high dimensional optimization problems.     

Stochastic multi-objective optimization of a viscoelastic composite plate

A layered viscoelastic rectangular plate fiber-reinforced in three directions and compressed in one direction has been studied. Two plate properties, namely, the critical compressive stress _cr and the coefficient of linear thermal expansion _xx, were analyzed by varying two parameters of the reinforcement geometry. The properties of the plate are determined by the properties of the composite components, eight of which are considered stochastic. The problem was solved for two variants: _xx min or _xx max. The calculations were carried out for three time intervals: t = 0, 27 days, and . For t = 0, the region of t real plate properties is determined with isolines for design parameters. Multi-objective compromise solutions are given for all three times t for each of the two variants along with the parameters of the property scatter ellipses.Presented at the Ninth International Conference on Mechanics of Composite Materials, Riga, October, 1995.Translated from Mekhanika Kompozitnykh Materialov, Vol. 31, No. 3, pp. 363–369, May–June, 1995.     

An estimation of distribution algorithm for nurse scheduling

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (EDA) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (GAs) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The EDA is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.