The application of semantic technologies, particularly ontologies, in the realm of multi-objective evolutionary algorithms is overlook despite their effectiveness in knowledge representation. In this paper, we introduce MOODY, an ontology specifically tailored to formalize these kinds of algorithms, encompassing their respective parameters, and multi-objective optimization problems based on a characterization of their search space landscapes. MOODY is designed to be particularly applicable in automatic algorithm configuration, which involves the search of the parameters of an optimization algorithm to optimize its performance. In this context, we observe a notable absence of standardized components, parameters, and related considerations, such as problem characteristics and algorithm configurations. This lack of standardization introduces difficulties in the selection of valid component combinations and in the re-use of algorithmic configurations between different algorithm implementations. MOODY offers a means to infuse semantic annotations into the configurations found by automatic tools, enabling efficient querying of the results and seamless integration across diverse sources through their incorporation into a knowledge graph. We validate our proposal by presenting four case studies.

Modern applications of Big Data are transcending from being scalable solutions of data processing and analysis, to now provide advanced functionalities with the ability to exploit and understand the underpinning knowledge. This change is promoting the development of tools in the intersection of data processing, data analysis, knowledge extraction and management. In this paper, we propose TITAN, a software platform for managing all the life cycle of science workflows from deployment to execution in the context of Big Data applications. This platform is characterised by a design and operation mode driven by semantics at different levels: data sources, problem domain and workflow components. The proposed platform is developed upon an ontological framework of meta-data consistently managing processes and models and taking advantage of domain knowledge. TITAN comprises a well-grounded stack of Big Data technologies including Apache Kafka for inter-component communication, Apache Avro for data serialisation and Apache Spark for data analytics. A series of use cases are conducted for validation, which comprises workflow composition and semantic meta-data management in academic and real-world fields of human activity recognition and land use monitoring from satellite images.

Many Pareto-based multiobjective evolutionary algorithms require ranking the solutions of the population in each iteration according to the dominance principle, which can become a costly operation particularly in the case of dealing with many-objective optimization problems. In this article, we present a new efficient algorithm for computing the nondominated sorting procedure, called merge nondominated sorting (MNDS), which has a best computational complexity of$O(N\log N)$and a worst computational complexity of$O(MN^{2})$, with$N$being the population size and$M$being the number of objectives. Our approach is based on the computation of thedominance set, that is, for each solution, the set of solutions that dominate it, by taking advantage of the characteristics of the merge sort algorithm. We compare MNDS against six well-known techniques that can be considered as the state-of-the-art. The results indicate that the MNDS algorithm outperforms the other techniques in terms of the number of comparisons as well as the total running time.

MOTIVATION: Multiple sequence alignment (MSA) consists of finding the optimal alignment of three or more biological sequences to identify highly conserved regions that may be the result of similarities and relationships between the sequences. MSA is an optimization problem with NP-hard complexity (non-deterministic polynomial-time hardness), because the time needed to find optimal alignments raises exponentially along with the number of sequences and their length. Furthermore, the problem becomes multiobjective when more than one score is considered to assess the quality of an alignment, such as maximizing the percentage of totally conserved columns and minimizing the number of gaps. Our motivation is to provide a Python tool for solving MSA problems using evolutionary algorithms, a nonexact stochastic optimization approach that has proven to be effective to solve multiobjective problems. RESULTS: The software tool we have developed, called Sequoya, is written in the Python programming language, which offers a broad set of libraries for data analysis, visualization and parallelism. Thus, Sequoya offers a graphical tool to visualize the progress of the optimization in real time, the ability to guide the search toward a preferred region in run-time, parallel support to distribute the computation among nodes in a distributed computing system, and a graphical component to assist in the analysis of the solutions found at the end of the optimization. AVAILABILITY AND IMPLEMENTATION: Sequoya can be freely obtained from the Python Package Index (pip) or, alternatively, it can be downloaded from Github at https://github.com/benhid/Sequoya. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Multiple sequence alignment (MSA) is an NP-complete optimization problem found in computational biology, where the time complexity of finding an optimal alignment raises exponentially along with the number of sequences and their lengths. Additionally, to assess the quality of a MSA, a number of objectives can be taken into account, such as maximizing the sum-of-pairs, maximizing the totally conserved columns, minimizing the number of gaps, or maximizing structural information based scores such as STRIKE. An approach to deal with MSA problems is to use multi-objective metaheuristics, which are non-exact stochastic optimization methods that can produce high quality solutions to complex problems having two or more objectives to be optimized at the same time. Our motivation is to provide a multi-objective metaheuristic for MSA that can run in parallel taking advantage of multi-core-based computers. RESULTS: The software tool we propose, called M2Align (Multi-objective Multiple Sequence Alignment), is a parallel and more efficient version of the three-objective optimizer for sequence alignments MO-SAStrE, able of reducing the algorithm computing time by exploiting the computing capabilities of common multi-core CPU clusters. Our performance evaluation over datasets of the benchmark BAliBASE (v3.0) shows that significant time reductions can be achieved by using up to 20 cores. Even in sequential executions, M2Align is faster than MO-SAStrE, thanks to the encoding method used for the alignments. AVAILABILITY AND IMPLEMENTATION: M2Align is an open source project hosted in GitHub, where the source code and sample datasets can be freely obtained: https://github.com/KhaosResearch/M2Align. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Multiple sequence alignment (MSA) plays a core role in most bioinformatics studies and provides a framework for the analysis of evolution in biological systems. The MSA problem consists in finding an optimal alignment of three or more sequences of nucleotides or amino acids. Different scores have been defined to assess the quality of MSA solutions, so the problem can be formulated as a multiobjective optimization problem. The number of proposals focused on this approach in the literature is scarce, and most of the works take as base algorithm the NSGA-II metaheuristic. So, there is a lack of a study involving a set of representative multiobjective metaheuristics to deal with this complex problem. Our main goal in this paper is to carry out such study. We propose a biobjective formulation for the MSA and perform an exhaustive comparative study of six multiobjective algorithms. We have considered a number of problems taken from the benchmark BAliBASE (v3.0). Our experiments reveal that the classic NSGA-II algorithm and MOCell, a cellular metaheuristic, provide the best overall performance.

The design of bar structures in civil engineering is a complex problem when dealing with real-world structures. An approach to deal with these problems is to apply metaheuristics, which are stochastic methods based on iteratively producing and evaluating tentative solutions. In particular, we focus on multi-objective metaheuristics, as we consider two goals to be minimized: the weight and the deflection of the structure. When applying these techniques to real-world problems, running a metaheuristic for several thousands of evaluations may require many days on a single processor. In this paper, we develop distributed master/slave versions of four multi-objective metaheuristics that are representative of the state-of-the-art and apply them to optimize the design of two instances of a cable-strayed bridge. Our study reveals that our parallel proposals are able to effectively use up to 450 cores, providing accurate solutions in a short time.

MOTIVATION: Molecular docking is a method for structure-based drug design and structural molecular biology, which attempts to predict the position and orientation of a small molecule (ligand) in relation to a protein (receptor) to produce a stable complex with a minimum binding energy. One of the most widely used software packages for this purpose is AutoDock, which incorporates three metaheuristic techniques. We propose the integration of AutoDock with jMetalCpp, an optimization framework, thereby providing both single- and multi-objective algorithms that can be used to effectively solve docking problems. RESULTS: The resulting combination of AutoDock + jMetalCpp allows users of the former to easily use the metaheuristics provided by the latter. In this way, biologists have at their disposal a richer set of optimization techniques than those already provided in AutoDock. Moreover, designers of metaheuristic techniques can use molecular docking for case studies, which can lead to more efficient algorithms oriented to solving the target problems. AVAILABILITY AND IMPLEMENTATION: jMetalCpp software adapted to AutoDock is freely available as a C++ source code at http://khaos.uma.es/AutodockjMetal/.

Algorithms based on the Particle Swarm Optimization (PSO) scheme have become popular to solve both single- and multi-objective optimization problems. In this paper, we focus on SMPSO, a PSO designed to cope with this second group of problems. Taking it as our starting point, we analyze different leader selection schemes, which give rise to four new variants of SMPSO. These new versions, along with the original algorithm, are compared using a benchmark composed of 21 problems. Our study reveals that SMPSOhv, a variant that uses the hypervolume indicator to guide leader selection, is the best performing algorithm in our comparison, outperforming also the original version of SMPSO. To further assess the performance of SMPSOhv, we compare it against NSGA-II and SMS-EMOA, achieving again the best overall results in this new comparative study. Based on these observations, we conclude that the use of the hypervolume for leader selection is a promising approach for multi-objective PSO algorithms.

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

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

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

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

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

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.

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

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

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

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