Методы кроссовера в генетических алгоритмах

Question

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

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

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

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

Answer 1

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

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

Для очень простого и хорошо написанного прохождения см. 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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

Типичный многоточечный кроссовер с набором высоты

 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();            
    }

Answer 4

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

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

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

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

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

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

Answer 5

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

Как вы сказали:

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

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

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