crossover

44 """ 45 Function: Koza1PointCrossover 46 ============================== 47 create 2 offsprings from 2 parents using a modified version of Koza-1-point 48 crossover. This version try to produce offsprings compliant with the 49 constraints and rules used to build an individual. If it does not manage, 50 it produce a report showing if the offsprings produced are compatible. 51 52 @param maxdepth: maximum depth of the mutated offspring 53 @param p1: parent tree 1 e.g. a=buildtree.buildTree().AddHalfNode((0,2,'root'),0,2,7) 54 @param p2: parent tree 2 e.g. a=buildtree.buildTree().AddHalfNode((0,2,'root'),0,2,7) 55 @param p1_mp: parent tree index mapping e.g a_map=crossutil.get_indices_mapping_from_tree(a) 56 @param p2_mp: parent tree index mapping e.g a_map=crossutil.get_indices_mapping_from_tree(a) 57 @param p1_depth: parent tree depth e.g. a_depth=crossutil.get_depth_from_indices_mapping(a_map) 58 @param p2_depth: parent tree depth e.g. a_depth=crossutil.get_depth_from_indices_mapping(a_map) 59 60 @return: a tuple containing 3 elements 61 - The first one is a list of 1 and 0 indicating if the first and second offspring are rule 62 compliant. 63 [1,1,1,1] frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2 64 [1,0,1,1] frag2_leaf_compatible_p1 and not frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2 65 [1,1,0,1] frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and frag1_branch_compatible_p2 66 and so on... This information can be use to decide if we want to introduce non-compliant offsprings into the population. 67 - The second one is the first offspring 68 - The third one is the second offspring 69 70 """ 71 p1_map=deepcopy(p1_mp) 72 p2_map=deepcopy(p2_mp) 73 # get a random depth for parent1 74 p1_cross_depth=random.randint(1, p1_depth-1) 75 # get a random depth in p2 such that the resulting 76 # offspring lenght is <= offspring maxdepth 77 fragment_p1_depth= p1_depth-1-p1_cross_depth 78 if p2_depth > (maxdepth-fragment_p1_depth): 79 if maxdepth-fragment_p1_depth>0: 80 p2_cross_depth=random.randint(1,(maxdepth-fragment_p1_depth)) 81 else: 82 p2_cross_depth=1 83 else: 84 p2_cross_depth=random.randint(1, p2_depth-1) 85 mychoice1=crossutil.UnpackIndicesFromList(\ 86 crossutil.GetPackedListIndicesAtDepth(p1_map,p1_cross_depth)) 87 p1_point=random.choice(mychoice1) 88 #print crossutil.index_lst_to_index_str2(p1_point) 89 mychoice2=crossutil.UnpackIndicesFromList(\ 90 crossutil.GetPackedListIndicesAtDepth(p2_map,p2_cross_depth)) 91 p2_point=random.choice(mychoice2) 92 #print crossutil.index_lst_to_index_str2(p2_point) 93 parent1_clone=deepcopy(p1) 94 parent2_clone=deepcopy(p2) 95 exec("fragment_p1=parent1_clone%s"%crossutil.IndexLstToIndexStr2(p1_point)) 96 exec("fragment_p2=parent2_clone%s"%crossutil.IndexLstToIndexStr2(p2_point)) 97 # Having selected a sub tree, we need to check structural integrity and compatibility 98 #print fragment_p1 99 #print fragment_p2 100 # first we want to know if the sub-tree is located under a specific ADF defining branch 101 102 # first we need to extract the top node of each subtree 103 if isinstance(fragment_p1, list): 104 firstnode_p1= fragment_p1[0] 105 #print list(treeutil.BFS_Search(fragment_p1)) 106 if isinstance(fragment_p1, tuple): 107 firstnode_p1=fragment_p1 108 if isinstance(fragment_p2, list): 109 firstnode_p2=fragment_p2[0] 110 #print list(treeutil.BFS_Search(fragment_p2)) 111 if isinstance(fragment_p2, tuple): 112 firstnode_p2=fragment_p2 113 114 # get the parent node of each sub tree (context of each parent) 115 subtree1_parent_s = crossutil.IndexLstToIndexStr2(p1_point) 116 if firstnode_p1[0]!=2: 117 subtree1_parent_s= subtree1_parent_s[:-3] 118 119 subtree2_parent_s = crossutil.IndexLstToIndexStr2(p2_point) 120 if firstnode_p2[0]!=2: 121 subtree2_parent_s= subtree2_parent_s[:-3] 122 123 exec("subtree1_parent=parent1_clone%s"%subtree1_parent_s) 124 #print subtree1_parent[0] 125 exec("subtree2_parent=parent2_clone%s"%subtree2_parent_s) 126 #print subtree2_parent[0] 127 128 # get the context from grammar rules for each parent 129 # print buildtree.buildTree().treeSets 130 context_p1= settings.treeRules[subtree1_parent[0][2]] 131 context_p2= settings.treeRules[subtree2_parent[0][2]] 132 133 # check that the subtree are compatible with their new parents 134 frag1_leaf_compatible_p2=True 135 frag2_leaf_compatible_p1=True 136 frag1_branch_compatible_p2=True 137 frag2_branch_compatible_p1=True 138 # extract all terminal nodes of the fragment subtrees in flat lists 139 frag1, frag2 =[], [] 140 #print fragment_p1 141 #print list(treeutil.LeafNodes_Search(fragment_p1)) 142 if list(treeutil.LeafNodes_Search(fragment_p1)): 143 if isinstance(list(treeutil.LeafNodes_Search(fragment_p1))[0], tuple): 144 frag1=list(treeutil.LeafNodes_Search(fragment_p1)) 145 else: 146 frag1=[tuple(fragment_p1)] 147 else: 148 frag1=fragment_p1 149 if list(treeutil.LeafNodes_Search(fragment_p2)): 150 if isinstance(list(treeutil.LeafNodes_Search(fragment_p2))[0], tuple): 151 frag2=list(treeutil.LeafNodes_Search(fragment_p2)) 152 else: 153 frag2=[tuple(fragment_p2)] 154 else: 155 frag2=fragment_p2 156 #print frag1 157 #print context_p2[1] 158 #print frag2 159 #print context_p1[1] 160 # check if the fragments have terminal nodes incompatible with parent context 161 for elem_frag2 in frag2: 162 if elem_frag2 not in context_p1[p1_point[-1]-1][1]: 163 frag2_leaf_compatible_p1=False 164 break 165 for elem_frag1 in frag1: 166 if elem_frag1 not in context_p2[p2_point[-1]-1][1]: 167 frag1_leaf_compatible_p2=False 168 break 169 # extract all branch nodes of the fragment subtrees in flat lists 170 frag1, frag2 =[], [] 171 if isinstance(list(treeutil.BranchNodes_Search(fragment_p1))[0], tuple): 172 frag1=list(treeutil.BranchNodes_Search(fragment_p1)) 173 else: 174 frag1=[tuple(fragment_p1)] 175 if isinstance(list(treeutil.BranchNodes_Search(fragment_p2))[0], tuple): 176 frag2=list(treeutil.BranchNodes_Search(fragment_p2)) 177 else: 178 frag2=[tuple(fragment_p2)] 179 # if no branch node in subtree, then branch is all compatible... 180 for elem_frag1 in frag1: 181 if len(frag1)==1 and frag1[0][0]!=1: 182 frag1_branch_compatible_p2=True 183 elif elem_frag1 not in context_p2[0]: 184 frag1_branch_compatible_p2=False 185 break 186 else: 187 frag1_branch_compatible_p2=True 188 for elem_frag2 in frag2: 189 if len(frag2)==1 and frag2[0][0]!=1: 190 frag2_branch_compatible_p1=True 191 elif elem_frag2 not in context_p1[0]: 192 frag2_branch_compatible_p1=False 193 break 194 else: 195 frag2_branch_compatible_p1=True 196 197 #print frag1 198 #print context_p2[0] 199 #print frag2 200 #print context_p1[0] 201 202 # if the automatic replacement of compatible branch operators is authorized 203 # do it to make the offspring compatible wit hthe grammar rules... 204 copy_fragment_p1 = deepcopy(fragment_p1) 205 copy_fragment_p2 = deepcopy(fragment_p2) 206 if frag1_branch_compatible_p2==False \ 207 and frag1_leaf_compatible_p2==True \ 208 and settings.Strongly_Typed_Crossover_degree>=1: 209 #print 'replace branches fragment1' 210 211 frag1=list(set(frag1)) 212 temp1=str(copy_fragment_p1) 213 #print temp1 214 for elem_frag1 in frag1: 215 for elem_p2 in context_p2[p2_point[-1]-1][0]: 216 for elem_crossover_mapping in settings.crossover_mapping: 217 if elem_crossover_mapping[1]==str(elem_p2[2]) and elem_crossover_mapping[0]==str(elem_frag1[2]): 218 temp1=temp1.replace(elem_crossover_mapping[0], elem_crossover_mapping[1]) 219 #print temp 220 exec("copy_fragment_p1 =%s"%temp1) 221 #print copy_fragment_p1 222 223 if frag2_branch_compatible_p1==False \ 224 and frag2_leaf_compatible_p1==True \ 225 and settings.Strongly_Typed_Crossover_degree>=1: 226 #print 'replace branches fragment2' 227 228 frag2=list(set(frag2)) 229 temp2=str(copy_fragment_p2) 230 #print temp2 231 for elem_frag2 in frag2: 232 for elem_p1 in context_p1[p1_point[-1]-1][0]: 233 for elem_crossover_mapping in settings.crossover_mapping: 234 if elem_crossover_mapping[1]==str(elem_p1[2]) and elem_crossover_mapping[0]==str(elem_frag2[2]): 235 temp2=temp2.replace(elem_crossover_mapping[0], elem_crossover_mapping[1]) 236 #print temp 237 exec("copy_fragment_p2 =%s"%temp2) 238 #print copy_fragment_p2 239 240 frag1_leaf_compatible_p2=True 241 frag2_leaf_compatible_p1=True 242 frag1_branch_compatible_p2=True 243 frag2_branch_compatible_p1=True 244 # extract all terminal nodes of the fragment subtrees in flat lists 245 frag1, frag2 =[], [] 246 if list(treeutil.LeafNodes_Search(fragment_p1)): 247 if isinstance(list(treeutil.LeafNodes_Search(fragment_p1))[0], tuple): 248 frag1=list(treeutil.LeafNodes_Search(fragment_p1)) 249 else: 250 frag1=[tuple(fragment_p1)] 251 else: 252 frag1=fragment_p1 253 if list(treeutil.LeafNodes_Search(fragment_p2)): 254 if isinstance(list(treeutil.LeafNodes_Search(fragment_p2))[0], tuple): 255 frag2=list(treeutil.LeafNodes_Search(fragment_p2)) 256 else: 257 frag2=[tuple(fragment_p2)] 258 else: 259 frag2=fragment_p2 260 #print frag1 261 #print context_p2[1] 262 #print frag2 263 #print context_p1[1] 264 # check if the fragments have terminal nodes incompatible with parent context 265 for elem_frag2 in frag2: 266 if elem_frag2 not in context_p1[p1_point[-1]-1][1]: 267 frag2_leaf_compatible_p1=False 268 break 269 for elem_frag1 in frag1: 270 if elem_frag1 not in context_p2[p2_point[-1]-1][1]: 271 frag1_leaf_compatible_p2=False 272 break 273 274 #print frag2_leaf_compatible_p1 275 #print frag1_leaf_compatible_p2 276 #print frag1_branch_compatible_p2 277 #print frag2_branch_compatible_p1 278 279 # return the offspring resulting from the crossover with indicators of 280 # structural compliance of the offspring. 281 # [1,1,1,1] frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2 282 # [1,0,1,1] frag2_leaf_compatible_p1 and not frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2 283 # [1,1,0,1] frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and frag1_branch_compatible_p2 284 # and so on... 285 # This information can be use to decide if we want to introduce non-compliant offsprings into the population. 286 287 if frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2: 288 exec("parent1_clone%s=copy_fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 289 exec("parent2_clone%s=copy_fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 290 return ([1,1,1,1],parent1_clone,parent2_clone) 291 elif frag2_leaf_compatible_p1 and not frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2: 292 #print "One of the Leafs from fragment1 in the offspring is not compatible with context from parent2 " 293 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 294 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 295 return ([1,0,1,1],parent1_clone,parent2_clone) 296 elif not frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2: 297 #print "One of the Leafs from fragment2 in the offspring is not compatible with context from parent1 " 298 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 299 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 300 return ([0,1,1,1],parent1_clone,parent2_clone) 301 elif not frag2_leaf_compatible_p1 and not frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and frag1_branch_compatible_p2: 302 #print "Leafs from fragment2 and fragment1 in the offsprings are not compatible with context from parent1 and parent2 " 303 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 304 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 305 return ([0,0,1,1],parent1_clone,parent2_clone) 306 elif frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and frag1_branch_compatible_p2: 307 #print "One of the Branches from fragment2 in the offspring is not compatible with context from parent1 " 308 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 309 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 310 return ([1,1,0,1],parent1_clone,parent2_clone) 311 elif frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and frag2_branch_compatible_p1 and not frag1_branch_compatible_p2: 312 #print "One of the Branches from fragment1 in the offspring is not compatible with context from parent2 " 313 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 314 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 315 return ([1,1,1,0],parent1_clone,parent2_clone) 316 elif frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and not frag1_branch_compatible_p2 : 317 #print "Branches from fragment1 and Fragment2 in the offsprings are not compatible with context from parent2 and parent1 " 318 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 319 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 320 return ([1,1,0,0],parent1_clone,parent2_clone) 321 elif frag2_leaf_compatible_p1 and not frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and not frag1_branch_compatible_p2 : 322 #print "Branches from fragment1 and Fragment2 in the offsprings are not compatible with context from parent2 and parent1 " 323 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 324 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 325 return ([1,0,0,0],parent1_clone,parent2_clone) 326 elif not frag2_leaf_compatible_p1 and frag1_leaf_compatible_p2 and not frag2_branch_compatible_p1 and not frag1_branch_compatible_p2 : 327 #print "Branches from fragment1 and Fragment2 in the offsprings are not compatible with context from parent2 and parent1 " 328 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 329 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 330 return ([0,1,0,0],parent1_clone,parent2_clone) 331 else: 332 # no branch nor leaf compatible from fragment to parent nodes 333 exec("parent1_clone%s=fragment_p2"%crossutil.IndexLstToIndexStr2(p1_point)) 334 exec("parent2_clone%s=fragment_p1"%crossutil.IndexLstToIndexStr2(p2_point)) 335 return ([0,0,0,0],parent1_clone,parent2_clone)

Source Code for Module crossover