Information Science and Biomedical Engineering

Associate professor

Ono, Satoshi

Optimization algorithms inspired by natural evolution

Learn how to solve difficult problems from natural evolution process

Evolution is a process where organisms acquire their traits adapted to the environment by leaving descendants over the years. Evolutionary computation is a problem solving algorithm that imitates the natural evolution process (*1). Normally, a problem is solved by initially designing and gradually improving just one solution candidate to find a good solution. On the other hand, evolutionary computation algorithms generate a number of solution candidates, such as 100 or 1,000, and regard the candidates as virtual creatures. And these creatures create offsprings. When parents having good traits make offsprings, the offsprings may inherit the good traits of the parents and be a better solution candidate. It is expected that an accumulation of such accidental improvements may effectively solve difficult problems. The right figure shows an example process of evolutionary computation that generates decorated QR codes obeying its standards. When you overlay a picture on a QR code, the picture destroys part of the code and makes it difficult to read when it gets stained. On the other hand, the decorative QR code generated by evolutionary computation can create a module pattern that is visually meaningful to humans without sacrificing any of the QR code functions.

Process to design decorated QR code using evolutionary computation

Evolutionary computation algorithms are applicable to various real-world problems

evolutionary 3D image registration that reconstructs an entire object shape from the world's smallest number of measurements

Evolutionary computation is good at solving problems called optimization, and can be applied to various fields such as design, manufacturing, distribution, and finance. Here, we introduce one of our applications to three dimensional (3D) measurements. Generally, when measuring an object using a 3D scanner, it is necessary to measure several times while changing the viewpoint and synthesize the measured partial shapes. The process of aligning the measured 3D shapes is called 3D registration. When using general registration methods, it is necessary to measure four to ten times in order to reconstruct the whole object shape. We developed a new 3D registration algorithm using evolutionary computation. It can find the optimal solution by avoiding falling into local optima (*2), by exploiting the characteristics of evolutionary computation; that is, the property that many solution candidates have simultaneously improved. By incorporating a new objective function (*3) presuming the use of evolutionary computation, the proposed method can reconstruct the entire object shape from the measurement results an extremely small number of times (two or three times, which are the world’s least number of times, to the best of our knowledge).

*1 In particular, evolutionary computation is good at solving optimization problems in which parameters are simultaneously decided so that an objective function should be minimized (or maximized).
*2 Local optima are solutions that have any neighbor better than them.
*3 An objective function is a function that determines how good a solution candidate is.

Profile

Information Science and Biomedical Engineering

Associate professor

Ono, Satoshi

Dr. Satoshi Ono graduated with a Ph.D. in Engineering from University of Tsukuba in 2002, and started working at Kagoshima University in 2003. He became Associate Professor in 2010. His interest is in computer science, artificial intelligence, and evolutionary computation. He is a member of IEEE, Information Processing Society of Japan (IPSJ), the Japanese Society for Artificial Intelligence (JSAI), and the Institute of Electronics, Information and Communication Engineers. He won the 2008 and 2017 JSAI Research Awards, 2012 JSAI Annual Conference Award, 2012 ISPJ SIG Research Award, Best Paper Award of the Society for Art and Science, etc.

Message for Students

Research and development of software is different from other manufacturing, i.e., we do not need a production process when distributing our product. So your program might be used in the world in a few days. We welcome applications from highly-motivated students. Our main activity is evolutionary computation, but we also have a strong interest in machine learning. Please contact Prof. Ono by e-mail (ono@ibe.kagoshima-u.ac.jp) if you have an interest in our lab.

Other Researcher