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.

Communication networks and systems are continuously threatened by a great variety of cybersecurity attacks coming from new malware that targets old and new systems’ vulnerabilities. In this sense, Intrusion Detection Systems (IDSs) and, specifically, Network IDSs (NIDSs) are used to count on robust methods and techniques to detect and classify security attacks. One of the important parts in the assessment of NIDSs, is the Feature Engineering (FE) process, where raw datasets are transformed onto derived ones where both, features and observations are smartly transformed. In this work, the ff4ml framework, which includes the Feature as a Counter (FaaC) FE approach, is used to transform raw features into new ones that are counters of the originals. The FaaC approach aggregates raw observations by time intervals, thus limiting its use to network datasets containing timestamps. This work proposes a batch-based aggregation technique that allows applying FaaC in timestamp-less datasets and analyzes its impact on the performance of Machine Learning (ML)-based NIDSs in comparison to timestamp-based aggregation approaches.

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 IEEE Workshop on Parallel / Distributed Combinatorics and Optimization aims at providing a forum for scientific researchers and engineers on recent advances in the field of parallel or distributed computing for difficult combinatorial optimization problems, like 0–1 multidimensional knapsack problems, cutting stock problems, scheduling problems, large scale linear programming problems, nonlinear optimization problems and global optimization problems. Emphasis is placed on new techniques for the solution of these difficult problems like cooperative methods for integer programming problems. Techniques based on metaheuristics and nature-inspired paradigms are considered. Aspects related to Combinatorial Scientific Computing (CSC) are considered. In particular, we solicit submissions of original manuscripts on sparse matrix computations, graph algorithm and original parallel or distributed algorithms. The use of new approaches in parallel and distributed computing like GPU, MIC, FPGA, volunteer computing are considered. Application to cloud computing, planning, logistics, manufacturing, finance, telecommunications and computational biology are considered.

Presently, we are living in a hyper-connected world where millions of heterogeneous devices are continuously sharing information in different application contexts for wellness, improving communications, digital businesses, etc. However, the bigger the number of devices and connections are, the higher the risk of security threats in this scenario. To counteract against malicious behaviours and preserve essential security services, Network Intrusion Detection Systems (NIDSs) are the most widely used defence line in communications networks. Nevertheless, there is no standard methodology to evaluate and fairly compare NIDSs. Most of the proposals elude mentioning crucial steps regarding NIDSs validation that make their comparison hard or even impossible. This work firstly includes a comprehensive study of recent NIDSs based on machine learning approaches, concluding that almost all of them do not accomplish with what authors of this paper consider mandatory steps for a reliable comparison and evaluation of NIDSs. Secondly, a structured methodology is proposed and assessed on the UGR’16 dataset to test its suitability for addressing network attack detection problems. The guideline and steps recommended will definitively help the research community to fairly assess NIDSs, although the definitive framework is not a trivial task and, therefore, some extra effort should still be made to improve its understandability and usability further., The authors would like to acknowledge the Spanish Ministerio de Ciencia, Innovación y Universidades and ERDF for the support provided under contracts RTI2018-100754-B-I00 (iSUN) and RTI2018-098160-B-I00 (DEEPAPFORE).

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.

Dynamic optimization problems have attracted the attention of researchers due to their wide variety of challenges and their suitability for real-world problems. The application of hyper-heuristics to solve optimization problems is another area that has gained interest recently. These algorithms can apply a search space exploration method at different stages of the execution for finding high quality solutions. However, most of the proposed works using these methodologies do not focus on the development of hyper-heuristics for dynamic optimization problems. Despite that, they arise as very appropriate methods for dynamic problems, being highly responsive and able to quickly adapt to any possible changes in the problem environment. In this paper, we present a brief study of the most salient previously proposed hyper-heuristics to solve dynamic optimization problems, and classify them, taking into consideration the complexity of their low-level heuristics. Then, we identify some the most important research areas that have been vaguely explored in the Literature yet.

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.

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

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.

Engineering students often find difficulties in understanding electrical diagrams, specially those from Design and Mechanical Engineering. A tool that can automatically generate the ladder diagram out of the wiring diagram would be extremely useful for them in their studies. Unfortunately, such a tool does not exist yet. We present in this paper a novel CAD tool that offers this functionality. The tool, called CADDI (standing for CAD for Electrical Diagrams) is designed to help students better understanding wiring and ladder diagrams. In CADDI, the user can either draw the ladder diagram using its graphical interface, or code the wiring diagram using a novel simple programming language, and it will automatically generate its ladder diagram. The mentioned new language was especially designed for this purpose by the students of Automata Theory and Formal Languages subject, from Computer Science Engineering degree of the University of Cadiz. In order to make CADDI accessible to all students, it was implemented as a web page. The tool has become a great assistance for students, who regularly use it during their studies.

MANETs are specially vulnerable against security attacks. For protecting them, security solutions are traditionally addressed by the so-called intrusion detection and response systems. Nevertheless, using reactive (response) solutions, once the attack is detected, rely in long attack mitigation times. In this work, we propose the use of relay node placement techniques as proactive security solutions. Preliminary experimentation demonstrates the suitability and feasibility of such approaches, not only in reducing the attack mitigation time but in replacing detection and response based traditional solutions.

Sensitivity analysis is a mathematical tool that distributes the uncertainty of the output of a model among its different input variables. We use in this work the Extended Fourier Amplitude Sensitivity Test to carefully analyze the impact of 54 LLVM code optimization operators on the execution time of nine benchmark software programs. Experiments presented involve performing over 16 million executions. The results show that the different LLVM transformations have a low direct effect on the execution time, but it becomes meaningful when considering the transformation in combination with the others (almost 60% average impact by all passes on all considered benchmarks). These results provide slight indications on the transformations to apply for optimizing the software, revealing the extreme difficulty of the problem.

This article introduces a new kind of broker for cloud computing, whose business relies on outsourcing virtual machines (VMs) to its customers. More specifically, the broker owns a number of reserved instances of different VMs from several cloud providers and offers them to its customers in an on-demand basis, at cheaper prices than those of the cloud providers. The essence of the business resides in the large difference in price between on-demand and reserved VMs. We define the Virtual Machine Planning Problem, an optimization problem to maximize the profit of the broker. We also propose a number of efficient smart heuristics (seven two-phase list scheduling heuristics and a reordering local search) to allocate a set of VM requests from customers into the available pre-booked ones, that maximize the broker earnings. We perform experimental evaluation to analyze the profit and quality of service metrics for the resulting planning, including a set of 400 problem instances that account for realistic workloads and scenarios using real data from cloud providers.

We propose a new accurate and fast memetic parallel optimization algorithm for the independent tasks scheduling problem. The new technique combines the Virtual Savant (VS) with a parallel genetic algorithm (called PA-CGA). VS is an optimization framework based on machine learning that learns from a reference set of (pseudo-)optimal solutions how to solve the problem, providing accurate results in extremely low run times. We propose in this work the use of VS to generate a highly accurate initial population for the PA-CGA. Results show how initializing the population with VS (we test two versions of VS, differing on its training process) significantly increases the accuracy of the PA-CGA, compared to two other population initialization techniques: random and using a state-of-the-art heuristic.

This chapter presents a new kind of cloud brokering model called virtual broker. The virtual broker owns and manages what we call a virtual cloud, composed by a set of reserved VMs from a number of public cloud providers. This new broker sublets its resources to its customers as on-demand VMs, at lower prices than those offered in the market. This model is feasible because of the large price difference between on-demand and reserved VMs in current pricing schemes. We propose a number of online and offline heuristics to efficiently manage the resources of the virtual broker in order to optimize its revenue, as well as the QoS level offered to the customers. Two realistic versions of the problem are proposed and analyzed. The results show the proposed brokering model is a profitable business model for both the virtual broker and the cloud customers, reducing cloud customer costs down to 80% when compared to traditional on-demand renting costs.

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

This article addresses a virtual machine (VM) allocation problem that appears in a novel business model for cloud computing. In this model, a cloud service broker owns a number of cloud reserved instances that outsources to its customers as cheap as on-demand VMs. The objective of the broker is to efficiently manage its reserved resources to maximize its revenue. We enhance the previous definition of the problem by considering more realistic parameters: geographical localization of resources and users, different types of applications, and data transfer costs. We propose a set of heuristics to solve the optimization problem of maximizing the cloud provider profit while offering appropriate Quality-of-Service to the users. The experimental analysis is performed over different scenarios using real data from cloud providers.

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

The energy consumption of large data centers has been increasing for the last decades and currently is a major concern for economic and environmental reasons. Accurate scheduling of the data center operation and use of renewable energy sources present themselves as promising solutions for this problem. In this paper we study the problem of scheduling workflows of tasks in distributed heterogeneous data centers which are partially powered by renewable energy sources. This problem takes into account quality of service, infrastructure usage, and power consumption of machines and cooling devices. We propose a mathematical model for accurate scheduling solutions.

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.

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.

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

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 kind of networks, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcasting strategy in MANETs is a multi-objective problem targeting three goals: reaching as many devices as possible, minimizing the network utilization, and reducing the duration time of the broadcasting process. In this paper, we study the fine-tuning of broadcasting strategies by using a cellular multi-objective genetic algorithm (cMOGA) which computes a Pareto front of solutions to empower a human designer with the ability of choosing the preferred configuration for the network. We define two formulations of the problem, one with three objectives and another one with two objectives plus a constraint. For our tests, a benchmark of three realistic environments for metropolitan MANETs has been defined. Our experiments using a complex and realistic MANET simulator reveal that cMOGA is a promising approach to solve the optimum broadcasting problem.

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.

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

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.

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

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

International audience; Green Light Optimal Speed Advisory (GLOSA) systems provide drivers with speed advices that allow them to pass traffic lights during green interval. In this article we compare performance of single- and multi-segment GLOSA approaches. In a single-segment GLOSA traffic signals are considered independently, i.e. the system provides vehicles with the optimal speed for the segment ahead of the nearest traffic signals. In a multi-segment GLOSA several signals in a sequence on a vehicle's route are taken into account, that is, vehicles receive speed advices for a set of segments ahead of the vehicle. Traveling time and fuel efficiency are used as performance measures. We demonstrate that as long as traffic conditions allow drivers selecting a wide range of speed (e.g. during free-flow) a multi-segment GLOSA results in much better performance when compared with a single-segment approach.

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

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

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

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

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

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

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.

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

In mobile ad hoc networks (or MANETs) devices usually rely on batteries, so the lifetime of these networks highly depends on the energy consumption of the devices composing them. In this paper, we improve the performance of the adaptive enhanced distance based broadcasting algorithm, AEDB, as well as we optimize it using a hybrid multi-objective algorithm, CellDE. The optimization is done by maximizing the coverage achieved by the broadcast process while minimizing at the same time both, the energy consumption and the broadcast time. CellDE provides a wide range of different solutions for the configuration of AEDB, outperforming all of them the performance of the protocol using the original configuration.

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

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

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

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

This work proposes a new parallel asynchronous cellular genetic algorithm model for multi-core processors. The algorithm has been used for solving the DNA fragment assembly problem with the aim of finding highly accurate solutions in short computation times. This NP-Complete problem lies in reconstructing a DNA chain from multiple fragments that have previously been sequenced in a laboratory. The considered problem is a critical step in any genomic project, since the resulting chains are the basis for the entire work. Therefore, the quality of these chains is a major aspect for the correct development of the project. The proposed algorithm is able to find highly accurate results much faster than the other algorithms in the literature. Additionally, since it is parallel, it could be scalable to much larger problem instances, for which the methods typically used usually encounter difficulties. Finally, several new local search methods have been designed, and their influence on the performance of the algorithm has been analyzed.

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.

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