Artif Life Robotics (1998) 2:48-52

9 ISAROB 1998

II-Kwon Jeong 9 Ju-Jang Lee

A self-organizing genetic algorithm for multimodal function optimization

Received: February 19, 1998 / Accepted: March 19, 1998 Abstract A genetic algorithm (GA) has control parameters that must be determined before execution. We propose a self-organizing genetic algorithm (SOGA) as a multimodal function optimizer which sets G A parameters such as population size, crossover probability, and mutation probability adaptively during the execution of a genetic algorithm. In SOGA, GA parameters change according to the fitnesses of individuals. S O G A and other approaches for adapting operator probabilities in GAs are discussed. The validity of the proposed algorithm is verified in simulation examples, including system identification.

Key words Genetic algorithm 9 Self-organizing

Introduction Genetic algorithms (GAs) are robust search and optimization techniques which are based on natural selection and genetics. GAs are currently applied to a number of practical problems. GAs differ from conventional optimization methods in several ways. The G A is a parallel and global search method which searches multiple points, so it is more likely to get the global optimum. It makes no assumptions on the search space, so it can easily be applied to different problems. In the control area, it has been applied to identification, 1 adaptation, and neural network controllers. ~'3 However, GAs are inherently slow and not good at fine tuning the solutions.

I.-K. Jeong ( 9 ) 9J.-J. Lee Department of Electrical Engineering, Korea Advanced Institute of Science and Technology,373-1 Kusong-dong,Yusong-gu,Taejon 305-701, Korea Fax +82-42-869-3410 e-mail: [email protected]

This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18-20, 1996

The G A may be thought of as an evolutionary process where a population of solutions evolves over a sequence of generations. During each generation, the fitness (goodness) of each solution is calculated, and solutions are selected for reproduction based on their fitness values. The probability of the survival of a solution is proportional tO its fitness value, This process is based on the principle of "survival of the fittest." The reproduced solutions then undergo recombination, which consists of crossover and mutation. The genetic representation may differ from the real form of the parameters of the solutions. Fixed-length and binaryencoded strings have been widely used to represent solutions since they provide the maximum number of schemata and they are simple to implementJ In this paper, we propose a self-organizing genetic algorithm (SOGA) for multimodal function optimization which is designed to set its control parameters such as population size, crossover probability, and mutation probability adaptively during its execution. The choice of the crossover probability, p~, and the mutation probability, Pro, is known to have a critical effect on the behavior and performance of the GA. Although a number of generalized guidelines exist in the literature for choosing Pc and Pro, these guidelines are inadequate as the choice of optimal Pc and p,, becomes specific to the problem under consideration. The size of a population is another important parameter that affects the performance of an algorithm. In our algorithm, p,., Pro, and the size of the population are determined adaptively by the GA itself to realize the twin goals of maintaining diversity in the population and sustaining the convergence capacity of the GA. There has been similar work to improve evolutionary algorithms. Jeong and Lee 2 incorporated the simulated annealing technique into a GA. They suggested a fitness modification technique and an adaptive mutation probability) Miller et al. 5 introduced a local improvement operator. Srinivas and Patnaik 6 made the crossover and the mutation probabilities vary according to the population maximum fitness and the population mean fitness, but their adaptive rules are not general in the sense that the rules only apply to solutions which are above average. Julstrom 7 used the rela-

49 tire credit of each genetic operator over some generations. However, his algorithm needs more memory and longer computation time compared with above-mentioned algorithms. Smith and Fogarty 8 investigated the use of genetically encoded mutation rates within a steady state GA. Again their algorithm needs a lot of memory, and it cannot be applied to a generational GA. This paper is organized as follows. The next section describes a simple genetic algorithm, and the following one describes a self-organizing genetic algorithm (SOGA). Simulation examples follow, and then our conclusions are presented.

A simple genetic algodthm A G A is a search method based on natural selection and genetics. A G A is computationally simple and yet powerful, and it is not limited by assumptions about the search space. The most important goal of optimization should be improvement. Although a G A cannot guarantee that the solution will converge to the optimum, it tries to find the optimum, that is, it works for improvement. Following the model of evolution, GAs establish a population of individuals where each individual corresponds to a point in the search space. An objective function is applied to each individual to evaluate their fitness. Using genetic operators, the next generation is formed based upon the survival of the fittest. Therefore, the evolution of individuals from generation to generation tends to result in fitter individuals (solutions) in the search space. Empirical studies have shown that genetic algorithms do converge on global optima for many problems, including NP-hard ones. A simple G A (SGA) has three basic genetic operators: reproduction, crossover, and mutation. There are three differences from random search in a GA: first, the existence of the direction of search owing to the selection probability, second, the fact that the better strings make more offspring, and third, being likely to be improved in average fitness over generations.

Self-organizing genetic algorithm In optimizing unimodal functions, it is important that the G A should be able to converge to the optimum in as few generations as possible. For multimodal functions, there is a need to be able to locate the region in which the global optimum exists, and then converge to that optimum. GAs possess poor hill-climbing capabilities and they are vulnerable to getting stuck at a local optimum, especially when the populations are small. The significance of p,. and Pm in controlling G A performance has long been acknowledged in G A research. The higher the value of p~,, the quicker are the new solutions introduced into the population. As p~ increases, however, solutions can be disrupted faster than selection can exploit them. Large values of pro transform the

G A into a purely random search, while some mutation is required to prevent the premature convergence of the G A to suboptimal solutions. The population size also affects G A performance. Premature convergence may occur when the population size is small, while a large population size makes the algorithm slow. Usually, the choice of Pc, Pm, and population size is left to the user to determine statically prior to the execution of the GA. Typical values of Pc and Pm are in the range [0.5, 1.0] and [0.001, 0.1], respectively. In order to overcome the above-stated problem of difficulty in choosing the G A parameters, we suggest the following expressions, which are the main components of SOGA. They determine Pc and p,, adaptively in response to the fitness values of the solutions.

p~=- k,(fm,~- f ' ) / ( f m . . - fmin) + k2 kl + k2 < 1

(1)

Pm= k3(fmax-f)/(fmax-fmin) +k4 k3 + k4 < 1

(2)

where f,n,x is the maximum fitness value and fmi, is the minimum fitness value of a population, f is the larger of the fitness values of the solutions to be crossed, and f is the fitness of the solution to be mutated, kl, k2, and k 4 are positive constants, k3 and the population size, Npop, are changed adaptively using the following procedure. 1. Initialize k 3. 2. i <-- i + 1, generation i. 3. If the fittest is the same for rite,e,generations, then Npop eNpop + nl and go to step 1. 4. Npop 6-- Np,,p - n2, k3 6-- c • k3, go to step 2. Here n j, n2, and n,~, are positive constants of integers, and 0 < c < 1. As we can see from eq. 1, Pc is a linear function of f , and it varies from k~ + k2 to k2 as f changes from f,,i, to f,,~. Similarly, Pm varies from k 3 if- k4 to k4 as f changes from f,,,, to fm,x" Thus, the higher (lower) the fitness of a solution, the lower (higher) the probability of crossover or mutation of the solution. The idea behind the equations is that the near-optimal (high fitness) solutions should not be disrupted by crossover or mutation, and they can then aid in the convergence of the SOGA. Inferior (low fitness) solutions have higher values of Pc and p,,, which promote the S O G A to explore the search space. Therefore, we are able to preserve "good" solutions of the population while the low fitness solutions prevent the G A from getting stuck at a local optimum. Note that k 3 is designed to decrease exponentially over generations. After a few generations, k 3 vanishes to 0 from its initial value and the mutation operator begins to behave like a normal one with a probability k4. It has been empirically proved that the adaptive mutation probability accelerates convergence and improves the hill-climbing property of the GA. 3 When the fittest (the best solution) is the same for nreset generations, that is, the algorithm is stuck at a local optimum, p,, is enlarged to its initial value to try to direct the search for the global optimum, and the population size

50

Npop is increased by n 1 to search a wider region of the search space. Otherwise, Npop is decreased by n2 at every generation to speed up the algorithm. There remains the problem of the choice of values for kl, k2, and initial k3, k4, n~, n2. k~ + k 2 (k3 + k4) and k2 (k4) are the upper and the lower limits of pc (Pro), respectively. Considering the typical ranges for Pc and Pro, we assign k2 and k 4 a value of 0.5 and 0.01, respectively, and use a value of 0.5 for k~ and the initial k 3. n I and n2 are determined by trial and error. Other parameters are adopted from Jeong and Lee. 3 In order to prevent the population size from becoming abnormal, minimum and maximum values are used in the simulation.

2, and c = 0.9 for the SOGA. Figure i shows the best fitness value averaged over ten independent simulations versus generations using the three algorithms. The A G A shows the worst performance. While the SGA shows rapid convergence, the S O G A shows a steady convergence, which reflects the ideas considered in designing the genetic operator probabilities. This steady convergence may be preferable when applied to multimodal function optimization. The average population size of the S O G A was about 92. System identification The problem considered here is the same as those in Kristinsson and Dumont. 1 It is presented here for comparison. The object system is a discrete time system

Simulations

A(q

Rosenbrock's function

where q-I is the backward shift operator and the objective is identifying A(q 1), B(q 1), and the delay d using the given input u(t) and the output y(t). We define the error sequence

The problem is minimizing Rosenbrock's function,

frosenbrock(X) =

X2)2 + (1

1 0 0 ( X ? --

-- X1) 2,

X = (X1,

X2)T

~l(t) = y(t) - f~(t)

(4)

"........

"S~A..........

I ..............

i....................... lOS

?

10 7

i ',

10 6

10~ 104 ,-"

102 10~ tO o

0

50

100

150

200

250

300

350

400

450

500

Generations Fig.

I R o s e n b r o c k ' s function minimization results using the S G A , and S O G A

AGA,

with

.21(q-1)~(t) : l~(q-1)u(t - d)

(7)

The fitness function to be maximized is t) :

t l ( t - i))

(8)

where w represents window size. The system polynomials, poles, and zeros in the reparameterized plane I are

A(q -1) = 1.0 - 1.5q -1 + 0.70 -2

0(10 +

(9)

+

[pl, p2] = [0.75, -0.37], [Z,, Z2] = [-0.25, 0.25]

u(t) = sin(t) - sin(t/2.5) + random(-1 ~ 1)

AGA

10 3

(6)

(11)

where b0 is 1 and the delay d was set to 1. We apply the SGA and the S O G A to identify Pl, P2, Zl, z2, bo, and d. b 0 is assumed to be in [0, 2] and the poles and zeros in [ - 1 , 1]. Seven bits are assigned to each parameter except d (2 bits), so the resolution is slightly smaller than 0.02. A string consists of 37 (= 7 • 5 + 2) bits. Control parameters are the same as in the previous example, and the window size, w, is 30. Input for the sample data is

1010

: ...........

(5)

as

Hence it is now a fitness function maximization problem. An individual is a 24-bit binary string with 12 bits per variable. Three algorithms, a simple G A (SGA), an adaptive G A 6 (AGA), and a SOGA, were compared. For SGA, Pc = 0.8 andp,~ = 0.1 were used. The parameters for the A G A were adopted from Srinivas and Patnaik. 6 Npop was 100 for both the S G A and the A G A . We used kl = k2 = 0.5, an initial k3 = 0 . 5 , k 4 = 0.01, an initial Npop - 50, n . . . . . ~ - 5, nl = 4, n2 =

109

B(q-1)u(t- d)

(3)

This is a continuous, unimodal, bi-quadratic function with two variables. It is a standard test function in optimization, which was proposed by Rosenbrock. The solution is at x* = (1, 1)r; fros,,broc* (X*) = 0. The fitness function is defined as

F(t) = 1/(frose, brock(X)+ 1.0e-- 10)

I)y(t)=

(12)

One simulation was done using 200 samples with three generations per sample, i.e., 600 generations. Ten simulations were done for each algorithm. Figures 2-4 show the average of the identification results using the SGA. The true value of p2 is -0.371, but the limitation on the resolution due to binary coding makes P2 equal to -0.375. Figures 5-7 show the average of the results using the SOGA. It shows the better hill-climbing and optimum finding capability compared with the SGA. The average of the population sizes of ten simulations using the S O G A was found to be 43.4,

51 0.4

0.8

0.75

r

t

[.......................................... 9._2_5_.. 0"2I .......... < ....... :,. . . . . . . ........ i

0.6

.

0.4

0

0.2

-0.2

0

<

. . . . . .

i

~i

~ -,,z2

;"

:

',:

-' .....

--

~

~

4).25

-0.4

i l:~, -0.2

-0.6

i-~..p2

,-. ~"-w 0.375 . . . . . "~-':~. . . . . . . . . . . . ,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -0.4'

100

200

30O

40O

500

-0.8

6O0

0

10O

200

Generation Fig. 2 Identification

300

400

500

600

~ .......... 500

600

500

6O0

Generation

of the poles using the SGA

Fig. 3 Identification

of the zeros using the SGA

0.8 0.75 0.6 g 0.4 -m 0.2

g

i

~

.<

~d

____~________: ...._

!~

<

0

-0.2

-0.4 0

100

200

300

500

400

600

--'-.._ p2 '- ~~-~.___.~_~:. :1~.~: : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .-0.375 ....... 100 200 300 400 0 Generation

Generation Fig. 4 Identification

Fig. 5 Identification

o f b0 a n d d u s i n g t h e S G A

of the poles using the SOGA

0.3 ..............................................

"0~25 - --

0.2 1.g! 0.1 g z2 . _,---

<

__..-.-..__,-

,. ~

4).1 .~

1.6 ~

g

-0.2

.o; ,"- - " " " - ' """""

-0.25

-0.3 4).4

.< .... "V

-0.5 t/ 4).6

1.4

zl 1.2

1,/

d

J -- f 100

200

300

400

500

60o

0.8

0

100

Fig. 6 Identification

of the zeros using the SOGA

200

300

400

Generation

Generation Fig. 7 Identification

o f bo a n d d u s i n g t h e S O G A

52

which is much smaller than that for the SGA although the performance of the S O G A is much better.

Conclusion A self-organizing genetic algorithm (SOGA) was designed to prevent the premature convergence and to sustain the convergence capacity of the GA. S O G A determines Pc, Pro, and Np,,p automatically using its rules, and so we do not have to determine the values for the parameters prior to the execution of the GA. Simulation results indicate that the S O G A has adaptive characteristics and improved hill-climbing capability compared with the SGA or AGA, which makes S O G A suitable for a multimodal function optimization problem such as the system identification example. Using adaptive population size, the execution time of the algorithm can be significantly lowered. Further work includes the theoretical analysis of the SOGA.

References 1. Kristinsson K, Dumont GA (1992) System identification and control using genetic algorithms. IEEE Trans Syst Man Cybern 22(5):10331046 2. Jeong 1K, Lee JJ (1994) Genetic algorithms and neural networks for identification and control. Proceedings of the first Asian control conference, Japan, pp 697-700 3. Jeong IK, Lee JJ (1995) A modified genetic algorithm for neurocontrollers. IEEE international conference on evolutionary computation, Australia, pp 306-311 4. Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading 5. Miller JA, Potter WD, Gandham RV, Lapena CN (1993) An evaluation of local improvement operators for genetic algorithms. IEEE Trans Syst Man Cybern 23(5):1340-1351 6. Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst Man Cybern 24(4):656-667 7. Julstrom BA (1995) What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. Proceedings of the 6th international conference on genetic algorithms, pp 81-87 8. Smith J, Fogarty TC (1996) Self adaptation of mutation rates in a steady state genetic algorithm. IEEE International Conference on Evolutionary Computation, Japan, pp 318-323