International audience

Hyperparameter optimization of spiking neural networks (SNNs) is a difficult task which has not yet been deeply investigated in the literature. In this work, we designed a scalable constrained Bayesian based optimization algorithm that prevents sampling in non-spiking areas of an efficient high dimensional search space. These search spaces contain infeasible solutions that output no or only a few spikes during the training or testing phases, we call such a mode a "silent network". Finding them is difficult, as many hyperparameters are highly correlated to the architecture and to the dataset. We leverage silent networks by designing a spike-based early stopping criterion to accelerate the optimization process of SNNs trained by Spike Timing Dependent Plasticity (STDP) and surrogate gradient. We parallelized the optimization algorithm asynchronously, and ran large-scale experiments on heterogeneous multi-GPU Petascale architecture. Results show that by considering silent networks, we can design more flexible high-dimensional search spaces while maintaining a good efficacy. The optimization algorithm was able to focus on networks with high performances by preventing costly and worthless computation of silent networks.

Multi-objective reinforcement learning (MORL) extends traditional RL by seeking policies making different compromises among conflicting objectives. The recent surge of interest in MORL has led to diverse studies and solving methods, often drawing from existing knowledge in multi-objective optimization based on decomposition (MOO/D). Yet, a clear categorization based on both RL and MOO/D is lacking in the existing literature. Consequently, MORL researchers face difficulties when trying to classify contributions within a broader context due to the absence of a standardized taxonomy. To tackle such an issue, this paper introduces multi-objective reinforcement learning based on decomposition (MORL/D), a novel methodology bridging the literature of RL and MOO. A comprehensive taxonomy for MORL/D is presented, providing a structured foundation for categorizing existing and potential MORL works. The introduced taxonomy is then used to scrutinize MORL research, enhancing clarity and conciseness through well-defined categorization. Moreover, a flexible framework derived from the taxonomy is introduced. This framework accommodates diverse instantiations using tools from both RL and MOO/D. Its versatility is demonstrated by implementing it in different configurations and assessing it on contrasting benchmark problems. Results indicate MORL/D instantiations achieve comparable performance to current state-of-the-art approaches on the studied problems. By presenting the taxonomy and framework, this paper offers a comprehensive perspective and a unified vocabulary for MORL. This not only facilitates the identification of algorithmic contributions but also lays the groundwork for novel research avenues in MORL.

In this paper, we propose DRAGON (for DiRected Acyclic Graph OptimizatioN), an algorithmic framework to automatically generate efficient deep neural networks architectures and optimize their associated hyperparameters. The framework is based on evolving Directed Acyclic Graphs (DAGs), defining a more flexible search space than the existing ones in the literature. It allows mixtures of different classical operations: convolutions, recurrences and dense layers, but also more newfangled operations such as self-attention. Based on this search space we propose neighbourhood and evolution search operators to optimize both the architecture and hyper-parameters of our networks. These search operators can be used with any metaheuristic capable of handling mixed search spaces. We tested our algorithmic framework with an asynchronous evolutionary algorithm on a time series forecasting benchmark. The results demonstrate that DRAGON outperforms state-of-the-art handcrafted models and AutoML techniques for time series forecasting on numerous datasets. DRAGON has been implemented as a python open-source package.

Multi-objective reinforcement learning algorithms (MORL) extend standard reinforcement learning (RL) to scenarios where agents must optimize multiple---potentially conflicting---objectives, each represented by a distinct reward function. To facilitate and accelerate research and benchmarking in multi-objective RL problems, we introduce a comprehensive collection of software libraries that includes: (i) MO-Gymnasium, an easy-to-use and flexible API enabling the rapid construction of novel MORL environments. It also includes more than 20 environments under this API. This allows researchers to effortlessly evaluate any algorithms on any existing domains; (ii) MORL-Baselines, a collection of reliable and efficient implementations of state-of-the-art MORL algorithms, designed to provide a solid foundation for advancing research. Notably, all algorithms are inherently compatible with MO-Gymnasium; and(iii) a thorough and robust set of benchmark results and comparisons of MORL-Baselines algorithms, tested across various challenging MO-Gymnasium environments. These benchmarks were constructed to serve as guidelines for the research community, underscoring the properties, advantages, and limitations of each particular state-of-the-art method.

The interest in Unmanned Aerial Vehicles (UAVs) for civilian applications has seen a drastic increase in the past few years. Indeed, UAVs feature unique properties such as three-dimensional mobility and payload flexibility which provide unprecedented advantages when conducting missions like infrastructure inspection or search and rescue. However their current usage is mainly limited to a single operated or autonomous device which brings several limitations like its range of action and resilience. Using several UAVs as a swarm is one promising approach to address those limitations. However, manually designing globally efficient swarming approaches that solely rely on distributed behaviours is a complex task. The goal of this work is thus to automate the design of UAV swarming behaviours to tackle an area coverage problem. The first contribution of this work consists in modelling this problem as a multi-objective optimisation problem. The second contribution is a hyper-heuristic based on multi-objective reinforcement learning for generating distributed heuristics for that problem. Experimental results demonstrate the good stability of the generated heuristic on instances with different sizes and its capacity to well balance the multiple objectives of the optimisation problem.

The ever-increasing complexity of both Deep Neural Networks (DNN) and hardware accelerators has made the co-optimization of these domains extremely complex. Previous works typically focus on optimizing DNNs given a fixed hardware configuration or optimizing a specific hardware architecture given a fixed DNN model. Recently, the importance of the joint exploration of the two spaces drew more and more attention. Our work targets the co-optimization of DNN and hardware configurations on edge GPU accelerators. We propose an evolutionary-based co-optimization strategy by considering three metrics: DNN accuracy, execution latency, and power consumption. By combining the two search spaces, a larger number of configurations can be explored in a short time interval. In addition, a better tradeoff between DNN accuracy and hardware efficiency can be obtained. Experimental results show that the co-optimization outperforms the optimization of DNN for fixed hardware configuration with up to 53% hardware efficiency gains with the same accuracy and inference time.

International audience

Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present preliminary results of a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. For sufficiently large problem instances and beam widths our work-in-progress implementation in the JIT-compiled Julia language admits promising speed-ups over 30x on 32 cores with uniform memory access for the Permutation Flow Shop Scheduling (PFSP) problem with flowtime objective.

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.

Data Envelopment Analysis (DEA) is a nonparametric methodology for estimating technical efficiency of a set of Decision Making Units (DMUs) from a dataset of inputs and outputs. This paper is devoted to computational aspects of DEA models under the application of the Principle of Least Action. This principle guarantees that the efficient closest targets are determined as benchmarks for each assessed unit. Usually, these models have been addressed in the literature by applying unsatisfactory techniques, based fundamentally on combinatorial NP-hard problems. Recently, some heuristics have been developed to partially solve these DEA models. This paper improves the heuristic methods used in previous works by applying a combination of metaheuristics and an exact method. Also, a parameterized scheme of metaheuristics is developed in order to implement metaheuristics and hybridations/combinations, adapting them to the particular problem proposed here. In this scheme, some parameters are used to study several types of metaheuristics, like Greedy Random Adaptative Search Procedure, Genetic Algorithms or Scatter Search. The exact method is included inside the metaheuristic to solve the particular model presented in this paper. A hyperheuristic is used on top of the parameterized scheme in order to search, in the space of metaheuristics, for metaheuristics that provide solutions close to the optimum. The method is competitive with exact methods, obtaining fitness close to the optimum with low computational time.

We propose the first large-scale message passing distributed scheme for parallelizing the computational flow of Moea/d, a popular decomposition-based evolutionary multiobjective optimization algorithm. We show how synchronicity and workload granularity can impact both quality and computing time, in an extremely fine-grained configuration where each individual in the Moea/d population is mapped to a single distributed processing unit. More specifically, we deploy our distributed protocol using a large-scale environment of 128 computing cores and conduct a throughout analysis using a broad range of bi-objective combinatorial ρMNK-landscapes. Besides being able to show significant speed-ups while maintaining competitive search quality, our experimental results provide insights into the behavior of the proposed scheme in terms of quality/speedup trade-offs; thus pushing a step towards the achievement of effective and efficient parallel decomposition-based approaches for large-scale multi-objective optimization.

In this paper an iterated local search (ILS) is embedded with a variable neighborhood Descent (VND) hyper-heuristic. The proposed hyper-heuristic combines low-level heuristics. Several variants from the literature within the proposed ILS were implemented and tested. This article conducts an empirical study involving hard combinatorial optimization problems, permutation flowshop scheduling problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. The proposed ILS based hyper-heuristic proved its general and applicable across the studied problems.

Solving to optimality large instances of combinatorial optimization problems using Brand and Bound (B&B) algorithms requires a huge amount of computing resources. In this paper, we investigate the design and implementation of such algorithms on computational grids. Most of existing grid-based B&B algorithms are based on the Master-Worker paradigm, their scalability is therefore limited. In addition, even if the volatility of resources is a major issue in grids fault tolerance is rarely addressed in these works. We thereby propose FTH-B&B, a fault tolerant hierarchical B&B. FTH-B&B is based on different new mechanisms enabling to efficiently build and maintain balanced the hierarchy, and to store and recover work units (sub-problems). FTH-B&B has been implemented on top of the ProActive grid middleware and programming environment and applied to the Flow-Shop scheduling problem. Very often, the validation of existing grid-based B&B works is performed either through simulation or a very small real grid. In this paper, we experimented FTH-B&B on the Grid’5000 real French nation-wide computational grid using up to 1,900 processor cores distributed over six sites. The reported results show that the overhead induced by the proposed mechanisms is very low and an efficiency close to 100 percent can be achieved on some Taillards benchmarks of the Flow-Shop problem. In addition, the results demonstrate the robustness of the proposed mechanisms even in extreme failure situations.

In this paper, we deal with cloud brokering for the assignment optimization of VM requests in three-tier cloud infrastructures. We investigate the Pareto-based meta-heuristic approach to take into account multiple client and broker-centric optimization criteria. We propose a new multi-objective Genetic Algorithm (MOGA-CB ) that can be integrated in a cloud broker. Two objectives are considered in the optimization process: minimizing both the response time and the cost of the selected VM instances to satisfy the clients and to maximize the profit of the broker. The approach has been experimented using realistic data of different types of Amazon EC2 instances and their pricing history. The reported results show that MOGA-CB provides efficiently effective Pareto sets of solutions.

Public cloud computing allows one to rent virtual servers on a hourly basis. This raises the problematic of being able to decide which server offers to take, which providers to use, and how to use them to acquire sufficient service capacity, while maintaining a cost effective platform. This article proposes a new realistic model to tackle the problem, placing services into IAAS virtual machines from multiple providers. A flexible protocol is defined to generate real-life instances, and applied on two industrial cases with four real cloud providers. An evolutionary approach, with new specific operators, is introduced and compared to a MIP formulation. Experiments conducted on two data-sets show that the evolutionary approach is viable to tackle real-size instances in reasonable amount of time.

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

In this paper, we propose a pioneering framework called ParadisEO-MO-GPU for the reusable design and implementation of parallel local search metaheuristics (S- Metaheuristics)on Graphics Processing Units (GPU). We revisit the ParadisEO-MO software framework to allow its utilization on GPU accelerators focusing on the parallel iteration-level model, the major parallel model for S- Metaheuristics. It consists in the parallel exploration of the neighborhood of a problem solution. The challenge is on the one hand to rethink the design and implementation of this model optimizing the data transfer between the CPU and the GPU. On the other hand, the objective is to make the GPU as transparent as possible for the user minimizing his or her involvement in its management. In this paper, we propose solutions to this challenge as an extension of the ParadisEO framework. The first release of the new GPU-based ParadisEO framework has been experimented on the permuted perceptron problem. The preliminary results are convincing, both in terms of flexibility and easiness of reuse at implementation, and in terms of efficiency at execution on GPU.

Global optimization in large-scale distributed systems requires massive amounts of computations for complex objective functions. Conventional global optimization based on stochastic algorithms cannot guarantee an actual global optimum with a finite searching iteration. Therefore, scalability is a desirable feature for the optimization techniques in highly distributed dynamic environments, where the storage and computing capabilities can be spread over a wide geographical area. They must dynamically adapt to organizational relationships and real-world uncertainties. Intelligent Networks, such as grids, peer-to-peer, ad hoc networks, constellations, and clouds enable the flexible routing and charging, advanced user interactions and the aggregation and sharing of geographically distributed resources. Collectively owned and managed by distinct organizational bodies, such complex large-scale distributed systems typically encompass computational resources from different institutions, enterprises, and individuals and are governed by heterogeneous administrative policies and regulations. System management techniques must therefore be able to group, predict, and classify different sets of rules, configuration directives, and environmental conditions to impose dissimilar usage policies on various users and resources. They must effectively deal with various optimization criteria, users’ requirements, massive data processing, and, finally, uncertainties in system information that may be incomplete, imprecise, and fragmentary. Next information technology architectures, such as green cloud-to-cloud systems and green mobile clouds, provide elastic and in fact unlimited resources, including storage, as various services to cloud users with possible minimal energy utilization. However, both cloud users and cloud service providers are almost certain to be from different trust domains. Therefore, a secure user-enforced data access control mechanism must be provided before cloud users have the liberty to outsource sensitive data to the cloud for storage and further processing. With the advent of intelligent networks, where efficient interdomain operation and high scalability of the whole system are the most important features, it is arguably required to investigate novel methods and techniques to enable secure access to data and resources, flexible communication, efficient scheduling, self-adaptation, decentralization, and self-organization. This special issue herewith presents six research papers with novel concepts in the analysis, implementation, and evaluation of the next generation of intelligent scalable techniques for data-intensive processing and global optimization problems in large-scale distributed systems. The first three papers discuss novel scalable solutions of data-intensive global optimization problems in well-known large-scale network environments. The presented techniques and their implementations are based on formal mathematical and logical models with the new optimization criteria (energy conservation), semantic rules and ontology, and modern synchronization modules of parallel computational processes. Li et al. in 1 introduced a methodology for improvement of the performance of the dynamic core of Global/Regional Assimilation and Prediction System (GRAPES) – the Numerical Weather Prediction system used by Chinese Meteorology Administration. The system performance is formally modeled as a sequence of large, sparse linear systems formulated by the discretization of global 3D Helmholtz equation. The authors developed a solver that enables an effective synchronization of the numerical processes at the global units of the system. The results of simple empirical analysis show good scalability of the proposed methodology achieved by using up to 6144 active cores in GRAPES. In 2, the authors present a framework for the energy-aware system management in backbone networks. The energy optimization problem is formulated as a general mathematical programming problem with various constraints and control parameters. Dynamic voltage and frequency scaling method is implemented for minimizing the energy utilization at global and local levels of the management system along with a wide range of the resolution methodologies. All possible energy saving decisions of the system units are directly specified, together with decisions concerning traffic assignment to particular links. The results of the experiments show the best performance of the system in the case of concentration of the network traffic on a minimal subset of network components. The problem of massive processing of huge volumes of data in the Internet is discussed in 3. Dong and Hussein propose an ontology-based Web crawler and Web page classifier with an embedded semisupervised learning module. This module enables the continuous enrichment of the definitions of ontological concepts in crawling and Web page classification process. The semantic relevance of crawling topics and Web pages is specified by semantic similarity and probabilistic models. The remaining three papers address the big-data paradigm from various perspective. Bilal et al. 4 benchmark some well-known data center network architectures and categorically state their pros and cons. With this knowledge, the authors propose future advancements pertaining to the network architecture of data centers. In 5, a generic data-structure oriented programming template is discussed for supporting massive remote sensing data. The authors have built the case that the templates provide distributed abstractions for large remote sensing image data with complex data structures. The performance of their technique is improved by developing efficient parallel input/output (I/O) directly to and from the distributed data structures. Zhang et al. 6 have discussed an advanced data center architecture that harness the power of multiple data centers. The key technology that they advocate to manage such a large-scale distributed computing system is to build on both groups of distributed data centers/clusters that are equipped with data center or cluster resource manager. Additional security and access control procedures are put in place to provide a seamless interaction between various domains. In addition to a structure, the domain data centers are organized as collaborative modules, which enables processing of workflow workloads. We believe that all of the papers presented in this Special Issue ought to serve as a reference for students, researchers, and industry practitioners interested or currently working in the evolving and interdisciplinary area of scalable computing and intelligent networking. We hope that the readers will find new inspiration for their research. We are grateful to all the contributors of this issue. We thank the authors for their time and efforts in the presentation of their recent research results. We also would like to express our sincere thanks to the reviewers, who have helped us to ensure the quality of this publication. Our special thanks go to Prof Geoffrey C. Fox (Editor-in-Chief) and all of the editorial and management team of Concurrency and Computation: Practice and Experience Wiley journal for their great support throughout the entire publication process.

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.

This article presents CoBRA, a new evolutionary algorithm, based on a coevolutionary scheme, to solve bi-level optimization problems. It handles population-based algorithms on each level, each one cooperating with the other to provide solutions for the overall problem. Moreover, in order to evaluate the relevance of CoBRA against more classical approaches, a new performance assessment methodology, based on rationality, is introduced. An experimental analysis is conducted on a bi-level distribution planning problem, where multiple manufacturing plants deliver items to depots, and where a distribution company controls several depots and distributes items from depots to retailers. The experimental results reveal significant enhancements, particularly over the lower level, with respect to a more classical approach based on a hierarchical scheme.

Biclustering is a well-known data mining problem in the field of gene expression data. It consists in extracting genes that behave similarly under some experimental conditions. As the Biclustering problem is NP-Complete in most of its variants, many heuristics and metaheuristics are defined to solve for it. Classical algorithms allow the extraction of some biclusters in reasonable time, however most of them remain time consuming. In this work, we propose a new hybrid multi-objective meta-heuristic H-MOBI based on NSGA-II (Non-dominated Sorting Genetic Algorithm II), CC (Cheng and Church) heuristic and a multi-objective local search PLS-1 (Pareto Local Search 1). Experimental results on real data sets show that our approach can find significant biclusters of high quality.

Microarrays are a powerful tool in studying genes expressions under several conditions. The obtained data need to be analyzed using data mining methods. Biclustering is a data mining method which consists in simultaneous clustering of rows and columns in a data matrix. Using biclustering, we can extract genes that have similar behavior (co-express) under specific conditions. These genes may share identical biological functions. The aim in analyzing gene expression data is the extraction of maximal number of genes and conditions that present similar behavior. The two objectives to be optimized (size and similarity) are conflicting. Therefore, multi-objective optimization is suitable for biclustering. In our work, we combine a well-known multi-objective genetic algorithm (NSGA-II) with a heuristic to solve the biclutering problem. Due to the huge size of the datasets, we use a string of integers as a solution representation where integers represent the indexes of the rows and the columns. Experimental results on real data set show that our approach can find significant biclusters of high quality.

Usually, the combinatorial optimization problems are modeled in a static way. All data are known in advance, i.e., before the optimization process has started. But in practice, many problems are dynamic, and change during the time. For the Dynamic Vehicle Routing Problem (DVRP), new orders arrive when the working day plan is in progress. Thus, the routes must be reconfigured dynamically during the optimization process. The Particle Swarm Optimization has been previously used to solve continuous dynamic optimization problems, whereas only, few works were proposed for combinatorial ones. In this paper, we present an Adaptive Particle Swarm for solving the Vehicle Routing Problem with Dynamic Requests (VRPDR). The effectiveness of this approach is evaluated thanks to a well-known set of benchmarks. It is compared with different population based metaheuristics, and a single-solution based metaheuristic. Experimental results show that our approach may significantly decrease travel distances, and is adaptive with respect to dynamic environment.

The quadratic 3-dimensional assignment problem (Q3AP) is an extension of the well-known NP-hard quadratic assignment problem. It has been proved to be one of the most difficult combinatorial optimization problems. Local search (LS) algorithms are a class of heuristics which have been successfully applied to solve such hard optimization problem. These methods handle with a single solution iteratively improved by exploring its neighborhood in the solution space. In this paper, we propose an iterated tabu search for solving the Q3AP. The design of this algorithm is essentially based on a new large neighborhood structure. Indeed, in LS heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions. However, designing such neighborhood is at the expense of a highly computationally process. Therefore, the use of graphics processing units (GPUs) provides an efficient complementary way to speed up the search. The proposed GPU-based iterated tabu search has been experimented on 5 different Q3AP instances. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.

We consider the Molecular Distance Geometry Problem (MDGP), which is the problem of finding the conformation of a molecule from some known distances between its atoms. Such distances can be estimated by performing experiments of Nuclear Magnetic Resonance (NMR). Unfortunately, data obtained during these experiments are usually noisy and affected by errors. In particular, some of the estimated distances can be wrong, typically because assigned to the wrong pair of atoms. When particular assumptions are satisfied, the problem can be discretized, and solved by employing an ad-hoc algorithm called Branch & Prune (BP). However, this algorithm has been proved to be less efficient than a meta-heuristic algorithm when the percentage of wrong distances is large. We propose a parallel version of the BP algorithm which is able to handle this kind of instances. The scalability of the proposed algorithm allows for solving very large instances containing wrong distances. Implementation details of the algorithm in C/MPI are discussed, and computational experiments, performed on the nation-wide grid infrastructure Grid5000, are presented.

Over the last years, interest in hybrid meta-heuristics has risen considerably in the field of optimization. Combinations of methods such as evolutionary algorithms and local searches have provided very powerful search algorithms. However, due to their complexity, the computational time of the solution search exploration remains exorbitant when large problem instances are to be solved. Therefore, the use of GPU-based parallel computing is required as a complementary way to speed up the search. This paper presents a new methodology to design and implement efficiently and effectively hybrid evolutionary algorithms on GPU accelerators. The methodology enables efficient mappings of the explored search space onto the GPU memory hierarchy. The experimental results show that the approach is very efficient especially for large problem instances.

When dealing with exponential search spaces and when no special knowledge is available on global optima, initial populations for population-based meta-heuristics should be uniformly distributed on the search space in order to sample basins of attraction of all local optima. In this paper, we propose a new initialization strategy for permutation problems. The new method is based on an original tree representation of the search space. Such representation was previously used for exact methods but never for meta-heuristics. The proposed method has been tested using a parallel Genetic Algorithm implemented in the ParadisEO framework and experimented on the Nationwide Grid5000 experimental grid using the Q3AP (3D QAP) permutation problem. The preliminary results are promising.

Precedence-constrained parallel applications are one of the most typical application model used in scientific and engineering fields. Almost all efforts, on this kind of applications, have focused on the minimization of makespan (completion time). It is only recently that much attention has been paid to energy consumption. In this paper, we address the precedence-constrained parallel applications on heterogeneous computing systems (HCSs). We propose a new bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. This metaheuristic adopts dynamic voltage scaling (DVS) to minimize energy consumption. Our study provides promising results showing the significance and potential of DVS. The experimental results from our comparative evaluation study confirm the superior performance of our approach over the other known heuristics on the two criteria energy saving and completion time.

In real life optimization problems, it is very important to have high quality solutions (optimal). But when uncertainty becomes part of the optimization problem, solutions should be optimal and robust to the uncertain environmental changes. This paper focuses on finding robust optimal solution for the vehicle routing problem with stochastic demands VRPSD. In this case when the uncertainty of the customers demands enters this problem, the classical methods of VRP can not be used to obtain optimal solutions. We need new methods with new strategies to have robust optimal solution. For that we propose two bi-objective models, depending on the multi-objective evolutionary algorithms MOEAs: IBEA, MOGA and NSGAII. We compare the robustness degree of the two models and also we compare the performance of the three MOEAs over these two models.

The island model for evolutionary algorithms allows to delay the global convergence of the evolution process and encourage diversity. However, solving large size and time-intensive combinatorial optimization problems with the island model requires a large amount of computational resources. GPU computing is recently revealed as a powerful way to harness these resources. In this paper, we focus on the parallel island model on GPU. We address its re-design, implementation, and associated issues related to the GPU execution context. The preliminary results demonstrate the effectiveness of the proposed approaches and their capabilities to fully exploit the GPU architecture.

Given a palette P of at most V colors, and a parameter d, a (d, V)-coloring of a graph is an assignment of a color from the palette P to every node in the graph such that any two nodes at distance at most d have different colors. We prove that for every n-node unit disk graph with maximum degree Δ, there exists a distributed algorithm computing a (1,O(Δ))-coloring under the SINR (Signal-to-Interferenceplus-Noise Ratio) physical model in at most O(Δ log n) time slots, which is optimal up to a logarithmic factor. Our result is based on revisiting a previous coloring algorithm, due to T. Moscibroda and R. Wattenhofer, described in the so called graph-based model. We also prove that, for a well defined constant d, a (d, O(Δ))-coloring allows us to schedule an interference free TDMA-like MAC protocol under the physical SINR constraints. As a corollary, any uniform interferencefree message passing algorithm with running time r can be simulated in the SINR model in O(Δ(log n+τ)) time slots. The latter generic result provides new insights into the distributed scheduling of radio network tasks under the harsh SINR constraints.

Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of epsilon-dominance. Though bounds on the quality of the limit approximation-which are entirely determined by the archiving strategy and the value of epsilon-have been obtained, the strategies do not guarantee to obtain a gap free approximation of the Pareto front. That is, such approximations A can reveal gaps in the sense that points f in the Pareto front can exist such that the distance of f to any image point F(a), a epsilon A, is "large." Since such gap free approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included in the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs, we give some numerical results to visualize the behavior of the different archiving strategies. Finally, we demonstrate the potential for a possible hybridization of a given stochastic search algorithm with a particular local search strategy-multi-objective continuation methods-by showing that the concept of epsilon-dominance can be integrated into this approach in a suitable way.

Conformational sampling, the computational prediction of the experimental geometries of small proteins (folding) or of protein-ligand complexes (docking), is often cited as one of the most challenging multimodal optimization problems. Due to the extreme ruggedness of the energy landscape as a function of geometry, sampling heuristics must rely on an appropriate trade-off between global and local searching efforts. A previously reported ldquoplanetary strategyrdquo, a generalization of the classical island model used to deploy a hybrid genetic algorithm on computer grids, has shown a good ability to quickly discover low-energy geometries of small proteins and sugars, and sometimes even pinpoint their native structures-although not reproducibly. The procedure focused on broad exploration and used a tabu strategy to avoid revisiting the neighborhood of known solutions, at the risk of ldquoburyingrdquo important minima in overhastily set tabu areas. The strategy reported here, termed ldquodivide-and-conquer planetary modelrdquo couples this global search procedure to a local search tool. Grid nodes are now shared between global and local exploration tasks. The phase space is cut into ldquocellsrdquo corresponding to a specified sampling width for each of the N degrees of freedom. Global search locates cells containing low-energy geometries. Local searches pinpoint even deeper minima within a cell. Sampling width controls the important trade-off between the number of cells and the local search effort needed to reproducibly sample each cell. The probability to submit a cell to local search depends on the energy of the most stable geometry found within. Local searches are allotted limited resources and are not expected to converge. However, as long as they manage to discover some deeper local minima, the explored cell remains eligible for further local search, now relying on the improved energy level to enhance chances to be picked again. This competition prevents the system to waste too much effort in fruitless local searches. Eventually, after a limited number of local searches, a cell will be ldquoclosedrdquo and used - first as ldquoseedrdquo, later as tabu zone-to bias future global searches. Technical details and some folding and docking results will be discussed.

In the absence of a priori knowledge about global optima, initial populations in genetic algorithms (GAs) should at least be diversified, especially while dealing with large spaces. On the other hand, the use of parallel models for GAs helps to solve large instances. We will focus on the island model. In this paper we propose an island initialization technique for permutation-based problems. We exploit a virtual tree organisation commonly used in exact methods (Branch and Bound) to generate a fully disjoint and well distributed (over the search space) initial population in each island. This method can be used for all permutation-based problems (QAP, Flow-shop, Q3AP..). regardless of the number of permutations. Experiments are performed over Q3AP benchmarks using a $10$ island model. The results shows the efficiency of the proposed method especially for large instances.

In this work, we hybridize the genetic quantum algorithm with the support vector machines classifier for gene selection and classification of high dimensional microarray data. We named our algorithm GQASVM. Its purpose is to identify a small subset of genes that could be used to separate two classes of samples with high accuracy. A comparison of the approach with different methods of literature, in particular GASVMand PSOSVM, was realized on six different datasets issued of microarray experiments dealing with cancer (leukemia, breast, colon, ovarian, prostate, and lung) and available on Web. The experiments clearified the very good performances of the method. A first contribution shows that the algorithm GQASVMis able to find genes of interest and improve the classification on a meaningful way. A second important contribution consists of the actual discovery of new and challenging results on datasets used.able to find genes of interest and improve the classification on a meaningful way. A second important contribution consists of the actual discovery of new and challenging results on datasets used.

We present a metaheuristic-based attack against the traceability of an ultra-lightweight authentication protocol for RFID environments called SLMAP, and analyse its implications. The main interest of our approach is that it is a complete black-box technique that doesn't make any assumptions on the components of the underlying protocol and can thus be easily generalised to analyse many other proposals.

In this paper we propose a parallel hybrid genetic method for solving Quadratic 3-dimensional Assignment Problem (Q3AP). This problem is proved to be computationally NP-hard. The parallelism in our algorithm is of two hierarchical levels. The first level is an insular model where a number of GAs (genetic algorithms) evolve in parallel. The second level is a parallel transformation of individuals in each GA. Implementation has been done using ParadisEO1 framework, and the experiments have been performed on GRID5000, the French nation-wide computational grid. To evaluate our method, we used three benchmarks derived from QAP instances of QAPLIB and the results are compared with those reported in the literature. The preliminary results show that the method is promising. The obtained solutions are close to the optimal values and the execution is efficient.

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

The integration of information provided by an a priori landscape analysis as a guiding tool for interactive EMO methods is proposed. For this purpose, a new type of a priori landscape analysis is introduced, namely ellipse enclosure of the feasible solutions set in the solution space. The interaction takes place in the solution space, the user having as visual guiding tools the computed enclosure as well as the set of solutions found at the previous search phase. Furthermore, reference points are specified by the user thus directing the search. The effectiveness and efficiency of the method are supported through statistical experimentation performed on the bi-objective permutation flow shop problem.

Molecular docking is an essential tool for drug design. It helps the scientist to rapidly know if two molecules, respectively called ligand and receptor, can be combined together to obtain a stable complex. We propose a new multi-objective model combining an energy term and a surface term to gain such complexes. The aim of our model is to provide complexes with a low energy and low surface. This model has been validated with two multi-objective genetic algorithms on instances from the literature dedicated to the docking benchmarking.

The branch and bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimization problems. In a previous article, we proposed a new approach of the parallel B&B algorithm for distributed systems using the farmer-worker paradigm. However, the new farmer-worker approach has a disadvantage: some nodes of the B&B tree can be explored by several B&B processes. To prevent this redundant work and speed up, we propose a new P2P approach inspired from the strategies of existing P2P systems like Napster and JXTA. Validation is performed by experimenting the two approaches on mono-objective flow-shop problem instances using 500 processors belonging to the French national grid, Grid'5000. The obtained results prove the efficiency of the proposed P2P approach. Indeed, the execution time obtained with the P2P version, even if more communicative, is better than the farmer-worker's one.

In this work we study the convergence of generic stochastic search algorithms toward the entire set of approximate solutions of continuous multi-objective optimization problems. Since the dimension of the set of interest is typically equal to the dimension of the parameter space, we focus on obtaining a finite and tight approximation, measured by the Hausdorff distance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.

Common evolutionary approaches to protein-ligand docking optimization use mutation operators based on Gaussian and Cauchy distributions, with local search hybrids. The choice of a local search method is important for an efficient algorithm. We investigate the impact of local search with mutation operators by performing a locality analysis. High locality means that small variations in the genotype imply small variations in the phenotype. Results show that local search hybrids reduce locality and act as local optimizers with the solution as a starting point.

The main interest of this paper is the optimization of the location areas planning in cellular radio networks. It is well known that the quality of service in mobile networks depends on many parameters, among them an optimal location area planning. Furthermore, it is more interesting to provide a logical organization for the already deployed networks. In this paper, we propose the use of heuristics strategies and hybrid metaheuristics strategies to solve the location areas planning problem. The latter is formulated as a constrained planar graph partitioning problem by using a mathematical model which is based on a very realistic specification. Heuristics strategies are based on greedy algorithms while hybrid metaheuristics are based on genetic algorithms. New genetic operators have been designed to this specific problem. Moreover, parallel approaches have been proposed to improve the quality of solutions and speedup the search. Results obtained on real-life benchmarks show the effectiveness of the developed optimization algorithms.

Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm requires a huge amount of computational resources. The efficiency of such algorithm can be improved by distributing at large scale the computation required by the exploration of the search tree. In this paper, we propose ParallelBB, which is a P2P-based parallelization of the Branch-and-Bound algorithm for the computational Grid. The algorithm has been implemented using the ProActive distributed object Grid middleware. The algorithm has been applied to a mono- criterion permutation flow-shop problem and promisingly experimented on the Grid5000 computational Grid.

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 using a binary representation in Hamming space. 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).

Computational simulations of conformational sampling in general, and of macromolecular folding in particular represent one of the most important and yet one of the most challenging applications of computer science in biology and medicinal chemistry. The advent of GRID computing may trigger some major progress in this field. This paper presents our first attempts to design GRID-based conformational sampling strategies, exploring the extremely rugged energy response surface in function of molecular geometry, in search of low energy zones through phase spaces of hundreds of degrees of freedom. We have generalized the classical island model deployment of genetic algorithms (GA) to a "planetary" model where each node of the grid is assimilated to a "planet" harboring quasi-independent multi-island simulations based on a hybrid GA-driven sampling approach. Although different "planets" do not communicate to each other-thus minimizing inter-CPU exchanges on the GRID-each new simulation will benefit from the preliminary knowledge extracted from the centralized pool of already visited geometries, located on the dispatcher machine, and which is disseminated to any new "planet". This "panspermic" strategy allows new simulations to be conducted such as to either be attracted towards an apparently promising phase space zone (biasing strategies, intensification procedures) or to avoid already in-depth sampled (tabu) areas. Successful folding of mini-proteins typically used in benchmarks for all- atoms protein simulations has been observed, although the reproducibility of these highly stochastic simulations in huge problem spaces is still in need of improvement. Work on two structured peptides (the "tryptophane cage" 1L2Y and the "tryptophane zipper" 1LE1) used as benchmarks for all-atom protein folding simulations has shown that the planetary model is able to reproducibly sample conformers from the neighborhood of the native geometries. However, within these neighborhoods (within ensembles of conformers similar to models published on hand of experimental geometry determinations), the energy landscapes are still extremely rugged. Therefore, simulations in general produce "correct" geometries (similar enough to experimental model for any practical purposes) which sometimes unfortunately correspond to relatively high energy levels and therefore are less stable than the most stable among misfolded conformers. The method thus reproducibly visits the native phase space zone, but fails to reproducibly hit the bottom of its rugged energy well. Intensifications of local sampling may in principle solve this problematic behavior, but is limited by computational resources. The quest for the optimal time point at which a phase space zone should stop being intensively searched and declared tabu, a very difficult problem, is still awaiting for a practically useful solution.

Real or academic combinatorial optimization problems are in the majority NP-hard. For large dimensions, an exact resolution is often impractical due to a limited amount of resources. The use of large scale deployment on distributed systems such as peer-to-peer (P2P) systems, based on exploiting free CPU cycles, provides an efficient way to reach high computing performance by distributing the computation to solve these problems. In this paper, we are interested in solving exactly optimization problems using parallel branch-and-bound algorithm on large scale distributed systems. We propose ParallelBB, which is a parallelization of the branch-and-bound algorithm and apply it to a mono-criterion permutation flow-shop problem. Furthermore, we develop P2PBB, which is the peer-to-peer implementation of our algorithm using ProActive

No abstract available.

Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of ε-dominance. Though bounds on the quality of the limit approximation -- which are entirely determined by the archiving strategy and the value of ε -- have been obtained, the strategies do not guarantee to obtain a gap-free Pareto front approximation. Since such approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included into the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs we give somenumerical results to visualize the behavior of the different archiving strategies.

Solving optimally large instances of combinatorial optimization problems requires a huge amount of computational resources. In this paper, we propose an adaptation of the parallel branch and bound algorithm for computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing, fault tolerance, global information sharing and termination detection of the algorithm. A new efficient coding of the work units (search sub-trees) distributed during the exploration of the search tree is proposed to optimize the involved communications. The algorithm has been implemented following a large scale idle time stealing paradigm (Farmer-Worker). It has been experimented on a flow-shop problem instance (Ta056) that has never been optimally solved. The new algorithm allowed to realize a success story as the optimal solution has been found with proof of optimality, within 25 days using about 1900 processors belonging to 9 Nation-wide distinct clusters (administration domains). During the resolution, the worker processors were exploited with an average of 97% while the farmer processor was exploited only 1.7% of the time. These two rates are good indicators on the efficiency of the proposed approach and its scalability.

A comparative study of parallel metaheuristics executed in grid environments is proposed, having as case study a genetic algorithm, a simulated annealing algorithm and a random search method. The random search method was constructed in order to offer a lower bound for the comparison. Furthermore, a conjugated gradient local search method is employed for each of the algorithms, at different points on the execution path. The algorithms are evaluated using the protein structure prediction problem, the benchmark instances consisting of the tryptophan-cage protein (Brookhaven protein data bank ID 1L2Y) and alpha-cyclodextrin. The algorithms are designed to benefit from the grid environment although having no particular optimization for the specified benchmarks. The presented results are obtained by running the algorithms independently and, in a second time, in conjunction with the conjugated gradient search method. Experimentations were performed on a nation-wide grid reuniting five distinct administrative domains and cumulating 400 CPUs. The complexity of the protein structure prediction problem remains prohibitive as far as large proteins are concerned, making the use of parallel computing on the computational grid essential for its efficient resolution.

The branch and bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimization problems. This article focuses on the multi-objective version of this algorithm, and proposes a new parallel approach adapted to grid computing systems. This approach addresses several issues related to the characteristics of the algorithm itself and the properties of grid computing systems. Validation is performed by experimenting the approach on a bi-objective flow-shop problem instance that has never been solved exactly. Solving this instance, after several days of computation on a grid of more than 1000 processors, belonging to 7 distinct clusters, the obtained results prove the efficiency of the proposed approach

In this paper we introduce line search strategies originating from continuous optimization for the realization of the guidance mechanism in particle swarm optimization for scalar optimization problems. Since these techniques are well-suited for-but not restricted to-local search the resulting algorithm can be considered to be memetic. Further, we will use the same techniques for the construction of a new variant of a hill climber. We will discuss possible realizations and will finally present some numerical results indicating the strength of the two algorithms

Protein identification is one of the major task of Proteomics researchers. Protein identification could be resumed by searching the best match between an experimental mass spectrum and proteins from a database. Nevertheless this approach can not be used to identify new proteins or protein variants. In this paper an evolutionary approach is proposed to discover new proteins or protein variants thanks a "de novo sequencing" method. This approach has been experimented on a specific grid called Grid5000 with simulated spectra and also real spectra.

In Proteomics, only the de novo peptide sequencing approach allows a partial amino acid sequence of a peptide to be found from a MS/MS spectrum. In this article a preliminary work is presented to discover a complete protein sequence from spectral data (MS and MS/MS spectra). For the moment, our approach only uses MS spectra. A genetic algorithm (GA) has been designed with a new evaluation function which works directly with a complete MS spectrum as input and not with a mass list like the other methods using this kind of data. Thus the mono isotopic peak extraction step which needs a human intervention is deleted. The goal of this approach is to discover the sequence of unknown proteins and to allow a better understanding of the differences between experimental proteins and proteins from databases.

The focus of this paper is on the parallel multi-start and island models of meta-heuristics within the context of multiobjective optimization on the computational grid. The combination of these two models often provides very effective parallel algorithms. However, experiments on large-size problem instances are often stopped before the convergence of these algorithms is achieved. The full exploitation of the cooperation needs a large amount of computational resources and the management of the fault tolerance issue. In this paper, we propose a grid-based fault-tolerant approach for these models and their implementation on the XtremWeb grid middleware. The approach has been experimented on the bi-objective Flow-Shop problem on a computational grid which is a multi-domain education network composed of 321 heterogeneous Linux PCs. The preliminary results, obtained after an execution time of several days, demonstrate that the use of grid computing allows to fully exploit effectively and efficiently the two parallel models and their combination for solving challenging optimization problems. An improvement of the effectiveness by over 60% compared to a serial meta-heuristic is obtained with a computational grid.

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics - a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method - a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models - the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem - 50 jobs on 5 machines. More than 400 processors belonging to 4 administrative domains have contributed to the resolution process during more than 6 days

In this paper, we present ParadisEO-CMW, an extension of the open source ParadisEO framework, originally intended to the design and deployment of parallel hybrid meta heuristics on dedicated clusters of SMPs. Coupled with the Condor-MW library, it enables the execution of such parallel applications on volatile heterogeneous computational resources. The motivations, architecture and main features will be discussed. The framework has been tested by tackling a real-world NP-hard problem: feature selection in near-infrared spectroscopic data mining. It has been resolved by deploying a multi-level parallel model of evolutionary algorithms. Experimentations have been carried out on more than one hundred PCs originally intended for education. The obtained results are convincing, both in terms of flexibility and easiness at implementation, and in terms of efficiency and quality of provided solutions at execution.

This paper presents briefly the aims and challenges addressed in the GGM (Grid for Geno-Medicine) project. The idea behind the project is to offer a software infrastructure able to analyze and discover links between distributed medical and genetic data.

Knowledge discovery from DNA microarray data has become an important research area for biologists. Association rules is an important task of knowledge discovery that can be applied to the analysis of gene expression in order to identify patterns of genes and regulatory network. Association rules discovery may be modeled as an optimization problem. We propose a multicriteria model for association rules problem and present a genetic algorithm designed to deal with association rules on DNA microarray data, in order to obtain associations between genes. Hence, we expose the main features of the proposed genetic algorithm. We emphasize on specificities for the association rule problem (encoding, mutation and crossover operators) and on its multicriteria aspects. Results are given for real datasets.

Nowadays, in the heuristic and metaheuristics community, there is a schism between researchers who say: "we proved experimentally that a given heuristic provides good results on a given problem and we can guess that it is enough general to be applied for other problems", and those who claim: "the No Free Lunch theorem (NFL) proves that there exists no absolute efficient heuristic". The formers suspect the existence of a structure in the solved problem and that structure can occur in other problems. The latters fear that heuristics are especially adapted for the testbed problem this paper addresses structural aspect of combinatorial optimization problems. In a first time, we recall some related works which provide a frame to our work. Particularly, we recall the existence of deceptive problems which are proved to be hard to optimize, the definitions of the five scenarios of knowledge in optimization problem, and some works which already discuss the reach of NFL theorem. In the next part, we give a short overview of how NFL works and discuss its significance with regards to complexity. This leads to the observation that the notion of structure of optimization problems is missing in NFL use. Then, we prove that k-coloring problems respect such a notion of structure, for any k. In the last part we discuss the relevance of our work on four points: the polynomial reduction of NP-complete problems and structure preservation, the connection between our work and the study which squeeze NFL using neighborhood search operators, the position of our study on the five scenarios of knowledge, and finally the difference between metaheuristics and heuristics.

Summary form only given. We treat the linkage disequilibrium, used to discover haplotypes, candidate to explain multifactorial diseases such as diabetes or obesity, as an optimization problem where a given objective function has to be optimized. In order to determine what kind of algorithm is able to solve this problem, we first study the specificities and the structure of the problem. Results of this study show that exact algorithms are not adapted to this specific problem and lead us to the development of a parallel dedicated adaptive multipopulation genetic algorithm that is able to find several haplotypes of different sizes. After describing the biological problem, we present the dedicated genetic algorithm, its specificities, such as the use of several populations and its advanced mechanisms such as the adaptive choice of operators, random immigrants, and its parallel implementation. We give results on a real dataset.

Multi-objective optimization using evolutionary algorithms has been extensively studied in the literature. We propose formal methods to solve problems appearing frequently in the design of such algorithms. To evaluate the effectiveness of the introduced mechanisms, we apply them to the flow-shop scheduling problem. We propose a dynamic mutation Pareto genetic algorithm (GA) in which different genetic operators are used simultaneously in an adaptive manner, taking into account the history of the search. We present a diversification mechanism which combines sharing in the objective space as well as in the decision space, in which the size of the niche is automatically calculated. We also propose a hybrid approach which combines the Pareto GA with local search. Finally, we propose two performance indicators to evaluate the effectiveness of the introduced mechanisms.

This paper presents a dynamic multi-application scheduling approach for running and scheduling parallel adaptive applications in Networks of Workstations (NOWs) and Clusters of Processors (COPs). Parallel adaptive applications have the property of varying their parallelism degree dynamically following availability of resources and changes in the underlying environment state. In our model, each parallel adaptive application is controlled by its own scheduler responsible for optimizing resources which it uses. Multi-application scheduling consists of sharing resources among applications fairly and uses a combined (time-sharing and space-sharing) scheduling approach. The scheduling approach is characterized especially by dynamic arrivals of applications, and remapping of allocation in order to handle dynamic arrivals and departures of applications and underlying environment state changes. Therefore, resources are fairly shared among applications. The multi-application scheduler interacts with the application schedulers in order to optimize the scheduling approach. The application schedulers are responsible for applying the multi-application scheduler decisions and internally optimizing the resources exploited by the application. Beyond the adaptive aspect which allows parallel applications to exploit idle cycles in NOWs with respect to the personal character of workstations, the proposed model provides a multi-application scheduling support which globally ensures better resource utilization and fair resource sharing.

Rule mining consists of discovering valid and useful rules in large databases. As other data mining tasks, it is known to be time-consuming and I/O intensive. Evolutionary algorithms and parallelism are two important ways to deal with that performance problem. In this paper, we propose a parallel genetic algorithm for rule discovery, namely . We evaluated it on the Nursery School public domain data set available from the UCI Repository of Machine Learning databases. The results show that is efficient and allows to discover high quality rules.

In order to show that the parallel co-evolution of different heuristic methods may lead to an efficient search strategy, we have hybridized three heuristic agents of complementary behaviours: A Tabu Search is used as the main search algorithm, a Genetic Algorithm is in charge of the diversification and a Kick Operator is applied to intensify the search. The three agents run simultaneously, they communicate and cooperate via an adaptive memory which contains a history of the search already done, focusing on high quality regions of the search space. This paper presents CO-SEARCH, the co-evolving heuristic we have designed, and its application on large scale instances of the quadratic assignment problem. The evaluations have been executed on large scale network of workstations via a parallel environment which supports fault tolerance and adaptive dynamic scheduling of tasks.

Engineering of mobile telecommunication networks endures two major problems: the design of the network and the frequency assignment. We address the first problem in this paper, which has been formulated as a multiobjective constrained combinatorial optimisation problem. We propose a genetic algorithm (GA) that aims to approximate the Pareto frontier of the problem. Advanced techniques have been used, such as Pareto ranking, sharing and elitism. The GA has been implemented in parallel on a network of workstations to speed up the search. To evaluate the performance of the GA, we have introduced two new quantitative indicators: the entropy and the contribution. Encouraging results are obtained on real-life problems.

The fitness function is generally defined rather straightforwardly in evolutionary algorithms (EA): it is simply the value of the function to optimize. We argue and show that embedding more information in the fitness function leads to a significant improvement of the quality of the local optima that are reached. The technique is developed here on NP-hard problems and demonstrated on the job-shop scheduling problem. The technique is first used in a mere steepest descent hill-climber in order to assess its usefulness. Then, it is shown that its use in an EA also improves its performance in terms of the quality of solutions that are found.

The goal of the work described is to build a path planner able to drive a robot in a dynamic environment where the obstacles are moving. In order to do so, the authors propose a method, called Ariadne's clew algorithm, to build a global path planner based on the combination of two local planning algorithms: an explore algorithm and a search algorithm. The purpose of the explore algorithm is to collect information about the environment with an increasingly fine resolution by placing landmarks in the searched space. The goal of the search algorithm is to opportunistically check if the target can be easily reached from any given placed landmark. The Ariadne's clew algorithm is shown to be very fast is most cases, allowing planning in dynamic environment. It is shown to be complete, which means that it is sure to find a path when one exists. A massively parallel implementation of this algorithm is described.

Article A parallel genetic algorithm for the graph partitioning problem Share on Authors: E.-G. Talbi Laboratoire de Génie Informatique / Institut IMAG, University of Grenoble Laboratoire de Génie Informatique / Institut IMAG, University of GrenobleView Profile , P. Bessière BP53X, F-38041 Grenoble, France and Laboratoire de Génie Informatique / Institut IMAG, University of Grenoble BP53X, F-38041 Grenoble, France and Laboratoire de Génie Informatique / Institut IMAG, University of GrenobleView Profile Authors Info & Claims ICS '91: Proceedings of the 5th international conference on SupercomputingJune 1991 Pages 312–320https://doi.org/10.1145/109025.109102Online:01 June 1991Publication History 39citation1,240DownloadsMetricsTotal Citations39Total Downloads1,240Last 12 Months29Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access