Optimization and Machine Learning
Description
Optimization and Machine Learning presents modern advances in the selection, configuration and engineering of algorithms that rely on machine learning and optimization. The first part of the book is dedicated to applications where optimization plays a major role, and the second part describes and implements several applications that are mainly based on machine learning techniques. The methods addressed in these chapters are compared against their competitors, and their effectiveness in their chosen field of application is illustrated.
More details
Other editions
Additional editions
Persons
Patrick Siarry is a Professor in automatics and informatics at Paris-East Creteil University, France. His main research interests are the design of stochastic global optimization heuristics and their applications in various engineering fields. He has coordinated several books in the field of optimization.
Content
Introduction xi
Rachid CHELOUAH
Part 1 Optimization 1
Chapter 1 Vehicle Routing Problems with Loading Constraints: An Overview of Variants and Solution Methods 3
Ines SBAI and Saoussen KRICHEN
1.1 Introduction 3
1.2 The capacitated vehicle routing problem with two-dimensional loading constraints 5
1.2.1 Solution methods 6
1.2.2 Problem description 8
1.2.3 The 2L-CVRP variants 9
1.2.4 Computational analysis 10
1.3 The capacitated vehicle routing problem with three-dimensional loading constraints 11
1.3.1 Solution methods 11
1.3.2 Problem description 13
1.3.3 3L-CVRP variants 14
1.3.4 Computational analysis 16
1.4 Perspectives on future research 18
1.5 References 18
Chapter 2 MAS-aware Approach for QoS-based IoT Workflow Scheduling in Fog-Cloud Computing 25
Marwa MOKNI and Sonia YASSA
2.1 Introduction 26
2.2 Related works 27
2.3 Problem formulation 29
2.3.1 IoT-workflow modeling 31
2.3.2 Resources modeling 31
2.3.3 QoS-based workflow scheduling modeling 31
2.4 MAS-GA-based approach for IoT workflow scheduling 33
2.4.1 Architecture model 33
2.4.2 Multi-agent system model 34
2.4.3 MAS-based workflow scheduling process 35
2.5 GA-based workflow scheduling plan 38
2.5.1 Solution encoding 39
2.5.2 Fitness function 41
2.5.3 Mutation operator 41
2.6 Experimental study and analysis of the results 43
2.6.1 Experimental results 45
2.7 Conclusion 51
2.8 References 51
Chapter 3 Solving Feature Selection Problems Built on Population-based Metaheuristic Algorithms 55
Mohamed SASSI
3.1 Introduction 56
3.2 Algorithm inspiration 57
3.2.1 Wolf pack hierarchy 57
3.2.2 The four phases of pack hunting 58
3.3 Mathematical modeling 59
3.3.1 Pack hierarchy 59
3.3.2 Four phases of hunt modeling 61
3.3.3 Research phase - exploration 64
3.3.4 Attack phase - exploitation 65
3.3.5 Grey wolf optimization algorithm pseudocode 66
3.4 Theoretical fundamentals of feature selection 67
3.4.1 Feature selection definition 67
3.4.2 Feature selection methods 68
3.4.3 Filter method 68
3.4.4 Wrapper method 69
3.4.5 Binary feature selection movement 69
3.4.6 Benefits of feature selection for machine learning classification algorithms 70
3.5 Mathematical modeling of the feature selection optimization problem 70
3.5.1 Optimization problem definition 71
3.5.2 Binary discrete search space 71
3.5.3 Objective functions for the feature selection 72
3.6 Adaptation of metaheuristics for optimization in a binary search space 76
3.6.1 Module ¿¿¿¿1 77
3.6.2 Module ¿¿¿¿2 78
3.7 Adaptation of the grey wolf algorithm to feature selection in a binary search space 81
3.7.1 First algorithm bGWO1 81
3.7.2 Second algorithm bGWO2 83
3.7.3 Algorithm 2: first approach of the binary GWO 84
3.7.4 Algorithm 3: second approach of the binary GWO 85
3.8 Experimental implementation of bGWO1 and bGWO2 and discussion 86
3.9 Conclusion 87
3.10 References 88
Chapter 4 Solving the Mixed-model Assembly Line Balancing Problem by using a Hybrid Reactive Greedy Randomized Adaptive Search Procedure 91
Belkharroubi LAKHDAR and Khadidja YAHYAOUI
4.1 Introduction 92
4.2 Related works from the literature 95
4.3 Problem description and mathematical formulation 97
4.3.1 Problem description 97
4.3.2 Mathematical formulation 98
4.4 Basic greedy randomized adaptive search procedure 99
4.5 Reactive greedy randomized adaptive search procedure 100
4.6 Hybrid reactive greedy randomized adaptive search procedure for the mixed model assembly line balancing problem type-2 101
4.6.1 The proposed construction phase 102
4.6.2 The local search phase 106
4.7 Experimental examples 107
4.7.1 Results and discussion 111
4.8 Conclusion 115
4.9 References 116
Part 2 Machine Learning 119
Chapter 5 An Interactive Attention Network with Stacked Ensemble Machine Learning Models for Recommendations 121
Ahlem DRIF, SaadEddine SELMANI and Hocine CHERIFI
5.1 Introduction 122
5.2 Related work 124
5.2.1 Attention network mechanism in recommender systems 124
5.2.2 Stacked machine learning for optimization 125
5.3 Interactive personalized recommender 126
5.3.1 Notation 128
5.3.2 The interactive attention network recommender 129
5.3.3 The stacked content-based filtering recommender 134
5.4 Experimental settings 136
5.4.1 The datasets 136
5.4.2 Evaluation metrics 137
5.4.3 Baselines 139
5.5 Experiments and discussion 140
5.5.1 Hyperparameter analysis 140
5.5.2 Performance comparison with the baselines 143
5.6 Conclusion 146
5.7 References 146
Chapter 6 A Comparison of Machine Learning and Deep Learning Models with Advanced Word Embeddings: The Case of Internal Audit Reports 151
Gustavo FLEURY SOARES and Induraj PUDHUPATTU RAMAMURTHY
6.1 Introduction 152
6.2 Related work 154
6.2.1 Word embedding 156
6.2.2 Deep learning models 157
6.3 Experiments and evaluation 158
6.4 Conclusion and future work 163
6.5 References 165
Chapter 7 Hybrid Approach based on Multi-agent System and Fuzzy Logic for Mobile Robot Autonomous Navigation 169
Khadidja YAHYAOUI
7.1 Introduction 170
7.2 Related works 171
7.2.1 Classical approaches 172
7.2.2 Advanced methods 173
7.3 Problem position 174
7.4 Developed control architecture 176
7.4.1 Agents description 177
7.5 Navigation principle by fuzzy logic 183
7.5.1 Fuzzy logic overview 183
7.5.2 Description of simulated robot 184
7.5.3 Strategy of navigation 185
7.5.4 Fuzzy controller agent 186
7.6 Simulation and results 194
7.7 Conclusion 196
7.8 References 196
Chapter 8 Intrusion Detection with Neural Networks: A Tutorial 201
Alvise DE' FAVERI TRON
8.1 Introduction 201
8.1.1 Intrusion detection systems 201
8.1.2 Artificial neural networks 202
8.1.3 The NSL-KDD dataset 202
8.2 Dataset analysis 203
8.2.1 Dataset summary 203
8.2.2 Features 203
8.2.3 Binary feature distribution 204
8.2.4 Categorical features distribution 207
8.2.5 Numerical data distribution 211
8.2.6 Correlation matrix 212
8.3 Data preparation 213
8.3.1 Data cleaning 213
8.3.2 Categorical columns encoding 213
8.3.3 Normalization 214
8.4 Feature selection 217
8.4.1 Tree-based selection 217
8.4.2 Univariate selection 218
8.5 Model design 219
8.5.1 Project environment 219
8.5.2 Building the neural network 220
8.5.3 Learning hyperparameters 220
8.5.4 Epochs 220
8.5.5 Batch size 221
8.5.6 Dropout layers 221
8.5.7 Activation functions 222
8.6 Results comparison 222
8.6.1 Evaluation metrics 222
8.6.2 Preliminary models 223
8.6.3 Adding dropout 225
8.6.4 Adding more layers 226
8.6.5 Adding feature selection 227
8.7 Deployment in a network 228
8.7.1 Sensors 228
8.7.2 Model choice 229
8.7.3 Model deployment 229
8.7.4 Model adaptation 231
8.8 Future work 231
8.9 References 231
List of Authors 233
Index 235
1
Vehicle Routing Problems with Loading Constraints: An Overview of Variants and Solution Methods
Ines SBAI1 and Saoussen KRICHEN1
1Université de Tunis, Institut Supérieur de Gestion de Tunis, LARODEC Laboratory, Tunisia
This chapter combines two of the most studied combinatorial optimization problems, namely, the capacitated vehicle routing problem (CVRP) and the two/three-dimensional bin packing problem (2/3D-BPP). It focuses heavily on real-life transportation problems such as the transportation of furniture or industrial machinery. An extensive overview of the CVRP with two/three-dimensional loading constraints is presented by surveying over 76 existing contributions. We provide an updated review of the variants of the L-CVRP studied in the literature and analyze some of the most popular optimization methods presented in the existing literature. Alongside this, we discuss their variants and constraints, their applications for solving real-world problems, as well as their impact on the current literature.
1.1. Introduction
Although the vehicle routing problem (VRP) is the most studied combinatorial optimization problem, the challenge still remains to achieve the most optimal and effective results (Sbai et al. 2020a). The VRP aims to minimize total traveling cost in cases where a fleet of identical vehicles is used to visit a set of customers. The VRP is used in many real-world applications, for example: pharmaceutical distribution, food distribution, the urban bus problem and garbage collection. The basic version of the VRP is known as the capacitated VRP (CVRP); each vehicle has a fixed capacity which must be respected and must not be exceeded when loading items. It is aimed at minimizing the total cost of serving all the customers. The CVRP can be extended to the VRP with time windows (VRPTW) by adding time windows to define the overall traveling time for a vehicle. It can also be extended to the VRP with pickups and deliveries (VRPPD) where orders may be picked up and delivered. Another variant of the basic CVRP is the VRP with backhauls (VRPB). Here, pickups and deliveries may be combined in a single route; all delivery requests therefore need to be performed before the empty vehicle can collect goods from customer locations. Two surveys, conducted by Cordeau et al. (2002) and Laporte (2009), provide further details.
Loading and transporting items from the depot to different customers are practical problems that are regularly encountered within the logistics industry. The loading problem can be extended to the BBP. When taking into account the number of dimensions that are relevant to the problem, packing problems are classified into 2D and 3D problems. The first related problem is the 2D-BPP (Zang et al. 2017; Wei et al. 2018; Sbai and Krichen 2019) where both items and bins are rectangular and the aim is to pack all items, without overlap, into the minimum number of bins. The second one is the 3D-BPP (Araujo et al. 2019; Pugliese et al. 2019); this consists of finding an efficient and accurate way to place 3D rectangular goods into the minimum number of 3D containers (bins), while ensuring goods are housed completely within the containers.
In recent years, some researchers have focused on the combined routing and loading problem. The combinatorial problem includes the 2D loading VRP, denoted as 2L-CVRP and the 3D loading VRP, denoted as 3L-CVRP. The purpose of addressing these problems is to minimize the overall travel costs associated with all the routes that serve each of the customers, as well as to satisfy all the constraints of the loading dimensions. The two problems are solved by exact and metaheuristic algorithms which are reviewed in detail in the sections that follow. For further information, we refer the reader to Pollaris et al. (2015) and Iori and Martello (2010), wherein detailed surveys are presented in relation to vehicle routing with packing problems.
This chapter is organized as follows: section 1.2 provides an overview of the literature concerning VRPs in combination with 2D loading problems and the existing variants and constraints. Section 1.3 focuses on VRPs with 3D loading problems and the existing variants and constraints. Finally, in section 1.4, we close with conclusions and opportunities for further research.
1.2. The capacitated vehicle routing problem with two-dimensional loading constraints
The 2L-CVRP is a variant of the classical CVRP characterized by the two-dimensionality of customer demand. The problem aims to serve a set of customers using a homogeneous fleet of vehicles with minimum total cost. The 2D loading constraints must be respected.
The 2L-CVRP is available in a set of real-life problems (Sbai et al. 2020b), for example household appliances and professional cleaning equipment. Table 1.1 presents a comparative study of the existing literature for the 2L-CVRP, which includes solution methods, variants and constraints.
Table 1.1. Comparative study of the 2L-CVRP
Author
Problem
Routing problem Solution methods
Loading problem Solution methods
lori et al. (2007)
Gendreau et al. (2008)
Fuellerer et al. (2009)
Zachariadis et al. (2009)
2L-CVRP
2L-CVRP
2L-CVRP
2L-CVRP
Branch-and-cut TS
ACO GTS
Branch-and-bound
LH2SL, LH2U L
LB, Branch and Bound Bottom-Left Fill (L,W axis) Max Touching Perimeter
Max Touching Perimeter No Walls Min Area
Bottom-Left Fill(L,W axis) Max Touching Perimeter
Max Touching Perimeter No Walls Min. Area
LBFH GRASP-ELS PRMP
Leung et al. (2011)
2L-CVRP
EGTS
Duhamel et al. (2011)
Zachariadis et al. (2013)
Wei et al. (2015)
Wei et al. (2017)
Sbai et al. (2020b)
Leung et al. (2013)
2L-CVRP
2L-CVRP
2L-CVRP
2L-CVRP
2L-CVRP
2L-HFVRP
GRASP-ELS
LS
VNS SA GA
SAHLS
Skyline heuristic
Open space based heuristic ALWF
Bottom-Left Fill (L,W axis) Max. Touching Perimeter
Max. Touching Perimeter
No Walls Min. Area
Max. fitness value
Bottom-Left Fill (L,W axis)
Max Touching Perimeter
Max. Touching Perimeter
No Walls Min. Area
Max. fitness value Lower
Bound
L-cuts MA ALWF ILP
GVNS BLH
Best-Fit LS
VNS VNS LS
Bottom-Left
Heuristics
Sabar et al. (2020)
2L-HFVRP
MA
Cote et al. (2013)
Cote et al. (2020)
Khebbache-Hadji et al. (2013)
Sbai et al. (2017)
Attanasio et al. (2007)
Song et al. (2019)
Pinto et al. (2015)
Dominguez et al. (2016)
Zachariadis et al. (2017)
Pinto et al. (2017)
Pinto et al. (2020)
Zachariadis et al. (2016)
Malapert et al. (2008)
S2L-CVRP S2L-CVRP 2L-CVRPTW
2L-CVRPTW
2L-CVRPTW
2L-CVRPTW
2L-VRPMB
2L-VRPB
2L-VRPB
2L-SPD
2L-VRPB
2L-VRPMB
2L-SPD
2L-VRPPD
L-Cuts L-Cuts MA GA ILP
GVNS
Insert-heur
LNS
Touch-Per LS
VNS VNS LS
Scheduling based-model
1.2.1. Solution methods
The 2L-CVRP is an NP-hard problem, it is solved by exact, heuristic and metaheuristic algorithms:
Iori et al. (2007) use the first exact algorithm for solving small-scale instances of the 2L-CVRP and only for the sequential variant. They proposed a branch-and-cut approach for the routing problem and branch-and-bound for the packing problem.
Gendreau et al. (2008) use a Tabu search (TS) metaheuristic algorithm. They considered two loading heuristics for the sequential and unrestricted case, known as the LH2S L and the LH2U L.
Zachariadis et al. (2009) propose another metaheuristic algorithm which integrates TS and guided local search, referred to as GTS. For the loading problem, they used five packing heuristics and three neighborhood searches to generate the initial solution, namely: customer relocation, route exchange and route interchange.
Fuellerer et al. (2009) present an algorithm based on ant colony optimization (ACO) while bottom-left-fill and touching perimeter algorithms are proposed for solving the packing problem.
Leung et al. (2011) propose an extended guided Tabu search (EGTS) algorithm for the routing problem and a lowest line best-fit heuristic (LBFH) to solve 2D-BPP.
Duhamel et al. (2011) use the greedy randomized adaptive search procedure and the evolutionary local search algorithm, denoted GRASP-ELS.
Leung et al. (2013) study the heterogeneous fleet vehicle routing problem (2L-HFVRP). They propose six packing heuristics to check the feasibility of loading (presented in Table 1.1) and simulated annealing with a...
