Understanding What Makes an Optimisation Problem Difficult by Learning from Evolved Instances
Date and time:
04/11/2009, 14:00
Location:
Building: 26, Room: 135, Clayton campus
Presenters:
Professor Kate Smith-Miles, School of Mathematical Sciences, Monash University
Abstract:
A generic answer to the question of what makes an optimisation
problem hard has been elusive, since it is clear that problem specific characteristics determine the intrinsic difficulty of a particular instance of an optimisation problem for a particular algorithm. Consequently, there has been increasing interest in
measuring the characteristics of instances for a given optimisation problem to gain insights into which features of an instance make a particular algorithm perform well or poorly.
Whether the goal is performance prediction, or insights into
the relationships between algorithm performance and instance
characteristics, a comprehensive set of meta-data from which relationships can be learned is needed. In this talk a methodology is proposed to determine if the meta-data is sufficient, and the critical role played by instance generation methods is demonstrated. Instances of the Travelling
Salesman Problem (TSP) are evolved using an evolutionary algorithm to produce distinct classes of instances that are intentionally easy or hard for certain algorithms.
A comprehensive set of features is used to characterise instances
of the TSP, and the impact of these features on difficulty for each algorithm is analysed. Finally, performance predictions are achieved with high accuracy on unseen instances for predicting search effort as well as identifying the algorithm likely to perform best.
Speaker biographies:
Kate Smith-Miles is a Professor and Head of the School of Mathematical Sciences at Monash University in Australia. Prior to commencing this role in January 2009, she held a Chair in Engineering at Deakin University (where she was Head of the School of Engineering and Information Technology from 2006-2008) and was a Professor in Information Technology at Monash University, where she worked from 1996-2006. Her third Chair (in
Mathematical Sciences), demonstrates her multi-disciplinary breadth. Kate obtained a B.Sc(Hons) in Mathematics and a Ph.D. in Electrical Engineering, both from the University of Melbourne, Australia.
She has published 2 books on neural networks and data mining applications, and over 180 refereed journal and international conference papers in the areas of neural networks,
combinatorial optimization, intelligent systems and data mining. She has supervised to completion 16 PhD students, and has been awarded over AUD$1.75 million in competitive grants, including 8 Australian Research Council grants, and other industry awards.
She is on the editorial board of several international journals including IEEE Transactions on Neural Networks, and has been a member of the organizing committee for over 50 international data
mining and neural network conferences, including several as chair. She is a frequent reviewer of international research activities including grant applications in Canada, U.K., Finland, Hong Kong, Singapore and Australia, refereeing for international research journals, and PhD examinations. From 2007-2008 she was Chair of the IEEE Technical Committee on Data Mining (IEEE
Computational Intelligence Society).
She was elected Fellow of the Institute of Engineers Australia (FIEAust) in 2006, and Fellow of the Australian Mathematical Society (FAustMS) in 2008. She has been a Senior Member of the IEEE since 2001. In addition to her academic activities, she also regularly acts as a consultant to industry in the areas of optimisation, data mining,
and intelligent systems.
