Автоматизированное проектирование. Норенков И.П. - 118 стр.

 5@!"! 4                             %!#*%!#&F*:,$*    $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

     O"#++#($" (+%"$A'()*'$). Кроссовер, иногда называемый кроссинговером, заключается в пере-
даче участков генов от родителей к потомкам. При простом (одноточечном) кроссовере хромосомы
родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва
равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как
это показано в табл. 4.3, где разрыв подразумевается между пятым и шестым локусами.
                                                                          M:BD+=: 4.3

                  Хромосома                                    Гены

                   родителя A                f    a   c    d     g    k     v     e

                   родителя B                a    b   c    d     e    f     g     h

                   потомка *                 f    a   c    d     g    f     g     h

                   потомка D                 a    b   c    d     e    k     v     e

      L7&)=''. Оператор мутации выполняется с некоторой вероятностью Sм, т.е. с вероятностью Sм
происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области оп-
ределения гена. Именно благодаря мутациям расширяется область генетического поиска.
      :$4$%='9. После каждого акта генерации пары потомков в новое поколение включается лучший
экземпляр пары.
      Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным N.
Количество повторений G внешнего цикла чаще всего определяется автоматически по появлению
признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита ма-
шинного времени.
      %:?049+504,-+ @.0.-+A.,7+6 43.8:-4849. Возможны отклонения от представленной выше в
простом генетическом алгоритме схемы вычислений.
      O"#++#($". Во-первых, допустимы схемы многоточечного кроссовера.
      Во-вторых, отметим ситуации, когда на состав аллелей наложены некоторые дополнительные
условия. Например, пусть в задаче разбиения графа число вершин в подграфах C1 и C2 должно быть
N1 и N2 и пусть k-й аллель, равный 1, означает, что вершина k попадает в C1, если же k-й аллель равен
0, то в C2. Очевидно, что число единиц в хромосоме должно равняться N1, число нулей — N2. Тогда
при рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в пра-
вом участке (от другого родителя) нужно согласовать число единиц с N1 тем или иным способом.
      Один из способов — метод PMX (Partially Matched Crossover). Для иллюстрации PMX рассмот-
рим пример двухточечного кроссовера в задаче, когда в хромосоме должны присутствовать, причем
только по одному разу, все значения генов из заданного набора. Пусть в примере этот набор включа-
ет числа от 1 до 9.
      В табл. 4.4 первые две строки представ-                                              M:BD+=: 4.4
ляют родительские хромосомы. Третья стро-         )    2       3     4   5       6    7     8    9
ка содержит хромосому одного из потомков,
                                                  3    7       )     9   2       4    8     6    5
сгенерированного в результате применения
двухточечного кроссовера (после второго и         )    2       )     9   2       6    7     8    9
пятого локусов). Полученная хромосома не          )    2       3     9   5       6    7     8    4
относится к числу допустимых, так как в
ней значения генов 1, 2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка по-
казывает результат применения РМХ. В этом методе выделяются сопряженные пары аллелей в одно-
именных локусах одной из рекомбинируемых частей. В нашем примере это пары (3 и 1), (4 и 9), (5 и
2). Хромосома потомка просматривается слева направо; если повторно встречается некоторое значе-
ние, оно заменяется на сопряженное значение. Так, в примере в локусах 3, 5 и 9 повторно встречаю-

 &.+.)$(*),$" . !"#$%!#&'&($"!))$*          +($*,#&($"!)&*                                    118