pythonで遺伝的アルゴリズムを実装してみた。

genom.py

import random
import itertools


SIZES = tuple(random.randint(0, 10) for i in range(200))
TARGET = 100
GENOM_NUM = 100
MUTATION_NUM = 10

MAX_LOOP = 100


def make_genom():
	return tuple(bool(random.randint(0, 1)) for i in range(len(SIZES)))


def cross_genom(a, b):
	pos = random.randint(1, len(a)-2)
	return tuple(itertools.chain(a[:pos], b[pos:]))


def mutation(a):
	pos = random.randint(0, len(a)-1)
	result = list(a)
	result[pos] = not result[pos]
	return tuple(result)


def fitness(genom):
	return abs(TARGET - sum(SIZES[i] for i in range(len(SIZES)) if genom[i]))


def choice(xs):
	return min((random.choice(xs) for i in range(2)), key=fitness)


if __name__ == '__main__':
	xs = [make_genom() for i in  range(GENOM_NUM)]
	best = min(fitness(x) for x in xs)

	for i in range(MAX_LOOP):
		if i%5 == 0:
			print('{0}: {1}'.format(i, best))

		xs = [cross_genom(choice(xs), choice(xs)) for i in range(GENOM_NUM)]

		for j in range(MUTATION_NUM):
			pos = random.randint(0, GENOM_NUM-1)
			xs[pos] = mutation(xs[pos])

		best = min(fitness(x) for x in xs)
		if best == 0:
			break

	print('-'*5)
	print('{0}: {1}'.format(i, best))