Branch-and-Bound (BB) is an exact method in integer programming that recursively divides the search space into a tree. During the resolution process, determining the next subproblem to explore within the tree—known as the search strategy—is crucial. Hand-crafted heuristics are commonly used, but none are effective over all problem classes. Recent approaches utilizing neural networks claim to make more intelligent decisions but are computationally expensive. In this paper, we introduce GP2S (Genetic Programming for Search Strategy), a novel machine learning approach that automatically generates a BB search strategy heuristic, aiming to make intelligent decisions while being computationally lightweight. We define a policy as a function that evaluates the quality of a BB node by combining features from the node and the problem; the search strategy policy is then defined by a best-first search based on this node ranking. The policy space is explored using a genetic programming algorithm, and the policy that achieves the best performance on a training set is selected. We compare our approach with the standard method of the SCIP solver, a recent graph neural network-based method, and handcrafted heuristics. Our first evaluation includes three types of primal hard problems, tested on instances similar to the training set and on larger instances. Our method is at most 2 percents slower than the best baseline and consistently outperforms SCIP, achieving an average speedup of 11.3 percents. Additionally, GP2S is tested on the MIPLIB 2017 dataset, generating multiple heuristics from different subsets of instances. It exceeds SCIP’s average performance in 7 out of 10 cases across 15 times more instances and under a time limit 15 times longer, with some GP2S methods leading on most experiments in terms of the number of feasible solutions or optimality gap.

Mining meaningful patterns from numerical healthcare data is challenging, as continuous lab values are difficult to analyze directly and traditional association rule mining often generates arbitrary thresholds. We introduce Threshold-Aware Association Rules (TAAR), a framework that converts continuous lab values into semantic intervals and extracts interpretable rules using an enhanced Apriori algorithm. Large Language Models (LLMs) are employed to refine support and confidence thresholds, filter implausible rules, and produce natural-language explanations. Applied to blood test data, TAAR improves clinical usability, guides actionable follow-up recommendations, and supports informed decision-making.

Mixed-integer linear programming (MILP) is a powerful tool for addressing a wide range of real-world problems, but it lacks a clear structure for comparing instances. A reliable similarity metric could establish meaningful relationships between instances, enabling more effective evaluation of instance set heterogeneity and providing better guidance to solvers, particularly when machine learning is involved. Existing similarity metrics often lack precision in identifying instance classes or rely heavily on labeled data, which limits their applicability and generalization. To bridge this gap, this paper introduces the first mathematical distance metric for MILP instances, derived directly from their mathematical formulations. By discretizing right-hand sides, weights, and variables into classes, the proposed metric draws inspiration from the Earth mover’s distance to quantify mismatches in weight-variable distributions for constraint comparisons. This approach naturally extends to enable instance-level comparisons. We evaluate both an exact and a greedy variant of our metric under various parameter settings, using the StrIPLIB dataset. Results show that all components of the metric contribute to class identification, and that the greedy version achieves accuracy nearly identical to the exact formulation while being nearly 200-times faster. Compared to state-of-the-art baselines—including feature-based, image-based, and neural network models—our unsupervised method consistently outperforms all non-learned approaches and rivals the performance of a supervised classifier on class and subclass grouping tasks.

The substantial increase in AI model training has considerable environmental implications, requiring energy-efficient and sustainable AI practices. On one hand, data-centric approaches show great potential towards training energy-efficient AI models. On the other hand, instance selection methods demonstrate the capability of training AI models with minimised training sets and negligible performance degradation. Despite the growing interest in both topics, the impact of data-centric training set selection on energy efficiency remains to date unexplored. This paper presents an evolutionary-based sampling framework aimed at (i) identifying elite training samples tailored for datasets and model pairs, (ii) comparing model performance and energy efficiency gains against typical model training practice, and (iii) investigating the feasibility of this framework for fostering sustainable model training practices. To evaluate the proposed framework, we conducted an empirical experiment including 8 commonly used AI classification models and 25 publicly available datasets. The results showcase that by considering 10% elite training samples, the models’ performance can show a 50% improvement and remarkable energy savings of 98% compared to the common training practice. In essence, this study establishes a new benchmark for AI researchers and practitioners interested in improving the environmental sustainability of AI model training via data-centric approaches.

Swarms of autonomous robots have become an interesting alternative for space and aerospace applications due to their versatility, robustness, and self-organising capability. Some of those applications, such as asteroid observation, convoy escort, and counter-drone systems, rely on stable formations achieved around a central point of interest. However, the use of different numbers of robots and the existence of a wide range of initial conditions contribute to make it a challenging problem. We propose in this research work a novel approach for self-organising a swarm of autonomous robots where the members’ movements depend only on their relative position (range and bearing) obtained from their respective radio beacons. An optimisation approach based on an evolutionary algorithm is proposed to calculate the optimal swarm’s parameters, e.g. speed and attracting/repelling forces, to achieve robust formations under different initial conditions and failure rates. Experiments are conducted using realistic simulations of six case studies featuring three, five, ten, fifteen, twenty, and thirty robots. The best valued configurations were tested on 420 scenarios showing that our proposal is robust since it has always achieved the desired circular formation. Finally, we have used real E-Puck2 robots to validate the swarm’s capability of self-organising around a central point of interest as well as its resilience to robot failure, obtaining successful circular formations in all the experiments.

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.

The computing continuum can enable new, novel big data use cases across the edge-cloud-supercomputer spectrum. Fast and high-volume data movement workflows rely on state-of-the-art architectures built on top of stream ingestion and file transfer open-source tools. Unfortunately, users struggle when faced with dealing with such diverse architectures: stream ingestion was designed for small-size datasets and low latency, while file transfer was designed for large-size datasets and high throughput. In this paper, we propose to unify ingestion and transfer, while introducing architectural design principles and discussing future implementation challenges.

Federated learning is a particular type of distributed machine learning, designed to permit the joint training of a single machine learning model by multiple participants that each possess a local dataset.A characteristic feature of federated learning strategies is the avoidance of any disclosure of client data to other participants of the learning scheme.While a wealth of well-performing solutions for different scenarios exists for Horizontal Federated Learning (HFL), to date little attention has been devoted to Vertical Federated Learning (VFL).Existing approaches are limited to narrow application scenarios where few clients participate, privacy is a main concern and the vertical distribution of client data is well-understood.In this article, we first argue that VFL is naturally applicable to another, much broader application context where sharing of data is mainly limited by technological instead of privacy constraints, such as in sensor networks or satellite swarms.A VFL scheme applied to such a setting could unlock previously inaccessible on-device machine learning potential.We then propose the Joint-embedding Vertical Federated Learning framework (JoVe-FL), a first VFL framework designed for such settings.JoVe-FL is based on the idea of transforming the vertical federated learning problem to a horizontal one by learning a joint embedding space, allowing us to leverage existing HFL solutions.Finally, we empirically demonstrate the feasibility of the approach on instances consisting of different partitionings of the CIFAR10 dataset.

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.

Autonomous robot swarm systems allow to address many inherent limitations of single robot systems, such as scalability and reliability. As a consequence, these have found their way into numerous applications including in the space and aerospace domains like swarm-based asteroid observation or counter-drone systems. However, achieving stable formations around a point of interest using different number of robots and diverse initial conditions can be challenging. In this article we propose a novel method for autonomous robots swarms self-organisation solely relying on their relative position (angle and distance). This work focuses on an evolutionary optimisation approach to calculate the parameters of the swarm, e.g. inter-robot distance, to achieve a reliable formation under different initial conditions. Experiments are conducted using realistic simulations and considering four case studies. The results observed after testing the optimal configurations on 72 unseen scenarios per case study showed the high robustness of our proposal since the desired formation was always achieved. The ability of self-organise around a point of interest maintaining a predefined fixed distance was also validated using real robots.

International audience

This paper presents the parameterisation and optimisation of the CACOC (Chaotic Ant Colony Optimisation for Coverage) mobility model used by an Unmanned Aerial Vehicle (UAV) swarm to perform surveillance tasks. CACOC uses chaotic solutions of a dynamical system and pheromones for optimising area coverage. Consequently, several parameters of CACOC are to be optimised with the aim of improving its coverage performance. We propose a Genetic Algorithm (GA) and two Cooperative Coevolutionary Genetic Algorithms (CCGA) to tackle this problem. After testing our proposals on four case studies we performed a comparative analysis to conclude that the cooperative approaches allow a better exploration of the search space by optimising each UAV parameters independently.

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is an NP-hard problem. In this paper, we tackle large-scale and combinatorial bi-level problems using GP hyper-heuristics, i.e., an approach that permits to train heuristics like a machine learning model. Our contribution aims at targeting the intensive and complex lower-level optimizations that occur when solving a large-scale and combinatorial bi-level problem. For this purpose, we consider hyper-heuristics through heuristic generation. Using a GP hyper-heuristic approach, we train greedy heuristics in order to make them more reliable when encountering unseen lower-level instances that could be generated during bi-level optimization. To validate our approach referred to as GA+AGH, we tackle instances from the bi-level cloud pricing optimization problem (BCPOP) that model the trading interactions between a cloud service provider and cloud service customers. Numerical results demonstrate the abilities of the trained heuristics to cope with the inherent nested structure that makes bi-level optimization problems so hard. Furthermore, it has been shown that training heuristics for lower-level optimization permits to outperform human-based heuristics and metaheuristics which constitute an excellent outcome for bi-level optimization.

The huge volume, variety, and velocity of big data have empowered Machine Learning (ML) techniques and Artificial Intelligence (AI) systems. However, the vast portion of data used to train AI systems is sensitive information. Hence, any vulnerability has a potentially disastrous impact on privacy aspects and security issues. Nevertheless, the increased demands for high-quality AI from governments and companies require the utilization of big data in the systems. Several studies have highlighted the threats of big data on different platforms and the countermeasures to reduce the risks caused by attacks. In this paper, we provide an overview of the existing threats which violate privacy aspects and security issues inflicted by big data as a primary driving force within the AI/ML workflow. We define an adversarial model to investigate the attacks. Additionally, we analyze and summarize the defense strategies and countermeasures of these attacks. Furthermore, due to the impact of AI systems in the market and the vast majority of business sectors, we also investigate Standards Developing Organizations (SDOs) that are actively involved in providing guidelines to protect the privacy and ensure the security of big data and AI systems. Our far-reaching goal is to bridge the research and standardization frame to increase the consistency and efficiency of AI systems developments guaranteeing customer satisfaction while transferring a high degree of trustworthiness.

Carsharing services have successfully established their presence and are now growing steadily in many cities around the globe. Carsharing helps to ease traffic congestion and reduce city pollution. To be efficient, carsharing fleet vehicles need to be located on city streets in high population density areas and considering demographics, parking restrictions, traffic and other relevant information in the area to satisfy travel demand. This work proposes to formulate the initial placement of a fleet of cars for a round-trip carsharing service as a multi-objective optimization problem. The performance of state-of-the-art metaheuristic algorithms, namely, SPEA2, NSGA-II, and NSGA-III, on this problem is evaluated on a novel benchmark composed of synthetic and real-world instances built from real demographic data and street network. Inverted generational distance (IGD), spread and hypervolume metrics are used to compare the algorithms. Our findings demonstrate that NSGA-II yields significantly lower IGD and higher hypervolume than the rest and SPEA2 has a significantly better diversity if compared with NSGA-II and NSGA-III.

Motivation: The root mean square deviation (RMSD) is one of the most used similarity criteria in structural biology and bioinformatics. Standard computation of the RMSD has a linear complexity with respect to the number of atoms in a molecule, making RMSD calculations time-consuming for the large-scale modeling applications, such as assessment of molecular docking predictions or clustering of spatially proximate molecular conformations. Previously, we introduced the RigidRMSD algorithm to compute the RMSD corresponding to the rigid-body motion of a molecule. In this study, we go beyond the limits of the rigid-body approximation by taking into account conformational flexibility of the molecule. We model the flexibility with a reduced set of collective motions computed with e.g. normal modes or principal component analysis. Results: The initialization of our algorithm is linear in the number of atoms and all the subsequent evaluations of RMSD values between flexible molecular conformations depend only on the number of collective motions that are selected to model the flexibility. Therefore, our algorithm is much faster compared to the standard RMSD computation for large-scale modeling applications. We demonstrate the efficiency of our method on several clustering examples, including clustering of flexible docking results and molecular dynamics (MD) trajectories. We also demonstrate how to use the presented formalism to generate pseudo-random constant-RMSD structural molecular ensembles and how to use these in cross-docking. Availability and implementation: We provide the algorithm written in C++ as the open-source RapidRMSD library governed by the BSD-compatible license, which is available at http://team.inria.fr/nano-d/software/RapidRMSD/. The constant-RMSD structural ensemble application and clustering of MD trajectories is available at http://team.inria.fr/nano-d/software/nolb-normal-modes/. Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: Biomedical knowledge grows in complexity, and becomes encoded in network-based repositories, which include focused, expert-drawn diagrams, networks of evidence-based associations and established ontologies. Combining these structured information sources is an important computational challenge, as large graphs are difficult to analyze visually. RESULTS: We investigate knowledge discovery in manually curated and annotated molecular interaction diagrams. To evaluate similarity of content we use: i) Euclidean distance in expert-drawn diagrams, ii) shortest path distance using the underlying network and iii) ontology-based distance. We employ clustering with these metrics used separately and in pairwise combinations. We propose a novel bi-level optimization approach together with an evolutionary algorithm for informative combination of distance metrics. We compare the enrichment of the obtained clusters between the solutions and with expert knowledge. We calculate the number of Gene and Disease Ontology terms discovered by different solutions as a measure of cluster quality. Our results show that combining distance metrics can improve clustering accuracy, based on the comparison with expert-provided clusters. Also, the performance of specific combinations of distance functions depends on the clustering depth (number of clusters). By employing bi-level optimization approach we evaluated relative importance of distance functions and we found that indeed the order by which they are combined affects clustering performance. Next, with the enrichment analysis of clustering results we found that both hierarchical and bi-level clustering schemes discovered more Gene and Disease Ontology terms than expert-provided clusters for the same knowledge repository. Moreover, bi-level clustering found more enriched terms than the best hierarchical clustering solution for three distinct distance metric combinations in three different instances of disease maps. CONCLUSIONS: In this work we examined the impact of different distance functions on clustering of a visual biomedical knowledge repository. We found that combining distance functions may be beneficial for clustering, and improve exploration of such repositories. We proposed bi-level optimization to evaluate the importance of order by which the distance functions are combined. Both combination and order of these functions affected clustering quality and knowledge recognition in the considered benchmarks. We propose that multiple dimensions can be utilized simultaneously for visual knowledge exploration.

In molecular biology, the subject of protein structure prediction is of continued interest, not only to chart the molecular map of living cells, but also to design proteins with new functions. The Inverse Folding Problem (IFP) of finding sequences that fold into a defined structure is in itself an important research problem at the heart of rational protein design. In this work the Preference-Based Genetic Algorithm (PBGA) is employed to find many diversified solutions to the IFP. The PBGA algorithm incorporates a weighted sum model in order to combine fitness and diversity into a single objective function scoring a set of individuals as a whole. By adjusting the sum weights, a direct control of the fitness vs. diversity trade-off in the algorithm population is achieved by means of a selection scheme iteratively removing the least contributing individuals. Experimental results demonstrate the superior performance of the PBGA algorithm compared to other state-of-the-art algorithms both in terms of fitness and diversity.

Multibeam satellite systems offer flexibility that aims at efficiently reusing the available spectrum. To fully exploit the flexibility advantages, the payload resources—transmit power and bandwidth—must be efficiently allocated among multiple beams. This paper investigates the resource optimization problem in multibeam satellites. The NP-hardness and inapproximability of the problem are demonstrated motivating the use of metaheuristics. A systematic approach accomplishing the best traffic match is carried out. The additional requirement of minimizing the total power consumption is then considered, giving rise to a multi-objective optimization approach. The solutions to thea prioriaccomplished traffic matching optimization are used to enhance the efficiency of the multi-objective metaheuristic method proposed and, consequently, of the multibeam satellite system. The optimized performance is represented by the Pareto front, which provides trade-off points between total power consumption and rate achieved. This allows the decomposition of the problem into independent color-based sub-problems rendering the proposed two-stage optimization framework suitable for dimensioning the next generation multispot satellite systems.

A key factor for accurate vehicular ad hoc networks (VANET) simulation is the quality of its underlying mobility model. VehILux is a recent vehicular mobility model that generates traces using traffic volume counts and real-world map data. This model uses probabilistic attraction points which values require optimization to provide realistic traces. Previous sensitivity analysis and application of genetic algorithms (GAs) on the Luxembourg problem instance have outlined this model's limitations. In this article, we first propose an extension of the model using a higher number of auto-generated attraction points. Then its decomposition on the Luxembourg instance using geographical information is proposed as a way to break epistatic links and hence make its optimization using cooperative coevolutionary genetic algorithms (CCGAs) more efficient. Experimental results demonstrate the significant realism increase brought by both the VehILux model enhancements and the CCGA compared to the generational and cellular GAs.

The size and complexity of communication satellite payloads have been increasing very quickly over the last years and their configuration / reconfiguration have become very difficult problems. In this work, we propose to compare the efficiency of three well-known metaheuristic methods to solve an initial configuration problem, which objective is to minimise the length of the longest channel path. Experiments are conducted on real-world problem instances with realistic operational constraints (e.g., a maximum computation time of 10 minutes) and Wilcoxon test is used to determine with statistical confidence what technique is more suitable and what are its limitations. The results of this work will serve as an initial step in our research to design hybrid approaches to push even further the solving capabilities, i.e., tackling bigger payloads and more channels to activate.

This article introduces asynchronous implementations of selected synchronous cooperative co-evolutionary multi-objective evolutionary algorithms (CCMOEAs). The CCMOEAs chosen are based on the following state-of-the-art multi-objective evolutionary algorithms (MOEAs): Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). The cooperative co-evolutionary variants presented in this article differ from the standard MOEAs architecture in that the population is split into islands, each of them optimizing only a sub-vector of the global solution vector, using the original multi-objective algorithm. Each island evaluates complete solutions through cooperation, i.e., using a subset of the other islands current partial solutions. We propose to study the performance of the asynchronous CCMOEAs with respect to their synchronous versions and base MOEAs on well kown test problems, i.e. ZDT and DTLZ. The obtained results are analyzed in terms of both the quality of the Pareto front approximations and computational speedups achieved on a multicore machine.

The first step in the evaluation of vehicular ad hoc networks (VANETs) applications is based on simulations. The quality of those simulations not only depends on the accuracy of the network model but also on the degree of reality of the underlying mobility model. VehILux-a recently proposed vehicular mobility model, allows generating realistic mobility traces using traffic volume count data. It is based on the concept of probabilistic attraction points. However, this model does not address the question of how to select the best values of the probabilities associated with the points. Moreover, these values depend on the problem instance (i.e. geographical region). In this article we demonstrate how genetic algorithms (GAs) can be used to discover these probabilities. Our approach combined together with VehILux and a traffic simulator allows to generate realistic vehicular mobility traces for any region, for which traffic volume counts are available. The process of the discovery of the probabilities is represented as an optimisation problem. Three GAs-generational GA, steady-state GA, and cellular GA-are compared. Computational experiments demonstrate that using basic evolutionary heuristics for optimising VehILux parameters on a given problem instance permits to improve the model realism. However, in some cases, the results significantly deviate from real traffic count data. This is due to the route generation method of the VehILux model, which does not take into account specific behaviour of drivers in rush hours.

Realistic simulations of Vehicular Ad hoc Networks (VANETs) are necessary to evaluate novel technologies based on such networks and to prove benefits obtained from their implementation. This survey gathers from several research domains aspects that increase the quality of VANET simulations. It explains a multi-fold nature of VANETs and presents main building blocks of their simulation-traffic and network simulators. The paper proposes a comprehensive architecture for VANET simulation platform that focuses on producing reliable results. The architecture contains traffic and network simulators that communicate with each other in a dynamic and bi-directional way. The concept of a realistic traffic generator is introduced. It uses real-world data (e.g. maps, traffic volume counts) to model an activity-based traffic varying in time. The traffic generator aims at reproducing accurate vehicular traces for urban scenario. A higher level of realism can be obtained by modelling of human behaviour with intelligent agents and by the implementation of related subsystems, like traffic management and control or weather factors.

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

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

When considering realistic mobility patterns, nodes in mobile ad hoc networks move in such a way that the networks most often get divided in a set of disjoint partitions. This presence of partitions is an obstacle to communication within these networks. Ad hoc networks are generally based on technologies allowing nodes in a geographical neighborhood to communicate for free, in a P2P manner. These technologies include IEEE802.11 (Wi-Fi), Bluetooth, etc. In most cases a communication infrastructure is available. It can be a set of access point as well as GMS/UMTS network. The use of such an infrastructure is billed, but it permits distant nodes to get in communication, through what we call "bypass links". The objective of our work is to improve the network connectivity by defining a set of long distance connections. To do this we consider the number of bypass links, as well as the two properties that build on the "small-world" graph theory: the clustering coefficient, and the characteristic path length. A fitness function, used for genetic optimization, is processed out of these three metrics. In this paper we investigate the use of two coevolutionary genetic algorithms (LCGA and CCGA) and compare their performance to a generational and a steady- state genetic algorithm (genGA and ssGA) for optimizing one instance of this topology control problem and present evidence of their capacity to solve it.

This work aims at optimizing injection networks, which consist in adding a set of long-range links (called bypass links) in mobile multi-hop ad hoc networks so as to improve connectivity and overcome network partitioning. To this end, we rely on small-world network properties, that comprise a high clustering coefficient and a low characteristic path length. We investigate the use of two genetic algorithms (generational and steady-state) to optimize three instances of this topology control problem and present results that show initial evidence of their capacity to solve it.