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
|
local module = {}
setmetatable(module, {__index=_G})
setfenv(1, module)
local GA = {}
local metaGA = { __index=GA }
function module.createGA(population, operators)
local self = {
population=population,
operators=operators,
}
local totalWeight =
(operators.crossWeight or 1) +
(operators.mutationWeight or 1) +
(operators.reproductionWeight or 1)
self.operators.crossDensity = (operators.crossWeight or 1) / totalWeight
self.operators.mutationDensity = self.operators.crossDensity + ((operators.mutationWeight or 1) / totalWeight)
self.operators.reproductionDensity = 1
setmetatable(self, metaGA)
return self
end
function GA.evaluate(self)
self.fitnesses = {}
for i, p in ipairs(self.population) do
self.fitnesses[i] = self.operators.evaluate(p)
if i == 1 or self.fitnesses[i] > self.maxFitness then
self.maxFitness = self.fitnesses[i]
self.bestMember = i
end
end
end
function GA.tournamentPick(self, k)
local tournamentPop = {}
while #tournamentPop < k do
table.insert(tournamentPop, math.ceil(#self.population * math.random()))
end
table.sort(tournamentPop, function(a, b) return self.fitnesses[a] > self.fitnesses[b] end)
return tournamentPop[1]
end
function GA.stochasticPick(self)
local idx = math.ceil(#self.population * math.random())
local f = self.fitnesses[idx] / self.maxFitness
if math.random() < f then
return idx
else
return self:stochasticPick()
end
end
function GA.createNewPopulation(self, k)
k = k or 128
local newPop = {}
while #newPop < #self.population do
local r = math.random()
if r < self.operators.crossDensity then
local a = self:tournamentPick(k)
local b = self:tournamentPick(k)
table.insert(newPop, self.operators.crossover(self.population[a], self.population[b]))
elseif r < self.operators.mutationDensity then
local a = self:tournamentPick(k)
table.insert(newPop, self.operators.mutate(self.population[a]))
elseif r < self.operators.reproductionDensity then
local a = self:tournamentPick(k)
table.insert(newPop, self.population[a])
end
end
return newPop
end
function GA.step(self)
self.fitnesses = nil
self.maxFitness = nil
self:evaluate()
self.population = self:createNewPopulation()
return self.maxFitness
end
return module
|
