Search

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.

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.

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

This 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 sequencing process of a DNA chain for reading its components supposes a complex process, since only small DNA fragments can be read nowadays. Therefore, the use of optimization algorithms is required to rebuild a single chain from all the small pieces. We address here a simplified version of the problem, in which no errors in the sequencing process are allowed. The methods typically used in the literature for this problem are not satisfactory when solving realistic size instances, so there is a need for new more efficient and accurate methods. We propose a new iterated local search algorithm, highly competitive with the best algorithms in the literature, and considerably faster.

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.

Satellites to car multimedia content delivery systems, such as KU Mobile, are a promising area for research and development. With vehicles becoming more computational and communicative, the demand for bringing multimedia and information technology services into vehicles is raising. However, these systems suffer from significant signal fading and incomplete reception caused by obstacles along the road interrupting the mandatory line of sight between satellite and car while these two are communicating. Therefore, additional technologies need to be specifically designed to complete partially received information in such scenarios. In this paper we propose xChangeMobile, an inter-vehicular ad-hoc wireless network (VANET) content exchange system. It is composed by two novel communication protocols, VanetDFCN and ChunkXChange, designed specifically for this scenario. Finally, using multi-objective genetic algorithms, we optimized the main parameters of proposed protocols to achieve the best communication performances.

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.

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.