Learning from negative examples: application in combinatorial optimization


Prabhas Chongstitvatana

This talk introduces Coincidence Algorithm which is designed for combinatorial optimization.  Coincidence Algorithm (COIN) belongs to the class of Estimation of Distribution Algorithm.  The algorithms in this class use probabilistic models to solve hard problems.  They are considered to be the modern successor of Genetic Algorithms.  The emphasise in this talk is on the use of negative examples in Coincidence Algorithm.  Learning from negative examples helps the algorithm to avoid repeating the mistakes that had already been found.

I will give background about Coincidence Algorithm including its working mechanism. Then I will report the recent result from my research team.  The strength of COIN in solving multimodal puzzles will be demonstrated.  The analysis on the behavior of the algorithm based on what it learn from negative examples is presented.  Some applications in industrial engineering field will be highlighted.

Speaker's biography

Prabhas Chongstitvatana earned B.Eng. in Electrical Engineering from Kasetsart University, Thailand in 1980 and Ph.D. from the department of artificial intelligence, Edinburgh University, U.K. in 1992.  Presently, he is a professor in the department of computer engineering, Chulalongkorn University.  His research includes robotics, evolutionary computation and computer architecture.  He is actively promote the collaboration to create Thai national grid for scientific computing.  He is the lifetime member of Thailand Engineering Institute, Thai Academy of Science and Technology, Thai Robotics Society, Thai Embedded System Association and IEEE Robotics and Automation Society.  Presently he is the president of ECTI Association of Thailand. He has been awarded National Distinguished Researcher, from National Research Council, Thailand in 2009.