Search

Distributed parallel computing platforms contribute for a large part to some of the most powerful computers. Such architectures are typically based on accelerators (General Purpose computing on Graphics Processing Units, Many Integrated Cores e.g. Xeon Phi co-processors) and/or a large number of interconnected computing nodes. Obviously, they raise new challenges, typically in terms of scalability, robustness, adaptability and security. At the advent of the quest for Ultra scale Computing Systems, this paper addresses the issue of fault tolerance toward Byzantine failures over's such platforms. Indeed, the inherent unpredictable nature of these errors render their detection, not speaking of their correction, hard or even impossible to perform at large-scale. At this level, Algorithm-Based Fault Tolerance (ABFT) techniques where the fault tolerance scheme is tailored to the algorithm performed, seems the most promising approaches to deal with such failures. In this context, Evolutionary Algorithms (EAs), especially panmictic global parallel EAs, exhibit a remarkable resilience against byzantine failures modeled as cheating faults as demonstrated either empirically or theoretically in previous studies. In this paper, we extend this analysis to the case of distributed EAs based on the cellular model leading to distributed Cellular Evolutionary Algorithms (dCEAs). Our empirical study over a set or reference optimization problem confirm the ABFT nature of dCEAs. To our knowledge, this is the first study of dCEAs under the perspective of cheating issues and crash faults in a domain of distributed computations, thus opening new insights and perspectives for the design of competitive ultra-scale system based on evolutionary programming models.

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 chapter is focused on the problem of scheduling independent tasks on heterogeneous machines. The main contributions of our work are the following: a linear programming model to compute energy consumption for the execution of independent tasks on heterogeneous clusters, a constructive heuristic based on local search, and a new benchmark set. To assess our approach we compare the performance of two solution methods: a memetic algorithm, based on population search and local search, and a seeded genetic algorithm, based on NSGA-II. A Wilcoxon rank-sum test shows significant differences in the diversity of solutions found but not in hypervolume. The memetic algorithm gets the best diversity for a bigger instance set from the state of the art.

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).

International audience; This article presents a two-level strategy for scheduling large workloads of parallel applications in multicore distributed systems, taking into account the minimization of both the total computation time and the energy consumption of solutions. Nowadays, energy efficiency is of major concern when using large computing systems such as cluster, grid, and cloud computing facilities. In the approach proposed in this article, a combination of higher-level (i.e., between distributed systems) and lower-level (i.e., within each data-center) schedulers are studied for finding efficient mappings of workflows into the resources in order to maximize the quality of service, while reducing the energy required to compute them. The experimental evaluation demonstrates that accurate schedules are computed by using combined list scheduling heuristics (accounting for both problem objectives) in the higher level, and ad-hoc scheduling techniques to take advantage of multicore infrastructures in the lower level. Solutions are also evaluated with two user- and administrator-oriented metrics. Significant improvements are reported on the two problem objectives when compared with traditional load-balancing and round-robin techniques.

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.

Describes how evolutionary algorithms (EAs) can be used to identify, model, and minimize day-to-day problems that arise for researchers in optimization and mobile networking Mobile ad hoc networks (MANETs), vehicular networks (VANETs), sensor networks (SNs), and hybrid networks—each of these require a designer’s keen sense and knowledge of evolutionary algorithms in order to help with the common issues that plague professionals involved in optimization and mobile networking. This book introduces readers to both mobile ad hoc networks and evolutionary algorithms, presenting basic concepts as well as detailed descriptions of each. It demonstrates how metaheuristics and evolutionary algorithms (EAs) can be used to help provide low-cost operations in the optimization process—allowing designers to put some “intelligence” or sophistication into the design. It also offers efficient and accurate information on dissemination algorithms topology management, and mobility models to address challenges in the field. Evolutionary Algorithms for Mobile Ad Hoc Networks : Instructs on how to identify, model, and optimize solutions to problems that arise in daily research Presents complete and up-to-date surveys on topics like network and mobility simulators Provides sample problems along with solutions/descriptions used to solve each, with performance comparisons Covers current, relevant issues in mobile networks, like energy use, broadcasting performance, device mobility, and more Evolutionary Algorithms for Mobile Ad Hoc Networks is an ideal book for researchers and students involved in mobile networks, optimization, advanced search techniques, and multi-objective optimization.

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.

The multi-objective optimization methods are traditionally based on Pareto dominance or relaxed forms of dominance in order to achieve a representation of the Pareto front. However, the performance of traditional optimization methods decreases for those problems with more than three objectives to optimize. The decomposition of a multi-objective problem is an approach that transforms a multi-objective problem into many single-objective optimization problems, avoiding the need of any dominance form. This chapter provides a short review of the general framework, current research trends and future research topics on decomposition methods.

Due to the highly unpredictable topology of ad hoc networks, most of the existing communication protocols rely on different thresholds for adapting their behavior to the environment. Good performance is required under any circumstances. Therefore, finding the optimal configuration for those protocols and algorithms implemented in these networks is a complex task. We propose in this work to automatically fine tune the AEDB broadcasting protocol for MANETs thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. AEDB is an advanced adaptive protocol based on the Distance Based broadcasting algorithm that acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. In this work, it will be fine tuned using multi-objective techniques in terms of the conflicting objectives: coverage, energy and network resources, subject to a broadcast time constraint. Because of the few parameters of AEDB, we defined new versions of the problem in which variables are discretized into bit-strings, making it more suitable for cooperative coevolutionary algorithms. Two versions of the proposed method are evaluated and compared versus the original NSGA-II, providing highly accurate tradeoff configurations in shorter execution times.

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; 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.

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. In order to face this new multi-objective optimisation problem, the NSGAII algorithm was used on realistic instances in the city-centre of Luxembourg. The accurate tradeoff solutions found by NSGAII (assuming global knowledge of the network) will permit to better know and understand the problem. This will later ease the design of decentralised solutions to be used in real environments, as well as their future validation.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithms (GAs) with decentralized population in which interactions among individuals are restricted to the closest 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, the use of decentralized populations 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. Hence, in this work we propose a new adaptive technique based in Cellular Automata, Game Theory and Coalitions that allow to manage dynamic neighborhoods. As a result, the new adaptive cGAs (EACO) with coalitions outperform the compared cGA with fixed neighborhood for the selected benchmark of combinatorial optimization problems.

A Self-organizing Map (SOM) is a competitive learning neural network architecture that make available a certain amount of classificatory neurons, which self-organize spatially based on input patterns. In this paper we explore the use of complex network topologies, like small-world, scale-free or random networks; for connecting the neurons within a SOM, and apply them for Time Series Prediction (TSP).We follow the classical VQTAMmodel for function prediction, and consider several benchmarks to evaluate the quality of the predictions. The results presented in this work suggest that the most regular the network topology is, the better results it provides in prediction. Besides, we have found that not updating all the cells at the same time provides much better results.

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 decentralized and self-organized agent system for dynamically load-balancing tasks arriving in the form of Bags-of-Tasks (BoTs) in large-scale decentralized systems. the approach is inspired by the emergent behavior of the sand pile model, a cellular automaton behaving at the edge of chaos. Depending on the state of the cellular automaton, rather 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 proportion between the abundance of avalanches and their sizes shows a power-law relation, a scale-invariant behavior that does not need to be tuned. That means that large - catastrophic - avalanches are very rare but small ones occur very often. Such a smart and emergent behavior fits well with the idea of non-clairvoyant scheduling, where tasks are load balanced into computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. in order to study the viability of the approach, we have conducted an empirical experimentation which shows that the sand pile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures.

Energy systems are not only real-world systems; they are also one of the most important foundations of the modern world. Especially with the upcoming required changes to make more efficient use of energy and to shift towards a global use of sustainable, green energy sources, there are many challenges in mathematics and computer science. Thus, with the current increase in living standards, diminishing natural resources and environmental concerns, the management of energy production and use became one of the most important global issues today.First, on the consumer side, there is an increasing need for more efficient, smart uses of energy, be it in large-scale computing systems and data warehouses, in homes or in office buildings. Second, on the producer side, there is a push toward the use of sustainable, green, energy sources, which are often less reliable, e.g. wind energy. In addition, future energy systems are often envisioned to be "smart", consisting of massive amounts of small generators, such as solar panels, located at consumers, effectively turning consumers into potential producers whenever they have a surplus of energy. The management, control and planning of, and efficient use of energy in (future) energy systems brings about as many important questions. Real-world challenges, such as those arising in (future) energy systems, are\ typically highly complex because of the many aspects to be considered that are often disregarded in theoretical research such as dynamic changes, uncertainty and multiple objectives. In many situations therefore, problem-specific algorithms are infeasible or impractical. Instead, flexible and powerful approaches such as evolutionary algorithms (EAs) can often provide viable solutions. Typical real-world challenges that are addressed by EAs are of the optimization type. This covers the use of EAs to optimize issues ranging from energy consumption (e.g. scheduling, memory/storage management, communication protocols, smart sensors, etc.) to the planning and design of energy systems at many levels, ranging from small printed circuit boards to entire transmission networks.The aim of this workshop is therefore to bring together researchers interested in addressing challenging issues related to the use of evolutionary computation for applications in (future) energy systems. The workshop is a follow up of the GreenIT Evolutionary Computation workshop held at GECCO 2011.

The use of small-world graphs as a topology structure for the population of Evolutionary Algorithms (EAs) has been recently proposed in the literature. The motivation is clear: the high clustering coefficient and low characteristic path length of such networks makes them suitable for fast local information dissemination, while at the same time preventing it from quickly spreading on the whole population, as it happens in panmictic populations. However, even though several papers addressed this issue so far, only a few of them are able to provide competitive results with other panmictic and/or decentralized population EAs with similar configurations. Therefore, we perform ax study in this work, both theoretically and empirically, on the most appropriate mechanisms to generate SW topologies for Genetic Algorithms (a family of EA). The algorithms are analyzed in terms of efficiency and efficacy, and the best studied variant is validated versus other GAs using well known centralized and decentralized population structures, outperforming them.

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.

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, the use of decentralized populations 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. Hence, we propose in this work two new adaptive techniques that allow removing the neighborhood to use from the algorithm's configuration. As a result, one of the new adaptive cGAs outperform the compared cGAs with fixed neighborhoods in the continuous and combinatorial domains.

This chapter proposes a novel Grid-based scheduling algorithm that optimizes both computation and communications costs of workflow applications. Based on a hierarchical two-steps optimization process, a super scheduler first applies a Recursive Convex Clustering Algorithm (RCCA) that efficiently clusters tasks while minimizing communication costs. In the second step, a resource-broker assigns the generated convex sets to resources clusters. Local schedulers then optimize the makespan for the group of tasks assigned to their cluster, using a graphic processing unit (GPU)-based parallel cellular Genetic Algorithm(cGA). The performance improvement brought by this novel two-step scheduling algorithm compared to a hierarchical list-scheduling approach is empirically demonstrated on different real-world workflow applications.

This chapter introduces three new multi-objective cooperative coevolutionary variants of three state-of-the-art multi-objective evolutionary algorithms, namely, Nondominated 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, 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 the performance of the coevolutionary multi-objective approaches in two different contexts: continuous and combinatorial optimization. In the first case we deal with a set of well-known benchmark problems, while in the the second one we conduct a study about 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 have made 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.

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

We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

In modern parallel and distributed systems, inter-processor communications are a crucial factor of performance. The time for exchanging data is usually larger than that for computing elementary operations. Consequently, these communications slow down the execution of the application scheduled on the computing platform. Accounting for these communications is essential for attaining efficient hardware and software utilization. Moreover, energy dissipation due to the transfer of data between processing elements has become a major concern. Therefore, in this paper we develop an energy-aware static algorithm, which intrinsically optimizes the energy consumption due to the transfer of data in a distributed system. This is achieved by properly allocating and scheduling the tasks that constitute the applications on the processing elements, minimizing inter-processor communications. The proposed algorithm is a new Cellular Genetic Algorithm based on task clustering techniques. That is, the genetic operators work considering groups of tasks instead of applying them directly on the tasks. Simulation results showed that this algorithm is very compelling in terms of application completion time, inter-processor communication and energy communication dissipation.

Differential Evolution (DE) algorithms are efficient Evolutionary Algorithms (EAs) for the continuous optimization domain. There exist a large number of DE variants in the literature. In this paper, we analyze the effect of adding a cellular structure to the population of some of the most outstanding existing ones. The original algorithms will be compared versus their equivalent versions with cellular population both in terms of accuracy and convergence speed. As a result, we conclude that the cellular versions of the algorithms perform, in general, better than the equivalent state-of-the-art ones in the two considered issues.

We deal in this paper with the important problem of partitioning in ad hoc networks. In our approach, we assume that some devices might have other communication interfaces rather than Wi-Fi and/or Bluetooth allowing to connect remote devices (e.g., technologies such as GPRS or HSDPA). This would allow us to build hybrid networks for overcoming the network partitioning. Hence, the problem considered in this work is to establish remote links between devices (called bypass links) in order to maximize the QoS of the network by optimizing its properties to make it small world. Additionally, the number of this kind of links in the network should be minimized as well, since we consider that not all the devices have these communication capabilities, or it could be a requirement to minimize the use of the long range network (for example, in the case its use supposes some cost). We face the problem with four different GAs (both parallel and sequential) and compare their behaviors on six different network instances. All the algorithms were tested with a new encoding of the problem, which is demonstrated to provide more accurate results than the previously existing one.

Cellular genetic algoritms (cGAs) are characterized by its grid structure population, in which individuals can only interact with their neighbors. This kind of algorithms has demonstrated to have a high numerical performance thanks to the good exploration/exploitation balance they perform in the search space. Although cGAs seem very appropriate for parallelism, there is a low number of works proposing or studing parallel models for clusters of computers. This is probably because the model requires a high communication level between sub-populations due to the tight interactions among individuals. These parallel versions are however needed to cope with the high computational requirements of the current real-world problems. This article proposes a new parallel cellular genetic algorithm which maintains (or even improves because its asynchronicity) the numerical behaviour of a serial cGA, while at the same time it provokes an important reduction on the execution time for finding the optimal solution.

VANETs are ad hoc networks in which devices are vehicles moving at high speeds. This kind of network is getting more and more importance since it has many practical and important applications, like multimedia file sharing (e.g., maps, music, news, weather), or dissemination of alarm messages (e.g., accidents, traffic jams, bad road conditions). One important problem faced in ad hoc networks is network partitioning, causing the formation of isolated clusters, and preventing devices in different clusters from communicating. Usually, devices composing the ad hoc network are provided with other communication interfaces rather than Wi-Fi and/or Bluetooth that allow them to connect to remote devices, such as GPRS/HSDPA. Additionally, there exists some network infrastructure in cities or roads that could be used by VANETs (e.g. hotspots). By taking advantage of these technologies and infrastructures, devices could be able to form a hybrid network, establishing remote links between them (called bypass links) in order to improve the network connectivity by joining, for example, separate clusters. In this work, we face the problem of optimizing the number and location of these remote connections for maximizing the QoS of the network. We use an efficient genetic algorithm with structured population, called cellular genetic algorithm (cGA), to optimize this hard problem. The evaluation of the quality of the network connectivity is made using small world properties. Our goal is to find highly accurate solutions (that could be used as reference values for future works) and then analyze the influence of the quality of the solutions in the real behavior of the network. This is achieved by using the JANE simulator to disseminate a message in the network using two broadcasting protocols having different features.

The DNA fragment assembly problem is to re construct a DNA chain from multiple fragments that have previously been sequenced in a laboratory. This is a critical step in any genomic project, since the resulting chains are the basis of all the work. Therefore, the quality of these chains is a prime importance to the correct development of the project. The methods typically applied to this problem usually encounter difficulties on large instances, so more efficient techniques are necessary. In this context, this work proposes a new method combining a general purpose metaheuristic (an advanced cellular genetic algorithm which automatically regulates the intensity of the search) with a local search method specifically designed for this problem (PALS). This local search method (recently published) finds very accurate solutions in very short times. As a result, our proposal is a very accurate and efficient hybrid technique clearly outperforming the other existing ones.

The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications. The scheduling problem is computationally hard even when there are no dependencies among jobs. Thus, we present in this paper a new tabu search (TS) algorithm for the problem of batch job scheduling on computational grids. We consider the job scheduling as a bi-objective optimization problem consisting of the minimization of the makespan and flowtime. The bi-objectivity is tackled through a hierarchic approach in which makespan is considered a primary objective and flowtime a secondary one. An extensive experimental study has been first conducted in order to fine-tune the parameters of our TS algorithm. Then, our tuned TS is compared versus two well known TS algorithms in the literature (one of them is hybridized with an ant colony optimization algorithm) for the problem. The computational results show that our TS implementation clearly outperforms the compared algorithms. Finally, we evaluated the performance of our TS algorithm on a new set of instances that better fits with the concept of computational grid. These instances are composed of a higher number of -heterogeneous- machines (up to 256) and emulate the dynamic behavior of these systems.