Search

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

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.

In this chapter, an analytical parameter tuning for the Archive Multi-Objective Simulated Annealing (AMOSA) with a fuzzy logic controller is proposed. The analytical tuning is used to compute the initial and final temperature, as well as the maximum metropolis length. The fuzzy logic controller is used to adjust the metropolis length for each temperature. These algorithms are used to solve the Heterogeneous Computing Scheduling Problem. The tuned AMOSA with a fuzzy logic controller is compared against an AMOSA without tuning. Three quality indicators are used to compare the performance of the algorithms, these quality indicators are hypervolume, generational distance, and generalized spread. The experimental results show that the tuned AMOSA with fuzzy logic controller achieves the best performance.

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

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

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

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

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

This paper presents a new parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. SMPSO adopts a strategy for limiting the velocity of the particles that prevents them from having erratic movements. This characteristic provides the algorithm with a high degree of reliability. The proposed approach, called CCSMPSO, is based on a new design and implementation of SMPSO in a cooperative coevolutionary (CC) framework. In such an architecture, the population is split into several subpopulations, which are in turn in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. We compare our work with two different state-of-the-art multi-objective CC metaheuristics, namely CCNSGA-II and CCSPEA2, as well as the original SMPSO in order to demonstrate its effectiveness. Our experiments indicate that our proposed solution, CCSMPSO, offers significant computational speedups, a higher convergence speed and better and comparable results in terms of solution quality, when compared to the other two CC algorithms and SMPSO, respectively. Three different criteria are used for making the comparisons, namely the quality of the resulting approximation sets, average computational time and the convergence speed to the Pareto front.

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.

The sensitivity analysis of a Cellular Genetic Algorithm (CGA) with local search is used to design a new and faster heuristic for the problem of mapping independent tasks to a distributed system (such as a computer cluster or grid) in order to minimize makespan (the time when the last task finishes). The proposed heuristic improves the previously known Min-Min heuristic. Moreover, the heuristic finds mappings of similar quality to the original CGA but in a significantly reduced runtime (1,000 faster). The proposed heuristic is evaluated across twelve different classes of scheduling instances. In addition, a proof of the energy-efficiency of the algorithm is provided. This convergence study suggests how additional energy reduction can be achieved by inserting low power computing nodes to the distributed computer system. Simulation results show that this approach reduces both energy consumption and makespan.

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.

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

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.

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.

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.

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.

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

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.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithm (GA) — population based heuristic — with a structured population so that each individual can only interact with its neighbors. The existence of small overlapped neighborhoods in this decentralized population provides both diversity and opportunities for exploration, while the exploitation of the search space is strengthened inside each neighborhood. This balance between intensification and diversification makes cGAs naturally suitable for solving complex problems. In this chapter, we solve a large benchmark (composed of 160 instances) of the Capacitated Vehicle Routing Problem (CVRP) with a cGA hybridized with a problem customized recombination operation, an advanced mutation operator integrating three mutation methods, and two well-known local search algorithms for routing problems. The studied test-suite contains almost every existing instance for CVRP in the literature. In this work, the best-so-far solution is found (or even improved) in 80% of the tested instances (126 out of 160), and in the other cases (20%, i.e. 34 out of 160) the deviation between our best solution and the best-known one is always very low (under 2.90%). Moreover, 9 new best-known solutions have been found.

In this paper we study a number of issues related to the design of a cellular genetic algorithm (cGA) for multiobjective optimization. We take as an starting point an algorithm following the canonical cGA model, i.e., each individual interacts with those ones belonging to its neighborhood, so that a new individual is obtained using the typical selection, crossover, and mutation operators within this neighborhood. An external archive is used to store the non-dominated solutions found during the evolution process. With this basic model in mind, there are many different design issues that can be faced. Among them, we focus here on the synchronous/asynchronous feature of the cGA, the feedback of the search experience contained in the archive into the algorithm, and two different replacement strategies. We evaluate the resulting algorithms using a benchmark of problems and compare the best of them against two state-of-the-art genetic algorithms for multiobjective optimization. The obtained results indicate that the cGA model is a promising approach to solve this kind of problem.

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.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithm (GA) – population based heuristic– with a structured population so that individuals can only interact with their neighbors. The existence of small overlapped neighborhoods in this decentralized population provides both diversity and exploration, while the exploitation of the search space is strengthened inside each neighborhood. This balance between exploration and exploitation makes cGAs naturally suitable for solving complex problems. In this paper we tackle the minimization of a number of problems (both academic and from the real world) with a real-coded cGA, called JCell. The results show that JCell improves the compared algorithms for a number of the studied problems, thus increasing the overall performance with respect to other complex heterogeneous distributed GAs, belonging to the state-of-the-art in continuous optimization.