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.

It is important to know the properties of an optimization problem and the difficulty an algorithm faces to solve it. Population evolvability obtains information related to both elements by analysing the probability of an algorithm to improve current solutions and the degree of those improvements. DPEM_HH is a dynamic multi-objective hyper-heuristic that uses low-level heuristic (LLH) selection methods that apply population evolvability. DPEM_HH uses dynamic multiobjective evolutionary algorithms (DMOEAs) as LLHs to solve dynamic multi-objective optimization problems (DMOPs). Population evolvability is incorporated in DPEM_HH by calculating it on each candidate DMOEA for a set of sampled generations after a change is detected, using those values to select which LLH will be applied. DPEM_HH is tested on multiple DMOPs with dynamic properties that provide several challenges. Experimental results show that DPEM_HH with a greedy LLH selection method that uses average population evolvability values can produce solutions closer to the Pareto optimal front with equal to or better diversity than previously proposed heuristics. This shows the effectiveness and feasibility of the application of population evolvability on hyperheuristics to solve dynamic optimization problems. First published online 12 July 2019

High-Performance Computing (HPC) is a growing necessity of our technological society, HPC demands high loads of parallel computing jobs, an optimal scheduling of the parallel applications tasks is a priority to meet the demands of its users on time. Branch-and-bound (BB) Algorithms and Mathematical Programming (MP) solve complex optimization problems in an optimal manner, some MP or BB even have parallel computing capabilities, making them suitable solutions to solve real-world problems. In this paper, we propose two exact algorithms, a BB and a MP Model for scheduling precedence-constrained applications, on heterogeneous computing systems, as far as we known the first ones on his kind presented in the state of the art. One major contribution of the work is the proposed formulations of the objective function in both methods. Experimental results obtained more than twenty optimal values for synthetic applications from the literature.

This paper investigates the automatic generation of a Map-Reduce program, which implements a heuristic for an NP-complete problem with machine learning. The objective is to automatically design a new concurrent algorithm that finds solutions of comparable quality to the original heuristic. Our approach, called Savant, is inspired from the savant syndrome. Its concurrency model is based on Map-Reduce. The approach is evaluated with the well-known Min-Min heuristic. Experimental results on two problem sizes are promising, the produced algorithm is able to find solutions of comparable quality.

Computer-aided design (CAD) is a technological revolution, very powerful and with large applicability to problem solving. It is essential in many different disciplines ranging from architecture to education, medicine, physics, or gaming. In this work, we propose a novel CAD tool, called CADDi, to assist in the design of electric diagrams in the educational context. We are applying the theory of formal languages to create WDLang, an easy-to-use, highly expressive, unequivocal, and correct programming language for designing electric circuits. This programming language is the cornerstone of CADDi, which automatically generates the equivalent ladder diagram (explains the circuit operation) to the programmed circuit, offering additional features that allow analysis of its functionality in an interactive way. It also offers a graphical interface to directly design ladder diagrams, or to modify the automatically generated ones. The existing electrical CAD tools are either very simple, e.g., for creating good-looking diagrams with no functionality, or too complex, for professional systems design. CADDi is extremely useful for learning purposes. It assists users on how to generate ladder diagrams, and on understanding the behavior of electrical circuits. Additionally, it serves as an assessment tool for self-evaluation in the translation from wiring diagrams to ladder ones. In order to make CADDi highly accessible, it was implemented as a web page.

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.

This paper presents a new parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. 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. The proposed approach, called CCSMPSO, is based on a new design and implementation of SMPSO in a cooperative coevolutionary (CC) framework. In such an architecture, the population is split into several subpopulations, which are in turn in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. We compare our work with two different state-of-the-art multi-objective CC metaheuristics, namely CCNSGA-II and CCSPEA2, as well as the original SMPSO in order to demonstrate its effectiveness. Our experiments indicate that our proposed solution, CCSMPSO, offers significant computational speedups, a higher convergence speed and better and comparable results in terms of solution quality, when compared to the other two CC algorithms and SMPSO, respectively. 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.

Evolutionary algorithms are metaheuristic algorithms that provide quasioptimal solutions in a reasonable time. They have been applied to many optimization problems in a high number of scientific areas. In this survey paper, we focus on the application of evolutionary algorithms to solve optimization problems related to a type of complex network likemobilemultihop ad hoc networks. Since its origin, mobile multihop ad hoc network has evolved causing new types of multihop networks to appear such as vehicular ad hoc networks and delay tolerant networks, leading to the solution of new issues and optimization problems. In this survey, we review the main work presented for each type of mobile multihop ad hoc network and we also present some innovative ideas and open challenges to guide further research in this topic.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithms (GAs) with decentralized population in which interactions among individuals are restricted to close ones. The use of decentralized populations in GAs allows to keep the population diversity for longer, usually resulting in a better exploration of the search space and, therefore, in a better performance of the algorithm. However, it supposes the need of several new parameters that have a major impact on the behavior of the algorithm. In the case of cGAs, these parameters are the population and neighborhood shapes. We propose in this work two innovative cGAs with new adaptive techniques that allow removing the neighborhood and population shape from the algorithm's configuration. As a result, the new adaptive cGAs are highly competitive (statistically) with all the compared cGAs in terms of the average solutions found in the continuous and combinatorial domains, while finding, in general, the best solutions for the considered problems, and with less computational effort.

Mobile ad hoc networks (or MANETs) are wireless networks that are spontaneously created by the neighbouring devices, without the use of any kind of infrastructure. These devices usually rely on batteries, so the lifetime of this type of network highly depends on the energy consumption of the devices composing it. Therefore, the optimisation of the energy consumption is a must in a realistic MANET. We deal in this paper with the optimisation of enhanced distance based (or EDB) broadcasting protocol for MANETs. EDB is an improved version of DB (distance based protocol), a state-of-the-art broadcasting protocol for MANETs, that is focussed on saving the energy used by the devices in the dissemination process (an essential component in MANETs), without degrading the network connectivity or the performance in the coverage of the broadcasting process. A set of parameters were identified in EDB and optimised using CellDE, a hybrid multi-objective optimisation algorithm, to maximise the coverage of the broadcast while minimising at the same time both the energy consumption and the broadcast time. The ns3 simulator was used to evaluate the different configurations of EDB. As a result, 100 different solutions are provided for every studied network, covering a wide range of design options; all of them have quality better than or similar to that provided by EDB with previously recommended values for its parameters.

Computational grids are an important emerging paradigm for large-scale distributed computing. As grid systems become more wide-spread, techniques for efficiently exploiting the large amount of grid computing resources become increasingly indispensable. A key aspect in order to benefit from these resources is the scheduling of jobs to grid resources. Due to the complex nature of grid systems, the design of efficient grid schedulers becomes challenging since such schedulers have to be able to optimize many conflicting criteria in very short periods of time. This problem has been tackled in the literature by several different metaheuristics, and our main focus in this work is to develop a new highly competitive technique with respect to the existing ones. For that, we exploit the capabilities of cellular memetic algorithms (cMAs), a kind of memetic algorithm with structured population, for obtaining efficient batch schedulers for grid systems, and the obtained results will be compared versus the state of the art. A careful design of the cMA methods and operators for the problem yielded to an efficient and robust implementation. Our experimental study, based on a known static benchmark for the problem, shows that this heuristic approach is able to deliver very high quality planning of jobs to grid nodes and thus it can be used to design efficient dynamic schedulers for real grid systems. Such dynamic schedulers can be obtained by running the cMA-based scheduler in batch mode for a very short time to schedule jobs arriving in the system since the last activation of the cMA scheduler.

Graphical abstractAEDB is an advanced adaptive protocol for information dissemination in mobile ad hoc networks MANETs. It is based on the Distance Based broadcasting protocol, and it acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. As most of the existing communication protocols, AEDB relies on different thresholds for adapting its behavior to the environment. We propose in this work to look for configurations that induce a stable performance of the protocol in different networks by automatically fine tuning these thresholds thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. Finding robust solutions for this problem is important because MANETs have a highly unpredictable and dynamic topology, features that have a strong influence on the performance of the protocol. Consequently, robust solutions that show a good performance under any circumstances are required. In this work, we define different fitness functions that taken into account robust metrics for better guiding the algorithm towards more robust solutions. They are: median, constrained, worst coverage, and worst hypervolume. Results show, that the two worst-case approaches perform better, not only in case of robustness but also in terms of accuracy of the reported AEDB configurations on a large set of networks. Display Omitted The Adaptive Enhanced Distance Based Broadcasting Protocol, AEDB hereinafter, is an advanced adaptive protocol for information dissemination in mobile ad hoc networks (MANETs). It is based on the Distance Based broadcasting protocol, and it acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. As most of the existing communication protocols, AEDB relies on different thresholds for adapting its behavior to the environment. We propose in this work to look for configurations that induce a stable performance of the protocol in different networks by automatically fine tuning these thresholds thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. Finding robust solutions for this problem is important because MANETs have a highly unpredictable and dynamic topology, features that have a strong influence on the performance of the protocol. Consequently, robust solutions that show a good performance under any circumstances are required. In this work, we define different fitness functions that measure robustness of solutions for better guiding the algorithm towards more robust solutions. They are: median, constrained, worst coverage, and worst hypervolume. Results show, that the two worst-case approaches perform better, not only in case of robustness but also in terms of accuracy of the reported AEDB configurations on a large set of networks.

This paper studies static and dynamic decentralized versions of the search model known as cellular genetic algorithm (cGA), in which individuals are located in a specific topology and interact only with their neighbors. Making changes in the shape of such topology or in the neighborhood may give birth to a high number of algorithmic variants. We perform these changes in a methodological way by tuning the concept of ratio. Since the relationship (ratio) between the topology and the neighborhood shape defines the search selection pressure, we propose to analyze in depth the influence of this ratio on the exploration/exploitation tradeoff. As we will see, it is difficult to decide which ratio is best suited for a given problem. Therefore, we introduce a preprogrammed change of this ratio during the evolution as a possible additional improvement that removes the need of specifying a single ratio. A later refinement will lead us to the first adaptive dynamic kind of cellular models to our knowledge. We conclude that these dynamic cGAs have the most desirable behavior among all the evaluated ones in terms of efficiency and accuracy; we validate our results on a set of seven different problems of considerable complexity in order to better sustain our conclusions.

HighlightsHeterogeneous, energy-aware precedence constrained (DAG) scheduling problem.Three multi-objective algorithms schemas are adapted: MOCell, NSGAII and IBEA.A representation with corresponding mutations and grouping crossover operators.Experimentation on a diversified and large set of real and synthetic applications.MOCell schema is the most versatile and the best performing one. The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches of computer science due to its financial, ecological, political, and technical consequences. One of the answers is given by scheduling combined with dynamic voltage scaling technique to optimize the energy consumption. The way of reasoning is based on the link between current semiconductor technologies and energy state management of processors, where sacrificing the performance can save energy.This paper is devoted to investigate and solve the multi-objective precedence constrained application scheduling problem on a distributed computing system, and it has two main aims: the creation of general algorithms to solve the problem and the examination of the problem by means of the thorough analysis of the results returned by the algorithms.The first aim was achieved in two steps: adaptation of state-of-the-art multi-objective evolutionary algorithms by designing new operators and their validation in terms of performance and energy. The second aim was accomplished by performing an extensive number of algorithms executions on a large and diverse benchmark and the further analysis of performance among the proposed algorithms. Finally, the study proves the validity of the proposed method, points out the best-compared multi-objective algorithm schema, and the most important factors for the algorithms performance.

International audience; Advantages of bringing small-world properties in mobile ad hoc networks (MANETs) in terms of quality of service has been studied and outlined in the past years. In this work, we focus on the specific class of vehicular ad hoc networks (VANETs) and propose to un-partition such networks and improve their small-world properties. To this end, a subset of nodes, called injection points, is chosen to provide backend connectivity and compose a fully-connected overlay network. The optimisation problem we consider is to find the minimal set of injection points to constitute the overlay that will optimise the small-world properties of the resulting network, i.e., (1) maximising the clustering coefficient (CC) so that it approaches the CC of a corresponding regular graph and (2) minimising the difference between the average path length (APL) of the considered graph and the APL of corresponding random graphs. Two accurate evolutionary algorithms (namely, NSGAII and MOCHC) are used to find an upper-bound of high quality solutions to this new multi-objective optimisation problem, on realistic instances in the city-centre of Luxembourg. The obtained sets of solutions are then used to assess the performance of five novel heuristics proposed to solve the problem, i.e., two centralised and three decentralised. The results provided by these heuristics turned out to be extremely accurate with respect to the solutions found by the evolutionary algorithms.

Cooperative coevolutionary evolutionary algorithms differ from standard evolutionary algorithms’ architecture in that the population is split into subpopulations, each of them optimising only a sub-vector of the global solution vector. All subpopulations cooperate by broadcasting their local partial solutions such that each subpopulation can evaluate complete solutions. Cooperative coevolution has recently been used in evolutionary multi-objective optimisation, but few works have exploited its parallelisation capabilities or tackled real-world problems. This article proposes to apply for the first time a state-of-the-art parallel asynchronous cooperative coevolutionary variant of the non-dominated sorting genetic algorithm II (NSGA-II), named CCNSGA-II, on the injection network problem in vehicular ad hoc networks (VANETs). This multi-objective optimisation problem, consists in finding the minimal set of nodes with backend connectivity, referred to as injection points, to constitute a fully connected overlay that will optimise the small-world properties of the resulting network. Recently, the well-known NSGA-II algorithm was used to tackle this problem on realistic instances in the city-centre of Luxembourg. In this work we analyse the performance of the CCNSGA-II when using different numbers of subpopulations, and compare them to the original NSGA-II in terms of both quality of the obtained Pareto front approximations and execution time speedup. Los algoritmos evolutivos cooperativos coevolutivos difieren de la arquitectura de los algoritmos evolutivos estándares en que la población se divide en sub-poblaciones, cada una de ellas dedicada a la optimización de un único sub-vector del vector que forma la solución global al problema. Todas las sub-poblaciones cooperan haciendo pública su mejor solución parcial local, de forma que cada subpoblación pueda evaluar soluciones completas usando esta información. La coevolución cooperativa se ha utilizado recientemente en algoritmos evolutivos de optimización multi-objetivo, pero muy pocos trabajos han explotado su capacidad de paralelismo o se han enfocado a problemas del mundo real. Este artículo propone aplicar, por primera vez, un algoritmo evolutivo cooperativo coevolutivo paralelo y asíncrono, variante del algoritmo NSGA-II, y llamado CCNSGA-II, para el problema de la inyección de enlaces en redes ad hoc vehiculares (VANETs). Este problema de optimización multi-objetivo consiste en encontrar el conjunto mínimo de nodos con conectividad adicional, llamados puntos de inyección, para formar una red subyacente completamente conectada de forma que las características de mundo pequeño de la red resultante sean optimizadas. Recientemente, el conocido algoritmo NSGA-II se utilizó para resolver este problema en instancias realistas del centro de la ciudad de Luxemburgo. En este trabajo analizamos el rendimiento de CCNSGA-II con distintos números de sub-poblaciones, y lo comparamos con el NSGA-II original en función de la calidad de la aproximación al frente de Pareto obtenido y del tiempo de ejecución.

One of the main challenges in cloud computing is to increase the availability of computational resources, while minimizing system power consumption and operational expenses. This article introduces a power efficient resource allocation algo- rithm for tasks in cloud computing data centers. The developed approach is based on genetic algorithms which ensure perfor- mance and scalability to millions of tasks. Resource allocation is performed taking into account computational and networking requirements of tasks and optimizes task completion time and data center power consumption. The evaluation results, obtained using a dedicated open source genetic multi-objective framework called jMetal show that the developed approach is able to perform the static allocation of a large number of independent tasks on homogeneous single-core servers within the same data center with a quadratic time complexity. Index Terms—Data center, Cloud Computing, Genetic Algo- rithm, Resource Allocation, Power Efficiency.

This paper studies a self-organized criticality model called sandpile for dynamically load-balancing tasks arriving in the form of Bag-of-Tasks in large-scale decentralized system. The sandpile is designed as a decentralized agent system characterizing a cellular automaton, which works in a critical state at the edge of chaos. Depending on the state of the cellular automaton, different responses may occur when a new task is assigned to a resource: it may change nothing or generate avalanches that reconfigure the state of the system. The abundance of such avalanches is in power-law relation with their sizes, a scale-invariant behavior that emerges without requiring tuning or control parameters. That means that large--catastrophic--avalanches are very rare but small ones occur very often. Such emergent pattern can be efficiently adapted for non-clairvoyant scheduling, where tasks are load balanced in computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. The algorithm design is experimentally validated showing that the sandpile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures.

International audience; In this paper, we simplify a Parallel Asynchronous Cellular Genetic Algorithm, by removing thread locks for shared memory access. This deliberate error aims to accelerate the algorithm, while preserving its search capability. Experiments with three benchmark problems show an acceleration, and even a slight improvement in search capability, with statistical significance.

International audience; This paper investigates the automatic parallelization of a heuristic for an NP-complete problem, with machine learning. The objective is to automatically design a new concurrent algorithm that finds solutions of comparable quality to the original heuristic. Our approach, called Savant, is inspired from the Savant syndrome. Its concurrency model is based on map-reduce. The approach is evaluated with the well-known Min-Min heuristic. Simulation results on two problem sizes are promising, the produced algorithm is able to find solutions of comparable quality.

International audience; The advantages of using structured populations in Evolutionary Algorithms (EAs) and other metaheuristicas are well known today, not only for parallelization purposes, but also for enhancing the performance of the algorithm with respect to the equivalent algorithm with panmictic population, even for sequential executions. The use of an appropriate population structure will allow us to create a higher efficiency and efficacy algorithm once structured, both numerically and in real time (e.g. parallelism). The articles composing this special issue represent excellent novel contributions in this direction. We collected six high-quality papers out of the 43 received ones. These finally selected papers deal with different aspects related to the topic of this special issue, such as theoretical studies, identification of current challenges in the field, novel population structure designs, and empirical validation on highly complex problems.

International audience; The development of large scale data center and cloud computing optimization models led to a wide range of complex issues like scaling, operation cost and energy efficiency. Different approaches were proposed to this end, including classical resource allocation heuristics, machine learning or stochastic optimization. No consensus exists but a trend towards using many-objective stochastic models became apparent over the past years. This work reviews in brief some of the more recent studies on cloud computing modeling and optimization, and points at notions on stability, convergence, definitions or results that could serve to analyze, respectively build accurate cloud computing models. A very brief discussion of simulation frameworks that include support for energy-aware components is also given.

International audience; Mobile ad hoc networks are infrastructure less communication networks that are spontaneously created by a number of mobile devices. Due to the highly fluctuating topology of such networks, finding the optimal configuration of communication protocols is a complex and crucial task. Additionally, different objectives must be usually considered. Small changes in the values of the parameters directly affects the performance of the protocol, promoting one objective while reducing another. Therefore, multi-objective optimisation is needed for fine tuning the protocol. In this work, we propose a novel parallel multi-objective local search that optimises an energy efficient broadcasting algorithm in terms of coverage, energy used, broadcasting time, and network resources. The proposed method looks for appropriate values for a set of 5 variables that markedly influence the behavior of the protocol to provide accurate tradeoff configurations in a reasonable short execution time. The new proposed algorithm is validated versus two efficient multi-objective evolutionary algorithms from the state of the art, offering comparable quality results in much shorter times.

Multi-objective evolutionary algorithms rely on the use of variation operators as their basic mechanism to carry out the evolutionary process. These operators are usually fixed and applied in the same way during algorithm execution, e.g., the mutation probability in genetic algorithms. This paper analyses whether a more dynamic approach combining different operators with variable application rate along the search process allows to improve the static classical behavior. This way, we explore the combined use of three different operators (simulated binary crossover, differential evolution’s operator, and polynomial mutation) in the NSGA-II algorithm. We have considered two strategies for selecting the operators: random and adaptive. The resulting variants have been tested on a set of 19 complex problems, and our results indicate that both schemes significantly improve the performance of the original NSGA-II algorithm, achieving the random and adaptive variants the best overall results in the bi- and three-objective considered problems, respectively.

International audience; This article presents a new parallel hybrid evolutionary algorithm to solve the problem of virtual machines subletting in cloud systems. The problem deals with the efficient allocation of a set of virtual machine requests from customers into available pre-booked resources from a cloud broker, in order to maximize the broker profit. The proposed parallel algorithm uses a distributed subpopulations model, and a Simulated Annealing operator. The experimental evaluation analyzes the profit and make span results of the proposed methods over a set of problem instances that account for realistic workloads and scenarios using real data from cloud providers. A comparison with greedy heuristics indicates that the proposed method is able to compute solutions with up to 133.8% improvement in the profit values, while accounting for accurate make span results.

This paper proposes a new selection scheme for Evolutionary Algorithms (EAs) based on altruistic cooperation between individuals. Cooperation takes place every time an individual undergoes selection: the individual decreases its own fitness in order to improve the mating chances of worse individuals. On the one hand, the selection scheme guarantees that the genetic material of fitter individuals passes to subsequent generations as to decrease their fitnesses individuals have to be firstly selected. On the other hand, the scheme restricts the number of times an individual can be selected not to take over the entire population. We conduct an empirical study for a parallel EA version where cooperative selection scheme is shown to outperform binary tournament: both selection schemes yield the same qualities of solutions but cooperative selection always improves the times to solutions.

This article introduces asynchronous implementations of selected synchronous cooperative co-evolutionary multi-objective evolutionary algorithms (CCMOEAs). The CCMOEAs chosen are based on the following state-of-the-art multi-objective evolutionary algorithms (MOEAs): Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). The cooperative co-evolutionary variants presented in this article differ from the standard MOEAs architecture in that the population is split into islands, each of them optimizing only a sub-vector of the global solution vector, using the original multi-objective algorithm. Each island evaluates complete solutions through cooperation, i.e., using a subset of the other islands current partial solutions. We propose to study the performance of the asynchronous CCMOEAs with respect to their synchronous versions and base MOEAs on well kown test problems, i.e. ZDT and DTLZ. The obtained results are analyzed in terms of both the quality of the Pareto front approximations and computational speedups achieved on a multicore machine.

In this work, we focus on vehicular ad hoc networks, also called VANETs, which are communication networks that devices (in this case vehicles) use to exchange messages in a decentralized fashion, i.e., using no preexisting infrastructure. We first assess the feasibility of relying on a tree-based topology management structure for mobile ad hoc networks and in particular for VANETs. Next, we enhance DAGRS, an existing decentralized model for enabling distributed tree management and build BODYF on it, an efficient broadcast algorithm. Several broadcasting algorithms of the state of the art are implemented in order to compare the performance of BODYF. The approach is validated by simulation through three realistic scenarios located in Luxembourg city: the city center for both pedestrian and vehicles, and a highway environment. The comparison is made in terms of the coverage achieved by the broadcasting process as well as the complexity of the messages. DAGRS/BODYF approach outperforms other existing protocols in terms of both the number of devices reached and the network use.

The resolution of complex problems requires the use of advanced approximate algorithms and huge computational resources to find accurate solutions in reasonable time. Computing clusters, as well as GPGPUs, grids, and cloud computing infrastructures arise as appropriate innovative computing platforms to implement and execute such algorithms and find accurate solutions to complex problems arising in many application areas. This special issue contains extended versions of the best papers presented in HPCLATAM-2012 and SCCG-2012 conferences, as well as other novel contributions. In total, 27 papers were submitted to the special issue, from which only 10 were finally accepted for publication. These are outstanding contributions proposing novel designs of highly efficient parallel algorithms to solve complex problems, or dealing with salient problems in the fields of grid and cloud computing. In the first paper of this compilation, “Approximating Static List Schedules in Dynamic Multithreaded Applications”, Camargo et al. propose in their contribution the use of list algorithms to optimally schedule algorithms in a multi-thread environment. The difficulty of the approach deals with the fact that a dynamic environment is considered, and no assumptions are assumed to be known about the programs. A novel algorithm is presented to build a directed cyclic graph representing a multithread program from a data flow description, in form of a directed acyclic graph. Several