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
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
56 if p1_depth>=1:
57 p1_mutation_depth=1
58 else:
59 p1_mutation_depth=random.randint(1, p1_depth-1)
60
61
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
68 if isinstance(fragment_p1, list):
69 firstnode_p1= fragment_p1[0]
70 if isinstance(fragment_p1, tuple):
71 firstnode_p1=fragment_p1
72
73 subtree1_parent_s = crossutil.IndexLstToIndexStr2(p1_point)
74
75
76 if firstnode_p1[0]!=2:
77 subtree1_parent_s= subtree1_parent_s[:-3]
78
79 exec("subtree1_parent=parent1_clone%s"%subtree1_parent_s)
80
81
82 context_p1= settings.treeRules[subtree1_parent[0][2]]
83 context=copy.deepcopy(context_p1)
84
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
89
90
91 min_mutation_depth=1
92
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
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
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
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