ࡱ> G bjbjَ ( ]8$T,'@#B#B#B#=#9%&$(*''VVVV @#@#VV@#@#2dQ4@#Introduction to Genetic Algorithms Theory and Applications The Seventh Oklahoma Symposium on Artificial Intelligence November 19, 1993 Roger L. Wainwright Dept. of Mathematical and Computer Sciences The University of Tulsa 600 South College Avenue Tulsa, OK 74104-3189 (918) 631-3143 rogerw@penguin.mcs.utulsa.edu C Copyright RLW 1993 Tutorial Outline Part I Introduction and Concepts of Genetic Algorithms _ Bibliography _ GA Definitions _ Overview of GAs _ When to Use GAs _ GA vs Traditional Algorithms _ GA vs SA _ Applications of GA _ The Standard GA (Algorithm) _ Population Representation _ Reproduction _ Example GA Fitness Function _ Roulette Wheel _ Crossover _ Mutation _ Schema Theory _ Fundamental Theorem of GA _ Deception _ Genetic Programming Tutorial Outline Part II Example Applications of Genetic Algorithms _ Order Based GAs _ PMX Crossover _ TSP GA _ Additional Applications using GAs _ Three Dimensional Bin Packing _ Set Covering Problem _ Multiple Vehicle Routing _ Neural Network GA _ Parallel GA Issues _ Genetic Algorithm Packages _ GATutor _ GA Newsletter and How to Join Primary GA Bibliography (1993) 1.Proceedings of the First International Conference on Genetic Algorithms, John Grefenstette, Editor, Lawrence Erlbaum Assoc., 1985. 2.Proceedings of the Second International Conference on Genetic Algorithms, John Grefenstette, Editor, Lawrence Erlbaum Assoc., 1987. 3.Proceedings of the Third International Conference on Genetic Algorithms, J. David Schaffer, Editor, Morgan Kaufmann, 1989. 4.Proceedings of the Fourth International Conference on Genetic Algorithms, Richard Beler, Editor, Morgan Kaufmann, 1991. 5.Proceedings of the Fifth International Conference on Genetic Algorithms, Stephanie Forrest, Editor, Morgan Kaufmann, 1993 6.Genetic Algorithms and Simulated Annealing, Lawrence Davis, Editor, Pitman Publishing, 1987. 7.Handbook of Genetic Algorithms, Lawrence Davis, Editor, Van Nostrand Reinhold, 1991. 8.Genetic Algorithms in Optimization, Search and Machine Learning, David Goldberg, Addison Wesley, 1989. 9.Adaptation in Natural and Artificial Systems, John H. Holland, The University of Michigan Press, Ann Arbor, MI, 1975. 10.Adaptation in Natural and Artificial Systems, John H. Holland, MIT Press, 1992. 11.Genetic Programming, John R. Koza, MIT Press, 1992. 12.Parallel Problem Solving from Nature 2, Reinhard Manner and Bernard Manderick, Editors, Noth-Holland, 1992. 13.Foundations of Genetic Algorithms, Gregory Rawlins, Editor, Morgan Kaufmann, 1991. 14.Foundations of Genetic Algorithms 2, Darrell Whitley, Editor, Morgan Kaufmann, 1993. 15.Nicol N. Schraudolph, "Genetic Algorithm Software Survey", available by anonymous ftp from cs.ucsd.edu as /pub/GAucsd/GAsoft.txt, August, 1992. Other GA References (1993) 16.J. Grefenstette, GENESIS, Navy Center for Applied Research in Artificial Intelligence, Navy research Lab., Wash. D.C. 20375-5000. 17.J. Grefenstette, "Optimization of Control Parameters for Genetic Algorithms", IEEE Transactions on Systems, Man and Cybernetics, pp. 122-128, 1986. 18.H. Muehlenbein, "Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization", Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, 1989. 19.R. Tanese, "Distributed Genetic Algorithms, Proceedings of the Third International Conference on Genetic Algorithms, ed. J.D. Schaffer, Morgan Kaufmann, pp. 434-439, 1989. 20.T. Starkweather, S. McDaniel, K. Mathias, D. Whitley and C. Whitley, "A Comparison of Genetic Sequencing Operators", Proceedings of the Fourth International Conference on Genetic Algorithms, June, 1991. 21.T. Starkweather, D. Whitley, and K. Mathias, "Optimization Using Distributed Genetic Algorithms," in Parallel Problem Solving from Nature, ed. H. Schwefel and R. Maenner, Springer Verlag, Berlin, Germany, 1991. 22.D. Whitley, T. Starkweather, and C. Bogart, "Genetic Algorithm and Neural Networks: Optimizing Connections and Connectivity", Parallel Computing, 14:347-361. 23.D. Whitley and J. Kauth, GENITOR: A Different Genetic Algorithm, Proceedings of the Rocky Mountain Conference on Artificial Intelligence, Denver, Co., 1988, pp. 118-130. 24.D. Whitley, T. Starkweather, and D. Fuquat, "Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator", Proceedings of the Third International Conference on Genetic Algorithms, June, 1989. 25.D. Whitley and T. Starkweather, "GENITOR II: A Distributed Genetic Algorithm", Journal of Experimental and Theoretical Artificial Intelligence, 2(1990) 189-214. University of Tulsa GA References (1993) 26.Abuali, F. N., Schoenefeld, D. A. and Wainwright, R. L. "The Design of a Multipoint Line Topology for a Communication Network Using Genetic Algorithms", Seventh Oklahoma Conference on Artificial Intelligence, November, 1993. 27.Abuali, F.N., Schoenefeld, D.A. and Wainwright, R.L., "Terminal Assignment in a Communication Network Using Genetic Algorithms", to appear in the 22nd Annual ACM Computer Science Conference - CSC'94, March, 1994. 28.Blanton, J.L. and Wainwright, R.L. "Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms", Proceedings of the Fifth International Conference on Genetic Algorithms (ICGA-93), Stephanie Forrest, Editor, Morgan Kaufmann Publisher, 1993, pp. 452-459. 29.Corcoran, A. L. and Wainwright, R. L. "A Genetic Algorithm for Packing in Three Dimensions", Proceedings of the 1992 ACM Symposium on Applied Computing, March 1-3, 1992, pp. 1021-1030, ACM Press. 30.Corcoran, A. L. and Wainwright, R. L., "LibGA: A User-Friendly Workbench for Order-Based Genetic Algorithm Research", Proceedings of the 1993 ACM/SIGAPP Symposium on Applied Computing, February, 14-16, 1993, pp. 111-117, ACM Press. 31.Corcoran, A.L. and Wainwright, R.L. "The Performance of a Genetic Algorithm on a Chaotic Objective Function", Seventh Oklahoma Conference on Artificial Intelligence, November, 1993. 32.Knight, L. R. and Wainwright, R. L. "HYPERGEN - A Distributed Genetic Algorithm on a Hypercube", Proceedings of the 1992 IEEE Scalable High Performance Computing Conference, Williamsburg, VA., April 26-29, 1992, pp. 232-235, IEEE Press. 33.Mutalik, P. M., Knight, L. R., Blanton, J. L. and Wainwright, R. L. "Solving Combinatorial Optimization Problems Using Parallel Simulated Annealing and Parallel Genetic Algorithms", Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing, March 1-3, 1992. pp. 1031-1038, ACM Press. 34.Prince, C., Wainwright, R.L., Schoenefeld, D.A. and Tull, T., "GATutor: A Graphical Tutorial System for Genetic Algorithms" to appear in the 25th ACM SIGCSE Technical Symposium - SIGCSE'94, March, 1994. 35.Sekharan, D. Ansa and Wainwright, R. L., "Manipulating Subpopulations of Feasible and Infeasible Solutions in Genetic Algorithms", Proceedings of the 1993 ACM/SIGAPP Symposium on Applied Computing, February, 14-16, 1993, pp. 118-125, ACM Press. 36.Sekharan, D. Ansa and Wainwright, R. L., "Manipulating Subpopulations in Genetic Algorithms for Solving the k-way Graph Partitioning Problem", Seventh Oklahoma Conference on Artificial Intelligence, November, 1993. 37.Wu, Yu and Wainwright, R. L., "Near-Optimal Triangulation of a Point Set using Genetic Algorithm", Seventh Oklahoma Conference on Artificial Intelligence, November, 1993. Genetic Algorithm Definitions Grefenstette [16] "A genetic Algorithm is an iterative procedure maintaining a population of structures that are candidate solutions to specific domain challenges. During each temporal increment (called a generation), the structures in the current population are rated for their effectiveness as domain solutions, and on the basis of these evaluations, a new population of candidate solutions is formed using specific genetic operators such as reproduction, crossover, and mutation." Goldberg [8] "They combine survival of the fittest among string structures with a structured yet randomized information exchange to form a search algorithm with some of the innovative flair of human search. In every generation, a new set of artificial creatures (strings) is created using bits and pieces of the fittest of the old; an occasional new part is tried for good measure. While randomized, genetic algorithms are no simple random walk. They efficiently exploit historical information to speculate on new search points with expected improved performance." Genetic Algorithms Overview _ Developed by John Holland in 1975 [9]. _ Genetic Algorithms (GAs) are search algorithms based on the mechanics of the natural selection process (biological evolution). The most basic concept is that the strong tend to adapt and survive while the weak tend to die out. That is, optimization is based on evolution, and the "Survival of the fittest" concept. _ GAs have the ability to create an initial population of feasible solutions, and then recombine them in a way to guide their search to only the most promising areas of the state space. _ Each feasible solution is encoded as a chromosome (string) also called a genotype, and each chromosome is given a measure of fitness via a fitness (evaluation or objective) function. _ The fitness of a chromosome determines its ability to survive and produce offspring. _ A finite population of chromosomes is maintained. Genetic Algorithms Overview Continued _ GAs use probabilistic rules to evolve a population from one generation to the next. The generations of the new solutions are developed by genetic recombination operators: _ Biased Reproduction: selecting the fittest to reproduce) _ Crossover: combining parent chromosomes to produce children chromosomes _ Mutation: altering some genes in a chromosome. _ Crossover combines the "fittest" chromosomes and passes superior genes to the next generation. _ Mutation ensures the entire state-space will be searched, (given enough time) and can lead the population out of a local minima. _ Most Important Parameters in GAs: _ Population Size _ Evaluation Function _ Crossover Method _ Mutation Rate Genetic Algorithms Overview Continued _ Determining the size of the population is a crucial factor _ Choosing a population size too small increases the risk of converging prematurely to a local minima, since the population does not have enough genetic material to sufficiently cover the problem space. _ A larger population has a greater chance of finding the global optimum at the expense of more CPU time. _ The population size remains constant from generation to generation. Genetic Algorithms Overview Continued _ A robust search technique _ GAs will produce "close" to optimal results in a "reasonable" amount of time _ Suitable for parallel processing _ Some problems are deceptive _ Can use a noisy fitness function _ Fairly simple to develop _ Makes no assumptions about the problem space _ GAs are blind without the fitness function. The Fitness Function Drives the Population Toward Better Solutions and is the most important part of the algorithm. _Probability and randomness are essential parts of GA Use Genetic Algorithms _ When an acceptable solution representation is available _ When a good fitness function is available _ When it is feasible to evaluate each potential solution _ When a near-optimal, but not optimal solution is acceptable. _ When the state-space is too large for other methods Genetic Algorithms vs Traditional Algorithm Goldberg [8] 1. The GA works with a coding of the parameter rather than the actual parameter. 2. The GA works from a population of strings instead of a single point. 3. Application of GA operators causes information from the previous generation to be carried over to the next. 4. The GA uses probabilistic transition rules, not deterministic rules. Genetic Algorithms vs. Simulated Annealing SA _ 1 Feasible Solution _ Perturbation Function _ Acceptance Function _ Temperature Parameter GA _ Population of Feasible Solutions _ Evaluation Function _ Selection Bias _ Reproduction _ Mutation Applications of Genetic Algorithms _ Scheduling: Facility, Production, Job, and Transportation Scheduling _ Design: Circuit board layout, Communication Network design, keyboard layout, Parametric design in aircraft _ Control: Missile evasion, Gas pipeline control, Pole balancing _ Machine Learning: Designing Neural Networks, Classifier Systems, Learning rules _ Robotics: Trajectory Planning, Path planning _ Combinatorial Optimization: TSP, Bin Packing, Set Covering, Graph Bisection, Routing, _ Signal Processing: Filter Design _ Image Processing: Pattern recognition _ Business: Economic Forecasting; Evaluating credit risks Detecting stolen credit cards before customer reports it is stolen _ Medical: Studying health risks for a population exposed to toxins The Standard Genetic Algorithm >>>> Use the flowchart I created >>>> Replace this page with flowchart page GENETIC ALGORITHMS Preliminary Considerations 1. Determine how a feasible solution should be represented a) Choice of Alphabet. This should be the smallest alphabet that permits a natural expression of the problem. b) The String Length. A string is a chromosome and each symbol in the string is a gene. 2. Determine the Population Size. This will remain constant throughout the algorithm. Choosing a population size too small increases the risk of converging prematurely to a local optimum, since the population does not sufficiently cover the problem space. A larger population has a greater chance of finding the global optimum at the expense of more CPU time. 3. Determine the Objective Function to be used in the algorithm. A Genetic Algorithm 1. Determine an Initial Population. a) Random or b) by some Heuristic 2. REPEAT A. Determine the fitness of each member of the population. (Perform the objective function on each population member) Fitness Scaling can be applied at this point. Fitness Scaling adjusts down the fitness values of the super- performers and adjusts up the lower performers, promoting competition among the strings. As the population matures, the really bad strings will drop out. Linear Scaling is an example. B. Reproduction (Selection) Determine which strings are "copied" or "selected" for the mating pool and how many times a string will be "selected" for the mating pool. Higher performers will be copied more often than lower performers. Example: the probability of selecting a string with a fitness value of f is f/ft, where ft is the sum of all of the fitness values in the population. Genetic Algorithm Continued C. Crossover 1. Mate each string randomly using some crossover technique 2. For each mating, randomly select the crossover position(s). (Note one mating of two strings produces two strings. Thus the population size is preserved.) D. Mutation Mutation is performed randomly on a gene of a chromosome. Mutation is rare, but extremely important. As an example, perform a mutation on a gene with probability .005. If the population has g total genes (g = string length * population size) the probability of a mutation on any one gene is 0.005g, for example. This step is a no-op most of the time. Mutation insures that every region of the problem space can be reached. When a gene is mutated it is randomly selected and randomly replaced with another symbol from the alphabet. UNTIL Maximum number of generation is reached. Various Population Representations _ Chromosomes can be represented as _ Bit Strings (1011 ... 0100) _ Reals (19.3, 45.1, -12.9, ... 6.2) _ Integers (1,4,2,7,5,9,3,6,8) Usually Permutations of 1..n _ Characters (A, G, Q, ... F) Usually Permutations _ List of rules (R1, R2, ... R20) _ Chromosomes are all of the same type (Bit Strings) _ Chromosomes are all the same length _ The population size remains constant from generation to generation Reproduction (Survival of the fittest) Parents are SELECTED for REPRODUCTION biased on the fitness function Consider the fitness function f(x) = 4 * cos(x) + x + 2.5 0 <= x >= 31 >>> Graph of P0 data points <<< Initial Population P0 No. Times No. Chromosome x f(x) P(x) Selected* 1 1001 1 19 25.459 .185 2 2 01 010 10 9.144 .066 1 3 1 1001 25 31.465 .229 2 4 00110 6 12.341 .090 0 5 0 1011 11 13.518 .098 1 6 1011 1 23 23.369 .170 1 7 00100 4 3.885 .028 0 8 10 001 17 18.399 .134 1 SUM 115 137.580 1.000 8 AVE 14 17.198 .125 1 MAX 25 31.465 .229 2 f(Pop)= sum f(x)/n = 137.58 / 8 = 17.198 P(x) = f(x) / sum f(x) = the Probability of Selection * Based on Selection Roulette Wheel The Selection Roulette Wheel Roulette: the classical selection operator for generational GA as described by Goldberg. Each member of the pool is assigned space on a roulette wheel proportional to its fitness. The members with the greatest fitness have the highest probability of selection. This selection technique works only for a GA which maximizes its objective function. << wheel >> Crossover _ Causes an exchange of genetic material between two parents _ Crossover point(s) is determined stochastically _ The Crossover Operator is the most important feature in a GA Single Point Crossover Example Parent 1 1 0 0 1 0 0 1 0 1 0 Parent 2 0 0 1 0 1 1 0 1 1 1 Child 1 1 0 0 0 1 1 0 1 1 1 Child 2 0 0 1 1 0 0 1 0 1 0 Double Point Crossover Example Parent 1 1 1 0 1 0 0 1 0 0 1 0 1 1 Parent 2 0 1 0 1 1 0 0 0 1 0 1 0 1 Child 1 1 1 0 1 0 0 0 0 1 0 0 1 1 Child 2 0 1 0 1 1 0 1 0 0 1 1 0 1 Mutation _ The Mutation operator guarantees the entire state-space will be searched, given enough time. _ Restores lost information or adds information to the population. _ Performed on a child after crossover. _ Performed infrequently (For example, 0.005 probability of altering a gene in a chromosome) Child 1 1 1 0 1 0 0 0 0 1 0 0 1 1 after mutation 1 1 0 1 1 0 0 0 1 0 0 1 1 _ Special Mutation operators may be application dependent (TSP) _ Adaptive Mutation: _ Monitor the hamming distance between two parents. _ The more similar the parents, the more likely mutation is applied. Whitley, Starkweather [25] Continuation of the fitness function f(x) = 4 * cos(x) + x + 2.5 0 <= x >= 31 Population P1 (After Crossover. Assume no Mutation) No. New Parents Crossover x f(x) Chromosome (from P0) Point 1 01 001 (2,8) 2 9 7.8552 2 10 010 (2,8) 2 18 23.141 3 1001 1 (1,6) 4 19 25.459 4 1011 1 (1,6) 4 23 23.369 5 1 1011 (3,5) 1 27 28.331 6 0 1001 (3,5) 1 9 7.855 7 100 01 (1,3) 3 17 18.399 8 110 11 (1,3) 3 27 28.331 SUM 149 162.740 AVE 18 20.343 MAX 27 28.331 f(Pop0) = 17.198 f(Pop1) = 20.343 >>> plot of the function showing the 8 initial points of Pop0 and the 8 points of Pop1 Schema Theory (John Holland) _ An abstract way to view the complexities of crossover. _ Consider 6-bit representations where * indicates don't care 0***** represents a subset of 32 strings 1**00* represents a subset of 8 strings _ Let H represent a schema such as 1**1** _ Order: o(H) The number of fixed positions in the schema, H. o(1*****) = 1, o(1**1*1) = 3 _ Length: delta(H) The distance between sentinel fixed positions in H. delta(1**1**) = (4-1) = 3 delta(1*****) = 0 delta(***1**) = 0 Fundamental Theorem of Genetic Algorithms (The Schema Theorem) The expected number of copies, m, of schema H is bounded by: >>>> Slide from GATUTOR 91 Where m - number of schemata H - schema t - time or generation f - fitness function fave - average fitness value pc - crossover probability delta - length l - string length pm - mutation probability o - order Consider H = 1**** in the above problem: The Schema Theorem states that m(H,P1) >= m(H,P0) f(H)/fave 6 >= 4 * 25.753 / 17.198 6 >= 6 (Note in this case o(1****) = 1 and delta(1****) = 0 and pm = 0 greatly reducing the formula) In Other Words: Theorem: The number of representatives of any schema, S, increases in proportion to the observed relative performance of S. Deception What Problems are Difficult for GAs Example: an order-3 deception [25] "information represented by the schemata in the search space leads the search away from the global optimum, and instead directs the search toward the binary string that is the complement of the global optimum. The search space is order-3 deceptive .. if the following relationships hold for the [three-bit] schemata:" 0** > 1** and 00* > 11*, 01*, 10* *0* > *1* and 0*0 > 1*1, 0*1, 1*0 **0 > **1 and *00 > *11, *01, *10 but, 111 > 000, 001, 010, 100, 110, 101, 011 Example: f(000) = 28 f(100) = 14 f(001) = 26 f(101) = 10 f(010) = 22 f(110) = 5 f(011) = 20 f(111) = 30 Chaotic, noisy and "needle in a haystack" functions GA-easy, GA-hard problems Overview of Genetic Programming Koza [11] Manipulate strings of instructions rather than strings of data. Goal: Allow computers to develop their own software (Survival of the fittest computer programs) Crossover and mutation manipulate branches of the program tree. "Genetic Programming starts with an initial population of randomly generated computer programs composed of functions and terminals appropriate to the problem domain. The functions may be standard arithmetic operations, standard programming operations, standard mathematical functions, logical functions, or domain-specific functions. Depending on the particular problem, the computer program may be Boolean-valued, integer-valued, real-valued, complex-valued, vector-valued, symbolic valued, or multiple-valued. The creation of this initial random population is, in effect, a blind random search of the search space of the problem. Each individual computer program in the population is measured in terms of how well it performs in the particular problem environment. This measure is called the fitness measure. The nature of the fitness measure varies with the problem" [11]. Koza's initial problem: Given a set of initial predicates and possible actions, develop (evolve) a computer program (in Lisp) to control the movement of an ant searching for food. The chromosome is a variable sized Lisp program where the leaf nodes are actions (left, right, move, etc.), and the internal nodes are predicates or logic controls (if found food), etc. Each chromosome (program) is used to control the actions of a simulated ant in searching for food. The evaluation function for a given chromosome is the amount of food gathered by an ant in a fixed amount of time. Consider the following two parent computer programs given as LISP S-expressions. <<<>>>> These two parents are equivalently represented as: (OR (NOT D1) (AND D0 D1)) and (OR (OR D1 (NOT D0)) (AND (NOT D0) (NOT D1))). The first parent has 6 nodes (points) in its S-expression, and the second parent has 10 points in its S-expression as shown above. Randomly select any one of the 6 points in parent 1 as its crossover point, say node "NOT". Randomly select any one of the 10 points in parent 2 as its crossover point, say node "AND". The Selected S-expressions are shown below. <<< Fig 6.6 page 102 >> The above crossover fragments are exchanged at node "NOT" in the first parent, and node "AND" in the second parent to produce the following two children S-expressions [11]. <<<< Fig 6.7 page 102 >>> Part II Example Applications of Genetic Algorithms Order-Based Genetic Algorithms _An order-based GA is where all chromosomes are a permutation of the list. _Order-based GAs greatly reduce the size of the search space by pruning solutions that we do not want to consider. _Order-based GAs can be applied to a number of classic combinatorial optimization problems such as: TSP, Bin Packing, Package Placement, Job Scheduling, Network Routing, Vehicle Routing, various layout problems, etc. _Crossover functions for order-based GAs include Edge Recombination, Order Crossover #1, Order Crossover #2, PMX, Cycle Crossover, Position Crossover, etc. Whitley and Starkweather [20,25]. PMX (Partially Matched Crossover) Parent 1 3 7 1 9 | 6 4 5 | 2 8 Parent 2 4 7 8 5 | 3 9 2 | 1 6 ( 6 <--> 3 ) ( 4 <--> 9 ) ( 5 <--> 2 ) Child 1 6 7 1 4 | 3 9 2 | 5 8 Child 2 9 7 8 2 | 6 4 5 | 1 3 Mutation functions for order-based GAs include Swap two elements * * * * 9 8 7 6 5 4 3 2 1 ==> 9 3 7 6 5 4 8 2 1 Move one element * * 9 8 7 6 5 4 3 2 1 ==> 9 8 6 5 4 3 7 2 1 Reorder a sublist 9 8 | 7 6 5 4 3 | 2 1 ==> 9 8 | 5 3 4 6 7 | 2 1 Traveling Salesman Problem Example TSP GA executions adjusting pool size: TSP 1024 Cities. PoolSize 500 250 125 Length_String 1024 Trials 100000 Bias 1.9 RandomSeed 15394157 MutateRate 0.15 NodeFile cities1024 StatusInterval 5000 RESULT = 116987 88436 90906 TSP 320 Cities. PoolSize 2000 1000 500 250 125 Length_String 320 Trials 100000a Bias 1.9 RandomSeed 15394157 MutateRate 0.15 NodeFile cities320 StatusInterval 1000 RESULTS: Best: 30,761b 25,708 21,366 18,676c 23,760d Worst: 35,102 28,366 23,235 18,676 23,760 Average: 34,209 27,863 22,880 18,676 23,760 a A poolsize of 2000 for 205,000 trials yielded best of 22,777 b CPU time on a SPARC 1+ was approximately 100 minutes. c Converged after 72,000 trials d Converged prematurely after 33,000 trials TSP 105 Cities. PoolSize 750 500 250 125 Length_String 105 Trials 70000 Bias 1.9 RandomSeed 15394157 MutateRate 0.15 NodeFile cities105 StatusInterval 1000 RESULTS: Trials at Convergence: 109,000 61,000 32,000 9,000 Best: 16,503 17,193 24,079 32,370 Worst: 16,503 17,193 24,079 32,370 Average: 16,503 17,193 24,079 32,370 Additional Applications Using GAs Three Dimensional Bin Packing Using GAs [29] Set Covering Problem Using GAs [35] Multiple Vehicle Routing with Time and Capacity Constraints Using GAs [28] Genetic Algorithms and Neural Networks Fixed Architecture Genetic Algorithms and Neural Networks Unknown Architecture Parallel Genetic Algorithms [32] k-way Graph Partitioning Algorithm Using GAs [36] Graph Bisectioning Problem Using GAs [36] Triangulation of a Point Set Using GAs [37] The Package Placement Problem Using GAs [33] Three Dimensional Bin Packing Using GAs [29] Encoding: String of integers representing a permutation of the packages Evaluation: Height returned by the Next Fit of First Fit Heuristic Crossover: Order2, Cycle, PMX, and Random Swap Mutation: Adaptive, swap 2 packages and rotate on one axis. RESULTS (in % Fill) Rotated Presorted Without GA Using a GA Using a GA Next Fit Random 31-35% 41-55% 57-66% Next Fit Contrived 48-50% 56-71% 60-71% First Fit Random 36% 41-49% 53-63% First Fit Contrived 41-53% 56-59% 67-77% Tables from ART page 12 and 14 Set Covering Problem Using GAs [35] Page 6 and FIG 1 of D. Ansa's Slides Multiple Vehicle Routing with Time and Capacity Constraints Using GAs [28] Genetic Algorithms and Neural Networks Fixed Architecture Given: A Fixed Connection Topology Goal: Optimize Connection Weights in a Forward-feed Neural Network [22] Example Representation: Each weight ranges -127 to +127 (8-bits) Each Chromosome is the concatenated binary weights of the net. Example Evaluation Function: Run the Network in a feed-forward fashion for each training pattern just as if one were going to use back propagation. Accumulate the sum of the squared error as the fitness value Crossover results in new weight values to try Genetic Algorithms and Neural Networks Unknown Architecture Use GAs to determine a network architecture Each Chromosome Depicts a Possible Connection Topology Evaluate each architecture Parallel Genetic Algorithms Parallel Issues [32] Migration Interval 1. After 5,10,20,50,100 Generations 2. ADAPTIVE Migration Rate 1. 10%, 20%, 50% of the population 2. ADAPTIVE How to pick the migrants 1. uniformly 2. skewed towards the more fit 3. Generate "an over population" during migration generations so nothing is lost from the sending population, only new comers are analyzed as they come in 4. Perform an "exchange" of genetic material 5. ADAPTIVE Topology 1. Ring 2. Hypercube dimensions alternation through the dimensions Crossover and Mutation 1. The same strategy on all processors 2. Different crossover operators and mutation rates on different processors 3. ADAPTIVE Genetic Algorithm Packages (1993) _Generational GA: the offspring are saved in a separate pool until the pool size is reached. Then the children pool replaces the parent pool for the next generation. _Steady-State GA: the offspring and parents occupy the same pool. Each time an offspring is generated it is placed into the pool, and the weakest chromosome is "dropped off" the pool. _GENITOR [23] -- A Steady-state GA Package _GENESIS [16] -- A Generational GA Package _LibGA [30] -- This package was developed at The University of Tulsa and offers the best of GENESIS and GENITOR including the ability to use several additional features including the ability to use either a steady-state or generational, or a combination (generation gap). _HYPERGEN [32] -- This package was developed at The University of Tulsa. This GA package runs on a hypercube topology multiprocessor system. _GATutor [34] -- This package was developed at The University of Tulsa. It is a self study GA Tutorial Package that allows the user to grasp the fundamental concepts of genetic algorithms. PAGE6 <F`r A c f ?  G { (c*X5[##k#lQF0CmK  V !!""##V$$$$z&&&)B),6CJ 6CJCJCJ$CJ CJCJ(CJ4[#;<=wx'(FG]^_`$1$d#;<=wx'(FG]^_`ars(SPxFz   C j * \  ? @ B c d | } x y `a'(012e`ars(SPxFz$1$d   C j * \  ? @ B c d | } $1$dh$1$dh$1$d} x y `a'(012VW$1$dh $1$dhVW()z{`a  CDmn\]89gh7812+!,!""# ###$$$$$$$$&&&&&!)")#)$)%)&)B)C)p)q)**++W,X,,,,,,----.(.^.....7/8//e()z{`a  CDmn\$1$dh $1$dh $1$dh\]89gh7812+!,!""# ###$$$$ $1$d$1$d$1$dh $1$dh$$$$$&&&&&!)")#)$)%)&)B)C)p)q)**++W, $1$d $1$d$1$d $1$d$1$dW,X,,,,,,----.(.^.....7/8///010O0j00 $1$d$1$d $1$d,---2.;...0022444(6c678%88899<====@@DDHHIIJJKKK L!LMMMMMN*NNNNNNPPuQwQQMRkRMSqSVVV=WXXYYLYOYYCJ,5CJ CJ5CJH*OJQJ5CJOJQJ CJOJQJ6CJ CJ CJ$CJ0 CJOJQJ5CJ(CJ(CJ4K//010O0j000000011C2D222222222233343Y3Z3z3{3333333&4a4444444444556575e5f5g55555555%6&6(6)6U6V6c6d6e666666 777H777777777888%8&8'8j8k8888888e00000011C2D222222222233343Y3Z3z3$1$d $1$d $1$d $1$d$1$dz3{3333333&4a4444444444556575e5f5g555$1$d$1$d,$1$d555555%6&6(6)6U6V6c6d6e666666 777H77777$1$d$1$d77777888%8&8'8j8k888888888888)9*9M9O9l9$1$d888888)9*9M9O9l9m999999999:: :[:::::::3;4;A;j;k;;;;;;; <%<&<3<g<<<<<<===N=O==========>x>>>>>?????@E@j@k@l@@@@@@@@@@AAA)AiAAA*BmBBBCC)Cel9m999999999:: :[:::::::3;4;A;j;k;;;;;$1$d;;; <%<&<3<g<<<<<<===N=O==========>x>>$1$d>>>>?????@E@j@k@l@@@@@@@@@@AAA)AiAAA$1$dA*BmBBBCC)CmCCC9D~DDDDDDDDDDDDDDDDCE$1$d)CmCCC9D~DDDDDDDDDDDDDDDDCEEEFFFZFFFG_GGG0HtHHHHHHHHHHH I I/I0I[I\IIIIIJJJJfJgJhJJJJJJJJ K$K%K&KEKFKcKpKqKrKsKtKuKvKwKxKyKzKKKKKKKKKKKKKeCEEEFFFZFFFG_GGG0HtHHHHHHHHHHH I I/I0I$1$d0I[I\IIIIIJJJJfJgJhJJJJJJJJ K$K%K&KEK$1$d$1$dEKFKcKpKqKrKsKtKuKvKwKxKyKzKKKKKKKKKKKKK"L#L$1$d,$1$dK"L#LQLRLLLLLLLMM=M>MlMmMMMMMMMM)N*N+N`NaNNNNNNNNNNN`PaPbPcPdPePfPgPPPPPPPPPP.Q/QiQuQvQwQQQQQQRLRMRlRmRRRRSKSLSMSNSOSpSqSrSSSSTTHTITTTTTTUUUTUUUnUe#LQLRLLLLLLLMM=M>MlMmMMMMMMMM)N*N+N`NaN $1$Pd$1$d$1$d,aNNNNNNNNNNN`PaPbPcPdPePfPgPPPPPPPP$1$d$1$d$1$d $1$PdPPP.Q/QiQuQvQwQQQQQQRLRMRlRmRRRRSKSLSMSNSOS$1$d$1$dOSpSqSrSSSSTTHTITTTTTTUUUTUUUnUUUVVV $1$` d$1$d$1$dnUUUVVVMVNV~VVVVVVVW>W?WtWWWWXXFXzX{XXXXYLYYYYYYYYY Z=Z>Z?ZAZ^Z_Z`ZZZZZ[C[D[p[q[[[[[[[\\B\d\~\\\\\\\\\\]-].]/]R]S]T]U]b]]]]]]"^8^T^u^^^^^^^^eVMVNV~VVVVVVVW>W?WtWWWWXXFXzX{XXXXYLY$1$d$1$d$1$d,LYYYYYYYYY Z=Z>Z?ZAZ^Z_Z`ZZZZZ[C[D[p[q[[[$1$d$1$dY@Z_Z\\^^\^]^___n``cc4hChjkkk lnnnnqqBsss=ttttRvfvvvwwwwwwfyyyo{{}}~~ʀRnuO_@ǿǿǿǿθθ5CJ" CJOJQJCJH*OJQJ CJOJQJCJ( CJOJQJCJ,CJ2 CJOJQJ5CJ 6CJCJCJ"CJ H*CJ$CJ4CJ G[[[[[\\B\d\~\\\\\\\\\\]-].]/]R]S]T]U]$1$d$1$d$1$dU]b]]]]]]"^8^T^u^^^^^^^^^__D_E_^___`__$1$d, $1$pd$1$d^^__D_E_^___`__________l`m`o`p`z`{`````bbFbvbbbbbbcAcfcgcccccccccc(d)d^dddddhhhjjjj%kKkLkMkNkOkPkQkRkSkTkUkkkkkkkkkk l lllll^m_m`mmmmmmmmme_________l`m`o`p`z`{`````bbFbvbbbbbb$1$d$1$d,bcAcfcgcccccccccc(d)d^dddddhhhjjjj$1$dh$1$dj%kKkLkMkNkOkPkQkRkSkTkUkkkkkkkkkk l lllll^m$1$d^m_m`mmmmmmmmmmmhninjnknlnmnnnnnnnnnn$1$d$1$dmmmhninjnknlnmnnnnnnnnnnnnnnnnnnnnnnnnKoLoooppqqqqqqrArBrsrwrrrrrr(s)sBsCsosssssss=t>t?tYtZttttttttttt%u&uYunuuuuuvvvNvOvPvQvSvevfvgvvvvennnnnnnnnnnnnnnKoLoooppqqqqq$1$dh $1$d$1$dqqrArBrsrwrrrrrr(s)sBsCsosssssss=t>t?tYtZtt $1$dhtttttttttt%u&uYunuuuuuvvvNvOvPvQvSvev $1$d$1$d $1$dhevfvgvvvvv;w]wvwwwwww3xxxyxxx6ydyeygyyyzy{yy $1$d $1$dvv;w]wvwwwwww3xxxyxxx6ydyeygyyyzy{yyyyy-zEz^zrzsz|zzzzz2{k{l{m{o{p{{{{{{{{6|7|r|s|||||} }3}4}`}a}}}}}}~~L~M~}~~~~~~~~ D/0jklmnopqrseyyyy-zEz^zrzsz|zzzzz2{k{l{m{o{p{{{{{{{{6|7| $1$d7|r|s|||||} }3}4}`}a}}}}}}~~L~M~}~~~~~~~$1$d $1$d~~ D/0jklmnopqrsʀ$1$d $1$dʀˀ̀&'OPQSz{ $Q6wx҃ӃOPQm܄#34M^2cst}ȆɆ FcstvMN>?jk%&dʀˀ̀&'OPQSz{ $Q $1$d $1$d $1$d$1$d6wx҃ӃOPQm $1$d $1$d $1$d $1$d܄#34M^2cst}ȆɆ Fcstv $1$dvMN>?jk%&$1$$1$d $1$d $1$d@Glq'.CJOJQJmH CJOJQJjCJOJQJUCJ(CJ"5CJ"&00P/ =!"#$% [$@$NormalmH <A@<Default Paragraph Font1                              ! " # $ % & ' ( ) * + , - . / 0 1aA2 a8 &%(,.0'23589<@DFGJLMORU@VXZn\_fijmpRrfunwyq||}R}nuo     #%" ,!"#$$%&'(I)*+,-./0 ,Y@JUl`} \$W,0z357l9;>ACE0IEK#LaNPOSVLY[U]_bj^mnqtevy7|~ʀvKMNOQRSTWXYZ\]^_abcefghjkmnpqrsuvwxz{|~/8)CKnU^mvLPV[`dioty} !#&NQpr?BGSfmR W h p G M   ] e y - 4 F N c n 0;quv~'/68@AGhot!&floz|Q[@HQ[ejn{?CHRJS$.;EMXZ^cgnu%<J",CQ %%&&)!)++++\-b-..//<2>28E=EQGTG$K0KMMMMMMMMMMMMMMNN N NNNNNNNNN6N7N>N?NBNCNNNNNNNNNNNNNNNNNNNNNNNOOOOOOOO1O2O=O>OEOFOPPPPPPPPPPPPPPPPPPQQQQ Q QQQQRRRlRoRYYZZ[Z]Z [ [[[\\__ddYk\kkkllemlmqm}mooPpWp&q.qYqfqqqqqqqrrgrorrrrs;sEs]sesvss}t~ttt{uuuuuu-v7vEvMv^vlvwwwwww-x0xxyyy*y-yWyZyyyyy||||F}I}R^lqS_'.(.GSxBbdu} y ( 8  GUoJXN\Dmw|flCJLOdvswCHs#)w "57B] yKWR]!#!q!}!""##`$q$$$w%%&&&'''^(j()&)|))*&*j*q*****>+P+,,,---L.[./"///*0;000112222M3P333a6i6::F:J:::::;;;;<<I<K<<<= =2><>u>>>>>>u?{????@A@J@@@BB$C.CgCkCCCCC8D@D|DDDDEEEEEE_FeF GGFGGGGGGH&H0HUH]HHHHHHHIIAILIpIxIIIIIIJ0J1JfJhJJJ1K7K_KhKKKL"LLLLLmMoMMMMMMM#N+NyNNNNNNO!OOOOOPPPPPPQQaRbRRRRR2S=S?SFStS{SSSSSTTFTLT{TTTTTUUBULUvUUUUUUUUUVVVVW+WWWWWWWWWWXJXOXlXqXXX9YAYiYjYYYYYYYYYZZ)Z.Z?Z@Z[Z]Z|Z}ZZZ#[)[W[][|[~[[[[[\\]]]]&^.^S^[^^^^^^^__&_'_K_L_``aaCbPbccccd%dodxdddweef!f|ffgg%g-g hhhhh ij jjk|kkkkllemmmmn!nEnHnUnXnfninnnnnooppbpfpq"q&q8q`qlqnqqqqqqqqqr!r/rSrbrgrzrrrrrrrrs;sNs]susssstBtVtyt~ttttu6uCuguvu{uuuuuuuuu v-v@vEv]vvvvvwwAwTwwwsxxxxa{l{{{{{{|:|I|'}*}~~~ZkT]ekˁNW V_dnRoger L. WainwrightC:\RLW\GATUT93\GA1TUTF93.docRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. Wainwright2C:\windows\TEMP\AutoRecovery save of GA1TUTF93.asdRoger L. Wainwright#C:\RLW\CS7863-EC-2001\GA1TUTF93.docRoger L. WainwrightD:\GA-Tutorial-93.doc@EPSON Stylus COLOR 640LPT1:EPIJNL20EPSON Stylus COLOR 640EPSON Stylus COLOR 640& ohh DLLName16=EPIGUE3O.DLLDLLName32=EPIDA230.DLLEPSON Stylus COLOR 640hh  dhh x*** x***2RLEPSON Stylus COLOR 640& ohh DLLName16=EPIGUE3O.DLLDLLName32=EPIDA230.DLLEPSON Stylus COLOR 640hh  dhh x*** x***2RLll(le@@GTimes New Roman5Symbol3& Arial71Courier"AhB#&5U p191\0"Introduction to Genetic AlgorithmsRoger L. WainwrightRoger L. Wainwright Oh+'0 0< X d p|#Introduction to Genetic AlgorithmssntrRoger L. WainwrightogeogeNormal.Roger L. Wainwright9geMicrosoft Word 8.0@ԭ@\HQ@o.41p ՜.+,D՜.+,p, px  University of Tulsa@9 #Introduction to Genetic Algorithms Title 6> _PID_GUIDAN{7C471380-4C5D-11D5-8FE0-E81F2B329F3F}  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry F >@Q41Table*WordDocument(SummaryInformation(DocumentSummaryInformation8CompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q