Module mutation
[hide private]
[frames] | no frames]

Source Code for Module mutation

  1  """ 
  2  mutation 
  3  ======== 
  4  Contains strongly-typed version of the Koza-based mutation operator. 
  5   
  6  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  7  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
  8  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
  9  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 10  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 11  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 12  THE SOFTWARE. 
 13   
 14  @author: by Mehdi Khoury 
 15  @version: 1.20 
 16  @copyright: (c) 2009 Mehdi Khoury under the mit license 
 17  http://www.opensource.org/licenses/mit-license.html 
 18  @contact: mehdi.khoury at gmail.com 
 19  """ 
 20   
 21  import psyco 
 22  import random 
 23  import settings 
 24  import crossutil 
 25  import treeutil 
 26  import buildtree 
 27  import copy 
 28  #from types import * 
 29  import evalfitness 
 30  import sys 
 31  from collections import deque 
 32  import mutation 
 33   
 34  psyco.profile() 
 35   
 36   
 37   
38 -def Mutate(maxdepth,parent,p1_map,p1_depth):
39 """ 40 Function: Mutate 41 ================= 42 create a mutated individual from a parent tree using Koza styled mutation 43 44 @param maxdepth: maximum depth of the mutated offspring 45 @param parent: parent tree e.g. a=buildtree.buildTree().AddHalfNode((0,2,'root'),0,2,7) 46 @param p1_map: parent tree index mapping e.g a_map=crossutil.get_indices_mapping_from_tree(a) 47 @param p1_depth: parent tree depth e.g. a_depth=crossutil.get_depth_from_indices_mapping(a_map) 48 49 @return: a tuple containing two elements. 50 - The first one is a boolean indicating if the mutated tree is identical to the parent 51 (if identical, returns True) 52 - The second one is the mutated tree 53 54 """ 55 # get a random depth for parent1 56 if p1_depth>=1: 57 p1_mutation_depth=1 58 else: 59 p1_mutation_depth=random.randint(1, p1_depth-1) 60 # get a random depth in p2 such that the resulting 61 # offspring lenght is <= offspring maxdepth 62 mychoice1=crossutil.UnpackIndicesFromList(\ 63 crossutil.GetPackedListIndicesAtDepth(p1_map,p1_mutation_depth)) 64 p1_point=random.choice(mychoice1) 65 parent1_clone=copy.deepcopy(parent) 66 exec("fragment_p1=parent1_clone%s"%crossutil.IndexLstToIndexStr2(p1_point)) 67 # first we need to extract the top node of each subtree 68 if isinstance(fragment_p1, list): 69 firstnode_p1= fragment_p1[0] 70 if isinstance(fragment_p1, tuple): 71 firstnode_p1=fragment_p1 72 # get the parent node of each sub tree (context of each parent) 73 subtree1_parent_s = crossutil.IndexLstToIndexStr2(p1_point) 74 # if the first node is not an ADF, the string version of the 75 # index of the subtree is just the index of upper node in the tree 76 if firstnode_p1[0]!=2: 77 subtree1_parent_s= subtree1_parent_s[:-3] 78 # get the subtree using the index we just obtained 79 exec("subtree1_parent=parent1_clone%s"%subtree1_parent_s) 80 # get the flat list of permitted nodes for the parent tree 81 # for that first get the list of permitted branch nodes... 82 context_p1= settings.treeRules[subtree1_parent[0][2]] 83 context=copy.deepcopy(context_p1) 84 # and extend to it the list of permitted leaf nodes 85 context[p1_point[-1]-1][0].extend( context[p1_point[-1]-1][1]) 86 if len(context[p1_point[-1]-1][0])>1 and firstnode_p1[0]==2: 87 context[p1_point[-1]-1][0].remove(firstnode_p1) 88 # get the context from grammar rules for each parent 89 90 # min_mutation_depth for the subtree has to be extracted by looking when is the next child with a terminal 91 min_mutation_depth=1 92 #print context[p1_point[-1]-1][0] 93 flag=random.choice(context[p1_point[-1]-1][0]) 94 if not settings.treeRules[subtree1_parent[0][2]][p1_point[-1]-1][1]: 95 min_mutation_depth=2 96 #print flag 97 98 mutant_fragment=buildtree.buildTree().AddHalfNode(\ 99 random.choice(context[p1_point[-1]-1][0]) ,p1_mutation_depth,p1_mutation_depth+min_mutation_depth,maxdepth) 100 # make sure that the mutant fragment is different from the previous fragment 101 if len(mutant_fragment)==1 and isinstance(mutant_fragment[0], tuple): 102 mutant_fragment=mutant_fragment[0] 103 exec("parent1_clone%s=mutant_fragment"%crossutil.IndexLstToIndexStr2(p1_point)) 104 identical=False 105 if mutant_fragment==fragment_p1: 106 identical =True 107 # no branch nor leaf compatible from fragment to parent nodes 108 return (identical, parent1_clone)
109 110 111 if __name__ == '__main__': 112 for i in xrange(10000): 113 a=buildtree.buildTree().AddHalfNode((0,2,'root'),0,2,7) 114 a_map=crossutil.GetIndicesMappingFromTree(a) 115 a_depth=crossutil.GetDepthFromIndicesMapping(a_map) 116 print a 117 m=mutation.Mutate(10,a,a_map,a_depth) 118 print m 119 m_map=crossutil.GetIndicesMappingFromTree(m[1]) 120 m_depth=crossutil.GetDepthFromIndicesMapping(m_map) 121 print m_depth 122 print evalfitness.FinalFitness_tutorial8(evalfitness.EvalTreeForOneListInputSet_tutorial8(m[1])) 123