Реализация генетического алгоритма на Python

August 19, 2018 19:03

Генетический алгоритм - это эвристический алгоритм поиска, который используется для решения задач оптимизации и моделирования путем случайного подбора и комбинирования параметров. Такой алгоритм - разновидность эволюционных вычислений. Его главным отличием является использование оператора скрещивания. То есть алгоритм пытается скрещивать решения так, будто бы это происходит в реальном мире.

#!/bin/python
# Пример реализации генетического алгоритма
 
from random import randint, randrange


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

    return Person(loads=male.loads,
                  gens=male.gens[:point] + female.gens[point:],
                  proc_num=male.proc_num)


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

    def __str__(self):
        return 'population: \n{}'\
            .format(''.join(['\tperson #{}{}\n'.format(i, str(x), x.maxload) 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 = randrange(0, 8)
        point = randrange(0, len(self.gens))
        self.gens[point] ^= 2 ** (bit)
        self.maxload = self.max_load()

        return self.gens[point], self.loads[point], bit

    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:
                gen, load, bit = new_person.mut()
                print('\t**mutation** {} \n\tgen: ({}, {}) bit: {} \n'.format(new_person, gen, load, bit))

            new_population.persons.append(new_person)

    new_population.extinction(len(new_population.persons) - len(population.persons))
    return new_population


if __name__ == '__main__':

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

    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:
        ng = new_generation(population, P_cross, P_mut)
        print(ng)
        generation_iter += 1

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