ú΋“†Å>      !"#$%&'()*+,-./0123456789:;<= non-portable experimental Jan Snajder <jan.snajder@fer.hr>3This typeclass defines an interface to expressions B that can be genetically programmed. The operations that must be A provided by instances of this class are used for the generation E of random individuals as well as crossover and mutation operations. ! (An instance for members of the Data typeclass is provided in  GenProg.GenExpr.Data.) Minimal complete definition: , , ,  and . 'Exchanges subtrees of two expressions:  exchange e1 n1 e2 n2 replaces the subexpression of e1 rooted in node  n1 with the subexpression of e2 rooted in n2, and vice versa. :Maps a monadic transformation function over the immediate  children of the given node. ?Maps a query function over the immediate children of the given % node and returns a list of results. 8A list of indices of internal (functional) and external $ (terminal) nodes of an expression. ?Adjusts a subexpression rooted at the given node by applying a " monadic transformation function. #Number of nodes an expression has. BThe depth of an expression. Equals 1 for single-node expressions.  non-portable experimental Jan Snajder <jan.snajder@fer.hr> >?@ABCDASame as typeMoveFor, but throws an error if node index is out of  bound. EExchanges two zipper holes. FG non-portable experimental Jan Snajder <jan.snajder@fer.hr>K$Parameters governing the evolution. Default evolution parameters, ) as used in (Koza, 1992), are defined by 9 4 and indicated below. At least the fitness function  should  be overriden. 4Population size (number of individuals). Default is 500. 7Depth of expressions in initial population. Default is 6. ;Maximum depth of expressions created during the evolution.  Default is 17. %Probability of crossover. Default is 0.9. If crossover is not @ chosen, an individual is simply reproduced (copied as-is) into  the next generation. >Probability that an internal (functional) node is chosen as a  crossover point. Default is 0.9. If an internal node is not ( chosen, an external (terminal) node is  chosen. 8Probability that an individual gets mutated. Default is 0  (no mutation). =Probability that an internal (functional) node is chosen for  mutation. Default is 0.1. 0Standardized fitness function. Default value is  undefined  (must be overriden). ;Mutation function. Defines how to change a randomly chosen  node. Default is !defaultMutation defaultEvolParams I (replacement of a chosen node with a randomly generated subexpression). EElitist factor: number of best-fitted individuals that are preserved D from each generation (reproduced as-is into next evolution state).  Default is 0. "Termination predicate. Default is 50# (terminate after 50 generations). Termination predicate. /A function to mutate a chosen expression node. BStandardized fitness. It takes on values from 0 (best fitness) to  +infinity (worst fitness). The state of the evolution. Current population. 'Iteration (current generation number).  Best individual evolved so far. HCA population of individuals. (Basically a wrapper around a list of  individuals.) IUnwraps a population. JFitness distribution. ?A genetically programmed individual, representing a basic unit F of evolution. (Basically a wrapper around a genetically programmable  expression.) K 1Returns the expression wrapped by an individual. !;Adjusted fitness of an individual. Adjusted fitness equals  1/(1+s), where s, is the standardized fitness as computed by  8. To reduce computational costs, this value is computed  only once and then cached. LM"=A typeclass defining a genetic program interface. Datatypes e B that are to be used as genetic programs must be instances of the  / typeclass and must implement this interface. #Generates a random terminal T. $1Generates a random nonterminal (functional) node  F(T,...,T) whose A arguments are again terminals (this condition is not verified). N8Generates a random expression of a given maximum depth. %EGenerates a random expression fully expanded to the specified depth. &EGenerates a random expression of limited depth. The maximum depth of ? the resulting expression may be less than the specified depth . limit, and paths may be of different length. '(Wraps an expression into an individual. OP(5Standardized fitness of an individual as computed by  )/Wraps a list of individuals into a population. *>Generate population of given size and given depth limit using  ramped half-and-half5 method (Koza, 1992): for each depth value from 0 to  the initial depth limit  ), 50% of individuals are generated using  % and 50% are generated using  &/. Afterwards, duplicates are removed, thus the @ size of the resulting population may actually be less than the  specified size. +Replenishes a population up to   by randomly  generating new individuals. ,!Merges two populations by taking   best-fitted individuals ( from the union of the two populations. - Population's best-fitted individual. Q. Population' s average standardized fitness. /0Average depth of expressions in the population. 06Average number of expression nodes in the population. R19Crossover operation of two individuals, resulting in two D offsprings. Crossover is performed by choosing at random two nodes @ in each expressions, and then by exchanging the subexpressions D rooted at these nodes between the two individuals. The probability D that an internal (functional) node is chosen as crossover point is  set by the  parameter in  , whereas the ? probability that an external (terminal) node is chosen equals  1-ciProb6. Among internal and external nodes, nodes are chosen B uniformly at random. If the depth of a created offspring exceeds  the depth limit  # specified by evolution parameters   ., that offspring is discarded and a parent is " reproduced (i.e., copied as-is). 28Mutates an individual by applying the mutation function mutate ? to a randomly selected node. The probability that an internal 8 (functional) node is chosen for muration is set by the   parameter in  +, whereas the probability that an external " (terminal) node is chosen equals 1-miProb. Among internal and D external nodes, nodes are chosen uniformly at random. If the depth 3 of the mutated expression exceeds the depth limit   # specified by evolution parameters  , the individual is  left unaltered. STUVWX3<Applies crossover to two randomly chosen individuals from a E population. The probability of an individual being chosen as parent @ is fitness-proportionate (individuals with better fitness have 1 better chanches of being chosen for crossover). 4AApplies mutation operation to individuals from a population. The : probability of mutating each individual is determined by  parameter  from  EvalParams. YZ"Advances to next evolution state. 5>Default mutation. Replaces a node, irrespective of its value, C with a randomly generated subexpression whose depth is limited to   . 6ATermination predicate: terminate if any individual satisfies the  specified predicate. 73Termination predicate: terminate if best individual's G standardized fitness is greater than or equal to the specified value. 8ATermination predicate: terminate after running for the specified  number of iterations. [\]?Evolves one population from another one by performing a single  evolution step. :?Creates an initial population and evolves it until termination = predicate is satisfied, returning the last evolution state. ;5Evolves a given initial population until termination = predicate is satisfied, returning the last evolution state. 4 If the size of the initial population is less than   *, the population will be replenished (see +). <?Runs evolution on a given initial population until termination C predicate is satisfied and returns a list of successive evolution < states. If the size of the initial population is less than   *, the population will be replenished (see +). =7Creates an initial population and runs evolution until B termination predicate is satisfied. Returns a list of successive  evolution states. 8  !"#$%&'()*+,-./0123456789:;<=;"#$%& ! '!()*+,-./012345678 9:;=<5   ! !"#$#$%&'()*+,-./012345678:;<=^       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJ!KLMNOPQRSTUVWXYZ[\] genprog-0.1GenProg.GenExprGenProgGenProg.GenExpr.DataGenExprexchangenodeMapMnodeMapQ nodeIndicesadjustMnodesdepth EvolParamspopSizeiDepthcDepthcProbciProbmProbmiProbfitnessmutateelitists terminate TerminateMutateFitness EvolStatepopiter cachedBestPopunPopIndunIndaFitnessterminal nonterminalgenerateFullExprgenerateGrownExprmkIndsFitnessmkPop generatePop replenishPopmergePopbest avgFitnessavgDepthavgNodes crossoverInd mutateInd crossoverPop mutatePopdefaultMutationtSuccesstFitness tGenerationdefaultEvolParamsevolve evolveFromevolveTraceFrom evolveTraceMove backtrackrepeatMnextDfsQmoveForQ typeMoveFortypeMoveForUnsafe exchangeHolesindex terminalQ Distributiondist_iNodeseNodes generateExpradjustunadjustavg selectNode distributionchoosechoiceoneof selectInd reproducePop initState nextStateuntilM iterateUntilM evolvePop