• First dominance-based multi-objective optimization approach for bias mitigation. • First swarm intelligence approach, also including other interesting techniques. • Study of six real-life scenarios, considering different vital aspects and bias types. • High mitigation of bias, improving fairness and also the original model’s accuracy. • Results surpassing those from other authors’ approaches with remarkable improvements. At present, many decisions, even decisions that affect people’s lives, are increasingly made by decision-making software. For this reason, it is really important to avoid decision-making software being biased, that is, it needs to assure fairness. As decision-making software is generally based on classification models, its bias can be mitigated in three different stages: pre-processing, in-processing, and post-processing. However, despite the importance of fairness on these models, there are very few proposals for the post-processing stage that are able to mitigate bias without reducing the original model’s accuracy. Therefore, this problem should be addressed as a multi-objective problem, optimizing at the same time both fairness and accuracy. Taking this into account, we propose a Multi-Objective Swarm Intelligence approach for BIas Mitigation (MOSIBIM), which combines dominance-based multi-objective optimization (with techniques such as Pareto fronts, niching, and reference points), population-based evolutionary computation, swarm intelligence, and convergence-stagnation differentiation. In order to analyze the improvements that this proposal produces over other approaches in the literature, its results on fairness and accuracy have been compared with the results obtained by other five approaches, optimizing different classification models and in six distinct real-life scenarios which have various types of bias. The results of MOSIBIM show great improvements on fairness in comparison with the other approaches, as it reaches improvement percentages of 91.7 % and, on average, the results are always in the range of 66.6 % to 76.6 % of improvement. Furthermore, the proposed approach has been able to improve the original model’s accuracy in all the studied cases.

Research on parallel computing has promoted significant advances in the solution of different real-world problems. One of the main application domains that have benefited from the exploitation of parallelism is bioinformatics. However, bioinformatics tools are often constrained by the use of low-level platform-specific programming models. This issue limits the spectrum of hardware that can be used to accelerate time-consuming biological workloads, while also affecting programming productivity and code maintenance. To address such limitations, this work investigates high-level multi-platform approaches to parallelize, as a case study, an important task in evolutionary bioinformatics: the evaluation of phylogenetic quality. Particularly, we define parallel designs of the parsimony scoring function for CPU and GPU devices, using three high-level application programming interfaces with multi-platform support: OpenMP, OpenACC, and SYCL. Different optimizations and algorithmic strategies are defined to boost execution according to the characteristics of the tackled parallel tasks. An in-depth experimental evaluation on real-world data reveals the main strengths and areas of improvement for each high-level multi-platform approach, in comparison to lower-level platform-specific alternatives. In addition, the study of single-source performance portability suggests that CPU designs behave better than GPU ones, yet device-oriented optimizations are still needed to pursue a precise exploitation of computational resources.

Gene networks have gained considerable relevance in cancer research, enabling the representation of complex biological relationships that provide insights into the mechanisms driving tumor development and progression. The increasing availability of biological data facilitates the construction of clinically relevant gene networks by integrating multiple information sources. Specifically, we consider mutation data, patient survival data, and protein-protein interaction data to identify networks whose genes are recurrently mutated, significantly involved in patient survival, and functionally associated. To this end, we apply multi-objective optimization to simultaneously maximize survival impact, functional association, and mutation coverage. Herein, we introduce MOTEA-GENSU (Multi-Objective Two-archive Evolutionary Algorithm to discover GEne Networks involved in SUrvival), a novel method that employs two collaborative archives and intelligent evolutionary operators to guide the generation of high-quality gene networks. Evaluation across 27 real biological scenarios covering diverse cancer types shows that MOTEA-GENSU outperforms existing methods, achieving superior results in 92.6% of comparisons, with improvements of up to 315.8% over the best-performing competing approach, and consistently surpassing all state-of-the-art methods on average within each evaluated dataset. Biological analysis of the identified networks validates their functional coherence and significant impact on cancer patient survival, revealing clinically relevant networks composed of genes with demonstrated prognostic value.

• Multi-objective algorithm based on decomposition for the tagSNP selection problem • Implementation of five new problem-aware operators to explore the search space • Comparative study of the proposed method with six different alternative approaches • Experimentation with five highly relevant datasets from 1000 Genomes Project (1KGP) • Competitive approach in terms of runtime and results quality after the comparisons Nowadays multiple bioinformatics issues can be solved by using evolutionary computation due to its potential to address complex optimization problems. TagSNP selection lies within this class of challenging problems, since genotyping all the Single Nucleotide Polymorphisms (SNPs) for haplotype identification is economically costly and time-consuming. If a reduced number of tagSNPs is chosen instead, the classification of haplotypes will accordingly show a worsening. As a result, tagSNP selection can be considered as a multi-objective optimization problem, in which the aim is to optimize haplotype dissimilarity while minimizing the number of selected tagSNPs. We propose and detail an approach based on the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) for accurately selecting tagSNPs attending to these two objectives. The proposed method includes novel problem-aware operators for the initialization, crossover, and mutation to boost optimization capabilities. The proposal is experimentally compared with six approaches from the literature on five real datasets, using in the evaluation three quality metrics and their corresponding statistical analyses. The attained results denote that our algorithm provides statistically-significant improvements over previous methods with competitive runtimes, thus highlighting the relevance of the proposed multi-objective approach.

Abstract Nowadays, automatic text summarization task is a matter that has acquired special relevance in numerous contexts. Particularly, sentiment analysis and opinion mining need summarization methods to quickly analyze public opinion about any event. In this way, the aim of the sentiment-oriented summarization approach is to produce a summary reflecting the sentiment of the authors’ opinions, covering the main content, and reducing the redundancy. In this work, a Sentiment-Oriented Dominance-based Bee Algorithm (SODBA) has been designed, developed, and applied for solving this problem. Experimentation has been conducted with datasets provided by Document Understanding Conferences. The evaluation of the results has been carried out by using the Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics and the Pearson correlation coefficient. The reported results have outperformed those obtained in the scientific literature in terms of ROUGE metrics. Moreover, SODBA has been applied to the tweets concerning the COVID-19 pandemic to obtain the summaries of the days with the most positive and the most negative sentiment.

Identifying cancer driver pathways is essential in cancer research. This problem is well-suited to multi-objective optimization, as cancer driver pathways consist of frequently mutated genes that cover a significant proportion of patients and exhibit high correlation due to their coordinated functionality. Therefore, this problem involves two competing objectives to maximize: patient coverage and gene network correlation. To optimize these objectives simultaneously, we propose a Multi-objective Artificial Bee Colony approach for Identifying cancer driver Pathways (MABCIP). Our approach leverages the strengths of the Artificial Bee Colony algorithm in combining exploitation (via employed and onlooker bees) and exploration (through scout bees). MABCIP incorporates problem-aware initialization and mutation operators which substantially enhance its performance. Specifically, MABCIP achieves noteworthy improvements in hypervolume and attains 100% set coverage in most cases over the version with standard operators. We thoroughly evaluate MABCIP against state-of-the-art methods using real cancer datasets comprehending 45 experimental scenarios. MABCIP consistently outperforms existing methods, attaining the best results in 44 out of 45 experimental scenarios and showing remarkable performance in complex instances. Notably, MABCIP obtains results up to 7.1 times better than those of the best-performing state-of-the-art method. Moreover, MABCIP identifies pathways involved in the development of targeted therapies, highlighting its potential for identifying clinically relevant mechanisms.

• First multi-objective swarm-intelligence algorithm for solving document clustering • 3 objectives are adopted to handle clustering tasks: compactness, separation, and DBI • Problem-aware search operators are developed and integrated into the approach • The proposal is evaluated using 3 clustering metrics, comparing with other 15 methods • Mean improvements of 16.18% in F1C, 86.81% in ARI, and 21.53% in NMI are accomplished The explosive growth of uncategorized web documents requires effective methods for their organization. Clustering techniques address this challenge by automatically grouping similar documents, making large amounts of unstructured data more manageable. In recent times, multi-objective optimization approaches have become an effective way to solve the document clustering problem. However, in the scientific literature, there is a lack of studies that address this task by using swarm-intelligence algorithms from this optimization viewpoint. For this reason, a multi-objective swarm-intelligence algorithm for document clustering (MOSIDOC) has been designed, developed, and applied in this work. MOSIDOC is based on the idea of combining swarm-intelligence mechanisms from artificial bee colony with problem-aware operators to attain an accurate processing of the search space. The criteria of compactness, separation, and Davies-Bouldin index have been formulated as the objective functions to be optimized. The experimentation has been carried out on ODP-239, one of the most widely-used datasets for testing document clustering methods. To comprehensively evaluate the proposed approach, the evaluation metrics of cluster-level F1 measure, Adjusted Rand Index, and Normalized Mutual Information have been applied. The obtained results denote that MOSIDOC leads to average percentage improvements up to 86.81%, in comparison to other fifteen competing methods.

Abstract The use of keywords is increasingly being applied across diverse domains, including the movie industry, whose main platforms are adopting advanced natural language processing techniques. Algorithms for automatic extraction of keywords can provide relevant information in this domain. The most novel approaches covering several categories (statistics, graphs, word embedding, and hybrid) have been considered in a model study framework. They have been implemented, applied, and evaluated with standard datasets. In addition, a movie dataset with gold standard keywords, based on textual metadata from synopses and reviews, has been specifically developed for this scope. Keyword extraction models have been evaluated in terms of F-score and computation time. Furthermore, content analysis, both quantitative and qualitative, of the extracted keywords in the movie context has been performed. Results show a great variability in model performance and computation time among the different models. Qualitative results, in addition to F-score and computation time, demonstrate that keyword extraction works better with synopses than with reviews. The quantitative content analysis revealed that EmbedRank effectively reduces redundancy and limits the use of proper nouns, leading to high-quality keywords.

• IDHEA (Indicator and Decomposition-based Hybrid Evolutionary Algorithm) is proposed. • IDHEA is designed, implemented, and applied to solve automatic text summarization. • IDHEA’s performance is assessed by multi-objective and text summarization metrics. • IDHEA is compared with multi-objective algorithms and proposals from other authors. • IDHEA outperforms these other optimization algorithms from the scientific literature. The field of multi-objective optimization is experiencing a relevant growth due to its successful applications in numerous real-life problems. Two prominent trends are indicator-based and decomposition-based search strategies. However, the performance of these search strategies depends on the specific problem to solve. In the context of automatic summarization, hybridization of these techniques is an interesting and challenging proposal, which aims to improve the performance. For this reason, an Indicator and Decomposition-based Hybrid Evolutionary Algorithm (IDHEA) has been designed, implemented, and tested for addressing the automatic summarization problem. The proposed hybrid multi-objective approach has integrated the fundamentals of both indicator-based and decomposition-based techniques to solve this particular problem. Experimentation has been conducted using Document Understanding Conferences (DUC) dataset. The performance has been assessed by means of multi-objective metrics such as hypervolume, inverted generational distance, distance to ideal point, and set coverage, while summary quality has been evaluated with Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics. The proposed approach has outperformed standard algorithms in multi-objective evaluation, in addition to improving the existing results in the scientific literature in terms of summary quality.

Abstract Streaming services are increasingly leveraging Artificial Intelligence (AI) technologies for improved content cataloging, user experiences in content discovery, and personalization. A significant challenge in this domain is the automated assignment of microgenres to movies. This study introduces and evaluates approaches based on clustering, topic modeling, and word embedding to address this task. The evaluation employs a preprocessed dataset containing movie-related data—title tags, synopses, genres, and reviews—alongside a predefined microgenre list. Comparisons of three activation functions (binary step, ramp, and sigmoid) gauge their effectiveness in augmenting microgenre tags. Results demonstrate the superiority of the word embedding approach over clustering and topic modeling in terms of mean accuracy. Even more, the word embedding approach stands as the sole fully automated solution. Analysis indicates that incorporating review-based tags introduces noise and undermines accuracy. Besides, the word embedding approach yields optimal outcomes using the sigmoid function, effectively doubling assigned tags while maintaining matching quality. This sheds light on the potential of word embedding methods within the movie domain.

El número de investigaciones que intentan alinear las redes de interacción proteína-proteína (PPI) ha aumentado con el crecimiento de los estudios centrados en la recopilación de datos de PPI. Estos trabajos tienen como objetivo identificar áreas conservadas entre especies difíciles de diferenciar debido a la especiación. Sin embargo, no existe un enfoque estándar para alinear las redes PPI y los alineadores globales encuentran dificultades para construir alineamientos con alta calidad biológica y estructural. Para abordar este problema, proponemos una técnica de conjunto innovadora que combina las fortalezas de los alineadores en el campo de alineación de redes PPI evitando sus debilidades. Este enfoque reduce la dispersión en alineadores globales individuales tan diferentes y contribuye a lograr un estándar global que produzca alineamientos de mayor calidad. Esto es posible gracias a las dos ramas que componen nuestro conjunto y que tienen como objetivo mejorar los alineamientos en términos de calidad biológica o estructural. Además de una nueva heurística que reemplaza al alineador de segundo nivel en la rama biológica centrada en la calidad. Nuestro enfoque logra alineamientos de mayor calidad, como se demuestra a través de experimentos con 10 escenarios diferentes que involucran datos reales de 5 especies. Nuestras soluciones superan a otros alineadores individuales y técnicas de conjunto, como el embolsado, en términos de calidad biológica y estructural. Además, el tiempo necesario para realizar el conjunto es mínimo en comparación con el de los alineadores individuales.

Morality is a topic that people are increasingly concerned about. Morality is observed and measured during public acts or when developing and consuming products, such as movies. The Moral Foundations Theory (MFT) was developed to rigorously perform these measurements with the support of the Moral Foundations Dictionary (MFD). In this paper, a Word Embedding-based Moral Foundation Assignment (WEMFA) approach has been designed, implemented, and applied to the movie domain for multiple assignment of moral foundations. WEMFA may use any dictionary, and it has been applied to a movie collection generated from movie synopses. A comparison between WEMFA and MoralStrength, the only approach found in the scientific literature, has been carried out. The proposed approach provided a percentage improvement of 41.7% with respect to the best version of MoralStrength, which uses an extension of the original MFD almost 10 times larger in number of terms. In addition, an extension of the original MFD (MFD24) has been built by adding 14 new moral foundations to the 10 original ones, enriching the moral context. WEMFA provided a mean accuracy of 78% with MFD24 despite the increment of the number of moral foundations. Besides, new extended dictionaries or even totally different ones can be used with WEMFA, since it does not need any training.

This special section ofIEEE/ACM Transactions on Computational Biology and Bioinformaticspresents extended versions of some of the best papers accepted at the Eighth International Conference on Algorithms for Computational Biology, AlCoB 2021, held online due to the COVID-19 pandemic on November 9-11, 2021. The conference was organized by the Department of Computer Science at the University of Montana and the Institute for Research Development, Training and Advice - IRDTA, Brussels/London.

Currently, the explosive growth of the information available on the Internet makes automatic text summarization systems increasingly important. A particularly relevant challenge is the update summarization task. Update summarization differs from traditional summarization in its dynamic nature. While traditional summarization is static, that is, the document collections about a specific topic remain unchanged, update summarization addresses dynamic document collections based on a specific topic. Therefore, update summarization consists of summarizing the new document collection under the assumption that the user has already read a previous summarization and only the new information is interesting. The multiobjective number-one-selection genetic algorithm (MONOGA) has been designed and implemented to address this problem. The proposed algorithm produces a summary that is relevant to the user's given query, and it also contains updates information. Experiments were conducted on Text Analysis Conference (TAC) datasets, and Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics were considered to assess the model performance. The results obtained by the proposed approach outperform those from the existing approaches in the scientific literature, obtaining average percentage improvements between 12.74% and 55.03% in the ROUGE scores.

Automatic text summarization is a topic of great interest in many fields of knowledge. Particularly, query-oriented extractive multi-document text summarization methods have increased their importance recently, since they can automatically generate a summary according to a query given by the user. One way to address this problem is by multi-objective optimization approaches. In this paper, a memetic algorithm, specifically a Multi-Objective Shuffled Frog-Leaping Algorithm (MOSFLA) has been developed, implemented, and applied to solve the query-oriented extractive multi-document text summarization problem. Experiments have been conducted with datasets from Text Analysis Conference (TAC), and the obtained results have been evaluated with Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics. The results have shown that the proposed approach has achieved important improvements with respect to the works of scientific literature. Specifically, 25.41%, 7.13%, and 30.22% of percentage improvements in ROUGE-1, ROUGE-2, and ROUGE-SU4 scores have been respectively reached. In addition, MOSFLA has been applied to medicine texts from the Topically Diverse Query Focus Summarization (TD-QFS) dataset as a case study.

Optimization problems are becoming increasingly difficult challenges as a result of the definition of more realistic formulations and the availability of larger input data. Fortunately, the computing capabilities of state-of-the-art heterogeneous systems represent an opportunity to deal with the main complexity factors of these problems. These platforms open the door to the definition of robust metaheuristic solvers, in which parallel computations of different nature can be efficiently mapped to the most suitable architectures and hardware resources. This work investigates the combination of multi-level parallelism and heterogeneous computing to address an important multiobjective problem in bioinformatics: phylogenetics. A parallel metaheuristic approach, based on the joint exploitation of parallel tasks at the algorithm, iteration, and solution levels, is proposed to tackle computationally intensive inferences on CPU+GPU systems. Different heterogeneous design alternatives are also discussed, in accordance with the way the interactions between CPU and GPU are handled. The experimental evaluation of the proposal on real-world biological datasets points out the benefits of using multi-level, heterogeneous strategies, reporting accelerations up to 396× over the baseline metaheuristic as well as significant energy savings with regard to other parallel approaches, without impacting multiobjective solution quality.

The alignment of protein–protein interaction (PPI) networks is in the spotlight of the research in bioinformatics. The main goal is to find structural or functional complexes that are evolutionarily conserved between species. Recent works in the area struggle to produce alignments of both good topological and functional quality, since those two objectives conflict more than expected. To this end, we introduce a decomposition-based multi-objective algorithm with two new problem-aware mutation operators , being each of them focused on the improvement of one of both objectives. The experiments have been performed over 10 scenarios of PPI network alignment with real data from five different species. The results have been evaluated with five quality metrics. The performed experiments have confirmed that the solutions resulting from our proposal obtain statistically significant improvements and are of higher quality than the solutions from related works.

Inter-algorithm cooperative approaches are increasingly gaining interest as a way to boost the search capabilities of evolutionary algorithms (EAs). However, the growing complexity of real-world optimization problems demands new cooperative designs that implement performance-driven strategies to improve the solution quality. This article explores multiobjective cooperation to address an important problem in bioinformatics: the reconstruction of phylogenetic histories from amino acid data. The proposed method is built using representative algorithms from the three main multiobjective design trends: 1) nondominated sorting genetic algorithm II; 2) indicator-based evolutionary algorithm; and 3) multiobjective evolutionary algorithm based on decomposition. The cooperation is supervised by an Elite island component that, along with managing migrations, retrieves multitrend performance feedback from each approach to run additional instantiations of the most satisfying algorithm in each stage of the execution. Experimentation on five real-world problem instances shows the benefits of the proposal to handle complex optimization tasks, in comparison to stand-alone algorithms, standard island models, and other state-of-the-art methods.

Abstract One of the main challenges in synthetic biology lies in maximizing the expression levels of a protein by encoding it with multiple copies of the same gene. This task is often conducted under conflicting evaluation criteria, which motivates the formulation of protein encoding as a multi-objective optimization problem. Recent research reported significant results when adapting the artificial bee colony algorithm to address this problem. However, the length of proteins and the number of copies have a noticeable impact in the computational costs required to attain satisfying solutions. This work is aimed at proposing parallel bioinspired designs to tackle protein encoding in multiprocessor systems, considering different thread orchestration schemes to accelerate the optimization process while preserving the quality of results. Comparisons of solution quality with other approaches under three multi-objective quality metrics show that the proposed parallel method reaches significant quality in the encoded proteins. In addition, experimentation on six real-world proteins gives account of the benefits of applying asynchronous shared-memory schemes, attaining efficiencies of 92.11% in the most difficult stages of the algorithm and mean speedups of 33.28x on a 64-core server-grade system.

The papers in this special section were presented at the Sixth International Conference on Algorithms for Computational Biology, AlCoB 2019, that was held in Berkeley on May 28-30, 2019.

The papers in this special section were presented at the Seventh International Conference on Algorithms for Computational Biology, AlCoB 2020, held in Missoula, Montana on November 8-11, 2021 merged with AlCoB 2021. The conference was organized by the Department of Computer Science at the University of Montana and the Institute for Research Development, Training and Advice - IRDTA, Brussels/London. AlCoB 2020 was the seventh event in a series dedicated to promoting and displaying excellent research using string and graph algorithms and combinatorial optimization to deal with problems in biological sequence analysis, genome rearrangement, phylogeny reconstruction, and structure prediction.

This special section of the IEEE/ACM Transactions on Computational Biology and Bioinformatics presents extended versions of some of the best papers presented at the Fifth International Conference on Algorithms for Computational Biology, AlCoB 2018, held in Hong Kong on June 25-26, 2018. The conference was organized by the Department of Computing of Hong Kong Polytechnic University and the Research Group on Mathematical Linguistics (GRLMC) from Rovira i Virgili University, Tarragona, Spain. AlCoB 2018 was the fifth event in a series dedicated to promoting and displaying excellent research using string and graph algorithms and combinatorial optimization to deal with problems in biological sequence analysis, genome rearrangement, evolutionary trees, and structure prediction. Out of 25 submissions to the conference, 11 papers were accepted (which represents an acceptance rate of 44%). Among them, the authors of three papers were invited to submit to this special section. Each submission was reviewed by three experts and, based on their comments, the guest editors decided to accept two papers for this special section (which represents an acceptance rate of about 8% out of the submissions to the conference).

The papers in this special section were presented at the 3rd International Conference on Algorithms for Computational Biology, AlCoB 2016, that was held in Trujillo, Spain, on June 21- 22, 2016.

RNA inverse folding problem is a bioinformatics problem where the objective is to find an RNA sequence that folds into a given target secondary structure. In this paper, we use evolutionary computation to solve a new and innovative multiobjective definition of this problem. In this new multiobjective definition of the problem, we have considered the similarity between target and predicted structures as a constraint, and three objective functions: 1) partition function (free energy of the ensemble); 2) ensemble diversity; and 3) nucleotides composition. The multiobjective metaheuristic to design RNA sequences (m2dRNAs) proposed in this paper is compared against other RNA inverse folding methods published in the literature, such as RNAinverse, RNA secondary structure designer, inverse folding of RNA, MODENA, NUPACK, fRNAkenstein, dynamics in sequence space optimization, RNAiFOLD, antaRNA, evolutionary RNA design, and Eterna players. After a comprehensive comparative study on two well-known benchmarks (Rfam and Eterna100), we conclude that m2dRNAs is capable of obtaining very promising results in terms of both quality of RNA designs and required runtime. The source code of m2dRNAs is available at http://arco.unex.es/arl/m2dRNAs-source_code.zip.

Parallelism has become a recurrent tool to support computational intelligence and, particularly, evolutionary algorithms in the solution of very complex optimization problems, especially in the multiobjective case. However, the selection of parallel evolutionary designs often represents a difficult question due to the multiple variables that must be considered to attain an accurate exploitation of hardware resources, along with their influence in solution quality. This work looks into this issue by conducting a comparative performance analysis of intra-algorithm parallel multiobjective evolutionary algorithms running on shared-memory configurations. We consider different design trends including A) generational approaches based on measurements of solution quality plus diversity, B) generational approaches based on measurements of solution quality exclusively, and C) non-generational approaches. Following these trends, a total of six representative algorithms are applied to tackle a challenging bioinformatics problem as a case study, phylogenetic reconstruction. Experimentation on real-world scenarios point out the main advantages and weaknesses of each design, outlining guidelines for the selection of methods according to the characteristics of the employed hardware, evolutionary properties, and the parallelism exploitation capabilities of the evaluated approaches.

The multiple sequence alignment is a well-known bioinformatics problem that consists in the alignment of three or more biological sequences (protein or nucleic acid). In the literature, a number of tools have been proposed for dealing with this biological sequence alignment problem, such as progressive methods, consistency-based methods, or iterative methods; among others. These aligners often use a default parameter configuration for all the input sequences to align. However, the default configuration is not always the best choice, the alignment accuracy of the tool may be highly boosted if specific parameter configurations are used, depending on the biological characteristics of the input sequences. In this paper, we propose a characteristic-based framework for multiple sequence aligners. The idea of the framework is, given an input set of unaligned sequences, extract its characteristics and run the aligner with the best parameter configuration found for another set of unaligned sequences with similar characteristics. In order to test the framework, we have used the well-known multiple sequence comparison by log-expectation (MUSCLE) v3.8 aligner with different benchmarks, such as benchmark alignments database v3.0, protein reference alignment benchmark v4.0, and sequence alignment benchmark v1.65. The results shown that the alignment accuracy and conservation of MUSCLE might be greatly improved with the proposed framework, specially in those scenarios with a low percentage of identity. The characteristic-based framework for multiple sequence aligners is freely available for downloading at http://arco.unex.es/arl/fwk-msa/cbf-msa.zip.

Among the different scientific domains where metaheuristics find applicability, bioinformatics represents a particularly challenging field due to the multiple complexity factors involved in the processing of biological data. In this context, the exploration of protein sequence data is remarkably increasing the temporal demands of such biological problems, thus motivating the interest in investigating new approaches that effectively combine bioinspired metaheuristics and parallelism. This paper addresses the reconstruction of ancestral relationships from amino acid sequences by using a multiobjective approach based on the shuffled frog-leaping optimization technique. Due to the inherent parallel nature of this approach, we define different parallel schemes aimed at exploiting the computing capabilities of modern cluster platforms. The experiments performed in five real datasets give account of the relevance of using parallelism-aware metaheuristic designs, as well as the need to consider both parallel performance and solution quality when tackling such difficult optimization scenarios.

The analysis of scientific data, specially in different kinds of cosmological studies, has to deal with the increment in data volume. These studies include the calculation of correlation functions such as the Two-point Three-Dimensional Correlation Function. To get the final estimator value for these functions, it is necessary to construct histograms for storing large number counts. Histograms are a very common way of representing data and summarizing information in science. However, they have a high computational cost, which is worsened by the increase of the standard sample size. This increment leads directly to two problems: first of all, the large processing time and, secondly, the lack of accuracy of the result. Therefore, the implementations of correlation functions need to maintain high accuracy and affordable processing times. In order to reduce the high processing times, GPU computing is being widely used. In this work, the bin-recycling strategy is implemented and evaluated in the Two-Point Three-Dimensional Correlation Function. We show that this implementation outperforms others which also correctly process a large number of galaxies. As a result of this work, an accuracy-aware implementation of the Two-Point Three-Dimensional Correlation Function on GPU is described and evaluated to ensure the correctness of the results.

Summary Soft computing takes advantage of the computational capabilities provided by graphics processing units (GPUs), as it is reflected in the numerous works published every year. However, comparisons among these works are challenging because of their peculiarities. When evaluating evolutionary algorithms on GPUs, the data layout is a commonality for all the cases. In the current work the most promising data layout for a parallel evaluation of evolutionary algorithms on GPU is evaluated. The general scope of this work makes it broadly applicable, being useful for accelerating the fitness calculation of large instances of any population‐based evolutionary algorithm. For optimal performance to be achieved in this evaluation, it should be done through a hardware‐software co‐design approach. The co‐design process might imply a risk of overfitting. Because of this, a trade‐off in the co‐design approach is necessary for long‐term sustainability of the performance of such code. As a consequence of this study, a statement about the most promising data layout for evaluating large instances of population‐based evolutionary algorithms on GPU is presented. From the different approaches studied, the strategy with allocation of 1 individual per thread on registers with coalesced access to global memory on both Fermi and Kepler architectures outperforms all the other strategies.

Summary The availability of heterogeneous CPU+GPU systems has opened the door to new opportunities for the development of parallel solutions to tackle complex biological problems. The reconstruction of evolutionary histories among species represents a grand computational challenge, which can be addressed by exploiting this kind of hardware designs. In this research, we study the application of heterogeneous computing with OpenCL to accelerate one of the most well‐known objective functions for inferring phylogenies, the phylogenetic parsimony function. For this purpose, we undertake the design of CPU and GPU kernel implementations of this relevant function, proposing a heterogeneous CPU+GPU multidevice approach that distributes multiple parsimony evaluations among processing devices. Experiments on 6 real nucleotide data sets and comparisons with other parallel implementations give account of the benefits of the proposal in this paper, obtaining significant parallel results by combining CPU and GPU capabilities in accordance with the characteristics of the input data.

The integration of parallel computing techniques into metaheuristics has traditionally represented a promising approach to tackle computationally demanding optimization problems. In the last years, metaheuristics have evolved by including more complex search mechanisms whose parallelization often leads to performance issues under classic parallel schemes. This work investigates the asynchronous non-generational parallelization model, which is aimed at dealing with performance pitfalls by allowing worker threads to behave as asynchronous independent agents. We incorporate asynchronous principles into a recently proposed metaheuristic for multiobjective optimization, the Indicator-Based Multiobjective Bat Algorithm, and apply the resulting approach to solve a real-world problem in the bioinformatics domain: the reconstruction of evolutionary histories. Experiments on multicore multiprocessor systems comprising up to 64 cores reveal the suitability of the model to address the main challenges of the metaheuristic design under study, outperforming other implementations and methods in terms of parallel performance while also achieving significant solution quality.

The motif discovery problem (MDP) is an important biological optimization problem that has been addressed in numerous ways. However, it is important to note that when we address real complex optimization problems, we should adequately formulate them in order to provide real applicability to the developed techniques. In the particular case of MDP, as we do not know the size of the motifs and the number of repetitions that can be found in the sequences, we must not make any length or pattern-repetition assumptions. In addition, if we consider that it is practically impossible to adequately formulate an optimization problem with a single-objective function formulation, multiobjective optimization can be a good methodology to be considered. In this paper, we propose a novel hybrid multiobjective algorithm for tackling the MDP. Our main objective is to study the results achieved by our algorithm, analysing its performance when different motif occurrence models are considered. As we will see, experimental results on different sets of real instances will point out the advantages and disadvantages of each model, also checking how a more realistic definition of the optimized problem provides better quality biological results.

Over the last 25 years, the multiple sequence alignment (MSA) problem has attracted the attention of biologists because it is one of the major techniques used in several areas of computational biology, such as homology searches, genomic annotation, protein structure prediction, gene regulation networks, or functional genomics. This problem implicates the alignment of more than two biological sequences, and is considered as a nondeterministic polynomial time optimization problem. In this paper, we find a number of different approaches for dealing with this biological sequence alignment problem. Basically, we distinguish six main groups: 1) exact methods; 2) progressive methods; 3) consistency-based methods; 4) iterative methods; 5) evolutionary algorithms; and 6) structure-based methods. In this paper, we propose the use of evolutionary computation and multiobjective optimization for solving this bioinformatics problem. A multiobjective version of a memetic metaheuristic is presented: hybrid multiobjective metaheuristics for MSA. In order to prove the effectiveness of the new proposal, we use three structure-based benchmarks created by using empirical data as input. The results obtained by our method are compared with well-known methods published in this paper, concluding that the new approach presents remarkable accuracy when dealing with sets of sequences with a low sequence similarity, the most frequent ones in real world.

This paper discusses how a mobility model can be used jointly with a mobile activity trace and evolutionary computation to reduce the signaling load related to mobility management, an important and fundamental task in any public land mobile network. For this purpose, a mobility model is used to determine the most probable locations of each mobile subscriber, and this information, in turn, is used to assign paging areas. This paging strategy is evaluated by taking into account different probability thresholds and time-delay constraints, and in a multiobjective way. Thus, we study the whole objective space of the problem, ensure the results that are not dependent on the configuration of registration areas used in the analysis, and take into account the signaling traffic of both paging and location updates (in contrast to other published works, in which only the reduction in the paging load is considered). The feasibility of this paging scheme is evaluated by means of a performance analysis, in which it is compared with other paging schemes widely used in the recent literature. Results show that this paging strategy can reduce the blanket paging load by an average of ~56.73%. Furthermore, the performance analysis also shows that using evolutionary computation jointly with a paging procedure based on a mobility model is a very useful strategy for managing mobility in a public land mobile network, because it allows the total signaling load obtained by blanket paging to be reduced by ~67.03%.

Job scheduling is a challenging task in grid environments and reducing execution time is one of the most important ways to tackle this problem. Nowadays, society is also more conscious about energy saving, making this fact a really important issue to pursue. In this paper, a new multiobjective algorithm is presented based on the small-world phenomenon: Multiobjective Small-World Optimization (MOSWO), to optimize both objectives: energy consumption and execution time. MOSWO is compared with another recent and swarm algorithm based on the firefly's behaviour: Multiobjective Firefly Algorithm (MO-FA). Both algorithms are compared with the standard multiobjective algorithm Non-dominated Sorting Genetic Algorithm II to show their efficiency as multiobjective approaches. Moreover, the best algorithm proposed, MOSWO, is compared with MOHEFT (multiobjective version of one of the most used algorithms in workflow-scheduling, HEFT) and also with two real grid schedulers: Workload Management System and Deadline Budget Constraint. The results show the advantages of our proposal.

In this paper, we propose a parallel multiobjective approach based on the honey bees' behaviour for grooming low-speed traffic requests onto high-capacity optical channels. This problem of grooming low-speed traffic requests is known in the literature as the traffic grooming problem. This problem in mesh optical networks is an NP-hard problem, in which the solution time raises exponentially when the network size increases; therefore, the use of metaheuristics and parallelism jointly is a great option in order to reduce the prohibitive runtime. The parallel approach is implemented for shared-memory architectures by using OpenMP. In our experiments, we have measured the speedup and efficiency of the method with 1, 2, 4, 8 and 16 cores when dealing with three optical networks: small (6-node network, 6 nodes), medium (National Science Foundation, 14 nodes) and large (Nippon Telegraph and Telephone, 55 nodes). Furthermore, we present a comparative study with traditional methods and other multiobjective metaheuristics published in the literature; in which we show the advantages of our multiobjective proposal.

Summary Grid computing is considered a promising trend, which enables the sharing of a wide variety of computational and storage resources geographically distributed. Despite the advantages of such paradigm, several problems have emerged during the last decade; most of them caused by an inefficient utilization of grid resources. The present contribution proposes an approach to improve the grid resources selection process. An optimization model for choosing grid resources in an intelligent way has been designed. A mathematical formulation to monitor the resources efficiency has also been established. Furthermore, the model provides a self‐adaptive capability to grid applications, enhancing them for dealing with the changing environmental conditions. The model applies an artificial intelligence algorithm for ensuring an efficient selection. In particular, three different versions have been implemented. Each of them uses a different algorithm. Finally, during the evaluation phase of the model, the experimental tests were performed in a real grid infrastructure. The results show that the model improves the infrastructure throughput, by increasing the finished tasks rate and by reducing the applications execution time. Copyright © 2014 John Wiley & Sons, Ltd.

Summary Today, in an energy‐aware society, job scheduling is becoming an important task for computer engineers and system analysts that may lead to a performance per Watt trade‐off of computing infrastructures. Thus, new algorithms, and a simulator of computing environments, may help information and communications technology and data center managers to make decisions with a solid experimental basis. There are several simulators that try to address performance and, somehow, estimate energy consumption, but there are none in which the energy model is based on benchmark data that have been countersigned by independent bodies such as the Standard Performance Evaluation Corporation. This is the reason why we have implemented a performance and energy‐aware scheduling (PEAS) simulator for high‐performance computing. Furthermore, to evaluate the simulator, we propose an implementation of the non‐dominated sorting genetic algorithm‐II (NSGA‐II) algorithm, a fast and elitist multiobjective genetic algorithm, for the resource selection. With the help of the PEAS simulator, we have studied if it is possible to provide an intelligent job allocation policy that may be able to save energy and time without compromising performance. The results of our simulations show a great improvement in response time and power consumption. In most of the cases, NSGA‐II performs better than other ‘intelligent’ algorithms like multiobjective heterogeneous earliest finish time and clearly outperforms the first‐fit algorithm. We demonstrate the usefulness of the simulator for this type of studies and conclude that the superior behavior of multiobjective algorithms makes them recommended for use in modern scheduling systems. Copyright © 2015 John Wiley & Sons, Ltd.

Summary The field of computational biology encloses a wide range of optimization problems that show non‐deterministic polynomial‐time hard complexities. Nowadays, phylogeneticians are dealing with a growing amount of biological data that must be analyzed to explain the origins of modern species. Evolutionary relationships among organisms are often described by means of tree‐shaped structures known as phylogenetic trees. When inferring phylogenies, two main challenges must be addressed. First, the inference of reliable evolutionary trees on data sets where different optimality principles support conflicting evolutionary hypotheses. Second, the processing of enormous tree searches spaces where traditional sequential strategies cannot be applied. In this sense, phylogenetic inference can benefit from the combination of high performance computing and evolutionary computation to carry out the reconstruction of complex evolutionary histories in reduced execution times. In this paper, we introduce multiobjective phylogenetics, a hybrid OpenMP/MPI approach to parallelize a well‐known multiobjective metaheuristic, the fast non‐dominated sorting genetic algorithm (NSGA‐II). This algorithm has been designed to conduct phylogenetic analyses on multi‐core clusters in accordance with two principles: maximum parsimony and maximum likelihood. The main goal is to combine the benefits of shared‐memory and distributed‐memory programming paradigms to efficiently infer a set of high‐quality Pareto solutions. Experiments on six real nucleotide data sets and comparisons with other hybrid parallel approaches show that multiobjective phylogenetics is able to achieve significant performance in terms of parallel, multiobjective, and biological results. Copyright © 2014 John Wiley & Sons, Ltd.

Proteins are molecules that form the mass of living beings. These proteins exist in dissociated forms like amino-acids and carry out various biological functions, in fact, almost all body reactions occur with the participation of proteins. This is one of the reasons why the analysis of proteins has become a major issue in biology. In a more concrete way, the identification of conserved patterns in a set of related protein sequences can provide relevant biological information about these protein functions. In this paper, we present a novel algorithm based on teaching learning based optimization (TLBO) combined with a local search function specialized to predict common patterns in sets of protein sequences. This population-based evolutionary algorithm defines a group of individuals (solutions) that enhance their knowledge (quality) by means of different learning stages. Thus, if we correctly adapt it to the biological context of the mentioned problem, we can get an acceptable set of quality solutions. To evaluate the performance of the proposed technique, we have used six instances composed of different related protein sequences obtained from the PROSITE database. As we will see, the designed approach makes good predictions and improves the quality of the solutions found by other well-known biological tools.

The development of efficient parallel algorithms based on mixed mode programming represents one of the most popular lines of research in current bioinformatics. By exploiting hardware resources at inter-node/intra-node level, we can address grand computational challenges which involve the optimization of multiple objective functions simultaneously. In this sense, the inference of evolutionary trees represents one of the most difficult NP-hard problems in the field. Tackling such a problem requires efficient parallel designs to take advantage of the characteristics of modern multicore clusters. In this paper, we aim to solve the phylogenetic inference problem by applying MPI/OpenMP schemes to two multiobjective metaheuristics: fast non-dominated sorting genetic algorithm and multiobjective firefly algorithm. In order to assess the performance achieved by these proposals under different system and problem sizes, we have conducted experiments on six real nucleotide data sets according to a statistical methodology. Our parallel and multiobjective metrics point out the relevance of combining hybrid programming and novel bioinspired designs with regard to other parallel and biological approaches from the literature.

Cosmology is a data intensive field that will become more so in the coming years. In this scenario, GPU-computing is becoming very relevant for analysing large catalogs within a reasonable amount of time. In this work, we investigate the acceleration of the analysis by using a hybrid MPI-CUDA implementation.

Throughout the years, biological processing demands have been addressed by relying on the design of algorithmic approaches for parallel architectures. By taking advantage of multicore processor systems, we can deal with the main sources of complexity which explain the NP-hard nature of multiple problems in computational biology. In this work, we address the inference of phylogenetic topologies by using two multiobjective metaheuristics: Fast Non-Dominated Sorting Genetic Algorithm and Strength Pareto Evolutionary Algorithm 2. The additional complexity introduced by the multiobjective formulation of the problem motivates that parallel designs of these algorithms must be undertaken. For this purpose, OpenMP-based implementations of these two metaheuristics are applied. To evaluate the performance of these approaches, a comparative study has been conducted by performing experimentation on four nucleotide data sets. Our experiments suggest the relevance of these parallel algorithmic designs, improving the phylogenetic results reported by other multiobjective tools in reduced execution times.

SUMMARY Nowadays, it is common to find problems that require recognizing objects in an image, tracking them along time, or recognizing a complete real‐world scene. One of the most known and used algorithms to solve these problems is theSpeeded Up Robust Features (SURF) algorithm.SURFis a fast and robust local, scale and rotation invariant, features detector. This means that it can be used for detecting and describing a set ofpoints of interest(keypoints) from an image. Because of the importance of this algorithm and the rise of the parallelism‐based technologies, in the last years, diverse parallel implementations of SURF have been proposed. These parallel implementations are based on very different techniques: Compute Unified Device Architecture, OpenMp, OpenCL, and so on. In conclusion, we think valuable a comparative study of all of them highlighting the advantages and disadvantages of each parallel implementation. To our best knowledge, this article is the first attempt to do this comparative study. In order to make this study, we have used the standard metrics and image collection in this field, as well as other important metrics in parallelism as speedup and efficiency. Copyright © 2013 John Wiley & Sons, Ltd.

SUMMARY The future of designing optical networks focuses on the wavelength division multiplexing technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of optical fiber. However, when it is required to establish a set of demands, a problem comes up. This problem is known as routing and wavelength assignment problem. In this work, we have tackled the static routing and wavelength assignment problem by using multiobjective evolutionary computing. The algorithm applied is the differential evolution but modified with the Pareto tournaments concept for being adapted to the multiobjective context. By using OpenMP, an application programming interface that supports multiplatform shared memory multiprocessing programming, we have demonstrated that this algorithm is highly suitable to be parallelized. We have performed several experiments in multicore systems with two, four, and eight cores, obtaining 97.57% of mean efficiency. To ensure that our heuristic obtains relevant results, we have compared it with a parallel version of the standard fast nondominated sorting genetic algorithm. Finally, in order to show the goodness and effectiveness of the differential evolution with Pareto tournaments algorithm when dealing with this problem, we present diverse multiobjective comparisons with the nondominated sorting genetic algorithm and other approaches published in the literature. Copyright © 2013 John Wiley & Sons, Ltd.

At this time, Wireless Sensor Networks (WSNs) are widely used in many fields. This kind of network has some attractive features that have promoted their use, such as the absence of wires and the use of low-cost devices. However, WSNs also have important shortcomings that affect some features like energy cost and quality of service. In this paper, we optimize traditional static WSNs (a set of sensors and a sink node) by means of adding routers to simultaneously optimize a couple of important factors: energy consumption and average coverage. This multiobjective optimization problem was solved in a previous work using two genetic algorithms (NSGA-II and SPEA2) which had an important limitation: the computing time was very high and then, to address complex instances was difficult. In this paper, both algorithms are parallelized using OpenMP in order to reduce the computing time, and a more realistic data set is included. The results obtained are analyzed in depth from both multiobjective and parallel viewpoints. A Quite good efficiency is obtained with a wide range of processing cores, observing that NSGA-II provides the best results in small and medium instances, but in the largest ones the behavior of both algorithms is similar.

Optical networks have attracted much more attention in the last decades due to its huge bandwidth (Tbps). The Wavelength Division Multiplexing (WDM) is a technology that aims to make the most of this networks by dividing each single fiber link into several wavelengths of light or channels. Each channel operates in the range of Gbps; unfortunately, the requirements of the vast majority of current traffic connection requests are a few Mbps, causing a waste of bandwidth at each channel. We can solve this drawback by equipping each optical node with an access station for multiplexing or grooming several low-speed requests onto one single high-speed channel. This problem of grooming low-speed requests is known in the literature as the Traffic Grooming problem. In this work, we formulate the Traffic Grooming problem as a Multiobjective Optimization Problem, optimizing simultaneously the total throughput, the number of transceivers used, and the average propagation delay. We propose the use of the Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D). The experiments are conducted on three optical network topologies and diverse scenarios. The results report that the MOEA/D algorithm works more efficiently than other multiobjective approaches and other single-objective heuristics published in the literature.

A cis-regulatory element is a non-coding DNA sequence in or near a gene required for its expression, often containing transcription factors binding sites (TFBS). Identifying new TFBSs is fundamental to understand the regulation process of these genes. The optimization problem responsible for these findings is the Motif Discovery Problem (MDP), which is formulated as a short DNA pattern discovery problem. In addition, the MDP is an NP-hard optimization problem since it has to find short strings mixed among a large amount of biological information. In this paper, we propose and study a new hybrid multiobjective evolutionary algorithm based on Differential Evolution (DE) named Hybrid Differential Evolution with Pareto Tournaments (H-DEPT). To demonstrate the superiority of our proposed algorithm on a biological level, we compare the predictions made with those predicted by MEME, BioProspector and BioOptimizer when solving a set of four real sequence datasets. Finally, by using OpenMP, we also demonstrate that this algorithm is highly suitable to be parallelized. As we will see, we have performed several experiments with multi-core systems of 2, 4, and 8 cores; obtaining good parallel results.

Phylogenetic inference is one of the most challenging problems in Computational Biology. As recent research lines aim to introduce multiobjective optimization techniques to resolve incongruences in Phylogenetics, parallel multiobjective metaheuristics can be useful to address the computational complexity required to perform phylogenetic analyses according to multiple criteria simultaneously. In this work, we propose several master-worker hybrid approaches based on MPI and OpenMP to parallelize a multiobjective algorithm inspired by the behaviour of fireflies for inferring phylogenies on multicore cluster architectures. Experiments on four real biological data sets suggest that this algorithm can achieve significant speedup and efficiency values by using a proper hybrid model designed to exploit parallelism at the inference and assessment levels.

Currently, wavelength division multiplexing technology is widely used for exploiting the huge bandwidth of optical networks. It allows simultaneous transmission of traffic on many nonoverlapping channels (wavelengths). These channels support traffic demands in the gigabits per second (Gb/s) range; however, since the majority of devices or applications only require a bandwidth of megabits per second (Mb/s), this is a waste of bandwidth. This problem is efficiently solved by multiplexing a number of low-speed traffic demands (Mb/s) onto a high-speed wavelength channel (Gb/s). This is known as the traffic grooming problem. Since traffic grooming is an NP-hard problem, in this paper, we propose two novel multiobjective evolutionary algorithms for solving it. The selected algorithms are multiobjective variants of the standard differential evolution (DEPT) and variable neighborhood search. With the aim of ensuring the performance of our proposals, we have made comparisons with the well-known fast Nondominated Sort Genetic Algorithm (NSGA-II), Strength Pareto Evolutionary Algorithm 2, and other approaches published in the literature. After performing diverse comparisons, we can conclude that our novel approaches obtain promising results, highlighting in particular the performance of the DEPT algorithm.

User group key management is a critical task in secure multicast applications of multimedia contents, such as, the Internet TV, pay per view, satellite TV, etc. These keys must be recalculated, encrypted and redistributed when a user is joined or disjoined to a specific group in order to avoid that users which do not belong to a concrete group can access to the contents of that group. This paper presents a high performance dual MicroBlaze System on Chip (SoC) to perform this management as far as possible. This platform aims to reduce the influence of a user join or disjoin in the reception of the multimedia contents by the rest of users.

Scientists often have constraints from their experiments such as deadlines and budgets. For that reason, Job scheduling problem in Grid environments is not only important but also a challenging task. Both requirements - execution time and cost - are conflictive each other because faster resources usually involve higher costs. In this research, we compare two novel multiobjective algorithms from different fields - Complex Networks and Swarm approach - in an attempt to tackle the complex distributed infrastructure of Grid computing. On one hand, Multiobjective Small-World Optimization (MOSWO) is a multiobjective adaptation from algorithms based on the Small-World phenomenon, which is characteristic of complex scale-free networks. On the other hand, a novel swarm algorithm is the Multiobjective Gravitational Search Algorithm (MOGSA) inspired on gravitational attraction. Although both algorithms render good performance, MOGSA dominates in all the cases. Moreover, MOGSA attains improved performance with real schedulers such as the Workload Management System (WMS) from the most used European middleware gLite and the well-known Deadline Budget Constraint (DBC) algorithm from Nimrod-G.

A wide variety of optimization problems requires the combination of Bioinspired and Parallel Computing to address the complexity needed to get optimal solutions in reduced times. The multicore era allows the researcher to exploit modern arqitectures to resolve these NP-Hard problems. Inferring phylogenetic trees which describe a hypothesis of the evolution of species is a well-known example of this kind of problems. As the space of possible tree topologies increases exponentially with the number of species, exhaustive searches cannot be applied. Also, additional difficulties arise when we must consider simultaneously multiple optimality measures to resolve the problem. In this paper, we report a performance study on multicore machines of a parallel multiobjective adaptation of the Artificial Bee Colony algorithm for inferring phylogenies according to the maximum parsimony and maximum likelihood criteria. Experimental results reveal that our proposal can improve other approaches based on advanced High Performance Computing techniques on large data sets.

Bioinformatics and computational biology include researchers from many areas: biochemists, physicists, mathematicians, and engineers. The scale of the problems that are discussed ranges from small molecules to complex systems, where many organisms coexist. However, among all these issues, we can highlight genomics, which studies the genomes of microorganisms, plants, and animals. Predicting common patterns, i.e., motifs, in a set of deoxyribonucleic acid (DNA) sequences is one of the important sequence analysis problems, and it has not yet been resolved in an efficient manner. In this study, we study the application of evolutionary multiobjective optimization to solve the motif discovery problem, applied to the specific task of discovering novel transcription factor binding sites in DNA sequences. For this, we have designed, adapted, configured, and evaluated several types of multiobjective metaheuristics. After a detailed study, the results indicate that these metaheuristics are appropriate for discovering motifs. To find good approximations to the Pareto front, we use the hypervolume indicator, which has been successfully integrated into evolutionary algorithms. Besides the hypervolume indicator, we also use the coverage relation to ensure: Which is the best Pareto front? New results have been obtained, which significantly improve those published in previous research works.

The future of designing optical networks is focused on the wavelength division multiplexing (WDM) technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of fiber. However, when it is necessary to establish a set of demands, a problem comes up. This problem is known as a routing and wavelength assignment (RWA) problem. Depending on the traffic pattern, two varieties of a RWA problem have been considered in the literature: static and dynamic. In this paper, we present a comparative study among three multiobjective evolutionary algorithms (MOEAs) based on swarm intelligence to solve the RWA problem in real-world optical networks. Artificial bee colony (ABC) algorithm, gravitational search algorithm (GSA), and firefly algorithm (FA) are the selected evolutionary algorithms, but are adapted to multiobjective domain (MO-ABC, MO-GSA, and MO-FA, respectively). In order to prove the goodness of the swarm proposals, we have compared them with a standard MOEA: fast nondominated sorting genetic algorithm. Finally, we present a comparison among the metaheuristics based on swarm intelligence and several techniques published in the literature, coming to the conclusion that swarm intelligence is very suitable to solve the RWA problem, and presumably that it may obtain such quality results not only in diverse telecommunication optimization problems, but also in other engineering optimization problems.

Often, solutions to complex problems are found in nature. Swarm algorithms are capable of solving such complex problems by implementing patterns from nature. This patterns are found in a variety of scientific fields. In this paper, we discuss two swarm algorithms extracted from Biology and Physics, namely: Multiobjective Artificial Bee Colony (MOABC) and Multiobjective Gravitational Search Algorithm (MOGSA). The first one is based on bees behavior and the other follows the gravity between masses. These algorithms are implemented to solve the grid scheduling problem. Optimization of job scheduling is one of the most challenging tasks in Grid environments because it severely affects the execution time of an experiment (set of jobs). Experiments often are tied up to fulfill deadlines and budgets. One of the main contributions of this work is adding multiobjective processes to these swarm algorithms to minimize those conflictive objectives. Results show that MOABC clearly improves the MOGSA approach when solving the problem. MOABC is also compared with real grid meta-schedulers as Deadline Budget Constraint (DBC) and Workload Management System (WMS) by using the simulator GridSim to prove the improvement that offers this new algorithm.

WiMAX (Worldwide Interoperability for Microwave Access) or IEEE 802.16 is a technology developed to provide greater bandwidth and coverage. One of the most important challenges in wireless deploying network is the Base Stations (BS) location to meet traffic and coverage requirements efficiently. In this paper we are using a particularized swarm intelligence algorithm based on collective behavior of honey bees to find good solutions. In order to minimize the interference among cells and reduce energy consumption, we apply a post-processing to obtain power control and sectorization. Simulations results show that our method provides more efficient and better solutions than those are obtained by other evolutionary algorithms in the same instances.

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, where the total budget and human resources involved in software development must be managed optimally 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 and multi-objective metaheuristics have been used to solve the problem in the past. Nowadays, software projects faced by the large companies are increasing in size and we need algorithms that are able to deal with the new large instances of the SPS problem. In this paper we analyze the scalability of four multi-objective algorithms when they are applied to the SPS problem using instances of increasing size. The algorithms are a genetic algorithm (NSGA-II), an evolution strategy (PAES), a differential evolution (DEPT) and a firefly algorithm (MO-FA). The results suggest that PAES is the algorithm with the best scalability behaviour.

Recently, there have been several developments in the scientific community to model and solve complex optimization problems by employing natural metaphors. In some cases, due to their distributed schema, these algorithms can be adapted to distributed computing environments. A distributed and asynchronous bees (DAB) grid-based approach is here used to optimise the magnetic configuration in order to reduce the neoclassical transport of particles in a nuclear fusion device. Large-scale problems (as several plasma physics can be classified) present open challenges that need a large computing capacity to be solved. Thus, the use of large distributed infrastructures is mandatory in many of these problems. The use of grid computing offers a new paradigm where the distributed nature of foraging can be reproduced and applied to complex optimisation problems.

This paper focuses on solving large size optimization problems using GPGPU. Evolutionary Algorithms for solving these optimization problems suffer from the curse of dimensionality, which implies that their performance deteriorates as quickly as the dimensionality of the search space increases. This difficulty makes very challenging the performance studies for very high dimensional problems. Furthermore, these studies deal with a limited time-budget. The availability of low cost powerful parallel graphics cards has stimulated the implementation of diverse algorithms on Graphics Processing Units (GPU). In this paper, the design of a GPGPU-based Parallel Particle Swarm Algorithm, to tackle this type of problem maintaining a limited execution time budget, is described. This implementation profits of an efficient mapping of the data elements (swarm of very high dimensional particles) to the parallel processing elements of the GPU. In this problem, the fitness evaluation is the most CPU-costly routine, and therefore the main candidate to be implemented on GPU. As main conclusion, the speed-up curve versus the increase in dimensionality is shown. This curve indicates an asymptotic limit stemmed from the data-parallel mapping.

The last few years have seen a significant growth in communication networks. With the growth of data traffic, network operators seek network-engineering tools to extract the maximum benefits out of the existing infrastructure. This has suggested a number of new optimisation problems, most of them in the field of combinatorial optimisation. We address here the Terminal Assignment problem. The main objective is to assign a collection of terminals to a collection of concentrators. In this paper, we propose a Hybrid Scatter Search (HSS) algorithm to assign terminals to concentrators. Coupled with the Scatter Search algorithm we use a Tabu Search algorithm to locate the global minimum. We show that HSS is able to achieve feasible solutions to Terminal Assignment instances, improving the results obtained by previous approaches.

This paper proposes the use of Differential Evolution with Pareto Tournaments (DEPT) to identify common patterns, motifs, in biological sequences. The work is motivated by two fundamental facts: first, the role that bioinformatics problems are taking in computer engineering in recent years, and second, the limited existence of scientific papers that use evolutionary techniques for solving such problems. Although finding motifs in deoxyribonucleic acid (DNA) sequences is one of the classical sequence analysis problems, it has not yet been resolved in an efficient manner. Using evolutionary algorithms we can get nearly optimal solutions in a reasonable time. The Motif Discovery Problem (MDP) aims to maximize conflicting objectives: support, motif length, and similarity. These objectives imply multiobjective optimization (MOO) to obtain motifs in the most efficient way as possible. Moreover, in this work, we incorporate the hypervolume indicator to measure the quality of the solutions to this problem. As we will see, our results surpass the results obtained by other approaches proposed in the literature.

The technology based on Wavelength Division Multiplexing (WDM) applied to optical networks has resolved the bandwidth waste in this kind of networks. WDM divides the bandwidth of an optical fiber in different wavelengths that can be used by electronic devices to send and receive data without bottlenecks. Another problem appears when the necessity of choice of the path and the wavelengths to interconnect a set of source-destination pairs comes up. This problem is known as Routing and Wavelength Assignment (RWA) and there are two types, depending on the demands: Static-RWA and Dynamic-RWA. In this paper we present a multiobjective evolutionary algorithm to solve this problem. We choose the Differential Evolution (DE), incorporating the concept of Pareto Tournament (DEPT). To determine the parameters of the algorithm, we used two real different topologies (the first is a topology from USA, NSF network; and the second is a topology from Japan, NTT network) and six sets of source-destination pairs for each topology, that is, a total of twelve instances. After all experiments, we can conclude that with this multiobjective evolutionary algorithm, we have obtained better results than the other approaches published in the literature.

Despite of being a very common task in bioinformatics, multiple sequence alignment is not a trivial matter. Arranging a set of molecular sequences to reveal their similarities and their differences is often hardened by the complexity and the size of the search space involved, which undermine the approaches that try to explore exhaustively the solution's search space. Due to its nature, Genetic Algorithms, which are prone for general combinatorial problems optimization in large and complex search spaces, emerge as serious candidates to tackle with the multiple sequence alignment problem. We have developed an evolutionary approach, AlineaGA, which uses a Genetic Algorithm with local search optimization embedded on its mutation operators for performing multiple sequence alignment. Now, we have enhanced its selection method by employing an elitist strategy, and we have also developed a new crossover operator. These transformations allow AlineaGA to improve its robustness and to obtain better fit solutions. Also, we have studied the effect of the mutation probability in solutions' evolution by analyzing the performance of the whole population throughout generations. We conclude that increasing the mutation probability leads to better solutions in fewer generations and that the mutation operators have a dramatic effect in this particular domain.

Artificial Bee Colony (ABC) algorithm is an optimisation algorithm based on the intelligent behaviour of honey bee swarm. In this work, ABC algorithm is used to optimise the equilibrium of confined plasma in a nuclear fusion device. Plasma physics research for fusion still presents open problems that need a large computing capacity to be solved. This optimisation process is a long time consuming process so an environment like grid computing has to be used, thus the first step is to adapt and extend the ABC algorithm to use the grid capabilities. In this work we present a modification of the original ABC algorithm, its adaption to a grid computing environment and the application of this algorithm to the equilibrium optimisation process.

Abstract Plasma physics research for fusion still presents open problems that need a large computing capacity to be solved. Different modelling tools can be used to carry out simulations that will lead to saving costs in the development of fusion devices. The use of evolutionary algorithms (EAs) to look for approximate configurations offers a great approach for optimization processes, and avoids the use of brute force algorithms. However, since these applications require a high computational cost to perform their operations, the use of the grid arises as an ideal environment to carry out these tests. The distributed paradigm of the grid, as well as the number of computational resources, represents an excellent alternative to execute these tools. In this work we join these three ideas and present promising results. Copyright © 2009 John Wiley & Sons, Ltd.

This paper presents a new approach based on the Scatter Search (SS) algorithm applied to the Location Management problem using the Location Area (LA) scheme. The LA scheme is used to achieve the best configuration of the network partitioning, into groups of cells (location areas), that minimizes the costs involved. In this work we execute five distinct experiments with the aim of setting the best values for the Scatter Search parameters, using test networks generated with realistic data [1]. We also want to compare the results obtained by this new approach with those achieved through classical strategies, other algorithms from our previous work and also by other authors. The simulation results show that this SS based approach is very encouraging.

Searching for the best possible alignment for a set of sequences is not an easy task, mainly because of the size and complexity of the search space involved. Genetic algorithms are predisposed for optimizing general combinatorial problems in large and complex search spaces. We have designed a Genetic Algorithm for this purpose, AlineaGA, which introduced new mutation operators with local search optimization. Now we present the contribution that these new operators bring to this field, comparing them with similar versions present in the literature that do not use local search mechanisms. For this purpose, we have tested different configurations of mutation operators in eight BAliBASE alignments, taking conclusions regarding population evolution and quality of the final results. We conclude that the new operators represent an improvement in this area, and that their combined use with mutation operators that do not use optimization strategies, can help the algorithm to reach quality solutions.

The particle swarm optimisation concept is an evolutionary computation technique employed to find optimal solutions in problems with immense solution space. In this article, an application of particle swarm optimisation technique to the survey of the conjecture of Bateman is presented. The conjecture of Bateman requests how many coincidences of sums of powers of prime numbers are. Up today, only one coincidence has been proved. Neither previous exploration of the conjecture has been published in the scientific literature, nor analytical demonstration has proved the existence of a finite or infinite number of coincidences. In a previous and systematic exploration, not new coincidences have appeared. Unfortunately, the size of the Conjecture makes impossible to go on this brute-force and systematic survey. In order to support the exploration, a gLite grid computing infrastructure has been used, providing seamless access to computational resources.

In the last few years we have seen a significant growth in Synchronous Optical Network (SONET) deployments in telecommunication service providers. With growth of data traffic, network operators seek network-engineering tools to extract the maximum benefits out of the existing infrastructure. This has suggested a number of new optimization problems, most of them in the field of combinatorial optimization. We address here the Weighted Ring Edge-Loading Problem (WRELP). The WRELP is an important optimization problem arising in a popular ring topology for communication networks - given a set of nodes connected along a bi-directional SONET ring, the objective is to minimize the maximum load on the edges (pairwise) of a ring. Our procedure includes some original features, including the application of Hybrid Differential Evolution. We also perform comparisons with standard Differential Evolution, Genetic Algorithm and Tabu Search.

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 present a Grid implementation of a FPGA optimization tool. The application is based on a Distributed Genetic Algorithm (DGA). It solves the placement and routing problem into the FPGA design cycle. The Grid infrastructure is based both on gLite middleware and GridWay metascheduler. The DGA’s different islands are sent to the Working Nodes (WN), where they evolve as remote jobs. We implemented a migration system between islands based on centralizing the exchanging data on a local node. Parting from this data, the local node builds new islands and the evolution continues until the stop criterion is reached. Obtained results show us that the main benefit of the distributed model is a large reduction of the execution time. By using the distributed platform users can launch more complex tasks and increase the number of experiments comparing with sequential execution, expending less amounts of time and effort.

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.

Fusion energy is the next generation of energy. The devices that scientists are using to carry out their researches need more energy than they produce, because many problems are presented in fusion devices. In magnetic confinement devices, one of these problems is the transport of particles in the confined plasma. Some modeling tools can be used to improve the transport levels, but the computational cost of these tools and the number of different configurations to simulate make impossible to perform the required test to obtain good designs. But with grid computing we have the computational resources needed for running the required number of tests and with genetic algorithms we can look for a good result without exploring all the solution space.

Frequency planning (also known as frequency assignment problem -FAP-) is a very important task for current GSM operators. The problem consists in trying to minimize the number of interferences caused when a limited number of frequencies has to be assigned to a quite high number of transceivers. In this work we focus on solving this problem for a realistic-sized, real-world GSM network using a parallelized version of the PBIL (population-based incremental learning) algorithm. Therefore, we have parallelized the PBIL algorithm fixed to the FAP problem using cluster computing. The analysis of the results proves that we have reached a double goal: on the one hand, with the parallelized version of the algorithm, its execution time is reduced down to the optimum values; and on the other hand, we prove that using a distributed island model applied to PBIL, the results for the network-planning are better than the ones obtained with the sequential version.

Fusion energy is the next generation of energy. Plasma confinement is part of the program to develop fusion energy, so many investigations have been performed on it. Grid computing is currently focused on scientific problems like fusion energy or climate. Using grid computing many of these problems, with high computational costs, can be simulated and optimized before implementing special devices. High number of tests can be performed using grid computing in the same time that a single test on a single machine, so researchers can obtain better results in less time than using traditional techniques. In this paper, we present our first steps in grid computing applied into fusion energy, being the starting point to analyse and optimize the configuration of a device for plasma confinement based on the transport inside the device. Finally we propose some goals to use the current work in future investigations.

In this paper we present a Differential Evolution based algorithm used to solve the Radio Network Design (RND) problem. This problem consists in determining the optimal locations for base station transmitters in order to get a maximum coverage area with a minimum number of transmitters. Because of the very high amount of possible solutions, this problem is suitable to be tackled with evolutionary techniques, so in our work it has been developed an algorithm inspired on the well-known Differential Evolution algorithm, obtaining good results.

In this work we present a system for implementing the placement and routing stages in the FPGA cycle of design, into the physical design stage. We start with the ISCAS benchmarks, on EDIF format, of Boolean functions to be implemented. They are processed by a parser in order to obtain an internal representation which is able to be processed by a genetic algorithm (GA) tool. This tool develops the placement and routing tasks, considering possible restricted area into the FPGA. In order to help to the GA to make the routing stage we have added a local search procedure. That local search gets a path between two points without considering neither their placement nor the restricted areas among them. The GA is fully customizable, featuring the ability to work with one or several islands. The experiments have verified that using distributing execution improves the costs and speeds up the convergence towards better results in smaller slots of time.

In this paper we study the use of FPGAs as part of an industrial inspection system. More exactly, to evaluate the cork stopper quality applying real-time image processing. Our system uses the HOT2-XL PCI board, a hardware module library implementing some of the most common operations for image processing, and a Visual C++ application in order to validate the hardware designs and manage the platform. Also, we propose an algorithm for obtaining different features of cork stopper defects, so allowing their classification. Finally, the practical results obtained with this algorithm are presented along with the conclusions and future work.