144 research outputs found
A multi-granularity locally optimal prototype-based approach for classification
Get PDFPrototype-based approaches generally provide better explainability and are widely used for classification. However, the majority of them suffer from system obesity and lack transparency on complex problems. In this paper, a novel classification approach with a multi-layered system structure self-organized from data is proposed. This approach is able to identify local peaks of multi-modal density derived from static data and filter out more representative ones at multiple levels of granularity acting as prototypes. These prototypes are then optimized to their locally optimal positions in the data space and arranged in layers with meaningful dense links in-between to form pyramidal hierarchies based on the respective levels of granularity accordingly. After being primed offline, the constructed classification model is capable of self-developing continuously from streaming data to self-expend its knowledge base. The proposed approach offers higher transparency and is convenient for visualization thanks to the hierarchical nested architecture. Its system identification process is objective, data-driven and free from prior assumptions on data generation model with user- and problem- specific parameters. Its decision-making process follows the “nearest prototype” principle, and is highly explainable and traceable. Numerical examples on a wide range of benchmark problems demonstrate its high performance
Adapting Multi-objectivized Software Configuration Tuning
Get PDFWhen tuning software configuration for better performance (e.g., latency or throughput), an important issue that many optimizers face is the presence of local optimum traps, compounded by a highly rugged configuration landscape and expensive measurements. To mitigate these issues, a recent effort has shifted to focus on the level of optimization model (called meta multi-objectivization or MMO) instead of designing better optimizers as in traditional methods. This is done by using an auxiliary performance objective, together with the target performance objective, to help the search jump out of local optima. While effective, MMO needs a fixed weight to balance the two objectives—a parameter that has been found to be crucial as there is a large deviation of the performance between the best and the other settings. However, given the variety of configurable software systems, the “sweet spot” of the weight can vary dramatically in different cases and it is not possible to find the right setting without time-consuming trial and error. In this paper, we seek to overcome this significant shortcoming of MMO by proposing a weight adaptation method, dubbed AdMMO. Our key idea is to adaptively adjust the weight at the right time during tuning, such that a good proportion of the nondominated configurations can be maintained. Moreover, we design a partial duplicate retention mechanism to handle the issue of too many duplicate configurations without losing the rich information provided by the “good” duplicates. Experiments on several real-world systems, objectives, and budgets show that, for 71% of the cases, AdMMO is considerably superior to MMO and a wide range of state-of-the-art optimizers while achieving generally better efficiency with the best speedup between 2.2x and 20x
Evolutionary many-objective optimisation: pushing the boundaries
Get PDFThis thesis was submitted for the award of Doctor of Philosophy and was awarded by Brunel University LondonMany-objective optimisation poses great challenges to evolutionary algorithms. To start with, the ineffectiveness of the Pareto dominance relation, which is the most important criterion in multi-objective optimisation, results in the underperformance of traditional Pareto-based algorithms. Also, the aggravation of the conflict between proximity and diversity, along with increasing time or space requirement as well as parameter sensitivity, has become key barriers to the design of effective many-objective optimisation algorithms. Furthermore, the infeasibility of solutions' direct observation can lead to serious difficulties in algorithms' performance investigation and comparison. In this thesis, we address these challenges, aiming to make evolutionary algorithms as effective in many-objective optimisation as in two- or three-objective optimisation. First, we significantly enhance Pareto-based algorithms to make them suitable for many-objective optimisation by placing individuals with poor proximity into crowded regions so that these individuals can have a better chance to be eliminated. Second, we propose a grid-based evolutionary algorithm which explores the potential of the grid to deal with many-objective optimisation problems. Third, we present a bi-goal evolution framework that converts many objectives of a given problem into two objectives regarding proximity and diversity, thus creating an optimisation problem in which the objectives are the goals of the search process itself. Fourth, we propose a comprehensive performance indicator to compare evolutionary algorithms in optimisation problems with various Pareto front shapes and any objective dimensionality. Finally, we construct a test problem to aid the visual investigation of evolutionary search, with its Pareto optimal solutions in a two-dimensional decision space having similar distribution to their images in a higher-dimensional objective space. The work reported in this thesis is the outcome of innovative attempts at addressing some of the most challenging problems in evolutionary many-objective optimisation. This research has not only made some of the existing approaches, such as Pareto-based or grid-based algorithms that were traditionally regarded as unsuitable, now effective for many-objective optimisation, but also pushed other important boundaries with novel ideas including bi-goal evolution, a comprehensive performance indicator and a test problem for visual investigation. All the proposed algorithms have been systematically evaluated against existing state of the arts, and some of these algorithms have already been taken up by researchers and practitioners in the field.Department of Computer Science, Brunel University Londo
A Performance Comparison Indicator for Pareto Front Approximations in Many-Objective Optimization
No full textIncreasing interest in simultaneously optimizing many objectives (typically more than three objectives) of problems leads to the emergence of various many-objective algorithms in the evolutionary multi-objective optimization field. However, in contrast to the development of algorithm design, how to assess many-objective algorithms has received scant concern. Many performance indicators are designed in principle for any number of objectives, but in practice are invalid or infeasible to be used in many-objective optimization. In this paper, we explain the di culties that popular performance indicators face and propose a performance comparison indicator (PCI) to assess Pareto front approximations obtained by many-objective algorithms. PCI evaluates the quality of approximation sets with the aid of a reference set constructed by themselves. The points in the reference set are divided into many clusters, and the proposed indicator estimates the minimum moves of solutions in the approximation sets to weakly dominate these clusters. PCI has been verified both by an analytic comparison with several well-known indicators and by an empirical test on four groups of Pareto front approximations with different numbers of objectives and problem characteristics
Multi-objectivizing software configuration tuning
Get PDFAutomatically tuning software configuration for optimizing a single performance attribute (e.g., minimizing latency) is not trivial, due to the nature of the configuration systems (e.g., complex landscape and expensive measurement). To deal with the problem, existing work has been focusing on developing various effective optimizers. However, a prominent issue that all these optimizers need to take care of is how to avoid the search being trapped in local optima — a hard nut to crack for software configuration tuning due to its rugged and sparse landscape, and neighboring configurations tending to behave very differently. Overcoming such in an expensive measurement setting is even more challenging. In this paper, we take a different perspective to tackle this issue. Instead of focusing on improving the optimizer, we work on the level of optimization model. We do this by proposing a meta multi-objectivization model (MMO) that considers an auxiliary performance objective (e.g., throughput in addition to latency). What makes this model unique is that we do not optimize the auxiliary performance objective, but rather use it to make similarly-performing while different configurations less comparable (i.e. Pareto nondominated to each other), thus preventing the search from being trapped in local optima.Experiments on eight real-world software systems/environments with diverse performance attributes reveal that our MMO model is statistically more effective than state-of-the-art single-objective counterparts in overcoming local optima (up to 42% gain), while using as low as 24% of their measurements to achieve the same (or better) performance result
On the use of hypervolume for diversity measurement of Pareto front approximations
Get PDFThe file attached to this record is the author's final peer reviewed version. The Publisher's final version can be found by following the DOI link.In multiobjective optimization, a good quality indicator is of great importance to the performance assessment of algorithms. This paper investigates the effectiveness of the widely-used hypervolume indicator, which is the only one found so far to strictly comply with the Pareto dominance. While hypervolume is of undisputed success to assess the quality of an approximation, it is sensitive to misleading cases, particularly for diversity assessment. To address this issue, this paper presents a modified hypervolume indicator based on linear projection for diversity evaluation. In addition to experimental studies to demonstrate the effectiveness of the proposed indicator, the indicator is introduced into the environmental selecction of an indicator-based multiobjective optimization evolutionary algorithm. Experiments show that the proposed indicator yields more evenly-distributed approximations than the original hypervolume indicator
A test problem for visual investigation of high-dimensional multi-objective search
Get PDFAn inherent problem in multiobjective optimization is that the visual observation of solution vectors with four or more objectives is infeasible, which brings major difficulties for algorithmic design, examination, and development. This paper presents a test problem, called the Rectangle problem, to aid the visual investigation of high-dimensional multiobjective search. Key features of the Rectangle problem are that the Pareto optimal solutions 1) lie in a rectangle in the two-variable decision space and 2) are similar (in the sense of Euclidean geometry) to their images in the four-dimensional objective space. In this case, it is easy to examine the behavior of objective vectors in terms of both convergence and diversity, by observing their proximity to the optimal rectangle and their distribution in the rectangle, respectively, in the decision space. Fifteen algorithms are investigated. Underperformance of Pareto-based algorithms as well as most state-of-the-art many-objective algorithms indicates that the proposed problem not only is a good tool to help visually understand the behavior of multiobjective search in a high-dimensional objective space but also can be used as a challenging benchmark function to test algorithms' ability in balancing the convergence and diversity of solutions
Do Performance Aspirations Matter for Guiding Software Configuration Tuning? An Empirical Investigation under Dual Performance Objectives
No full textConfigurable software systems can be tuned for better performance. Leveraging on some Pareto optimizers, recent work has shifted from tuning for a single, time-related performance objective to two intrinsically different objectives that assess distinct performance aspects of the system, each with varying aspirations to be satisfied, e.g., "the latency is less than 10s"while "the memory usage is no more than 1GB". Before we design better optimizers, a crucial engineering decision to make therein is how to handle the performance requirements with clear aspirations in the tuning process. For this, the community takes two alternative optimization models: either quantifying and incorporating the aspirations into the search objectives that guide the tuning, or not considering the aspirations during the search but purely using them in the later decision-making process only. However, despite being a crucial decision that determines how an optimizer can be designed and tailored, there is a rather limited understanding of which optimization model should be chosen under what particular circumstance, and why.In this article, we seek to close this gap. Firstly, we do that through a review of over 426 articles in the literature and 14 real-world requirements datasets, from which we summarize four performance requirement patterns that quantify the aspirations in the configuration tuning. Drawing on these, we then conduct a comprehensive empirical study that covers 15 combinations of the state-of-the-art performance requirement patterns, four types of aspiration space, three Pareto optimizers, and eight real-world systems/environments, leading to 1,296 cases of investigation. Our findings reveal that (1) the realism of aspirations is the key factor that determines whether they should be used to guide the tuning; (2) the given patterns and the position of the realistic aspirations in the objective landscape are less important for the choice, but they do matter to the extents of improvement; (3) the available tuning budget can also influence the choice for unrealistic aspirations but it is insignificant under realistic ones. To promote open science practice, we make our code and dataset publicly available at: https://github.com/ideas-labo/aspiration-study.</p
An empirical investigation of the optimality and monotonicity properties of multiobjective archiving methods
Get PDFMost evolutionary multiobjective optimisation (EMO) algorithms explicitly or implicitly maintain an archive for an approximation of the Pareto front. A question arising is whether existing archiving methods are reliable with respect to their convergence and approximation ability. Despite theoretical results available, it remains unknown how these archivers actually perform in practice. In particular, what percentage of solutions in their final archive are Pareto optimal? How frequently do they experience deterioration during the archiving process? Deterioration means archiving a new solution which is dominated by some solution discarded previously. This paper answers the above questions through a systematic investigation of eight representative archivers on 37 test instances with two to five objectives. We have found that 1) deterioration happens to all the archivers; 2) the deterioration degree can vary dramatically on different problems; 3) some archivers clearly perform better than others; and 4) several popular archivers sometime return a population with most solutions being the non-optimal. All of these suggest the need of improvement of current archiving methods
- …
