Genetic Algorithms in VimL (Part I)

Burak Kanber is into machine learning. I was entertained by his Hello World genetic algorithm example and, in alignment with his implementation language agnosticism, I thought I'd write a version in VimL:

This depends on vim-rng for the random number stuff.

let s:Chromosome = {}

function! s:Chromosome.New(...)
  let chromosome = copy(self)
  let chromosome.code = ''
  let chromosome.cost = 9999
  let chromosome.pivot = 0

  if a:0
    let chromosome.code = a:1
    let chromosome.pivot = (strchars(chromosome.code) / 2) - 1
  endif

  return chromosome
endfunction

function! s:Chromosome.random(length)
  let self.code = RandomString(a:length)
  let self.pivot = (a:length / 2) - 1
  return self
endfunction

function! s:Chromosome.mutate(chance)
  if (RandomNumber(100) / 100.0) < a:chance
    let index = RandomNumber(1, strchars(self.code)) - 1
    let upOrDown = RandomNumber(100) <= 50 ? -1 : 1
    let exploded = split(self.code, '\zs')
    let change = nr2char(char2nr(exploded[index]) + upOrDown)
    if index == 0
      let self.code = change . join(exploded[index+1:], '')
    else
      let self.code = join(exploded[0:index-1], '') . change . join(exploded[index+1:], '')
    endif
  endif
  return self
endfunction

function! s:Chromosome.mate(chromosome)
  let child1 = strpart(self.code, 0, self.pivot) . strpart(a:chromosome.code, self.pivot)
  let child2 = strpart(a:chromosome.code, 0, self.pivot) . strpart(self.code, self.pivot)
  return [s:Chromosome.New(child1), s:Chromosome.New(child2)]
endfunction

function! s:Chromosome.calcCost(compareTo)
  let total = 0
  let i = 0
  while i < strchars(self.code)
    let diff = char2nr(self.code[i]) - char2nr(a:compareTo[i])
    let total += diff * diff
    let i += 1
  endwhile
  let self.cost = total
  return self
endfunction

function! s:Chromosome.to_s()
  return self.code . ' (' . string(self.cost) . ')'
endfunction


let s:Population = {}

function! s:Population.New(goal, size)
  let population = copy(self)
  let population.members = []
  let population.goal = a:goal
  let population.generationNumber = 0
  let population.solved = 0

  let size = a:size
  let length = strchars(population.goal)
  while size > 0
    let chromosome = s:Chromosome.New()
    call chromosome.random(length)
    call add(population.members, chromosome)
    let size -= 1
  endwhile

  return population
endfunction

function! s:Population.display()
  % delete
  call setline(1, "Generation: " . self.generationNumber)
  call setline(2, map(copy(self.members), 'v:val.to_s()'))
  redraw
  return self
endfunction

function! s:Population.costly(a, b)
  return float2nr(a:a.cost - a:b.cost)
endfunction

function! s:Population.sort()
  call sort(self.members, self.costly, self)
endfunction

function! s:Population.generation()
  call map(self.members, 'v:val.calcCost(self.goal)')

  call self.sort()
  call self.display()

  let children = self.members[0].mate(self.members[1])
  let self.members = extend(self.members[0:-3], children)

  let i = 0
  while i < len(self.members)
    call self.members[i].mutate(0.5)
    call self.members[i].calcCost(self.goal)
    if self.members[i].code == self.goal
      call self.sort()
      call self.display()
      let self.solved = 1
      break
    endif
    let i += 1
  endwhile

  let self.generationNumber += 1

  return self
endfunction

enew
let population = s:Population.New('Hello, world!', 20)
while population.solved != 1
  call population.generation()
endwhile

To see it run save it in a file and type   :so %   from within vim.

Why, dear bairui, you ask? Well, at this stage... I don't know. It just looked like fun. However, a couple of wild thoughts occurred to me: finding the ideal (good enough; as in 'correct' enough) combination of various vim options to achieve a desired look and behaviour. Take for example the various C indenting styles - what mad combination of &cinoptions, &cinkeys and &cinwords would you need to achieve Frankenstein's Indentation Style? What about getting &formatlistpat right for your preferred markup style? Sure, these might be totally hair-brained ideas -- but they might give you an idea for something less hairy and actually useful. Either way, I plan to keep playing with Burak's tutorial as he progresses through it. Thanks, Burak! :-)