Блог

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

Мне еще предстоит увидеть фактический код реализованного генетического алгоритма для реальных отраслевых приложений, но мне трудно представить, что этого достаточно для работы с простыми типами данных.

Я всегда представлял, что различные этапы генетических алгоритмов будут выполняться на сложных объектах, включающих сложные математические операции, а не просто заменять некоторые биты в отдельных целых числах.

Даже Википедия просто перечисляет эти виды операций для кроссовера.

Я упускаю что-то важное или такие методы кроссовера действительно используются?

Используется несколько вещей… хотя необходимость параллельности и нескольких поколений (а иногда и большой совокупности) приводит к использованию методов, которые хорошо работают…

Еще один момент, который следует иметь в виду, заключается в том, что «замена некоторых битов» при правильном моделировании напоминает простую и довольно точную версию того, что происходит естественным образом (рекомбинация генов, мутации)…

Очень простое и красиво написанное пошаговое руководство см. http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world /

Для получения дополнительной информации см.

• http://www.codeproject.com/KB/recipes/btl_ga.aspx
• http://www.codeproject.com/KB/recipes/genetics_dot_net.aspx
• http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx
• http://www.c-sharpcorner.com/UploadFile/mgold/GeneticAlgorithm12032005044205AM/GeneticAlgorithm.aspx

Я всегда представлял, что различные этапы генетических алгоритмов будут выполняться на сложных объектах, включающих сложные математические операции, а не просто заменять некоторые биты в отдельных целых числах.

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

Так что же происходит? Ну, обычно программист (или ученый) идентифицирует различные параметры в конфигурации, а затем сопоставляет эти параметры с целыми числами / числами с плавающей точкой. Это ограничивает направления, в которых алгоритм может исследовать, но это единственный реалистичный метод получения каких-либо результатов.

Давайте посмотрим на эволюцию антенны. Вы могли бы выполнить сложное моделирование с помощью генетического алгоритма, перестраивающего молекулы меди, но это было бы очень сложно и заняло бы целую вечность. Вместо этого вы бы определили «параметры» антенны. Большинство антенн построены из проводов определенной длины, согнутых в определенных местах, чтобы максимизировать их зону покрытия. Таким образом, вы могли бы определить пару параметров: количество пусковых проводов, длины сечений, угол изгибов. Все это легко представлено в виде целых чисел, и поэтому генетическому алгоритму легко манипулировать. Полученные манипуляции могут быть переданы в «Симулятор антенны», чтобы увидеть, насколько хорошо он принимает сигналы.

Короче говоря, когда вы говорите:

Мне трудно представить, что этого достаточно для работы с простыми типами данных.

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

В генетических алгоритмах обычно используется обмен битами некоторого разнообразия.

Как вы уже сказали:

Я всегда представлял, что различные этапы генетических алгоритмов будут выполняться на сложных объектах, включающих сложные математические операции

Я думаю, вы ищете генетическое программирование, где хромосома описывает программу, в этом случае вы сможете сделать больше с операторами при применении кроссовера.

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

Для разных приложений требуются разные encondigs. Цель, безусловно, состоит в том, чтобы найти наиболее эффективную кодировку, и достаточно часто простые кодировки лучше подходят. Так, например, задача планирования работы магазина может быть представлена в виде списка перестановок, которые представляют порядок выполнения заданий на разных машинах (так называемая матрица последовательности заданий). Однако он также может быть представлен в виде списка правил приоритета, которые строят расписание. Проблема коммивояжера или проблема квадратичного присвоения обычно представлена одной перестановкой, которая обозначает тур в одном случае или задание в другом случае. Оптимизация параметров имитационной модели или нахождение корня сложной математической функции обычно представлены вектором реальных значений.

Для всех этих все еще существуют простые типы операторов кроссовера и мутации. Для перестановки это, например, OX, ERX, CX, PMX, UBX, OBX и многие другие. Если вы можете объединить несколько простых представлений для представления решения вашей сложной проблемы, вы можете повторно использовать эти операции и применять их к каждому компоненту по отдельности.

Для эффективной работы кроссовера важно, чтобы выполнялось несколько свойств:

• Кроссовер должен сохранять те части, которые похожи в обоих
• Для тех частей, которые не похожи, кроссовер не должен вводить элемент, который еще не является частью одного из родителей
• Пересечение двух решений должно, по возможности, привести к возможному решению

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

Если вы хотите поэкспериментировать с различными операторами и задачами, у нас есть хорошее программное обеспечение, управляемое графическим интерфейсом: HeuristicLab.

Обычно используется простая замена битов. Ключевым моментом является кодировка, которая используется в каждом решении-кандидате. Решения должны быть закодированы таким образом, чтобы в новом потомстве была минимальная ошибка или ее не было. Любая ошибка потребует, чтобы алгоритм предоставил исправление, что приведет к увеличению времени обработки.

В качестве примера я разработал генератор университетского расписания на C #, который использует целочисленную кодировку для представления временных интервалов, доступных в каждый день. Это представление позволяет использовать очень эффективный одноточечный или многоточечный оператор кроссовера, который использует функцию LINQ intersect для объединения родительских элементов.

Типичный многоточечный кроссовер с подъемом на холм

  public List<TimeTable> CrossOver(List<TimeTable> parents) // Multipoint crossover
    {                                   
        var baby1 = new TimeTable {Schedule = new List<string>(), Fitness = 0};
        var baby2 = new TimeTable {Schedule = new List<string>(), Fitness = 0};

        for (var gen = 0; gen < parents[0].Schedule.Count; gen  )
        {               
            if (rnd.NextDouble() < (double) CrossOverProb)
            {                      
                baby2.Schedule.Add(parents[0].Schedule[gen]);
                baby1.Schedule.Add(parents[1].Schedule[gen]);                                                          
            }
            else
            {
                baby1.Schedule.Add(parents[0].Schedule[gen]);
                baby2.Schedule.Add(parents[1].Schedule[gen]);
            }
        }

        CalculateFitness(ref baby1);
        CalculateFitness(ref baby2);  

        // allow hill-climbing
        parents.Add(baby1);
        parents.Add(baby2);

        return parents.OrderByDescending(i => i.Fitness).Take(2).ToList();            
    }