A Methodology for Processing Problem Constraints in Genetic
Contents
1. increasing sur vival chances In this case the measure of fit to this environment is based on the quality of a chromosome as a solution to the problem being solved Chromosomes interact with each other via crossover to produce new offspring solutions and they are subjected to mutation Most genetic algorithms operate on fixed length chromosomes which may not be suitable for some problems To deal with that some genetic algorithms adapted variable length representation as in machine learning 3 5 Moreover traditional genetic algorithms use low level binary representation but many recent applications use other abstracted alphabets 2 5 Genetic programming GP 7 8 9 uses trees to represent chromosomes At first used to generate LISP computer programs GP is also being used to solve problems where solutions have arbitrary interpretations 7 Tree representation is richer than that of linear fixed length strings However there is a price to pay for this richness In general the number of trees should equal the number of potential solutions with one to one mapping between them Unfortunately this is hardly ever possible Because we need a mapping for each potential solution the number of trees will tend to be much larger with some of them being redundant or simply invalid Therefore some means of dealing with such cases such as possibly avoiding the exploration of such extraneous trees are desired While for some problems some2. it is quite useful as our experiments illustrate section 4 and we believe the expressible constraints are the most general that could be implemented without increasing the computational complexity of lil gp section 3 2 5 and 3 2 7 Because Tspecs and F specs allow redundant specifications an obvious issue is that of the ex istence of sufficiently minimal specifications It turns out that after certain transformations only a subset of Tspecs and F specs is sufficient to express all such constraints This obser vation is extremely important as it will allow efficient constraint enforcement mechanisms after some initial preprocessing The first step is to extend F specs Proposition 1 The following are valid inferences for extending Fspecs from Tspecs Vier fe ZT fr FI Vrer fk g T Root EN fr E F If fk returns a range which is not compatible with the domain for the specific function argument fe T then fg cannot be used to provide values for the argument The same applies to values returned from the program The above proposition is very important as it states that Tspecs can be expressed with Fspecs Definition 3 If Fspecs explicitly satisfy proposition 1 then call them T extensive Fspecs If F specs do not satisfy proposition 1 for any function then call them T intensive F specs In other words T intensive Fspecs list only semantics based constraints which cannot be inferred from data types Proposition 2
3. this issue would be dealt with by CGP lil gp itself since no node would be labeled with such a function Early detection is rather a tool aimed at presenting such situations to the user Definition 6 If a function from F cannot label any nodes in a valid tree call it a useless function Proposition 6 A function f F is useless iff e it is a member of all sets of the normal form or e it is a member of all sets of the normal form except for only sets associated with useless functions 1 FS sets of the normal form list functions excluded from being called as children of other functions F lists functions excluded from labeling the Root A function excluded from labeling the Root and excluded from labeling all children nodes cannot possibly label any node in a valid program On the other hand if the function does not appear in at least one of the sets of the normal form then it can indeed label some nodes The only exception to the latter is when the function is allowed to be directly called only from other functions which are found to be useless Because the useless functions cannot label any nodes then the function in question will never be called in any tree Proposition 7 Removing useless functions from F does not change the CGP search space That is exactly the same programs can be evolved before and after the removal Useless functions cannot appear in any valid tree 3 2 3 Mutation sets lil gp allows parameters det
4. 7 will evolve solutions of the form illustrated in figure 2 lt Insert Fig2 gt Figure 2 Solution form for E7 4 10 Experimental results and discussion The results are very interesting some even striking To illustrate them we present two figures Figure 3 presents quality of the best solutions captured in 5 iteration intervals averaged over 5 independent runs In cases when a run finds the perfect 2048 tree before the 100th iteration its 2048 evaluation is used for averaging in subsequent iterations Figure 4 presents complexity measured by the number of nodes of the same best trees For each run which completes before the 100th iteration complexity 0 is used for averaging on subsequent generations This way the curves are directly proportional to average time needed to evaluate an individual since no more work is necessary after a solution is found In other words lower complexity would result in lower processing times per generation Moreover the area bounded by each curve is directly proportional to the total time needed for evolution with a bound 100 iterations 18 First when constraints are not present base and Eo both lil gp and CGP lil gp perform very similar searches discrepancies result from a different number of random calls thus resulting in stochastically different runs As indicated before this is not intended to serve as verification validation More systematic experiments are used to accomplish that w
5. A Methodology for Processing Problem Constraints in Genetic Programming Cezary Z Janikow Department of Mathematics and Computer Science University of Missouri St Louis emailto janikow radom umsl edu November 6 1997 Abstract Search mechanisms of artificial intelligence combine two elements representation which determines the search space and a search mechanism which actually explores the space Unfortunately many searches may explore redundant and or invalid so lutions Genetic programming refers to a class of evolutionary algorithms based on genetic algorithms but utilizing a parameterized representation in the form of trees These algorithms perform searches based on simulation of nature They face the same problems of redundant invalid subspaces These problems have just recently been ad dressed in a systematic manner This paper presents a methodology devised for the public domain genetic programming tool lil gp This methodology uses data typing and semantic information to constrain the representation space so that only valid and pos sibly unique solutions will be explored The user enters problem specific constraints which are transformed into a normal set This set is checked for feasibility and sub sequently it is used to limit the space being explored The constraints can determine valid possibly unique space Moreover they can also be used to exclude subspaces the user considers uninteresting using some problem spe
6. T ertensive Fspecs are sufficient to express all Tspecs Consider function fy and function fi of type I with arguments Two cases are possible e fk gt f Then fr Z T in Tspecs and according to proposition 1 fk F Thus Fspecs express the same information that f cannot be called from the j argument of fi e f gt fi Then fp T in Tspecs Thus based on Tspecs there is no reason to exclude from being called by the j argument of fi However Fspecs list additional constraints which supersede those of Tspecs Thus if f F then fy should be excluded regardless of Tspecs and if fy Z F then Fspecs and Tspecs say the same Now we look at redundancies among Fspecs Proposition 3 Suppose f E F and Fspecs are T extensive Then Vier fe Fi O Vyetuaxdi F If fk cannot call f then f will never be called by fy on any of its ap arguments However F and F are not equivalent a function may be allowed on some arguments but not on others Nevertheless both are not needed either F Fspecs are stronger Definition 4 If Fspecs explicitly satisfy proposition 3 then call them F extensive Fspecs Dropping all F from the F extensive Fspecs gives F intensive F specs Proposition 4 T ertensive F intensive Fspecs are sufficient to express all Fspec constraints Follows from proposition 3 Definition 5 Call the T exrtensive F intensive Fspecs the normal form That is the normal form cont
7. a more challenging environment in which only 200ur DNF GP evolved less than 90Even though a direct comparison was not an objective here one may draw some conclusions In this case both programs were using the same representation DNF The only difference is that CGP lil gp used only blind crossover mutation fired with static probabilities while GIL used operators modeling the inductive methodology whose firing was controlled by heuristics This suggests that such problem specific knowledge is extremely important to evolutionary problem solving lt Insert Fig3 gt Figure 3 Comparison of the quality of the best of population tree Because of similar results figures 3 and 4 report averages of FE Eo and E3 In the other experiments we investigate the utility of the if function for this specific problem The reason for this experiment is that our previous results with restricted but still sufficient function sets failed to improve search characteristics instead degrading the performance and leading to our suspicion that this interpretation rich function is extremely important for solving this problem with GP Thus E4 was set to evolve with only one type I function if Results are strikingly obvious perfect solutions finally emerge from this evolution on the 19 average after about 70 iterations However time complexity increases due to the increase in tree sizes figure 4 Increased tree sizes translate directly into longer proce
8. a valid tree To generate a valid random tree create the Root node and mutate it using the mutation operator Proposition 15 If Troo 9V Froot 4 and functions such that trees with such roots cannot cbfiw are removed from F then operator 2 will create a tree with at least one node the tree will be finite and valid with respect to constraints Because of the conditions at least one node can be labaled The functions remaining in the mutation sets can label trees with finite elements and guarantee validity 3 2 7 CGP lil gp crossover The idea to be followed is to generate one offspring by replacing a selected subtree from parent1 with a subtree selected from parent2 To generate two offspring the same may be repeated after swapping the parents Operator 3 Crossover Suppose that node N from parent is selected to receive a material from parent2 First determine Fy and Tn Assume that F gt is the set of labels appearing in parent2 Then Fn U Tn O F is the set of labels determining which subtrees from parent can replace the subtree of parent1 starting with N In other words any subtree of parent2 whose root is labeled with one of Fn UTn N F gt can replace N and still generate a valid tree Proposition 16 I f two valid trees are selected for crossover the operator will always produce a valid tree Moreover this is done with only the same order computational complexity For the first part arguments follow those of pr
9. ad hoc mechanisms have been proposed 7 8 there is no general methodology Our objective is to provide a systematic means while making sure that the means do not increase the overall computational complexity In this paper we present a method suitable for and implemented with a standard GP tool lil gp This methodology is a somehow weaker version of 6 modified specifically for lil gp lil gp is a tool 11 for developing GP applications Its implementation is based on the standard GP closure property 8 which states that every function can call any other function and that any terminal can provide values for any function argument Even though this is usually called a property it is in fact a necessity in the absence of other means for dealing with invalid trees Almost any application imposes some problem specific constraints on the placement of ele ments in solution trees Invalid solutions can be re interpreted as redundant solutions as done to force closure or they can be assigned low evaluations practically causing their extinction penalty approach Both approaches may face potential problems Too many ad hoc redundancies may easily change problem characteristics problem landscape Too many extinction bound solutions waste computational resources and may cause premature convergence over selection in GP 8 Recently other methods have been explored and proposed For example Montana has developed means for ensuring tha
10. ains only the F and F Fspecs after proper transformations Proposition 5 The normal form is sufficient to express all constraints of the Tspec F spec language According to proposition 2 T extensive Fspecs express or supersede Tspecs According to proposition 4 T extensive F intensive Fspecs express all the same info as any other form of F specs It is not shown here but the normal form is also the minimal form that expresses the Tspec and Fspec constraints Example 3 Constraints of eramples 1 and 2 have the following normal form ee A ta ad 1 F fi fo fs fa fos fr 2 FR F his fa fs fr 3 Fy Fy fs 4 Fz fs fs 5 The normal form expresses constraints in a unique and minimal form These transformed constraints are consulted by lil gp to restrict the search space Obvious questions remain how can crossover mutation use the information in an efficient and effective way We propose to express the normal form differently in mutation sets to facilitate efficient con sultations In fact we show that the overall O complexity for constrained mutation crossover remain the same 3 2 2 Useless functions Given a specific set of constraints it may happen that the constraints prohibit some func tions from being used in any valid program such functions would invalidate any program regardless of their position in the program tree Detection of such cases is addressed in this section Notice that
11. cient set the 11 multiplexer function expressed with these two functions is necessarily more complex Thus we should not expect any payoff from this constraint this is another example of problem specific knowledge In other words we suspect that this is not the right sufficient set 4 4 Experiment F DNF We attempt to generate DNF disjunctive normal form solutions Obviously if must be excluded However this is not sufficient We must also ensure that or is distributed over and and that not applies to type II functions atoms only This can be expressed one of possible options with the following Fspecs PRoot if F i z 0 Frou tif or and not Fina tif or Fy tif 4 5 Experiment 3 structure restricted DNF The above DNF specification leaves many interpretation isomorphic trees In this experi ment we intend to remove some of those redundancies though not all We constrain the trees to grow conjunctions and disjunctions to the left only thus we prohibit right recursive calls on or and and This is accomplished with the following modifications to Fspecs of E FRoot if F 0 pO Fra tif or and not 16 Poal or Eni 5 if or and Fa Ee if or Previous experience with other evolutionary algorithms using DNF representation suggest that DNF is the right representation GIL system 5 Thus we would expect both FE and E3 to do relatively well We will shortly observe tha
12. cific knowledge A simple exam ple is followed thoroughly to illustrate the constraint language transformations and the normal set Experiments with boolean 11 multiplexer illustrate practical applica tions of the method to limit redundant space exploration by utilizing problem specific knowledge Supported by a grant from NASA JSC NAG 9 847 1 Preliminaries Solving a problem of the computer involves two elements representation of the problem or that for its potential solutions and a search mechanism to explore the space spanned by the representation In the simplest case of computer programs the two elements are not explicitly separated and instead are hard coded in the programs However separating them has numerous advantages such as reusability for other problems which may require only modified representation This idea has been long realized and practiced in artificial intelligence There one class of algorithms borrows ideas from nature namely population dynamics selective pressure and information inheritance by offspring to organize its search This is the class of evolutionary algorithms Genetic algorithms GAs 2 3 4 are the most extensively studied and applied evolution ary algorithms A GA uses a population of chromosomes coding individual potential solu tions These chromosomes undergo a simulated evolution facing Darwinian selective pressure Chromosomes which are better with respect to a simulated environment have
13. citly retained and effectively randomly or exhaustively searched by an algorithms Instead the space is defined by implicit means often by transition operators generating new states from existing ones along with a set of currently explored solutions Given a complete set of operators some control strategy is then used to manage the search Such approaches are called state space searches in artificial intelligence 1 Evolutionary algorithms utilize state space searches The subspace being explored is retained in the population of chromosomes Genetic operators such as mutation and crossover gen erate new solutions from the existing ones The control is stochastic promoting exploration of better subspaces additional heuristics may be used to further guide the search as in 5 In GP a set of functions and a set of terminals are defined Elements of these label the internal and the external nodes respectively Interpretations of those elements are given by providing implementations for evaluating nodes labeling them Then a generic interpreter uses those interpretations to evaluate a tree by following a standard traversal For example a root node having three subtrees must be labeled with a function having three arguments These subtrees are evaluated recursively and their values are used as arguments to the function labeling the root Following evolutionary algorithms GP generates a population of random trees using the primit
14. e lil gp allows any function of type I to label any internal node and any function of type II and III to label any external node Obviously in general different functions take different arguments and return different ranges Tspecs allow expressing such differences thus allowing reduction in the space of tree structures and tree instances Moreover some Tspecs also implicitly restrict what function can call other functions Tspecs are analogous to function prototypes and data typing in the context of tree like computer programs and thus they are similar to Montana s type restrictions 10 Example 1 Assume Fr fi fo fs with arities 3 2 and 1 respectively Assume Fy fa and Frrr fs fe fr Assume that the three type III functions generate random boolean integer and real respectively Assume f reads an integer Assume f takes boolean and two integers respectively and returns a real Assume fo takes two reals and returns a real Assume fz takes a real and returns an integer Also assume that the problem spec ifications state that a solution program should compute a real number what the problem might be is irrelevant here The example assumes that integers are compatible with reals while booleans are not compatible with either different than in the C programming language These assumptions are expressed with the following Tspecs eee Se ST a fis fa fs Sas fo fr re fs TT fs fa fo However syntac
15. ed in DNF disjunctive normal form as 241A 9d7 V 0201 God V 9G aod V 2G Goda V G01 Apd3 V G21 God V G20 Ad V G20 dodo In 8 Koza has proposed to use the following function set Fy and or not if and termi nals Fry ao d2 do d7 no Frrr functions for evolving the 11 multiplexer function 14 with GP In this case GP evolves trees which are labeled with the above primitive elements each element having the standard interpretation The only feedback to this evolution is the evaluation environment which assigns a fitness value to each tree based on the number of the possible 2048 input combinations which compute the correct output bit The function set is obviously complete thus satisfying sufficiency However the set is also redundant a number of type I subsets such as and not are known to be sufficient to represent any boolean formula Thus by placing restrictions on function use we may reduce the amount of redundant subspaces in the representation space However we do not know what function sets make it easier or more difficult to solve this problem by evolution In fact the following experiments will spark very interesting observations suggesting that sufficiency itself is not strong enough to predict learning properties in addition to providing the necessary functions terminals one should also provide the right functions terminals As to closure it is trivially satisfied for this problem since al
16. ermining how deep to grow a subtree while in mutation That is lil gp allows differentiation between functions of type I and terminal nodes labeled with type II or III We need to provide for the same capabilities Definition 7 Define Fy to be the set of functions of type I that can label thus excluding useless functions node N without invalidating an otherwise valid tree containing the node Define Ty to be the set of terminals T that can label node N the same way Proposition 8 Assume the normal form for constraints and node N not being the Root and being the j child of a node labeled fi Then Tn falta E p A fe Frr U Frrr Fu fife Z FZ A fe Fr The normal constraints express all Tspecs and Fspecs according to proposition 5 N is not the Root so it must be a child of a node labeled with functions with arguments F in the normal form lists all functions excluded from labeling the child N Proposition 9 Assume the normal form for constraints and node N being Root Then Th felfe FPO A fe Fre U Frrr Fu falfe Z FA fe Fr Arguments follow those for Proposition 8 Definition 8 Let us denote Troot and Froot the pair of mutation sets associated with Root Let us denote T and F the pair of mutation sets for the j child of a node labeled with f Proposition 10 For an application problem there are 1 Ell a mutation set pairs There is exactly one pair for Root For other nodes the mutation
17. i If the sets J are nonempty for all a children all the children can be instantiated to leaves Any child having T and only allowing recursive calls first case will necessarily create an infinite tree Any such child which also allows other type I function calls must be eventually instantiated with a finite tree only indirect recursion would obviously lead to infinite trees those are excluded in the second case Proposition 13 helps identify functions causing only infinite trees to be valid Such cases can be reported to the user Moreover the troublesome functions can be removed from consideration This feature along with useless functions is not currently implemented Montana 10 presents a procedure which also takes tree depth into account 3 2 5 CGP lil gp mutation lil gp mutates a tree by selecting a random node different probabilities for internal and external nodes The mutated node becomes the root of a subtree which is grown as deter mined by some parameters To stop growing a terminal function is used as the label To force growing a type I function is used as the label In CGP lil gp the only difference is that a subset of the original functions provides candidates for labels Operator 1 Mutation To mutate a node N first determine the kind of the node either Root or otherwise what the label of the parent is and which child of that parent N is If the growth is to continue label the node with a ra
18. is further supports our observation that providing such information is advantageous not only to generate solutions with some specific characteristics but to speeding up evolution as well Unfortunately usually this can only be done by a careful redesign of the algorithm representation operators or the function set in GP In CGP no changes are needed Between and Ey it is worthwhile to point out that Es which uses less redundant search space explores trees of slightly lower complexity Finally between the two and Es it is interesting to observe that while the former evolve perfect solutions in many fewer gener ations this involves trees of larger sizes In fact in terms of clock time performance Es outperforms these two areas in figure 4 5 Summary This paper describes a method to prune constraints identified subspaces from being explored in GP search The constraints are allowed in a user friendly language aimed at expressing syntax and semantics based restrictions to closure Specific constraints lead to the exclusion of syntactically invalid redundant or simply undesired trees from ever being explored Such 20 pruning may not only lead to more efficient problem solving with lil gp When studied systematically it may also give insights about pruning redundant subspaces from any state space search We have presented a complete methodology and illustrated it with an example We have also used the 11 multiplexer problem to il
19. ith extra processing to ensure the same random calls take place in which case both programs explore exactly the same trees Because the runs were very similar here figures 3 and 4 report averages from these two experiments Forcing evolution with and not type I set E1 even though it dramatically reduces the number of redundant solutions being explored has a disastrous effect It seems that the most important reason for this degradation is that as pointed out shortly if is extremely efficient in solving this problem with GP Moreover 11 multiplexer expressions using and not are necessarily more complex This would require extra processing to evolve as seen in Figure 3 the learning curve has not saturated after 100 iterations Forcing DNF functions to evolve 2 has equally disastrous effects on the program In this case even further restrictions on tree structures 3 failed to compensate for the dis advantage It seems that the reasons are similar to those above if will prove to be the most effective and thus extremely important The fact that GP fails to efficiently evolve DNF solutions is striking when compared against another evolutionary program designed for machine learning GIL 5 is a genetic algorithm with specialized DNF representation specialized inductive operators and evolutionary state space search controlled by inductive heuristics In reported experiments while evolving solutions to the same function but in
20. ive elements Then all trees are evaluated in the environment using functional in terpretations with the interpreter and the problem at hand Crossover and mutation are used to generate new trees in the population from parents selected following Darwinian principles GP also allows another operator selection which simply copies chromosomes to the new population Since all trees are evolved from the primitive elements these must be sufficient to generate the sought tree The assumption that this is indeed the case is called the sufficiency principle 8 However in general to satisfy sufficiency a large number of functions must be given This unfortunately exponentially explodes the search space In up to date applications this is dealt with by providing the right functions and terminals Obviously in many cases this may not happen and the search space will explode nevertheless To deal with this potential problem as well as its current weak manifestation practical size restrictions are imposed on the trees Unfortunately the more rigid the restriction the more likely that some important solutions may be excluded In the next section we will present a methodology to utilize constraints to prune implicitly identified subspaces In general the constraints we propose for the pruning include both syntactic and semantic elements Syntactic constraints include typing function arguments values returned by functions and individual termi
21. l terminals address data sensors and all type I functions return boolean Thus this problem does not have any invalid subspaces all constraints will be used only to reduce the number of redundant undesired trees Even given this triviality it is a very interesting problem We set a number of experiments intended to illustrate how CGP lil gp can be used to utilize various constraints drawn from problem specific knowledge For each case we repeat and average 10 independent runs with a population of 2000 0 85 0 1 0 05 probabilities for crossover selection mutation and otherwise the default parameters We report averages of best solutions generated at 5 iteration increments discrete learning curves while running for 100 iterations Previously we observed that the constraint language allows redundant specifications In fact many of the constraints we subsequently use can be expressed in a number of different ways it is the translator that generates unique equivalent constraints To make the presentation more systematic we assume that Tspecs stay constant and all constraints are expressed with F specs In one case however we illustrate how the same constraints can be expressed with different T specs The generic Tspecs we use do not impose any constraints Thus T Root T and or not if ao a2 do d7 where indicates any possible value here meaning that all sets are the same 4 1 Unconstrained 11 multiplexer
22. lustrate practical application of the methodology Even though illustration was our primary goal some interesting observations were made It has been obvious that the function set proposed by Koza for solving this problem is redundant Our experiments suggest that reducing those redundancies and thus reducing the search space is not necessarily advantageous However if the right choices are made a tremendous payoff can be expected This is further amplified by using additional problem specific knowledge CGP lil gp allows us to express such information with a generic constraint language alleviating the need for devising specialized representation operators However by comparing the results with those of another specialized algorithm we may observe that such a specialized algorithm makes it advantageously possible to implement other problem specific information and heuristics In the future we plan to make more systematic testing aimed at supporting the observations made here In particular we did not even explore the methodology s impact on the more serious problem of invalid subspaces where we expect the benefits to amplify We are also currently extending the implementation for ADFs automatically defined functions which will allow similar capabilities to Montana s generic functions 10 yet more general as our crossover is more general One should point out that the current constraint specification language does not allow fo
23. nals These are similar to those of Mon tana 10 Semantic constraints are additional restrictions based on function or terminal interpretation The methodology presented here is a weaker version of that presented in 6 but it is the one that has been implemented with Jzl gp 3 CGP Methodology 3 1 Constraint specifications In lil gp 11 functions and terminals fall into three categories Let us call them functions of type I II and III as described below and sets of those functions will be denoted as Fr Fir and Frrr Unless explicitly stated all references to functions imply all function types denoted F and all references to terminals imply functions of type II and III denoted T Borrowing 11 s terminology we have I Ordinary functions These are functions of at least one argument thus they can label internal nodes with the number of subtrees corresponding to the number of arguments II Ordinary terminals These are functions of no arguments Therefore they can label external nodes However they are not instantiated in trees but rather during interpre tation In other words these terminal values are provided by the environment as for a function reading the current temperature Ill Ephemeral random constant terminals These are functions of no arguments which are instantiated individually in each tree thus the values are independent of the envi ronment In lil gp 11 terminal sets for type HI are not exte
24. ndom element of Fy and continue growing the proper number of subtrees each grown recursively with the same mutation operator Otherwise select a random element of Tn instantiate it if from Frrr and stop expanding N If growing a tree and Fy 9 then select a member of Tn guaranteed not to be empty under proposition 11 If stopping the growth and Ty 9 then select a member of Fy this will unfortunately extend the tree but it is guaranteed to stop according to proposition 13 Proposition 14 If a valid tree is selected for mutation operator 1 will always produce a valid tree Moreover this is done with only constant overhead The mutation sets express exactly the same information as ae and Fspecs Moreover the only implementation difference is to consult one of 1 Sela instead of a single set of function labels in lil gp Which set to consult is immediately determined from the parent node and can be accessed in constant time given proper data structure 12 Example 6 Assume the mutation sets of erample 4 Assume mutating parenti as in figure 1 Assume the node N is selected for mutation It is the 1st child of a node labeled with fs Thus Tn T fa fe fr and Fy Ft fi fo If the current mode is to grow the tree then the mutated node will be randomly labeled with either f or fo If the current node is to generate a leaf then label N with either fa fg or fr 3 2 6 CGP lil gp initialization Operator 2 Create
25. nsively defined Instead they are defined by generating functions which return uniform random elements from the appropriate ranges Ranges for functions of type I and type II and not explicitly defined either In 6 we defined the notion of domain range compatibility denoted here which can be used to infer validity of using functions and terminals as arguments to other functions That notion based on sets allows automated processing of such compatibilities With lil gp these capabilities cannot be automated since no explicit sets are used and the resulting methodology is somehow weaker section 4 gives an example Therefore all compatibility specifications are left to user s responsibility similarly to Montana s approach 10 This unfortunately means that the user must be trained in the domain Fortunately our pre processing offers a user friendly method to specify constraints which method can deal with inconsistent and or redundant specifications Definition 1 Define the following Tspecs syntactic constraints 1 T the set of functions which return data type compatible with the problem speci fication 2 T Tj is the set of functions compatible with the jth argument of fi In terms of a labeled tree Toot is the set of functions which according to data types can possibly label the Root node T is the set of functions that can possibly label the j child node of a node labeled with f Following closur
26. oposition 14 since crossover is based on the same mutation sets Crossover is implemented in lil gp in such a way that a random number up to the number of nodes in parent2 is generated and then the tree is traversed until the numbered node is encountered can be done separately for internal and external nodes Therefore crossover s complexity is in the size of the tree O n CGP lil gp does not know ahead of the traversal how many nodes will be found applicable During the traversal applicable nodes are indexed for constant time access and they are counted At the end of the tree a random number up to the counter is generated and the proper node is immediately accessed On average this requires traverasl twice as long but 13 in the same order Instead of generating indexed constant time access structures another traversal may follow This does not change the overall complexity adds another O n lt Insert Fig gt Figure 1 Illustration of mutation and crossover Example 7 Assume mutation sets of erample 4 Assume parenti and parent2 as in figure 1 Assume the node N is selected for replacing with a subtree of parent2 It is the 1st child of a node labeled with fs Then Tn T3 fa fo fz and Fy Fz fi fo and only the subtrees with the shaded roots can be used to replace N Crossover would select a random element from a so marked set of nodes and move the corresponding subtree 4 Illustrative Experiment In this
27. ore powerful since it allows more feasible offspring from the same two parents A more systematic comparison will be presented separately In section 2 we overview the problems CGP attempts to alleviate In section 3 we present the CGP methodology for lil gp along with a complexity analysis A simple example is used to illustrate the processing from constraint specification to generation of the minimal set This section can be omitted by readers not interested in technical details In section 4 we present initial experiments designed to illustrate CGP lil gp s application to deal with re dundant undesired search spaces using the 11 multiplexer problem This experiment is only intended to illustrate how problem specific knowledge can be expressed with the constraint language and what the implications of restricting the search are However some important observations are made in section 4 10 fttp radom umsl edu 2 State Space Searches and GP Search Space In artificial intelligence solving a problem on the computer involves searching the collection of possible solutions For example solving a two dimensional integer optimization problem with both domains 1 100 would involve searching through the space of 10 000 solutions one for each pair This search may be random enumerated exhaustive or heuristic 1 However in most practical problems of interest to artificial intelligence the space of potential solutions is too large to be expli
28. r arbitrary constraints to be expressed In particular this lil gp s version is even weaker than the originally proposed methodology Thus for the future we also plan to explore extending the language and or this implementation of lil gp References 1 Leonard Bole amp Jerzy Cytowski Search Methods for Artificial Intelligence Academic Press 1992 2 Lawrence Davis ed Handbook of Genetic Algorithms Van Nostrand Reinhold 1991 3 David E Goldberg Genetic Algorithms in Search Optimization and Machine Learning Addison Wesley 1989 4 Holland J Adaptation in Natural and Artificial Systems University of Michigan Press 1975 5 Cezary Z Janikow A Knowledge Intensive GA for Supervised Learning Machine Learning 13 1993 pp 189 228 21 Cezary Z Janikow Constrained Genetic Programming Submitted to Evolutionary Computation Kenneth E Kinnear Jr ed Advances in Genetic Programming The MIT Press 1994 John R Koza Genetic Programming The MIT Press 1992 John R Koza Genetic Programming II The MIT Press 1994 David J Montana Strongly typed genetic programming Evolutionary Computation Vol 3 No 2 1995 Douglas Zonker amp Bill Punch lil gp 1 0 User s Manual zonker isl cps msu edu 22
29. section we follow a practical example intended to illustrate how problem specific knowledge can be used to come up with various constraints In this experiment we explore different constraints that can be used to express and thus restrict some of the redundant solutions from being explored by GP This is intended as illustration but we also explore the implications of such restrictions on the behavior of GP In fact this issue arises in any state space search and has yet to be addressed We hope that our tool will help in studying this issue We will use the widely studied 11 multiplexer problem 8 Multiplexer is a boolean circuit with a number of inputs and exactly one output In practical applications a multiplexer is used to propagate exactly one of the inputs to the output For example in the computer CPU central processing unit multiplexers are used to pass binary bits via a group of multiplexers from exactly one location e g one register to the ALU arithmetic logic unit Multiplexer has two kinds of binary inputs address and data The address combination determines which of the data inputs propagates to the output Thus for a address bits there are 2 data bits 11 multiplexer has 3 address and 8 data bits Let us call them ag a2 and do dz respectively For example when the address is 110 the boolean formula a2a then dg is passed to the output 11 multiplexer implements a boolean function which can be express
30. sets are determined by what function labels the parent node and which child of the parent the node is Parent nodes are of type I If the label of the parent is fi then it can have exactly a different children The above implies that the information expressed in the normal form can be expressed with 2 1 yl a different function sets while only two sets one pair are needed in lil gp itself Now we show how these sets alone are sufficient to initialize CGP lil gp programs with only valid trees to mutate valid trees into valid trees and to crossover valid trees into valid trees 10 Proposition 11 For any non root node N of a valid program at least one of the two mutation sets is guaranteed not to be empty The same is true for Root see proposition 12 Suppose N is labeled with f If N is an internal node then fi E Fy If N is a leaf then fi E Tn Example 4 Here are selected examples of mutation sets generated for example 3 TRoot fr Frot fis fo fa Tz fa fs fo Fa fi fa 3 2 4 Constraint feasibility Unfortunately constraints may be so severe that only empty or only infinite trees are valid In the first case GP would fail to initialize trees or it would try infinitely In the second case GP would run out of memory or it would fail as in the first case if size restrictions were imposed To avoid such problems this could be detected early and the troublesome functions can be identified and pos
31. sibly removed from the function set We exclude the empty tree from being valid In other words a tree must contain at least one node to constitute a potential solution Proposition 12 If TRoot 9 A Froot 9 then no valid trees exist There is no way to label the Root Thus valid nonempty trees do not exist Stated differently a valid tree cannot have both of these sets empty Proposition 12 identifies trivial cases when no valid trees exist because only empty trees are valid However a more common problem might be that only infinite trees exist Example 5 Consider a function f Fy such that Jjea F F fi in the normal form In other words on the given argument the function can only call itself It can be verified that any node N being the j child of any node labeled with fi will have the following mutation sets proposition 8 Ty and Fy fi This means that the child node can only be labeled the same way as the parent f Recursively the same will apply to its j child Note that the same can happen through indirect recursion as well Definition 9 We say that a subtree whose root is labeled f can be finitely instantiated without cbfiw F C F iff finite valid trees without labels from F do exist 11 Proposition 13 A tree with its root labeled f cannot be finitely instantiated without func tions from F fi cbfiw F iff either is true en ON A hh jea OAV eneu te chfiw FU f
32. ssing time per iteration Thus the wall clock performance might not necessarily improve To alleviate the problem we used additional problem specific information about different interpretation of address and data bits Es This leads not only to further speed up in evolution figure 3 The evolving trees also have the smallest sizes from among all experiments figure 4 This result supports our previous conjecture that problem specific knowledge is crucial here It also illustrates how the generic CGP lil gp can utilize this kind of information GIL on the other hand was designed and implemented with such problem specific knowledge from the beginning In other words this result indicates that it is indeed important to provide the right and minimal set of functions for GP For example comparing results from Ey and E4 one may see a dramatic improvement despite the fact that both experiments use the identified if function This indicates that reducing the redundant subspace pays off in this case but only because the right subspace was pruned away lt Insert Fig4 gt Figure 4 Comparison of complexity needed for evolving solutions in 100 generations com plexity 0 used on finished runs Finally providing additional heuristic about the desired solutions and thus pruning away other otherwise valid solutions leads to even better speed ups and Ey in figure 3 are av eraged since they produced indistinguishable curves Th
33. t and speculate why this is not the case 4 6 Experiment F using if only Here we observe that the type I function set Fy if is completely sufficient for the task of learning the 11 multiplexer Even though studying that is not our explicit objective we may compare the learning characteristics of this experiment with those of other complete function sets E4 F2 and E3 giving us some insights as to what functions make it easier for GP to evolve solutions to the 11 multiplexer problem Our observations will be rather striking Restricting trees to use this function only can be accomplished with the following Fspecs Foot F and or not F 0 x a Tor and VE irrelevant 4 7 Experiment FE E4 with problem specific knowledge Now suppose that in addition to observing that if is a sufficient type I function set we also use some additional problem specific knowledge For example suppose we know that the first three bits are addresses and the others are data bits Knowing the interpretation of if which we do since we implement it we may further conclude that the condition argument 1 should test addresses and the other arguments should compute and thus return data bits This constraint could be completely expressed with a slightly enlarged function set To avoid extra complexity we express a somehow lesser constraint one which restricts only immediate arguments in the original theory it is possible to specify
34. t only valid trees evolve Strongly Typed Genetic Programming STGP 10 and we independently proposed a similar methodology for processing more arbitrary constraints in Constrained Genetic Pro gramming CGP 6 CGP in addition to providing means for avoiding exploration of invalid subspaces also provides for specification avoidance of both redundant subspaces as well as subspaces which are perfectly valid but some problem specific heuristics suggest to exclude them from being desired solutions The objectives of CGP is to provide means to specify syntax and semantic constraints and to provide efficient systematic mechanisms to enforce them 6 We have just implemented a pilot tool which incorporates CGP with the widely used GP tool lil gp1 02 lil gp allows forrest chromosomes which for computer programs corresponds to program modules our current methodology deals with a single tree but it is currently being extended This paper describes CGP applied to lil gp called CGP lil gp Even though this paper is not intended to compare STGP with CGP it is worthwhile to point out that CGP ensures that the extra processing does not change the overall complexity of the basic GP mechanisms Moreover CGP allows more user friendly front end for constraint specifications with a transformation aimed at reducing the constraints to a minimal set It also allows various constraints such as syntax and semantics based Finally CGP s crossover is m
35. the stronger constraint for this function set because that theory is based on sets rather than functions 6 This can be expressed with the following Fspecs proot and or not ao Qi az F 0 F and or not do d7 Fy F and or not ao a1 a2 x ls Eor and Ppi irrelevant or the same Fspecs as those of E plus the following Tspecs this is just for illustration however as indicated earlier Tspecs are intended to restrict closure T if ao 41 a2 TST ei if do dr 17 4 8 Experiment Es with further heuristic knowledge Further suppose that we prevent trees of E from using if on its first argument This further reduces redundancy while still allowing solutions to evolve This can be accomplished with FRoot and or not Ao Q1 da F F and or not if do dr F FR and or not ag a1 a2 F F F irrelevant and 4 9 Experiment Ez E relaxed Finally suppose that we want to allow another function to enrich our explored search space not to be used in the condition part of if However we make sure that it only applies to non negated address bits This of course introduces additional redundancy This can be accomplished with FrRoot and or not ao a1 a2 F F and or if do dr Fy F and or not ao a1 a2 Faot F a0 a1 a2 Sees a F Fr g irrelevant With the above E
36. tic fit does not necessarily mean that a function should call another function One needs additional specifications based on program semantics These are provided by means of F specs which further restrict the space of trees Definition 2 Define the following Fspecs semantic constraints 1 Fe the set of functions disallowed at the Root 2 F F is the set of functions disallowed as direct callers to f generally a function is unaware of the caller however GP constructs a tree Cee ile F is the set of functions disallowed as arg to fi 6 Example 2 Continue example 1 Assume that we know that the sensor reading function fs does not provide the solution to our problem We also know that boolean generated by fs cannot be the answer this information is actually redundant as it can be inferred from Tspecs however it will be easier for the user if no specific requirements are made as to how to specify non redundant constraints Also assume that for some semantic reasons we wish to exclude f3 from calling itself e g this is the integer part function which yields identity when applied to itself These constraints are expressed with the following Fspecs the other sets are empty FrRoot fa fs Fy fs 3 2 Transformation of the constraints 3 2 1 Normal form The above Tspecs and Fspecs provide a specification language for expressing problem con straints Obviously this language is limited in power However
37. with lilgp base experiment Even though it is not our current intention here to evaluate the impact that the reduction of redundant subspaces may have on search properties we set a benchmark obtained from unconstrained lil gp on the same problem In this experiment we evolve 11 multiplexer solu tions using the above function set and no constraints Thus we recreate Koza s experiments except that we use lil gp and not CGP lil gp either The remaining experiments all use CGP lil gp 15 4 2 Experiment Epo unconstrained 11 multiplexer with CGP lil gp This is the same base experiment except that it is run with CGP lil gp Thus there are no constraints all Fspecs are empty This experiment may be treated as informal validation formal validation verification is done separately and will be reported elsewhere 4 3 Experiment E using sufficient set and not We observe that and not is a sufficient type I function set Thus we run an experiment with only these two type I functions While in this specific case it is also possible to run lil gp with only these functions by modifying and then recompiling the program this is not our objective Instead we show how this particular constraint can be presented in CGP lil gp Our constraint is that of the four type I functions if and or be not used at all This can be expressed with the following Fspecs FP _ F if or F We should note that even though and not is a suffi
Download Pdf Manuals
Related Search