Generic package: GeneticAlgs_GB |
with GenListNodes;
-- GenListNode and GenListNodeClassPtr types;
-- generic: instantiate with type GenItem and GenItemPtr;
with GenLinkedLists;
-- GenList and GenListPtr types;
-- generic: instantiate with GLNP is new GenListNodes;
with CoefBooleans_Container;
-- CoefObj, CoefObjPtr, and CoefObjClassPtr types;
with EvalNodes;
-- EvalNode, EvalNodePtr, and EvalNodeClassPtr types;
-- generic: instantiate with types GenItem and genItemPtr;
with GenBinaryHeaps;
-- GenHeap, GenHeapPtr, HeapArray, HeapArrayPtr types;
-- generic: instantiate with package ENP is new EvalNodes;
with Mutates_GB;
-- MakeMutate() and DoMutate();
-- Mutate and MutatePtr types;
-- see 7/28/03 changes note re significance of the change;
with CrossOvers_GB;
-- CrossOver and CrossOverPtr types;
with MasterCrossOvers_GB;
-- MakeMasterCrossOver() and PerformMasterCrossOver();
-- types MasterCrossOver and MasterCrossOverPtr;
with Evaluations_GB;
file RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/FLEXIBLE_GA /geneticalgs_gb.ads (modified slightly from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/FLEXIBLE_GA /geneticalgs_ts.ads) (modified from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/TRAV_SALES /geneticalgsm2.ads) (adapted from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/TRAV_SALES) /geneticalgs.ads (copied from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/SINSERIES3/ geneticalgs.ads) (package renamed from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/SINSERIES3/ geneticalg_p.ads) (modified from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/SINSERIES2/ geneticalg_pack.ads) (adapted from: RESEARCH/AL/APLYSIA3/GENETIC_PROGRAMMING/SINSERIES/ geneticalg_pack.ads)
author Melvin Neville date August 5, 2004 (.../FLEXIBLE_GA/geneticalgs_gb.ads) July 30, 2004 (.../FLEXIBLE_GA/geneticalgs_ts.ads) July 28, 2003 (.../TRAV_SALES/geneticalgsm2.ads) June 3, 17, 2003 (.../TRAV_SALES/geneticalgs.ads) February 24, 2003 (.../SINSERIES3/geneticalgs.ads) February 17, 2003 (.../SINSERIES3/geneticalgs.ads) December 16, 31, 2002 (.../SINSERIES3/geneticalgs.ads) November 7, 12-14, 2002 (.../SINSERIES3/geneticalg_p.ads) May 14-15, August 30, 2002 (.../SINSERIES2/geneticalg_pack.ads) December 27-29, 2001; January 10, 14-16, 2002; Feb. 21, 2002 (.../SINSERIES/geneticalg_pack.ads)
purpose Specification for generic package GeneticAlgs_GB, manages the running of the genetic algorithm
The SINSERIES2 package differs from the SINSERIES package through the introduction of crossover.
The SINSERIES3 package differs from the SINSERIES2 package through:
the radical reduction of generic parameters to: the Evaluate() function (this is special for any particular object being evolved and hence evaluated). Remaining generic aspects are instantiated inside the package: EvalNode_Pack is instantiated so that EvalNodes point to CoefObj_P.CoefObjs; GenListNode_Pack is instantiated so that GenListNodes point to EvalNode_Pack.EvalNodes; GenList_Pack is instantiated so that GenList contains a list of GenListNode_Pack.GenListNodes; GenBinHeap_Pack is instantiated so that a GenBinHeap contains an array of pointers to EvalNode_Pack.EvalNodes;
The TRAV_SALES package relates to the solution of the Travelling Salesman problem, a very different problem than the SINSERIES problem. However, the genetic algorithm used is the same.
SINSERIES2:
The package is made very generic so that different objects can be subjected to the genetic algorithm processing: one must supply:
a generic package which serves to bundle types together (this is provided by the MasterCrossOver_Pack2); a procedure to Evaluate the goodness of The_Object; a function to create and return a Mutator objct; a procedure to DoMutate The_Object; generic packages to handle the crossover of individual objects and of a list of such objects;
instantiations of packages (SINSERIES3 package names in parentheses): GenListNode_Pack, (GenListNodes) GenLinkedList_Pack, (GenLinkedLists) GenHeapNode_Pack (EvalNodes) GenBinaryHeap_Pack, (GenBinaryHeaps) GenericCrossOver_Pack2, (not present) MasterCrossOver_Pack2 (MasterCrossOvers2) using the generic bundling package so that all types are congruent. (not used)
SINSERIES3:
Stages of the algorithm:
One cycle involves (high-level description): (1) The cycle commences with the NumWin surviving organisms having just been placed on the Winners list; (2) The Children list is then filled from the TempList (= same number as in Winners list) and the remaining entities in the PrioityQueue (= full_size - number of entities that have moved onto the Winners list); none of the values are currently significant; (2) Each of these organisms on the Winners list generates ChildPerWin children, which are also exposed to the possibility of mutation through the mutation object; This generation is accomplished by CoefObjs.CopyOver() being applied to ChildPerWin nodes on the Children list for each Winner node in the Winners list; mutation and then Crossover as possibilities are invoked for all but the first node in each sequence of ChildPerWin nodes, as the first node is kept inviolate as a copy; (3) All the children are then evaluated (new as of 2/24/03); (4) All children are placed in the PriorityQ, sorted according to the evaluation function; and the NumWin best are allowed to survive and reproduce; (5) NumWin best are deleted from the PriorityQueue and placed on the Winners list.
Initial set-up involves: (1) Setting up the Winners list with NumWin nodes, each with EvalNode-CoefObj pairs whose CoefObjs are copies of the InitialOrg entity; (2) The Children list is initially empty; it will have (NumWin*ChildPerWin) links; (3) The TempList is set up with NumWin links, each with a EvalNode-CoefObj node pair of unimportant value; (4) The PriorityQueue is set up with NumWin * ChildPerWin nodes; of these the first (lowest) NumWin*ChildPerWin - NumWin nodes have EvalNode-CoefObj node pairs of unimportant value; (5) The MasterCrossOver object is established, with its CrossOverListP being the Children list.
The data structures represented by the fields of a GeneticAlg record: (1) Winners: a linked-list whose nodes are the surviving and reproducing children; this list is precisely NumWin nodes long; (2) TempList: a linked-list used to hold the Winners list entities after they have been processed (so that the nodes do not have to be dynamically destroyed and then allocated anew); this list is precisely NumWin nodes long; (2) Children: a linked-list whose nodes are the children generated from the Winners: the list is precisely (NumWin * ChildPerWin) nodes long, and each section of ChildPerWin nodes represents the progeny from a Winners child in turn; (3) PriorityQ: a binary heap whose nodes are the children which are to be sorted so that NumWin children with "best" (lowest) key values can be placed into the Winners list; the maximum size of the PriorityQ is (NumWin * ChildPerWin).
Movement of organisms during the algorithm: (1) Nature of an organism: Each organism is represented as an EvalNodes (instantiated below to GHNP) EvalNode where the organism's current goodness rating is its Key value and its other values are in the node pointed to by the GenNode_Pack (instantiated below to GN_Pack GenObjectPtr which is the GHNP.EvalNode ItemPtr; example: in the case of the SINSERIES algorithm the node poined to by the EvalNode is a SinSeries object. (2) Once the initial node allocations have been made, the linked-lists do not alter their lengths; however, the GenListNodes.GenListNode.ItemPtr can be null or can point to a different entity (an EvalNode). It is the alteration of what these pointers point to that alters what is stored in the lists and the de-facto movement of organisms among the data structures.
More detailed description of the algorithmic steps in a cycle (breaking up the high-level one cycle description above): (1) The cycle commences with the NumWin surviving organisms already placed on the Winners list: (this is either because of initialization of the GeneticAlg object before the first cycle commences or because of step 4 below); (2) FillChildrenList() moves the EvalNode-CoefObj node pairs over from the TempList and the undeleted portion of the PriorityQueue to hang off the Children list's ListNodes; (3) Each of the Winner organisms generates ChildPerWin children, which are also exposed to the possibility of mutation through the mutation object: GenMutatedChildren(): places ChildPerWin copies of each Winners entity in turn on the Children list, with the first Winners entity's offsrping occupying the first ChildPerWin nodes on the Children list, the second's offspring occupying the next ChildPerWin nodes on the Children list, and so on; a) Each child on the Children list is given the possibility of undergoing a mutation, where its chances are ChanceOrgMut in that generational cycle (the first child of each winner is left untouched so that the solution rachets towards becoming better); b) The Children list is subject to crossover through PerformMasterCrossOver(), with the first child of each winner being excluded from the operation so that the solution rachets towards becoming better); c) Each child on the Children list is Evaluated by Evaluate() (this was stated here but only added 2/24/03!); (4) All children are placed in the PriorityQ (the NumWin best are to be allowed in the next stage to survive and reproduce: MoveChildrenToPriorityQ(): all the Children entities are moved into the PriorityQ which is then sorted; (5) These NumWin best are placed on the Winners list: MoveWinnersToTempList(): frees the Winners list for the top NumWin entities from the PriorityQ by moving the former Winners entities to the TempList; SelectTopChildren(): the top NumWin entitties are deleted from the PriorityQ and placed on the Winners list;
Additions: Feb. 24, 2003: UpdateChildrenEvals() added as a call from RunAlgOneG() -- see commentary in documentation of geneticalgs.adb; Feb. 21, 2002: InitializeWinnersList(), inspired by the creation of the averimproverate.adb driver; Aug. 30, 2002: The generic parameter function Evaluate() is altered to have a second parameter, Angle_Step. Nov. 7, 2002: SINSERIES3: removal of most of the generics. Nov. 13, 2002: I had to modify MasterCrossOver_P to put in generics so that the linked-list of the MasterCrossOver_P would be compatible with the linked-lists of GenericAlg_P. Dec. 16, 2002: Package renamed to Geneticalgs to follow the plural-in-naming convention. 2/17/03: The documentation above has been altered to that (fundamentally) the algorithm RunAlgOneG commences with FillChildrenList(); this calls for altering the implementations but not specifications of RunAlgOneG() and MakeGeneticAlg(). 6/17/03: This version is in the Travelling Salesman problem. DeltaSourceFile has been removed as a parameter to MakeGeneticAlg() but a DistanceMatrixPtr has been added, and, in a related matter, the second parameter of the generic parameter function Evaluate() has been changed from type Float to type TravSalesFuncEvals.DistanceMatrixPtr; the second parameters of UpdateChildrenEvals(), InitializeWinnersList(), and RunAlg...() procedrues have been changed to a DistanceMatrixPtr. 7/22/03: GeneticAlgsM2 version: the change is to with Mutates2 instead of Mutates: i.e., mutation involves a 50-50 chance that two nodes will be swapped (the values of two coefficients in the CoefObj being mutated will be exchanged) or that they and the node string inbetween (with wrap-around) will be inverted (so: inversion of that segment of the circular chromosome). 7/30/04: GeneticAlgs_TS version: (1) Evaluations is now a singleton package that contains DistanceMatrixP as well as the function Evaluate(): this allows a simplification many of the subroutines' signatures. 8/5/04: GeneticAlgs_GB version: (1) Package name changes to match the system necessary for this problem (GENBITEVOLVE) as opposed to the TRAV_SALES problem: so suffixes of "_TS" are changed to "_GB"; additionally, the fundamental package of CoefInts_Container is altered to CoefBooleans_Container as this problem deals with the gene being represented by a bit instead of by an Integer.
renamings of fundamental packages:
Header | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generated on 2004-08-19 at 12:12:58 by AdaBrowse 4.0.2. |