Genetic Algorithms in Competitive Environments
Descripción
Genetic Algorithms in a Competitive Environment with Application to Reliability Optimal Design V. K. Koumousis and C. K. Dimou Institute of Structural Analysis & Aseismic Research National Technical University of Athens Zografou Campus, 157 73 Athens, Greece.
Abstract Competition is introduced among Genetic Algorithms (GAs) with different parameters evolving to solve a specific problem. The aim is to calibrate tuning parameters of the GAs as they struggle for the resources of the system. The evolution of the size of the different populations is controlled on the metapopulation level, i.e. the union of populations, on the basis of the statistics and trends of the evolution of every population. The method is applied to the reliability optimal design of a simple truss. Numerical results are presented and the robustness of the proposed algorithm is discussed.
1
INTRODUCTION
Genetic Algorithms are search algorithms based on the concepts of natural selection and survival of the fittest (Goldberg 1989). They guide an evolution of a set of randomly selected designs through a number of generations that are subjected to successive reproduction, crossover and mutation, based on the statistics of each generation. The efficiency of the process is problem dependent and relies heavily on the successful selection of the number of parameters, such as population size, probability of crossover and probability of mutation, type of crossover etc. In this work a method is proposed that attempts to automate tuning of the evolution of the size of populations through an adaptive process. This is based on the competition of populations, with different sets of GA parameters, struggling for the available resources of the system. Competition among different populations is common in natural systems. Populations evolve by adapting themselves to the environment where resources are limited. By coupling GAs with a scheme of Competing Populations (CP) a number of populations are produced in every generation. They evolve in the design space guided by every GA in an adaptive way by altering their population size. By reducing gradually the resources, the system organizes better its overall search strategy. It manages to come up with very good near optimal solutions faster as compared to the same number of standard GAs. The relative capacity of every population to adapt to the artificial habitat is used to calculate the overall fitness at a particular generation. Competition arises when the resources are insufficient to sustain the entire population. “Predator – Prey” relationships are activated, by assigning conflicts among the populations. The “predator” population is trying to survive through the extinction or drastic reduction of its “prey”. The prize for the “predator” is the resources allocated for the “prey”. The proposed method is applied to the reliability optimal design of a typical statically determined truss. Numerical results are presented that illustrate the advantages of the proposed method as compared to the standard GA.
2
GA AT POPULATION AND METAPOPULATION LEVEL
A simple GA scheme is employed for every population (Goldberg, 1989). No mixing among designs of different populations is allowed to preserve the characteristics of each population. Reproduction is based on a ranking scheme, while elitism is adopted allowing the best designs to survive at the next generation (Koumousis and Georgiou 1994 Gaudenzi et al. 1996). Various crossover techniques such as single crossover double crossover and single crossover per design variable are implemented. For the mutation probability, a decreasing function is used. The entire system operates in two levels, the level of populations and the level of the metapopulation, where all decisions about the characteristics of the next series of populations are made. The normalized fitness of the ith design of the jth population, is expressed as: max fˆij x Nc j i, j f ij x , fˆij x Cij x c jk T g k x (1) ˆf x k 1 ij where, gk(x) is the kth inequality constraint of the design, cjk is the penalty factor assigned for the kth constraint for the jth population and Cij(x) is the objective function. Operator T is given as:
x T x 0
x x
(2)
where, ε is the tolerance in violating the constraints. A convergence criterion is introduced that works as a trade-off between the minimum uniformity of the population, i.e. the saturation of a dominant schema per design variable of the problem, and the Coefficient of Variation (C.O.V.) of the objective function. Convergence is reached for population uniformity over 85% and C.O.V. less than 5%.
3
COMPETITION SCHEME
Competition is common in natural systems. Dimitrova and Vitanov 2000, study the evolution of competing populations through adaptation in a nonlinear dynamical system with limited resources. Hanski and Gulpin 1997, present the important parameters of interaction among different populations in a natural environment. Populations of different species share the environment in a state of dynamic equilibrium. Competition among different species arises when they share the same resources. 3.1
RESOURCES
Assuming the necessary computational resources constant per design within a population, the amount of resources required to process all the designs of the metapopulation in a specific generation is given as: Np
Rreq Ri Ni
N
NP
N
i
(3)
i 1
i 1
where, Ri are the resources per design of the ith population and Np is the number of populations in the system. The amount of available resources at generation t can be represented by a step like function with initial resources R:
Ravail R H t ti Ri m
(4)
i 1
where, m defines the number of changes of the step-like function at particular instances, i.e. at generations ti with reduction of resources ΔRi, and H is the Heaviside function. Alternatively, one can consider accumulation of resources across generations. The available and required resources of the system are given as:
t Np t Rreq Ri N i t 0 i 1 In either case if the available resources are less than the required ones, conflict appears in the system. t m t Ravail R H t ti Ri t 0 i 1
3.2
,
(5)
POPULATION FITNESS
The fitness of a population can be expressed as the sum of the fitness of its designs. This favors the expansion and survival of larger populations and of populations with many “good” designs. Alternative expressions may be used that consider the fitness of a population as the average of the fitness of its designs. The overall fitness is expressed as: Nj
Fˆ j f ij ,
Fj
i 1
Fˆ j
max Fˆi
(6)
i 1, N P
where, Nj is the total number of designs of the jth population. The main goal at this stage is to introduce a more stringent approach, as compared to the GA, that will process the emerging data and guide the next steps taking into account the uncertainties of the system. Therefore, a diversity measure Dj of the chromosome of every population j is evaluated based on descriptive statistics of the digits appearing at every position of the chromosome. Diversity is used as an estimate of the “age” of populations. “Younger” populations exhibit higher diversity as compared to “older” ones. Moreover, “younger” populations are more prominent to adapt that “older” ones. The amount of resources for each design appropriately normalized, is given by: Rˆ i (7) Ri max Rˆ
j 1, Np
j
The overall fitness of the ith population OFi is expressed as the ratio of the product of fitness and diversity with the resources of the population as:
OFi Fi Di Ri (8) where, a, b and c are parameters, that attenuate or intensify relative variations among the populations. In this analysis a 1.0, b 2 3 and c 1.0 . Equation (8) is frequently used in econometric models. a
b
c
3.3
ENGAGEMENT RULES
The probability of conflict among different populations i and j, when shortage of resources is observed, is given by:
N (OFi OF j ) OFi Pr popi , pop j T 0 N
Rreq Ravail EN i OFi OF j , N OFi OF j ERi N i
0 x T x d 1
x0 0 xd
(9)
xd
where, d is a parameter controlling the transition from a state of no conflict to a state of conflict emerging among populations based on the available amount of resources. This equation assures that no conflict arises if the available resources are adequate. Moreover, conflicts arise in proportion of the resource deficit. Stronger populations fight only weaker ones. The probability of conflict between two competing populations increases linearly with the relative difference of their overall fitness. Only one conflict per generation for a pair of populations is allowed. Thus, no population is engaged in more that one conflicts in a specific generation. Finally, conflict ceases when the available resources are adequate. The outcome of a conflict between populations i and j, determines the size of these populations in the next generation as follows:
N ,2 0.5 f x max g N p OFi OFJ N i N i T eij 0 0.5 x 0.5 f OFi N , T x max g ,2 0.5 f x 0.5 1 OFi OFJ N p N j N j T 1 e OFi ij 2 N ,4 x 0.5 f max g Np where, eij is equal to:
eij 1
e rand 0.5 0.5
(10)
(11)
and, e and f are parameters handling the fuzziness of the outcome. In this analysis e 0.2 and f 0.2 . Furthermore, the g factor is used to regulate the velocity of variation of the size of population. Populations vanish, if their population drops to zero. Typical values of g factor are around unity. The main ingredients of the proposed scheme at the level of metapopulation, are the introduction of diversity in equation (8) as a result of formal descriptive statistics on the different schemata, and the fuzzy outcome of the conflict between populations. The influence of parameters e, f in equations (10) and (11) is of secondary importance.
4
TRUSS EXAMPLE– FORMULATION OF THE OPTIMIZATION PROBLEM
A statically determined truss (Haftka et al. 1992) is presented in Figure 1. The design variables are the five crosssectional areas of the members and the two heights that control the shape of the truss. The objective function is the cost of the structure, i.e. construction cost plus the cost due to possible structural failure. The constraints of the problem are the failure probability of the entire structure and the failure probabilities of its elements.
5 1
h1
4 2
h2
3 L
L P
Figure 1. A Statically Determined Truss The optimization problem in its typical form is as follows: N
min F Ai , hi Vi Ai , hi C mat Pf , s C fail i 1
Subject to:
(12)
g j Ai , hi
Pf , j P j , lim
g s Ai , hi
1.0 0
Pf , s Ps , lim
1.0 0
(13)
where, N is the number of elements of the truss, Vi is the volume of the ith element, Cmat and Cfail is the cost per unit volume of the structure and the cost of a potential structural failure respectively, Pf,s is the overall failure probability, Pf,,j and Pj,lim are the failure probability of the jth element and its highest acceptable failure probability respectively and Pf,,s and Ps,lim are the failure probability and its limit value for the entire structure. The safety margin for a structural element is given as:
M
R Ai F hi
(14)
where, R(Ai,) and F(hi) is the ultimate resistance and the applied load respectively given as:
R Ai u Ai ,
F hi f i hi P
(15)
and fi(hi) are influence coefficients reflecting the results of structural analysis that depend on the geometry of the structure. The load P, the ultimate yield stress and the areas of the cross-sections are the random variables of the problem. If these variables follow a lognormal distribution (see Table 1) an analytical solution of the failure probability can be obtained. Table 1. Probabilistic data for the Determined truss Variable Load P (kN) Ultimate Capacity (MPa) 2
Cross section (mm )
Distribution Lognormal
Average 20.0
C.O.V. 12.5%
Lognormal
400.0
10.0%
Lognormal
Var.
10.0%
Since the structure is statically determined failure of one of its elements results into failure of the entire structure. The structure is modeled as a series system of correlated elements. Ditlevsen bounds are used to obtain estimates of the system reliability (Christensen and Murotsu 1986, Christensen and Baker 1982). A number of problems were solved for L=6 m, starting with an initial population size of 40 designs. The available resources vary according to three different schemes shown in Figure 2. Three levels of reliability are examined as shown in Table 2. Table 2. Limit probabilities for the three Reliability cases Reliability Level High
Pj,lim Parameter 10-6
Ps,lim Parameter 5*10-6
Medium
10-5
5*10-5
Low
10-4
5*10-4
Five different sets from A to E are considered in the analysis. They vary in the available scheme of resources they use, i.e. equations (3) and (4) for type I, and equation (5) for type II. Moreover, a distinction is made with respect to the redistribution of resources of the populations that have converged after a specific generation. Finally, the influence of parameter g in equation (11) is examined. The characteristics of these variations are presented in Table 3. Table 3. Cases A-E Resources
A II
B I
C II
D I
E II
Redistribution
YES
YES
NO
NO
NO
g factor
0.0
0.0
0.0
0.8
0.8
Three crossover methods and two crossover probabilities are combined to create six different populations. Single crossover, double crossover and single crossover per Design Variable (DV) are used in the analysis. Single crossover per DV usually leads to poor convergence especially in the case of multivariate problems and chromosomes of small length. These populations are presented in Table 4.
Table 4. Parameters of the GA Population Crossover Prob.
Pop #1 0.7
Pop #2 0.7
Pop #3 0.7
Pop #4 0.85
Pop #5 0.85
Pop #6 0.85
Crossover Type
Single per DV
Double Point
Single Point
Single per DV
Double Point
Single Point
In Figure 3, comparison of the computing time of the five different schemes is presented as compared to the time needed for the same number of GA with constant population size 40. In all cases, reduction of computing time is observed. The best performance is obtained in case C followed by cases E and D respectively. For case C, reductions of the order of 70% as compared to the time needed for the standard GA are observed. The time needed for the standard GA is of the order of 8 min for 60 simulations with different random seeds on a Pentium PC. Comparison of Computational Effort
Resource Variation Schemes 100%
1.1
90%
1 80%
A
B
C
D
E
70% 60%
0.8 %
% of Original
0.9
GA
0.7
50% 40%
0.6
30%
RVS #1
0.5
RVS #2
20%
RVS #3
10%
0.4
0%
0
10
20
30
40
50
60
70
80
90
Low
Medium
High
Reliability
Generation
Figure 2. Evolution of Resource Variation Schemes.
Figure 3. Comparison of computing time.
In Figure 4, the robustness of the different schemes with regard to the GA is presented for the high reliability study for near optimal solutions within the 1% and 2.5% of the true optimum, determined by complete enumeration of the analytical solution of the problem (Haftka et al., 1992). The term “robustness” is used to determine the ability of the algorithm to deduce optimum or near optimum solutions. In this study, the number of designs within 1% and 2.5% of the true optimum are considered. The design space of 16 6 solutions was evaluated in 7 h computing time. Cases A and D are the most robust followed by B and C. Case E appears slightly inferior as compared to the GA scheme. Similar results were obtained for medium and low reliability. In Figure 5, the evolution of the objective function is presented for six different populations starting with 40 designs and having the characteristics presented in Table 4. It is observed that in the first generation, the results start from bad solutions and they progress rapidly. Following the reduction scheme #2, reductions of resources appear every 5 generations in the beginning and every 10 to 20 generations later on. This initiates conflicts that lead either to the extinction of certain populations, or early convergence to their optimum. In this case population #2 continues alone and finds the optimum solution.
Evolution of Objective for the Best Individual
12
80
10
75
8
70
Objective
Count
Count of Optimal Designs (average on the cases considered)
6
4
Pop #1 Pop #2 Pop #3 Pop #4 Pop #5 Pop #6
65 60 55
2
50 0
GA
A
B
C
D
E
1.0%
2
3
3
2
3
2
2.5%
5
11
6
7
8
4
Figure 4. Robustness of cases A to E
45 0
10
20 30 Generations
40
50
Figure 5 Evolution of the objective, Low Reliability.
In Figure 6, the evolution of the objective is presented for case D for medium reliability where conflict exists until the 25th generation. The best solution converges and due to redistribution of resources, population 5 continues until to converge to a non-optimal solution, yet not very far from the computed optimum. For this case, the evolution of the population size of the six different GAs is presented in Figure 7. The first reduction scheme is applied. It is observed that population #2 wins the conflicts and increases its population size to converge around the 25th generation. Then population #5 consumes all the available resources until its convergence.
Evolution of Individual Populations
Evolution of Objective for the Best Individual 60
90 85
70 65
50
Size
Objective
75
Pop #1 Pop #2 Pop #3 Pop #4 Pop #5 Pop #6
55
Pop #1 Pop #2 Pop #3 Pop #4 Pop #5 Pop #6
80
45 40
60
35 55
30
50 0
5
10
15
20
25
30
35
40
45
50
Generations
Figure 6. Evolution of the objective, Medium Reliability
0
10
20 30 Generations
40
50
Figure 7 Evolution of Population size, Medium Reliability
Similar results were obtained for the high reliability case. In general, the reduction resource scheme #1 gives the best compromise results between robustness and computational time, followed by schemes #2 and #3.
5
CONCLUSIONS
From the above analysis and the parametric studies performed it becomes evident that the proposed competitive scheme controls satisfactorily the evolution process favoring the expansion of “promising” populations and the contraction of “weak” populations in a statistical sense. The descriptive statistics in the metapopulation level together with the rules of conflict guide the utilization of resources towards the most competent GAs. The method succeeds in finding good “near” optimal solutions in a robust way and in most cases faster than a standard GA. For computational intensive problems, like reliability optimal design, near optimal solutions are found in considerably less time. References Christensen, P. T., and Murotsu Y. (1986) “Application of Structural Systems Reliability Theory”, Springer Verlag, Berlin, Germany. Christensen, P. T., and Baker M. J., (1982) “Structural Reliability Theory and its Applications”, Springer Verlag, Berlin, Germany. Dimitrova Z. I., Vitanov N. K., (2000) “Influence of adaptation on the nonlinear dynamics of a system of competing populations” Physic Letters A, Vol. 272, pp. 368-380. Goldberg, D. E., (1989). “Genetic algorithms in search, optimization, and machine learning”. Addison-Wesley, Reading, Mass. Haftka R. T., Gurdal Z., Kamat M. P., (1992) “Elements of Structural Optimization” 3rd Edition, Kluwer Academic Publishers. Hanski I. A., Gilpin M. E. (eds) (1997) “Metapopulation Biology” Academic Press. Gaudenzi P., Fantini E., Koumousis V., Gantes Ch., “G.A. Optimization for the Active Control of a Beam by means of PZT Actuators”, Journal of Intelligent Material Systems and Structures, Vol. 9 – April 1998, pp. 291-300. Koumousis V. K., Georgiou P. G. (1994) “Genetic Algorithms in Discrete Optimization of Steel Truss Roofs” Journal of Computing in Civil Engineering Vol. 8, No. 3, pp. 309-325.
Lihat lebih banyak...
Comentarios
