Пример 4.6

Рассмотрим задачу, аналогичную задаче из примера 4.5, т.е будем искать максимум функции, заданной формулой (4.1), но для переменной х, принимающей действительные значения из интервала [а, Ь], где а = 0, b = 3,1. Допустим, что нас интересует решение с точ­ностью до одного знака после запятой.

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

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

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

Заметим, что если бы в примере 4.6 нас интересовало реше­ние с точностью, превышающей один знак после запятой, то интервал [0, 3,1] необходимо было бы разбить на большее количество подин-тервалов, и для кодирования соответственно большего количества чисел потребовались более длинные хромосомы (с длиной, превы-

а 4. Ле

алгоритмы

4.7. Основная теорема о генетических алгоритмах

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

Представим теперь задачу из примера 4.6 в более общем ви­де. Допустим, что ищется максимум функции f(x^, x₂,.... х_п)> 0 для

х/ е[а/, Ь] с R; i = 1, 2.... л и требуется найти решение с точностью до

q знаков после запятой для каждой переменной х,-. В такой ситуации необходимо разбить интервал [а,-, Ь/] на (Ь,- - а,) ■ 10<? одинаковых подинтервалов. Это означает применение дискретизации с шагом г = Ю-ч. Наименьшее натуральное число т,, удовлетворяющее нера­венству

(bj-ajJ-IO" 5 2^-1 (4.4)

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

(4.5)

х,- = а,- + у,- -

Таким способом задаются фенотипы, соответствующие кодо­вым последовательностям с длиной т,. Пример 4.6 - это частный слу­чай задачи в данной постановке при условии, что / = 1 и q = 1. Выра­жение (4.5) - это следствие из простого линейного отображения ин­тервала [а* Ц на интервал [0, 2^т'- 1], где 2^т'- десятичное число, за­кодированное двоичной последовательностью длиной т,- и состав­ленной исключительно из единиц, а 0 - это, очевидно, десятичное значение двоичной последовательности длиной пц, составленной только из нулей. Обратим внимание, что если а,- = - 25, Ь,- = 25 и при­меняется шаг г - 0, 05. то согласно формуле (4.4) получаем пу - 10, а с помощью формулы (4 5) можно проверить значения фенотипов для генотипов, представленных в табл. 4.1.

Дата добавления: 2015-06-04