Optimizing Prices and Periods in Time-of-use Electricity Tariff Design Using Bilevel Programming
Maria Alves, Carlos Henggeler Antunes, Inês Soares
In this paper, a comparison is made between two bilevel programming models to design time-of-use tariffs in the electricity retail market. The upper-level objective function consists of the maximization of the retailer’s profit and the lower-level problem relates to the minimization of the consumer’s cost. In the first model, the periods in which prices apply are pre-defined and the aim is to determine the price values. In the second model, which is developed for the first time in this paper, both the periods and prices are decision variables, thus leading to a very large search space for the upper-level problem due to the number of combinations periods-prices. For the model with variable periods, a hybrid approach combining a genetic algorithm for the upper-level search with a mixed-integer linear programming solver to obtain optimal solutions to the lower-level problem is herein developed. Computational results comparing the two models are presented.
An algebraic approach for the search space of permutations with repetition
Marco Baioletti, Alfredo Milani, Valentino Santucci (recorded presentation)
We present an algebraic approach for dealing with combinatorial optimization problems based on permutations with repetition. The approach is an extension of an algebraic framework defined for combinatorial search spaces which can be represented by a group (in the algebraic sense). Since permutations with repetition does not have the group structure, in this work we derive some definitions and we devise discrete operators that allow to design algebraic evolutionary algorithms whose search behavior is in line with the algebraic framework. In particular, a discrete Differential Evolution algorithm which directly works on the space of permutations with repetition is defined and analyzed. As a case of study, an implementation of this algorithm is provided for the Job Shop Scheduling Problem. Experiments have been held on commonly adopted benchmark suites, and they show that the proposed approach obtains competitive results compared to the known optimal objective values.
A comparison of genetic representations for multi-objective shortest path problems on multigraphs
Lilla Beke, Michal Weiszer, Jun Chen (recorded presentation)
The use of multi-graphs in modelling multi-objective transportation problems is gaining popularity, necessitating the consideration of the Multi-objective Shortest Path Problem (MSPP) on multigraphs. This problem is encountered in time-dependent vehicle routing, multimodal transportation planning and in optimising airport operations. This problem is more complex than the NP-hard simple graph MSPP, and thus approximate solution methods are needed to find a good representation of the true Pareto front in a given time budget. Evolutionary algorithms have been applied with success to the simple graph MSPP, however their performances on multigraph MSPP were not systematically investigated. To this aim, we extend the most popular genetic representations to the multigraph case and compare the achieved performances. We find that the priority based encodings outperform the direct ones with purely random initialisation. We further introduce a novel heuristic initialisation technique, that is generic enough for many representations, and that further improves the convergence speed and solution quality of the algorithms. The results are encouraging for later application to the time constrained multigraph MSPP.
The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis
Benjamin Doerr, Martin S. Krejca
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DLB problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most \lambda( n/2 + 2e ln n) fitness evaluations. Since an offspring population size \lambda of order n log n can prevent genetic drift, the UMDA can solve the DLB problem with O(n^2 log n) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than O(n^3) is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
A Beam Search Approach to the Traveling Tournament Problem
Nikolaus Frohner, Bernhard Neumann, Günther R. Raidl
The well-known traveling tournament problem is a hard optimization problem in which a double round robin sports league schedule has to be constructed while minimizing the total travel distance over all teams. The teams start and end their tours at their home venues, are only allowed to play a certain maximum number of games in a row at home or away, and must not play against each other in two consecutive rounds. The latter aspects introduce also a difficult feasibility aspect. In this work, we study a beam search approach based on a recursive state space formulation. We compare different state ordering heuristics for the beam search based on lower bounds derived by means of decision diagrams. Furthermore, we introduce a randomized beam search variant that adds Gaussian noise to the heuristic value of a node for diversifying the search in order to enable a simple yet effective parallelization. In our computational study, we use randomly generated instances to compare and tune algorithmic parameters and present final results on the classical National League and circular benchmark instances. Results show that this purely construction-based method provides mostly better solutions than existing ant-colony optimization and tabu search algorithms and it comes close to the leading simulated annealing based approaches without using any local search. For two circular benchmark instances we found new best solutions for which the last improvement was twelve years ago.The presented state space formulation and lower bound techniques could also be beneficial for exact methods like A* or DFS* and may be used to guide the randomized construction in ACO or GRASP approaches.
Cooperative Parallel SAT Local Search with Path Relinking
Padraigh Jarvis, Alejandro Arbelaez (recorded presentation)
In this paper, we propose the use of path relinking to improve the performance of parallel portfolio-based local search solvers for the Boolean Satisfiability problem. In the portfolio-based framework several algorithms explore the search space in parallel, either independently or cooperatively with some communication between the solvers. Path relinking is a method to maintain an appropriate balance between diversification and intensification (and explore paths that aggregate elite solutions) to properly craft a new assignment for the variables to restart from. We present an empirical study that suggest that path relinking outperforms a set of well-known parallel portfolio-based local search algorithms with and without cooperation.
Dynamic Compartmental Models for Large Multi-objective Landscapes and Performance Estimation
Hugo Monzón, Hernán Aguirre, Sébastien Verel, Arnaud Liefooghe, Bilel Derbel, Kiyoshi Tanaka
Dynamic Compartmental Models are linear models inspired by epidemiology models to study Multi- and Many-Objective Evolutionary Algorithms dynamics. So far they have been tested on small MNK-Landscapes problems with 20 variables and used as a tool for algorithm analysis, algorithm comparison, and algorithm configuration assuming that the Pareto optimal set is known. In this paper, we introduce a new set of features based only on when non-dominated solutions are found in the population, relaxing the assumption that the Pareto optimal set is known in order to use Dynamic Compartment Models on larger problems. We also propose an auxiliary model to estimate the hypervolume from the features of population dynamics that measures the changes of new non-dominated solutions in the population. The new features are tested by studying the population changes on the Adaptive epsilon-Sampling epsilon-Hood while solving 30 instances of a 3 objective, 100 variables MNK-landscape problem. We also discuss the behavior of the auxiliary model and the quality of its hypervolume estimations.
Fitness Landscape Analysis of Automated Machine Learning Search Spaces
Cristiano G. Pimenta, Alex G. C. de Sá, Gabriela Ochoa, Gisele L. Pappa (recorded presentation)
The field of Automated Machine Learning (AutoML) has as its main goal to automate the process of creating complete Machine Learning (ML) pipelines to any dataset without requiring deep user expertise in ML. Several AutoML methods have been proposed so far, but there is not a single one that really stands out. Furthermore, there is a lack of studies on the characteristics of the fitness landscape of AutoML search spaces. Such analysis may help to understand the performance of different optimization methods for AutoML and how to improve them. This paper adapts classic fitness landscape analysis measures to the context of AutoML. This is a challenging task, as AutoML search spaces include discrete, continuous, categorical and conditional hyperparameters. We propose an ML pipeline representation, a neighborhood definition and a distance metric between pipelines, and use them in the evaluation of the fitness distance correlation (FDC) and the neutrality ratio for a given AutoML search space. Results of FDC are counter-intuitive and require a more in-depth analysis of a range of search spaces. Results of neutrality, in turn, show a strong positive correlation between the mean neutrality ratio and the fitness value.
On the Combined Impact of Population Size and Sub-problem Selection in MOEA/D
Geoffrey Pruvost, Bilel Derbel, Arnaud Liefooghe, Ke Li, Qingfu Zhang (recorded presentation)
This paper intends to understand and to improve the working principle of decomposition-based multi-objective evolutionary algorithms. We review the design of the well-established MOEA/D framework to support the smooth integration of different strategies for sub-problem selection, while emphasizing the role of the population size and of the number of offspring created at each generation. By conducting a comprehensive empirical analysis on a wide range of multi- and many-objective combinatorial NK landscapes, we provide new insights into the combined effect of those parameters on the anytime performance of the underlying search process. In particular, we show that even a simple random strategy selecting sub-problems at random outperforms the performance over existing sophisticated strategies. We also study the sensitivity of such strategies with respect to the ruggedness and the objective space dimension of the target problem.
A Grouping Genetic Algorithm for Multi Depot Pickup and Delivery Problems with Time Windows and Heterogeneous Vehicle Fleets
Cornelius Rüther, Julia Rieck
The Multi Depot Pickup and Delivery Problem with Time Windows and Heterogeneous Vehicle Fleets is a Rich Vehicle Routing Problem as it combines many real-world problems and is therefore relevant to practice. In this paper a new mathematical two-index model formulation for the MDPDPTWHV is developed as well as a Grouping Genetic Algorithm (GGA), which features a grouping-oriented individual representation. Therefore, each chromosome contains only the assignment of requests to vehicles, i.e., no information about the customer sequence is included. In order to compare different variants of the GGA to each other as well as the best one to solutions calculated by Cplex, 120 MDPDPTWHV datasets are created through a generator implemented by the authors. In a benchmark study, it can be shown that the way in which population management is performed is important to enhance the solution quality of the GGA. On average, the best GGA variant is 2.43% worse than the best known solution.
MILPIBEA: Algorithm for Multi-objective Features Selection in (Evolving) Software Product Lines
Takfarinas Saber, David Brevet, Goetz Botterweck, Anthony Ventresque (recorded presentation)
Software Product Lines Engineering (SPLE) proposes techniques to model, create and improve groups of related software systems in a systematic way, with different alternatives formally expressed, e.g., as Feature Models. Selecting the best software system(s) turns into a problem of improving the quality of selected subsets of software features (components) from feature models, or as it is widely known, Feature Configuration. When there are different independent dimensions to assess how good a software product is, the problem becomes even more challenging – it is then a multi-objective optimisation problem. Another big issue for software systems is evolution where software components change. This is common in the industry but, as far as we know, there is no algorithm designed to the particular case of multi-objective optimisation of evolving software product lines. In this paper we present MILPIBEA, a novel hybrid algorithm which combines the scalability of a genetic algorithm (IBEA) with the accuracy of a mixed-integer linear programming solver (IBM ILOG CPLEX). We also study the behaviour of our solution (MILPIBEA) in contrast with SATIBEA, a state-of-the-art algorithm in static software product lines. We demonstrate that MILPIBEA outperforms SATIBEA on average, especially for the most challenging problem instances, and that MILPIBEA is the one that continues to improve the quality of the solutions when SATIBEA stagnates (in the evolving context).
A Group Genetic Algorithm for Resource Allocation in Container-based Clouds
Boxiong Tan, Hui Ma, Yi Mei
Containers have gain popularity because they support fast development and deployment of cloud-native software such as micro-services and server-less applications. Additionally, containers have low overhead, hence they save resources in cloud data centers. However, the difficulty of the Resource Allocation in Container-based clouds (RAC) is far beyond Virtual Machine (VM)-based clouds. The allocation task selects heterogeneous VMs to host containers and consolidate VMs to Physical Machines (PMs) simultaneously. Due to the high complexity, existing approaches use simple rule-based heuristics and meta-heuristics to solve the RAC problem. They either prone to stuck at local optima or have inherent defects in their indirect representations. To address these issues, we propose a novel group genetic algorithm (GGA) with a direct representation and problem-specific operators. This design has shown significantly better performance than the state-of-the-art algorithms in a wide range of test datasets.
The Local Optima Level in Chemotherapy Schedule Optimisation
Sarah L. Thomson, Gabriela Ochoa (recorded presentation)
In this paper a multi-drug Chemotherapy Schedule Optimisation Problem (CSOP) is subject to Local Optima Network (LON) analysis. LONs capture global patterns in fitness landscapes. CSOPs have not previously been subject to fitness landscape analysis. We fill this gap: LONs are constructed and studied for meaningful structure. The CSOP formulation presents novel challenges and questions for the LON model because there are infeasible regions in the fitness landscape and an unknown global optimum; it also brings a topic from healthcare to LON analysis. Two LON Construction algorithms are proposed for sampling CSOP fitness landscapes: a Markov-Chain Construction Algorithm and a Hybrid Construction Algorithm. The results provide new insight into LONs of highly-constrained spaces, and into the proficiency of search operators on the CSOP. Iterated Local Search and Memetic Search, which are the foundations for the LON algorithms, are found to markedly out-perform a Genetic Algorithm from the literature.
A New Representation in Genetic Programming for Evolving Dispatching Rules for Dynamic Flexible Job Shop Scheduling
Fangfang Zhang, Yi Mei, Su Nguyen, Mengjie Zhang
Dynamic flexible job shop scheduling (DFJSS) is a very important problem with a wide range of real-world applications such as cloud computing and manufacturing. In DFJSS, it is critical to make two kinds of real-time decisions (i.e. the routing decision that assigns machine to each job and the sequencing decision that prioritises the jobs in a machine’s queue) effectively in the dynamic environment with unpredicted events such as new job arrivals and machine breakdowns. Dispatching rule is an ideal technique for this purpose. In DFJSS, one has to design a routing rule and a sequencing rule for making the two kinds of decisions. Manually designing these rules is time consuming and requires human expertise which is not always available. Genetic programming (GP) has been applied to automatically evolve more effective rules than the manually designed ones. In GP for DFJSS, different features in the terminal set have different contributions to the decision making. However, the current GP approaches cannot perfectly find proper combinations between the features in accordance with their contributions. In this paper, we propose a new representation for GP that better considers the different contributions of different features and combines them in a sophisticated way, thus to evolve more effective rules. The results show that the proposed GP approach can achieve significantly better performance than the baseline GP in a range of job shop scenarios.