An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

On operators and search space topology in multi-objective flow shop scheduling

Multi-objective optimization using evolutionary algorithms identifies Pareto-optimal alternatives or their close approximation by means of a sequence of successive local improvement moves. While several successful applications to combinatorial optimization problems are known, studies of underlying problem structures are still scarce.     

Second-order optimality conditions for nondominated solutions of multiobjective programming with C 1,1 data

We examine new second-order necessary conditions and sufficient conditions which characterize nondominated solutions of a generalized constrained multiobjective programming problem. The vector-valued criterion function as well as constraint functions are supposed to be from the class C ^1,1. Second-order optimality conditions for local Pareto solutions are derived as a special case.     

A multiobjective evolutionary algorithm for approximating the efficient set

In this article, a new framework for evolutionary algorithms for approximating the efficient set of a multiobjective optimization (MOO) problem with continuous variables is presented. The algorithm is based on populations of variable size and exploits new elite preserving rules for selecting alternatives generated by mutation and recombination. Together with additional assumptions on the considered MOO problem and further specifications on the algorithm, theoretical results on the approximation quality such as convergence in probability and almost sure convergence are derived.     

NAUTILUS method: An interactive technique in multiobjective optimization based on the nadir point

Most interactive methods developed for solving multiobjective optimization problems sequentially generate Pareto optimal or nondominated vectors and the decision maker must always allow impairment in at least one objective function to get a new solution. The NAUTILUS method proposed is based on the assumptions that past experiences affect decision makers’ hopes and that people do not react symmetrically to gains and losses. Therefore, some decision makers may prefer to start from the worst possible objective values and to improve every objective step by step according to their preferences. In NAUTILUS, starting from the nadir point, a solution is obtained at each iteration which dominates the previous one. Although only the last solution will be Pareto optimal, the decision maker never looses sight of the Pareto optimal set, and the search is oriented so that (s)he progressively focusses on the preferred part of the Pareto optimal set. Each new solution is obtained by minimizing an achievement scalarizing function including preferences about desired improvements in objective function values. NAUTILUS is specially suitable for avoiding undesired anchoring effects, for example in negotiation support problems, or just as a means of finding an initial Pareto optimal solution for any interactive procedure. An illustrative example demonstrates how this new method iterates.     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

On the combinatorial structure of the permutation flow shop problem

In this paper we investigate the combinatorial structure of then/m/P/C _max permutation flow shop problem. To each solution (a permutation ofn elements) we introduce a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network we derive combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the considered problem.For several neighbourhood structures we calculate the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement.

---

Zusammenfassung In der vorliegenden Arbeit wird die kombinatorische Struktur desn/m/P/C _max Permutationsflußproblems untersucht. Zu jeder zulässigen Lösung, beschreibbar durch eine Permutation vonn Elementen, wird ein Netzplan eingeführt, der die Bearbeitungsreihenfolge der Operationen charakterisiert. Aufbauend auf einem eingeführten verallgemeinerten Abstand zwischen einer Permutation und einem Weg in einem Netzplan werden danach einige kombinatorische Eigenschaften bezüglich spezieller Nachbarschaftsstrukturen abgeleitet, die im Hinblick auf die Entwicklung von iterativen Heuristiken für das betrachtete Problem von Bedeutung sind. So werden u. a. für ausgewählte Nachbarschaftsstrukturen mittlere Mächtigkeiten reduzierter Nachbarschaften, bei denen jeder Nachbar eine notwendige Bedingung für eine Zielfunktionswertverbesserung erfüllt, hergeleitet.

     

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.     

On the potential balance among compulsory education outcomes through econometric and multiobjective programming analysis

This paper sheds new light on the relationship between inputs and outputs in the framework of the educational production function. In particular, it is geared at gaining a better understanding of which factors may be affected in order to achieve an optimal educational output level. With this objective in mind, we analyze teacher-based assessments (actual marks) in three different subjects using a multiobjective schema. For much of the analysis we use data from a recent (2010) Survey – ESOC10, linked with the results from an educational assessment program conducted among 11 and 15 year-old students and with the administrative records on teacher-based scores. Following the statistical and econometric analysis of these data, they are used to build a multiobjective mixed integer model. A reference point approach is used to determine the profile of, potentially, the most “successful and balanced” students in terms of educational outcomes. This kind of methodology in multiobjective programming allows generating “very balanced” solutions in terms of the objective values (subjects). Finally, a sensitivity analysis is used to determine policies that can be carried out in order to improve the performance levels of primary and secondary education students. Particularly, policy makers should be more concerned with the need to promote some cultural habits – such as reading –, from both the students’ and parents’ side. Additionally, policy efforts should be focused on making the vocational pathways available to Spanish youth more appealing, with the aim of taking advantage of the particular skills of students not succeeding in the academic track.     

Approximate dynamic programming via direct search in the space of value function approximations

This paper deals with approximate value iteration (AVI) algorithms applied to discounted dynamic programming (DP) problems. For a fixed control policy, the span semi-norm of the so-called Bellman residual is shown to be convex in the Banach space of candidate solutions to the DP problem. This fact motivates the introduction of an AVI algorithm with local search that seeks to minimize the span semi-norm of the Bellman residual in a convex value function approximation space. The novelty here is that the optimality of a point in the approximation architecture is characterized by means of convex optimization concepts and necessary and sufficient conditions to local optimality are derived. The procedure employs the classical AVI algorithm direction (Bellman residual) combined with a set of independent search directions, to improve the convergence rate. It has guaranteed convergence and satisfies, at least, the necessary optimality conditions over a prescribed set of directions. To illustrate the method, examples are presented that deal with a class of problems from the literature and a large state space queueing problem setting.     

On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given.     

An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.     

A geometrical analysis of the efficient outcome set in multiple objective convex programs with linear criterion functions

This article performs a geometrical analysis of the efficient outcome setY _E of a multiple objective convex program (MLC) with linear criterion functions. The analysis elucidates the facial structure ofY _E and of its pre-image, the efficient decision setX _E . The results show thatY _E often has a significantly-simpler structure thanX _E . For instance, although both sets are generally nonconvex and their maximal efficient faces are always in one-to-one correspondence, large numbers of extreme points and faces inX _E can map into non-facial subsets of faces inY _E , but not vice versa. Simple tests for the efficiency of faces in the decision and outcome sets are derived, and certain types of faces in the decision set are studied that are immune to a common phenomenon called collapsing. The results seem to indicate that significant computational benefits may potentially be derived if algorithms for problem (MLC) were to work directly with the outcome set of the problem to find points and faces ofY _E , rather than with the decision set.     

On the application of TRIMAP to problems with multiple decision makers

In this paper the potentialities of TRIMAP to provide decision support in multiobjective problems with multiple decision makers are exploited. TRIMAP is an interactive three-objective linear programming package which enables a progressive and selective learning of the nondominated solution set. The aim is to aid the opposing parties in exploring their own preferences and to explore the dynamic nature of the negotiation process.     

On the convexity of integrals of multivalued mappings: Applications in control theory

Using the notion of the local convexity index, we characterize in a quantitative way the local convexity of a set in then-dimensional Euclidean space, defined by an integral of a multivalued mapping. We estimate the rate of convergence of the conditional gradient method for solving an abstract optimization problem by means of the convexity index of the constraining set at the solution point. These results are applied to the qualitative analysis of the solutions of time-optimal and Mayer problems for linear control systems, as well as for estimating the convergence rate of algorithms solving these problems.