Evolutionary optimization in dynamic environment.

Rotar, Corina ; Ileana, Ioan ; Muntean, Maria 等

1. INTRODUCTION

Mostly, finding only the global optimum is not sufficient in the problem context. Real world problems frequently have more than one optimum. Therefore, evolutionary techniques have been developed to offer multiple optima of the considered problem. Standard evolutionary algorithm has an important drawback: the lack of population diversity and the convergence towards one optimum causes an impossibility of maintaining multiple optima of the problem. The research is focused on this direction of finding skillful evolutionary techniques for solving multimodal problems. Several significant improvements were made by adding extra mechanisms to evolutionary algorithms: the niching techniques inspired by the niche concept (Goldberg, 1989) are suitable for maintaining several subpopulations (niches) corresponding to each optimum and these techniques are responsible for preventing the genetic drift.

The main idea of the crowding techniques (CrowdingDE) is to provoke the individuals to establish around each optimum by using a replacement procedure based on the similarity degree. Standard crowding described by de Jong and Deterministic Crowding are two variants of the same approach.

Fitness sharing described in (Goldberg et al., 1987) is enriched by an extra mechanism in which case the population consists in several subpopulations corresponding to all promising regions of the search space. This partitioning of the population is suggested by the biological concept of ecological niches. Each subpopulation tends to occupy a specific zone, and therefore to converge to one optimum. The principle of sharing technique is to reduce the fitness of each individual of the current population by an amount proportional to the number of similar individuals of the population.

Speciation techniques, eg. SCGA algorithm, (Balazs et al., 2002), inspired by a natural process of evolution, are also niching methods which exploit the concept of species. The algorithm is based on the concept of partitioning the population into several subpopulations according to similarity degree of the individuals. Each of these subpopulations is called species and is built around a dominating individual called the species seed. All species seeds of the current population are conserved by moving them into the next generation.

The clearing technique (Petrowski, 1996) is based on the niching principle according to which the subpopulations share the limited resources of the same area. There are similarities with the sharing techniques, but in clearing procedure's case, each subpopulation has a winner (the individual with the best fitness) which will fully gain the whole resources, while the others' fitness will be set to zero. The procedure can be generalized by accepting more than one winner on each niche.

2. DESCRIPTION OF MMEA

The paper introduces an algorithm named Multidimensional Mutation Evolutionary Algorithm (MMEA) aimed for solving optimization problem in dynamic multimodal environment.

The algorithm induces subpopulations that are able to settle in the multiple optima areas of the problem under consideration. Moreover, in a dynamic environment, without additional procedure, the proposed technique is able to quickly adapt the population to the changeable landscape.

MM-Evolutionary Algorithm

1. Randomly generate the initial population P(0), t=0.

2. Evaluate individuals of P(0)

3. While (stopping_condition=false) execute: For each ith individual of population P(t) do Find the next position, encoded by c' Evaluate c'

c' replaces the parent if it is better than the parent Compute the AQ coefficient of new ith individual of the population

t:=t+1

3. EXPERIMENTAL RESULTS IN DYNAMIC ENVIRONMENT

In order to validate our proposal we conduct numerical experiments on several well-known test function, comparing the MMEA's results with the result obtained by other popular algorithms for multimodal optimization: CrowdingDE, SCGA, and Genetic Algorithm with Clearing. Each of the mentioned algorithms use one of the niching methods described in introductory part of the paper.

3.1 Static environment results

We present next the results obtained on Shubert test function.

Each algorithm runs for 30 times. The population size is set to 100 individuals and the maximum number of produced generations is 100. Regarding the specific parameters for each algorithm (species distance, clearing radius), we follow the suggestion found in (Deb et al., 1989). The results obtained by each run of each compared algorithm are analyzed. MMEA proves to be more effective in finding multiple optima of the considered test functions. In most of the cases, the results obtained by MMEA overcome the results obtained by other algorithms. Reported in (Balazs et al., 2002), SCGA is able to find all 18 global optima of the Shubert. In our experiments, for a population of 100 and 100 produced generations, with the recommended species distance's value, SCGA fails to locate all 18 minima. Moreover, the average number of optima is very low. However, for the same value of the major parameters (population size and number of produced generations) MMEA succeeds to find all optima in one third of the runs and more than 16 optima in the rest of runs with better precision.

[FIGURE 1 OMITTED]

3.2 Dynamic environment results

We conducted experiments both in static and dynamic environments by using for comparison an evolutionary algorithm designed for multimodal optimization problem: Crowding DE. Previous performance of CrowdingDE algorithm in static environment encourages us to select this technique to compare with MMEA in further experiments.

The evaluation metrics of the performances of compared algorithms are: Peak Ratio and Peak Accuracy. These evaluation metrics are used when the location of optima and their number are known.

For experiments in dynamic environment we consider the moving Peaks Benchmark proposed by Branke in 1999. The peaks are changed randomly at each 10000 function evaluation. For further comparisons, we compute before each change in environment the following performance metrics: Peak Ratio and Peak Accuracy. We consider the same test scenarios 1-6 described before, but in these experiments, at each run of the algorithms the environment is changed for 10 times. A change occurs after 10000 function evaluations and the algorithms run for 10 times. In each run, the positions of the peaks are changed for 10 times, therefore, the average values of the considered metrics will show the behavior of the algorithms for 100 changes in the environment.

In all test scenarios the behavior of MMEA regarding the evaluation metrics considered is better than CrowdingDE's behavior: Peak Accuracy's values are smaller in MMEA's results and the number of found peaks is larger. The following charts show the average values for the considered metrics at each generation along 10 runs of MMEA and CrowdingDE.

4. CONCLUSIONS

In this paper, we presented MMEA, a comprehensible algorithm for solving multimodal optimization problems. The technique is based on using a special mutation procedure combined with an elitist replacement of each parent individual with the best mutant. The main advantages of MMEA consist in its independence by the user defined parameters, the natural utilization in dynamic environment without any adjustment and better results than other popular algorithms for different test functions. Moreover, the algorithm can be simply applied for dynamic optimization problems without any additional mechanism to assure the population's adaptation to the possible changes in the environment.

5. REFERENCES

Balazs, M., E.; Li, J-P; Parks, G., T. & Clarkson, P., J. (2002). A species conserving genetic algorithm for multimodal function optimization, Evolutionary Computation, Vol. 10, No. 3, pp 207-234, ISSN 1063-6560

Deb, K.; Goldberg, D., E. (1989). An investigation of niche and species formation in genetic function optimization, Proceedings of the Third International Conference on Genetic Algorithms, Schaffer, J., D., (Ed.), pp 42-50, ISBN 1-55860-066-3, George Mason University, Fairfax, Virginia, USA, June 1989, Morgan Kaufmann

Goldberg, D., E.; Richardson, J. (1987). Genetic algorithms with sharing for multimodal function optimization, Proceedings Second International Conference Genetic Algorithms, Grefensette, J., J., (Ed.), pp 41-49, ISBN 08058-0158-8, Cambridge, Massachusetts, United States, 1987, L. Erlbaum Assoc. Inc., Hillsdale, NJ, USA

Goldberg, D., E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Pub. Company, Inc., ISBN-13 9780201157673

Petrowski, A. (1996). A Clearing Procedure as a Niching Method for Genetic Algorithms, Proceedings of IEEE International Conference Evolutionary Computation, pp 798-803, ISBN 0-7803-2902-3, Nagoya, Japan

Tab. 1. The results obtained by compared algorithms for the
Shubert test function

Total number of optima 18 18 18
Species distance/Clearing radius 1.6 1.6 1.6
Epsilon 0.1 1 10
MMEA 14.8 16.77 17.5
SCGA 0.33 1.23 4.93
CrowdingDE 0.8 4.47 15.17
Clearing Algorithm 0.27 1.37 3.5

Tab. 2. Average values for PeakRatio and PeakAccuracy

 Average Peak Ratio Average Peak Accuracy
No
 MMEA CrowdingDE MMEA CrowdingDE

1 0.952 0.732 24.6486 134.8798
2 0.534 0.028 169.5849 242.161
3 0.196 0.136 247.6158 246.8104
4 0.896 0.741 87.80904 286.281
5 0.424 0.002 353.9968 490.1668
6 0.149 0.057 496.787 503.4237

Fig. 2. Average Peak Ratio and Peak Accuracy values for each
test scenario 1-6

Average Peak Ratio

Test no. mmEA Crow dingDE

1 0.952 0.732
2 0.534 0.028
3 0.196 0.136
4 0.896 0.741
5 0.424 0.002
6 0.149 0.057

Average Peak Acuraccy

Test no. mmEA Crow dingDE

1 0.952 0.732
2 0.534 0.028
3 0.196 0.136
4 0.896 0.741
5 0.424 0.002
6 0.149 0.057

Note: Table made from bar graph.