Search

Dynamic optimization multi-objective problems (DMOPs) are characterized by the environmental changes they experiment . For these problems, optimization algorithms have limited time to find accurate results before every change. A common scenario in optimization is the presence of a decision maker (DM), which establishes preferences on the problem being solved. Nowadays, there are few works focused on applying preference incorporation techniques in DMOPs. This work proposes the Plane Separation (PS) method, a novel technique that allows incorporating preferences in the optimization process by splitting the population into multiple planes based on the proximity of solutions to the region of interest (ROI). PS uses those planes to focus the search towards the ROI while maintaining diversity in the solutions set to avoid stagnation in local optima. PS is incorporated into two versions of DNSGA-II, and in a novel dynamic version of GDE3 we propose. These algorithms are also used as low-level heuristics of a hyper-heuristic. All PS-incorporated algorithms were compared against DRNSGA-II, a dynamic version proposal of a single-reference-point technique for solving MOPs under different preferential setups. The results favor the performance of the proposed PS-based algorithms, confirming its feasibility and effectiveness as a technique for incorporating preferences within a dynamic environment.

We propose a new method for multi-objective optimization, called Fuzzy Adaptive Multi-objective Evolutionary algorithm (FAME). It makes use of a smart operator controller that dynamically chooses the most promising variation operator to apply in the different stages of the search. This choice is guided by a fuzzy logic engine, according to the contributions of the different operators in the past. FAME also includes a novel effective density estimator with polynomial complexity, called Spatial Spread Deviation (SSD). Our proposal follows a steady-state selection scheme and includes an external archive implementing SSD to identify the candidate solutions to be removed when it becomes full. To assess the performance of our proposal, we compare FAME with a number of state of the art algorithms (MOEA/D-DE, SMEA, SMPSOhv, SMS-EMOA, and BORG) on a set of difficult problems. The results show that FAME achieves the best overall performance.

In this paper, we address the exact solution of the vertex bisection problem (VBP). We propose two novel B&B algorithms to solve VBP, which include new upper and lower bound constructive heuristics, and an efficient strategy to explore the combinatorial search space. The computational results show that the proposed algorithms clearly outperforms the state-of-the-art B&B algorithm in quality and efficiency. The two proposed B&B versions differ in the exploration strategy and the storage of the search tree. Also, we provide four new solutions, previously unknown. We consider that the main contributions of this work can be adapted to solve combinatorial problems in other related domains.

Today's IT systems and IT processes must be ready to handle change in an efficient and responsive manner to allow businesses to both evolve and adapt to a changing world. In this paper we describe an approach that consists of using simulation based multi-objective optimization to select optimal ITIL change management process strategies that help IT managers achieve process efficiency as a Critical Success Factor (CSF). A multi-method simulation model, which is based on agent-based and discrete-event simulation paradigms, has been built to simulate the whole process lifecycle, since the change initiation until its closure. As most engineering problems, assuring an efficient delivery of the change management process requires optimizing simultaneously the corresponding Key Performance Indicators (KPIs) in which the process-efficiency CSF can be rolled down. In this paper, we show the results of applying two well-known Multi-Objective Evolutionary Algorithms, namely NSGA-II and SPEA2, to obtain a set of optimal solutions for the KPIs associated with delivering process efficiency as a CSF. We also compare the results obtained with the output from the single-objective optimization algorithm provided by the simulation tool. The experimental work included shows how the approach can provide the IT manager with a wide range of high quality solutions to support them in their decision-making towards CSF achievement.

We present a novel method to automatically generate new parallel solvers for optimization problems, called the Virtual Savant. It applies machine learning to model a reference algorithm (which is treated as a black box) from its solutions to a given problem, and after, it is able to efficiently and accurately reproduce its solutions on new unseen problem instances. Additionally, the generated parallel algorithm is scalable to a different problem dimension. We analyze the performance and accuracy of our novel technique on a scheduling problem, and we use instances of different features and sizes. Virtual Savant was used to learn from an exact algorithm, a well-known heuristic, and a specialized parallel metaheuristic. During our experiments, our method solved to optimality up to 95.5% of the 200 unseen instances tested. For larger instances, it is not only highly competitive with the reference algorithms, but it is even able to outperform them in some cases. Another outstanding result is that Virtual Savant improved its accuracy when scaling the problem size (without additional training), with respect to the original algorithm.

We present a parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. The algorithm, called CCSMPSO, is the first multi-objective cooperative coevolutionary algorithm based on PSO in the literature. SMPSO adopts a strategy for limiting the velocity of the particles that prevents them from having erratic movements. This characteristic provides the algorithm with a high degree of reliability. In order to demonstrate the effectiveness of CCSMPSO, we compare our work with the original SMPSO and three different state-of-the-art multi-objective CC metaheuristics, namely CCNSGA-II, CCSPEA2 and CCMOCell, along with their original sequential counterparts. Our experiments indicate that our proposed solution, CCSMPSO, offers significant computational speedups, a higher convergence speed and better or comparable results in terms of solution quality, when evaluated against three other CC algorithms and four state-of-the-art optimizers (namely SMPSO, NSGA-II, SPEA2, and MOCell), respectively. We then provide a scalability analysis, which consists of two studies. First, we analyze how the algorithms scale when varying the problem size, i.e., the number of variables. Second, we analyze their scalability in terms of parallelization, i.e., the impact of using more computational cores on the quality of solutions and on the execution time of the algorithms. Three different criteria are used for making the comparisons, namely the quality of the resulting approximation sets, average computational time and the convergence speed to the Pareto front.

This article presents how Virtual Savant (VS) can be used to automatically learn, from an exact algorithm, how to solve the basic independent Next Release Problem in a quick and accurate way. This variant of the Next Release Problem (NRP) is in essence a 0/1 Knapsack Problem and VS is applied to solve the underlying optimization problem. VS is a generic problem-solving approach based on machine learning and heuristics, that works by mimicking how a reference program produces solutions to problem instances. Essentially, VS learns how to generate solutions to a given problem from a reference algorithm and a training set of instances, and it is able to efficiently solve new problem instances by using the acquired knowledge. In this paper, an exact optimizer is used as a reference algorithm. Hence, we are using VS to learn from optimal solutions, which helps to reduce the approximation error inherent to the learning process. We compare five versions of VS (differing in the heuristics they implement) on a large benchmark, composed of problems with different sizes and difficulties. For the best VS configuration, which also has the lowest computational complexity, computed solutions differ less than 1% from the optima in the worst case. Therefore, VS succeeds in learning how to solve the problem under study, and it does so in a highly efficient way, exempting the programmer from having a deep knowledge of the problem domain or highly specialized parallel programming skills.

We propose a new accurate Micro Genetic Algorithm ( μ GA) for multi-objective optimization problems that we call Micro-FAME (or μ FAME). The distinctive feature of μ FAME with respect to the other existing multi-objective algorithms in the literature is its high elitism and fast convergence, produced by the application of the evolution directly on the Pareto front approximation. This means that it has a bounded population of variable size, determined by the number of non-dominated solutions found so far. In μ FAME (and generally in μ GAs) the premature convergence problem acquires especial relevance, and generating and maintaining solutions diversity is of extreme importance to deal with it. This is especially significant in the multi-objective field, where the algorithm looks for a wide and diverse set of non-dominated solutions. In μ FAME, the diversity loss that high elitism usually produces is overcome by the decisions driven by the Fuzzy Inference System (FIS), that chooses the most appropriate operators to apply during the evolution to promote both diversity and accuracy of solutions. The algorithm arises as a suitable solution for problems with a computationally heavy fitness function, because it is able to quickly achieve good quality local optimal solutions, but it is also highly competitive in long runs. Experiments reveal a great performance of μ FAME according to several convergence related metrics, when comparing against seven state-of-the-art algorithms on a large set of benchmark problems, as well as on a real-world engineering one with an expensive fitness function.

This work presents a novel parallel branch and bound algorithm to efficiently solve to optimality a set of instances of the multi-objective flexible job shop scheduling problem for the first time, to the very best of our knowledge. It makes use of the well-known NSGA-II algorithm to initialize its upper bound. The algorithm is implemented for shared-memory architectures, and among its main features, it incorporates a grid representation of the solution space, and a concurrent priority queue to store and dispatch the pending sub-problems to be solved. We report the optimal Pareto front of thirteen well-known instances from the literature, which were unknown before. They will be very useful for the scientific community to provide more accuracy in the performance measurement of their algorithms. Indeed, we carefully analyze the performance of NSGA-II on these instances, comparing the results against the optimal ones computed in this work. Extensive computational experiments show that the proposed algorithm using 24 cores achieves a speedup of 15.64x with an efficiency of 65.20%.

We present in this work the first parallel implementation of Virtual Savant (VS), a novel optimization method that is able to quickly generate pseudo-optimal solutions to a given combinatorial problem, thanks to its parallel pattern recognition engine. The proposed parallel implementation does not require any information exchange between the threads during the run, they just get/send the required information before/after the execution. This design allows for a flexible algorithm that can perform efficiently on both shared- and distributed-memory systems. Our implementation uses both OpenMP for parallel architectures and MPI for distributed environments, which can efficiently make use of both kind of systems. The performance of VS is extensively analyzed on four different computing infrastructures, varying the number of threads used on each considered architecture. In addition, we propose a simulator to accurately predict the performance of VS on any parallel system. Experimental results show that VS is able to make an efficient use of the available computing resources, showing good scalability properties on all studied architectures.

This article introduces three new multi-objective cooperative coevolutionary variants of three state-of-the-art multi-objective evolutionary algorithms, namely, Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). In such a coevolutionary architecture, the population is split into several subpopulations or islands, each of them being in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. Evaluation of complete solutions is achieved through cooperation, i.e., all subpopulations share a subset of their current partial solutions. Our purpose is to study how the performance of the cooperative coevolutionary multi-objective approaches can be drastically increased with respect to their corresponding original versions. This is specially interesting for solving complex problems involving a large number of variables, since the problem decomposition performed by the model at the island level allows for much faster executions (the number of variables to handle in every island is divided by the number of islands). We conduct a study on a real-world problem related to grid computing, the bi-objective robust scheduling problem of independent tasks. The goal in this problem is to minimize makespan (i.e., the time when the latest machine finishes its assigned tasks) and to maximize the robustness of the schedule (i.e., its tolerance to unexpected changes on the estimated time to complete the tasks). We propose a parallel, multithreaded implementation of the coevolutionary algorithms and we have analyzed the results obtained in terms of both the quality of the Pareto front approximations yielded by the techniques as well as the resulting speedups when running them on a multicore machine.

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min-min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min-min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min-min heuristic when more accurate solutions are needed, at the expense of an increased runtime.

Mobile Ad Hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such kind of networks, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcasting strategy in MANETs is a multi-objective problem targeting three goals: reaching as many devices as possible, minimizing the network utilization, and reducing the duration time of the broadcasting process. In this paper, we study the fine-tuning of broadcasting strategies by using a cellular multi-objective genetic algorithm (cMOGA) which computes a Pareto front of solutions to empower a human designer with the ability of choosing the preferred configuration for the network. We define two formulations of the problem, one with three objectives and another one with two objectives plus a constraint. For our tests, a benchmark of three realistic environments for metropolitan MANETs has been defined. Our experiments using a complex and realistic MANET simulator reveal that cMOGA is a promising approach to solve the optimum broadcasting problem.

The Vehicle Routing Problem (VRP) is a hard combinatorial problem with numerous industrial applications. Among the large number of extensions to the canonical VRP, we study the Capacitated VRP (CVRP), which is mainly characterized by using vehicles of the same capacity. A cellular Genetic Algorithm (cGA)--a kind of decentralized population based heuristic--is used for solving CVRP, improving several of the best existing results so far in the literature. Our study shows a high performance in terms of the quality of the solutions found and the number of function evaluations (effort).