Skip to main content
Top

2018 | Book

Bioinspired Optimization Methods and Their Applications

8th International Conference, BIOMA 2018, Paris, France, May 16-18, 2018, Proceedings

insite
SEARCH

About this book

This book constitutes the thoroughly refereed revised selected papers of the 10th International Conference on Bioinspired Optimization Models and Their Applications, BIOMA 2018, held in Paris, France, in May 2018.
The 27 revised full papers were selected from 53 submissions and present papers in all aspects of bioinspired optimization research such as new algorithmic developments, high-impact applications, new research challenges, theoretical contributions, implementation issues, and experimental studies.

Table of Contents

Frontmatter
Optimization of Home Care Visits Schedule by Genetic Algorithm
Abstract
Currently, it has been verified that population is increasingly aged and it is necessary to perform home services. These services include home care visits to patients with impossibility of travel to healthcare centers, where the health professionals perform the medical treatments. Usually, this home care services are performed by nurses that need transportation for this purpose. Therefore, it is necessary to make a schedule of these home care visits that, usually, is made manually by the healthcare center. This work aims to carry out an automatic schedule of home care visits of the healthcare Center of Bragança, Portugal, in order to reduce the travel costs and optimize the time spent on trips. The Genetic Algorithm was used to solve this problem. In this paper it is presented the schedule of home care visits for three days of the healthcare center.
Filipe Alves, Ana I. Pereira, Adília Fernandes, Paulo Leitão
New Techniques for Inferring L-systems Using Genetic Algorithm
Abstract
Lindenmayer systems (L-systems) are a formal grammar system that iteratively rewrites all symbols of a string, in parallel. When visualized with a graphical interpretation, the images have been particularly successful as a concise method for simulating plants. Creating L-systems to simulate a given plant manually by experts is limited by the availability of experts and time. This paper introduces the Plant Model Inference Tool (PMIT) that infers deterministic context-free L-systems from an initial sequence of strings generated by the system using a genetic algorithm. PMIT is able to infer more complex systems than existing approaches. Indeed, while existing approaches can infer D0L-Systems where the sum of production successors is 20, PMIT can infer those where the sum is 140. This was validated using a testbed of 28 known D0L-system models, in addition to models created artificially by bootstrapping larger models.
Jason Bernard, Ian McQuillan
An Adaptive Metaheuristic for Unconstrained Multimodal Numerical Optimization
Abstract
The purpose of this paper is to show an adaptive metaheuristic based on GA, DE, and PSO. The choice of which one will be used is made based on a probability that is uniform at the beginning of the execution, and it is updated as the algorithm evolves. That algorithm producing better results tend to present higher probabilities of being selected. The metaheuristic has been tested in four multimodal benchmark functions for 1000, 2000, and 3000 iterations, managing to reach better results than the canonical GA, DE, and PSO. A comparison between our adaptive metaheuristic and an adaptive GA has shown that our approach presents better outcomes, which was proved by a t-test, as well.
Helder Pereira Borges, Omar Andres Carmona Cortes, Dario Vieira
Scrum Task Allocation Based on Particle Swarm Optimization
Abstract
In this paper, we present a novel algorithm called STAPSO, which comprises Scrum task allocation and the Particle Swarm Optimization algorithm. The proposed algorithm aims to address one of the most significant problems in the agile software development, i.e., iteration planning. The actuality of the topic is not questionable, since nowadays, agile software development plays a vital role in most of the organizations around the world. Despite many agile software development methodologies, we include the proposed algorithm in Scrum Sprint planning, as it is the most widely used methodology. The proposed algorithm was also tested on a real-world dataset, and the experiment shows promising results.
Lucija Brezočnik, Iztok Fister Jr., Vili Podgorelec
Cooperative Model for Nature-Inspired Algorithms in Solving Real-World Optimization Problems
Abstract
A cooperative model of eight popular nature-inspired algorithms (CoNI) is proposed and compared with the original algorithms on benchmark set CEC 2011 collection of 22 real-world optimization problems. The results of experiments demonstrate the superiority of CoNI variant in the most of the real-world problems although some of original nature-inspired algorithms perform rather poorly. Proposed CoNI shares the best position in 20 out of 22 problems and achieves the best results in 8 out 22 test problems. Further fundamental points for improvement of CoNI are in selection of topology, migration policy, and migration frequency.
Petr Bujok
Collaborative Agent Teams (CAT): From the Paradigm to Implementation Guidelines
Abstract
We propose a general solution method framework based on a Collaborative Agent Teams (CAT) architecture to tackle large-scale mixed-integer optimization problems with complex structures. This framework introduces several conceptual improvements over previous agent teams’ approaches. We discuss how to configure the three key components of a CAT solver for multidimensional optimization problems: the problem representation, the design of agents, and the information sharing mechanisms between agents. Implementation guidelines are also given.
Marc-André Carle, Alain Martel, Nicolas Zufferey
A Bio-inspired Approach for Collaborative Exploration with Mobile Battery Recharging in Swarm Robotics
Abstract
Swarm Robotics are widely conceived as the development of new computationally efficient tools and techniques aimed at easing and enhancing the coordination of multiple robots towards collaboratively accomplishing a certain mission or task. Among the different criteria under which the performance of Swarm Robotics can be gauged, energy efficiency and battery lifetime have played a major role in the literature. However, technological advances favoring power transfer among robots have unleashed new paradigms related to the optimization of the battery consumption considering it as a resource shared by the entire swarm. This work focuses on this context by elaborating on a routing problem for collaborative exploration in Swarm Robotics, where a subset of robots is equipped with battery recharging functionalities. Formulated as a bi-objective optimization problem, the quality of routes is measured in terms of the Pareto trade-off between the predicted area explored by robots and the risk of battery outage in the swarm. To efficiently balance these conflicting two objectives, a bio-inspired evolutionary solver is adopted and put to practice over a realistic experimental setup implemented in the VREP simulation framework. Obtained results elucidate the practicability of the proposed scheme, and suggest future research leveraging power transfer capabilities over the swarm.
Maria Carrillo, Ian Gallardo, Javier Del Ser, Eneko Osaba, Javier Sanchez-Cubillo, Miren Nekane Bilbao, Akemi Gálvez, Andrés Iglesias
Constructive Metaheuristics for the Set Covering Problem
Abstract
Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the problem considered.
Broderick Crawford, Ricardo Soto, Gino Astorga, José García
Single and Multiobjective Evolutionary Algorithms for Clustering Biomedical Information with Unknown Number of Clusters
Abstract
This article presents single and multiobjective evolutionary approaches for solving the clustering problem with unknown number of clusters. Simple and ad-hoc operators are proposed, aiming to keep the evolutionary search as simple as possible in order to scale up for solving large instances. The experimental evaluation is performed considering a set of real problem instances, including a real-life problem of analyzing biomedical information in the Parkinson’s disease map project. The main results demonstrate that the proposed evolutionary approaches are able to compute accurate trade-off solutions and efficiently handle the problem instance involving biomedical information.
María Eugenia Curi, Lucía Carozzi, Renzo Massobrio, Sergio Nesmachnow, Grégoire Danoy, Marek Ostaszewski, Pascal Bouvry
Evolutionary Algorithms for Scheduling of Crude Oil Preheating Process Under Linear Fouling
Abstract
The crude oil preheating process in refineries is required to be scheduled in a way to minimize the processing cost involved with it, subject to the satisfaction of various process related constraints. The process forms a mixed-integer optimization problem as the scheduling of the processing units involves binary variables, while the discharges from the running units are real valued. The two parts of such problems are usually handled by two different algorithms, where the optimum scheduling obtained by one algorithm is fed to another algorithm for optimizing its discharge process. In the present work, formulating the crude oil preheating process under the effect of linear fouling as a mixed-integer nonlinear programming (MINLP) model, three binary-real coded evolutionary algorithms (EAs) are investigated in order to demonstrate that a single EA can successfully tackle its both binary and real parts. Further, the statistical analysis of the performances of the EAs are also presented through their application to a benchmark instance of the problem.
Dimbalita Deka, Dilip Datta
Hybrid Weighted Barebones Exploiting Particle Swarm Optimization Algorithm for Time Series Representation
Abstract
The amount of data available in time series is recently increasing in an exponential way, making difficult time series preprocessing and analysis. This paper adapts different methods for time series representation, which are based on time series segmentation. Specifically, we consider a particle swarm optimization algorithm (PSO) and its barebones exploitation version (BBePSO). Moreover, a new variant of the BBePSO algorithm is proposed, which takes into account the positions of the particles throughout the generations, where those close in time are given more importance. This methodology is referred to as weighted BBePSO (WBBePSO). The solutions obtained by all the algorithms are finally hybridised with a local search algorithm, combining simple segmentation strategies (Top-Down and Bottom-Up). WBBePSO is tested in 13 time series and compared against the rest of algorithms, showing that it leads to the best results and obtains consistent representations.
Antonio Manuel Durán-Rosal, David Guijo-Rubio, Pedro Antonio Gutiérrez, César Hervás-Martínez
Data-Driven Preference-Based Deep Statistical Ranking for Comparing Multi-objective Optimization Algorithms
Abstract
To find the strengths and weaknesses of a new multi-objective optimization algorithm, we need to compare its performance with the performances of the state-of-the-art algorithms. Such a comparison involves a selection of a performance metric, a set of benchmark problems, and a statistical test to ensure that the results are statistical significant. There are also studies in which instead of using one performance metric, a comparison is made using a set of performance metrics. All these studies assume that all involved performance metrics are equal. In this paper, we introduce a data-driven preference-based approach that is a combination of multiple criteria decision analysis with deep statistical rankings. The approach ranks the algorithms for each benchmark problem using the preference (the influence) of each performance metric that is estimated using its entropy. Experimental results show that this approach achieved similar rankings to a previously proposed method, which is based on the idea of the majority vote, where all performance metrics are assumed equal. However, as it will be shown, this approach can give different rankings because it is based not only on the idea of counting wins, but also includes information about the influence of each performance metric.
Tome Eftimov, Peter Korošec, Barbara Koroušić Seljak
Construction of Heuristic for Protein Structure Optimization Using Deep Reinforcement Learning
Abstract
Deep neural networks are constructed that are able to partially solve a protein structure optimization problem. The networks are trained using reinforcement learning approach so that free energy of predicted protein structure is minimized. Free energy of a protein structure is calculated using generalized three-dimensional AB off-lattice protein model. This methodology can be applied to other classes of optimization problems and represents a step toward automatic heuristic construction using deep neural networks. Trained networks can be used to construct better initial populations for optimization. It is shown that differential evolution applied to protein structure optimization problem converges to better solutions when initial population is constructed in this way.
Rok Hribar, Jurij Šilc, Gregor Papa
Comparing Boundary Control Methods for Firefly Algorithm
Abstract
This paper compares four different methods for handling the roaming behavior of fireflies in the firefly algorithm. The problems of boundary constrained optimization forces the algorithm to actively keep the fireflies inside the feasible area of possible solutions. The recent CEC’17 benchmark suite is used for the performance comparison of the methods and the results are compared and tested for statistical significance.
Tomas Kadavy, Michal Pluhacek, Adam Viktorin, Roman Senkerik
A New Binary Encoding Scheme in Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem
Abstract
In the last decades the Vehicle Routing Problem (VRP) and its ramifications, including the Capacitated Vehicle Routing Problem (CVRP), have attracted the attention of researchers mainly because their presence in many practical situations. Due to the difficulties encountered in their solutions, such problems are usually solved by means of heuristic and metaheuristics algorithms, among which is the Genetic Algorithm (GA). The solution of CVRP using GA requires a solution encoding step, which demands a special care to avoid high computational cost and to ensure population diversity that is essential for the convergence of GA to global optimal or sub-optimal solutions. In this work, we investigated a new binary encoding scheme employed by GA for solving the CVRP. Conducted experiments demonstrated that the proposed binary encoding is able to provide good solutions and is suitable for practical applications that require low computational cost.
Stanley Jefferson de A. Lima, Sidnei Alves de Araújo
Ensemble and Fuzzy Techniques Applied to Imbalanced Traffic Congestion Datasets: A Comparative Study
Abstract
Class imbalance is among the most persistent complications which may confront the traditional supervised learning task in real-world applications. Among the different kind of classification problems that have been studied in the literature, the imbalanced ones, particularly those that represents real-world problems, have attracted the interest of many researchers in recent years. In order to face this problems, different approaches have been used or proposed in the literature, between then, soft computing and ensemble techniques. In this work, ensembles and fuzzy techniques have been applied to real-world traffic datasets in order to study their performance in imbalanced real-world scenarios. KEEL platform is used to carried out this study. The results show that different ensemble techniques obtain the best results in the proposed datasets.
Pedro Lopez-Garcia, Antonio D. Masegosa, Enrique Onieva, Eneko Osaba
Multi-objective Design of Time-Constrained Bike Routes Using Bio-inspired Meta-heuristics
Abstract
This paper focuses on the design and implementation of a bike route optimization approach based on multi-objective bio-inspired heuristic solvers. The objective of this approach is to produce a set of Pareto-optimal bike routes that balance the trade-off between the length of the route and its safety level, the latter blending together the slope of the different street segments encompassing the route and their average road velocity. Additionally, an upper and lower restriction is imposed on the time taken to traverse the route, so that the overall system can be utilized for planning bike rides during free leisure time gaps. Instead of designing a discrete route encoding strategy suitable for heuristic operators, this work leverages a proxy software – Open Trip Planner, OTP – capable of computing routes based on three user-level preference factors (i.e. safety, inclination and duration), which eases the adoption of off-the-shelf multi-objective solvers. The system has been assessed in a realistic simulation environments over the city of Bilbao (Spain) using multi-objective bio-inspired approaches. The obtained results are promising, with route sets trading differently distance for safety of utmost utility for bike users to exploit fully their leisure time.
Eneko Osaba, Javier Del Ser, Miren Nekane Bilbao, Pedro Lopez-Garcia, Antonio J. Nebro
Ensemble of Kriging with Multiple Kernel Functions for Engineering Design Optimization
Abstract
We introduce the ensemble of Kriging with multiple kernel functions guided by cross-validation error for creating a robust and accurate surrogate model to handle engineering design problems. By using the ensemble of Kriging models, the resulting ensemble model preserves the uncertainty structure of Kriging, thus, can be further exploited for Bayesian optimization. The objective of this paper is to develop a Kriging methodology that eliminates the needs for manual kernel selection which might not be optimal for a specific application. Kriging models with three kernel functions, that is, Gaussian, Matérn-3/2, and Matérn-5/2 are combined through a global and a local ensemble technique where their approximation quality are investigated on a set of aerodynamic problems. Results show that the ensemble approaches are more robust in terms of accuracy and able to perform similarly to the best performing individual kernel function or avoiding misspecification of kernel.
Pramudita Satria Palar, Koji Shimoyama
Path Planning Optimization Method Based on Genetic Algorithm for Mapping Toxic Environment
Abstract
The ionizing radiation is used in the nuclear medicine field during the execution of diagnosis exams. The administration of nuclear radio pharmaceutical components to the patient contaminates the environment. The main contribution of this work is to propose a path planning method for scanning the nuclear contaminated environment with a mobile robot optimizing the traveled distance. The Genetic Algorithm methodology is proposed and compared with other approaches and the final solution is validated in simulated and real environment in order to achieve a closer approximation to reality.
Luis Piardi, José Lima, Ana I. Pereira, Paulo Costa
Tuning Multi-Objective Optimization Algorithms for the Integration and Testing Order Problem
Abstract
Multi-Objective Evolutionary Algorithms (MOEAs) are one of the most used search techniques in Search-Based Software Engineering (SBSE). However, MOEAs have many control parameters which must be configured for the problem at hand. This can be a very challenging task by itself. To make matters worse, in Multi-Objective Optimization (MOO) different aspects of quality of the obtained Pareto front need to be taken in to account. A novel method called MOCRS-Tuning is proposed to address this problem. MOCRS-Tuning is a meta-evolutionary algorithm which uses a chess rating system with quality indicator ensemble. The chess rating system enables us to determine the performance of an MOEA on different problems easily. The ensemble of quality indicators ensures that different aspects of quality are considered. The tuning was carried out on five different MOEAs on the Integration and Test Order Problem (ITO). The experimental results show significant improvement after tuning of all five MOEAs used in the experiment.
Miha Ravber, Matej Črepinšek, Marjan Mernik, Tomaž Kosar
Surrogate-Assisted Particle Swarm with Local Search for Expensive Constrained Optimization
Abstract
This paper develops a surrogate-assisted particle swarm optimization framework for expensive constrained optimization called CONOPUS (CONstrained Optimization by Particle swarm Using Surrogates). In each iteration, CONOPUS considers multiple trial positions for each particle in the swarm and uses surrogate models for the objective and constraint functions to identify the most promising trial position where the expensive functions are evaluated. Moreover, the current overall best position is refined by finding the minimum of the surrogate of the objective function within a neighborhood of that position and subject to surrogate inequality constraints with a small margin and with a distance requirement from all previously evaluated positions. CONOPUS is implemented using radial basis function (RBF) surrogates and the resulting algorithm compares favorably to alternative methods on 12 benchmark problems and on a large-scale application from the auto industry with 124 decision variables and 68 inequality constraints.
Rommel G. Regis
Indicator-Based Versus Aspect-Based Selection in Multi- and Many-Objective Biochemical Optimization
Abstract
The identification of qualified peptides as ligands for diagnostic and therapeutic interventions requires the solution of multi- and many-objective biochemical optimization problems. A MOEA has been designed for molecular optimization with a combined indicator- and Pareto-based selection strategy that encounters common classification problems of the solutions’ quality with the rise of the problem dimension. Therefore, a sophisticated selection strategy is presented in this work that selects the individuals for the succeeding generation related to two general aspects in biochemical optimization: the first aspect reflects the peptide quality and the second one the genetic dissimilarity among the peptides in a population. The search behavior of this aspect-based selection is compared to the traditional selection on generic 3- to 6-dimensional physiochemical optimization problems and the impact of the reference point in the aspect-based selection is investigated.
Susanne Rosenthal, Markus Borschbach
An Approach for Recovering Distributed Systems from Disasters
Abstract
This paper presents an approach to recovering distributed applications, which consist of software agents running on different computers from drastic damages by disasters. The approach is inspired from regeneration mechanisms in living things, e.g., tails of lizards. When an agent delegates a function to another agent coordinating with it, if the former has the function, this function becomes less-developed and the latter’s function becomes well-developed like differentiation processes in cells. It can also initialize and restart differentiated software agents, when some agents cannot be delegated like regeneration processes. It is constructed as a general-purpose and practical middleware system for software agents on real distributed systems consisting of embedded computers or sensor nodes.
Ichiro Satoh
Population Diversity Analysis for the Chaotic Based Selection of Individuals in Differential Evolution
Abstract
This research deals with the modern and popular hybridization of chaotic dynamics and evolutionary computation. It is aimed at the influence of chaotic sequences on the population diversity as well as the algorithm performance of the simple parameter adaptive Differential Evolution (DE) strategy: jDE. Experiments are focused on the extensive investigation of the different randomization schemes for the selection of individuals in DE algorithm driven by the nine different two-dimensional discrete chaotic systems, as the chaotic pseudo-random number generators. The population diversity and jDE convergence are recorded on the 15 test functions from the CEC 2015 benchmark.
Roman Senkerik, Adam Viktorin, Michal Pluhacek, Tomas Kadavy
Robust Design with Surrogate-Assisted Evolutionary Algorithm: Does It Work?
Abstract
Recently, the use of surrogate models for robustness assessment has become popular in various research fields. In this paper, we investigate whether it is advantageous to use the sample data to build a model instead of computing the robustness measures directly. The results suggest that if the quality of the surrogate model cannot be guaranteed, their use can be harmful to the optimization process.
Rodrigo C. P. Silva, Min Li, Vahid Ghorbanian, Frederico G. Guimarães, David A. Lowther
How Distance Based Parameter Adaptation Affects Population Diversity
Abstract
This paper discusses the effect of distance based parameter adaptation on the population diversity of the Success-History based Adaptive Differential Evolution (SHADE). The distance-based parameter adaptation was designed to promote exploration over exploitation and provide better search capabilities of the SHADE algorithm in higher dimensional objective spaces. The population diversity is recorded on the 15 test functions from the CEC 2015 benchmark set in two-dimensional settings, 10D and 30D, to provide the empiric evidence of a beneficial influence of the distance based parameter adaptation in comparison with the objective function value based approach.
Adam Viktorin, Roman Senkerik, Michal Pluhacek, Tomas Kadavy
Collaborative Variable Neighborhood Search
Abstract
Variable neighborhood search (VNS) is a well-known metaheuristic. Two main ingredients are needed for its design: a collection \(M=(N_1, \ldots , N_r)\) of neighborhood structures and a local search LS (often using its own single neighborhood L). M has a diversification purpose (search for unexplored zones of the solution space S), whereas LS plays an intensification role (focus on the most promising parts of S). Usually, the used set M of neighborhood structures relies on the same type of modification (e.g., change the value of i components of the decision variable vector, where i is a parameter) and they are built in a nested way (i.e., \(N_i\) is included in \(N_{i+1}\)). The more difficult it is to escape from the currently explored zone of S, the larger is i, and the more capability has the search process to visit regions of S which are distant (in terms of solution structure) from the incumbent solution. M is usually designed independently from L. In this paper, we depart from this classical VNS framework and discuss an extension, Collaborative Variable Neighborhood Search (CVNS), where the design of M and L is performed in a collaborative fashion (in contrast with nested and independent), and can rely on various and complementary types of modifications (in contrast with a common type with different amplitudes).
Nicolas Zufferey, Olivier Gallay
Backmatter
Metadata
Title
Bioinspired Optimization Methods and Their Applications
Editors
Peter Korošec
Nouredine Melab
El-Ghazali Talbi
Copyright Year
2018
Electronic ISBN
978-3-319-91641-5
Print ISBN
978-3-319-91640-8
DOI
https://doi.org/10.1007/978-3-319-91641-5

Premium Partner