Khalifa University’s EBTIC Developed Hybrid Algorithms Capable of Solving Complex Computer Science Optimization Problems at Genetic and Evolutionary Computations Conference 2019
An algorithm developed by Khalifa University’s Emirates ICT Innovation Center (EBTIC), which is a key part of Khalifa University’s new Artificial Intelligence Institute, together with Spain’s University of Basque Country recently finished 3rd in a prestigious competition at the Genetic and Evolutionary Computations Conference (GECCO) 2019, held in Prague in July 2019.
The developed algorithm was designed to solve a complex multi-objective optimization problem known as Travelling Thief Problem (TTP) – a combination of the “Travelling Salesman Problem” and the “Knapsack Problem” – two classic algorithmic problems in the field of computer science and operations research. Dr. Sid Shakya, EBTIC Chief Researcher, and Dr. Roberto Santana, researcher from the University of Basque Country and an EBTIC fellow, proposed a robust multi-objective method to solve the problem.
The pair’s solution was based on a combination of two artificial intelligence (AI) methods, known as dynamic programming and evolutionary multi-objective optimization, which maximize the coverage of possible solutions for meeting two conflicting objectives related to the Travelling Salesman Problem and the Knapsack Problem.
The Traveling Salesman Problem involves finding the shortest possible route between a set of cities, where every city is visited exactly once before returning to the starting point. The Knapsack Problem involves determining the number of items to include in a collection (given a set of items, each with a weight and a value) so that the total weight is less than or equal to a given limit and the total value is as large as possible. Both are problems in combinatorial optimization – where you must find the “optimal” solution from a finite but very large set of possible solutions.
Problems like these arise frequently in real world settings. The number of possible solutions grows rapidly with the size of the input to the problem, making it impractical to apply an exhaustive search of potential solutions. The aim of combinatorial optimization is to develop hybrid algorithms capable of exploring numerous potential solutions.
“We designed specific variation operators, which were applied as part of a hybrid multi-objective evolutionary search. The high computational cost of the optimization problem was addressed using an efficient evaluation scheme that reuses partial evaluations of the solution,” Dr. Shakya explained.
“This resulted in a competitive solution of high-dimensional TTP instances that was able to outperform some of the latest known solutions. One of the key motivations for this work was to address other real-word multi-component optimization problems, such as enterprise planning, scheduling and allocation problems, which are part of some of the core research focus areas at EBTIC and its partner organizations,” he added.
GECCO is a premier AI conference for optimization, with a key focus on evolutionary algorithms. It attracts high quality research from top AI institutions working in the area of search heuristics and computational optimization.
Erica Solomon
Senior Editor
15 August 2019
