Transcript ppt - SIUE
(Genetic Algorithm Interface Architecture) Final Presentation CS 425 Created By: Chuck Hall Simone Connors Héctor Aybar Mike Grim WHAT IS A GENETIC ALGORITHM? Search algorithm that mimics natural genetics Searches for optimal solutions to complex functions Shared fundamental units of natural genetics Chromosomes Genes WHAT IS A GENETIC ALGORITHM? Chromosomes are usually represented as arrays Chromosome 7 Genes 1 0 25 0 0 100 1 0 320 1 1 90 0 0 37 1 1 222 0 1 10 WHAT IS A GENETIC ALGORITHM? GA Hierarchy Populations are comprised of chromosomes A single chromosome is a member of the population Chromosomes are comprised of genes Genes contain values If the GA is solving f(x), then one chromosome is an ‘x’ WHAT IS A GENETIC ALGORITHM? Shared fundamental principles of natural genetics Crossover (parent chromosomes swap some genes) Mutation (specific genes are given new values) Parents/Offspring Populations/Generations Higher quality offspring have a better chance of reproducing and surviving (chromosomes are assigned a ‘fitness value’) WHAT IS A GENETIC ALGORITHM? Choose parent chromosomes Perform Crossover Basic flow of the algorithm Perform Mutation Can be specialized Elitism Convergence criteria Place children in the next generation Number of generations Is the generation full? Best fitness value Average fitness value Yes Pool Terminate the algorithm No Yes Have the convergence criteria been met? No Create another generation SCENARIO – minimize f(x) = x2 Joe makes some decisions Minimize between 0 and 15 Represent x with a 4 gene chromosome Represent each gene with a single bit He writes a fitness function He randomly creates the first generation SCENARIO – minimize f(x) = x2 SCENARIO – minimize f(x) = x2 Choose parent chromosomes Duplicate them Perform crossover Perform mutation Determine fitness value Store new chromosomes mutation 0 1 0 0 0 0 0 1 1 crossover point SCENARIO – minimize f(x) = x2 GAIA terminates after the 500th generation Best chromosome in the final generation: bit-string of all zeroes fitness value of 0 WHY USE A GENETIC ALGORITHM? Calculus doesn’t always work It’s not feasible to try every possibility. 3 Vital fundamentals of genetics Crossover (refine within a region) Mutation (explore a new region) Survival of the fittest WHY USE A GENETIC ALGORITHM? STAGED DELIVERY LIFECYCLE Software Concept Requirements Analysis Architectural Design Stage 1: default bit-string and function pointer prototype Delivery Date: October 11, 2004 Stage 2: default integer and double-string prototype Delivery Date: November 8, 2004 Stage 3: module efficiency prototype Delivery Date: December 6, 2004 Detailed Design Coding Testing Delivery STAGE 1 Function pointers and default bit string prototype User can specify a user-defined gene type Function pointers allow GAIA to use user supplied functions Bit string is the default gene type that will be provided Functions that perform operations on bit string gene types will be provided STAGE 2 Default integer and double string prototype Integer gene type is a default gene type that will be provided Default functions to perform operations on integer gene types Double string gene type is a default gene type that will be provided Default functions to perform operations on double string gene types STAGE 3 Module efficiency prototype Includes improvements to algorithms used in the GAIA library Copy memory to and from internal data structures Slows Gaia down Make improvements to internal data structures Improves efficiency of GAIA library TIMELINE FOR FALL 2004 WHY STAGED DELIVERY? Deliver a functioning part of GAIA library early in development Shows signs of progress to client Allows for the discovery of problems early in development Client knew exactly what wanted TIMELINE FOR SPRING 2004 TEAM ORGANIZATION Edmond Abrahamian Dr. Yu Upper Management Client Chuck Hall Project Manager Simone Connors Hector Aybar Mike Grim Project Member Project Member Project Member HARDWARE/SOFTWARE MAPPING SYSTEM ARCHITECTURE Interface 3-Tier – Interface – Application Logic – Storage API Application Logic Genetic Algorithm Management Storage Librarian Instance Storage Create two pointers: Instance of GAIA GA Parameters structure Initialize Memory: Instance of GAIA Instance of GA Parameters structure FLOW OF EVENTS (API) GA Parameters and Function Pointers are setup: parameters delete_chromosome copy_chromosome crossover mutation selection fitness Is there an error? No Yes Primary application fills the initial population. Optimize problem using the genetic algorithm. (Details in another figure.) Primary application asks for the solution to be returned to it. Free all the memory associated with an instance of GAIA. Primary application requests a human-readable error to be returned. If no error, just return. Precondition: Initial population has been filled and all Fitness values have been calculated. FLOW OF EVENTS: GENETIC ALGORITHM Select 2 parent chromosomes. Make 2 copies of each. Start creating the next generation. No Perform crossover and mutation on one set. Have any of the convergence criteria been met? Calculate fitness values for the 2 children. No Check each parent and child chromosome. Is it already in the pool? Insert into the pool sorted by fitness value. Copy the best chromosomes from the pool into the next generation. Yes Delete the copy. No Is the pool filled? Yes Yes Halt the algorithm. WHERE DO WE GO NOW? What affected our design Languages and Development Tools Plans for Implementation, Testing, and Development WHAT AFFECTED OUR DESIGN? Unix/Linux Symmetric Multi-Processing Programming Languages: C XML Ensuring functions are reentrant Abstraction Dynamic Design LANGUAGES AND DEVELOPMENT TOOLS Languages: C XML Development Tools: expat GCC/GDB CVS OpenOffice PLANS FOR IMPLEMENTATION Two primary development leads: Chuck Mike Chuck will lead the implementation of the GA. Mike will lead the implementation of the API and support libraries. Mike Grim Chuck Hall Lead Developer Lead Developer Simone Connors Héctor Aybar Backup Developer Backup Developer PLANS FOR TESTING Two primary testing leads: Hector Simone Hector will lead the testing of the GA. Simone will lead the testing of the API and support libraries. Héctor Aybar Simone Connors Lead Tester Lead Tester Chuck Hall Mike Grim Backup Tester Backup Tester PLANS FOR TESTING Hierarchical Testing Plan Unit Testing (During Implementation) Integration Testing System Testing (F6 Function) Acceptance Testing PLANS FOR DEPLOYMENT Client will take source and Makefiles. Client will build GAIA and link with his code. Code will be available to client in multiple forms: CVS of most recent code Tarball (archive) of latest stable build Code and project site will be transferred to SourceForge. WHAT IS IT THOU SEEKS?