Genetic algorithm for one max problem

one_max.py

#coding:utf-8

import random
import math
import copy

def calc_score(x):
    return sum(x)

def find_elite(population):
    score = map(lambda x: calc_score(x), population)
    max_val = -1
    max_index = None

    for i, val in enumerate(score):
        if val > max_val:
            max_val = val
            max_index = i

    return copy.deepcopy(population[max_index])


def cross(parent1, parent2):
    length = len(parent1)
    r1 = int(math.floor(random.random() * length))
    r2 = r1 + int(math.floor(random.random() * (length - r1)))

    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]

    return child


def mutate(parent):
    r = int(math.floor(random.random() * len(parent)))
    child = copy.deepcopy(parent)
    child[r] = (parent[r] + 1) % 2

    return child



def select(num, population):
    selection = []
    score = map(lambda x:calc_score(x), population)
    total = sum(score)
    for i in range(n):
        threshold = math.floor(random.random() * total)
        sum_score = 0
        for index, val in enumerate(score):
            sum_score += val
            if sum_score > threshold:
                selection.append(population[index])
                break

    return selection

if __name__ == "__main__":
    dim = 10
    n = 20
    cross_rate = 0.95
    generation = 25

    population = []
    for i in range(n):
        arr = [random.randint(0, 1) for j in range(dim)]
        population.append(arr)


    for g in range(generation):
        print "Generation: " + str(g)

        #find elite
        elite = find_elite(population)    

        #cross and mutate
        next_population = []
        for i in range(n):
            if random.random() < cross_rate:
                if i != n - 1:
                    child = cross(population[i], population[i+1])
                else:
                    child = cross(population[i], population[0])
            else:
                child = mutate(population[i])
            next_population.append(child)

        #selection
        population = select(n - 1, population + next_population)
        population = [elite] + population

        print map(sum, population)