Results 1-18 of 18.
((uid:50008504))

Bookmark and Share    
Full Text
Peer Reviewed
See detailA GP Hyper-Heuristic Approach for Generating TSP Heuristics
Duflo, Gabriel UL; Kieffer, Emmanuel UL; Brust, Matthias R. UL et al

in 33rd IEEE International Parallel & Distributed Processing Symposium (IPDPS 2019) (2019, May 20)

Detailed reference viewed: 89 (36 UL)
Full Text
Peer Reviewed
See detailTackling Large-Scale and Combinatorial Bi-level Problems with a Genetic Programming Hyper-heuristic
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in IEEE Transactions on Evolutionary Computation (2019)

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is a NP-hard problem. In this work, we tackle large-scale and combinatorial bi-level problems using GP ... [more ▼]

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is a NP-hard problem. In this work, we tackle large-scale and combinatorial bi-level problems using GP Hyper-heuristics, i.e., an approach that permits to train heuristics like a machine learning model. Our contribution aims at targeting the intensive and complex lower-level optimizations that occur when solving a large-scale and combinatorial bi-level problem. For this purpose, we consider hyper-heuristics through heuristic generation. Using a GP hyper-heuristic approach, we train greedy heuristics in order to make them more reliable when encountering unseen lower-level instances that could be generated during bi-level optimization. To validate our approach referred to as GA+AGH, we tackle instances from the Bi-level Cloud Pricing Optimization Problem (BCPOP) that model the trading interactions between a cloud service provider and cloud service customers. Numerical results demonstrate the abilities of the trained heuristics to cope with the inherent nested structure that makes bi-level optimization problems so hard. Furthermore, it has been shown that training heuristics for lower-level optimization permits to outperform human-based heuristics and metaheuristics which constitute an excellent outcome for bi-level optimization. [less ▲]

Detailed reference viewed: 66 (21 UL)
Full Text
Peer Reviewed
See detailGP hyper-heuristic for the travelling salesman problem
Duflo, Gabriel UL; Kieffer, Emmanuel UL; Danoy, Grégoire UL et al

Scientific Conference (2019, January 29)

Detailed reference viewed: 74 (24 UL)
Full Text
See detailCo-evolutionary Hybrid Bi-level Optimization
Kieffer, Emmanuel UL

Doctoral thesis (2019)

Multi-level optimization stems from the need to tackle complex problems involving multiple decision makers. Two-level optimization, referred as ``Bi-level optimization'', occurs when two decision makers ... [more ▼]

Multi-level optimization stems from the need to tackle complex problems involving multiple decision makers. Two-level optimization, referred as ``Bi-level optimization'', occurs when two decision makers only control part of the decision variables but impact each other (e.g., objective value, feasibility). Bi-level problems are sequential by nature and can be represented as nested optimization problems in which one problem (the ``upper-level'') is constrained by another one (the ``lower-level''). The nested structure is a real obstacle that can be highly time consuming when the lower-level is $\mathcal{NP}-hard$. Consequently, classical nested optimization should be avoided. Some surrogate-based approaches have been proposed to approximate the lower-level objective value function (or variables) to reduce the number of times the lower-level is globally optimized. Unfortunately, such a methodology is not applicable for large-scale and combinatorial bi-level problems. After a deep study of theoretical properties and a survey of the existing applications being bi-level by nature, problems which can benefit from a bi-level reformulation are investigated. A first contribution of this work has been to propose a novel bi-level clustering approach. Extending the well-know ``uncapacitated k-median problem'', it has been shown that clustering can be easily modeled as a two-level optimization problem using decomposition techniques. The resulting two-level problem is then turned into a bi-level problem offering the possibility to combine distance metrics in a hierarchical manner. The novel bi-level clustering problem has a very interesting property that enable us to tackle it with classical nested approaches. Indeed, its lower-level problem can be solved in polynomial time. In cooperation with the Luxembourg Centre for Systems Biomedicine (LCSB), this new clustering model has been applied on real datasets such as disease maps (e.g. Parkinson, Alzheimer). Using a novel hybrid and parallel genetic algorithm as optimization approach, the results obtained after a campaign of experiments have the ability to produce new knowledge compared to classical clustering techniques combining distance metrics in a classical manner. The previous bi-level clustering model has the advantage that the lower-level can be solved in polynomial time although the global problem is by definition $\mathcal{NP}$-hard. Therefore, next investigations have been undertaken to tackle more general bi-level problems in which the lower-level problem does not present any specific advantageous properties. Since the lower-level problem can be very expensive to solve, the focus has been turned to surrogate-based approaches and hyper-parameter optimization techniques with the aim of approximating the lower-level problem and reduce the number of global lower-level optimizations. Adapting the well-know bayesian optimization algorithm to solve general bi-level problems, the expensive lower-level optimizations have been dramatically reduced while obtaining very accurate solutions. The resulting solutions and the number of spared lower-level optimizations have been compared to the bi-level evolutionary algorithm based on quadratic approximations (BLEAQ) results after a campaign of experiments on official bi-level benchmarks. Although both approaches are very accurate, the bi-level bayesian version required less lower-level objective function calls. Surrogate-based approaches are restricted to small-scale and continuous bi-level problems although many real applications are combinatorial by nature. As for continuous problems, a study has been performed to apply some machine learning strategies. Instead of approximating the lower-level solution value, new approximation algorithms for the discrete/combinatorial case have been designed. Using the principle employed in GP hyper-heuristics, heuristics are trained in order to tackle efficiently the $\mathcal{NP}-hard$ lower-level of bi-level problems. This automatic generation of heuristics permits to break the nested structure into two separated phases: \emph{training lower-level heuristics} and \emph{solving the upper-level problem with the new heuristics}. At this occasion, a second modeling contribution has been introduced through a novel large-scale and mixed-integer bi-level problem dealing with pricing in the cloud, i.e., the Bi-level Cloud Pricing Optimization Problem (BCPOP). After a series of experiments that consisted in training heuristics on various lower-level instances of the BCPOP and using them to tackle the bi-level problem itself, the obtained results are compared to the ``cooperative coevolutionary algorithm for bi-level optimization'' (COBRA). Although training heuristics enables to \emph{break the nested structure}, a two phase optimization is still required. Therefore, the emphasis has been put on training heuristics while optimizing the upper-level problem using competitive co-evolution. Instead of adopting the classical decomposition scheme as done by COBRA which suffers from the strong epistatic links between lower-level and upper-level variables, co-evolving the solution and the mean to get to it can cope with these epistatic link issues. The ``CARBON'' algorithm developed in this thesis is a competitive and hybrid co-evolutionary algorithm designed for this purpose. In order to validate the potential of CARBON, numerical experiments have been designed and results have been compared to state-of-the-art algorithms. These results demonstrate that ``CARBON'' makes possible to address nested optimization efficiently. [less ▲]

Detailed reference viewed: 112 (18 UL)
Full Text
Peer Reviewed
See detailA Competitive Approach for Bi-Level Co-Evolution
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (2018, May 25)

Detailed reference viewed: 59 (11 UL)
Full Text
Peer Reviewed
See detailBayesian optimization to enhance coverage performance of a swarm of UAV with chaotic dynamics
Kieffer, Emmanuel UL; Rosalie, Martin UL; Danoy, Grégoire UL et al

Scientific Conference (2018, February 26)

We introduce the optimization of CACOC through Bayesian Optimization. CACOC is based on a chaotic system, i.e. Rossler system whose behavior can be modified by tuning the α parameter. In order to evaluate ... [more ▼]

We introduce the optimization of CACOC through Bayesian Optimization. CACOC is based on a chaotic system, i.e. Rossler system whose behavior can be modified by tuning the α parameter. In order to evaluate the performance of CACOC for different value of α, the coverage metric has to be evaluated after simulation. The latter is time-consuming. Therefore, a surrogate-based optimization, i.e. Bayesian Optimization has been privilegied to tackle this issue. An analysis of the chaotic system with the obtained α value has been performed to compare the periodic orbits and their associated patterns. Numerical results show that the best α value avoid a waste of time in periodic region of the bifurcation diagram. Future works will focus on more complex chaotic system as well as new application domain of the optimized CACOC approach. [less ▲]

Detailed reference viewed: 104 (22 UL)
Full Text
Peer Reviewed
See detailClustering approaches for visual knowledge exploration in molecular interaction networks.
Ostaszewski, Marek UL; Kieffer, Emmanuel UL; Danoy, Gregoire et al

in BMC bioinformatics (2018), 19(1), 308

BACKGROUND: Biomedical knowledge grows in complexity, and becomes encoded in network-based repositories, which include focused, expert-drawn diagrams, networks of evidence-based associations and ... [more ▼]

BACKGROUND: Biomedical knowledge grows in complexity, and becomes encoded in network-based repositories, which include focused, expert-drawn diagrams, networks of evidence-based associations and established ontologies. Combining these structured information sources is an important computational challenge, as large graphs are difficult to analyze visually. RESULTS: We investigate knowledge discovery in manually curated and annotated molecular interaction diagrams. To evaluate similarity of content we use: i) Euclidean distance in expert-drawn diagrams, ii) shortest path distance using the underlying network and iii) ontology-based distance. We employ clustering with these metrics used separately and in pairwise combinations. We propose a novel bi-level optimization approach together with an evolutionary algorithm for informative combination of distance metrics. We compare the enrichment of the obtained clusters between the solutions and with expert knowledge. We calculate the number of Gene and Disease Ontology terms discovered by different solutions as a measure of cluster quality. Our results show that combining distance metrics can improve clustering accuracy, based on the comparison with expert-provided clusters. Also, the performance of specific combinations of distance functions depends on the clustering depth (number of clusters). By employing bi-level optimization approach we evaluated relative importance of distance functions and we found that indeed the order by which they are combined affects clustering performance. Next, with the enrichment analysis of clustering results we found that both hierarchical and bi-level clustering schemes discovered more Gene and Disease Ontology terms than expert-provided clusters for the same knowledge repository. Moreover, bi-level clustering found more enriched terms than the best hierarchical clustering solution for three distinct distance metric combinations in three different instances of disease maps. CONCLUSIONS: In this work we examined the impact of different distance functions on clustering of a visual biomedical knowledge repository. We found that combining distance functions may be beneficial for clustering, and improve exploration of such repositories. We proposed bi-level optimization to evaluate the importance of order by which the distance functions are combined. Both combination and order of these functions affected clustering quality and knowledge recognition in the considered benchmarks. We propose that multiple dimensions can be utilized simultaneously for visual knowledge exploration. [less ▲]

Detailed reference viewed: 75 (17 UL)
Full Text
Peer Reviewed
See detailVisualizing the Template of a Chaotic Attractor
Olszewski, Maya Alexandra UL; Meder, Jeff Alphonse Antoine UL; Kieffer, Emmanuel UL et al

in 26th International Symposium on Graph Drawing and Network Visualization (GD 2018) (2018)

Detailed reference viewed: 64 (17 UL)
Full Text
Peer Reviewed
See detailA new modeling approach for the biobjective exact optimization of satellite payload configuration
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in International Transactions in Operational Research (2017)

Detailed reference viewed: 122 (14 UL)
Full Text
Peer Reviewed
See detailBayesian Optimization Approach of General Bi-level Problems
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in Proceedings of the Genetic and Evolutionary Computation Conference Companion (2017)

Detailed reference viewed: 113 (13 UL)
Full Text
Peer Reviewed
See detailCo-evolutionary approach based on constraint decomposition
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in Co-evolutionary approach based on constraint decomposition (2016, October)

Detailed reference viewed: 100 (11 UL)
Full Text
Peer Reviewed
See detailOn Bi-level approach for Scheduling problems
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL

Scientific Conference (2016, April)

Detailed reference viewed: 79 (13 UL)
Full Text
Peer Reviewed
See detailHybrid mobility model with pheromones for UAV detection task
Kieffer, Emmanuel UL; Danoy, Grégoire UL; Bouvry, Pascal UL et al

in Hybrid mobility model with pheromones for UAV detection task (2016)

Detailed reference viewed: 124 (19 UL)
Full Text
Peer Reviewed
See detailA Novel Co-evolutionary Approach for Constrained Genetic Algorithms
Kieffer, Emmanuel UL; Guzek, Mateusz UL; Danoy, Grégoire UL et al

in Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion (2016)

Detailed reference viewed: 135 (19 UL)
Full Text
Peer Reviewed
See detailBi-objective Exact Optimization of Satellite Payload Power Configuration
Kieffer, Emmanuel UL; Stathakis, Apostolos UL; Danoy, Grégoire UL et al

in VIII ALIO/EURO Workshop on Applied Combinatorial Optimization (2014, December)

Detailed reference viewed: 103 (29 UL)
Full Text
Peer Reviewed
See detailMulti-Objective Evolutionary Approach for the Satellite Payload Power Optimization Problem
Kieffer, Emmanuel UL; Stathakis, Apostolos UL; Danoy, Grégoire UL et al

in IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2014) (2014, December)

Detailed reference viewed: 86 (13 UL)
Full Text
Peer Reviewed
See detailBi-objective Optimization of Satellite Payload Power Configuration
Kieffer, Emmanuel UL; Stathakis, Apostolos UL; Danoy, Grégoire UL et al

in International Conference on Metaheuristics and Nature Inspired Computing (META 2014) (2014, October)

Detailed reference viewed: 81 (17 UL)