PhD Thesis Proposal: Parallel hybrid metaheuristics on GPU
Forum 'Emplois' - Sujet créé le 2013-05-10 par Lhassane Idoumghar
• Title: Parallel hybrid metaheuristics on GPU
• Supervizors: Lhassane IDOUMGHAR and Julien LEPAGNOT
• Contacts: lhassane.idoumghar@uha.fr, julien.lepagnot@uha.fr
• Location: LMIA Laboratory, Université de Haute Alsace
• Expected start time: October 2013
• Duration: 36 months
• Application deadline: 15th of July 2013
• Keywords: metaheuristics, GPU programming optimization, distributed computing
• Funding: French Government Research Grant (approximately 1300€ net per month including French health care coverage).
Context
The design of efficient methods for combinatorial optimization is a key issue for many industrial sectors (automotive, aerospace, broadcasting, etc.). Indeed, more and more efficient heuristics and exact methods have been proposed in recent years, enabling the resolution of many difficult problems.
Metaheuristics, such as evolutionary algorithms, particle swarm optimization and ant colony optimization, have been successfully used to solve many hard problems. It is an interesting approach to tackle high-dimensional problems. In the literature, a large and well-diversified set of metaheuristics has been proposed over the years, enabling the resolution of a wide range of problems.
To take advantage of this diversity, hybrid metaheuristics have been proposed. In this new class of algorithms, a smart combination of different optimization methods is used. Such hybridizations can be used to take advantage of strengths from different algorithms. Several examples in the literature show that hybrid metaheuristics can provide a more robust and efficient problem-solving, especially for real-world and large-scale problems.
However, this kind of hybridizations is mainly achieved statically and the parameter setting is performed experimentally. To overcome this limitation, we first need to define a proper set of hybridization parameters (how to combine two approaches, when to instantiate a particular approach, etc.). We wish through this thesis to answer these questions, which can help in the design of hybrid metaheuristics, and lead in term to advanced adaptive hybrid metaheuristics (using dynamic and adaptive hybridization).
Recently, graphics processing units (GPU) have emerged as a new popular support for massively parallel computing, mainly thanks to the publication of the CUDA development toolkit. The algorithms developed during this thesis will exploit a GPU cluster (a computer cluster in which each node is equipped with a GPU), through the use of GPGPU. This cluster provides the significant computing power required by these algorithms, especially if they are used to solve problems that require high computational capabilities.
Objective
Development of a library of massively parallel hybrid metaheuristics for single-objective/multi-objective optimization.
Work plan
- First step: consists in
• studying the evolution of the search process of hybrid metaheuristics ;
• extracting useful information that will help us hybridizing metaheuristics.
- Second step: consists in studying two problems currently treated in our team: the design of an electric motor and the structural resolution of new zeolites. The goal of this study is to determine and propose a classification of the different parameters to be optimized.
- Third step: consists in integrating the knowledge acquired on these problems in order to refine the exploration process used to find better solutions.
Working Conditions
The developed algorithms will be validated using a GPU cluster composed of 12 computers equipped with GTX 680 cards. This cluster is funded by the Scientific Council of University of Haute Alsace.
Prerequisites
• The applicant must hold a Master or equivalent in Computer Science or Applied Mathematics;
• He should have a strong background in GPU programming, metaheuristics and optimization;
• The applicant must speak English fluently;
• He should have good programming skills (programming language: C++).
Application
Candidates should submit the following documents:
• Motivation letter;
• Curriculum vitae;
• List of publications (if available);
• Copies of diplomas;
• University transcript.
• Supervizors: Lhassane IDOUMGHAR and Julien LEPAGNOT
• Contacts: lhassane.idoumghar@uha.fr, julien.lepagnot@uha.fr
• Location: LMIA Laboratory, Université de Haute Alsace
• Expected start time: October 2013
• Duration: 36 months
• Application deadline: 15th of July 2013
• Keywords: metaheuristics, GPU programming optimization, distributed computing
• Funding: French Government Research Grant (approximately 1300€ net per month including French health care coverage).
Context
The design of efficient methods for combinatorial optimization is a key issue for many industrial sectors (automotive, aerospace, broadcasting, etc.). Indeed, more and more efficient heuristics and exact methods have been proposed in recent years, enabling the resolution of many difficult problems.
Metaheuristics, such as evolutionary algorithms, particle swarm optimization and ant colony optimization, have been successfully used to solve many hard problems. It is an interesting approach to tackle high-dimensional problems. In the literature, a large and well-diversified set of metaheuristics has been proposed over the years, enabling the resolution of a wide range of problems.
To take advantage of this diversity, hybrid metaheuristics have been proposed. In this new class of algorithms, a smart combination of different optimization methods is used. Such hybridizations can be used to take advantage of strengths from different algorithms. Several examples in the literature show that hybrid metaheuristics can provide a more robust and efficient problem-solving, especially for real-world and large-scale problems.
However, this kind of hybridizations is mainly achieved statically and the parameter setting is performed experimentally. To overcome this limitation, we first need to define a proper set of hybridization parameters (how to combine two approaches, when to instantiate a particular approach, etc.). We wish through this thesis to answer these questions, which can help in the design of hybrid metaheuristics, and lead in term to advanced adaptive hybrid metaheuristics (using dynamic and adaptive hybridization).
Recently, graphics processing units (GPU) have emerged as a new popular support for massively parallel computing, mainly thanks to the publication of the CUDA development toolkit. The algorithms developed during this thesis will exploit a GPU cluster (a computer cluster in which each node is equipped with a GPU), through the use of GPGPU. This cluster provides the significant computing power required by these algorithms, especially if they are used to solve problems that require high computational capabilities.
Objective
Development of a library of massively parallel hybrid metaheuristics for single-objective/multi-objective optimization.
Work plan
- First step: consists in
• studying the evolution of the search process of hybrid metaheuristics ;
• extracting useful information that will help us hybridizing metaheuristics.
- Second step: consists in studying two problems currently treated in our team: the design of an electric motor and the structural resolution of new zeolites. The goal of this study is to determine and propose a classification of the different parameters to be optimized.
- Third step: consists in integrating the knowledge acquired on these problems in order to refine the exploration process used to find better solutions.
Working Conditions
The developed algorithms will be validated using a GPU cluster composed of 12 computers equipped with GTX 680 cards. This cluster is funded by the Scientific Council of University of Haute Alsace.
Prerequisites
• The applicant must hold a Master or equivalent in Computer Science or Applied Mathematics;
• He should have a strong background in GPU programming, metaheuristics and optimization;
• The applicant must speak English fluently;
• He should have good programming skills (programming language: C++).
Application
Candidates should submit the following documents:
• Motivation letter;
• Curriculum vitae;
• List of publications (if available);
• Copies of diplomas;
• University transcript.