The building deconstruction field is one of the main generators of waste. Although recovery techniques exist to valorize this waste, most of it is lost due to the scant management of waste flows. This study aims to model this sector in order to optimize the various flows emanating from buildings undergoing deconstruction and thus improve the overall recovery rate of the induced waste. Modeling of the deconstruction sector by a bi-level problem hinging on a weighted flexible job shop problem (FJSP) evaluated by a non-regular criterion is propounded. A hybrid resolution method based on a genetic algorithm is introduced. A new encoding, taking account of machine idle times, and its associated genetic operators are proposed. Two resolution approaches for the lower-level problem are assessed. Experiments are carried out on simulated but realistic datasets. The first results exhibit the potential of the proposed resolution method.

The early identification of the patients’ hospitalization at triage level within the Emergency Department (ED) presents a potential solution to reduce the risk of overcrowding and improve the quality of care. Thus, predicting patient out-come on arrival assists medical staff in the make of the appropriate patient pathway decision and so reduces the risk of medical error and complication of the patient’s condition. Previous works don’t consider the uncertainty of medical data while the management of this uncertainty is one of the most important and crucial tasks of medical information systems. Thus, we present in this paper an improved version of the classical prediction model by taking into account the uncertainty and by managing properly the missing information. In this context, we propose a new approach based on Dempster-Shafer theory and Dynamic Multi-Layer Perceptron algorithm. Our proposed approach deploys the correspondent neural network as follows: 1) computes for each input parameter the Basic Belief Assignment (BBA) that provides an assessment of the uncertainty pattern using the Dempster’s rule; 2) deduces the correspondent weights based on the computed BBA, and 3) uses an appropriate transfer function to activate the next layer neurons. In this paper, we demonstrate the effectiveness of our proposed method by using a real ED database. We prove that our proposed approach manages efficiently the uncertainty of the medical data sources and missing information, so improves the decision making and reduces errors and complexity.

We address the problem of biclustering on heterogeneous data, that is, data of various types (binary, numeric, symbolic, temporal). We propose a new method, HBC-t (Heterogeneous BiClustering for temporal data), designed to extract biclusters from heterogeneous, temporal, large-scale, sparse data matrices. HBC-t is based on HBC, using similar mechanisms but adding support for temporal data. The goal of this method is to handle Electronic Health Records (EHR) data gathered by hospitals on patients, stays, acts, diagnoses, prescriptions, etc.; and to provide valuable insights on this data. Temporal data accounts for a majority of the data available for this study, and in EHR in general where medical events are timestamped. Therefore, it is crucial to have an algorithm that supports this type of data. The proposed algorithm takes advantage of the data sparsity and uses a constructive greedy heuristic to build a large number of possibly overlapping biclusters. HBC-t is successfully compared with several other biclustering algorithms on numeric and temporal data. Experiments on full-scale real-life data sets further assert its scalability and efficiency.

This paper describes the concept and implementation of a multi-objective approach for professional training scheduling problem at Mandarine Academy. We address the timetabling of courses and trainers rostering in a highly constrained environment, in which we are required to optimize 5 different objectives. We describe the problem by providing a mathematical formulation of both hard/soft constraints and objectives. We propose the use of Multi-Objective Evolutionary Algorithms (MOEA's) like NSGA II and NSGA III with custom genetic operators (Mutation and Crossover) designed specifically for this problem. To evaluate the effectiveness of our approach, a parameter tuning phase using the i-race package is performed, followed by a performance comparison using real-world test instances varying in complexity. Final results shows a significant improvement in terms of computation time and solutions diversity with an interesting performance gap between NSGA II and NSGA III.

In the domain of partial classification, recent studies about multiobjective local search (MOLS) have led to new algorithms offering high performance, particularly when the data are imbalanced. In the presence of such data, the class distribution is highly skewed and the user is often interested in the least frequent class. Making further improvements certainly requires exploiting complementary solving techniques (notably, for the rule mining problem). As Constraint Programming (CP) has been shown to be effective on various combinatorial problems, it is one such promising complementary approach. In this paper, we propose a new hybrid combination, based on MOLS and CP that are quite orthogonal. Indeed, CP is a complete approach based on powerful filtering techniques whereas MOLS is an incomplete approach based on Pareto dominance. Experimental results on real imbalanced datasets show that our hybrid approach is statistically more efficient than a simple MOLS algorithm on both training and tests instances, in particular, on partial classification problems containing many attributes.

Nowadays Automated Machine Learning, abbreviated AutoML, is recognized as a good solution to quickly find a model without spending too much time on the tedious task of selecting an algorithm and its associated hyperparameters. AutoML is well studied on traditional classification problems but has never been explored on Time Series Classification (TSC) problems. Yet, we show in this article that this problem is different enough to require specific approaches. Indeed, while the preprocessing phases need to be defined with classical ML algorithms, most of them are embedded within the algorithms for TSC. This particularity is mainly due to the fact that we are dealing with ordered data. Over the last decade, there has been a lot of interest for this problem and many new ML algorithms oriented toward TSC (ML-TSC) have blossomed. A practitioner facing a TSC use case, and searching for the most adequate algorithm now has a wide range of options, and will generally end up trying a few algorithms with standard hyperparameters, similarly to what happens in classical ML. Clearly, this is suboptimal. In this article we propose an AutoML solution called AutoTSC based on Evolutionary Algorithms (EAs) and its associated ML-TSC search space. AutoTSC, when tested against standard datasets from the UCR archive, outperforms both a Random Search on the proposed search space and TPOT a well known standard AutoML tool.

This study proposes a novel multi-objective integer programming model for a collision-free discrete drone path planning problem. Considering the possibility of bypassing obstacles or flying above them, this study aims to minimize the path length, energy consumption, and the accumulated maximum path risk simultaneously. The static environment is represented as 3D grid cells. Due to the NP-hardness nature of the problem, several state-of-the-art evolutionary multi-objective optimization (EMO) algorithms with customized crossover and mutation operators are applied to find a set of non-dominated solutions. The results show the effectiveness of applied algorithms in solving several generated test cases.

Classification problems can be modeled as multi-objective optimization problems. MOCA-I is a multi-objective local search designed to solve these problems, particularly when the data are imbalanced. However, this algorithm has been tuned by hand in order to be efficient on particular datasets. In this paper, we propose a methodology to automatically conFigure a multi-objective algorithm for solving a supervised partial classification problem. This methodology is based on a multi-objective approach of automatic algorithm configuration and requires a clear definition of the experimental protocol. Therefore, we present a k-fold cross-validation protocol to train and test the configuration model. To the best of our knowledge, it is the first time that multi-objective automatic algorithm configuration is performed on optimization algorithms to solve classification problems. Experimental results on real imbalanced datasets show that our approach can find efficient configurations of MOCA-I with less effort in comparison with the ones found exhaustively by hand.

This paper considers multiobjective UAV path planning in a real 3D environment with the objective to find a safe energy-efficient path. An Enhanced Non-dominated Sorting Genetic Algorithm-II, called ENSGA-II, is proposed and combines several sorts of heuristic information to customize crossover and mutation operators. Furthermore, a local search and a ranking-based roulette wheel selection are incorporated for the mating procedure. Experiment results confirm that ENSGA-II has a better convergence rate and spread of solutions on several new real-world datasets. The effectiveness of the local search component is also validated on the CrazyS robot operating system (ROS) package which consists of a pelican quadcopter's modeling.

In solving combinatorial problems, the advent of multi-core machines has led to the development of new parallel methods offering higher performance as well as better solutions. However, finding the best parallel algorithm on such architectures for a given problem and programming these methods are still challenging tasks today. As a matter of fact, only a few parallel solvers have been designed so far to tackle multi-objective combinatorial optimisation problems. Therefore this paper first proposes a new highly parametric multi-thread and multiobjective local search algorithm dedicated to tackling optimisation problems. Specifically, this new parallel solver incorporates and combines most of methods available in the literature, such as single-walk and multi-walk parallel local search, which can be independent of each other or cooperative by sharing some solutions. In addition, this solver is also capable of making some innovative hybridisations by mixing both single-walk and multi-walk approaches. The major problem is that it then becomes very difficult, if not impossible, for a human expert to determine the best configurations. This obstacle is due to the fact that the number of parameters in parallel methods is excessively too large. Indeed, all configuration possibilities include the combination of two kinds of parameters. The first ones are the parameters of the sequential algorithms within the parallel solver for multi-walk-based methods. The second ones are those controlling the main parallel components such as hybridisation, diversification or choice of communications. Fortunately, automatic algorithm configuration allows this problem to be taken into account. Thus, we use a configurator especially designed for multi-objective problems called MO-ParamILS in order to expose some best parallel configurations for the bi-objective travelling salesman problem.

Data are omnipresent nowadays and contain knowledge and patterns that machine learning (ML) algorithms can extract so as to take decisions or perform a task without explicit instructions. To achieve that, these algorithms learn a mathematical model using sample data. However, there are numerous ML algorithms, all learning different models of reality. Furthermore, the behavior of these algorithms can be altered by modifying some of their plethora of hyperparameters. Cleverly tuning these algorithms is costly but essential to reach decent performance. Yet it requires a lot of expertise and remains hard even for experts who tend to resort to exploration-only approaches like random search and grid search. The field of AutoML has consequently emerged in the quest for automatized machine learning processes that would be less expensive than brute force searches. In this paper we continue the research initiated on the Tree-based Pipeline Optimization Tool (TPOT), an AutoML based on Evolutionary Algorithms (EA). EAs are typically slow to converge which makes TPOT incapable of scaling to large datasets. As a consequence, we introduce TPOT-SH inspired from the concept of Successive Halving used in Multi-Armed Bandit problems. This solution allows TPOT to explore the search space faster and have much better performance on larger datasets.

Automatic algorithm configuration (AAC) is becoming a key ingredient in the design of high-performance solvers for challenging optimisation problems. However, most existing work on AAC deals with configuration procedures that optimise a single performance metric of a given, single-objective algorithm. Of course, these configurators can also be used to optimise the performance of multi-objective algorithms, as measured by a single performance indicator. In this work, we demonstrate that better results can be obtained by using a native, multi-objective algorithm configuration procedure. Specifically, we compare three AAC approaches: one considering only the hypervolume indicator, a second optimising the weighted sum of hypervolume and spread, and a third that simultaneously optimises these complementary indicators, using a genuinely multi-objective approach. We assess these approaches by applying them to a highly-parametric local search framework for two widely studied multi-objective optimisation problems, the bi-objective permutation flowshop and travelling salesman problems. Our results show that multi-objective algorithms are indeed best configured using a multi-objective configurator.

Multi-objective optimisation algorithms expose various parameters that have to be tuned in order to be efficient. Moreover, in multi-objective optimisation, the correlation between objective functions is known to affect search space structure and algorithm performance. Considering the recent success of automatic algorithm configuration (AAC) techniques for the design of multi-objective optimisation algorithms, this raises two interesting questions: what is the impact of correlation between optimisation objectives on (1) the efficacy of different AAC approaches and (2) on the optimised algorithm designs obtained from these automated approaches? In this work, we study these questions for multi-objective local search algorithms (MOLS) for three well-known bi-objective permutation problems, using two single-objective AAC approaches and one multi-objective approach. Our empirical results clearly show that overall, multi-objective AAC is the most effective approach for the automatic configuration of the highly parametric MOLS framework, and that there is no systematic impact of the degree of correlation on the relative performance of the three AAC approaches. We also find that the best-performing configurations differ, depending on the correlation between objectives and the size of the problem instances to be solved, providing further evidence for the usefulness of automatic configuration of multi-objective optimisation algorithms.

Multi-objective local search (MOLS) algorithms are efficient meta-heuristics, which improve a set of solutions by using their neighbourhood to iteratively find better and better solutions. MOLS algorithms are versatile algorithms with many available strategies, first to select the solutions to explore, then to explore them, and finally to update the archive using some of the visited neighbours. In this paper, we propose a new generalisation of MOLS algorithms incorporating new recent ideas and algorithms. To be able to instantiate the many MOLS algorithms of the literature, our generalisation exposes numerous numerical and categorical parameters, raising the possibility of being automatically designed by an automatic algorithm configuration (AAC) mechanism. We investigate the worth of such an automatic design of MOLS algorithms using MO-ParamlLS, a multi-objective AAC configurator, on the permutation flowshop scheduling problem, and demonstrate its worth against a traditional manual design.

There is a significant body of research on neutrality and its effects in single-objective optimization. Particularly, the neutrality concept has been precisely defined and the neutrality between neighboring solutions efficiently exploited in local search algorithms. The extension of neutrality to multi-objective optimization is not straightforward and its effects on the dynamics of multi-objective optimization methods are not clearly understood. In order to develop strategies to exploit neutral neighbors in multi-objective local search algorithms, it is important and necessary to clearly define neutrality in the multi-objective context. In this paper, we propose several definitions of the neutrality property between neighboring solutions. A natural definition comes from the Pareto-dominance, widely used in multi-objective optimization. In addition, definitions derived from epsilon and hypervolume indicators are also proposed as such indicators are usually used to compare sets of solutions. We analyze permutation problems under the proposed definitions of neutrality and show that each definition of neutrality leads to a particular structure of the problem.

A large number of rule interestingness measures have been used as objectives in multi-objective classification rule mining algorithms. Aggregation or Pareto dominance are commonly used to deal with these multiple objectives. This paper compares these approaches on a partial classification problem over discrete and imbalanced data. After performing a Principal Component Analysis (PCA) to select candidate objectives and find conflictive ones, the two approaches are evaluated. The Pareto dominance-based approach is implemented as a dominance-based local search (DMLS) algorithm using confidence and sensitivity as objectives, while the other is implemented as a single-objective hill climbing using F-Measure as an objective, which combines confidence and sensitivity. Results shows that the dominance-based approach obtains statistically better results than the single-objective approach.

Biclustering is a well-known data mining problem in the field of gene expression data. It consists in extracting genes that behave similarly under some experimental conditions. As the Biclustering problem is NP-Complete in most of its variants, many heuristics and metaheuristics are defined to solve for it. Classical algorithms allow the extraction of some biclusters in reasonable time, however most of them remain time consuming. In this work, we propose a new hybrid multi-objective meta-heuristic H-MOBI based on NSGA-II (Non-dominated Sorting Genetic Algorithm II), CC (Cheng and Church) heuristic and a multi-objective local search PLS-1 (Pareto Local Search 1). Experimental results on real data sets show that our approach can find significant biclusters of high quality.

Microarrays are a powerful tool in studying genes expressions under several conditions. The obtained data need to be analyzed using data mining methods. Biclustering is a data mining method which consists in simultaneous clustering of rows and columns in a data matrix. Using biclustering, we can extract genes that have similar behavior (co-express) under specific conditions. These genes may share identical biological functions. The aim in analyzing gene expression data is the extraction of maximal number of genes and conditions that present similar behavior. The two objectives to be optimized (size and similarity) are conflicting. Therefore, multi-objective optimization is suitable for biclustering. In our work, we combine a well-known multi-objective genetic algorithm (NSGA-II) with a heuristic to solve the biclutering problem. Due to the huge size of the datasets, we use a string of integers as a solution representation where integers represent the indexes of the rows and the columns. Experimental results on real data set show that our approach can find significant biclusters of high quality.

VEGAS (Varying Evolvability-Guided Adaptive Search) is a new methodology proposed to deal with the neutrality property that frequently appears on combinatorial optimization problems. Its main feature is to consider the whole evaluated solutions of a neutral network rather than the last accepted solution. Moreover, VEGAS is designed to escape from plateaus based on the evolvability of solutions, and on a multi-armed bandit by selecting the more promising solution from the neutral network. Experiments are conducted on NK-landscapes with neutrality. Results show the importance of considering the whole identified solutions from the neutral network and of guiding the search explicitly. The impact of the level of neutrality and of the exploration-exploitation trade-off are deeply analyzed.

Usually, the combinatorial optimization problems are modeled in a static way. All data are known in advance, i.e., before the optimization process has started. But in practice, many problems are dynamic, and change during the time. For the Dynamic Vehicle Routing Problem (DVRP), new orders arrive when the working day plan is in progress. Thus, the routes must be reconfigured dynamically during the optimization process. The Particle Swarm Optimization has been previously used to solve continuous dynamic optimization problems, whereas only, few works were proposed for combinatorial ones. In this paper, we present an Adaptive Particle Swarm for solving the Vehicle Routing Problem with Dynamic Requests (VRPDR). The effectiveness of this approach is evaluated thanks to a well-known set of benchmarks. It is compared with different population based metaheuristics, and a single-solution based metaheuristic. Experimental results show that our approach may significantly decrease travel distances, and is adaptive with respect to dynamic environment.

Vehicle Routing Problems (VRP) are widely studied as they represent challenges for the future. However, most of the routing problems encountered in the literature are quite far from real life problems. Therefore, this work will be dedicated to the Heterogeneous Fixed Fleet Asymmetric Vehicle Routing Problem (HFF-AVRP), a variant of the VRP, which is more common in real life distribution management than the basic VRP. HFF-AVRP is a NP-hard combinatorial optimization problem. Heuristics and in particular meta-heuristics are then candidate methods to solve such problems. As these methods are very sensitive to neighborhoods, we propose in this article to examine two classical neighborhoods associated to this problem in order to analyze their performances.

In real life optimization problems, it is very important to have high quality solutions (optimal). But when uncertainty becomes part of the optimization problem, solutions should be optimal and robust to the uncertain environmental changes. This paper focuses on finding robust optimal solution for the vehicle routing problem with stochastic demands VRPSD. In this case when the uncertainty of the customers demands enters this problem, the classical methods of VRP can not be used to obtain optimal solutions. We need new methods with new strategies to have robust optimal solution. For that we propose two bi-objective models, depending on the multi-objective evolutionary algorithms MOEAs: IBEA, MOGA and NSGAII. We compare the robustness degree of the two models and also we compare the performance of the three MOEAs over these two models.

In this work we compare the use of a particle swarm optimization (PSO) and a genetic algorithm (GA) (both augmented with support vector machines SVM) for the classification of high dimensional microarray data. Both algorithms are used for finding small samples of informative genes amongst thousands of them. A SVM classifier with 10-fold cross-validation is applied in order to validate and evaluate the provided solutions. A first contribution is to prove that PSOSVMis able to find interesting genes and to provide classification competitive performance. Specifically, a new version of PSO, called geometric PSO, is empirically evaluated for the first time in this work. In this sense, a comparison of this approach with a new GASVMand also with other existing methods of literature is provided. A second important contribution consists in the actual discovery of new and challenging results on six public datasets identifying significant in the development of a variety of cancers (leukemia, breast, colon, ovarian, prostate, and lung).

Molecular docking is an essential tool for drug design. It helps the scientist to rapidly know if two molecules, respectively called ligand and receptor, can be combined together to obtain a stable complex. We propose a new multi-objective model combining an energy term and a surface term to gain such complexes. The aim of our model is to provide complexes with a low energy and low surface. This model has been validated with two multi-objective genetic algorithms on instances from the literature dedicated to the docking benchmarking.

In this work we compare the use of a particle swarm optimization (PSO) and a genetic algorithm (GA) (both augmented with support vector machines SVM) for the classification of high dimensional microarray data. Both algorithms are used for finding small samples of informative genes amongst thousands of them. A SVM classifier with 10- fold cross-validation is applied in order to validate and evaluate the provided solutions. A first contribution is to prove that PSOsvm is able to find interesting genes and to provide classification competitive performance. Specifically, a new version of PSO, called Geometric PSO, is empirically evaluated for the first time in this work using a binary representation in Hamming space. In this sense, a comparison of this approach with a new GAsvm and also with other existing methods of literature is provided. A second important contribution consists in the actual discovery of new and challenging results on six public datasets identifying significant in the development of a variety of cancers (leukemia, breast, colon, ovarian, prostate, and lung).

No abstract available.

Protein identification is one of the major task of Proteomics researchers. Protein identification could be resumed by searching the best match between an experimental mass spectrum and proteins from a database. Nevertheless this approach can not be used to identify new proteins or protein variants. In this paper an evolutionary approach is proposed to discover new proteins or protein variants thanks a "de novo sequencing" method. This approach has been experimented on a specific grid called Grid5000 with simulated spectra and also real spectra.

In Proteomics, only the de novo peptide sequencing approach allows a partial amino acid sequence of a peptide to be found from a MS/MS spectrum. In this article a preliminary work is presented to discover a complete protein sequence from spectral data (MS and MS/MS spectra). For the moment, our approach only uses MS spectra. A genetic algorithm (GA) has been designed with a new evaluation function which works directly with a complete MS spectrum as input and not with a mass list like the other methods using this kind of data. Thus the mono isotopic peak extraction step which needs a human intervention is deleted. The goal of this approach is to discover the sequence of unknown proteins and to allow a better understanding of the differences between experimental proteins and proteins from databases.

In this article, we present our latest work with a hybrid multiobjective evolutionary algorithm called LEMMO (learnable evolution model for multiobjective optimization) which integrates machine learning into evolutionary search based on Michalski's "LEM" approach. The objective is to both improve the performance of the MOEA and to reduce the number of evaluations needed when used for optimising the design of water distribution networks (where evaluations are highly computationally costly). We compare LEMMO with NSGA-II and conclude that our approach is very promising for improved speed and quality in the water systems optimisation domain.

Summary form only given. We treat the linkage disequilibrium, used to discover haplotypes, candidate to explain multifactorial diseases such as diabetes or obesity, as an optimization problem where a given objective function has to be optimized. In order to determine what kind of algorithm is able to solve this problem, we first study the specificities and the structure of the problem. Results of this study show that exact algorithms are not adapted to this specific problem and lead us to the development of a parallel dedicated adaptive multipopulation genetic algorithm that is able to find several haplotypes of different sizes. After describing the biological problem, we present the dedicated genetic algorithm, its specificities, such as the use of several populations and its advanced mechanisms such as the adaptive choice of operators, random immigrants, and its parallel implementation. We give results on a real dataset.