Generic package: GeneticAlgs_GB

Dependencies

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;
supplies Evaluate() and type DistanceMatrixPtr as well as (through subroutines) TheDistanceMatrixP variable;

Description

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

generic

    -- evaluates The_Object for selective fitness;
  with package ENP is new EvalNodes
    ( GenItem    => CoefBooleans_Container.CoefObj,
      GenItemPtr => CoefBooleans_Container.CoefObjPtr );
  with package GBHP is new GenBinaryHeaps
    ( ENP        => ENP );
  with package GLNP is new GenListNodes
    ( GenItem    => ENP.EvalNode,
      GenItemPtr => ENP.EvalNodePtr );
  with package GLLP is new GenLinkedLists ( GLNP => GLNP );
  with package MCOP is new MasterCrossOvers_GB
    ( ENP         => ENP,
      GLNP        => GLNP,
      GLLP        => GLLP );

package GeneticAlgs_GB is
 

Type Summary

GeneticAlg
Primitive Operations:  BestEval, FillChildrenList, GenCrossOverChildren, GenMutatedChildren, GetChanceOrgMut, GetChildPerWin, GetChildren, GetCur_Gen, GetInitialOrg, GetMax_Gen, GetMyCrossOverP, GetMyMutateP, GetNumWin, GetPriorityQ, GetTempList, GetThreshEval, GetWinners, InitializeWinnersList, MoveChildrenToPriorityQ, MoveWinnersToTempList, RunAlgManyG, RunAlgOneG, RunAlgToCriterion, SelectTopChildren, SetChanceOrgMut, SetChildPerWin, SetChildren, SetCur_Gen, SetInitialOrg, SetMax_Gen, SetMyCrossOverP, SetMyMutateP, SetNumWin, SetPriorityQ, SetTempList, SetThreshEval, SetWinners, UpdateChildrenEvals
GeneticAlgPtr

Other Items:

package COP  renames  CoefBooleans_Container;

package MP   renames  Mutates_GB;

package CCOP renames  CrossOvers_GB;

package Evals renames Evaluations_GB;

subtype ListPtrType is GLLP.GenListPtr;
renaming fundamental types:

subtype HeapPtrType is GBHP.GenHeapPtr;

subtype EvalNodePtrType is ENP.EvalNodeClassPtr;

type GeneticAlg is private;
the principal types of the package:

type GeneticAlgPtr is access all GeneticAlg;

procedure RunAlgOneG
  ( The_GeneticAlg  : in out GeneticAlg );
runs the algorithm for one generation;

procedure RunAlgManyG
  ( The_GeneticAlg  : in out GeneticAlg;
    Delta_Gen       : in     Natural );
runs the algorithm for Delta_Gen generations;

procedure RunAlgToCriterion
  ( The_GeneticAlg  : in out GeneticAlg;
    LimitGen        : in     Natural );
runs the algorithm until the criterion of Evaluate() <= ThreshEval is reached or until an amassed total of LimGen cycles have been reached, whichever comes first;

function MakeGeneticAlg
  ( ChildrenPerWinner  : in Positive;
      -- for ChildPerWin
    WinnersPerGen      : in Positive;
      -- for NumWin
    ProbOrgMut         : in Float;
      -- probability of an organism mutating
    ProbOrgCrossOver   : in Float;
      -- probability of an organism undergoing crossover
    HighCoef           : in Natural;
      -- highest coefficient index in range 0 .. HighCoef for
      --   an organism (used in crossover);
    MaxGenerations     : in Natural;
      -- maximum number of generations to run
    InitOrg            : in COP.CoefObjPtr;
      -- the organism used to initialize the
      --   Winners list at the startup
    ThresholdEvaluate  : in Float;
      -- the threshold value used to terminate
      --   execution of the algorithm;
    FileName           : in String
      -- in the specific case of TS, this is the name of the
      --   coordinates file from which internode distances
      --   are generated;
      -- in the specific case of GB, this parameter will be
      --   filled by the null string ("") as no extra file
      --   is necessary;
      -- in the specific case of SS, this is the name of the
      --   delta-file from which the size changes during mutations
      --   are calculated;
                        ) return GeneticAlgPtr;
called with the parameters necessary to set up a GeneticAlg, returns with a pointer to the newly created GeneticAlg;

procedure SetChildPerWin ( The_GeneticAlg : in out GeneticAlg;
                           NewChildPerWin : in  Positive );
pragma Inline( SetChildPerWin );
sets ChildPerWin of The_GeneticAlg to NewChildPerwin; = children per Winner, a defacto constant during normal runs;

function GetChildPerWin ( The_GeneticAlg : in GeneticAlg )
  return Positive;
pragma Inline( GetChildPerWin );
returns ChildPerWin of The_GeneticAlg; = children per Winner, a defacto constant during normal runs;

procedure SetNumWin ( The_GeneticAlg : in out GeneticAlg;
                      NewNumWin      : in     Positive );
pragma Inline( SetNumWin );
sets NumWin of The_Geneticalg to NewNumWin; = number of Winners in a given generation, a defacto constant during normal runs;

function GetNumWin ( The_GeneticAlg : in GeneticAlg )
  return Positive;
pragma Inline( GetNumWin );
returns NumWin of The_Geneticalg; = number of Winners in a given generation, a defacto constant during normal runs;

procedure SetChanceOrgMut ( The_GeneticAlg  : in out GeneticAlg;
                            NewChanceOrgMut : in     Float );
pragma Inline( SetChanceOrgMut );
sets ChanceOrgMut of The_GeneticAlg to NewChanceOrgMut; = chance that an entity will mutate in a particular generational cycle;

function GetChanceOrgMut ( The_GeneticAlg  : in GeneticAlg )
  return Float;
pragma Inline( GetChanceOrgMut );
returns ChanceOrgMut of The_GeneticAlg; = chance that an entity will mutate in a particular generational cycle;

procedure SetInitialOrg
  ( The_GeneticAlg : in out GeneticAlg;
    NewInitialOrg  : in     COP.CoefObjPtr );
pragma Inline( SetInitialOrg );
sets InitialOrg of The_GeneticAlg to NewInitialOrg; = points to the organism that is the initial set of values;

function GetInitialOrg ( The_GeneticAlg : in GeneticAlg )
  return COP.CoefObjPtr;
pragma Inline( GetInitialOrg );
returns InitialOrg of The_GeneticAlg; = points to the organism that is the initial set of values;

procedure SetThreshEval ( The_GeneticAlg : in out GeneticAlg;
                          NewThreshEval  : in     Float );
pragma Inline( SetThreshEval );
sets ThreshEval of The_GeneticAlg to NewThreshEval; = the threshold value which, when Evaluate() reaches (from above) marks when the algorithm should terminate;

function GetThreshEval ( The_GeneticAlg : in GeneticAlg )
  return Float;
pragma Inline( GetThreshEval );
returns ThreshEval of The_GeneticAlg; = the threshold value which, when Evaluate() reaches (from above) marks when the algorithm should terminate;

procedure SetWinners ( The_GeneticAlg : in out GeneticAlg;
                       NewWinners     : in     ListPtrType );
pragma Inline ( SetWinners );
sets Winners of The_GeneticAlg to NewWinners; = points to the linked list of current surviving entities

function GetWinners ( The_GeneticAlg : in GeneticAlg )
  return ListPtrType;
pragma Inline ( GetWinners );
returns Winners of The_GeneticAlg; = points to the linked list of current surviving entities

procedure SetTempList ( The_GeneticAlg : in out GeneticAlg;
                        NewTempList    : in     ListPtrType );
pragma Inline ( SetTempList );
sets TempList of The_GeneticAlg to NewTempList; = points to the linked list used to temporarily store Winners nodes until they can be used for new children;

function GetTempList ( The_GeneticAlg : in GeneticAlg )
  return ListPtrType;
pragma Inline ( GetTempList );
returns TempList of The_GeneticAlg; = points to the linked list used to temporarily store Winners nodes until they can be used for new children;

procedure SetCur_Gen ( The_GeneticAlg : in out GeneticAlg;
                       NewCur_Gen     : in     Natural );
pragma Inline ( SetCur_Gen );
sets Cur_Gen of The_GeneticAlg to NewCur_Gen; = current generation;

function GetCur_Gen ( The_GeneticAlg : in GeneticAlg )
  return Natural;
pragma Inline ( GetCur_Gen );
returns Cur_Gen of The_GeneticAlg; = current generation;

procedure SetMax_Gen ( The_GeneticAlg : in out GeneticAlg;
                       NewMax_Gen     : in     Natural );
pragma Inline ( SetMax_Gen );
sets Max_Gen of The_GeneticAlg to NewMax_Gen; = maximum generation: limit to which the algorithm can go

function GetMax_Gen ( The_GeneticAlg : in GeneticAlg )
  return Natural;
pragma Inline ( GetMax_Gen );
returns Max_Gen of The_GeneticAlg; = maximum generation: limit to which the algorithm can go

procedure SetChildren ( The_GeneticAlg : in out GeneticAlg;
                        NewChildren    : in     ListPtrType );
pragma Inline ( SetChildren );
sets Children of The_GeneticAlg to NewChildren; = points to the linked list which will be used to hold the possibly-mutated offspring of the Winners;

function GetChildren ( The_GeneticAlg : in GeneticAlg )
  return ListPtrType;
pragma Inline ( GetChildren );
returns Children of The_GeneticAlg; = points to the linked list which will be used to hold the possibly-mutated offspring of the Winners;

procedure SetPriorityQ ( The_GeneticAlg : in out GeneticAlg;
                         NewPriorityQ   : in     HeapPtrType );
pragma Inline ( SetPriorityQ );
sets PriorityQ of The_GeneticAlg to NewPriorityQ; = used to prioritize the children by their EvalNode.Key values;

function GetPriorityQ ( The_GeneticAlg : in GeneticAlg )
  return HeapPtrType;
pragma Inline ( GetPriorityQ );
returns PriorityQ of The_GeneticAlg; = used to prioritize the children by their EvalNode.Key values;

procedure SetMyMutateP
  ( The_GeneticAlg : in out GeneticAlg;
    NewMyMutateP   : in     MP.MutatePtr );
pragma Inline ( SetMyMutateP );
pragma Inline ( SetMyMutateP );
sets MyMutateP of The_GeneticAlg to NewMyMutateP;

function GetMyMutateP ( The_GeneticAlg : in GeneticAlg )
  return MP.MutatePtr;
pragma Inline ( GetMyMutateP );
returns MyMutateP of The_GeneticAlg;

procedure SetMyCrossOverP
  ( The_GeneticAlg  : in out GeneticAlg;
    NewMyCrossOverP : in     MCOP.MasterCrossOverPtr );
sets MyCrossOverP of The_GeneticAlg to NewMyCrossOverP;

function GetMyCrossOverP ( The_GeneticAlg : in GeneticAlg )
  return MCOP.MasterCrossOverPtr;
pragma Inline ( GetMyCrossOverP );
returns MyCrossOverP of The_GeneticAlg;

procedure InitializeWinnersList
  ( The_GeneticAlg  : in out GeneticAlg );
Takes the already-created node-list of the Winners list and initializes each node to the The_GeneticAlg.InitialOrg values;

procedure GenMutatedChildren ( The_GeneticAlg : in out GeneticAlg );
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; each child on the Children list is given the possibility of undergoing a mutation, where its chances are ChanceOrgMut in that generational cycle; modification of 1/16/02: the first child from each Winners entity is protected from mutation;

procedure GenCrossOverChildren ( The_GeneticAlg : in out GeneticAlg );
carries out crossover among the items on the Children list (exception: first child of each winner);

procedure UpdateChildrenEvals
  ( The_GeneticAlg  : in out GeneticAlg );
runs through the Children list, updating all the evaluations and storing these in the EvalNodes; added at 2/24/03; DistanceMatrixP added 6/17/02 for the new Evaluate(); DistanceMatrixP removed 7/30/04 for FLEXIBLE_GA version;

procedure MoveChildrenToPriorityQ ( The_GeneticAlg : in out GeneticAlg );
all the Children entities are moved into the PriorityQ which is then sorted;

procedure MoveWinnersToTempList ( The_GeneticAlg : in out GeneticAlg );
frees the Winners list for the top NumWin entities from the PriorityQ by moving the Winners entities to the TempList;

procedure SelectTopChildren ( The_GeneticAlg : in out GeneticAlg );
the top NumWin entities are taken from the PriorityQ and placed on the Winners list;

procedure FillChildrenList ( The_GeneticAlg : in out GeneticAlg );
the other entities from the PriorityQ plus the TempList entities are placed into the Children list: their values have no significance, but they are ready to be overridden by new values during the GenMutatedChildren() operation;

function BestEval ( The_GeneticAlg : in GeneticAlg ) return Float;
returns the evaluation value of the first entity on the Winners list (= at least the best current score);

private

   --  Implementation-defined ...
end GeneticAlgs_GB;