|
|
|
|
[an error occurred while processing this directive]
Overview of My Research
Some quick background: There are two extremes for attacking NP-hard COPs. The first extreme uses exact methods such as: Branch and Bound, which requires exponential computing time. In practice, for large problem size, exact methods generally unable to produce any results in reasonable time. We adopt the second extreme which uses non-exact methods. These methods are called Stochastic Local Search/Metaheuristic. SLS algorithms do not guarantee optimality of the solutions found, but in practice, they usually manage to obtain good results within reasonable computing time. SLS algorithms are gaining popularity in recent years. The performance of such SLS algorithm for a given NP-hard COP depends on many factors. If designed wrongly or without proper tuning, the performance of SLS algorithms are generally "poor", at best "average". The problem is, there is no proper guiding rules on how to properly design and tune the SLS algorithms yet... This is what I termed as: "SLS Design and Tuning Problem". This problem is mainly encountered within researchers and practitioners every time they implement an SLS algorithm to attack a COP. Typically, the development time required to tune the SLS algorithm is far exceeding the time required to implement the algorithm itself. Therefore, if we have a better way to conduct the design and tuning process, a lot of SLS algorithm development time can be saved. However, this problem has many subtleties and obviously not easy. To date, I have surveyed several 'types' of design and tuning problem as well as looking through at proposed methodologies or tools to these types. Yet I do not feel that this design and tuning problem is 'solved' yet. Currently, I am attempting a collaboration between human and computer, the integrated white+black-box approach (Halim et al., 2007), to help speeding up this complex tuning process. Human can interact with information in a way that permits humans to spot interesting signs in massive data sources. This capability may be useful for spotting interesting information occurred during the execution of the SLS algorithm itself. This step, understanding what is going on during the algorithm runs, is a necessary step before we update the design of the algorithm or to focus the SLS configuration space into a narrower one. Then, we combine our approach with the existing black-box tuning algorithm to achieve even better results. In order for human (algorithm designer) to properly tune his SLS algorithms, I have created an offline all-in-one SLS engineering suite Viz (Halim et al., 2006a, Halim et al., 2006b, Halim and Yap, 2007) --- extension of V-MDF (Visualizer for Metaheuristics Development Framework) (Lau et al., 2005, Halim and Lau, 2007). This visualization tool Viz has been presented to several conferences and workshops, and it has received positive feedbacks. Viz version 2 is now ready for public usage and can be downloadable for free from this page. At this current stage (mid 2008), I am focusing my research to analyze, design, and tune various SLS implementations on hard COPs. One successful example is with LABS problem (Halim et al. 2008). The approach that I have adopted requires familiarity with various aspects: the information visualization part (User Interface design, Computer Graphics, Statistical techniques to present data, etc), the optimization part (various Stochastic Local Search/Metaheuristic algorithms), as well as the connecting fields of study: Human Factors, Human Computer Interaction (HCI). Hopefully (this is my prayer), that during my PhD candidature and beyond, I managed to contribute several things to the stochastic local search/metaheuristics community. =)
About Me
Mr. Steven Halim
National University of Singapore E-mail: stevenha at comp.nus.edu.sg or stevenhalim at gmail.com Steven Halim is a PhD candidate in the School of Computing of the National University of Singapore. He obtained his B.Comp (Hons) from National University of Singapore. Currently, he is doing a direct PhD programme under the supervision from Dr Roland Yap Hock Chuan (School of Computing, National University of Singapore) and Dr Lau Hoong Chuin (School of Information Systems, Singapore Management University). His research interests are: studying various stochastic local search/metaheuristic algorithms (run-time behavior, strengths and weaknesses, suitability in attacking different COPs), information visualization of the statistical data derived from the SLS algorithms, human factors, human computer interaction, and Graphical User Interface (GUI) design. His published works can be found in his self-maintained publication page and also his DBLP page. To date, he has attended several (currently three) international scientific conferences and hopefully few more in the future conferences. He also written a long list of what he has learnt from his PhD candidature so far in his PhD tips. He also likes PhD comics, Dilbert, Foxtrot, Science Cartoon Plus and recommends other graduate students to enjoy reading these comics too. Life as a graduate student will be much easier if you reduce your stress level by reading these comics (on weekly basis). See the following examples and laugh :).
|
