Reasoning with sorted-pareto dominance and other qualitative and partially ordered preferences in soft constraints

In decision making problems where we need to choose a particular decision or alternative from a set of possible choices, we often have some preferences which determine if we prefer one decision over another. When these preferences give us an ordering on the decisions that is complete, then it is easy to choose the best or one of the best decisions. However it often occurs that the preferences relation is partially ordered, and we have no best decision. In this thesis, we look at what happens when we have such a partial order over a set of decisions, in particular when we have multiple orderings on a set of decisions, and we present a framework for qualitative decision making. We look at the different natural notions of optimal decision that occur in this framework, which gives us different optimality classes, and we examine the relationships between these classes. We then look in particular at a qualitative preference relation called Sorted-Pareto Dominance, which is an extension of Pareto Dominance, and we give a semantics for this relation as one that is compatible with any order-preserving mapping of an ordinal preference scale to a numerical one. We apply Sorted-Pareto dominance to a Soft Constraints setting, where we solve problems in which the soft constraints associate qualitative preferences to decisions in a decision problem. We also examine the Sorted-Pareto dominance relation in the context of our qualitative decision making framework, looking at the relevant optimality classes for the Sorted-Pareto case, which gives us classes of decisions that are necessarily optimal, and optimal for some choice of mapping of an ordinal scale to a quantitative one. We provide some empirical analysis of Sorted-Pareto constraints problems and examine the optimality classes that result.

Improving Collaborative Filtering Based Recommender Systems Using Pareto Dominance

Los sistemas de recomendación son un tipo de solución al problema de sobrecarga de información que sufren los usuarios de los sitios web en los que se pueden votar ciertos artículos. El sistema de recomendación de filtrado colaborativo es considerado como el método con más éxito debido a que sus recomendaciones se hacen basándose en los votos de usuarios similares a un usuario activo. Sin embargo, el método de filtrado de colaboración tradicional selecciona usuarios insuficientemente representativos como vecinos de cada usuario activo. Esto significa que las recomendaciones hechas a posteriori no son lo suficientemente precisas. El método propuesto en esta tesis realiza un pre-filtrado del proceso, mediante el uso de dominancia de Pareto, que elimina los usuarios menos representativos del proceso de selección k-vecino y mantiene los más prometedores. Los resultados de los experimentos realizados en MovieLens y Netflix muestran una mejora significativa en todas las medidas de calidad estudiadas en la aplicación del método propuesto. ABSTRACTRecommender systems are a type of solution to the information overload problem suffered by users of websites on which they can rate certain items. The Collaborative Filtering Recommender System is considered to be the most successful approach as it make its recommendations based on votes of users similar to an active user. Nevertheless, the traditional collaborative filtering method selects insufficiently representative users as neighbors of each active user. This means that the recommendations made a posteriori are not precise enough. The method proposed in this thesis performs a pre-filtering process, by using Pareto dominance, which eliminates the less representative users from the k-neighbor selection process and keeps the most promising ones. The results from the experiments performed on Movielens and Netflix show a significant improvement in all the quality measures studied on applying the proposed method.

Pareto Dominance of Deferred Acceptance through Early Decision

An early decision market is governed by rules that allow each student to apply to (at most) one college and require the student to attend this college if admitted. This market is ubiquitous in college admissions in the United States. We model this market as an extensive-form game of perfect information and study a refinement of subgame perfect equilibrium (SPE) that induces undominated Nash equilibria in every subgame (SPUE). Our main result shows that this game can be used to define a decentralized matching mechanism that weakly Pareto dominates student-proposing deferred acceptance.

Pareto Dominance of Deferred Acceptance through Early Decision

An early decision market is governed by rules that allow each student to apply to (at most) one college and require the student to attend this college if admitted. This market is ubiquitous in college admissions in the United States. We model this market as an extensive-form game of perfect information and study a refinement of subgame perfect equilibrium (SPE) that induces undominated Nash equilibria in every subgame (SPUE). Our main result shows that this game can be used to define a decentralized matching mechanism that weakly Pareto dominates student-proposing deferred acceptance.

Coupling hybrid-game strategies with particle swarm optimisation for multi-objective high lift systems design optimisation

This paper investigates the High Lift System (HLS) application of complex aerodynamic design problem using Particle Swarm Optimisation (PSO) coupled to Game strategies. Two types of optimization methods are used; the first method is a standard PSO based on Pareto dominance and the second method hybridises PSO with a well-known Nash Game strategies named Hybrid-PSO. These optimization techniques are coupled to a pre/post processor GiD providing unstructured meshes during the optimisation procedure and a transonic analysis software PUMI. The computational efficiency and quality design obtained by PSO and Hybrid-PSO are compared. The numerical results for the multi-objective HLS design optimisation clearly shows the benefits of hybridising a PSO with the Nash game and makes promising the above methodology for solving other more complex multi-physics optimisation problems in Aeronautics.

Paretian Quasi-Orders: Two Agents.

We characterize Paretian quasi-orders in the two-agent continuous case.

Um estudo algorítmico para otimização do plano de tratamento da radioterapia conformal

This work performs an algorithmic study of optimization of a conformal radiotherapy plan treatment. Initially we show: an overview about cancer, radiotherapy and the physics of interaction of ionizing radiation with matery. A proposal for optimization of a plan of treatment in radiotherapy is developed in a systematic way. We show the paradigm of multicriteria problem, the concept of Pareto optimum and Pareto dominance. A generic optimization model for radioterapic treatment is proposed. We construct the input of the model, estimate the dose given by the radiation using the dose matrix, and show the objective function for the model. The complexity of optimization models in radiotherapy treatment is typically NP which justifyis the use of heuristic methods. We propose three distinct methods: MOGA, MOSA e MOTS. The project of these three metaheuristic procedures is shown. For each procedures follows: a brief motivation, the algorithm itself and the method for tuning its parameters. The three method are applied to a concrete case and we confront their performances. Finally it is analyzed for each method: the quality of the Pareto sets, some solutions and the respective Pareto curves

Regularized model learning in EDAs for continuous and multi-objective optimization

Probabilistic modeling is the de�ning characteristic of estimation of distribution algorithms (EDAs) which determines their behavior and performance in optimization. Regularization is a well-known statistical technique used for obtaining an improved model by reducing the generalization error of estimation, especially in high-dimensional problems. `1-regularization is a type of this technique with the appealing variable selection property which results in sparse model estimations. In this thesis, we study the use of regularization techniques for model learning in EDAs. Several methods for regularized model estimation in continuous domains based on a Gaussian distribution assumption are presented, and analyzed from di�erent aspects when used for optimization in a high-dimensional setting, where the population size of EDA has a logarithmic scale with respect to the number of variables. The optimization results obtained for a number of continuous problems with an increasing number of variables show that the proposed EDA based on regularized model estimation performs a more robust optimization, and is able to achieve signi�cantly better results for larger dimensions than other Gaussian-based EDAs. We also propose a method for learning a marginally factorized Gaussian Markov random �eld model using regularization techniques and a clustering algorithm. The experimental results show notable optimization performance on continuous additively decomposable problems when using this model estimation method. Our study also covers multi-objective optimization and we propose joint probabilistic modeling of variables and objectives in EDAs based on Bayesian networks, speci�cally models inspired from multi-dimensional Bayesian network classi�ers. It is shown that with this approach to modeling, two new types of relationships are encoded in the estimated models in addition to the variable relationships captured in other EDAs: objectivevariable and objective-objective relationships. An extensive experimental study shows the e�ectiveness of this approach for multi- and many-objective optimization. With the proposed joint variable-objective modeling, in addition to the Pareto set approximation, the algorithm is also able to obtain an estimation of the multi-objective problem structure. Finally, the study of multi-objective optimization based on joint probabilistic modeling is extended to noisy domains, where the noise in objective values is represented by intervals. A new version of the Pareto dominance relation for ordering the solutions in these problems, namely �-degree Pareto dominance, is introduced and its properties are analyzed. We show that the ranking methods based on this dominance relation can result in competitive performance of EDAs with respect to the quality of the approximated Pareto sets. This dominance relation is then used together with a method for joint probabilistic modeling based on `1-regularization for multi-objective feature subset selection in classi�cation, where six di�erent measures of accuracy are considered as objectives with interval values. The individual assessment of the proposed joint probabilistic modeling and solution ranking methods on datasets with small-medium dimensionality, when using two di�erent Bayesian classi�ers, shows that comparable or better Pareto sets of feature subsets are approximated in comparison to standard methods.

Interval-based ranking in noisy evolutionary multiobjective optimization

As one of the most competitive approaches to multi-objective optimization, evolutionary algorithms have been shown to obtain very good results for many realworld multi-objective problems. One of the issues that can affect the performance of these algorithms is the uncertainty in the quality of the solutions which is usually represented with the noise in the objective values. Therefore, handling noisy objectives in evolutionary multi-objective optimization algorithms becomes very important and is gaining more attention in recent years. In this paper we present ?-degree Pareto dominance relation for ordering the solutions in multi-objective optimization when the values of the objective functions are given as intervals. Based on this dominance relation, we propose an adaptation of the non-dominated sorting algorithm for ranking the solutions. This ranking method is then used in a standardmulti-objective evolutionary algorithm and a recently proposed novel multi-objective estimation of distribution algorithm based on joint variable-objective probabilistic modeling, and applied to a set of multi-objective problems with different levels of independent noise. The experimental results show that the use of the proposed method for solution ranking allows to approximate Pareto sets which are considerably better than those obtained when using the dominance probability-based ranking method, which is one of the main methods for noise handling in multi-objective optimization.

SOP: Parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems

This paper presents a parallel surrogate-based global optimization method for computationally expensive objective functions that is more effective for larger numbers of processors. To reach this goal, we integrated concepts from multi-objective optimization and tabu search into, single objective, surrogate optimization. Our proposed derivative-free algorithm, called SOP, uses non-dominated sorting of points for which the expensive function has been previously evaluated. The two objectives are the expensive function value of the point and the minimum distance of the point to previously evaluated points. Based on the results of non-dominated sorting, P points from the sorted fronts are selected as centers from which many candidate points are generated by random perturbations. Based on surrogate approximation, the best candidate point is subsequently selected for expensive evaluation for each of the P centers, with simultaneous computation on P processors. Centers that previously did not generate good solutions are tabu with a given tenure. We show almost sure convergence of this algorithm under some conditions. The performance of SOP is compared with two RBF based methods. The test results show that SOP is an efficient method that can reduce time required to find a good near optimal solution. In a number of cases the efficiency of SOP is so good that SOP with 8 processors found an accurate answer in less wall-clock time than the other algorithms did with 32 processors.

Aboveground community and species-specific plant biomass from the Jena Experiment (Dominance Experiment, year 2006)

This data set contains aboveground community plant biomass (Sown plant community, Weed plant community, Dead plant material, and Unidentified plant material; all measured in biomass as dry weight) and species-specific biomass from the sown species of the dominance experiment plots of a large grassland biodiversity experiment (the Jena Experiment; see further details below). In the dominance experiment, 206 grassland plots of 3.5 x 3.5 m were established from a pool of 9 plant species that can be dominant in semi-natural grassland communities of the study region. In May 2002, varying numbers of plant species from this species pool were sown into the plots to create a gradient of plant species richness (1, 2, 3, 4, 6, and 9 species). Plots were maintained by bi-annual weeding and mowing. Aboveground community biomass was harvested twice in May and August 2006 on all experimental plots of the dominance experiment. This was done by clipping the vegetation at 3 cm above ground in two rectangles of 0.2 x 0.5 m per experimental plot. The location of these rectangles was assigned by random selection of coordinates within the central area of the plots (excluding an outer edge of 50cm). The positions of the rectangles within plots were identical for all plots. The harvested biomass was sorted into categories: individual species for the sown plant species, weed plant species (species not sown at the particular plot), detached dead plant material, and remaining plant material that could not be assigned to any category. All biomass was dried to constant weight (70°C, >= 48 h) and weighed. Sown plant community biomass was calculated as the sum of the biomass of the individual sown species. The mean of both samples per plot and the individual measurements are provided in the data file. Overall, analyses of the community biomass data have identified species richness and the presence of particular species as an important driver of a positive biodiversity-productivity relationship.

Aboveground community and species-specific plant biomass from the Jena Experiment (Dominance Experiment, year 2003)

This data set contains aboveground community plant biomass (Sown plant community, Weed plant community, and Dead plant material; all measured in biomass as dry weight) and species-specific biomass from the sown species of the dominance experiment plots of a large grassland biodiversity experiment (the Jena Experiment; see further details below). In the dominance experiment, 206 grassland plots of 3.5 x 3.5 m were established from a pool of 9 plant species that can be dominant in semi-natural grassland communities of the study region. In May 2002, varying numbers of plant species from this species pool were sown into the plots to create a gradient of plant species richness (1, 2, 3, 4, 6, and 9 species). Plots were maintained by bi-annual weeding and mowing. Aboveground community biomass was harvested twice in May and August 2003 on all experimental plots of the dominance experiment. This was done by clipping the vegetation at 3 cm above ground in two rectangles of 0.2 x 0.5 m per experimental plot. The location of these rectangles was assigned by random selection of coordinates within the central area of the plots (excluding an outer edge of 50cm). The positions of the rectangles within plots were identical for all plots. The harvested biomass was sorted into categories: individual species for the sown plant species, weed plant species (species not sown at the particular plot), detached dead plant material, and remaining plant material that could not be assigned to any category. All biomass was dried to constant weight (70°C, >= 48 h) and weighed. Sown plant community biomass was calculated as the sum of the biomass of the individual sown species. The mean of both samples per plot and the individual measurements are provided in the data file. Overall, analyses of the community biomass data have identified species richness and the presence of particular species as an important driver of a positive biodiversity-productivity relationship.

Aboveground community and species-specific plant biomass from the Jena Experiment (Dominance Experiment, year 2007)

This data set contains aboveground community plant biomass (Sown plant community, Weed plant community, Dead plant material, and Unidentified plant material; all measured in biomass as dry weight) and species-specific biomass from the sown species of the dominance experiment plots of a large grassland biodiversity experiment (the Jena Experiment; see further details below). In the dominance experiment, 206 grassland plots of 3.5 x 3.5 m were established from a pool of 9 plant species that can be dominant in semi-natural grassland communities of the study region. In May 2002, varying numbers of plant species from this species pool were sown into the plots to create a gradient of plant species richness (1, 2, 3, 4, 6, and 9 species). Plots were maintained by bi-annual weeding and mowing. Aboveground community biomass was harvested twice in May and August 2007 on all experimental plots of the dominance experiment. This was done by clipping the vegetation at 3 cm above ground in two rectangles of 0.2 x 0.5 m per experimental plot. The location of these rectangles was assigned by random selection of coordinates within the central area of the plots (excluding an outer edge of 50cm). The positions of the rectangles within plots were identical for all plots. The harvested biomass was sorted into categories: individual species for the sown plant species, weed plant species (species not sown at the particular plot), detached dead plant material, and remaining plant material that could not be assigned to any category. All biomass was dried to constant weight (70°C, >= 48 h) and weighed. Sown plant community biomass was calculated as the sum of the biomass of the individual sown species. The mean of both samples per plot and the individual measurements are provided in the data file. Overall, analyses of the community biomass data have identified species richness and the presence of particular species as an important driver of a positive biodiversity-productivity relationship.

Aboveground community and species-specific plant biomass from the Jena Experiment (Dominance Experiment, time series since 2002)

This data set comprises a time series of aboveground community plant biomass (Sown plant community, Weed plant community, Dead plant material, and Unidentified plant material; all measured in biomass as dry weight) and species-specific biomass from the sown species of the dominance experiment plots of a large grassland biodiversity experiment (the Jena Experiment; see further details below). In the dominance experiment, 206 grassland plots of 3.5 x 3.5 m were established from a pool of 9 species that can be dominant in semi-natural grassland communities of the study region. In May 2002, varying numbers of plant species from this species pool were sown into the plots to create a gradient of plant species richness (1, 2, 3, 4, 6, and 9 species). Plots were maintained by bi-annual weeding and mowing. Aboveground community biomass was harvested twice a year, generally in May and August (in 2002 only once in September) on all experimental plots of the dominance experiment. This was done by clipping the vegetation at 3 cm above ground in two rectangles of 0.2 x 0.5 m per experimental plot. The location of these rectangles was assigned by random selection of new coordinates every year within the central area of the plots (excluding an outer edge of 50cm). The positions of the rectangles within plots were identical for all plots. The harvested biomass was sorted into categories: individual species for the sown plant species, weed plant species (species not sown at the particular plot), detached dead plant material, and remaining plant material that could not be assigned to any category. Biomass was dried to constant weight (70°C, >= 48 h) and weighed. Sown plant community biomass was calculated as the sum of the biomass of the individual sown species. The mean of both samples per plot and the individual measurements are provided in the data file. Overall, analyses of the community biomass data have identified species richness and the presence of particular species as an important driver of a positive biodiversity-productivity relationship.

Aboveground community and species-specific plant biomass from the Jena Experiment (Dominance Experiment, year 2002)

This data set contains aboveground community biomass (Sown plant community, Weed plant community, and Unidentified plant material; all measured in biomass as dry weight) and species-specific biomass from the sown species of the dominance experiment plots of a large grassland biodiversity experiment (the Jena Experiment; see further details below). In the dominance experiment, 206 grassland plots of 3.5 x 3.5 m were established from a pool of 9 plant species that can be dominant in semi-natural grassland communities of the study region. In May 2002, varying numbers of plant species from this species pool were sown into the plots to create a gradient of plant species richness (1, 2, 3, 4, 6, and 9 species). Plots were maintained by bi-annual weeding and mowing. Aboveground community biomass was harvested in September 2002 on all experimental plots of the dominance experiment. This was done by clipping the vegetation at 3 cm above ground in two rectangles of 0.2 x 0.5 m per experimental plot. The location of these rectangles was assigned by random selection of coordinates within the central area of the plots (excluding an outer edge of 50cm). The positions of the rectangles within plots were identical for all plots. The harvested biomass was sorted into categories: individual species for the sown plant species, weed plant species (species not sown at the particular plot), detached dead plant material, and remaining plant material that could not be assigned to any category. The fresh mass of all biomass was determined and only biomass of one sample per plot could be dried to constant weight (70°C, >= 48 h). Dry mass of the other sample was calculated from the ratio of fresh to dry mass. Sown plant community biomass was calculated as the sum of the biomass of the individual sown species. The mean of both samples per plot and the individual measurements are provided in the data file. Overall, analyses of the community biomass data have identified species richness and the presence of particular species as an important driver of a positive biodiversity-productivity relationship.