Search

International audience; Mixed Integer Linear Programs (MILPs) are usually NP-hard mathematical programming problems, which present difficulties to obtain optimal solutions in a reasonable time for large scale models. Nowadays, metaheuristics are one of the potential tools for solving this type of problems in any context. In this paper, we focus our attention on MILPs in the specific framework of Data Envelopment Analysis (DEA), where the determination of a score of technical efficiency of a set of Decision Making Units (DMUs) is one of the main objectives. In particular, we propose a new hyper-matheuristic grounded on a MILP-based decomposition in which the optimization problem is divided into two hierarchical subproblems. The new approach decomposes the model into discrete and continuous variables, treating each subproblem through different optimization methods. In particular, metaheuristics are used for dealing with the discrete variables, whereas exact methods are used for the set of continuous variables. The metaheuristics use an indirect representation that encodes an incomplete solution for the problem, whereas the exact method is applied to decode the solution and generate a complete solution. The experimental results, based on simulated data in the context of Data Envelopment Analysis, show that the solutions obtained through the new approach outperform those found by solving the problem globally using a metaheuristic method. Finally, regarding the new hyper-matheuristic scheme, the best algorithm selection is found for a set of cooperative metaheuristics ans exact optimization algorithms.

During the past few years, research in applying machine learning (ML) to design efficient, effective, and robust metaheuristics has become increasingly popular. Many of those machine learning-supported metaheuristics have generated high-quality results and represent state-of-the-art optimization algorithms. Although various appproaches have been proposed, there is a lack of a comprehensive survey and taxonomy on this research topic. In this article, we will investigate different opportunities for using ML into metaheuristics. We define uniformly the various ways synergies that might be achieved. A detailed taxonomy is proposed according to the concerned search component: target optimization problem and low-level and high-level components of metaheuristics. Our goal is also to motivate researchers in optimization to include ideas from ML into metaheuristics. We identify some open research issues in this topic that need further in-depth investigations.

In recent years, research in applying optimization approaches in the automatic design of deep neural networks has become increasingly popular. Although various approaches have been proposed, there is a lack of a comprehensive survey and taxonomy on this hot research topic. In this article, we propose a unified way to describe the various optimization algorithms that focus on common and important search components of optimization algorithms: representation, objective function, constraints, initial solution(s), and variation operators. In addition to large-scale search space, the problem is characterized by its variable mixed design space, it is very expensive, and it has multiple blackbox objective functions. Hence, this unified methodology has been extended to advanced optimization approaches, such as surrogate-based, multi-objective, and parallel optimization.

International audience; Multi-objective optimization problems (MOPs) have been widely studied during the last decades. In this paper, we present a new intrinsically parallel approach based on Fractal decomposition (FDA) to solve MOPs. The key contribution of the proposed approach is to divide recursively the decisionspace using hyperspheres. Two different methods were investigated: the first one is based on scalarization that has been distributed on a parallel multi-node architecture virtual environments and taking profit from the FDA’s properties, while the second method is based on Pareto dominance sorting. A comparison with state of the art algorithms on different well known benchmarks shows the efficiency and the robustness of the proposed decomposition approaches.

Modern algorithms for symmetric and asymmetric encryptions are not suitable to provide security of data that needs data processing. They cannot perform calculations over encrypted data without first decrypting it when risks are high. Residue Number System (RNS) as a homomorphic encryption allows ensuring the confidentiality of the stored information and performing calculations over encrypted data without preliminary decoding but with unacceptable time and resource consumption. An important operation for encrypted data processing is a number comparison. In RNS, it consists of two steps: the computation of the positional characteristic of the number in RNS representation and comparison of its positional characteristics in the positional number system. In this paper, we propose a new efficient method to compute the positional characteristic based on the approximate method. The approximate method as a tool to compare numbers does not require resource-consuming non-modular operations that are replaced by fast bit right shift operations and taking the least significant bits. We prove that in case when the dynamic range of RNS is an odd number, the size of the operands is reduced by the size of the module. If one of the RNS moduli is a power of two, then the size of the operands is less than the dynamic range. We simulate proposed method in the ISE Design Suite environment on the FPGA Xilinx Spartan-6 SP605 and show that it gains 31% in time and 37% in the area on average with respect to the known approximate method. It makes our method efficient for hardware implementation of cryptographic primitives constructed over a prime finite field.

International audience; Within the framework of complex system analyses, such as aircraft and launch vehicles, the presence of computationally intensive models (e.g., finite element models and multidisciplinary analyses) coupled with the dependence on discrete and unordered technological design choices results in challenging modeling problems. In this paper, the use of Gaussian process surrogate modeling of mixed continuous/discrete functions and the associated challenges are extensively discussed. A unifying formalism is proposed in order to facilitate the description and comparison between the existing covariance kernels allowing to adapt Gaussian processes to the presence of discrete unordered variables. Furthermore, the modeling performances of these various kernels are tested and compared on a set of analytical and aerospace engineering design related benchmarks with different characteristics and parameterizations. Eventually, general tendencies and recommendations for such types of modeling problem using Gaussian process are highlighted.

Recently, due to the high penetration of distributed generators and storages, and the rapid growth of environmental concerns, energy optimisation plays a vital role in the operation of microgrids. In this paper, we propose a hybrid backtracking search matheuristic algorithm with a multiobjective indirect encoding (H-MOBSA) for the multiobjective mixed-integer nonlinear formulation of economic-emission dispatch in a grid-connected microgrid. In this approach, each partial discrete solution represented by the backtracking search algorithm is associated with a set of Pareto solutions of the related continuous subproblem where the fitness and diversity assignments are adapted to take into account all associated decoded solutions. The proposed algorithm aims to provide generation planning and the battery size that satisfy the trade-off between the total operating cost and pollutant emissions under equality and inequality constraints. To show the effectiveness of our approach, the proposed H-MOBSA is tested on typical MG and compared to other algorithms.

International audience; This paper studies the hybridization of Mixed Integer Programming (MIP) with dual heuristics and machine learning techniques, to provide dual bounds for a large scale optimization problem from an industrial application. The case study is the EURO/ROADEF Challenge 2010, to optimize the refueling and maintenance planning of nuclear power plants. Several MIP relaxations are presented to provide dual bounds computing smaller MIPs than the original problem. It is proven how to get dual bounds with scenario decomposition in the different 2-stage programming MILP formulations, with a selection of scenario guided by machine learning techniques. Several sets of dual bounds are computable, improving significantly the former best dual bounds of the literature and justifying the quality of the best primal solution known.

International audience; Multi-fidelity approaches combine different models built on a scarce but accurate data-set (high-fidelity data-set), and a large but approximate one (low-fidelity data-set) in order to improve the prediction accuracy. Gaussian Processes (GPs) are one of the popular approaches to exhibit the correlations between these different fidelity levels. Deep Gaussian Processes (DGPs) that are functional compositions of GPs have also been adapted to multi-fidelity using the Multi-Fidelity Deep Gaussian process model (MF-DGP). This model increases the expressive power compared to GPs by considering non-linear correlations between fidelities within a Bayesian framework. However, these multi-fidelity methods consider only the case where the inputs of the different fidelity models are defined over the same domain of definition (e.g., same variables, same dimensions). However, due to simplification in the modeling of the low-fidelity, some variables may be omitted or a different parametrization may be used compared to the high-fidelity model. In this paper, Deep Gaussian Processes for multi-fidelity (MF-DGP) are extended to the case where a different parametrization is used for each fidelity. The performance of the proposed multifidelity modeling technique is assessed on analytical test cases and on structural and aerodynamic real physical problems.

International audience; Surrogate modeling is an increasingly popular tool for engineering design as it enables to model the performance of very complex systems with a limited computational cost. A large number of techniques exists for the surrogate modeling of continuous functions, however, only a very few methods for the surrogate modeling of mixed continuous/discrete functions have been developed. In this chapter, existing adaptations and variants of Gaussian process-based surrogate modeling techniques for mixed continuous/discrete variables are described, discussed and compared on several analytical test-cases and aerospace design problems.

International audience; An extensive research has led to a general understanding of uncertainty issues in different fields ranging from computational biology to decision making in economics. However, a study of uncertainty on large scale computing systems and cloud computing systems is limited. Most of works examine uncertainty phenomena in users’ perceptions of the qualities, intentions and actions of cloud providers. In this paper, we discuss the role of uncertainty in the resource and service provisioning, privacy, etc. especially, in the presence of the risks of confidentiality, integrity, and availability. We review sources of uncertainty, and fundamental approaches for scheduling under uncertainty. We also discuss potentials of these approaches, and address methods for mitigating the risks of confidentiality, integrity, and availability associated with the loss of information, denial of access for a long time, and information leakage.

Cloud storages delivered as services are made available to the general public. As cloud storage provider prices become low, they have moved into the mainstream of storage technology. However, there are various factors that cause many potential users do not use it intensively. There exist high risks for confidentiality, integrity, and availability violation associated with the loss of information, denial of access, technical failures, etc. In this article, we propose a two-level secret sharing scheme (TL-SSS) based on a residue number system (RNS) for a configurable, reliable, and secure distributed data storage. RNS moduli of a special type increase the reliability of the data storage system and reduce the computational complexity of the data encoding and decoding from linear-logarithmic to linear. TL-SSS is the weighted data access structure. It creates and distributes data shares according to the characteristics of the cloud storages under various scenarios. We provide a solution that improves system reliability without reduction of the security level. In contrast to classical solutions, it can restore the data with less available shares than the state-of-the-art approaches.

International audience; This paper is focused on the problem of constrained multi-objective design optimization of aerospace vehicles. The design of such vehicles often involves disciplinary legacy models considered as black-box and computationally expensive simulations characterized by a possible non-stationary behavior (an abrupt change in the response or a different smoothness along the design space). The expensive cost of an exact function evaluation makes the use of classical evolutionary multi-objective algorithms not tractable. While Bayesian Optimization based on Gaussian Process regression can handle the expensive cost of the evaluations, the non-stationary behavior of the functions can make it inefficient. A recent approach consisting of coupling Bayesian Optimization with Deep Gaussian Processes showed promising results for single-objective non-stationary problems. This paper presents an extension of this approach to the multi-objective context. The efficiency of the proposed approach is assessed with respect to classical optimization methods on an analytical test-case and on an aerospace design problem.

This paper considers a multi-objective variant of vehicle routing problems, in which the customer demands are supposed to be triangular fuzzy numbers and the objective functions are also disrupted by fuzziness. However, the propagation of fuzzy demands to the objectives can affect the reliability of generated solutions. To this end, we propose a robustness approach to deal with fuzziness in the multi-objective context. The new approach tries to achieve robust routes that minimize two fuzzy-valued objectives, the total traveled distance and total tardiness time. Additionally, we suggest to refine our previously proposed algorithms for integrating robustness. An experimental study based on a Monte-Carlo simulation is finally carried out to evaluate the obtained results.

Planning the maintenance of nuclear power plants is a complex optimization problem, involving a joint optimization of maintenance dates, fuel constraints and power production decisions. This paper investigates Mixed Integer Linear Programming (MILP) matheuristics for this problem, to tackle large size instances used in operations with a time scope of five years, and few restrictions with time window constraints for the latest maintenance operations. Several constructive matheuristics and a Variable Neighborhood Descent local search are designed. The matheuristics are shown to be accurately effective for medium and large size instances. The matheuristics give also results on the design of MILP formulations and neighborhoods for the problem. Contributions for the operational applications are also discussed. It is shown that the restriction of time windows, which was used to ease computations, induces large over-costs and that this restriction is not required anymore with the capabilities of matheuristics or local search to solve such size of instances. Our matheuristics can be extended to a bi-objective optimization extension with stability costs, for the monthly re-optimization of the maintenance planning in the real-life application.

Cloud computing is significantly reshaping the computing industry. Individuals and small organizations can benefit from using state-of-the-art services and infrastructure, while large companies are attracted by the flexibility and the speed with which they can obtain the services. Service providers compete to offer the most attractive conditions at the lowest prices. However, the environmental impact and legal aspects of cloud solutions pose additional challenges. Indeed, the new cloud-related techniques for resource virtualization and sharing and the corresponding service level agreements call for new optimization models and solutions. It is important for computational intelligence researchers to understand the novelties introduced by cloud computing. The current survey highlights and classifies key research questions, the current state of the art, and open problems.

The articles in this special issue are dedicated to computational intelligence for Cloud computing. Cloud computing systems represent an emerging technology which allows its users to have access to large scale, efficient and highly reliable computing systems by paying according to their needs. Cloud computing generally consists of a heterogeneous system that holds a large amount of application programs and data.

International audience; The most dangerous emergency situations are those threatening a high population in complex and large scale buildings. Traditional evacuation plans seem to be inefficient and lack of flexibility owing to the difficulty in predicting both the behavior of evacuees and building status in such disasters. The emergence of smart building and technologies can help to design real-time evacuation guidance systems. They will provide shortest routes for evacuees regarding their position in the building by avoiding crowd and fire propagation. We propose a guidance system based on an ant colony optimizer. Experiments are performed to illustrate the ability of this intelligent guidance system in providing realistic plans according to the building parameters. Also, the decision maker can assess the safety of a given building by simulating evacuation process.

In an ideal world, it would be straightforward to identify the most suitable optimisation method to use in the solution of a given optimisation problem. However, although some methods may be more widely applicable than others, it is impossible a priori to know which method will work best. This may be due to the particular mathematical properties of the mathematical model, i.e. the formulation. It may also be due to the representation of the variables in the model. This combination of choices of method, representation and formulation makes it difficult to predict which combination may be best.

Cross-selling campaigns seek to offer the right products to the set of customers with the goal of maximizing expected profit, while, at the same time, respecting the purchasing constraints set by investors. In this context, a bi-objective version of this NP-Hard problem is approached in this paper, aiming at maximizing both the promotion campaign total profit and the risk-adjusted return, which is estimated with the reward-to-variability ratio known as Sharpe ratio. Given the combinatorial nature of the problem and the large volume of data, heuristic methods are the most common used techniques. A Greedy Randomized Neighborhood Structure is also designed, including the characteristics of a neighborhood exploration strategy together with a Greedy Randomized Constructive technique, which is embedded in a multi-objective local search metaheuristic. The latter combines the power of neighborhood exploration by using a Pareto Local Search with Variable Neighborhood Search. Sets of non-dominated solutions obtained by the proposed method are described and analyzed for a number of problem instances. The authors would like to thank Brazilian agency CAPES, CNPq (grants 305506/2010-2, 552289/2011-6, 306694/2013-1 and 312276/2013-3), FAPEMIG (grants APQ-04611-10, PPM CEX497-13) and FP7 CORDIS, “New Horizons for Multi Criteria Decision Making”, for supporting the development of this work. Helena Ramalhinho was also partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013- 48180-C3-P, TRA2015-71883-REDT).

Image registration is the process of overlaying two or more images of the same scene taken at different times, from different viewpoints, and/or by different sensors. It is a critical step in all image analysis tasks in which the final information is gained from the combination of various data sources like in image fusion or change detection.

International audience; This book highlights state-of-the-art developments in metaheuristics research. It examines all aspects of metaheuristic research including new algorithmic developments, applications, new research challenges, theoretical developments, implementation issues, in-depth experimental studies. The book is divided into two sections. Part I is focused on new optimization and modeling techniques based on metaheuristics. The chapters in this section cover topics from multi-objective problems with fuzzy data with triangular-valued objective functions, to hyper-heuristics optimization methodology, designing genetic algorithms, and also the cuckoo search algorithm. The techniques described help to enhance the usability and increase the potential of metaheuristic algorithms. Part II showcases advanced metaheuristic approaches to solve real-life applications issues. This includes an examination of scheduling, the vehicle routing problem, multimedia sensor network, supplier selection, bin packing, objects tracking, and radio frequency identification. In the fields covered in the chapters are of high-impact applications of metaheuristics. The chapters offer innovative applications of metaheuristics that have a potential of widening research frontiers. Altogether, this book offers a comprehensive look at how researchers are currently using metaheuristics in different domains of design and application.

International audience; Reducing energy consumption is an increasingly important issue in cloud computing, more specifically when dealing with a large scale cloud. Minimizing energy consumption can significantly reduce the amount of energy bills, and the greenhouse gas emissions. Therefore, many researches are carried out to develop new methods in order to consume less energy. In this paper, we present an Energy-aware Multi-start Local Search algorithm (EMLS-ONC) that optimizes the energy consumption of an OpenNebula based Cloud. Moreover, we propose a Pareto Multi-Objective version of the EMLS-ONC called EMLS-ONC-MO dealing with both the energy consumption and the Service Level Agreement (SLA). The objective is to find a Pareto tradeoff between reducing the energy consumption of the cloud while preserving the performance of Virtual Machines (VMs). The different schedulers have been experimented using different arrival scenarios of VMs and different hardware configurations (artificial and real). The results show that EMLS-ONC and EMLS-ONC-MO outperform the other energy- and performance-aware algorithms in addition to the one provided in OpenNebula by a significant margin on the considered criteria. Besides, EMLS-ONC and EMLS-ONC-MO are proved to be able to assign at least as many VMs as the other algorithms.

International audience; This paper presents a general-purpose software framework dedicated to the design, the analysis and the implementation of local search metaheuristics: ParadisEO-MO. A substantial number of single solution-based local search metaheuristics has been proposed so far, and an attempt of unifying existing approaches is here presented. Based on a fine-grained decomposition, a conceptual model is proposed and is validated by regarding a number of state-of-the-art methodologies as simple variants of the same structure. This model is then incorporated into the ParadisEO-MO software framework. This framework has proven its efficiency and high flexibility by enabling the resolution of many academic and real-world optimization problems from science and industry.

Local search metaheuristics (LSMs) are efficient methods for solving complex problems in science and industry. They allow significantly to reduce the size of the search space to be explored and the search time. Nevertheless, the resolution time remains prohibitive when dealing with large problem instances. Therefore, the use of GPU-based massively parallel computing is a major complementary way to speed up the search. However, GPU computing for LSMs is rarely investigated in the literature. In this paper, we introduce a new guideline for the design and implementation of effective LSMs on GPU. Very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of neighboring solutions to GPU threads, and memory management. These approaches have been experimented using four well-known combinatorial and continuous optimization problems and four GPU configurations. Compared to a CPU-based execution, accelerations up to \times 80 are reported for the large combinatorial problems and up to \times 240 for a continuous problem. Finally, extensive experiments demonstrate the strong potential of GPU-based LSMs compared to cluster or grid-based parallel architectures.

During the last years, interest on hybrid metaheuristics has risen considerably in the field of optimization and machine learning. The best results found for many optimization problems in science and industry are obtained by hybrid optimization algorithms. Combinations of optimization tools such as metaheuristics, mathematical programming, constraint programming and machine learning, have provided very efficient optimization algorithms. Four different types of combinations are considered in this paper: (i) Combining metaheuristics with complementary metaheuristics. (ii) Combining metaheuristics with exact methods from mathematical programming approaches which are mostly used in the operations research community. (iii) Combining metaheuristics with constraint programming approaches developed in the artificial intelligence community. (iv) Combining metaheuristics with machine learning and data mining techniques.

International audience; The paper addresses the robustness of multi-objective optimization problems with fuzzy data, expressed via triangular fuzzy numbers. To this end, we introduced a new robustness approach able to deal with fuzziness in the multi-objective context. The proposed approach is composed of two main contributions: First, new concepts of β-robustness are proposed to analyze fuzziness propagation to the multiple objectives. Second, an extension of our previously proposed evolutionary algorithms is suggested for integrating robustness. These proposals are illustrated on a multi-objective vehicle routing problem with fuzzy customer demands. The experimental results on different instances show the efficiency of the proposed approach.

In this paper, we propose a multiobjective evolutionary algorithm to solve the appliance scheduling problem in a smart home in a one-day horizon subdivided into 1440 time slots of one minute each. Mathematically, the appliance scheduling problem is formulated as an integer programming problem in which the decision variables consist of finding the optimal starting times of appliances under a time-varying electricity prices and the time windows in which the appliances must be operated. The aim is to minimize the two conflicting objectives simultaneously: The electricity cost and the discomfort caused by the delay or the advance of the appliances starting times from the preferred starting times set by a home consumer. The extreme solutions of the obtained pareto front; best cost solution and best discomfort solution, are compared with the reference case in which a home consumer starts his/her appliances on his/her preferred starting times. The simulation results show that the ability of the proposed algorithm to shift appliances consumption in response to time-varying electricity prices from the on-peak price periods to the off-peak price periods within the time windows of appliances, through which a home consumer may reduce electricity cost without a significant impact on his/her comfort.

International audience; In this paper, we investigate the problem of scheduling precedence-constrained parallel applications on heterogeneous computing systems (HCSs) like cloud computing infrastructures. This kind of applications was studied and used in many research works. Most of these works propose algorithms to minimize the completion time (makespan) without paying much attention to energy consumption. We propose a new parallel bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. We particularly focus on the island parallel model and the multi-start parallel model. Our new method is based on dynamic voltage scaling (DVS) to minimize energy consumption. In terms of energy consumption, the obtained results show that our approach outperforms previous scheduling methods by a significant margin. In terms of completion time, the obtained schedules are also shorter than those of other algorithms. Furthermore, our study demonstrates the potential of DVS.

In this article, a new approach is proposed for the de novo protein sequencing problem. The aim is to find the sequence of an experimental protein from only experimental data, i.e. without databases. To do so, a three-step model called SSO for Shape, Sequence and Order has been designed. No prior knowledge in genomics nor protein databases are used. Here we modelized de novo protein sequencing as a combinatorial optimisation problem and propose cooperative metaheuristics to solve it. Results are assessed on experimental proteins and proved the feasibility of this approach.

The interest about hybrid optimization methods has grown for the last few years. Indeed, more and more papers about cooperation between heuristics and exact techniques are published. In this paper, we propose to extend an existing taxonomy for hybrid methods involving heuristic approaches in order to consider cooperative schemes between exact methods and metaheuristics. First, we propose some natural approaches for the different schemes of cooperation encountered, and we analyse, for each model, some examples taken from the literature. Then we recall and complement the proposed grammar and provide an annotated bibliography.

The study of the sensitivity and the specificity of a classification test constitute a powerful kind of analysis since it provides specialists with very detailed information useful for cancer diagnosis. In this work, we propose the use of a multiobjective genetic algorithm for gene selection of Microarray datasets. This algorithm performs gene selection from the point of view of the sensitivity and the specificity, both used as quality indicators of the classification test applied to the previously selected genes. In this algorithm, the classification task is accomplished by Support Vector Machines; in addition a 10-Fold Cross- Validation is applied to the resulting subsets. The emerging behavior of all these techniques used together is noticeable, since this approach is able to offer, in an original and easy way, a wide range of accurate solutions to professionals in this area. The effectiveness of this approach is proved on public cancer datasets by working out new and promising results. A comparative analysis of our approach using two and three objectives, and with other existing algorithms, suggest that our proposal is highly appropriate for solving this problem. Ministerio de Ciencia e Innovación TIN2008-06491-C04-01 Junta de Andalucía P07-TIC-03044

International audience; An important task of knowledge discovery deals with discovering association rules. This very general model has been widely studied and efficient algorithms have been proposed. But most of the time, only frequent rules are seeked. Here we propose to consider this problem as a multi-objective combinatorial optimization problem in order to be able to also find non frequent but interesting rules. As the search space may be very large, a discussion about different approaches is proposed and a hybrid approach that combines a metaheuristic and an exact operator is presented.

This talk provides a complete background on efficient optimization algorithms and presents in a unified view the main design questions for all families of algorithms and clearly illustrates how to solve complex optimization problems in smart grids, networks, logistics and transportation, data mining. The key search components of metaheuristics are considered as a toolbox for: Designing efficient optimization algorithms (e.g. local search, tabu search, simulated annealing, evolutionary algorithms, particle swarm optimization, scatter search, ant colonies, bee colonies, artificial immune systems) for optimization problems · Designing efficient algorithms for multi-objective optimization problems • Solving complex optimization problems in smart grids, networks, transportation and data mining.

International audience; The Virtual Machine Mapping Problem (VMMP) arise by the development of cloud computing. Focusing on a novel approach for cloud broker model in multi-clouds environment, we present a new model to deal with VMMP that takes into account the uncertainty of the VM execution time, hence allowing to obtain robust assignment solutions. The uncertainty of the VM execution time is modeled by (i) relying on a truncated normal distribution for constructing mapping instances, and (ii) by using the expected value of the generating truncated normal distribution. The proposed methods, for the optimization for the VMMP, are conducted on the Grid5000 in order to bring a detailed results comparison between the obtained results from the experimental study with different benchmarks.

International audience; Offers of public IAAS providers often vary: new providers enter the market, existing ones change their pricing or improve their offering. Decision on whether and how to improve already deployed platforms, either by reconfiguration or migration to another provider, can be seen as a NP-hard optimization problem. In this paper, we define a new realistic model for this Migration Problem, based on a Multi-Objective Optimization formulation. An evolutionary approach is introduced to tackle the problem, using specific operators. Experiments are conducted on multiple realistic data-sets, showing that the evolutionary approach is viable to tackle real-size instances in a reasonable amount of time.

In spite of extensive research of uncertainty issues in different fields ranging from computational biology to decision making in economics, a study of uncertainty for cloud computing systems is limited. Most of works examine uncertainty phenomena in users’ perceptions of the qualities, intentions and actions of cloud providers, privacy, security and availability. But the role of uncertainty in the resource and service provisioning, programming models, etc. have not yet been adequately addressed in the scientific literature. There are numerous types of uncertainties associated with cloud computing, and one should to account for aspects of uncertainty in assessing the efficient service provisioning. In this paper, we tackle the research question: what is the role of uncertainty in cloud computing service and resource provisioning? We review main sources of uncertainty, fundamental approaches for scheduling under uncertainty such as reactive, stochastic, fuzzy, robust, etc. We also discuss potentials of these approaches for scheduling cloud computing activities under uncertainty, and address methods for mitigating job execution time uncertainty in the resource provisioning.

Over the last two decades, interest on hybrid metaheuristics has risen considerably in the field of multi-objective optimization (MOP). The best results found for many real-life or academic multi-objective optimization problems are obtained by hybrid algorithms. Combinations of algorithms such as metaheuristics, mathematical programming and machine learning techniques have provided very powerful search algorithms. Three different types of combinations are considered in this paper to solve multi-objective optimization problems: Combining metaheuristics with (complementary) metaheuristics. Combining metaheuristics with exact methods from mathematical programming approaches. Combining metaheuristics with machine learning and data mining techniques.

In this paper, we contribute with the first results on parallel cooperative multi-objective meta-heuristics on computational grids. We particularly focus on the island model and the multi-start model and their cooperation. We propose a checkpointing-based approach to deal with the fault tolerance issue of the island model. Nowadays, existing Dispatcher-Worker grid middlewares are inadequate for the deployment of parallel cooperative applications. Indeed, these need to be extended with a software layer to support the cooperation. Therefore, we propose a Linda-like cooperation model and its implementation on top of Xtrem Web. This middleware is then used to develop a parallel meta-heuristic applied to a bi-objective Flow-Shop problem using the two models. The work has been experimented on a multidomain education network of 321 heterogeneous Linux PCs. The preliminary results, obtained after more than 10 days, demonstrate that the use of grid computing allows to fully exploit effectively different parallel models and their combination for solving large-size problem instances. An improvement of the effectiveness by over 60% is realized compared to serial meta-heuristic.

Cellular network design is a major issue in second generation GSM mobile telecommunication systems. In this paper, a new model of the problem in its full practical complexity, based on multiobjective constrained combinatorial optimization, has been used. We propose an evolutionary algorithm that aims at approximating the Pareto frontier of the problem, which removes the need for a cellular network designer to rank or weight objectives a priori. Specific coding scheme and genetic operators have been designed. Advanced intensification and diversification search techniques, such as elitism and adaptive sharing, have been used. Three complementary hierarchical parallel models have been designed to improve the solution quality and robustness, to speed-up the search and to solve large instances of the problem. The obtained Pareto fronts and speed-ups on different parallel architectures show the efficiency and the scalability of the parallel model. Performance evaluation of the algorithm has been carried out on different realistic benchmarks. The obtained results show the impact of the proposed parallel models and the introduced search mechanisms.

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.

Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this paper, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms. As an illustration of the usefulness of the taxonomy an annoted bibliography is given which classifies a large number of hybrid approaches according to the taxonomy.

A comparison analysis of dynamic mutation operators is proposed, having the conformational sampling problem as a case study. The analysis is sustained by a parallel Optimal Computing Budget Allocation (OCBA) selection procedure, employed in order to attain computational speedup. A Pearson system distribution based mutation operator is proposed, allowing for a highly flexible construction. As defined by a set of four parameters, the mean, variance, skewness and kurtosis, a large number of distributions can be simulated. As determined by the analysis outcomes, the class of operators exhibiting significant energy minimization or Root Mean Square Deviation (RMSD) bias is identified. Experiments are carried out on a large number of computational resources, allowing for the outline of an automatic a priori operator tuning and selection methodology. Although not presented in this chapter, similar complementary studies have been conducted on intensification operators and local search algorithms.

International audience; The satellite communications market is competitive and rapidly evolving. The payload, which is in charge of applying frequency conversion and amplification to the signals received from Earth before their retransmission, is made of various components. These include reconfigurable switches that permit the re-routing of signals based on market demand or because of some hardware failure. In order to meet modern requirements, the size and the complexity of current communication payloads are increasing significantly. Consequently, the optimal payload configuration, which was previously done manually by the engineers with the use of computerized schematics, is now becoming a difficult and time consuming task. Efficient optimization techniques are therefore required to find the optimal set(s) of switch positions to optimize some operational objective(s). In order to tackle this challenging problem for the satellite industry, this work proposes two Integer Linear Programming (ILP) models. The first one is single-objective and focuses on the minimization of the length of the longest channel path, while the second one is bi-objective and additionally aims at minimizing the number of switch changes in the payload switch matrix. Experiments are conducted on a large set of instances of realistic payload sizes using the CPLEX® solver and two well-known exact multi-objective algorithms. Numerical results demonstrate the efficiency and limitations of the ILP approach on this real-world problem.

Cloud computing has emerged during the last decade to be widely adopted nowadays in several IT areas. It consists to propose market or not market-oriented resources as services that can be consumed in a ubiquitous, flexible and transparent way. In this paper, we deal with scheduling, one of the major cloud computing issue. According to the targeted cloud configuration, the addressed objectives and the accuracy of the view that one have of the cloud, we propose a taxonomy that identifies three levels of scheduling: service-level, task-level and Virtual Machine-level. We compare different cloud scheduling approaches from the literature and identify the common features and the differences between all the approaches according to each cloud scheduling level using different criteria. The reported results of the comparison show inter alia a weakness in the proposed schedulers, almost no Pareto multi-objective solving algorithms and very few realistic experiments facing the real cloud constraints.

International audience; Local search based algorithms are a general and computational efficient metaheuristic. Restarting strategies are used in order to not be stuck in a local optimum. Iterated local search restarts the local search using perturbator operators, and the variable neighbourhood search alternates local search with various neighbourhoods. These two popular restarting techniques, or operators, evolve independently and are disconnected. We propose a metaheuristic framework, we call it multi-operator metaheuristics, which allows the alternative or simultaneously usage of the two restarting methods. Tuning the parameters, i.e. the neighbourhood size and the perturbation rate, is essential for the performance of metaheuristics. We automatically adapt the parameters for the two restarting operators using variants of adaptive pursuit for the multi-operators metaheuristic algorithms. We experimentally study the performance of several instances of the new class of metaheuristics on the quadratic assignment problem (QAP) instances, a well-known and difficult combinatorial optimization problem.

Ant Colonies optimization take inspiration from the behavior of real ant colonies to solve optimization problems. This paper presents a parallel model for ant colonies to solve the quadratic assignment problem (QAP). The cooperation between simulated ants is provided by a pheromone matrix that plays the role of a global memory. The exploration of the search space is guided by the evolution of pheromones levels, while exploitation has been boosted by a tabu local search heuristic. Special care has also been taken in the design of a diversification phase, based on a frequency matrix. We give results that have been obtained on benchmarks from the QAP library. We show that they compare favorably with other algorithms dedicated for the QAP. © 2001 Elsevier Science B.V. All rights reserved.

In this work we compare the use of a Particle Swarm Optimization (PSO) and a Genetic Algorithm (GA) (both augmented with Support Vector Machines SVM) for the classification of high dimensional Microarray Data. Both algorithms are used for finding small samples of informative genes amongst thousands of them. A SVM classifier with 10-fold cross-validation is applied in order to validate and evaluate the provided solutions. A first contribution is to prove that PSOSVM is able to find interesting genes and to provide classification competitive performance. Specifically, a new version of PSO, called Geometric PSO, is empirically evaluated for the first time in this work. In this sense, a comparison of this approach with a new GASVM and also with other existing methods of literature is provided. A second important contribution consists in the actual discovery of new and challenging results on six public datasets identifying significant in the development of a variety of cancers (leukemia, breast, colon, ovarian, prostate, and lung).

In this paper, we present a new energy efficiency model and architecture for cloud management based on a prediction model with Gaussian Mixture Models. The methodology relies on a distributed agent model and the validation will be performed on OpenStack. This paper intends to be a position paper, the implementation and experimental run will be conducted in future work. The design concept leverages the prediction model by providing a full architecture binding the resource demands, the predictions and the actual cloud environment (Openstack). The prediction analysis feeds the power-aware agents that run on the compute nodes in order to turn the nodes into sleep mode when the load state is low to reduce the energy consumption of the data center.