|
|
| (131 intermediate revisions by one user not shown) |
| Line 1: |
Line 1: |
| − | ==Introduction==
| + | #REDIRECT [[GenA: A Genetic Algorithms Framework]] |
| − | Over the last few months I have become interested in problems associated with modelling non-linear systems. This interest has lead me to look into artificial neural networks, and how they can be trained using genetic algorithms. For those with an interest in this area, development environments like [http://en.wikipedia.org/wiki/MATLAB Matlab] provide an ideal platform for quick implementation and testing. However, at deployment time, a Matlab script is of little use to clients with a limited budget, or to developers targeting some embedded platforms. [What about on non-x86 architectures e.g. the supercomputer situated in the engineering department - that don't run Matlab?].
| + | |
| − | | + | |
| − | ==Genetic Algorithms for Dummies==
| + | |
| − | | + | |
| − | Disclaimer about how much I actually know about genetic algorithms. [Damn it Jim I'm a software engineer, not an AI specialist!]
| + | |
| − | | + | |
| − | ==Requirements==
| + | |
| − | The intention of this project is to provide a framework that is capable of mimicking the behaviour of the Matlab genetic algorithms library. This framework should be extensible; it should allow for:
| + | |
| − | *Client defined types
| + | |
| − | *Client defined selection, reproduction, and mutation strategies
| + | |
| − | *Packaged to provide the easy removal of unused strategies
| + | |
| − | Control of the framework should be the domain of the clients application: the intention is that the client will [[Adapter|adapt]] the framework to suit their needs.
| + | |
| − | | + | |
| − | ==A First Attempt==
| + | |
| − | This is the starting point - something I put together around 6 months ago.
| + | |
| − | | + | |
| − | My first working attempt at a generic genetic-algorithms library is shown in Fig. 1. This section will dissect and critique portions of the initial library design.
| + | |
| − | | + | |
| − | [[image:gaFirstAttempt.jpg|thumb|800px|centre|'''Figure 1: A [[UML 2.1]] [[Class diagram|class diagram]] representing my first working attempt at a generic genetic-algorithms library''']]
| + | |
| − | | + | |
| − | ===Creating New Candidates===
| + | |
| − | A set of candidates are required to initiate the algorithm. The creation of this initial set or generation of candidates is the responsibility of the library user.
| + | |
| − | ====The First Attempt====
| + | |
| − | In the first attempt, a modified [[Factory|Factory pattern]] was used here, this was taken from a [http://msdn.microsoft.com/en-us/library/ms954600.aspx Microsoft Patterns and Practices article by Doug Purdy]. An abstract factory class is provided by the library, the user is expected to provide a concrete candidate factory class.
| + | |
| − | [[image:gaFirstAttemptInitialisationStructure.jpg|thumb|800px|centre|'''Figure 2: A [[UML 2.1]] [[Class diagram|class diagram]] representing my first working attempt at generation initialisation structure''']]
| + | |
| − | [[image:gaFirstAttemptInitialisationCommunications.jpg|thumb|800px|centre|'''Figure 3: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing my first working attempt at generation initialisation communications''']]
| + | |
| − | ====A New Design====
| + | |
| − | To facilitate building candidates, the user should provide the genetic algorithm with a concrete candidate factory.
| + | |
| − | [[image:gaNewDesignInitialisationStructure.jpg|thumb|800px|centre|'''Figure 4: A [[UML 2.1]] [[Class diagram|class diagram]] representing an attempt to redesign the generation initialisation''']]
| + | |
| − | [[image:gaNewDesignInitialisationCommunications.jpg|thumb|800px|centre|'''Figure 5: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing an attempt to redesign the generation initialisation communications''']]
| + | |
| − | ===Selection of the Fittest===
| + | |
| − | Upon creating a generation of candidates, the process of creating a new generation begins. To start, a portion of the candidates are selected from the current generation based on fitness. The fitness of each candidate is calculated, then one of several candidate selection algorithms is applied to the current generation. The selection strategy may vary per iteration. The library user is responsible for choosing and configuring the selection strategy.
| + | |
| − | ====The First Attempt====
| + | |
| − | Fitness calculations are known about by
| + | |
| − | *the GeneticAlgorithms class
| + | |
| − | *the Generation class
| + | |
| − | *the Candidate class
| + | |
| − | [[image:gaFirstAttemptSelectionStructure.jpg|thumb|800px|centre|'''Figure 6: A [[UML 2.1]] [[Class diagram|class diagram]] representing my first working attempt at a selection structure''']]
| + | |
| − | [[image:gaFirstAttemptSelectionCommunications.jpg|thumb|800px|centre|'''Figure 7: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing my first working attempt at selection communications''']]
| + | |
| − | ====A New Design====
| + | |
| − | [[image:gaNewDesignSelectionStructure.jpg|thumb|800px|centre|'''Figure 8: A [[UML 2.1]] [[Class diagram|class diagram]] representing an attempt to redesign the selection structure''']]
| + | |
| − | [[image:gaNewDesignSelectionCommunications.jpg|thumb|800px|centre|'''Figure 9: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing an attempt to redesign the selection communications''']]
| + | |
| − | ===Creating New Candidates via Reproduction===
| + | |
| − | A new generation begins by selecting a set of candidates based on fitness. These candidates become the parents in the new generation; they reproduce to create a new set of genetically similar candidates. Reproduction, also known as crossover, is performed using one of several possible crossover algorithms. The same reproduction strategy is usually applied to the entire generation in any one iteration. It is often kept constant throughout the algorithm life-cycle. The library user is responsible for choosing the crossover strategy.
| + | |
| − | ====The First Attempt====
| + | |
| − | [[image:gaFirstAttemptReproductionStructure.jpg|thumb|800px|centre|'''Figure 10: A [[UML 2.1]] [[Class diagram|class diagram]] representing my first working attempt at a candidate reproduction structure ''']]
| + | |
| − | [[image:gaFirstAttemptReproductionCommunications.jpg|thumb|800px|centre|'''Figure 11: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing my first working attempt at candidate reproduction communications''']]
| + | |
| − | ====A New Design====
| + | |
| − | [[image:gaNewDesignReproductionStructure.jpg|thumb|800px|centre|'''Figure 12: A [[UML 2.1]] [[Class diagram|class diagram]] representing an attempt to redesign the reproduction structure''']]
| + | |
| − | [[image:gaNewDesignReproductionCommunications.jpg|thumb|800px|centre|'''Figure 13: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing an attempt to redesign the the reproduction communications''']]
| + | |
| − | ===Mutating Candidates===
| + | |
| − | Following the reproduction process, a proportion of the children produced may be mutated. In mutation, there are two responsibilities. One is performing the mutation - defining this algorithm is the responsibility of the library user. The other is selecting candidates for mutation - here the library user is responsible for choosing from one of several selection strategies defined within the library.
| + | |
| − | ====A New Design====
| + | |
| − | [[image:gaNewDesignMutationStructure.jpg|thumb|800px|centre|'''Figure 14: A [[UML 2.1]] [[Class diagram|class diagram]] representing an attempt to redesign the mutation structure''']]
| + | |
| − | [[image:gaNewDesignMutationCommunications.jpg|thumb|800px|centre|'''Figure 15: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing an attempt to redesign the mutation communications''']]
| + | |
| − | ==A New Design==
| + | |
| − | | + | |
| − | ===Core Class Structure===
| + | |
| − | | + | |
| − | [[image:gaCoreClassStructure.jpg|thumb|800px|centre|'''Figure 2: A [[UML 2.1]] [[Class diagram|class diagram]] representing an attempt to redesign the generic genetic-algorithms library''']]
| + | |
| − | | + | |
| − | ===Communications===
| + | |
| − | | + | |
| − | [[image:gaCommunications.jpg|thumb|800px|centre|'''Figure 3: A [[UML 2.1]] [[Communication diagram|communication diagram]] representing an attempt to redesign the generic genetic-algorithms library''']]
| + | |
| − | | + | |
| − | ==References==
| + | |
| − | #{{Note|1}} http://www.mathworks.com/access/helpdesk/help/toolbox/gads/
| + | |
| − | | + | |
| − | ==See Also==
| + | |
