Why do you think your paper is highly cited?

Our paper addresses the issue of fast convergence in evolutionary programming, which mostly uses optimization algorithms inspired by biological evolution and natural selection. Fast convergence is an important practical question in the optimization algorithm and there have been many attempts to achieve it.

Utilizing the Lévy probability distribution, our paper introduces an adaptive Lévy mutation operation, which not only overcomes the premature convergence problem but achieves fast convergence toward the desired solution. Although the idea of the proposed algorithm is rather simple and easy to implement, it outperforms conventional algorithms.

Does it describe a new discovery, methodology, or synthesis of knowledge?

This paper proposes a new method that can be applied to the optimization algorithm. While conventional algorithms usually adopt a mutation operation based on the Gasussian probability distribution, this new method introduces a mutation operation based on the Lévy probability distribution. The Lévy probability distribution differs from the Gaussian distribution in that it has an infinite second moment leading to the infinite displacement of variables.

In practice, an infinite displacement implies that it is possible to get a large variation on the offspring even after just one generation. The large variation at a single mutation enables the Lévy mutation to search a wider region of the search space. In addition, the Lévy mutation can explore the search space more effectively and evenly. Therefore, it can not only search a wider area of the search space but also generate more distinct values within the search space. This naturally renders a means to find an optimal solution faster and more effectively.

Would you summarize the significance of your paper in layman's terms?

Finding the minimum and/or maximum of a certain function or system is called an optimization problem. When the function or system is very complicated, having many local minima or maxima, it is called an NP-complete or NP-hard problem (NP stands for Non-deterministic Polynomial-time), and there is no general method which brings you the truly optimal answer.

An alternative way to solve an NP-hard problem is to find approximately optimal answers, and there are several optimization algorithms, such as simulated annealing and evolutionary computations, to enable a solution to be found.

All optimization algorithms inevitably suffer from so-called premature and slow convergence problems. The premature convergence problem occurs when an algorithm reach a local optima "prematurely" before reaching near a global optimum. The slow convergence problem prevents an algorithm from getting near the global optimum within a reasonable computation time.

Our paper alleviates these two problems by introducing the Lévy probability distribution to the evolutionary programming, which belongs to the class of evolutionary computations. The evolutionary programming is, as the name implies, an optimization method inspired by biological evolution and natural selection. In it, there are operations, such as mutations and selections, which mimic biological evolution and natural selection, and the mutation operation is the most important operation in the evolutionary programming.

The conventional way to implement the mutation operation is to use the Gaussian probability. However, due to the finite variance of the Gaussian distribution, the variation after the mutation operation is ineffective, which results in the two problems mentioned above. The mutation operation based on the Lévy probability distribution solves these problems significantly, if not entirely, since the distribution has an infinite variance and thus can search solution space more effectively.

How did you become involved in this research and were any particular problems encountered along the way?

For many years we were interested in scale-free phenomena, in which one finds there is no characteristic scale in the system. The Lévy probability distribution has such scale-free properties. One of the characteristics of the Lévy distribution is its power law in the tail region. The power law implies that there is no characteristic length scale and this is the milestone of fractal structure. Thus, the distribution has drawn much attention from scientific communities to explain the fractal structure of Nature, in such areas as turbulence, polymers, biological systems, and even economics.

We tried to apply the distribution to other problems and found that it is applicable to the optimization algorithm such as the evolutionary programming process. In applying the distribution to the optimization algorithm, we learned that, by adjusting the parameter in the distribution, one can tune the probability density, which in turn yields adjustable variation in the mutation. We encountered a problem in generating random variables of the Lévy probability distribution, and resolved it by introducing a transformation of two Gaussian random variables.

Where do you see your research leading in the future?

Research on optimization algorithms has its practical as well as theoretical importance. Our research would lead to more elaborate versions of the evolutionary programming incorporating self-adaptation of variances of mutations. In addition, it would be interesting to investigate the application of the adaptive Lévy mutation to the strategy parameters. Such a scheme will be much closer to self-adaptation in evolutionary computation.

Moreover, although this research restricts the parameter to four discrete values for adaptation, a better scheme of continuous adaptation might be possible during the evolution of solutions. Research in these directions could open up new adaptive possibilities within the area of artificial intelligence.

Do you foresee any social or political implications for your research?

Our proposal of a new optimization algorithm would be applied successfully to the optimization of real-valued functions and other practical problems. Although our paper focuses on the evolutionary programming for continuous parameter optimization, many of our conclusions are also applicable and robust for other evolutionary algorithms. We hope that the proposed method has drawn much attention toward the research community in conjunction with parallel and/or distributed computations, as well as that of general artificial intelligence.

Chang-Yong Lee, Ph.D.
Professor of Department of Industrial and Systems Engineering
College of Engineering
Kongju National University
Kongju, South Korea

KEYWORDS: EVOLUTIONARY OPTIMIZATION; EVOLUTIONARY PROGRAMMING; LEVY MUTATION; LEVY PROBABILITY DISTRIBUTION; MEAN-SQUARE DISPLACEMENT.