import random

MAX_GEN = 100
POP_SIZE = 50
IND_LEN = 50
CX_PROB = 0.8
MUT_PROB = 0.5
MUT_PROB_PER_BIT = 1/IND_LEN

def random_individual():
    return [random.randint(0,1) for _ in range(IND_LEN)]

def random_population(pop_size):
    return [random_individual() for _ in range(pop_size)]

def fitness(ind):
    return sum(ind)

def crossover(p1, p2):
    if random.random() < CX_PROB:
        point = random.randrange(0, IND_LEN)
        o1 = p1[:point] + p2[point:]
        o2 = p2[:point] + p1[point:]
        return o1, o2
    else:
        return p1[:], p2[:]

def mutation(p1):
    if random.random() < MUT_PROB:
        return [1-g if random.random() < MUT_PROB_PER_BIT else g for g in p1]
    else:
        return p1[:]

def select(pop, fits, N):
    return random.choices(pop, fits, k=N)

def evolutionary_algorithm(pop):
    log = []
    for _ in range(MAX_GEN):
        fits = [fitness(x) for x in pop]
        best = max(pop, key=fitness)
        log.append(max(fits))
        mating_pool = select(pop, fits, len(pop))
        offspring = []
        for p1, p2 in zip(mating_pool[::2], mating_pool[1::2]):
            o1, o2 = crossover(p1, p2)
            o1 = mutation(o1)
            o2 = mutation(o2)
            offspring.append(o1)
            offspring.append(o2)
        pop = offspring[:]
        pop[0] = best
    return pop, log

def pop_fit(pop):
    return [fitness(ind) for ind in pop]

pop = random_population(POP_SIZE)
fits = pop_fit(pop)
print(sum(fits)/POP_SIZE)

pop,log = evolutionary_algorithm(pop)
fits = pop_fit(pop)
print(sum(fits)/POP_SIZE)
print(log)

def plot(log):
    import matplotlib.pyplot as plt
    plt.plot(log)
    plt.show()

plot(log)