Search

Content Distribution Networks (CDN) are key for providing worldwide services and content to end-users. In this work, we propose three multiobjective evolutionary algorithms for solving the problem of designing and optimizing cloud-based CDNs. We consider the objectives of minimizing the total cost of the infrastructure (including virtual machines, network, and storage) and the maximization of the quality-of-service provided to end-users. The proposed model considers a multi-tenant approach where a single cloud-based CDN is able to host multiple content providers using a resource sharing strategy. The proposed evolutionary algorithms address the offline problem of provisioning infrastructure resources while a greedy heuristic method is proposed for addressing the online problem of routing contents. The experimental evaluation of the proposed methods is performed over a set of realistic problem instances. Results indicate that the proposed approach is effective for designing and optimizing cloud-based CDNs reducing total costs by up to 10.3% while maintaining an adequate quality of service.

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.

The study of dynamic multi-objective optimization problems (DMOP) is an area that has recently been receiving increased attention from researchers. Within the literature, various alternatives have been proposed to solve DMOPs, among them are the dynamic multi-objective evolutionary algorithms (DMOEA), which use stochastic methods to obtain solutions close to the optimum. With the constant proposal of new DMOPs with different challenges and properties, as well as DMOEAs to solve them, the issue of determining which alternatives are adequate for each problem arises. Hyper-heuristics are methodologies that use multiple heuristics to solve a problem. This allows them to effectively cover a wider spectrum of characteristics of optimization problems. This advantage also involves DMOPs, since a suitable hyper-heuristic can satisfactorily solve a greater number of problems compared to DMOEAs used individually. This paper presents a guide, as well as a checklist to support researchers in the design of hyper-heuristics to solve DMOPs using DMOEAs as their heuristics. This work also presents two case studies which include state-of-the-art proposals that follow each step of the proposed guide, the obtained results were efficient and satisfactory, which shows the effectiveness of this guide.

Several previous works have shown how using prior knowledge within machine learning models helps to overcome the curse of dimensionality issue in high dimensional settings. However, most of these works are based on simple linear models (or variations) or do make the assumption of knowing a pre-defined variable grouping structure in advance, something that will not always be possible. This paper presents a hybrid genetic algorithm and machine learning approach which aims to learn variables grouping structure during the model estimation process, thus taking advantage of the benefits introduced by models based on problem-specific information but with no requirement of having a priory any information about variables structure. This approach has been tested on four synthetic datasets and its performance has been compared against two well-known reference models (LASSO and Group-LASSO). The results of the analysis showed how that the proposed approach, called GAGL, considerably outperformed LASSO and performed as well as Group-LASSO in high dimensional settings, with the added benefit of learning the variables grouping structure from data instead of requiring this information a priory before estimating the model.

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.

This work addresses the multi-objective resource provisioning problem for building cloud-based CDNs. The optimization objectives are the minimization of VM, network and storage cost, and the maximization of the QoS for the end-user. A brokering model is proposed such that a single cloud-based CDN is able to host multiple content providers applying a resource sharing strategy. Following this model, an offline multiobjective evolutionary approach is applied to optimize resource provisioning while a greedy heuristic is proposed for addressing online routing of content. Experimental results indicate the proposed approach may reduce total costs by up to 10.6% while maintaining high QoS values.

This article presents and evaluates twenty-four novel bi-objective efficient heuristics for the simultaneous optimization of makespan and robustness in the context of the static robust tasks mapping problem for datacenters. The experimental analysis compares the proposed methods over realistic problem scenarios. We study their accuracy, as well as the regions of the search space they explore, by comparing versus state-of-the-art Pareto fronts, obtained with four different specialized versions of well-known multi-objective evolutionary algorithms.

This chapter analyzes the use of adaptive neighborhoods based on coalitions in evolutionary optimization frameworks. First, we introduce the concepts of evolutionary algorithms, population topologies and coalitions. We integrate all these topics to study how to avoid some of the drawbacks of previous evolutionary algorithms and to remove their typically required parameters. The main contribution of the chapter is a redefinition of the Evolutionary Algorithm with Coalitions (EACO), which uses cellular approaches with neighborhoods, allowing the formation of coalitions among cells as a way to create islands of evolution in order to preserve diversity. This idea speeds up the evolution of individuals grouped in high-quality coalitions that are quickly converging to promising solutions. In the results section, we successfully compare EACO with a canonical cGA (Cellular Genetic Algorithm), and provide evidences about the statistical significance of our results. We also analyze the influence of parameters in order to tune them up accordingly; and finally, we evaluate the performance of EACO under different complex network topologies.

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.

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.

Energy consumption is one of the main concerns in mobile ad hoc networks (or MANETs). The lifetime of its devices highly depends on the energy consumption as they rely on batteries. The adaptive enhanced distance based broadcasting algorithm, AEDB, is a message dissemination protocol for MANETs that uses cross-layer technology to highly reduce the energy consumption of devices in the process, while still providing competitive performance in terms of coverage and time. We use two different multi-objective evolutionary algorithms to optimize the protocol on three network densities, and we evaluate the scalability of the best found AEDB configurations on larger networks and different densities.

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.

Differential evolution (DE) algorithms compose an efficient type of evolutionary algorithm (EA) for the global optimization domain. Although it is well known that the population structure has a major influence on the behavior of EAs, there are few works studying its effect in DE algorithms. In this paper, we propose and analyze several DE variants using different panmictic and decentralized population schemes. As it happens for other EAs, we demonstrate that the population scheme has a marked influence on the behavior of DE algorithms too. Additionally, a new operator for generating the mutant vector is proposed and compared versus a classical one on all the proposed population models. After that, a new heterogeneous decentralized DE algorithm combining the two studied operators in the best performing studied population structure has been designed and evaluated. In total, 13 new DE algorithms are presented and evaluated in this paper. Summarizing our results, all the studied algorithms are highly competitive compared to the state-of-the-art DE algorithms taken from the literature for most considered problems, and the best ones implement a decentralized population. With respect to the population structure, the proposed decentralized versions clearly provide a better performance compared to the panmictic ones. The new mutation operator demonstrates a faster convergence on most of the studied problems versus a classical operator taken from the DE literature. Finally, the new heterogeneous decentralized DE is shown to improve the previously obtained results, and outperform the compared state-of-the-art DEs.

We propose the use of a new algorithm to solve multiobjective optimization problems. Our proposal adapts the well-known scatter search template for single-objective optimization to the multiobjective domain. The result is a hybrid metaheuristic algorithm called Archive-Based hYbrid Scatter Search (AbYSS), which follows the scatter search structure but uses mutation and crossover operators from evolutionary algorithms. AbYSS incorporates typical concepts from the multiobjective field, such as Pareto dominance, density estimation, and an external archive to store the nondominated solutions. We evaluate AbYSS with a standard benchmark including both unconstrained and constrained problems, and it is compared with two state-of-the-art multiobjective optimizers, NSGA-II and SPEA2. The results obtained indicate that, according to the benchmark and parameter settings used, AbYSS outperforms the other two algorithms as regards the diversity of the solutions, and it obtains very competitive results according to the convergence to the true Pareto fronts and the hypervolume metric.

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

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.

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.

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.

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.

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.

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.

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.

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.

We propose a new parallel asynchronous cellular genetic algorithm for multi-core processors. The algorithm is applied to the scheduling of independent tasks in a grid. Finding such optimal schedules is in general an NP-hard problem, to which evolutionary algorithms can find near-optimal solutions. We analyze the parallelism of the algorithm, as well as different recombination and new local search operators. The proposed algorithm improves previous schedules on benchmark problems. The parallelism of this algorithm suits it to bigger problem instances.

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.

A new class of estimation of distribution algorithms (EDAs), known as cellular EDAs (cEDAs), has recently emerged. In these algorithms, the population is decentralized by partitioning it into many small collaborating subpopulations, arranged in a toroidal grid, and interacting only with its neighboring subpopulations. In this work, we study the simplest cEDA —the cellular univariate marginal distribution algorithm (cUMDA). In an attempt to explain its behaviour, we extend the well known takeover time analysis usually applied to other evolutionary algorithms to the field of EDAs. We also give in this work empirical arguments in favor of using the cUMDAs instead of its centralized equivalent.

Mobile Ad-hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such scenario, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcasting strategy in MANETs is a multiobjective problem accounting for three goals: reaching as many stations as possible, minimizing the network utilization, and reducing the makespan. In this paper, we face this multiobjective problem with a state-of-the-art multiobjective scatter search algorithm called AbSS (Archive-based Scatter Search) that computes a Pareto front of solutions to empower a human designer with the ability of choosing the preferred configuration for the network. Results are compared against those obtained with the previous proposal used for solving the problem, a cellular multiobjective genetic algorithm (cMOGA). We conclude that AbSS outperforms cMOGA with respect to three different metrics.

Cellular Genetic Algorithms (cGA) are spatially distributed Genetic Algorithms that, because of their high level of diversity, are superior to regular GAs on several optimization functions. Also, since these distributed algorithms only require communication between few closely arranged individuals, they are very suitable for a parallel implementation. We propose a new kind of cGA, called hierarchical cGA (H-cGA), where the population structure is augmented with a hierarchy according to the current fitness of the individuals. Better individuals are moved towards the center of the grid, so that high quality solutions are exploited quickly, while at the same time new solutions are provided by individuals at the outside that keep exploring the search space. This algorithmic variant is expected to increase the convergence speed of the cGA algorithm and maintain the diversity given by the distributed layout. We examine the effect of the introduced hierarchy by observing the variable takeover rates at different hierarchy levels and we compare the H-cGA to the cGA algorithm on a set of benchmark problems and show that the new approach performs promising.

In This work we study cellular evolutionary algorithms, a kind of decentralized heuristics, and the importance of the induced exploration/exploitation balance on different problems. It is shown that, by choosing synchronous or asynchronous update policies, the selection pressure, and thus the exploration/exploitation tradeoff, can be influenced directly, without using additional ad hoc parameters. Synchronous algorithms of different neighborhood-to-topology ratio, and asynchronous update policies are applied to a set of benchmark problems. Our conclusions show that the update methods of the asynchronous versions, as well as the ratio of the decentralized algorithm, have a marked influence on its convergence and on its accuracy.

Cellular Genetic Algorithms (cGAs) are a subclass of Genetic Algorithms (GAs) in which the population diversity and exploration are enhanced thanks to the existence of small overlapped neighborhoods. Such a kind of structured algorithms is specially well suited for complex problems. In this paper we propose the utilization of some cGAs with and without including local search techniques for solving the vehicle routing problem (VRP). A study on the behavior of these algorithms has been performed in terms of the quality of the solutions found, execution time, and number of function evaluations (effort). We have selected the benchmark of Christofides, Mingozzi and Toth for testing the proposed cGAs, and compare them with some other heuristics in the literature. Our conclusions are that cGAs with an added local search operator are able of always locating the optimum of the problem at low times and reasonable effort for the tested instances.