This paper presents a minimal validated framework for designing energy-aware metaheuristics that operate under fixed energy budgets. We introduce a unified operator-level model that quantifies both numerical gain and energy consumption, and define a robust Expected Improvement per Joule (EI/J) score to guide adaptive selection among operator variants during the search. The resulting energy-aware solvers dynamically choose between operators to self-control exploration and exploitation, aiming to maximise fitness gain under limited energy. We instantiate this framework in three representative metaheuristics—steady-state GA, PSO, and ILS—each equipped with two lightweight/heavy update variants in a controlled setting. Experiments on three heterogeneous combinatorial problems (Knapsack, NK-landscapes, and Error-Correcting Codes) show that the energy-aware variants can reach comparable fitness while requiring substantially less energy than their non-energy-aware baselines. EI/J values stabilise early and yield clear operator-selection patterns, with each solver reliably self-identifying the most improvement-per-Joule-efficient operator across problems.

Addressing real-world optimization challenges requires not only advanced metaheuristics but also continuous refinement of their internal mechanisms. This paper explores the integration of machine learning in the form of neural surrogate models into metaheuristics through a recent lens: energy consumption. While surrogates are widely used to reduce the computational cost of expensive objective functions, their combined impact on energy efficiency, algorithmic performance, and solution accuracy remains largely unquantified. We provide a critical investigation into this intersection, aiming to advance the design of energy-aware, surrogate-assisted search algorithms. Our experiments reveal substantial benefits: employing a pre-trained surrogate can reduce energy consumption by up to 98%, execution time by approximately 98%, and memory usage by around 99% in our setting. Moreover, increasing the training dataset size may further enhance these gains up to a point by lowering the per-use computational cost, while static pre-training versus continuous (iterative) retraining exhibit different advantages depending on whether we aim at time/energy or accuracy and overall computational cost across instances, respectively. Surrogates may negatively impact cost and accuracy in some cases, and then they cannot be blindly adopted. These findings support a more holistic approach to surrogate-assisted optimization, integrating energy with time and predictive accuracy into performance assessments.

Solving complex real problems often demands advanced algorithms, and then continuous improvements in the internal operations of a search technique are needed. Hybrid algorithms, parallel techniques, theoretical advances, and much more are needed to transform a general search algorithm into an efficient, useful one in practice. In this paper, we study how surrogates are helping metaheuristics from an important and understudied point of view: their energy profile. Even if surrogates are a great idea for substituting a time-demanding complex fitness function, the energy profile, general efficiency, and accuracy of the resulting surrogate-assisted metaheuristic still need considerable research. In this work, we make a first step in analyzing particle swarm optimization in different versions (including pre-trained and retrained neural networks as surrogates) for its energy profile (for both processor and memory), plus a further study on the surrogate accuracy to properly drive the search towards an acceptable solution. Our conclusions shed new light on this topic and could be understood as the first step towards a methodology for assessing surrogate-assisted algorithms not only accounting for time or numerical efficiency but also for energy and surrogate accuracy for a better, more holistic characterization of optimization and learning techniques.

Federated learning is a paradigm that proposes protecting data privacy by sharing local models instead of raw data during each iteration of model training. However, these models can be large, with many parameters, provoking a substantial communication cost and having a notable environmental impact. Reducing communication overhead is paramount but conflictual to maintaining the model’s accuracy. Most research has dealt with the different factors influencing communication reduction separately without addressing their correlations. Moreover, most of them do not consider the heterogeneity of clients’ hardware. Finding the optimal configuration to fulfil all these training aspects can become intractable for classical techniques. This work explores the add-in that multi-objective evolutionary algorithms can provide for solving the communication overhead problem while achieving high accuracy. We do this by 1) realistically modelling and formulating this task as a multi-objective problem by considering the devices’ heterogeneity, 2) including all the communication-triggering aspects, and 3) applying a multi-objective evolutionary algorithm with an intensification operator to solve the problem. A simulated client–server architecture of four devices with four different processing speeds is studied. Both fully connected and convolutional neural network models are investigated with 33,400 and 887,530 weights, respectively. The experiments are performed using the MNIST and Fashion-MNIST datasets. A comparison is made between three approaches using an extensive set of metrics. Results prove that our approach obtains solutions with better accuracy than the full-communication setting and other methods while getting reductions in communications by around 1,000 times in most cases and up to 10,000 times in some cases compared to the maximum communication setting.

In the traffic light scheduling problem, the evaluation of candidate solutions requires the simulation of a process under various (traffic) scenarios. Thus, good solutions should not only achieve good objective function values, but they must be robust (low variance) across all different scenarios. Previous work has shown that combining IRACE with evolutionary operators is effective for this task due to the power of evolutionary operators in numerical optimization. In this article, we further explore the hybridization of evolutionary operators and the elitist iterated racing of IRACE for the simulation-optimization of traffic light programs. We review previous works from the literature to find the evolutionary operators performing the best when facing this problem to propose new hybrid algorithms. We evaluate our approach over a realistic case study derived from the traffic network of Málaga (Spain) with 275 traffic lights that should be scheduled optimally. The experimental analysis reveals that the hybrid algorithm comprising IRACE plus differential evolution offers statistically better results than the other algorithms when the budget of simulations is low. In contrast, IRACE performs better than the hybrids for a high simulations budget, although the optimization time is much longer.

Discrete-variable gate-model quantum machines are promising quantum systems considering their wide applicability. Being in their noisy-intermediate-scale era, they allow executing only circuits of limited complexity and fitting the machines' features. Thus, such systems implement a key and unavoidable tailoring process to produce the most possible compact and device-compliant circuit. The qubits' initialisation is a primary and complex step that can ease/jeopardise the tailoring process and restrict/extend the machine's computational capacities. Ultimately, this bottleneck can be responsible of making quantum leaps like quantum supremacy. As a step towards the former, this work investigates how evolutionary algorithms can enhance the qubits' initialisation by tackling it as a single-objective problem using a genetic algorithm. The experiments used instances representing 19 real IBM quantum machines with 7 to 65 qubits and 9 different qubit topologies. Also, 76 GHZ circuits of sizes 7-65 qubits and 25%-100% of entanglement were created and studied. Extensive standard and statistical comparisons have been made against the IBM qubit initialiser that is currently used in real quantum machines. Results showed that the proposal outperforms IBM in 64 instances and is similar to it in 10 ones, with an average circuit-compression gain up to 46%.

Quantum-inspired metaheuristics are solvers that incorporate principles inspired from quantum mechanics into classical-approximate algorithms using non-quantum machines. Due to the uniqueness of quantum principles, the inspiration of quantum phenomena and the way it is done in fundamentally different non-quantum systems rather than real or simulated quantum computers raise important questions about these algorithms’ design and the reproducibility of their results in real or simulated quantum devices. Thus, this work’s contribution stands in a first step towards answering those questions as an attempt to identify key findings in the existing literature that should be considered or adapted in order to build hybrid or fully-quantum algorithms that can be used in quantum machines. This is done by proposing and studying four inspired, simulated and real quantum cellular genetic algorithms that, as far as the authors’ knowledge, are the first quantum structured metaheuristics studied in the three quantum realms using a quantum simulator with 32 quantum bits and a real quantum machine employing 15 superconducting quantum bits. The users’ mobility management in cellular networks is taken as a validation problem using 13 real-world instances. The comparisons have been made against 6 diverse algorithms using 9 comparison metrics. Thorough statistical tests and parameters’ sensitivity analysis have been also conducted. The experiments allowed answering several questions, including how quantum hardware influences the studied-algorithms’ search process. They also enabled opening new perspectives in quantum metaheuristics’ design.

The number of devices, from smartphones to IoT hardware, interconnected via the Internet is growing all the time. These devices produce a large amount of data that cannot be analyzed in any data center or stored in the cloud, and it might be private or sensitive, thus precluding existing classic approaches. However, studying these data and gaining insights from them is still of great relevance to science and society. Recently, two related paradigms try to address the above problems. On the one hand, edge computing (EC) suggests to increase processing on edge devices. On the other hand, federated learning (FL) deals with training a shared machine learning (ML) model in a distributed (non-centralized) manner while keeping private data locally on edge devices. The combination of both is known as federated edge learning (FEEL). In this work, we propose an algorithm for FEEL that adapts to asynchronous clients joining and leaving the computation. Our research focuses on adapting the learning when the number of volunteers is low and may even drop to zero. We propose, implement, and evaluate a new software platform for this purpose. We then evaluate its results on problems relevant to FEEL. The proposed decentralized and adaptive system architecture for asynchronous learning allows volunteer users to yield their device resources and local data to train a shared ML model. The platform dynamically self-adapts to variations in the number of collaborating heterogeneous devices due to unexpected disconnections (i.e., volunteers can join and leave at any time). Thus, we conduct comprehensive empirical analysis in a static configuration and highly dynamic and changing scenarios. The public open-source platform enables interoperability between volunteers connected using web browsers and Python processes. (...)

This work aims at giving an updated vision on the successful combination between Metaheuristics and Software Engineering (SE). Mostly during the 90s, varied groups of researchers dealing with search, optimization, and learning (SOL) met SE researchers, all of them looking for a quantified manner of modeling and solving problems in the software field. This paper will discuss on the construction, assessment, and exploitation tasks that help in making software programs a scientific object, subject to automatic study and control. We also want to show with several case studies how the quantification of software features and the automatic search for bugs can improve the software quality process, which eases compliance to ISO/IEEE standards. In short, we want to build intelligent automatic tools that will upgrade the quality of software products and services. Since we approach this new field as a cross-fertilization between two research domains, we then need to talk not only on metaheuristics for SE (well known by now), but also on SE for metaheuristics (not so well known nowadays). In summary, we will discuss here with three time horizons in mind: the old times [before the term search-based SE (SBSE) was used for this], the recent years on SBSE, and the many avenues for future research/development. A new body of knowledge in SOL and SE exists internationally, which is resulting in a new class of researchers able of building intelligent techniques for the benefit of software, that is, of modern societies.

In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions can be computed in a short time and the search algorithm has to be stopped prematurely to analyze the solutions found so far. A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. However, just a few exact algorithms in the literature exist with the ability to provide such a well-spread set of solutions at any moment: we call them anytime algorithms. We propose a new exact anytime algorithm for multiobjective combinatorial optimization combining three novel ideas to enhance the anytime behavior. We compare the proposed algorithm with those in the state-of-the-art for anytime multiobjective combinatorial optimization using a set of 480 instances from different well-known benchmarks and four different performance measures: the overall non-dominated vector generation ratio, the hypervolume, the general spread and the additive epsilon indicator. A comprehensive experimental study reveals that our proposal outperforms the previous algorithms in most of the instances.

The goal in Robust Optimization is to optimize not only the quality of the solutions but also the variation of this quality with the uncertain parameters of the optimization problem . We propose a robust model for the bi-objective shortest path problem applied in a smart mobility context: Finding routes for cars in a city to minimize travel time and gas emissions. Our proposal treats robustness from a multi-objective point of view. We model the parameters that define each instance as random variables , described through their mean and variance. In this way, we can obtain efficient solutions that are also less sensitive to changes in the environment. We run different types of algorithms in multiple instances to solve this problem so that we obtain a global view of the behavior of different techniques. All experimentation uses a scenario based on real data : The province of Malaga, Spain. This realistic settlement for our study allows us to test the applicability of our model in final systems for the citizens. The results clearly state the interest of our proposal for tackling robustness and represents a new state-of-the-art in smart mobility, an always appealing feature of works, that could lead to an industrial prototype.

Having a mechanism to mathematically model the problem of the optimal allocation of parking spots within cities could bring great benefits to society. According to the International Parking Institute, about 38% of the cars circulating throughout a city are looking for available parking spots, leading to increased pollution and subsequent health problems, as well as economic losses due to wasted man-hours. In the work presented here, a new mathematical model describing the problem of the optimal allocation of parking spots is proposed, along with an evolutionary algorithm to demonstrate how this model can be used in practice. A simulated annealing algorithm was implemented to test the effectiveness of this approach. The proposed strategy will allow users to find parking more quickly and easily, as well as lead to new services for the hot-topic of smart mobility. For the definition of the problem, a real map of the city of Malaga, Spain, was used along with Sumo software to carry out the simulations. The results clearly demonstrated that the proposed mechanism is capable of minimising the global cost of parking, implying a direct benefit for users.

This paper is a brief description of the revamped presentation based in the original one I had the honor to deliver back in 2009 during the very first SSBSE in London. At this time, the many international forces dealing with search, optimization, and learning (SOL) met software engineering (SE) researchers in person, all of them looking for a quantified manner of modeling and solving problems in software. The contents of this work, as in the original one, will develop on the bases of metaheuristics to highlight the many good ways in which they can help to create a well-grounded domain where the construction, assessment, and exploitation of software are not just based in human expertise, but enhanced with intelligent automatic tools. Since the whole story started well before the first SSBSE in 2009, we will mention a few previous applications in software engineering faced with intelligent algorithms, as well as will discuss on the present interest and future challenges of the domain, structured in both short and long term goals. If we understand this as a cross-fertilization task between research fields, then we could learn a wider and more useful lesson for innovative research. In short, we will have here a semantic perspective of the old times (before SBSE), the recent years on SBSE, and the many avenues for future research and development spinning around this exciting clash of stars. A new galaxy has been born out of the body of knowledge in SOL and SE, creating forever a new class of researchers able of building unparalleled tools and delivering scientific results for the benefit of software, that is, of modern societies.

Genetic Algorithms (GAs) are being used to solve a wide range of problems in real world problems, and it is important to study their implementations to improve the solution quality and reduce the execution time. Designing parallel (e.g., distributed) GAs is one research line to do so. In distributed GAs, every individual represents a tentative solution. Individuals are split (and sparsely communicated) over many islands, with genetic operators being applied locally in each island. In addition, in order to maintain diversity and reduce the number of the evaluations, a migration operator is used to enhance their behavior. This article presents a basic study on the speed-up of parallel GAs where a common approach is followed to better understand synchronous and asynchronous versions together. We analyze the behavior of GAs over a homogeneous multiprocessor system. We will report results showing linear and even superlinear speed-up in both cases of study. The parallel performance of the synchronous and asynchronous versions is very good in a multiprocessor computer, both in terms of time and solution quality. Besides, a statistical analysis of the algorithms clearly proves that both cases have a similar numerical behavior over a homogeneous parallel system.

Finding the shortest path between two places is a well known problem in road traveling. While most of the work done up to this moment is focused on algorithmics, efficiently managing the information has received significantly less attention. Nevertheless, real world problems like road map routing present a challenge due to the impact that the immense size of the map has over the temporal complexity of the routing algorithms. In this work we propose a strategy for efficiently computing the shortest path in real road maps based on data managing: the tile map partitioning. To recreate a real scenario, we implemented a routing system and we tested our strategy using the road map of the Province of Málaga, Spain. Using a Differential Evolution we found the optimal tile size and prove that significant time reductions can be achieved by using the tile map partitioning.

GPS navigators are now present in most vehicles and smartphones. The usual goal of these navigators is to take the user in less time or distance to a destination. However, the global use of navigators in a given city could lead to traffic jams as they have a highly biased preference for some streets. From a general point of view, spreading the traffic throughout the city could be a way of preventing jams and making a better use of public resources. We propose a way of calculating alternative routes to be assigned by these devices in order to foster a better use of the streets. Our experimentation involves maps from OpenStreetMap, real road traffic, and the microsimulator SUMO. We contribute to reducing travel times, greenhouse gas emissions, and fuel consumption. To analyze the sociological aspect of any innovation, we analyze the penetration (acceptance) rate which shows that our proposal is competitive even when just 10% of the drivers are using it.

This article describes the application of a multiobjective evolutionary algorithm for locating roadside infrastructure for vehicular communication networks over realistic urban areas. A multiobjective formulation of the problem is introduced, considering quality-of-service and cost objectives. The experimental analysis is performed over a real map of Málaga, using real traffic information and antennas, and scenarios that model different combinations of traffic patterns and applications (text/audio/video) in the communications. The proposed multiobjective evolutionary algorithm computes accurate trade-off solutions, significantly improving over state-of-the-art algorithms previously applied to the problem.

Optimisation in changing environments is a challenging research topic since many real-world problems are inherently dynamic. Inspired by the natural evolution process, evolutionary algorithms (EAs) are among the most successful and promising approaches that have addressed dynamic optimisation problems. However, managing the exploration/exploitation trade-off in EAs is still a prevalent issue, and this is due to the difficulties associated with the control and measurement of such a behaviour. The proposal of this paper is to achieve a balance between exploration and exploitation in an explicit manner. The idea is to use two equally sized populations: the first one performs exploration while the second one is responsible for exploitation. These tasks are alternated from one generation to the next one in a regular pattern, so as to obtain a balanced search engine. Besides, we reinforce the ability of our algorithm to quickly adapt after cnhanges by means of a memory of past solutions. Such a combination aims to restrain the premature convergence, to broaden the search area, and to speed up the optimisation. We show through computational experiments, and based on a series of dynamic problems and many performance measures, that our approach improves the performance of EAs and outperforms competing algorithms.

Metaheuristics have yielded very promising results for the frequency assignment problem (FAP). However, the results obtainable using currently published methods are far from ideal in complex, large-scale instances. This paper applies and extends some of the most recent advances in evolutionary algorithms to two common variants of the FAP, and shows how, in traditional techniques, two common issues affect their performance: 1) premature convergence and 2) the way in which neutral networks are handled. A recent replacement-based diversity management strategy is successfully applied to alleviate the premature convergence drawback. Additionally, by properly defining a distance metric, the performance in the presence of neutrality can also be greatly improved. The replacement strategy combines the principle of transforming a single-objective problem into a multiobjective one by considering diversity as an additional objective, with the idea of adapting the balance induced between exploration and exploitation to the requirements of the different optimization stages. Tests with 44 publicly available instances yield very competitive results. New best-known frequency plans were generated for 11 instances, whereas in the remaining ones the best-known solutions were replicated. Comparisons with a large number of strategies designed to delay convergence of the population clearly show the advantages of our novel proposals.

Multi-Objective Evolutionary Algorithms (MOEAs) are powerful tools for solving a wide range of real-world applications that involve the simultaneous optimization of several objective functions. However, their scalability to many-objective problems remains as an important issue since, due to the large number of non-dominated solutions, the search is guided solely by the diversity criterion. In this paper, we propose a novel MOEA that incorporates a density estimator based on a visualization technique called Parallel Coordinates. Using this approach, a graph is represented by a digital image, where a pixel identifies the level of overlapping line segments and those individuals covering a wide area of the image have a high probability of survival. Experimental results indicate that our proposed approach, called Multi-objective Optimizer based on Value Path (MOVAP), outperforms existing algorithms based on clustering (SPEA2), crowding distance (NSGA-II), reference points (NSGA-III) and the hypervolume indicator (HypE) on most of the problems of the WFG test suite for five and seven objectives, while its performance in low dimensionality remains competitive.

In this article we work towards the desired future smart city in which IT and knowledge will hopefully provide a highly livable environment for citizens. To this end, we test a new concept based on intelligent LED panels (the Yellow Swarm) to guide drivers when moving through urban streets so as to finally get rid of traffic jams and protect the environment. This is a minimally invasive, low cost idea for the city that needs advanced simulations with real data coupled with new algorithms which perform well. Our proposal is to use evolutionary computation in the Yellow Swarm, which will finally help alleviate the traffic congestion, improve travel times, and decrease gas emissions, all at the same time and for a real case like the city of Quito (Ecuador).

In this paper, we present a recommendation system aimed at helping users and developers alike. We help users to choose optimal sets of applications belonging to different categories (eg. browsers, e-mails, cameras) while minimizing energy consumption, transmitted data, and maximizing application rating. We also help developers by showing the relative placement of their application's efficiency with respect to selected others. When the optimal set of applications is computed, it is leveraged to position a given application with respect to the optimal, median and worst application in its category (eg. browsers). Out of eight categories we selected 144 applications, manually defined typical execution scenarios, collected the relevant data, and computed the Pareto optimal front solving a multi-objective optimization problem. We report evidence that, on the one hand, ratings do not correlate with energy efficiency and data frugality. On the other hand, we show that it is possible to help developers understanding how far is a new Android application power consumption and network usage with respect to optimal applications in the same category. From the user perspective, we show that choosing optimal sets of applications, power consumption and network usage can be reduced by 16.61% and 40.17%, respectively, in comparison to choosing the set of applications that maximizes only the rating.

In this article we propose the Yellow Swarm architecture for reducing travel times, greenhouse gas emissions and fuel consumption of road traffic by using several LED panels to suggest changes in the direction of vehicles (detours) for different time slots. These time intervals are calculated using an evolutionary algorithm, specifically designed for our proposal, which evaluates many working scenarios based on real cities, imported from OpenStreetMap into the SUMO traffic simulator. Our results show an improvement in average travel times, emissions, and fuel consumption even when only a small percentage of drivers follow the indications provided by our panels.

It is often frustrating for drivers to find parking spaces, and parking itself is costly in almost every major city in the world. The search for a parking place is a task which can waste a lot of time and affect the efficiency of economic activities, social interactions, and the health of the environment. The planners of transport and city traffic must pay close attention to this issue in order to achieve an efficient management of mobility in smart cities. This work is intended to serve as an aid in the search for parking seeking the general interest of a group of drivers. We present an intensive description of the parking slots assignment problem for groups and apply it to a real case study. Also, we propose a hybrid genetic algorithm for solving this case and we compare it with three other algorithms in order to evaluate its performance.

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

This article presents an empirical study devoted to characterize the computational efficiency behavior of an evolutionary algorithm (usually called canonical) as a C program. The study analyzes the effects of several implementation decisions on the execution time of the resulting evolutionary algorithm. The implementation decisions studied include: memory utilization (using dynamic vs. static variables and local vs. global variables), methods for ordering the population, code substitution mechanisms, and the routines for generating pseudorandom numbers within the evolutionary algorithm. The results obtained in the experimental analysis allow us to conclude that significant improvements in efficiency can be gained by applying simple guidelines to best program an evolutionary algorithm in C. Copyright © 2013 John Wiley & Sons, Ltd.

Software Product Lines (SPLs) are families of related software products, each with its own set of feature combinations. Their commonly large number of products poses a unique set of challenges for software testing as it might not be technologically or economically feasible to test of all them individually. SPL pairwise testing aims at selecting a set of products to test such that all possible combinations of two features are covered by at least one selected product. Most approaches for SPL pairwise testing have focused on achieving full coverage of all pairwise feature combinations with the minimum number of products to test. Though useful in many contexts, this single-objective perspective does not reflect the prevailing scenario where software engineers do face trade-offs between the objectives of maximizing the coverage or minimizing the number of products to test. In contrast and to address this need, our work is the first to propose a classical multi-objective formalisation where both objectives are equally important. In this paper, we study the application to SPL pairwise testing of four classical multi-objective evolutionary algorithms. We developed three seeding strategies — techniques that leverage problem domain knowledge — and measured their performance impact on a large and diverse corpus of case studies using two well-known multi-objective quality measures. Our study identifies the performance differences among the algorithms and corroborates that the more domain knowledge leveraged the better the search results. Our findings enable software engineers to select not just one solution (as in the case of single-objective techniques) but instead to select from an array of test suite possibilities the one that best matches the economical and technological constraints of their testing context.

Software Product Lines (SPLs) are families of related software systems, which provide different feature combinations. Different SPL testing approaches have been proposed. However, despite the extensive and successful use of evolutionary computation techniques for software testing, their application to SPL testing remains largely unexplored. In this paper we present the Parallel Prioritized product line Genetic Solver (PPGS), a parallel genetic algorithm for the generation of prioritized pairwise testing suites for SPLs. We perform an extensive and comprehensive analysis of PPGS with 235 feature models from a wide range of number of features and products, using 3 different priority assignment schemes and 5 product prioritization selection strategies. We also compare PPGS with the greedy algorithm prioritized-ICPL. Our study reveals that overall PPGS obtains smaller covering arrays with an acceptable performance difference with prioritized-ICPL.

This paper proposes a novel algorithm combining path relinking with a set of cooperating trajectory based parallel algorithms to yield a new metaheuristic of enhanced search features. Algorithms based on the exploration of the neighborhood of a single solution, like simulated annealing (SA), have offered accurate results for a large number of real-world problems in the past. Because of their trajectory based nature, some advanced models such as the cooperative one are competitive in academic problems, but still show many limitations in addressing large scale instances. In addition, the field of parallel models for trajectory methods has not deeply been studied yet (at least in comparison with parallel population based models). In this work, we propose a new hybrid algorithm which improves cooperative single solution techniques by using path relinking, allowing both to reduce the global execution time and to improve the efficacy of the method. We test here this new model using a large benchmark of instances of two well-known NP-hard problems: MAXSAT and QAP, with competitive results.

This article proposes an innovative solution for reducing polluting gas emissions from road traffic in modern cities. It is based on our new Red Swarm architecture which is composed of a series of intelligent spots with WiFi connections that can suggest a customized route to drivers. We have tested our proposal in four different case studies corresponding to actual European smart cities. To this end, we first import the city information from OpenStreetMap into the SUMO road traffic micro-simulator, propose a Red Swarm architecture based on intelligent spots located at traffic lights, and then optimize the resulting system in terms of travel times and gas emissions by using an evolutionary algorithm. Our results show that an important quantitative reduction in gas emissions as well as in travel times can be achieved when vehicles are rerouted according to our Red Swarm indications. This represents a promising result for the low cost implementation of an idea that could engage the interest of both citizens and municipal authorities.

In last years, enhancing the vehicular traffic flow becomes a mandatory task to minimize the impact of polluting emissions and unsustainable fuel consumption in our cities. Smart Mobility optimisation emerges then, with the goal of improving the traffic management in the city. With this aim, we propose in this paper an optimisation strategy based on swarm intelligence to find efficient cycle programs for traffic lights deployed in large urban areas. In concrete, in this work we focus on the improvement of the traffic flow with the global purpose of reducing contaminant emissions (CO 2 and NO x ) and fuel consumption in the analyzed areas. For the sake of standardization, we follow European Union reference framework for traffic emissions, called HandBook Emission FActors (HBEFA). As a case study, we have concentrated in two extensive urban areas in the cities of Malaga and Seville (in Spain). After several comparisons between different optimisation techniques (Differential Evolution and Random Search), as well as other solutions provided by experts, our proposal is shown to obtain significant reductions of fuel consumption and gas emissions.

Reduced population algorithms have proven to be efficient for solving optimization problems in the past. In this paper, we incorporate a local search procedure into a micro differential evolution algorithm (DE) with the aim of tackling high dimensional problems. Our main purpose is to find out if our proposal is more competitive in these problems than a canonical differential evolution algorithm. In relation to the state of the art techniques, the results our micro-DELS are comparable (or better) with the reference algorithms DECC-G and MLCC. This empirical analysis supports our conjecture that a reduced population DE hybridized with local search (our microDELS) is a key combination in dealing with functions having high dimensionality at a low computational cost.

In this paper we design a new distributed genetic algorithm, which is able to self-adapt the value of one of the most important parameter in this kind of techniques using the information provided by theoretical models. We study different alternative ways to use the mathematical results in our genetic algorithm. We test our technique on a wide set of instances of the well-known MAX-SAT problem. Experiments show that our self-* proposal is able to obtain similar, or even better, results when it is compared to traditional algorithms whose setting is made by hand. We also show the benefits in terms of saving time and complexity of migration policy settings for distributed genetic algorithms without reducing their efficiency.

This work presents an original approach to regulate traffic by using an on-line system controlled by an EA. Our proposal uses computational spots with WiFi connectivity located at traffic lights (the Red Swarm), which are used to suggest alternative individual routes to vehicles. An evolutionary algorithm is also proposed in order to find a configuration for the Red Swarm spots which reduces the travel time of the vehicles and also prevents traffic jams. We solve real scenarios in the city of Malaga (Spain), thus enriching the OpenStreetMap info by adding traffic lights, sensors, routes and vehicle flows. The result is then imported into the SUMO traffic simulator to be used as a method for calculating the fitness of solutions. Our results are competitive compared to the common solutions from experts in terms of travel and stop time, and also with respect to other similar proposals but with the added value of solving a real, big instance.

Lopez-Herrejon, R. E., Chicano F., Ferrer J., Egyed A., & Alba E. (2013). Multi-objective Optimal Test Suite Computation for Software Product Line Pairwise Testing. 2013 IEEE International Conference on Software Maintenance, Eindhoven, The Netherlands, September 22-28, 2013. 404–407.

Optimal staging of traffic lights, and in particular optimal light cycle programs, is a crucial task in present day cities with potential benefits in terms of energy consumption, traffic flow management, pedestrian safety, and environmental issues. Nevertheless, very few publications in the current literature tackle this problem by means of automatic intelligent systems, and, when they do, they focus on limited areas with elementary traffic light schedules. In this paper, we propose an optimization approach in which a particle swarm optimizer (PSO) is able to find successful traffic light cycle programs. The solutions obtained are simulated with simulator of urban mobility, a well-known microscopic traffic simulator. For this study, we have tested two large and heterogeneous metropolitan areas with hundreds of traffic lights located in the cities of Bahía Blanca in Argentina (American style) and Málaga in Spain (European style). Our algorithm is shown to obtain efficient traffic light cycle programs for both kinds of cities. In comparison with expertly predefined cycle programs (close to real ones), our PSO achieved quantitative improvements for the two main objectives: 1) the number of vehicles that reach their destination and 2) the overall journey time.

Uniform crossover is a popular operator used in genetic algorithms to combine two tentative solutions of a problem represented as binary strings. We use the Walsh decomposition of pseudo-Boolean functions and properties of Krawtchouk matrices to exactly compute the expected value for the fitness of a child generated by uniform crossover from two parent solutions. We prove that this expectation is a polynomial in Á, the probability of selecting the best-parent bit. We provide efficient algorithms to compute this polynomial for ONEMAX and MAX-kSAT problems, but the results also hold for domains such as NK-Landscapes.

Combinatorial Interaction Testing (CIT) is a technique used to discover faults caused by parameter interactions in highly configurable systems. These systems tend to be large and exhaustive testing is generally impractical. Indeed, when the resources are limited, prioritization of test cases is a must. Important test cases are assigned a high priority and should be executed earlier. On the one hand, the prioritization of test cases may reveal faults in early stages of the testing phase. But, on the other hand the generation of minimal test suites that fulfill the demanded coverage criteria is an NP-hard problem. Therefore, search based approaches are required to find the (near) optimal test suites. In this work we present a novel evolutionary algorithm to deal with this problem. The experimental analysis compares five techniques on a set of benchmarks. It reveals that the evolutionary approach is clearly the best in our comparison. The presented algorithm can be integrated into a professional tool for CIT.

In a previous work, it was empirically shown that certain numbers of informants different from the standard "two" and the expensive "all" may provide the Particle Swarm Optimization (PSO) with new essential information about the search landscape, leading this algorithm to perform more accurately than other existing versions of it. Here, we extend this study by analyzing the internal behavior of PSO from the point of view of the evolvability. Our motivation is to find evidences of why such number of 6+/-2 informant particles, perform better than other neighborhood formulations of PSO. For this task, we have evaluated different combinations of informants for an extensive set of problem functions. Using fitness-distance correlation and fitness-fitness cloud analyses we have tested the accuracy of the resulting landscape characterizations. The results suggest that, in spite of certain deviation to the global optimum, a number of 6 informants in PSO can generate new improved particles for a longer time, even in complex problems with multi-funnel landscapes.

The problem of measuring performance in dynamic optimization is still an open issue. The most popular procedure consists of choosing one measure from the standard evolutionary optimization domain, such as the best fitness in the current population, and averaging it across the number of generations (sometimes, the number of periods). Generally, it is assumed that the measure of our election has been sufficiently exposed to the changing landscape, although there is no way of actually checking whether this exposition has taken place or not. Our purpose is proposing here for the first time a way of determining how long we should run our experiments in order to get meaningful conclusions in a changing environment after a representative number of changes. The new stopping condition is based on the convergence of the chosen measure for the dynamic problem at hand, thus globally useful.

Vehicular ad hoc networks (VANETs) are infrastructure-less and self-organized networks deployed among vehicles and other road users. Due to the limitations of the wireless technologies used and the rapid topology changes, designing efficient routing protocols for VANETs is becoming a major concern. In this study, we applied a multi-objective optimization metaheuristic, in order to find efficient OLSR parameterizations that improve the QoS of the OLSR RFC and a previous optimized configurations. Our optimized configuration significantly reduces OLSR scalability problems keeping competitive packet delivery rates. The OLSR routing overhead is reduced between 47% and 76% and the delivery times are between 32% and 38% shorter when using our optimized settings.

Scheduling is a capital problem when using distributed heterogeneous computing (HC) and grid environments to solve complex problems. The scheduling problem in heterogeneous environments is NP‐hard, so a significant effort has been made to develop efficient methods for solving the problem. However, few works have faced realistic grid‐sized problem instances. This work presents a parallel CHC (pCHC) evolutionary algorithm codified over MALLBA, a general‐purpose library for combinatorial optimization, for solving the scheduling problem in HC and grid environments. Efficient numerical results are reported in the experimental analysis performed on both a standard benchmark and a set of large‐sized problem instances specially designed in this work. The comparative study shows that pCHC is able to achieve high problem solving efficacy, significantly improving over traditional deterministic scheduling methods, while also showing a good scalability behavior when solving large problem instances.

SUMMARY Automatic test data generation is a very popular domain in the field of search‐based software engineering. Traditionally, the main goal has been to maximize coverage. However, other objectives can be defined, such as the oracle cost, which is the cost of executing the entire test suite and the cost of checking the system behavior. Indeed, in very large software systems, the cost spent to test the system can be an issue, and then it makes sense by considering two conflicting objectives: maximizing the coverage and minimizing the oracle cost. This is what we did in this paper. We mainly compared two approaches to deal with the multi‐objective test data generation problem: a direct multi‐objective approach and a combination of a mono‐objective algorithm together with multi‐objective test case selection optimization. Concretely, in this work, we used four state‐of‐the‐art multi‐objective algorithms and two mono‐objective evolutionary algorithms followed by a multi‐objective test case selection based on Pareto efficiency. The experimental analysis compares these techniques on two different benchmarks. The first one is composed of 800 Java programs created through a program generator. The second benchmark is composed of 13 real programs extracted from the literature. In the direct multi‐objective approach, the results indicate that the oracle cost can be properly optimized; however, the full branch coverage of the system poses a great challenge. Regarding the mono‐objective algorithms, although they need a second phase of test case selection for reducing the oracle cost, they are very effective in maximizing the branch coverage. Copyright © 2011 John Wiley & Sons, Ltd.

Bit-flip mutation is a common operation when a genetic algorithm is applied to solve a problem with binary representation. We use in this paper some results of landscapes theory and Krawtchouk polynomials to exactly compute the expected value of the fitness of a mutated solution. We prove that this expectation is a polynomial in p, the probability of flipping a single bit. We analyze these polynomials and propose some applications of the obtained theoretical results.

The Software Project Scheduling (SPS) problem relates to the decision of who does what during a software project lifetime. This problem has a capital importance for software companies. In the SPS problem, the total budget and human resources involved in software development must be optimally managed in order to end up with a successful project. Companies are mainly concerned with reducing both the duration and the cost of the projects, and these two goals are in conflict with each other. A multi-objective approach is therefore the natural way of facing the SPS problem. In this paper, a number of multi-objective metaheuristics have been used to address this problem. They have been thoroughly compared over a set of 36 publicly available instances that cover a wide range of different scenarios. The resulting project schedulings of the algorithms have been analyzed in order to show their relevant features. The algorithms used in this paper and the analysis performed may assist project managers in the difficult task of deciding who does what in a software project.

In the standard particle swarm optimization (PSO), a new \nparticle’s position is generated using two main informant elements: \nthe best position the particle has found so far and the \nbest performer among its neighbors. In fully informed PSO, \neach particle is influenced by all the remaining ones in the \nswarm, or by a series of neighbors structured in static \ntopologies (ring, square, or clusters). In this paper, we generalize \nand analyze the number of informants that take part in \nthe calculation of new particles. Our aim is to discover if a \nquasi-optimal number of informants exists for a given \nproblem. The experimental results seem to suggest that 6 to 8 \ninformants could provide our PSO with higher chances of \nsuccess in continuous optimization for well-known benchmarks.

In current modern cities, the increasing number of traffic lights that control the vehicular traffic flow requires a highly complex scheduling. Thousands of red lights, that have to be optimally programmed, are nowadays operating in congested urban areas. Therefore, automatic intelligent systems are indispensable tools for optimally tackling this task. In this work, we propose a Swarm Intelligence approach that, coupled with the SUMO traffic simulator, is able to find successful cycle programs of traffic lights for large urban areas. In concrete, we have focused on a metropolitan area of the city downtown of Córdoba (in Spain). The experiments and comparisons with other techniques reveal that our proposed approach obtains significant profits in terms of traffic flow and global trip time.

High computational requirements of current problems have driven most researches towards efficient processing formulations which require the use of multiple processors interconnected, this is the foundation of the parallel processing mechanism. Among the metrics to measure the performance of parallel algorithms, the most important and used is the speedup, but in the scientific community does not exist a consent on its definition and use. The aim of this work is to study different alternatives evaluating parallel metaheuristics. This report presents the results of several experimental tests to show the use of the speedup evaluating the same parallel distributed Genetic Algorithm in different ways, to solve MAXSAT problem. Our experiments show that depending on how the algorithm speedup is evaluated, different results can be obtained. Taking into account the test results we can conclude that the best scenario for evaluating parallel algorithms is comparing algorithms with the same accuracy, defining the quality of the solutions as stop condition, because all executions reach the optimal value allowing fair comparisons.

This article presents a study which characterizes the computational efficiency behavior of a standard EA as a software program. The study analyzes the effects of some implementation decisions regarding memory utilization (dynamic vs. static, local vs. global) and the generation of pseudorandom numbers, on the execution time of the resulting EA. The experimental analysis allows us to conclude that significant improvements in efficiency can be gained by applying simple guidelines on how to best program the EA.

In this work we use mathematical models, based on the study of the dynamics of the distributed evolutionary algorithms (dEA), to design self adaptive migration schedule for dEAs. We test our technique on two different problems: MAXSAT (a variant of the satisfiability problem), and a large scale problem, namely the radio network design problem. Its results are compared against the best results produced by distributed configurations with traditional tuning (constant preset migration schedules). Our experiments show that the technique produces results close to the best results obtained with fixed schedules while reducing the heavy cost of the parameter tuning.

Vehicular ad hoc networks (VANETs) provide the communications required to deploy Intelligent Transportation Systems (ITS). In the current state of the art in this field there is a lack of studies on real outdoor experiments to validate the new VANETs protocols and applications proposed by designers. In this work we have addressed the definition of a testbed in order to study the performance of the Vehicular Data Transfer Protocol (VDTP) in a real urban VANET. The VDTP protocol has been tested by employing six different parameter settings: one defined by human experts and five automatically optimized by means of metaheuristic algorithms (PSO, DE, GA, ES, and SA). As a result, we have been able to confirm the performance improvements when optimized VDTP configurations are used, validating the results previously obtained through simulation.

A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes.

Measuring the performance is still an important unsolved issue in dynamic optimization. Although several measures have been proposed in the literature, the problem about which ones should be used to describe the behaviour of algorithms remains open. One of the aspects to be considered is whether fitness averages are able to summarize the overall performance of metaheuristics over dynamic problems. Another issue is how to compare algorithms and, more specifically, how to quantify the numerical difference in performance between them. The main goal in this article is to propose a new way of measuring the behaviour of algorithms and also to provide a method to quantify the distance between them. We introduce thus two measures: one based on the area below the curve defined by some population property at each generation (e.g., the best-of-generation fitness), and a second one based on the area between the curves of two different algorithms.

In this article we analyze different metaheuristic algorithms applied to wind farm optimization. The basic idea is to utilize CHC (a sort of GA) and Simulated Annealing to obtain an acceptable configuration of wind turbines in the wind farm. The goal is to maximize the total output energy and minimize the number of wind turbines used. The energy produced depends of the farm geometry, wind conditions, and the terrain where it is settled. After analize some case studies we face a real wind distribution taken from Comodoro Rivadavia in Argentina. We study four scenarios, three of them having a constant west wind and the last one with the mentioned real wind distribution. We conclude that our methods outperform existing ones, as well as they produce actually useful results for real wind farms.

jMetal is a Java-based framework for multi-objective optimization using metaheuristics. It is a flexible, extensible, and easy-to-use software package that has been used in a wide range of applications. In this paper, we describe the design issues underlying jMetal, focusing mainly on its internal architecture, with the aim of offering a comprehensive view of its main features to interested researchers. Among the covered topics, we detail the basic components facilitating the implementation of multi-objective metaheuristics (solution representations, operators, problems, density estimators, archives), the included quality indicators to assess the performance of the algorithms, and jMetal's support to carry out full experimental studies.

The DNA fragment assembly problem is an NP-complete problem which has been solved efficiently by many metaheuristics. However, those techniques generally assemble fragments that belong to noiseless DNA sequences. But nowadays dealing with noisy instances is imperative. For that we analyse exhaustively how noiseless and noisy instances of this problem are dealt by three efficient algorithms (Problem aware local search, Simulated Annealing and Genetic Algorithms). This analysis includes a performance evaluation of those algorithms to assemble fragments and a study of the solution composition. From these analysis we observe that the GA is more robust in presence of noise than the other two searches, while it usually does not improve the accuracy of results for large instances (where Simulated Annealing is the more precise technique).

In this paper, we present a novel implementation of a Cellular Genetic Algorithm (cGA) model for a multi-GPU platform using NVIDIA's CUDA technology. This multi-GPU cGA model is compared first against a serial version in CPU and then versus an implementation on a single GPU. We divide the different operations of the cGA into distinct sets of instructions called kernels. Using the multi-GPU platform we observe that the speedup with respect to the CPU version ranges from 8 to 771, while it is similar to that of the GPU, with a little overhead in the multi-GPU case. Our results demonstrate that multi-GPU desktops can serve as cost-effective parallel computing platforms to obtain accurate results in very short time, although they need special considerations in order to improve on regular single GPUs.

In this work, we present a proposal for characterizing the OWL ontologies available on the Web from a significant sample. We have conducted a study to review the specific characteristics of these ontologies paying attention to features which can be important from the point of view of the ontology alignment: language, sizes, number, and kind of entities that are represented in them. As a result, we offer some statistical data that can be helpful in order to understand the current situation of OWL ontologies in the Web and, therefore to guide the process of taking decisions when developing applications for aligning them.

The Quadratic Assignment Problem (QAP) is a well-known NP-hard combinatorial optimization problem that is at the core of many real-world optimization problems. We prove that QAP can be written as the sum of three elementary landscapes when the swap neighborhood is used. We present a closed formula for each of the three elementary components and we compute bounds for the autocorrelation coefficient.

This paper presents a theoretical study about the selection pressure and the convergence speed of distributed evolutionary algorithms (dEA). In concrete, we model the best individual's growth curve and the takeover time for usual models of multipopulation EAs found in the literature. The calculation of the takeover time is a common analytical approach to measure the selection pressure of an EA. This work is another step forward to mathematically unify and describe the roles of all the parameters of the migration policy (the migration rate, the migration period, the topology, and the selection/replace schemes of immigrants) in the selection pressure induced by the dynamics of dEAs. In order to achieve these goals we analyze the behaviour of these algorithms and propose a mathematical formula which models that dynamic. The proposed mathematical model is later verified in practice.

We analyze various forms of the Frequency Assignment Problem using the theory of elementary landscapes. We show that three variants of the Frequency Assignment Problem are either directly an Elementary Landscape, or are a superposition of two Elementary Landscapes. We also examine the computability of neighborhood averages for partial neighborhoods.

SBSE techniques have been widely applied to requirements selection and prioritization problems in order to ascertain a suitable set of requirements for the next release of a system. Unfortunately, it has been widely observed that requirements tend to be changed as the development process proceeds and what is suitable for today, may not serve well into the future. Though SBSE has been widely applied to requirements analysis, there has been no previous work that seeks to balance the requirements needs of today with those of the future. This paper addresses this problem. It introduces a multi-objective formulation of the problem which is implemented using multi-objective Pareto optimal evolutionary algorithms. The paper presents the results of experiments on both synthetic and real world data. Copyright 2010 ACM.

To evaluate the search capabilities of a multiobjective algorithm, the usual approach is to choose a benchmark of known problems, to perform a fixed number of function evaluations, and to apply a set of quality indicators. However, while real problems could have hundreds or even thousands of decision variables, current benchmarks are normally adopted with relatively few decision variables (normally from 10 to 30). Furthermore, performing a constant number of evaluations does not provide information about the effort required by an algorithm to get a satisfactory set of solutions; this information would also be of interest in real scenarios, where evaluating the functions defining the problem can be computationally expensive. In this paper, we study the effect of parameter scalability in a number of state-of-the-art multiobjective metaheuristics. We adopt a benchmark of parameter-wise scalable problems (the Zitzler-Deb-Thiele test suite) and analyze the behavior of eight multiobjective metaheuristics on these test problems when using a number of decision variables that range from 8 up to 2048. By using the hypervolume indicator as a stopping condition, we also analyze the computational effort required by each algorithm in order to reach the Pareto front. We conclude that the two analyzed algorithms based on particle swarm optimization and differential evolution yield the best overall results.

Most of the software developed in the world follows the object-oriented (OO) paradigm. However, the existing work on evolutionary testing is mainly targeted to procedural languages. All this work can be used with small changes on OO programs, but object orientation introduces new features that are not present in procedural languages. Some important issues are polymorphism and inheritance. In this paper we want to make a contribution to the inheritance field by proposing some approaches that use the information of the class hierarchy for helping test case generators to better guide the search. To the best of our knowledge, no work exists using this information to propose test cases. In this work we define a branch distance for logical expressions containing the instanceof operator in Java programs. In addition to the distance measure, we propose two mutation operators based on the distance. We study the behaviour of the mutation operators on a benchmark set composed of nine OO programs. The results show that the information collected from the class hierarchy helps in the search for test cases.

Cellular genetic algoritms (cGAs) are characterized by its grid structure population, in which individuals can only interact with their neighbors. This kind of algorithms has demonstrated to have a high numerical performance thanks to the good exploration/exploitation balance they perform in the search space. Although cGAs seem very appropriate for parallelism, there is a low number of works proposing or studing parallel models for clusters of computers. This is probably because the model requires a high communication level between sub-populations due to the tight interactions among individuals. These parallel versions are however needed to cope with the high computational requirements of the current real-world problems. This article proposes a new parallel cellular genetic algorithm which maintains (or even improves because its asynchronicity) the numerical behaviour of a serial cGA, while at the same time it provokes an important reduction on the execution time for finding the optimal solution.

This paper introduces a new cellular genetic algorithm for solving multiobjective continuous optimization problems. Our approach is characterized by using an external archive to store nondominated solutions and a feedback mechanism in which solutions from this archive randomly replace existing individuals in the population after each iteration. The result is a simple and elitist algorithm called MOCell. Our proposal has been evaluated with both constrained and unconstrained problems and compared against NSGA-II and SPEA2, two state-of-the-art evolutionary multiobjective optimizers. For the studied benchmark, our experiments indicate that MOCell obtains competitive results in terms of convergence and hypervolume, and it clearly outperforms the other two compared algorithms concerning the diversity of the solutions along the Pareto front. © 2009 Wiley Periodicals, Inc.

The radio network design (RND) is an NP-hard optimization problem which consists of the maximization of the coverage of a given area while minimizing the base station deployment. Solving RND problems efficiently is relevant to many fields of application and has a direct impact in the engineering, telecommunication, scientific, and industrial areas. Numerous works can be found in the literature dealing with the RND problem, although they all suffer from the same shortfall: a noncomparable efficiency. Therefore, the aim of this paper is twofold: first, to offer a reliable RND comparison base reference in order to cover a wide algorithmic spectrum, and, second, to offer a comprehensible insight into accurate comparisons of efficiency, reliability, and swiftness of the different techniques applied to solve the RND problem. In order to achieve the first aim we propose a canonical RND problem formulation driven by two main directives: technology independence and a normalized comparison criterion. Following this, we have included an exhaustive behavior comparison between 14 different techniques. Finally, this paper indicates algorithmic trends and different patterns that can be observed through this analysis.

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

Model checking is a well-known and fully automatic technique for checking software properties, usually given as temporal logic formulae on the program variables. Most of model checkers found in the literature use exact deterministic algorithms to check the properties. These algorithms usually require huge amounts of memory if the checked model is large. We propose here the use of an algorithm based on ACOhg, a new kind of ant colony optimization model, to search for liveness property violations in concurrent systems. This algorithm has been previously applied to the search for safety errors with very good results and we apply it here for the first time to liveness errors. The results state that our algorithmic proposal, called ACOhg-live, is able to obtain very short error trails in faulty concurrent systems using a low amount of resources, outperforming by far the results of nested-DFS, the traditional algorithm used for this task in the model checking community and implemented in most of the explicit state model checkers. This fact makes ACOhg-live a very suitable algorithm for finding liveness errors in large faulty concurrent systems, in which traditional techniques fail because of the model size.

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

Some real-world optimization problems have hundreds or even thousands of decision variables. However, the effect that the scalability of parameters has in modern multi-objective metaheuristic algorithms has not been properly studied (the current benchmarks are normally adopted with ten to thirty decision variables). In this paper, we adopt a benchmark of parameter-wise scalable problems (the ZDT test problems) and analyze the behavior of six multi-objective metaheuristics on these test problems when using a number of decision variables that goes from 8 up to 2048. The computational effort required by each algorithm in order to reach the true Pareto front is also analyzed. Our study concludes that a particle swarm algorithm provides the best overall performance, although it has difficulties in multifrontal problems.

Liveness properties in concurrent systems are, informally, those properties that stipulate that something good eventually happens during execution. In order to prove that a given system satisfies a liveness property, model checking techniques are utilized. However, most of the model checkers found in the literature use exhaustive deterministic algorithms that require huge amounts of memory if the concurrent system is large. Here we propose the use of an algorithm based on ACOhg, a new kind of Ant Colony Optimization algorithm, for searching for liveness property violations in concurrent systems. We also take into account the structure of the liveness property in order to improve the efficacy and efficiency of the search. The results state that our algorithmic proposal, called ACOhg-live, is able to obtain very short error trails in faulty concurrent systems using a low amount of resources, outperforming by far the results of Nested-DFS and Improved-Nested-DFS, two algorithms used in the literature for this task in the model checking community. This fact makes ACOhg-live a very suitable algorithm for finding liveness errors in large faulty concurrent systems, in which traditional techniques fail because of the model size.

Model checking is a fully automatic technique for check-ing concurrent software properties in which the states of a concurrent system are explored in an explicit or implicit way. However, the state explosion problem limits the size of the models that are possible to check. Genetic Algorithms (GAs) are metaheuristic techniques that have obtained good results in problems in which exhaustive techniques fail due to the size of the search space. Unlike exact techniques, metaheuristic techniques can not be used to verify that a program satisfies a given property, but they can find errors on the software using a lower amount of resources than exact techniques. In this paper, we compare a GA against clas-sical exact techniques and we propose a new operator for this problem, called memory operator, that allows the GA to explore even larger search spaces. We implemented our ideas in the Java Pathfinder (JPF) model checker to validate them and present our results. To the best of our knowledge, this is the first implementation of a Genetic Algorithm in this model checker.

The Frequency Assignment Problem (FAP) is one of the key issues in the design of GSM networks (Global System for Mobile communications), and will remain important in the foreseeable future. There are many versions of FAP, most of them benchmarking-like problems. We use a formulation of FAP, developed in published work, that focuses on aspects which are relevant for real-world GSM networks. In this paper, we have designed, adapted, and evaluated several types of metaheuristic for different time ranges. After a detailed statistical study, results indicate that these metaheuristics are very appropriate for this FAP. New interference results have been obtained, that significantly improve those published in previous research.

This paper presents a new distributed Differential Evolution (dDE) algorithm and evaluates it according to the standard procedure set in the special session of continuous optimization of CEC’05. We statistically validate our results in continuous optimization versus several other efficient techniques. Our distributed Differential Evolution is simple and accurate, at the same time amenable, to be applied to a wide variety of problems, especially for noisy and multimodal functions.

Many specific algorithms and metaheuristics have been proposed for solving the DNA fragment assembly problem, but new algorithms with more capacity for solving this problem are necessary. The fragment assembly problem consists in building the DNA sequence from several hundreds (or even, thousands) of fragments obtained by biologists in the laboratory. This is an important task in any genome project since the rest of the phases depend on the accuracy of the results of this stage. In order to achieve this objective we propose a hybrid algorithm that achieves very accurate results in comparison with other metaheuristics.

In this paper we present a study of an Ant Colony System (ACS) for the two-dimensional strip packing problem. In our computational study, we emphasize the influence of incorporating a simple optimization method at each cycle of the ACS. In this hybrid approach, local optimization is applied to a subset of the newly generated solutions to move them to a local optimum. We show that our ACS algorithm, when combined with a fine-tuned local search procedure, can compete with an existing genetic algorithm, reaching solutions of good quality and also exhibiting low execution times.

In this work we show that a metaheuristic, the variable neighborhood search (VNS), can be effectively used in order to improve the performance of the hardware-friendly version of the support vector machine (SVM). Our target is the implementation of the feed-forward phase of SVM on resource-limited hardware devices, such as field programmable gate arrays (FPGAs) and digital signal processors (DSPs). The proposal has been tested on a machine-vision benchmark dataset for embedded automotive applications, showing considerable performance improvements respect to previously used techniques.

Many of the optimization problems from the real world are multiobjective in nature, and the reference algorithm for multiobjective optimization is NSGA-II. Frequently, these problems present a high complexity, so classical metaheuristic algorithms fail to solve them in a reasonable amount of time; in this context, parallelism is a choice to overcome this fact to some extent. In this paper we study three parallel approaches (a synchronous and two asynchronous strategies) for the NSGA-II algorithm based on the master-worker paradigm. The asynchronous schemes are designed to be used in grid systems, so they can make use of hundreds of machines. We have applied them to solve a real world problem which lies in optimizing a broadcasting protocol using a network simulator. Our experiences reveal that significant time reductions can be achieved with the distributed approaches by using a grid system of more than 300 processors.

The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications. The scheduling problem is computationally hard even when there are no dependencies among jobs. Thus, we present in this paper a new tabu search (TS) algorithm for the problem of batch job scheduling on computational grids. We consider the job scheduling as a bi-objective optimization problem consisting of the minimization of the makespan and flowtime. The bi-objectivity is tackled through a hierarchic approach in which makespan is considered a primary objective and flowtime a secondary one. An extensive experimental study has been first conducted in order to fine-tune the parameters of our TS algorithm. Then, our tuned TS is compared versus two well known TS algorithms in the literature (one of them is hybridized with an ant colony optimization algorithm) for the problem. The computational results show that our TS implementation clearly outperforms the compared algorithms. Finally, we evaluated the performance of our TS algorithm on a new set of instances that better fits with the concept of computational grid. These instances are composed of a higher number of -heterogeneous- machines (up to 256) and emulate the dynamic behavior of these systems.

We propose the use of a new algorithm to solve multiobjective optimization problems. Our proposal adapts the well-known scatter search template for single-objective optimization to the multiobjective domain. The result is a hybrid metaheuristic algorithm called Archive-Based hYbrid Scatter Search (AbYSS), which follows the scatter search structure but uses mutation and crossover operators from evolutionary algorithms. AbYSS incorporates typical concepts from the multiobjective field, such as Pareto dominance, density estimation, and an external archive to store the nondominated solutions. We evaluate AbYSS with a standard benchmark including both unconstrained and constrained problems, and it is compared with two state-of-the-art multiobjective optimizers, NSGA-II and SPEA2. The results obtained indicate that, according to the benchmark and parameter settings used, AbYSS outperforms the other two algorithms as regards the diversity of the solutions, and it obtains very competitive results according to the convergence to the true Pareto fronts and the hypervolume metric.

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

Ant Colony Optimization (ACO) has been successfully applied to those combinatorial optimization problems which can be translated into a graph exploration. Artificial ants build solutions step by step adding solution components that are represented by graph nodes. The existing ACO algorithms are suitable when the graph is not very large (thousands of nodes) but is not useful when the graph size can be a challenge for the computer memory and cannot be completely generated or stored in it. In this paper we study a new ACO model that overcomes the difficulties found when working with a huge construction graph. In addition to the description of the model, we analyze in the experimental section one technique used for dealing with this huge graph exploration. The results of the analysis can help to understand the meaning of the new parameters introduced and to decide which parameterization is more suitable for a given problem. For the experiments we use one real problem with capital importance in Software Engineering: refutation of safety properties in concurrent systems. This way, we foster an innovative research line related to the application of ACO to formal methods in Software Engineering.

Model Checking is a well-known and fully automatic technique forchecking software properties, usually given as temporal logicformulae on the program variables. Most model checkers found inthe literature use exact deterministic algorithms to check theproperties. These algorithms usually require huge amounts ofcomputational resources if the checked model is large. We proposehere the use of a new kind of Ant Colony Optimization (ACO) model, ACOhg, to refute safety properties in concurrent systems. ACO algorithms are stochastic techniques belonging to the class of metaheuristic algorithms and inspired by the foraging behaviour of real ants. The traditional ACO algorithms cannot deal with the model checking problem and thus we use ACOhg to tackle it. The results state that ACOhg algorithms find optimal or near optimal error trails in faulty concurrent systems with a reduced amount of resources, outperforming algorithms that are the state-of-the-art in model checking. This fact makes them suitable for checking safety properties in large concurrent systems, in which traditional techniques fail to find errors because of the model size.

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.

No abstract available.

No abstract available.

Frequency planning is a very important task for current GSM operators. In this work we present a new mathematical formulation of the problem in which the frequency plans are evaluated by using accurate interference information coming from a real GSM network. We have developed an ant colony optimization (ACO) algorithm to tackle this problem. After accurately tuning this algorithm, it has been compared against a (1,10) Evolutionary Algorithm (EA). The results show that the ACO clearly outperforms the EA when using different time limits as stopping condition for a rather extensive comparison.

Radio network design (RND) is a fundamental problem in cellular networks for telecommunications. In these networks, the terrain must be covered by a set of base stations (or antennae), each of which defines a covered area called cell. The problem may be reduced to figure out the optimal placement of antennae out of a list of candidate sites trying to satisfy two objectives: to maximize the area covered by the radio signal and to reduce the number of used antennae. Consequently, RND is a bi-objective optimization problem. Previous works have solved the problem by using single-objective techniques which combine the values of both objectives. The used techniques have allowed to find optimal solutions according to the defined objective, thus yielding a unique solution instead of the set of Pareto optimal solutions. In this paper, we solve the RND problem using a multi-objective version of the algorithm CHC, which is the metaheuristic having reported the best results when solving the single-objective formulation of RND. This new algorithm, called MOCHC, is compared against a binary-coded NSGA-II algorithm and also against the provided results in the literature. Our experiments indicate that MOCHC outperfoms NSGA-II and, more importantly, it is more efficient finding the optimal solutions than single-objectives techniques.

Computational grids are an important emerging paradigm for large-scale distributed computing. As grid systems become more wide-spread, techniques for efficiently exploiting the large amount of grid computing resources become increasingly indispensable. A key aspect in order to benefit from these resources is the scheduling of jobs to grid resources. Due to the complex nature of grid systems, the design of efficient grid schedulers becomes challenging since such schedulers have to be able to optimize many conflicting criteria in very short periods of time. In this work we exploit the capabilities of cellular memetic algorithms (cMAs) for obtaining efficient batch schedulers for grid systems. A careful design of the cMA methods and operators for the problem yielded to an efficient and robust implementation. Our experimental study, based on a known static benchmark for the problem, shows that this heuristic approach is able to deliver very high quality planning of jobs to grid nodes and thus it can be used to design efficient dynamic schedulers for real grid systems. Such dynamic schedulers can be obtained by running the cMA-based scheduler in batch mode for a very short time to schedule jobs arriving to the system since the last activation of the cMA scheduler.

Workforce planning is an important activity that enables organizations to determine the workforce needed for a given task. Solving a workforce planning problem is a hard combinatorial process requiring modern techniques such advanced metaheuristics. In this work, we analyze several options to design a parallel genetic algorithm, which can find high-quality solutions to realistic size problem instances.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithm (GA) -population based heuristic-with a structured population so that individuals can only interact with their neighbors. The existence of small overlapped neighborhoods in this decentralized population provides both diversity and exploration, while the exploitation of the search space is strengthened inside each neighborhood. This balance between exploration and exploitation makes cGAs naturally suitable for solving complex problems. In this paper we tackle the minimization of a number of problems (both academic and from the real world) with a real-coded cGA, called JCell. The results show that JCell improves the compared algorithms for a number of the studied problems, thus increasing the overall performance with respect to other complex heterogeneous distributed GAs, belonging to the state-of-the-art in continuous optimization.

Workforce planning is an important activity that enables organizations to determine the workforce needed for continued success. A workforce planning problem is a very complex task that requires modern techniques to be solved adequately. In this work, we describe the development of two parallel metaheuristic methods, a parallel genetic algorithm and a parallel scatter search, which can find high-quality solutions to 20 different problem instances. Our experiments show that parallel versions do not only allow to reduce the execution time but they also improve the solution quality

This paper presents a study of different models for the best individual's growth curve and the takeover time in a distributed evolutionary algorithm (dEA). The calculation of the takeover time is a common analytical approach to measure the selection pressure of an EA. This work is another step forward to mathematically unify and describe the roles of several parameters of the migration policy: the migration rate, the migration frequency, and the topology in the selection pressure induced by the dynamics of dEAs. In order to achieve these goals we comparatively evaluate the appropriateness of the well-known panmictic logistic model, hypergraph model and two new models for dEAs. We introduce new accurate models for growth curves and takeover times in dEAs, and analytically explain the effects of the migration rate, migration frequency, and topology

As more research centers embark on sequencing new genomes, the problem of DNA fragment assembly for shotgun sequencing is growing in importance and complexity. Accurate and fast assembly is a crucial part of any sequencing project and since the DNA fragment assembly problem is NP-hard, exact solutions are very difficult to obtain. Various heuristics, including genetic algorithms, were designed for solving the fragment assembly problem. While the sequential genetic algorithm has given good results, it is unable to sequence very large DNA molecules. In this work, we present two parallel methods, a distributed genetic algorithm and a parallel simulated annealing, to solve problem instances that are 77K base pairs long accurately

Cellular genetic algorithms (cGAs) are mainly characterized by their spatially decentralized population, in which individuals can only interact with their neighbors. In this work, we study the behavior of a large number of different cGAs when solving the well-known 3-SAT problem. These cellular algorithms differ in the policy of individuals update and the population shape, since these two features affect the balance between exploration and exploitation of the algorithm. We study in this work both synchronous and asynchronous cGAs, having static and dynamically adaptive shapes for the population. Our main conclusion is that the proposed adaptive cGAs outperform other more traditional genetic algorithms for a well known benchmark of 3-SAT.

Parallelism and Optimization are two disciplines that are used together in numerous applications. Solving complex problems in optimization often means to face complex search landscapes, what needs time-consuming operations. Exact and heuristic techniques are being used nowadays to get solutions to problems in mathematics, logistics, bioinformatics, telecommunications, and many other relevant fields. For these tasks it is mandatory to deal with cluster computing in many cases, multiprocessors, and even with computational grids. In this talk I will address the basic challenges of using parallel tools, software, and hardware for extending existing optimization procedures to work in a parallel environment. I will present some basic optimization algorithms, especially heuristic ones, and discuss the application of parallelism to them. Also, I will show how new techniques become possible due to parallelism, giving birth to a whole new class of algorithms and new research lines.

This paper studies static and dynamic decentralized versions of the search model known as cellular genetic algorithm (cGA), in which individuals are located in a specific topology and interact only with their neighbors. Making changes in the shape of such topology or in the neighborhood may give birth to a high number of algorithmic variants. We perform these changes in a methodological way by tuning the concept of ratio. Since the relationship (ratio) between the topology and the neighborhood shape defines the search selection pressure, we propose to analyze in depth the influence of this ratio on the exploration/exploitation tradeoff. As we will see, it is difficult to decide which ratio is best suited for a given problem. Therefore, we introduce a preprogrammed change of this ratio during the evolution as a possible additional improvement that removes the need of specifying a single ratio. A later refinement will lead us to the first adaptive dynamic kind of cellular models to our knowledge. We conclude that these dynamic cGAs have the most desirable behavior among all the evaluated ones in terms of efficiency and accuracy; we validate our results on a set of seven different problems of considerable complexity in order to better sustain our conclusions.

In this paper, we present quantitative models for the selection pressure of cellular evolutionary algorithms on regular one- and two-dimensional (2-D) lattices. We derive models based on probabilistic difference equations for synchronous and several asynchronous cell update policies. The models are validated using two customary selection methods: binary tournament and linear ranking. Theoretical results are in agreement with experimental values, showing that the selection intensity can be controlled by using different update methods. It is also seen that the usual logistic approximation breaks down for low-dimensional lattices and should be replaced by a polynomial approximation. The dependence of the models on the neighborhood radius is studied for both topologies. We also derive results for 2-D lattices with variable grid axes ratio.

In This work we study cellular evolutionary algorithms, a kind of decentralized heuristics, and the importance of the induced exploration/exploitation balance on different problems. It is shown that, by choosing synchronous or asynchronous update policies, the selection pressure, and thus the exploration/exploitation tradeoff, can be influenced directly, without using additional ad hoc parameters. Synchronous algorithms of different neighborhood-to-topology ratio, and asynchronous update policies are applied to a set of benchmark problems. Our conclusions show that the update methods of the asynchronous versions, as well as the ratio of the decentralized algorithm, have a marked influence on its convergence and on its accuracy.

Summary form only given. Evolutionary algorithms (EAs) are applied to solve the radio network design problem (RND). The task is to find the best set of transmitter locations in order to cover a given geographical region at an optimal cost. Usually, parallel EAs are needed in order to cope with the high computational requirements of such a problem. Here, we try to develop and evaluate a set of sequential and parallel genetic algorithms (GAs) in order to solve efficiently the RND problem. The results show that our distributed steady state GA is an efficient and accurate tool for solving RND that even outperforms existing parallel solutions. The sequential algorithm performs very efficiently from a numerical point of view, although the distributed version is much faster, with an observed linear speedup.

This paper contains a modern vision of the parallelization techniques used for evolutionary algorithms (EAs). The work is motivated by two fundamental facts: 1) the different families of EAs have naturally converged in the last decade while parallel EAs (PEAs) are still lack of unified studies; and 2) there is a large number of improvements in these algorithms and in their parallelization that raise the need for a comprehensive survey. We stress the differences between the EA model and its parallel implementation throughout the paper. We discuss the advantages and drawbacks of PEAs. Also, successful applications are mentioned and open problems are identified. We propose potential solutions to these problems and classify the different ways in which recent results in theory and practice are helping to solve them. Finally, we provide a highly structured background relating to PEAs in order to make researchers aware of the benefits of decentralizing and parallelizing an EA.

Parallel genetic algorithms (PGAs) have been traditionally used to overcome the intense use of CPU and memory that serial GAs need to solve complex problems. Non-parallel GAs can be classified into two classes: panmictic and structured-population algorithms. The difference relies on whether any individual in the population can mate with any other one or not. In this work they both are considered as two reproductive loop types executed in the islands of a parallel distributed GA. Our aim is to extend the existing studies on more conventional sequential islands to other kinds of evolution. A key issue in such a distributed PGA is the migration policy. The paper investigates the influence of the migration frequency and the migrant selection in a ring of islands performing either steady-state or cellular GAs. The study uses different problem types, namely deceptive, multimodal, NP-complete, and epistatic search landscapes, in order to provide a wide spectrum of problem difficulty to sustain the results. Large isolation values and random selection of the migrants are shown to provide a better success rate and a lower number of visited points. Also, some differences are pointed out in the behavior of panmictic and structured populations. Finally, the results show the advantages of an asynchronous migration step in the distributed GA.

This paper analyzes the detection of stagnation states in iterated local search algorithms. This is done considering elements such as the population size, the length of the encoding and the number of observed non-improving iterations. This analysis isolates the features of the target problem within one parameter for which three different estimations are given: two static a priori estimations and a dynamic approach. In the latter case, a stochastic reverse hill climbing algorithm is used to extract information from the fitness landscape. The applicability of these estimations is studied and exemplified on different problems.

A dataflow model to obtain parallelism in the evaluation of Datalog is presented. This model performs query evaluation as a dataflow through a network of communicating concurrent processes capable of solving the query. This process network is based on the intensional database definition, plus the concrete query to be evaluated. A cost model to cope with the load balancing problem is described. A load balancing algorithm is presented and discussed. An algorithm to optimize the evaluation is described which is based on process network rewriting. This utilizes information in the query bindings to be evaluated in order to optimize the dataflow graph.