Chang-Yong Lee talks with
ScienceWatch.com and answers a few questions about
this month's Emerging Research Front Paper in the field of
Computer Science.
Article: Evolutionary programming using mutations
based on the Levy probability distribution
Authors: Lee,
CY;Yao, X
Journal: IEEE TRANS EVOL COMPUTAT, 8 (1): 1-13 FEB
2004
Addresses: Kongju Natl Univ, Dept Ind Informat, Chungnam
340802, South Korea.
Kongju Natl Univ, Dept Ind Informat, Chungnam 340802, South
Korea.
Univ Birmingham, Sch Comp Sci, Birmingham B15 2TT, W
Midlands, England.
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.
"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."
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.
"This paper proposes a new method
that can be applied to the optimization
algorithm."
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.