Реализация генетического алгоритма с двухточечным кроссовером на Python

August 21, 2018 20:52

Двухточечное скрещивание отличается от точечного тем, что родительские хромосомы обмениваются участком генетического кода, который находится между двумя случайно выбранными точками скрещивания.

#!/bin/python
# Пример реализации генетического алгоритма с двухточечным кроссовером

from random import randint, randrange


def cross(male, female):
    point_0 = randrange(0, len(male.gens))
    point_1 = randrange(0, len(male.gens))

    if point_0 > point_1:
        point_0, point_1 = point_1, point_0

    female_gens_part = female.gens[point_0:point_1]
    child_gens = male.gens[:point_0] + female_gens_part + male.gens[point_1:]

    child = Person(loads=male.loads,
                    gens=child_gens,
                    proc_num=male.proc_num)
    
    return child

class Population:
    def __init__(self, persons):
        self.persons = persons

    def __str__(self):
        return 'population: \n{}'\
            .format(''.join(['\tperson #{}{}\n'.format(i, str(x)) for i, x in enumerate(self.persons)]))

    def __eq__(self, population):
        a = [p.maxload for p in population.persons]
        b = [p.maxload for p in self.persons]
        if min(a) == min(b):
            return True
        return False

    def extinction(self, count):
        if count == 0:
            return
        else:
            self.persons.sort(key=lambda p: p.maxload, reverse=False)
            for i in range(count):
                self.persons.pop()


class Person:
    def __init__(self, loads, proc_num, gens=None):
        self.loads = loads
        self.proc_num = proc_num
        self.gens = gens

        if gens is None:
            self.gens = [randrange(0, 255) for i in range(len(loads))]

        self.maxload = self.max_load()

    def __str__(self):
        return ' {} max_load: {}' \
            .format(''.join(['({}, {})'.format(x, y) for x, y in zip(self.gens, self.loads)]),
                    self.maxload)


    def mut(self):
        bit_0 = randrange(0, 8)
        point_0 = randrange(0, len(self.gens))
        self.gens[point_0] ^= 2 ** (bit_0)

        bit_1 = randrange(0, 8)
        point_1 = randrange(0, len(self.gens))
        
        self.gens[point_1] ^= 2 ** (bit_1)

        self.maxload = self.max_load()

        return ((self.gens[point_0], self.loads[point_0], bit_0), (self.gens[point_1], self.loads[point_1], bit_1))

    def max_load(self):
        procs = [0 for i in range(self.proc_num)]

        for i, gen in enumerate(self.gens):
            num = int(gen / (256 / self.proc_num))
            try:
                assert num < len(procs)
            except AssertionError as e:
                print(e)

            procs[num] += loads[i]

        return max(procs)

    def min_load(self):
        procs = [0 for i in range(self.proc_num)]

        for i, gen in enumerate(self.gens):
            num = int(gen / (256 / self.proc_num))
            try:
                assert num < len(procs)
            except AssertionError as e:
                print(e)

            procs[num] += loads[i]

        return min(procs)


def new_generation(population, p_cross, p_mut):
    new_population = Population([])

    for i, p in enumerate(population.persons):
        new_population.persons.append(p)

        if randint(0, 100) / 100 < p_cross:

            l = randrange(0, len(population.persons))
            while l == i:
                l = randrange(0, len(population.persons))

            new_person = cross(p, population.persons[l])
            print('\t~~child~~ {}\n\t parents: #{} and #{}\n'
                  .format(new_person, i, l))

            if randint(0, 100) / 100 < p_mut:
                one, two = new_person.mut()
                print('\t **mutation** {} \n'.format(new_person), '\n'.join([f'\tgen: ({gen}, {load}) bit: {bit}' for gen, load, bit in new_person.mut()]))
                    
                    # pass])))
                # print('\t**mutation** {} \n\tgen: ({}, {}) bit: {} \n'.format(new_person, gen, load, bit))

            new_population.persons.append(new_person)

    new_population.extinction(int(len(new_population.persons) / 2)) # вымирание половины поколения
    return new_population


if __name__ == '__main__':

    N = int(input('N:'))  # процессоров
    M = int(input('M:'))  # задач
    
    left, right = map(int, input('range: ').split())  # дапазон
    
    N_cr = int(input('N_cr:'))  # начальное число особей (хромосом)
    N_lim = int(input('N_lim:'))  # условие останова
    
    P_cross = float(input('P_cross:'))  # вероятность применения кросс оператора
    P_mut = float(input('P_mut:'))  # вероятность мутации

    # left = 10
    # right = 19

    # N = 5
    # M = 13

    # N_cr = 11
    # N_lim = 10

    # P_cross = 0.4
    # P_mut = 0.5

    loads = [randint(left, right) for i in range(M)]
    population = Population([Person(loads=loads, proc_num=N) for i in range(N_cr)])
    print(population)

    lim = 0
    generation_iter = 0

    while lim < N_lim - 1 and len(population.persons) > 1:
        ng = new_generation(population, P_cross, P_mut)
        print(f'generation # {generation_iter}', ng)
        generation_iter += 1

        if ng == population:
            lim += 1
        else:
            lim = 0
            
        population = Population(persons=list(ng.persons))