Skip to main content

2019 | Buch

Bioinspired Heuristics for Optimization

insite
SUCHEN

Über dieses Buch

This book presents recent research on bioinspired heuristics for optimization. Learning- based and black-box optimization exhibit some properties of intrinsic parallelization, and can be used for various optimizations problems. Featuring the most relevant work presented at the 6th International Conference on Metaheuristics and Nature Inspired Computing, held at Marrakech (Morocco) from 27th to 31st October 2016, the book presents solutions, methods, algorithms, case studies, and software. It is a valuable resource for research academics and industrial practitioners.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Possibilistic Framework for Multi-objective Optimization Under Uncertainty
Abstract
Optimization under uncertainty is an important line of research having today many successful real applications in different areas. Despite its importance, few works on multi-objective optimization under uncertainty exist today. In our study, we address combinatorial multi-objective problem under uncertainty using the possibilistic framework. To this end, we firstly propose new Pareto relations for ranking the generated uncertain solutions in both mono-objective and multi-objective cases. Secondly, we suggest an extension of two well-known Pareto-base evolutionary algorithms namely, SPEA2 and NSGAII. Finally, the extended algorithms are applied to solve a multi-objective Vehicle Routing Problem (VRP) with uncertain demands.
Oumayma Bahri, Nahla Benamor, El-Ghazali Talbi
Chapter 2. Solving the Uncapacitated Single Allocation p-Hub Median Problem on GPU
Abstract
This chapter presents a parallel GPU implementation for solving the Uncapacitated Single Allocation p-Hub Median Problem with genetic algorithm. Starting from an initial solution that locates hubs at center nodes, our GPU implementation quickly reaches optimal or near-optimal solutions. It efficiently exploits the computing power of the GPU and outperforms, in cost and in computing time, the other approaches proposed in the literature for this problem. We compare it to the best recent solutions on the benchmarks up to 1000 nodes and on large instances up to 6000 nodes generated by us. Moreover, we solved instance problems so far unsolved.
A. Benaini, A. Berrajaa, J. Boukachour, M. Oudani
Chapter 3. Phase Equilibrium Description of a Supercritical Extraction System Using Metaheuristic Optimization Algorithms
Abstract
This chapter describes the ongoing work dealing with the prediction and estimation of vapor-liquid thermodynamic properties using global optimization algorithms. For the present case, phase equilibrium parameters for the system of supercritical carbon dioxide (sCO\(_2\)) and some essential oils, were estimated using the corrected version of van der Waals and Wong-Sandler mixing rules, the Peng-Robinson state equation and the more common thermodynamic models for non-linear parameter estimation in equilibrium modeling, namely, Van Laar, NRTL and UNIQUAC. We propose using a variant of the traditional harmony search algorithm, i.e. self-regulated harmony search (SFHS), for this task. Here, we include preliminary simulation results for the system, sCO\(_2\): \(\alpha \)-pineno using the Wong-Sandler rule and the Van Laar model. Results show a good agreement between the experimental results reported in the literature, and the predictions using the SFHS algorithm. Furthermore, SFHS seems to be a promising algorithm for processing phase equilibrium data.
Ivan Amaya, Cristian Jiménez, Rodrigo Correa
Chapter 4. Intrusion Detection System Based on a Behavioral Approach
Abstract
Intrusion Detection System (IDS) can be defined as a group of tools, methods and resources that help us to predict or identify any unauthorized activity in a network. Current IDSs are mainly based on techniques constructed on heuristic rules, named signatures, in order to detect intrusions in a network environment. The drawbacks of these approach is that it could only detect a known attacks and referenced above. Contrastively, Intrusion Detection behavioral, or anomaly, assume that attacks causes an abnormal use of resources or manifest a strange behavior on the part of the user, by studying the behavior of the different types of network traffic it can identify the known and unknown attacks using the artificial learning algorithm. This study proposes a new behavioral approach of intrusion detection based on combination APSO (Accelerated Particle Swarm Optimization)-SVM (Support Vector Machine) to develop a model for IDS. The simulation results show a significant amelioration in performances, all tests were realized with the NSL-KDD data set. In comparison with other methods based on the same dataset, the proposed model shows a high detection performance.
Mehdi Moukhafi, Seddik Bri, Khalid El Yassini
Chapter 5. A New Hybrid Method to Solve the Multi-objective Optimization Problem for a Composite Hat-Stiffened Panel
Abstract
In this paper we present a new hybrid meta heuristic by combining Multi-objective bat algorithm (MOBA) and variable neighborhood search (VNS). The hybrid meta heuristic is coupled with response surface methodology (or meta modeling) to solve the mechanical multi-objective optimization problem of hat stiffened composite panel. The optimization criteria were the weight and the rigidity of the panel. Experimental results show that our suggested approach is quite effective, as it provides solutions that are competitive with the results obtained by using MOBA alone and other state of the art optimization algorithms.
Ahmad El Samrout, Oussama Braydi, Rafic Younes, Francois Trouchu, Pascal Lafon
Chapter 6. Storage Yard Management: Modelling and Solving
Abstract
The volume of cargo transported and stored around the world grows every year. To ensure competitiveness, productivity and cost savings, companies continually invest in process improvement and the development of IT tools. This chapter discusses various optimization problems existing in the process of storing and transporting loads. In this work, an integrated problem of planning and scheduling is defined, a mathematical programming model is investigated, and solutions are obtained through the use of heuristics and a commercial optimization package. The computational experiments (based in real cases) showed that the method is more efficient in producing a feasible solution than the solver.
Gustavo Campos Menezes, Geraldo Robson Mateus, Martín Gómez Ravetti
Chapter 7. Multi-capacitated Location Problem: A New Resolution Method Combining Exact and Heuristic Approaches Based on Set Partitioning
Abstract
In this paper, we present one generalization of the famous capacitated p-median location problem, called budget constraint multi-capacitated location problem (MCLP). This new generalization is characterized by allowing each facility to be used with different capacity levels. The MCLP solution can be represented as a set of disjoint clusters (pair of one facility and a subset of customers). Creating these clusters satisfies implicitly some constraints of the problem. In this work, we present the new formulation of the MCLP based on set partitioning, then we suggest an adapted solving method, which will be called NFF (Nearest Facility First). This new method can be used in two ways: as a heuristic by taking only the first solution found or exact approach when waiting finished the execution. Computational results are presented at the end using instances that we have created under some criteria of difficulties or adapted from those of p-median problems available in literature. The NFF method provides very good results for low and medium difficulty instances, but it is less effective for the more complex ones. To remedy this problem, the method will be supplemented by column generation approach.
Mohammed El Amrani, Youssef Benadada, Bernard Gendron
Chapter 8. Application of Genetic Algorithm for Solving Bilevel Linear Programming Problems
Abstract
Bilevel linear programming problem is a special class of nonconvex optimization problems which involves two levels with a hierarchical organization structure. In this paper, we present a genetic algorithm (GA) based approach to solve the bilevel linear programming (BLP) problem. The efficiency of this approach is confirmed by comparing the results with Kuo and Han’s method HGAPSO consisting of a hybrid of GA and particle swarm optimization algorithm (PSO) in Kuo and Han (Applied Mathematical Modelling 35:3905–3917, 2011, [15]) using four problems in the literature and an example of supply chain model. These results show that the proposed approach provides the optimal solution and outperforms HGAPSO for most test problems adopted from the literature.
M. Ait Laamim, A. Makrizi, E. H. Essoufi
Chapter 9. Adapted Bin-Packing Algorithm for the Yard Optimization Problem
Abstract
Given the importance of the Maritime transportation to move goods between continent, optimizing their processes becomes the objective of many types of research. In this paper, we present a new model of the yard optimization problem which contains three important components: unloading/loading, transfer and storage process. Our proposed method called Adapted Bin Packing Algorithm for the yard optimization problem (ABPAYOP) focus on using the approach of the Bin packing algorithm to build Bins (free positions in the yard, subgroup of containers) this will be a generalization of the container stacking problem as it will include the use of yard cranes, quay cranes and internal trucks. the ABPAYOP solutions can be represented as a set of disjoint clusters satisfying of given number of constraints (yard bays, subgroup of containers). In this work, we present the new formulation of the yard optimization problem, then we will apply our heuristic ABPAYOP to solve it. Computational results are presented at the end using instances created and adapted to the ones existing in the literature. Our results illustrate the performance of the applied method for the medium and big instances.
Chafik Razouk, Youssef Benadada, Jaouad Boukachour
Chapter 10. Hidden Markov Model Classifier for the Adaptive ACS-TSP Pheromone Parameters
Abstract
The Hidden Markov Models (HMM) are a powerful statistical techniques for modeling complex sequences of data. In this paper a Hidden Markov Model classifier is a special kind of these models that aims to find the posterior probability of each state given a sequence of observations and predicts the state with the highest probability. The purpose of this work is to enhance the performance of Ant Colony System algorithm applied to the Travelling Salesman Problem (ACS-TSP) by varying dynamically both local and global pheromone decay parameters based on the Hidden Markov Model algorithm, using two indicators: Diversity and Iteration that reflect the state of research space in a given moment. The proposed method was tested on several TSP benchmark instances, which compared with the basic ACS, the combination of Fuzzy Logic Controller (FLC) and ACS to prove the efficiency of its performance.
Safae Bouzbita, Abdellatif El Afia, Rdouan Faizi
Chapter 11. CHN and Min-Conflict Heuristic to Solve Scheduling Meeting Problems
Abstract
Meetings are important for teem works, However, scheduling a meeting that involves persons with different preferences and engagements remains a difficult task. This paper proposes a new hybrid approach to solve meeting scheduling problem (MSP). The proposed network combines the characteristics of neural networks and minimizing conflicts approach. Her the MSP is considerate as Constraint Satisfaction Problem, then we apply Continuous Hopfield Neural Netwok (CHN) and Conflicts Minimization Heuristics to solve a quadratic reformulation of the CSP-MSP model in other words the Min-Conflict heuristic will improve the given CHN solution. So, the performance of the network is compared with the existing scheduling algorithms under various experimental conditions.
Adil Bouhouch, Chakir Loqman, Abderrahim El Qadi
Chapter 12. A Probabilistic Finite State Machine Design of Particle Swarm Optimization
Abstract
Nowadays, control is the main concern with emergent behaviours of multi-agent systems and state machine reasoning. This paper focuses on the restriction of this general issue to swarm intelligence approaches designed for solving complex optimization problems. Indeed, we propose a probabilistic finite state machine for controlling particles behaviour of the particle swarm optimization algorithm. That is, our multi-agent approach consists of assigning different roles to each particle based on its probabilistic finite state machine control which is used to address this issue. We performed evaluations on ten benchmark functions to test our control scheme for particles. Experimental results show that our proposed scheme gives a distinguishable out-performance on a number of state of the art of PSO variants.
Abdellatif El Afia, Malek Sarhani, Oussama Aoun
Chapter 13. Algorithm Selector and Prescheduler in the ICON Challenge
Abstract
Algorithm portfolios are known to offer robust performances, efficiently overcoming the weakness of every single algorithm on some particular problem instances. Two complementary approaches to get the best out of an algorithm portfolio are to achieve algorithm selection (AS), and to define a scheduler, sequentially launching a few algorithms on a limited computational budget each. The presented system relies on the joint optimization of a pre-scheduler and a per-instance AS, selecting an algorithm well-suited to the problem instance at hand. ASAP has been thoroughly evaluated against the state-of-the-art during the ICON challenge for algorithm selection, receiving an honorable mention. Its evaluation on several combinatorial optimization benchmarks exposes surprisingly good results of the simple heuristics used; some extensions thereof are presented and discussed in the paper.
François Gonard, Marc Schoenauer, Michèle Sebag
Chapter 14. A Metaheuristic Approach to Compute Pure Nash Equilibria
Abstract
A pure Nash equilibrium is a famous concept in the field of game theory and has a wide range of applications. In the last decade, a lot of progress has been made in determining the computational complexity of finding equilibria in games. Deciding if a pure Nash equilibrium exists in n-player normal form games and several subclasses has been shown to be NP-complete. Current exact approaches to compute them are impractical and only able to solve small instances. In this paper, we apply three local search-based metaheuristics for solving the problem. Results on 280 randomly generated instances with different sizes show the clear outperformance of the metaheuristic approaches over the exact method based on Mixed Integer Linear Programming.
Niels Elgers, Nguyen Dang, Patrick De Causmaecker
Chapter 15. Hybrid Genetic Algorithms to Solve the Multidimensional Knapsack Problem
Abstract
This paper introduces solutions to deal with the Multidimensional Knapsack Problem (MKP), which is a NP-hard combinatorial optimisation problem. Two hybrid heuristics based on Genetic Algorithms (GA) are proposed: the Memetic Search Algorithm (MSA) and the Genetic Algorithm Guided by Pretreatment information (GAGP). MSA combines sequentially GA with the Stochastic Local Search-Simulated Annealing algorithm (SLSA). GAGP is composed of two steps, in the first, a ratio-based greedy algorithm extracts useful information and the core concept is utilised to decompose items according to their ratios; In the second, these information are integrated to the operators of a GA allowing to reach the best solutions faster. An operator is added to the GA to dynamically update the ratio values of the items. Two groups of data were used to examine the proposed approaches. A group of simple instances of MKP has been used to examine MSA and a group of complex MKP has been used to examine GAGP. The obtained results indicate that MSA and GAGP have the capability to give solutions of high quality.
Abdellah Rezoug, Mohamed Bader-El-Den, Dalila Boughaci
Chapter 16. Solving the Home Health Care Problem with Temporal Precedence and Synchronization
Abstract
Home health care (HHC) services aim to improve patients’ living condition by providing different services at patients home. This chapter presents a medium-term home health care problem (HHCP) model. This model considers qualification requirements, possible patients/nurses exclusions, temporal precedences, synchronized services, routing with time windows, and working time constraints. As building a proper HHC planning is a challenging task, we proposed a two-stages approach including a new construction heuristic and an enhance basic VNS. Various alternatives in the construction heuristic and tested neighborhoods are exposed and discussed. The obtained results of the solving approach are compared to the literature, on challenging publicly available short-term datasets with temporal precedences and synchronized services. Amongst the 40 instances used, we obtained better results than the literature for 37 of them.
Sophie Lasfargeas, Caroline Gagné, Aymen Sioud
Chapter 17. Automatically Generating Assessment Tests Within Higher Education Context Thanks to Genetic Approach
Abstract
In educational context (online or face-to-face), with increasing cohort size and the need for individualization, the question of partial or full automation of assessments is growing. This paper deals with preliminary works that tackle the question of automatic generation of assessment Tests that could guarantee fairness and reasonable difference, by the content and the structure. A structural metric characterizing the distance between two given Tests is presented. This metric provides a dedicated fitness function that leads to define a Genetic Algorithm (GA) technique. The original use of GA allows optimizing this structural differentiation and thus guarantees the generation of collections of Tests with the largest distance possible while involving the smallest items source database. Preliminary experiments and results on the basis of multiple choice questions items are discussed.
R. Ciguené, C. Joiron, G. Dequen
Chapter 18. Ant Colony Optimization for Optimal Low-Pass Filter Sizing
Abstract
In analog filter design, discrete components values such as resistors (R) and capacitors (C) are selected from the series following constant values chosen. Exhaustive search on all possible combinations for an optimized design is not feasible. In this chapter, we present an application of the Ant Colony Optimization (ACO) technique for optimal filter design considering different manufacturing series for both the resistors and capacitors. Three variants of the Ant Colony Optimization are applied, namely, the AS (Ant System), the MMAS (Min-Max AS) and the ACS (Ant Colony System), for the optimal sizing of the Low-Pass Butterworth filter. Different optimal designs of the filter are provided depending on the preference between two conflicting factors, namely the cutoff frequency and selectivity factor. SPICE simulations are used to validate the obtained results/performances. A comparison with published works is also highlighted.
Loubna Kritele, Bachir Benhala, Izeddine Zorkani
Chapter 19. Maximum a Posteriori Based Evolutionary Algorithm
Abstract
This work is dedicated to the presentation and the analysis of the performance of Maximum a posteriori based Evolutionary Algorithm (MEA). MEA allows a hybridization of set of operators to preserve the diversity during the search. This approach is based on a set of search strategies which are composed of one crossover with one mutation method, respectively. The algorithm uses the Maximum a Posteriori Principle (MAP) to select the most probable strategy from those available in the search set. Experiments were performed on well-known continuous optimization problems to observe the impact of population size and operators rates on MEA’s behaviour, robustness and performance.
Asmaa Ghoumari, Amir Nakib, Patrick Siarry
Metadaten
Titel
Bioinspired Heuristics for Optimization
herausgegeben von
Prof. El-Ghazali Talbi
Dr. Amir Nakib
Copyright-Jahr
2019
Electronic ISBN
978-3-319-95104-1
Print ISBN
978-3-319-95103-4
DOI
https://doi.org/10.1007/978-3-319-95104-1