Continuous Parameters in Dreamy Genetic ... - Semantic Scholar

7 downloads 251 Views 1MB Size Report
The conventional formulation suffers from convergence weaknesses. GAs tend to ... GA proceeds towards convergence in the
Session VC5

Continuous Parameters in Dreamy Genetic Algorithms Eric J. Gaudet III, Terrence L. Chambers, William E. Simon Department of Mechanical Engineering University of Louisiana at Lafayette

Abstract This paper investigates the use of continuous parameters in dreamy Genetic Algorithms, which feature alternating awake and sleep cycles. While awake, the algorithm converges towards a solution in the traditional manner; while dreaming it breaks away to further explore the search space. The dream phase is implemented to overcome a problem inherent to the genetic method: premature convergence. The cycles allow the algorithm to more fully utilize its exploration and exploitation capabilities, increasing diversity in the search space. As originally formulated, the dreamy algorithm used a binary encoding. The success of such a scheme is generally problemdependent, as Genetic Algorithms suffer from encoding brittleness. Continuous parameters are implemented in the dreamy model to demonstrate the effectiveness of the dreamy method on benchmark functions, in addition to showing the importance of robust encodings. Introduction Genetic Algorithms (GAs) search through (explore) a design space seeking optimal solutions by employing Darwinian evolution through natural selection. Darwin’s theory holds that existing life forms descended from earlier versions through the hereditary transmission of attributes, slight variations of which occur between generations. Superior variations are passed on and others are not. GAs mimic this generational preservation of exceptional attributes as an artificial adaptation of a natural process. GAs start with an initial random population of potential solutions and evolve new designs through pairing and mating, exploiting available information. The fitness of successive offspring improves as the number of generations increases, and the GA progresses towards an optimal solution. The conventional formulation suffers from convergence weaknesses. GAs tend to converge rapidly, but the design produced may not be the global optimum. The population becomes homogeneous over time as the best designs become dominant. The need to maintain diversity in the population is usually addressed using a mutation of parameters during the reproduction process. Dreamy GAs were designed to introduce variety at a representational level instead1. The framework is yet another adaptation of a natural process: sleep/awake cycles. While “awake” the GA proceeds towards convergence in the usual manner, exploiting available information; while “dreaming,” the algorithm is allowed to further explore the search space. The cycles alternate over a total number of generations for a more dynamic exploitation/exploration ratio1. Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

GAs also suffer from representational weaknesses. Implementation requires that the domain of the solution space be coded into the algorithm. Traditionally this is accomplished via strings of binary integers. The deficiency of this method is apparent when a domain of continuous parameters generates solutions. In this case, but perhaps only this case, a more natural and precise representation would be a direct encoding of real values. Dreamy GAs originally featured a binary encoding. A dreamy GA will be presented that uses a continuous (or real-valued) coding of parameters. To follow is a more extensive discussion of convergence, coding issues and dreamy GAs, the introduction a new continuous-parameter genetic operator, and the presentation benchmark results. Convergence and Representation The schema theorem is invoked often to describe how GAs work. The binary version defines a schema as a string consisting of three characters, two of which are the basic 1 and 0. The third is a wildcard, or “don’t care”, character ∗ that can assume either value. An example of a schema defined on {1, 0, ∗} is {10∗01}. It represents the strings {10001, 10101}. Two important concepts associated with schemata are order and length. The order of a schema is the number of non-∗ symbols. In the example, the order is four. The length of a schema is the difference between the extreme fixed symbols, as read from left to right. The length of the example schema is four. The theorem states that short, low-order schemata with above-average fitness will increase in number at an exponential rate between generations2,3,4,5,6. As the GA proceeds to explore the search space, it seeks to optimize through the exploitation of these particular schemata, also known as building blocks4. Consider further the schema concept. A given string will by definition contain schemata. For example, the bitstring 1 contains {1, ∗} and 11 contains {11, 1∗, ∗1, ∗∗}. This means that a GA will process a large number of schemata implicitly, a property known as implicit parallelism5. The property allows building blocks to replicate quickly throughout the population of strings, leading to less variation (from the fittest) in the following generations, and homogeneity as a result. The GA converges prematurely if this happens before a desirable solution is found. Maintaining an amount of diversity in the population combats premature convergence. Mutation is one method of enforcing diversity, but the schema theorem requires that its use be minimized so as to avoid the disruption of fit strings, and hence its probability of occurrence is usually low, on the order of 0.001. As a result, the GA will be biased towards exploitation to the detriment of exploration. Another technique applies the concept at a representational level, as opposed to an operational level. Known as the dual GA approach, it introduces doubles into the population and makes diversity more of a condition of membership. It is the basis of dreamy algorithms, and will be discussed in detail in the following section. Strings coded using small alphabets (such as binary) represent more schemata than large alphabets7. It would seem then, according to the schema theorem, that GAs would favor small alphabets, but practice suggests otherwise. Encoding brittleness has been defined as the dependency of GA performance on the particular coding scheme chosen for a given problem8. Many coding schemes have been developed that are problem-specific, and it seems reasonable that the most desirable coding scheme would be robust, or amenable to a variety of applications9,10,11,12,13. GAs are highly coding-dependent. What works well from one problem may not in another case. In particular, consider the brittleness of binary coding when applied to a continuous, or real-valued, search space. Continuous values must first be coded into binary Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

strings for reproduction, and then decoded for fitness calculations. There is a loss of precision and speed during the process. In addition, attention must be given to storage considerations. Since the length of the bit string determines precision, increased precision means increased storage requirements above that required for continuous parameters. The schema theorem has been shown to apply to real alphabets14. Thus the GA will operate in a similar manner, but with different results for a more complex alphabet. Because many engineering problems are dependent on continuous domains, such representations are favored over the binary model as a solution to brittleness. They are not, however, a panacea, as will be demonstrated. Dreamy Genetic Algorithms Dreamy GAs were designed to introduce cycles of diversity into the standard GA. Implementation is based on the dual GA concept1,15,16,17,18. As originally proposed, dual GAs feature an enhanced representation of the familiar binary string. A wildcard headbit h is associated with each string and determines its interpretation. The headbit may assume either of the two binary values, each of which has a different meaning. If h = 0 the string is read as it appears; if h = 1 then the complement of the string is read. For example, the chromosome {0 1100} represents {1100}, whereas the anti-chromosome {1 1100} represents {0011}. The use of the headbit introduces doubles into the population, or stated differently, it creates dual populations, thus expanding the domain of potential solutions. Further, consider the strings {0 000, 1 111}. They represent the same individual, namely {000}, and are said to be doubles forming a dual pair. Dual pairs demonstrate the representational advantage: implicit mutation. Consecutive crossovers on this dual pair at, say, bit 2 and then 3 yields {0 010, 1 101}. Both represent {010}, or a mutation of {000} at bit 2. The implicit mutation rate decreases over time and is dependent on the proportion of dual pairs in the population. There is a dual analogue to explicit mutation known as mirroring, where the entire string is transformed into its complement. As expected, its probability of usage is low, like 0.01. Dreamy GAs are an extension of the dual paradigm. Natural sleep/awake cycles are adapted to allow for a more regimented approach to exploration and exploitation. While awake the GA proceeds as usual, converging towards a solution; while dreaming the GA breaks away to further explore the dual search space. Specifically, a dream phase restricts crossover to chromosomes of identical h values. The authors show that, for their binary model, the exploration/exploitation ratio increases during the dream phase and decreases during the awake phase, improving on both the standard binary and dual binary GAs. Real Dreams The purpose of this work is to combine the advantages of dreamy GAs and real coding by proposing a dreamy GA that is based on a continuous encoding of parameters. The adaptation required the selection of a real mating scheme and the creation of a new real-valued complement operator. Many methods of mating have been proposed for real GAs3,14,19,20,21. Real crossover requires more deliberation than binary. Consider a direct application of the latter to the former. Given two strings p1 = { α , β } and p2 = { φ , δ }, crossover at the second bit simply swaps information Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

between the two without introducing anything new: (p1)’ = { α , δ } and (p2)’ = { φ , β }. For the real dreamy algorithm, a method will be used that extrapolates from the values composing the parents to introduce new parameters22. First, a random number is used to select a crossover point α for two parents. p1 = { pm1 pm2 … pmα … pmNpar} p2 = { pd1 pd2 … pdα … pdNpar } where m = mom and d = dad. New parameters are formed from the crossover points using a random number β between 0 and 1. pnew1 = pmα - β(pmα - pdα) pnew2 = pdα + β(pmα - pdα) Crossover is completed as usual after the new values are inserted at the crossover point. (p1)’ = { pm1 pm2 … pnew1 … pdNpar } (p2)’ = { pd1 pd2 … pnew2 … pmNpar } The real-valued complement operator returns a bounded real number x2 for a given real number x1 with the same bounds. If the upper bound is U and the lower bound is L then x2 = (U – x1) + L Note that when applied to Base10 integers that are greater than or equal to zero, where U and L are binary complements, it performs a complement operation on the associated binary strings for the integers within and at the bounds. See Table 1 for an example. N Real Comp. Binary(N) Binary Comp. Decoded 7 0 111 000 0 6 1 110 001 1 5 2 101 010 2 4 3 100 011 3 3 4 011 100 4 2 5 010 101 5 1 6 001 110 6 0 7 000 111 7

Upper Bound: 7 Lower Bound: 0

Table 1. Base10 complement example for real complement operator. It has the same effect on Base10 integers and binary strings in a 1’s complement system where U and L are binary complements, excepting zero. See Table 2.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

N Real Comp. Binary(N) Binary Comp. Decoded 3 -3 011 100 -3 2 -2 010 101 -2 1 -1 001 110 -1 0 -1 1 110 001 1 -2 2 101 010 2 -3 3 100 011 3

Upper Bound: 3 Lower Bound: -3

Table 2. 1’s Complement Example for real complement operator. Because it is based on special cases of binary manipulation it is considered a simulated binary complement operator for bounded real values. Experimental Results and Discussion The performance of binary dreamy GAs was originally measured using Whitley’s executable function, which predicts the proportions of individuals over time for comparison to a function of predefined values23. The particular type of problem simulated was the deceptive problem, which leads the GA away from the global optimal with an individual of nearly comparable fitness24. The aim is to demonstrate the importance of not only diversity but also encoding. So instead, DeJong’s five-function test suite25 will be used. The fifth function is modified for three additional problems and add an extra, non-related function to the group for a total of 9 test functions. The extra function is: Calc12 = 4x1x2 – x14 – x24 + x1. It is also modified from its original form26. Graphs of all the modified functions are found in the appendix. The binary strings contained four bits so that chromosomes were of eight bits. The crossover probability was 1 for all algorithms for a population size of 20 over 1000 generations. The mutation probability for the binary algorithm was 0.001 and the mirroring probability for the dreamy algorithms was 0.01. The dreamy algorithms were restricted to simple transitions of phases; specifically, there were two dream phases at 250 generations per and two awake phases for the same number over the total of 1000 generations. The average function value over 10 runs is reported for each algorithm. All algorithms were set to maximize, so the functions were adapted accordingly. Minimum values are maximums multiplied by –1. These parameters are generally representative of what is reported in the literature. The results follow in the comparison charts of Figure 3. Calc12 Comparison

DeJongf1 Comparison

3

0.8 0.7 0.6

2

Min = 0

3.04

2.5

Max

1.5 1

Average Maximum

0.4 0.3 0.2

0.5 0

0.5

0.1

Binary

Real Dreamy

Binary Dreamy

2.3613846

2.8555019

1.93375495

0 Average Minimum

Binary

Real Dreamy

Binary Dreamy

0.7373046

0.0003122

0.2114077

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

DeJongf2 Comparison

DeJongf3 Comparison 10

8

8

Max = 10

Min = 0

6 4 2 0 Average Minimum

6 4 2

Binary

Real Dreamy

Binary Dreamy

6.33226

0.4449953

1.6109319

0 Average Maximum

DeJongf4 Comparison

1 Max

Min = 0

0.7 0.68 0.66 0.64

Binary

Real Dreamy

Binary Dreamy

0.7449319

0.7393666

0.650058

Average Maximum

Binary

Real Dreamy

Binary Dreamy

0.0375155

0.1973231

0.0480626

DeJongf5-FWE Comparison

0.35

0.5

0.3

0.4

0.25

1

1

0.1

0

DeJongf5-FWT Comparison

Max

0.2

Max

0.15

0.05

0.62

0.15 0.1

0.3 0.2 0.1

0.05

Average Maximum

8.9

0.2

0.72

0

Binary Dreamy

7.8

0.25

0.74

Average Minimum

Real Dreamy

7.1

DeJongf5 Comparison

0.76

0.6

Binary

Binary

Real Dreamy

Binary Dreamy

0.0603467

0.306645

0.043964

0 Average Maximum

Binary

Real Dreamy

Binary Dreamy

0.2525988

0.4427164

0.2106854

DeJongf5-FWTS 0.8 0.7

Max > 1

0.6 0.5 0.4 0.3 0.2 0.1 0 Average Maximum

Binary

Real Dreamy

Binary Dreamy

0.4264278

0.6906731

0.4337953

Figure 3. Comparison Charts for GA Trail Results Using DeJong’s Five Functions.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

For the parameters chosen, the binary dreamy outperformed the ordinary binary algorithm on 6/9 of the functions, a clear majority. This supports the work of Collard and Escazut1. The binary dreamy algorithm indeed improves on the search capabilities of the traditional formulation. The real dreamy algorithm performed better than both on 7/9 of the benchmark functions. It encountered trouble on function 3, the step function, and function 4, the noisy function. It did markedly better than both on the various versions of function 5, where search is an important factor. The behavior of each algorithm is noted in view of the preceding discussions on convergence and representation. The binary dreamy GA did not outperform the simple binary in every case. This supports the original argument by Collard and Escazut1 that for equal coding, the execution is dependent on the choice of parameters. Considering the results of the real dreamy algorithm the performance is ultimately coding-dependent. A comparison to Wright’s results14 further demonstrates both contentions. His binary algorithm’s best performance was on function 5, whereas the real dreamy algorithm had a better showing. The effect of crossover operators is not to be discounted (he used real and linear crossover), as a further assessment will reveal, but the deciding factor is coding. Conclusions The dreamy approach improves on the traditional search process. The introduction of doubles into the search space and the characteristic implicit mutations serve to increase diversity and decrease the occurrences of premature convergence. This was shown to be true with different methods of coding with varying degrees of success. The disparate results suggest that a more multi-purpose, robust encoding scheme be developed for implementation of the dreamy method.

References 1.

Collard, P., Escazut, C., 1998, “Genetic Algorithms at the Edge of a Dream”, Artificial Evolution: Third European Conference, pp.69-80. 2. Altenberg, L., 1995, “The Schema Theorem and Price’s Theorem”, Foundations of Genetic Algorithms, No. 3, pp. 23-49. 3. Herrera, F., Lozano, M., Verdegay, J.L., 1998, “Tackling Real-Coded Genetic Algorithms: Operators and Tool for Behavioral Analysis”, Artificial Intelligence Review, pp. 265-319. 4. Mitchell, M., 1999, An Introduction to Genetic Algorithms, MIT Press, Massachusetts, pp. 29-30, 167, 156. 5. Whitley, D., 1994, “A Genetic Algorithm Tutorial”, Statistics and Computing, Vol. 4, pp. 65-85. 6. Wright, A., “The Exact Schema Theorem”, URL: http://www.cs.umt.edu/CS/FAC/WRIGHT/pubs.htm. 7. Goldberg, D., 1991, “Real-Coded Genetic Algorithms, Virtual Alphabets and Blocking”, Complex Systems 5, pp. 139-168. 8. Ronald, S., 1997, “Robust Encodings in Genetic Algorithms”, Evolutionary Algorithms in Engineering Applications, pp. 29-44. 9. Deb, K., 1997, “GeneAS: A Robust Optimal Design Technique for Mechanical Component Design”, Evolutionary Algorithms in Engineering Applications, pp. 497-514. 10. Lam, S.S., Tang, K.W.C., Cai, X., 1996, “Genetic Algorithm with Pigeon-Hole Coding Scheme for Solving Sequencing Problems” Applied Artificial Intelligence, pp. 239-256. 11. Na, K.M., Chae, S.I., Ann, S.G., 1995, “Modified Delta Coding Algorithm for Real-Parameter Optimization”, Electronics Letters, pp. 1169-1170. Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

12. Schraudolph, N., Belew, R., “Dynamic Parameter Encoding for Genetic Algorithms”, UCSD Technical Report CS90-175, University of California, San Deigo. 13. Streifel, R., Marks II, R., Reed, R., Cjoi, J., Healy, M., 1999, “Dynamic Fuzzy Control of Genetic Algorithm Parameter Coding”, IEEE Transactions on Systems, Man and Cybernetics—Part B: Cybernetics, Vol. 29, No. 3, pp. 426-433. 14. Wright, A., 1991, “Genetic Algorithms for Real Parameter Optimization”, Foundations of Genetic Algorithms, pp. 205-218. 15. Collard, P., Aurand, J.P., 1994, “DGA: An Efficient Genetic Algorithm”, ECAI ’94: European Conference on Artificial Intelligence, pp. 487-491. 16. Collard, P., Escazut, C., 1995, “Genetic Operators in a Dual Genetic Algorithm”, ICTAI ’95: Proceedings of the Seventh IEEE International Conference on Tools with Artificial Intelligence, pp. 12-19. 17. Collard, P., Escazut, C., 1995, “Relational Schemata: A way to improve the expressiveness of classifiers”, ICGA ’95: Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 397-404. 18. Collard, P., Escazut, C., 1996, “Fitness Distance Correlation in a Dual Genetic Algorithm”, ECAI ’96: 12th European Conference on Artificial Intelligence, pp. 218-222. 19. Deb, K., Agrawal, R.B., 1995, “Simulated Binary Crossover for Continuous Search Space”, Complex Systems 9, pp 115-148. 20. Deb, K., Beyer, H.G., 1999, “Self-Adaptation in Real-Parameter Genetic Algorithms with Simulated Binary Crossover”, GECCO ’99: Genetic Algorithms. 21. Rasheed, K., Hirsh, H., Gelsey, A., “A Genetic Algorithm for Continuous Design Search Space”, Rutgers University Computer Science Dept. Technical Report dcs-tr-352, URL: http://www.cs.rutgers.edu/pub/technical-reports. 22. Haupt, R., Haupt, S.E., 1998, Practical Genetic Algorithms. John Wiley & Sons, New York, pp. 49-65. 23. Whitley, D., 1993, “An Executable Model of a Simple Genetic Algorithm”, Foundations of Genetic Algorithms 2, pp. 45-62. 24. Whitley, D., 1991, “Fundamental Principles of Deception in Genetic Search”, Foundations of Genetic Algorithms, pp. 221-241. 25. DeJong, K.A., 1975, “Analysis of the Behavior of a Class of Genetic Adaptive Systems”, Ph.D. Dissertation, Dept. of Computer and Communications Sciences, University of Michigan, Ann Arbor, MI. 26. Larson, R., Hostetler, R., Edwards, B., 1990, Calculus, 4th Ed., 7th Printing, Heath, Massachusetts, p. 890.

ERIC J. GAUDET III Mr. Gaudet is a graduate student at the University of Louisiana at Lafayette, and is employed by an engineering consulting firm serving the petrochemical industry in Lake Charles, Louisiana. His research interests include optimization, genetic algorithms and finite element analysis. Mr. Gaudet is a registered engineer in Louisiana. TERRENCE L. CHAMBERS Dr. Chambers is an Assistant Professor and the Mechanical Engineering/LEQSF Regents Professor in Mechanical Engineering at the University of Louisiana at Lafayette. His research interests include design optimization and artificial intelligence. He is a member of ASME and ASEE, and is currently serving as the Vice-President of the ASEE Gulf-Southwest Section. Prof. Chambers is a registered Professional Engineer in Texas and Louisiana. WILLIAM E. SIMON Dr. Simon is a Professor and Department Chair in the Mechanical Engineering Department at the University of Louisiana at Lafayette, and holds a Ph.D. in Mechanical Engineering from the University of Houston. He is a registered PE in Louisiana and Texas and is a member of ASME, Pi Tau Sigma, Tau Beta Pi, Phi Kappa Phi, and LES. Areas of interest include Heat Transfer, Thermodynamics, HVAC and Aerospace Power Systems.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

Appendix In Figures A1 – A3 are depictions of the modified version of DeJong’s fifth function. Featured are different combinations of trenches and extra foxholes. Figure A4 presents the graph of an additional function that is somewhat deceptive in that it has a local optimum near the global. It is included to measure the search capabilities of each GA with a misleading solution point. 1.200

1.000

0.800 f 0.600 0.400 0.200 0.000 49

X2

30 11

7 19

-17

-27 -5

-41

-8 -29

-65

-53

X1

-46

55

31

43

Figure A1. DeJong’s Foxholes with a Trench (DeJongf5-FWT). -65

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

1.200

1.000

0.800 f 0.600 0.400 0.200 45

0.000

X2

-43 -65

55

31

43

7

X1

19

-17

-21 -5

-41

-29

1 -53

-65

23

Figure A2. DeJong’s Foxholes with Extra Hole (DeJongf5-FWE).

1.400 1.200 1.000 0.800

f

0.600 0.400

61 43

0.200 25 0.000

-65

-29

-41

-65

-53

-5

-47

-17

7

-29

31

55

-11

19

X2

43

7

X1

Figure A3. DeJong’s Foxholes with Trenches and a Sinkhole (DeJongf5-FWTS).

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education

10

0

-10

f -20

-30

-40 1.75 1 -50

X2

-1.25 -2 2

1.5

1

0 0.5

X1

-0.5

-1

-1.5

-2

0.25 -0.5

Figure A4. Calc12.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference, The University of Louisiana at Lafayette, March 20-22, 2002. Copyright  2002, American Society for Engineering Education