Понимание генетического алгоритма

Генетический алгоритм? О чем это? Это эвристический поиск, вдохновленный великой теорией эволюции Чарльза Дарвина. В очередной раз область информатики черпала вдохновение из области биологии.

Теория эволюции Чарльза Дарвина утверждает, что эволюция происходит путем естественного отбора.

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

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

Генетические алгоритмы имитируют выживание наиболее приспособленных среди особей последовательных поколений к решению проблемы. Итак, прежде чем углубляться, давайте напомним себе о некоторых ключевых принципах Чарльза Дарвина в теории естественного отбора.

Наследственность. Должен происходить процесс, при котором дети наследуют некоторые характеристики от своих родителей.
Изменчивость. Должно быть разнообразие в чертах популяции или способах внесения изменчивости или разнообразия в популяцию.
Отбор. В популяции должен существовать способ, при котором родители передают свои генетические характеристики своим детям, и способ, при котором некоторые из них не передают эти генетические характеристики.

Как эти принципы используются в генетическом алгоритме?

Должна существовать популяция, которая поддерживается в пространстве поиска. Как и в теории Дарвина, каждая хромосома (индивидуально составленная из нескольких генов) составляет популяцию, которая участвует в борьбе за выживание наиболее приспособленных. В генетическом алгоритме мы создаем пространство поиска (т. е. популяцию), каждая из точек которого представляет собой решение пространства поиска для данной проблемы.
Итак, в этой статье мы пытаемся найти строку «Меня зовут Ричард», поэтому мы создаем пространство поиска в диапазоне от a до z, от A до Z и некоторого символа. Важно, чтобы население было на месте.

Функция пригодности определяет, насколько приспособлена способность индивидуума в популяции конкурировать с другими индивидуумами. Хромосомы (индивидуумы) с лучшими показателями приспособленности имеют больше возможностей для размножения по сравнению с другими хромосомами с плохими показателями приспособленности. Замечено, что хромосомы с лучшими показателями приспособленности дают лучшее потомство за счет объединения хромосом родителей. Поскольку размер популяции статичен, существующие хромосомы должны умереть, чтобы создать пространство для нового поколения. Для каждого поколения цикл продолжается, и каждое поколение, которое следует за предыдущим поколением, имеет лучшие гены, следовательно, ближе к решению, чем предыдущие поколения. Когда нет существенной разницы в потомстве, произведенном между предыдущим поколением и последующим поколением, говорят, что алгоритм сходится к набору решений проблемы.

Как происходит эволюция от поколения к поколению в генетическом алгоритме?

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

После рождения нового потомства одним из принципов Дарвина в теории естественного отбора является важность изменчивости популяции. Следовательно, важно мутировать гены новых потомков, чтобы обеспечить разнообразие или изменчивость популяции, а также избежать преждевременной конвергенции. Следовательно, оператор мутации необходим для обеспечения вышеуказанного.

При реализации генетического алгоритма для получения целевой строки, начиная со случайной строки, реализуется приведенное выше обсуждение генетического алгоритма.

Популяция инициализируется
Рассчитывается приспособленность популяции
Родители выбираются из населения.
Оператор кроссовера генерирует новый набор населения
Мутация выполняется на новом наборе популяции
Шаг 2 выполняется снова

Шаги с 3 по 6 выполняются снова и снова, пока не будет достигнута сходимость.

Также следует отметить, что оценка пригодности здесь — это количество символов, которые отличаются от символов в целевой строке по определенному индексу. Следовательно, требуется низкий показатель физической подготовки.

# Python3 program to create target string, starting from
# random string using Genetic Algorithm
import random
# Number of individuals in each generation
POPULATION_SIZE = 100
# Valid genes
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP 
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''
# Target string to be generated
TARGET = "My name is Richard"
class Individual(object):
    '''
    Class representing individual in population
    '''
def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = self.cal_fitness()
@classmethod
    def mutated_genes(self):
        '''
        create random genes for mutation
        '''
        global GENES
        gene = random.choice(GENES)
        return gene
@classmethod
    def create_gnome(self):
        '''
        create chromosome or string of genes
        '''
        global TARGET
        gnome_len = len(TARGET)
        return [self.mutated_genes() for _ in range(gnome_len)]
def mate(self, par2):
        '''
        Perform mating and produce new offspring
        '''
# chromosome for offspring
        child_chromosome = []
        for gp1, gp2 in zip(self.chromosome, par2.chromosome):
# random probability
            prob = random.random()
# if prob is less than 0.45, insert gene
            # from parent 1
            if prob < 0.45:
                child_chromosome.append(gp1)
# if prob is between 0.45 and 0.90, insert
            # gene from parent 2
            elif prob < 0.90:
                child_chromosome.append(gp2)
# otherwise insert random gene(mutate),
            # for maintaining diversity
            else:
                child_chromosome.append(self.mutated_genes())
# create new Individual(offspring) using
        # generated chromosome for offspring
        return Individual(child_chromosome)
def cal_fitness(self):
        '''
        Calculate fittness score, it is the number of
        characters in string which differ from target
        string.
        '''
        global TARGET
        fitness = 0
        for gs, gt in zip(self.chromosome, TARGET):
            if gs != gt: fitness += 1
        return fitness
# Driver code
def main():
    global POPULATION_SIZE
# current generation
    generation = 1
found = False
    population = []
# create initial population
    for _ in range(POPULATION_SIZE):
        gnome = Individual.create_gnome()
        population.append(Individual(gnome))
while not found:
# sort the population in increasing order of fitness score
        population = sorted(population, key=lambda x: x.fitness)
# if the individual having lowest fitness score ie.
        # 0 then we know that we have reached to the target
        # and break the loop
        if population[0].fitness <= 0:
            found = True
            break
# Otherwise generate new offsprings for new generation
        new_generation = []
# Perform Elitism, that mean 10% of fittest population
        # goes to the next generation
        s = int((10 * POPULATION_SIZE) / 100)
        new_generation.extend(population[:s])
# From 50% of fittest population, Individuals
        # will mate to produce offspring
        s = int((90 * POPULATION_SIZE) / 100)
        for _ in range(s):
            parent1 = random.choice(population[:50])
            parent2 = random.choice(population[:50])
            child = parent1.mate(parent2)
            new_generation.append(child)
population = new_generation
print("Generation: {}\tString: {}\tFitness: {}". \
              format(generation,
                     "".join(population[0].chromosome),
                     population[0].fitness))
generation += 1
print("Generation: {}\tString: {}\tFitness: {}". \
          format(generation,
                 "".join(population[0].chromosome),
                 population[0].fitness))
if __name__ == '__main__':
    main()

Вывод

Generation: 1 String:  j#uq dMm5 0F latd Fitness: 15
Generation: 2 String: 
?#/qSduGs eG latd Fitness: 14
Generation: 3 String: 
?#/qSduGs eG latd Fitness: 14
Generation: 4 String: 
?#/qSduGs eG latd Fitness: 14
Generation: 5 String: 7yycqbe_i5 hd }Std Fitness: 13
Generation: 6 String: 7yycqbe_i5 hd }Std Fitness: 13
Generation: 7 String: 7yycqbe_i5 hd }Std Fitness: 13
Generation: 8 String: Rd uVTcMt} Ri(}atd Fitness: 12
Generation: 9 String: ;? ufWdM!s Ri(xaRd Fitness: 11
Generation: 10 String: ;? ufWdM!s Ri(xaRd Fitness: 11
Generation: 11 String: )0}cX=e is Rirja2d Fitness: 9
Generation: 12 String: #? usWe is Ri(4a)d Fitness: 8
Generation: 13 String: #? usWe is Ri(4a)d Fitness: 8
Generation: 14 String: #? usWe is Ri(4a)d Fitness: 8
Generation: 15 String: #? usWe is Ri(4a)d Fitness: 8
Generation: 16 String: #? usWe is Ri(4a)d Fitness: 8
Generation: 17 String: ;y8n0Ee is RiK}a)d Fitness: 7
Generation: 18 String: ;y8n0Ee is RiK}a)d Fitness: 7
Generation: 19 String: MB ns4e is R-Kha)d Fitness: 6
Generation: 20 String: MB ns4e is R-Kha)d Fitness: 6
Generation: 21 String: MB ns4e is R-Kha)d Fitness: 6
Generation: 22 String: MB ns4e is R-Kha)d Fitness: 6
Generation: 23 String: My nPEe is  Jwhard Fitness: 5
Generation: 24 String: My nPEe is  Jwhard Fitness: 5
Generation: 25 String: My nPEe is  Jwhard Fitness: 5
Generation: 26 String: My nPEe is  Jwhard Fitness: 5
Generation: 27 String: My n7=e is RLKhard Fitness: 4
Generation: 28 String: My n7=e is RLKhard Fitness: 4
Generation: 29 String: My nTpe is Rizhard Fitness: 3
Generation: 30 String: My nTpe is Rizhard Fitness: 3
Generation: 31 String: My nTpe is Rizhard Fitness: 3
Generation: 32 String: My nTpe is Rizhard Fitness: 3
Generation: 33 String: My nTpe is Rizhard Fitness: 3
Generation: 34 String: My nTpe is Rizhard Fitness: 3
Generation: 35 String: My nTpe is Rizhard Fitness: 3
Generation: 36 String: My nTpe is Rizhard Fitness: 3
Generation: 37 String: My nTpe is Rizhard Fitness: 3
Generation: 38 String: My nTpe is Rizhard Fitness: 3
Generation: 39 String: My nTpe is Rizhard Fitness: 3
Generation: 40 String: My nTpe is Rizhard Fitness: 3
Generation: 41 String: My nTpe is Rizhard Fitness: 3
Generation: 42 String: My nTpe is Rizhard Fitness: 3
Generation: 43 String: My nTpe is Rizhard Fitness: 3
Generation: 44 String: My nTpe is Rizhard Fitness: 3
Generation: 45 String: My n7#e is Richard Fitness: 2
Generation: 46 String: My n7#e is Richard Fitness: 2
Generation: 47 String: My n7#e is Richard Fitness: 2
Generation: 48 String: My n7#e is Richard Fitness: 2
Generation: 49 String: My n7#e is Richard Fitness: 2
Generation: 50 String: My n7#e is Richard Fitness: 2
Generation: 51 String: My n7#e is Richard Fitness: 2
Generation: 52 String: My n7#e is Richard Fitness: 2
Generation: 53 String: My n7#e is Richard Fitness: 2
Generation: 54 String: My n7#e is Richard Fitness: 2
Generation: 55 String: My n7#e is Richard Fitness: 2
Generation: 56 String: My na#e is Richard Fitness: 1
Generation: 57 String: My na#e is Richard Fitness: 1
Generation: 58 String: My na#e is Richard Fitness: 1
Generation: 59 String: My na#e is Richard Fitness: 1
Generation: 60 String: My na#e is Richard Fitness: 1
Generation: 61 String: My na#e is Richard Fitness: 1
Generation: 62 String: My na#e is Richard Fitness: 1
Generation: 63 String: My na#e is Richard Fitness: 1
Generation: 64 String: My na#e is Richard Fitness: 1
Generation: 65 String: My na#e is Richard Fitness: 1
Generation: 66 String: My na#e is Richard Fitness: 1
Generation: 67 String: My na#e is Richard Fitness: 1
Generation: 68 String: My na#e is Richard Fitness: 1
Generation: 69 String: My na#e is Richard Fitness: 1
Generation: 70 String: My na#e is Richard Fitness: 1
Generation: 71 String: My na#e is Richard Fitness: 1
Generation: 72 String: My na#e is Richard Fitness: 1
Generation: 73 String: My na#e is Richard Fitness: 1
Generation: 74 String: My na#e is Richard Fitness: 1
Generation: 75 String: My na#e is Richard Fitness: 1
Generation: 76 String: My na#e is Richard Fitness: 1
Generation: 77 String: My na#e is Richard Fitness: 1
Generation: 78 String: My na#e is Richard Fitness: 1
Generation: 79 String: My na#e is Richard Fitness: 1
Generation: 80 String: My na#e is Richard Fitness: 1
Generation: 81 String: My na#e is Richard Fitness: 1
Generation: 82 String: My na#e is Richard Fitness: 1
Generation: 83 String: My na#e is Richard Fitness: 1
Generation: 84 String: My na#e is Richard Fitness: 1
Generation: 85 String: My na#e is Richard Fitness: 1
Generation: 86 String: My na#e is Richard Fitness: 1
Generation: 87 String: My na#e is Richard Fitness: 1
Generation: 88 String: My na#e is Richard Fitness: 1
Generation: 89 String: My na#e is Richard Fitness: 1
Generation: 90 String: My na#e is Richard Fitness: 1
Generation: 91 String: My na#e is Richard Fitness: 1
Generation: 92 String: My na#e is Richard Fitness: 1
Generation: 93 String: My na#e is Richard Fitness: 1
Generation: 94 String: My na#e is Richard Fitness: 1
Generation: 95 String: My na#e is Richard Fitness: 1
Generation: 96 String: My na#e is Richard Fitness: 1
Generation: 97 String: My na#e is Richard Fitness: 1
Generation: 98 String: My na#e is Richard Fitness: 1
Generation: 99 String: My na#e is Richard Fitness: 1
Generation: 100 String: My name is Richard Fitness: 0

Из приведенного выше видно, что потребовалось до сотни поколений, чтобы найти соответствие с целевой строкой. Весь процесс генетического алгоритма можно наблюдать на выходе программы. Видно, что все принципы естественного отбора Чарльза Дарвина были соблюдены. Для дальнейшего чтения ознакомьтесь с Генетический алгоритм и машинное обучение для программистов.

📝 Читайте эту историю позже в Журнале.

👩‍💻 Просыпайтесь каждое воскресное утро и слушайте самые примечательные новости недели в области технологий, ожидающие в вашем почтовом ящике. Читать информационный бюллетень Noteworthy in Tech.

Понимание генетического алгоритма

Вопросы по теме