On the Convergence of the Cross-Entropy Method

The cross-entropy method is a relatively new method for combinatorial optimization. The idea of this method came from the simulation field and then was successfully applied to different combinatorial optimization problems. The method consists of an iterative stochastic procedure that makes use of the importance sampling technique. In this paper we prove the asymptotical convergence of some modifications of the cross-entropy method.     

A redundancy detection algorithm for fuzzy stochastic multi-objective linear fractional programming problems

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic–possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.     

Multi-objective optimisation of positively homogeneous functions and an application in radiation therapy

Unconstrained multi-objective optimisation problems with p$p$ positively homogeneous objective functions are considered. We prove that such problems reduce to multi-objective optimisation problems with p−1$p-1$ objectives and a single equality constraint. Thus, problems with two objectives can be solved with standard single objective optimisation methods and, for problems with p>2$p>2$ objectives, we can compute infinitely many efficient solutions by solving a finite number of single objective problems. The proposed procedure is applied on radiotherapy for cancer treatment.     

An objective space cut and bound algorithm for convex multiplicative programmes

Multiplicative programming problems are global optimisation problems known to be NP-hard. In this paper we propose an objective space cut and bound algorithm for approximately solving convex multiplicative programming problems. This method is based on an objective space approximation algorithm for convex multi-objective programming problems. We show that this multi-objective optimisation algorithm can be changed into a cut and bound algorithm to solve convex multiplicative programming problems. We use an illustrative example to demonstrate the working of the algorithm. Computational experiments illustrate the superior performance of our algorithm compared to other methods from the literature.     

Cárnico-ICSPEA2—A metaheuristic co-evolutionary navigator for a complex co-evolutionary farming system

This paper introduces Cárnico-ICSPEA2, a metaheuristic co-evolutionary navigator designed by its end-user as an aid for the analysis and multi-objective optimisation of a beef cattle enterprise running on temperate pastures and fodder crops in Chalco, Mexico State, in the central plateau of Mexico. By combining simulation routines and a multi-objective evolutionary algorithm with a deterministic and stochastic framework, the software imitates the evolutionary behaviour of the system of interest, helping the farm manager to ‘navigate’ through his system’s dynamic phase space. The ultimate goal was to enhance the manager’s decision-making process and co-evolutionary skills, through an increased understanding of his system and the discovery of new, improved heuristics. This paper describes the numerical simulation and optimisation resulting from the application of Cárnico-ICSPEA2 to solve a specific multi-objective optimisation problem, along with implications for the management of the system of interest.     

METHOD OF CENTERS ALGORITHM FOR MULTI-OBJECTIVE PROGRAMMING PROBLEMS

In this paper, we consider a method of centers for solving multi-objective programming problems, where the objective functions involved are concave functions and the set of feasible points is convex. The algorithm is defined so that the sub-problems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the KKT conditions. Finally, we establish convergence of the proposed method of centers algorithm for solving multiobjective programming problems.     

The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems

In the last few years, a significant number of multi-objective metaheuristics have been proposed in the literature in order to address real-world problems. Local search methods play a major role in many of these metaheuristic procedures. In this paper, we adapt a recent and popular indicator-based selection method proposed by Zitzler and Künzli in 2004, in order to define a population-based multi-objective local search. The proposed algorithm is designed in order to be easily adaptable, parameter independent and to have a high convergence rate. In order to evaluate the capacity of our algorithm to reach these goals, a large part of the paper is dedicated to experiments. Three combinatorial optimisation problems are tested: a flow shop problem, a ring star problem and a nurse scheduling problem. The experiments show that our algorithm can be applied with success to different types of multi-objective optimisation problems and that it outperforms some classical metaheuristics. Furthermore, the parameter sensitivity analysis enables us to provide some useful guidelines about how to set the parameters.     

Pruned Pareto-optimal sets for the system redundancy allocation problem based on multiple prioritized objectives

In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e., weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality and single solution approaches.     

熵权DEA混合多目标评价方法研究

提高多目标决策问题评价结果的客观性、准确性,一直是决策科学研究的重要课题.结合熵权、DEA等数学方法对多目标决策问题进行研究,构造混合评价方法.首先通过构造熵权模型,获取主观权重;其次DEA的方法对多目标决策问题进行综合评价,得到问题的综合评价值,最后根据评价结果进行问题分析和判断.算例结果表明,方法能够应用于多目标决策问题,评价结果客观、准确.     

Optimisation of road vehicle passive suspension systems. Part 1. Optimisation algorithm and vehicle model

Numerous problems have in the past been experienced during the development of military vehicle suspension systems. In order to solve some of these problems a two-dimensional multi-body vehicle dynamics simulation model has been developed for computer implementation. This model is linked to a mathematical optimisation algorithm in order to enable the optimisation of vehicle design parameters through the minimisation of a well defined objective function. In part 1 of this paper the concept of multi-disciplinary design optimisation is discussed. This is followed by the presentation of the up to six degrees of freedom vehicle model developed for this study, and a discussion of the specific gradient-based optimisation algorithm selected for the optimisation. In particular the derivation of the set of second-order differential equations, describing the acceleration of the different solid bodies of the vehicle model, is presented. In order to perform the optimisation of the non-linear suspension component characteristics, a six piece-wise continuous and linear approximation is used which is also described in this paper. Part 2 of this study will outline the simulation programme and the qualification of the programme. It will also present a typical case study where the proposed optimisation methodology is applied to improve the damper characteristics of a specific vehicle.     

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.     

The development of a multi-objective Tabu Search algorithm for continuous optimisation problems

While there have been many adaptations of some of the more popular meta-heuristics for continuous multi-objective optimisation problems, Tabu Search has received relatively little attention, despite its suitability and effectiveness on a number of real-world design optimisation problems. In this paper we present an adaptation of a single-objective Tabu Search algorithm for multiple objectives. Further, inspired by path relinking strategies common in discrete optimisation problems, we enhance our algorithm to allow it to handle problems with large numbers of design variables. This is achieved by a novel parameter selection strategy that, unlike a full parametric analysis, avoids the use of objective function evaluations, thus keeping the overall computational cost of the procedure to a minimum. We assess the performance of our two Tabu Search variants on a range of standard test functions and compare it to a leading multi-objective Genetic Algorithm, NSGA-II. The path relinking-inspired parameter selection scheme gives a clear performance improvement over the basic multi-objective Tabu Search adaptation and both variants perform comparably with the NSGA-II.     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

Modelling and optimisation for sustainable development policy assessment

Earlier work on sustainable development devised a policy assessment tool that was based on a static optimisation formulation. Key ingredients in sustainable development problems are the presence of random effects and the conflict between different objectives. To accommodate these, the earlier formulation was strongly stochastic and was posed in a multi-objective framework. The purpose of this paper is to consider the extension of the work to a formulation that deploys dynamic optimisation. In particular it is the aim here to use simulations based on a large scale model to derive dynamic rather than static representations, to integrate these into the optimisation scheme and to assess the benefits.     

Robustness of mechanical systems against uncertainties

In this paper, one can propose a method which takes into account the propagation of uncertainties in the finite element models in a multi-objective optimization procedure. This method is based on the coupling of stochastic response surface method (SRSM) and a genetic algorithm provided with a new robustness criterion. The SRSM is based on the use of stochastic finite element method (SFEM) via the use of the polynomial chaos expansion (PC). Thus, one can avoid the use of Monte Carlo simulation (MCS) whose costs become prohibitive in the optimization problems, especially when the finite element models are large and have a considerable number of design parameters.The objective of this study is on one hand to quantify efficiently the effects of these uncertainties on the responses variability or the cost functions which one wishes to optimize and on the other hand, to calculate solutions which are both optimal and robust with respect to the uncertainties of design parameters.In order to study the propagation of input uncertainties on the mechanical structure responses and the robust multi-objective optimization with respect to these uncertainty, two numerical examples were simulated. The results which relate to the quantification of the uncertainty effects on the responses variability were compared with those obtained by the reference method (REF) using MCS and with those of the deterministic response surfaces methodology (RSM).In the same way, the robust multi-objective optimization results resulting from the SRSM method were compared with those obtained by the direct optimization considered as reference (REF) and with RSM methodology.The SRSM method application to the response variability study and the robust multi-objective optimization gave convincing results.     

Approximating the Pareto optimal set using a reduced set of objective functions

Real-world applications of multi-objective optimization often involve numerous objective functions. But while such problems are in general computationally intractable, it is seldom necessary to determine the Pareto optimal set exactly. A significantly smaller computational burden thus motivates the loss of precision if the size of the loss can be estimated. We describe a method for finding an optimal reduction of the set of objectives yielding a smaller problem whose Pareto optimal set w.r.t. a discrete subset of the decision space is as close as possible to that of the original set of objectives. Utilizing a new characterization of Pareto optimality and presuming a finite decision space, we derive a program whose solution represents an optimal reduction. We also propose an approximate, computationally less demanding formulation which utilizes correlations between the objectives and separates into two parts. Numerical results from an industrial instance concerning the configuration of heavy-duty trucks are also reported, demonstrating the usefulness of the method developed. The results show that multi-objective optimization problems can be significantly simplified with an induced error which can be measured.     

凸二次整数规划的随机水平值逼近算法

对凸二次整数极小化问题提出了一种随机水平值逼近算法,该算法应用了重点取样技术,并利用极小化相对熵的思想来更新取样密度．对算法的渐近收敛性进行了证明,给出了数值实验的结果．     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Multi-objective time–cost trade-off in dynamic PERT networks using an interactive approach

We develop a multi-objective model for the time–cost trade-off problem in a dynamic PERT network using an interactive approach. The activity durations are exponentially distributed random variables and the new projects are generated according to a renewal process and share the same facilities. Thus, these projects cannot be analyzed independently. This dynamic PERT network is represented as a network of queues, where the service times represent the durations of the corresponding activities and the arrival stream to each node follows a renewal process. At the first stage, we transform the dynamic PERT network into a proper stochastic network and then compute the project completion time distribution by constructing a continuous-time Markov chain. At the second stage, the time–cost trade-off problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. Then, the STEM method is used to solve a discrete-time approximation of the original problem. Finally, the proposed methodology is extended to the generalized Erlang activity durations.