4.6. Кодирование параметров задачи в генетическом алгоритмеВыбор исходной популяции связан с представлением параметров задачи в форме хромосом, т.е. с так называемым хромосомным представлением. Это представление определяется способом кодирования. В классическом генетическом алгоритме применяется двоичное кодирование, т.е. аллели всех генов в хромосоме равны 0 или 1. Длина хромосом зависит от условий задачи, точнее говоря - от количества точек в пространстве поиска. Генетические алгоритмы находят применение главным образом в задачах оптимизации. Пример 4.5 демонстрирует выполнение классического генетического алгоритма, аналогичного рассмотренному в примере 4.4, но для случая оптимизации функции. Для простоты примем, что это функция одной переменной. В новом примере хромосомы выступают в роли закодированной формы соответствующих фенотипов, а оптимизируется сама функция приспособленности. В примере 4.6 оптимизируется та же функция, однако внимание читателя акцентируется на другом способе кодирования хромосом для иной области определения переменной Пример 4.5 Рассмотрим очень простой пример - задачу нахождения максимума функции, заданной выражением (4.1) для целочисленной переменной Для применения генетического алгоритма необходимо прежде всего закодировать значения переменной Также очевидно, что в роли функции приспособленности будет выступать целевая функция Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (например, можно 30 раз подбросить монету); при этом
Соответствующие им фенотипы - это представленные ниже числа из интервала от 0 до 31:
По формуле (4.1) рассчитываем значения функции приспособленности для каждой хромосомы в популяции и получаем
Селекция хромосом. Методом рулетки (также, как и в примере 4.4), выбираем 6 хромосом для репродукции. Колесо рулетки представлено на рис. 4.7. Рис. 4.7. Колесо рулетки для селекции в примере 4.5. Допустим, что выбраны числа 97 26 54 13 31 88. Это означает выбор хромосом
Пусть скрещивание выполняется с вероятностью
Кроме того, допустим, что случайным образом выбрана точка скрещивания, равная 3 для хромосом Рис. 4.8. Процесс скрещивания хромосом в примере 4.5. При условии, что вероятность мутации
Для расчета значений функции приспособленности этих хромосом необходимо декодировать представляющие их двоичные последовательности и получить соответствующие им фенотипы. Обозначим их
Соответственно, значения функции приспособленности хромосом новой популяции, рассчитанные по формуле (4.1), составят
Легко заметить, что в этом случае среднее значение приспособленности возросло с 589 до 1262. Обратим внимание, что если на следующей итерации будут сформированы для скрещивания пары хромосом, например, Отметим, что при длине хромосом, равной 5 битам, пространство поиска очень мало и насчитывает всего Также следует упомянуть, что в малых популяциях часто встречаются ситуации, когда на начальном этапе несколько особей имеют значительно большие значения функции принадлежности, чем остальные особи данной популяции. Применение метода селекции на основе «колеса рулетки» позволяет в этом случае очень быстро выбрать «наилучшие» особи, иногда - на протяжении «жизни» одного поколения. Однако такое развитие событий считается нежелательным, поскольку оно становится главной причиной преждевременной сходимости алгоритма, называемой сходимостью к неоптимальному решению. По этой причине используются и другие методы селекции, отличающиеся от колеса рулетки, либо применяется масштабирование функции приспособленности (см. п. 4.8.5). Также обратим внимание на возможность реализации генетического микроалгоритма, описываемого в п. 4.8.8. Он работает с малой популяцией и вероятностями скрещивания и мутации такими, как и в примерах 4.4 и 4.5, но одновременно хорошо противостоит преждевременной сходимости. Этот факт иллюстрируется примером 4.12, в котором с помощью этого алгоритма находится минимум функции, заданной формулой (4.1). Пример 4.6 Рассмотрим задачу, аналогичную задаче из примера 4.5, т.е. будем искать максимум функции, заданной формулой (4.1), но для переменной Поиск решения сводится к просмотру пространства, состоящего из 32 точек Таким образом, мы можем воспроизвести последовательность этапов генетического алгоритма (так же, как в примере 4.5), не забывая, что конкретным хромосомам (генотипам) в данном примере соответствуют другие фенотипы. Те кодовые последовательности, которые в примере 4.5 представляли фенотипы В результате выполнения этого алгоритма будет выбрано наилучшее решение, которое представляется хромосомой Заметим, что если бы в примере 4.6 нас интересовало решение с точностью, превышающей один знак после запятой, то интервал Представим теперь задачу из примера 4.6 в более общем виде. Допустим, что ищется максимум функции
определяет необходимую и достаточную длину двоичной последовательности, требуемой для кодирования числа из интервала
Таким способом задаются фенотипы, соответствующие кодовым последовательностям с длиной
|