initial commit

1 files changed, 93 insertions, 0 deletions

diff --git a/ga.lua b/ga.lua
new file mode 100644
index 0000000..8b5b0e2
--- /dev/null
+++ b/ga.lua
@@ -0,0 +1,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