4.6. Кодирование параметров задачи в генетическом алгоритме

Выбор исходной популяции связан с представлением параметров задачи в форме хромосом, т.е. с так называемым хромосомным представлением. Это представление определяется способом кодирования. В классическом генетическом алгоритме применяется двоичное кодирование, т.е. аллели всех генов в хромосоме равны 0 или 1. Длина хромосом зависит от условий задачи, точнее говоря - от количества точек в пространстве поиска.

Генетические алгоритмы находят применение главным образом в задачах оптимизации. Пример 4.5 демонстрирует выполнение классического генетического алгоритма, аналогичного рассмотренному в примере 4.4, но для случая оптимизации функции. Для простоты примем, что это функция одной переменной. В новом примере хромосомы выступают в роли закодированной формы соответствующих фенотипов, а оптимизируется сама функция приспособленности. В примере 4.6 оптимизируется та же функция, однако внимание читателя акцентируется на другом способе кодирования хромосом для иной области определения переменной .

Пример 4.5

Рассмотрим очень простой пример - задачу нахождения максимума функции, заданной выражением (4.1) для целочисленной переменной , принимающей значения от 0 до 31.

Для применения генетического алгоритма необходимо прежде всего закодировать значения переменной  в виде двоичных последовательностей. Очевидно, что целые числа из интервала  можно представить последовательностями нулей и единиц, используя их представление в двоичной системе счисления. Число 0 при этом записывается как 00000, а число 31 - как 11111. В данном случае хромосомы приобретают вид двоичных последовательностей, состоящих из 5 битов, т.е. цепочками длиной 5 (аналогично примеру 4.1).

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

Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (например, можно 30 раз подбросить монету); при этом . Допустим, что выбраны хромосомы

            

                       

                       

Соответствующие им фенотипы - это представленные ниже числа из интервала от 0 до 31:

                    

                     

                     

По формуле (4.1) рассчитываем значения функции приспособленности для каждой хромосомы в популяции и получаем

           

             

             

Селекция хромосом. Методом рулетки (также, как и в примере 4.4), выбираем 6 хромосом для репродукции. Колесо рулетки представлено на рис. 4.7.

Рис. 4.7. Колесо рулетки для селекции в примере 4.5.

Допустим, что выбраны числа

97        26        54        13        31        88.

Это означает выбор хромосом

                         

Пусть скрещивание выполняется с вероятностью . Допустим, что для скрещивания сформированы пары

 и        и        и

Кроме того, допустим, что случайным образом выбрана точка скрещивания, равная 3 для хромосом  и , а также точка скрещивания, равная 2 для хромосом  и  (рис.4.8).

Рис. 4.8. Процесс скрещивания хромосом в примере 4.5.

При условии, что вероятность мутации , в новую популяцию включаются хромосомы

                       

                      

                       .

Для расчета значений функции приспособленности этих хромосом необходимо декодировать представляющие их двоичные последовательности и получить соответствующие им фенотипы. Обозначим их . В результате декодирования получаем числа (из интервала от 0 до 31)

                   

                  

                    .

Соответственно, значения функции приспособленности хромосом новой популяции, рассчитанные по формуле (4.1), составят

                      

                    

                       .

Легко заметить, что в этом случае среднее значение приспособленности возросло с 589 до 1262.

Обратим внимание, что если на следующей итерации будут сформированы для скрещивания пары хромосом, например,  и ,  и  или  и  с точкой скрещивания 2 или 3, то среди прочих будет получена хромосома  с фенотипом, равным числу 31, при котором оптимизируемая функция достигает своего максимума. Значение функции приспособленности для этой хромосомы оказывается наибольшим и составляет 1923. Если такое сочетание пар в данной итерации не произойдет, то можно будет ожидать образования хромосомы с наибольшим значением функции приспособленности на следующих итерациях. Хромосома  могла быть получена и на текущей итерации в случае формирования для скрещивания пары  и  с точкой скрещивания 3.

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

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

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

Пример 4.6

Рассмотрим задачу, аналогичную задаче из примера 4.5, т.е. будем искать максимум функции, заданной формулой (4.1), но для переменной , принимающей действительные значения из интервала , где , . Допустим, что нас интересует решение с точностью до одного знака после запятой.

Поиск решения сводится к просмотру пространства, состоящего из 32 точек . Эти точки (фенотипы) можно представить в виде хромосом (генотипов), если использовать бинарные пятизвенные цепочки, поскольку с помощью 5 битов можно получить  различных кодовых комбинации. Следовательно, можно использовать такое же множество кодовых последовательностей, как и в примере 4.5, причем хромосома  будет соответствовать числу 0,0, хромосома  - числу 0,1 и т.д., вплоть до хромосомы , соответствующей числу 3,1.

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

В результате выполнения этого алгоритма будет выбрано наилучшее решение, которое представляется хромосомой  со значением фенотипа 3,1. Функция приспособленности этой хромосомы равна 20,22; это максимально возможное значение.

Заметим, что если бы в примере 4.6 нас интересовало решение с точностью, превышающей один знак после запятой, то интервал  необходимо было бы разбить на большее количество подинтервалов, и для кодирования соответственно большего количества чисел потребовались более длинные хромосомы (с длиной, превышающей 5 битов). Аналогично, расширение области определения переменной  также потребует применения более длинных хромосом. Из этих наблюдений можно сделать вывод, что длина хромосом зависит от ширины области определения  и от требуемой точности решения.

Представим теперь задачу из примера 4.6 в более общем виде. Допустим, что ищется максимум функции  для ;  и требуется найти решение с точностью до  знаков после запятой для каждой переменной . В такой ситуации необходимо разбить интервал  на  одинаковых подинтервалов. Это означает применение дискретизации с шагом . Наименьшее натуральное число , удовлетворяющее неравенству

                       (4.4)

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

.                (4.5)

Таким способом задаются фенотипы, соответствующие кодовым последовательностям с длиной . Пример 4.6 - это частный случай задачи в данной постановке при условии, что  и . Выражение (4.5) - это следствие из простого линейного отображения интервала  на интервал , где  - десятичное число, закодированное двоичной последовательностью длиной  и составленной исключительно из единиц, а 0 - это, очевидно, десятичное значение двоичной последовательности длиной , составленной только из нулей. Обратим внимание, что если ,  и применяется шаг , то согласно формуле (4.4) получаем , а с помощью формулы (4.5) можно проверить значения фенотипов для генотипов, представленных в табл. 4.1.