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.

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.

This article presents the application of Virtual Savant to solve resource allocation problems, a widely-studied area with several real-world applications. Virtual Savant is a novel soft computing method that uses machine learning techniques to compute solutions to a given optimization problem. Virtual Savant aims at learning how to solve a given problem from the solutions computed by a reference algorithm, and its design allows taking advantage of modern parallel computing infrastructures. The proposed approach is evaluated to solve the Knapsack Problem, which models different variant of resource allocation problems, considering a set of instances with varying size and difficulty. The experimental analysis is performed on an Intel Xeon Phi many-core server. Results indicate that Virtual Savant is able to compute accurate solutions while showing good scalability properties when increasing the number of computing resources used.

We propose a new method for multi-objective optimization, called Fuzzy Adaptive Multi-objective Evolutionary algorithm (FAME). It makes use of a smart operator controller that dynamically chooses the most promising variation operator to apply in the different stages of the search. This choice is guided by a fuzzy logic engine, according to the contributions of the different operators in the past. FAME also includes a novel effective density estimator with polynomial complexity, called Spatial Spread Deviation (SSD). Our proposal follows a steady-state selection scheme and includes an external archive implementing SSD to identify the candidate solutions to be removed when it becomes full. To assess the performance of our proposal, we compare FAME with a number of state of the art algorithms (MOEA/D-DE, SMEA, SMPSOhv, SMS-EMOA, and BORG) on a set of difficult problems. The results show that FAME achieves the best overall performance.

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

In this paper, we address the exact solution of the vertex bisection problem (VBP). We propose two novel B&B algorithms to solve VBP, which include new upper and lower bound constructive heuristics, and an efficient strategy to explore the combinatorial search space. The computational results show that the proposed algorithms clearly outperforms the state-of-the-art B&B algorithm in quality and efficiency. The two proposed B&B versions differ in the exploration strategy and the storage of the search tree. Also, we provide four new solutions, previously unknown. We consider that the main contributions of this work can be adapted to solve combinatorial problems in other related domains.

Particle Swarm Optimization algorithms (or PSO) have been widely studied in the Literature. It is known that they provide highly competitive results. However, they suffer from fast convergence to local optima. There exist works proposing the swarm decentralization by including some specific topologies in order to deal with this problem. These approaches highly improve the results. In this work, we propose PSO-CO, a PSO algorithm able to reduce the exploitation of the algorithm by introducing the concept of coalitions in the swarm. There is one leader in each of these coalitions, so that the particles belonging to a coalition are only influenced by their local leader, and not the global one. This mechanism allows different coalitions to explore different parts of the search space, reducing thus the convergence speed and enhancing the exploration capabilities of the algorithm. Moreover, the particles can leave a coalition and join another, facilitating the exchange of information between coalitions. For testing the efficiency of the proposed PSO-CO, we have chosen a relevant benchmark in the literature, specially designed for continuous optimization. Results show that PSO-CO highly improves the results obtained compared to classical PSO.

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

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.

Plug-in hybrid (PH) buses offer range and operating flexibility of buses with conventional internal combustion engines with environmental. However, when they are frequently charged, they also enable societal benefits (emissions- and noise-related) associated with electric buses. Thanks to geofencing, pure electric drive of PH buses can be assigned to specific locations via a back-office system. As a result, PH buses not only can fulfil zero-emission (ZE) zones set by city authorities, but they can also minimize total energy use thanks to selection of locations favouring (from energy perspective) electric drive. Such a location-controlled behaviour allows executing targeted air quality improvement and noise reduction strategies as well reducing energy consumption. However, current ZE zone assignment strategies used by PH buses are static—they are based on the first-come-first serve rule and do not consider traffic conditions. In this article, we propose a novel recommendation system, based on artificial intelligence, that allows PH buses operating efficiently in a dynamic environment, making the best use of the available resources so that emission- and noise-pollution levels are minimized.

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.

We present a novel method to automatically generate new parallel solvers for optimization problems, called the Virtual Savant. It applies machine learning to model a reference algorithm (which is treated as a black box) from its solutions to a given problem, and after, it is able to efficiently and accurately reproduce its solutions on new unseen problem instances. Additionally, the generated parallel algorithm is scalable to a different problem dimension. We analyze the performance and accuracy of our novel technique on a scheduling problem, and we use instances of different features and sizes. Virtual Savant was used to learn from an exact algorithm, a well-known heuristic, and a specialized parallel metaheuristic. During our experiments, our method solved to optimality up to 95.5% of the 200 unseen instances tested. For larger instances, it is not only highly competitive with the reference algorithms, but it is even able to outperform them in some cases. Another outstanding result is that Virtual Savant improved its accuracy when scaling the problem size (without additional training), with respect to the original algorithm.

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.

This article presents how Virtual Savant (VS) can be used to automatically learn, from an exact algorithm, how to solve the basic independent Next Release Problem in a quick and accurate way. This variant of the Next Release Problem (NRP) is in essence a 0/1 Knapsack Problem and VS is applied to solve the underlying optimization problem. VS is a generic problem-solving approach based on machine learning and heuristics, that works by mimicking how a reference program produces solutions to problem instances. Essentially, VS learns how to generate solutions to a given problem from a reference algorithm and a training set of instances, and it is able to efficiently solve new problem instances by using the acquired knowledge. In this paper, an exact optimizer is used as a reference algorithm. Hence, we are using VS to learn from optimal solutions, which helps to reduce the approximation error inherent to the learning process. We compare five versions of VS (differing in the heuristics they implement) on a large benchmark, composed of problems with different sizes and difficulties. For the best VS configuration, which also has the lowest computational complexity, computed solutions differ less than 1% from the optima in the worst case. Therefore, VS succeeds in learning how to solve the problem under study, and it does so in a highly efficient way, exempting the programmer from having a deep knowledge of the problem domain or highly specialized parallel programming skills.

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.

High-Performance Computing (HPC) is a growing necessity of our technological society, HPC demands high loads of parallel computing jobs, an optimal scheduling of the parallel applications tasks is a priority to meet the demands of its users on time. Branch-and-bound (BB) Algorithms and Mathematical Programming (MP) solve complex optimization problems in an optimal manner, some MP or BB even have parallel computing capabilities, making them suitable solutions to solve real-world problems. In this paper, we propose two exact algorithms, a BB and a MP Model for scheduling precedence-constrained applications, on heterogeneous computing systems, as far as we known the first ones on his kind presented in the state of the art. One major contribution of the work is the proposed formulations of the objective function in both methods. Experimental results obtained more than twenty optimal values for synthetic applications from the literature.

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

We present in this work the first parallel implementation of Virtual Savant (VS), a novel optimization method that is able to quickly generate pseudo-optimal solutions to a given combinatorial problem, thanks to its parallel pattern recognition engine. The proposed parallel implementation does not require any information exchange between the threads during the run, they just get/send the required information before/after the execution. This design allows for a flexible algorithm that can perform efficiently on both shared- and distributed-memory systems. Our implementation uses both OpenMP for parallel architectures and MPI for distributed environments, which can efficiently make use of both kind of systems. The performance of VS is extensively analyzed on four different computing infrastructures, varying the number of threads used on each considered architecture. In addition, we propose a simulator to accurately predict the performance of VS on any parallel system. Experimental results show that VS is able to make an efficient use of the available computing resources, showing good scalability properties on all studied architectures.

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.

A key issue when using distributed computing environments is finding a planning strategy to execute tasks in order to use the computational resources efficiently. This article presents the application of Virtual Savant to solve the heterogeneous computing scheduling problem, a widely-studied problem with several real-world applications. Virtual Savant is a novel method that uses machine learning techniques to automatically generate programs that can be executed in parallel to solve a given problem. Experimental analysis is performed on a set of problem instances generated following methodologies from the related literature. Results show that Virtual Savant is able to outperform MinMin, a well-known heuristic for the studied problem, by up to 15% while showing good scalability properties when increasing the number of computing resources and the dimension of the problem instances.

Over the last ten years, there has been a significant change in computing. After reaching the physical limits in integrated circuit technology, Moore's law (predicting an exponential growth of computing capacity over the years) has been maintained thanks to the replication of computing components (i.e., parallelization). Current computers now incorporate multiple processors, which are themselves multi-core, and come with technologies to increase the parallel capabilities of processors, like the Intel hyper-threading technology that implements two logical processors per core. This is the architecture present not only in today's servers or workstations, but also in portable and mobile devices as laptops, tablets, or mobile phones. It is accepted that this trend towards more and more parallel architectures will be maintained in the coming years.

Literature reveals that optimization algorithms are generally composed of a large number of parameters that highly influence on its performance. In the early stages of the definition of a new algorithm, it is crucial to know how the uncertainty in the input parameters affects the behavior of the algorithm, influencing on its final output, so that it is possible to set up the most efficient configuration.

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

Support vector machines are widely used for classification and regression tasks. However, sequential implementations for support vector machines are usually unable to deal with the increasing size of current real-world learning problems. In this context, Intel®Xeon PhiTM processors allow easily incorporating high performance computing strategies to improve execution times. This article proposes a parallel implementation of the popular LIBSVM library, specially adapted to the Intel®Xeon PhiTM architecture. The proposed implementation is evaluated using publicly available datasets corresponding to classification and regression tasks. Results show that the proposed parallel version computes the same results than the original LIBSVM while reducing the time needed for training by up to a factor of 4.81.

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

This article introduces 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.

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.

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min-min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min-min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min-min heuristic when more accurate solutions are needed, at the expense of an increased runtime.

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.

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.