/
calculateCompatibilityDistance.lua
151 lines (121 loc) · 3.93 KB
/
calculateCompatibilityDistance.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
require("NEAT/util/getLargerGenome")
--Calculate the compatibility distance between two genomes
function calculateCompatibilityDistance(genome1,genome2)
--Equation 1 from the paper
local E = numExcess(genome1,genome2)
local D = numDisjoint(genome1,genome2,E)
local C1 = COMPATIBILITY_C1
local C2 = COMPATIBILITY_C2
local C3 = COMPATIBILITY_C3
local N = #getLargerGenome(genome1,genome2).synapses
if(N < SMALL_GENOME_THRESHOLD) then
N = 1
end
local W = calculateW(genome1,genome2)
--print("E: ",E)
--print("D: ",D)
--print("C1: ",C1)
--print("C2: ",C2)
--print("C3: ",C3)
--print("N: ",N)
--print("W: ",W)
local compatibilityDistance = (C1*E/N) + (C2*D/N) + C3*W
return compatibilityDistance
end
--Using excessCount as input to speed up the algorithm and save space
--Hackathon: This could probably be optimized better
function numDisjoint(genome1,genome2,excessCount)
local disjointCount = 0
for i=1,#genome1.synapses do
-- Check if it has a matching synapse
local foundMatch = false
for j=1,#genome2.synapses do
--If the two markings are the same, it's a match
if genome1.synapses[i].historicalMarking == genome2.synapses[j].historicalMarking then
foundMatch = true
break;
end
end
if not foundMatch then
disjointCount = disjointCount + 1
end
end
--Now do it the other way around as well
for i=1,#genome2.synapses do
-- Check if it has a matching synapse
local foundMatch = false
for j=1,#genome1.synapses do
--If the two markings are the same, it's a match
if genome2.synapses[i].historicalMarking == genome1.synapses[j].historicalMarking then
foundMatch = true
break;
end
end
if not foundMatch then
disjointCount = disjointCount + 1
end
end
--Excess don't match but are categorized differently
local disjointCount = disjointCount - excessCount
return disjointCount
end
function numExcess(genome1,genome2)
local maxHistoricalMarkingGenome1 = 0
for i=1,#genome1.synapses do
if genome1.synapses[i].historicalMarking > maxHistoricalMarkingGenome1 then
maxHistoricalMarkingGenome1 = genome1.synapses[i].historicalMarking
end
end
local maxHistoricalMarkingGenome2 = 0
for i=1, #genome2.synapses do
if genome2.synapses[i].historicalMarking > maxHistoricalMarkingGenome2 then
maxHistoricalMarkingGenome2 = genome2.synapses[i].historicalMarking
end
end
--The genome with the more recent changes
local recentGenome = {}
--The most recent change to the less recent genome
local maxHistoricalMarkingOlderGenome = 0
if(maxHistoricalMarkingGenome1 > maxHistoricalMarkingGenome2) then
recentGenome = genome1
maxHistoricalMarkingOlderGenome = maxHistoricalMarkingGenome2
else
recentGenome = genome2
maxHistoricalMarkingOlderGenome = maxHistoricalMarkingGenome1
end
local excessCount = 0
--Run through each of the synapses
for i=1,#recentGenome.synapses do
local synapse = recentGenome.synapses[i]
--If the synapse we're looking at is newer than the newest in the older genome, then it's excess
if(synapse.historicalMarking > maxHistoricalMarkingOlderGenome) then
excessCount = excessCount + 1
end
end
return excessCount
end
--W is the average weight differences of matching synapses (including disabled synapses)
function calculateW(genome1,genome2)
local weightDifferences = {}
--Find all matches
for i=1,#genome1.synapses do
local synapse1 = genome1.synapses[i]
for j=1,#genome2.synapses do
local synapse2 = genome2.synapses[j]
if synapse1.historicalMarking == synapse2.historicalMarking then
--It's a match!
--What's the weight difference?
local weightDifference = math.abs(synapse1.weight - synapse2.weight)
table.insert(weightDifferences,weightDifference)
break
end
end
end
--Find the average of the weight differences
local weightDifferenceSum = 0
for i=1,#weightDifferences do
weightDifferenceSum = weightDifferenceSum + weightDifferences[i]
end
local W = weightDifferenceSum/#weightDifferences
return W
end