A new mechanism to maintain diversity in multi-objective metaheuristics

In this article, a new mechanism to spread the solutions generated by a multi-objective evolutionary algorithm is proposed. This approach is based on the use of stripes that are applied in objective function space and is independent of the search engine adopted. Additionally, it overcomes some of the drawbacks of other previous proposals such as the ?-dominance method. In order to validate the proposed approach, it is coupled to a multi-objective particle swarm optimizer and its performance is assessed with respect to that of state-of-the-art algorithms, using standard test problems and performance measures taken from the specialized literature. The results indicate that the proposed approach is a viable diversity maintenance mechanism that can be incorporated to any multi-objective metaheuristic used for multi-objective optimization.     

A preference-based multi-objective evolutionary algorithm R-NSGA-II with stochastic local search

Incorporation of a decision maker’s preferences into multi-objective evolutionary algorithms has become a relevant trend during the last decade, and several preference-based evolutionary algorithms have been proposed in the literature. Our research is focused on improvement of a well-known preference-based evolutionary algorithm R-NSGA-II by incorporating a local search strategy based on a single agent stochastic approach. The proposed memetic algorithm has been experimentally evaluated by solving a set of well-known multi-objective optimization benchmark problems. It has been experimentally shown that incorporation of the local search strategy has a positive impact to the quality of the algorithm in the sense of the precision and distribution evenness of approximation.     

Resolution approach for multi-objective problems with uncertain demands

The job-shop scheduling problem (JSP) is one of the hardest problems (NP-complete problem). In a lot of cases, the combination of goals and resource exponentially increases search space. The objective of resolution of such a problem is generally, to maximize the production with a lower cost and makespan. In this paper, we explain how to modify the objective function of genetic algorithms to treat the multi-objective problem and to generate a set of diversified “optimal” solutions in order to help decision maker. We are interested in one of the problems occurring in the production workshops where the list of demands is split into firm (certain) jobs and predicted jobs. One wishes to maximize the produced quantity, while minimizing as well as possible the makespan and the production costs. Genetic algorithms are used to find the scheduling solution of the firm jobs because they are well adapted to the treatment of the multi-objective optimization problems. The predicted jobs will be inserted in the real solutions (given by genetic algorithms). The solutions proposed by our approach are compared to the lower bound of the cost and makespan in order to prove the quality and robustness of our proposed approach.     

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.     

Swarm approach based on gravity for optimizing energy savings in grid systems

Execution time optimization is one of the most important objectives to accomplish for experiments launched on grid environments. However, the computing community is becoming more conscious about energy savings, seeking their optimization. In this work, both execution time and energy consumption are optimized through two swarm and multi-objective algorithms based on both physics and biology fields. On the one hand, multi-objective gravitational search algorithm (MOGSA) is inspired by the gravity forces between the planet masses. On the other hand, Multi-Objective Firefly Algorithm is based on the light attraction between the fireflies. These swarm algorithms are compared with the standard multi-objective algorithm non-dominated sorting genetic algorithm II to study their efficiency as multi-objective algorithms. Moreover, the best algorithm proposed, MOGSA, is compared with MOHEFT (a multi-objective version of one of the most-used algorithms in workflow scheduling, HEFT), and also with two real grid schedulers: Workload Management System and deadline budget constraint. Results show the superior performance of MOGSA regarding the others.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these 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.     

Utilizing expected improvement and generalized data envelopment analysis in multi-objective genetic algorithms

Meta-heuristic methods such as genetic algorithms (GA) and particle swarm optimization (PSO) have been extended to multi-objective optimization problems, and have been observed to be useful for finding good approximate Pareto optimal solutions. In order to improve the convergence and the diversity in the search of solutions using meta-heuristic methods, this paper suggests a new method to make offspring by utilizing the expected improvement (EI) and generalized data envelopment analysis (GDEA). In addition, the effectiveness of the proposed method will be investigated through several numerical examples in comparison with the conventional multi-objective GA and PSO methods.     

Bi-objective hypervolume-based Pareto optimization

The search for the best trade-off solutions with respect to several criteria (also called the Pareto set) is the main approach pursued in multi-objective optimization when no additional preferences are associated to the objectives. This problem is known to be compliant with the maximization of the hypervolume (or S-metric), consisting in the Lebesgue measure of the dominated region covered by a set of solutions in the objective space, and bounded by a reference point. While several variants of population-based metaheuristics like evolutionary algorithms address formulations maximizing the hypervolume, the use of gradient-based algorithms for this task has been largely neglected in the literature. Therefore, this paper proposes to solve bi-objective problems by hypervolume maximization through a sequential quadratic programming algorithm. After theoretical developments including the analytical expression of the sensitivities of the hypervolume expressed as functions of the gradient of the objectives, the method is applied to six benchmark test cases, demonstrating the efficiency of the proposed method in comparison with a scalarization of the objectives, and with a state-of-the-art multi-objective genetic algorithm. This method is believed to provide an interesting alternative to metaheuristics when the gradients of the objective functions are available at a limited additional cost, a situation which is encountered in versatile applications, for instance with adjoint methods implemented in computational solid mechanics or fluid dynamics.     

Convergence of stochastic search algorithms to finite size pareto set approximations

In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.      

灾情巡视问题的蚁群两目标优化算法研究

分析目前灾情巡视问题求解方法存在的缺陷,归纳出灾情巡视问题两目标优化模型.针对灾情巡视问题模型特点,引入蚁群算法和多目标优化理论,提出两个灾情巡视问题的蚁群两目标优化算法:算法1将灾情巡视问题的道路网络转化为完全图,增加m-1个(m为巡视组数)虚拟巡视起点,将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,然后使用蚁群算法和多目标优化理论进行迭代求解.算法2使用一只蚂蚁寻找一个子回路,m个子回路构成一个灾情巡视可行方案,采用罚函数法和多目标优化理论构建增广两目标优化评价函数,使用g组,共g×m只蚂蚁共同协作来发现灾情巡视问题的最优解.算法特点:①算法1将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,可以充分利用已有蚁群算法求解单旅行商问题的研究成果;②两个算法引入蚁群算法,提高了算法效率;③两个算法克服目前灾情巡视问题的求解方法不严密性缺陷;④两目标优化算法可以为用户提供多个满足约束条件的Pareto组合解,扩大了用户选择范围,增强了算法的适用性.算法测试表明:灾情巡视问题的蚁群两目标优化算法是完全可行和有效的.     

Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

Divide-and-conquer memetic algorithm for online multi-objective test paper generation

Online test paper generation (Online-TPG) generates a test paper automatically online according to user specification based on multiple assessment criteria, and the generated test paper can then be attempted online by user. Online-TPG is challenging as it is a multi-objective optimization problem that is NP-hard, and it is also required to satisfy the online generation requirement. In this paper, we propose an efficient multi-objective optimization approach based on the divide-and-conquer memetic algorithm (DAC-MA) for Online-TPG. Instead of solving the multi-objective constraints simultaneously, the set of constraints is divided into two subsets of relevant constraints, which can then be solved separately and effectively by evolutionary computation and local search of DAC-MA. The empirical performance results have shown that the proposed approach has outperformed other TPG techniques in terms of runtime efficiency and paper quality.     

ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation

This paper investigates the use of multi-objective methods to guide the search when solving single-objective optimisation problems with genetic algorithms. Using the job shop scheduling and travelling salesman problems as examples, experiments demonstrate that the use of helper-objectives (additional objectives guiding the search) significantly improves the average performance of a standard GA. The helper-objectives guide the search towards solutions containing good building blocks and help the algorithm escape local optima. The experiments reveal that the approach works if the number of simultaneously used helper-objectives is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically. The experiments reveal that for the majority of problem instances studied, the proposed approach significantly outperforms a traditional GA.The experiments also demonstrate that controlling the proportion of non-dominated solutions in the population is very important when using helper-objectives, since the presence of too many non-dominated solutions removes the selection pressure in the algorithm.     

A mixture experiments multi-objective hyper-heuristic

This paper proposes a hyper-heuristic that combines genetic algorithm with mixture experiments to solve multi-objective optimisation problems. At every iteration, the proposed algorithm combines the selection criterion (rank indicator) of a number of well-established evolutionary algorithms including NSGA-II, SPEA2 and two versions of IBEA. Each indicator is called according to an associated probability calculated and updated during the search by means of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the maximum (probability distribution) of the surface represented by this model, we also find a good algorithm parameterisation. The design of mixture experiments approach allowed the authors to identify and exploit synergies between the different rank indicators at the different stages of the search. This is demonstrated by our experimental results in which the proposed algorithm compared favourably against other well-established algorithms.     

Inverse multi-objective combinatorial optimization

Inverse multi-objective combinatorial optimization consists of finding a minimal adjustment of the objective functions coefficients such that a given set of feasible solutions becomes efficient. An algorithm is proposed for rendering a given feasible solution into an efficient one. This is a simplified version of the inverse problem when the cardinality of the set is equal to one. The adjustment is measured by the Chebyshev distance. It is shown how to build an optimal adjustment in linear time based on this distance, and why it is right to perform a binary search for determining the optimal distance. These results led us to develop an approach based on the resolution of mixed-integer linear programs. A second approach based on a branch-and-bound is proposed to handle any distance function that can be linearized. Finally, the initial inverse problem is solved by a cutting plane algorithm.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.