Searching of test for the problem "Japanese computer" by genetic algorithm

gen.py

#!/usr/bin/env python
# gen.py -- Searching of test for the problem "Japanese computer" by genetic algorithm
# Usage: ./gen.py ./executable_file
#
# Author: Roman Tereshin <tereshin.roman@gmail.com>
# Created: 2014-03-19

import os
import sys
import time
import math
import random
import subprocess

mut_factor = 2
gen_size = 1000
numof_gens = 20
copy_limit = 1
internal_timer = False

executable_test_fname = "computer.in"
executable_fname = "./exec"
max_time_prefix = "./max_time"
max_time_fname = max_time_prefix + ".time"
max_test_fname = max_time_prefix + ".in"
time_util = "/usr/bin/time"

r = random.Random()
max_time = 0.0
max_memory = 0
counter = 0

max_n = 42

def make_random_test():
  n = r.randint(1, max_n - 1)
  return set(r.sample(range(2, max_n + 1), n))

def make_child(parent1, parent2):
  both = parent1.intersection(parent2)
  symdiff = parent1.symmetric_difference(parent2)
  child = both.union(r.sample(symdiff, r.randint(0, len(symdiff))))
  suppl = set(range(2, max_n + 1)).difference(child)
  to_remove = r.sample(child, r.randint(0, min(mut_factor, len(child))))
  to_insert = r.sample(suppl, r.randint(0, min(mut_factor, len(suppl))))
  mut_child = child.difference(to_remove).union(to_insert)
  return mut_child

def string_of_test(test):
  return str(len(test)) + "\n" + " ".join([str(i) for i in test]) + "\n"

def run():
  global max_memory
  if os.path.isfile(time_util) and os.access(time_util, os.X_OK):
    out = subprocess.check_output([time_util, "-f", "%M", executable_fname],
                                  stderr=subprocess.STDOUT)
    memory_cons = int(out) / 4
    max_memory = max(max_memory, memory_cons)
  else:
    subprocess.check_call(executable_fname)

def run_with_internal_timer():
  out1 = subprocess.check_output([executable_fname], stderr=subprocess.STDOUT)
  out2 = subprocess.check_output([executable_fname], stderr=subprocess.STDOUT)
  return min(float(out1), float(out2))

def measure_time(test):
  open(executable_test_fname, "w").write(string_of_test(test))
  if internal_timer:
    return run_with_internal_timer()
  start_time = time.time()
  run()
  elapsed_time = time.time() - start_time
  return elapsed_time

def make_message(gen_max_time):
  msg = "max time changed: %.3f" % gen_max_time
  if max_memory > 0:
    msg += " (max memory usage %.1f Mb)" % (max_memory / 1024.0)
  return msg

def create_next_gen(gen):
  global max_time
  global counter
  measured_gen = map(lambda test: (measure_time(test), test), gen)
  measured2    = map(lambda test: (measure_time(test), test), gen)
  measured_gen = map(min, measured_gen, measured2)
  measured_gen.sort()
  measured_gen.reverse()
  for i in xrange(len(measured_gen)):
    if measured_gen[i][0] > copy_limit:
      counter += 1
      open(max_test_fname + "%04d" % counter, "w") \
          .write(string_of_test(measured_gen[i][1]))
    else:
      break
  if measured_gen[0][0] > max_time:
    max_time = measured_gen[0][0]
    open(max_test_fname, "w").write(string_of_test(measured_gen[0][1]))
    open(max_time_fname, "w").write(str(max_time) + "\n")
    print make_message(measured_gen[0][0])
  numof_parents = int(math.sqrt((0.5 * len(gen)) / mut_factor))
  parents = map(lambda pair: pair[1], measured_gen[:numof_parents])
  new_gen = parents[:]
  for p1 in parents:
    for p2 in parents:
      new_gen += [make_child(p1, p2) for _ in xrange(mut_factor)]
  new_gen += [make_random_test() for _ in xrange(len(gen) - len(new_gen))]
  return new_gen

def print_usage_and_exit():
  print ("Usage %s <executable file> [<number of generations>]\n" \
       + "Example: %s %s\nDefault number of generations is %d") \
       % (sys.argv[0], sys.argv[0], executable_fname, numof_gens)
  sys.exit(1)

def main():
  global executable_fname
  global numof_gens
  global max_time
  if len(sys.argv) < 2 and not os.path.isfile(executable_fname):
    print_usage_and_exit()
  if len(sys.argv) >= 2:
    executable_fname = sys.argv[1]
    if len(sys.argv) > 2:
      numof_gens = int(sys.argv[2])

  if os.path.isfile(max_time_fname):
    max_time = float(open(max_time_fname).read())

  gen = [make_random_test() for _ in xrange(gen_size)]
  for i in xrange(1, numof_gens + 1):
    print "gen #%d" % i
    try:
      gen = create_next_gen(gen)
    except KeyboardInterrupt:
      print "  Bye!"
      sys.exit(1)
    if counter > 0:
      print "number of tests with time over %.2f: %d" % (copy_limit, counter)

if __name__ == "__main__":
  main()

24
8 14 16 17 18 19 20 22 23 24 25 26 27 29 31 32 33 34 35 36 38 39 41 42

5
17 42 23 37 31