назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42]


30

Обратите внимание, что данный способ кодирования двоичных строк подходит только для целых величин. Но мы можем приспособить его и для чисел с плавающей запятой с помощью некоторого постоянного делителя. Так, если мы выберем постоянный делитель равным, скажем, 1000, то сможем представлять числа от 0/1000 до 4095/1000, или от О до 4,095, с точностью до 0,001.

Теперь нам понадобится процедура преобразования вариантов рещений в кодовые двоичные строки и обратно.

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

Задание целевой функции. Битовые строки декодируются в свои десятичные эквиваленты, которые используются для задания целевой функции. (Например, при наличии двух сценарных спектров целевая функция дает нам величину координаты Z, или высоту трехмерного изображения, в предположении, что величины / соответствующих сценарных спектров - это координаты X и Y.) Это проделывается для всех вариантов решений, и значения целевой функции для них сохраняются. (Важно: значения целевой функции должны быть неотрицательными!)

Репродуцирование

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

Случайный отбор по приспособленности. Теперь ранжированные целевые функции упорядочиваются следующим образом. Если, скажем, у первой целевой функции коэффициент приспособленности равен 0,05, у второй - 0,1, а у третьей - 0,08, то они

следующим образом включаются в схему отбора (образуются интервалы):

первый вариант О - 0,05;

второй вариант 0,05 - 0,15;

третий вариант 0,15 - 0,23.

И так продолжают далее, пока верхняя граница последнего варианта не окажется на 1,0.

Далее генерируются два случайных числа в интервале от О до 1, нужные для определения на основе предыдущей схемы отбора, какими будут два родителя. Теперь для каждого варианта решения следующего поколения нужно выбрать двух родителей.

Кроссовер*. Последовательно формируется каждый бит ребенка - нового варианта решения популяции. Начинают с копирования первого бита первого родителя в первый бит ребенка. Одновременно с этим вы должны генерировать случайное число. Если это случайное число оказывается меньше или равно вероятности кроссовера, деленной на длину гена, то переключаемся на копирование битов от другого родителя. Так, если у нас три сценарных спектра с двенадцатью битами для каждой переменной, то длина гена равна тридцати шести. Если используемая нами вероятность кроссовера равна 0,6, то для переключения на копирование кода другого родителя в последующих битах, генерируемое при каждом бите случайное число должно быть меньше 0,6/36, или 0,01667. Это продолжается до тех пор, пока все биты не будут скопированы в коде ребенка. Данную операцию нужно проделать для всех новых членов популяции.

Обычно вероятности кроссовера находятся в интервале от 0,6 до 0,9. Так, вероятность кроссовера 0,9 означает, что шансы возникновения кроссовера у ребенка будут равны 90% , в среднем; то есть 10% шансов будет за то, что ребенок будет точной копией одного из родителей.

Мутация. Попутно с копированием каждого бита родителя в бит ребенка генерируется второе случайное число. Если это

* Принятый в биологии термин, обозначающий генотип, образующийся в результате перекрестной рекомбинации. - Прим. пер.



случайное число оказывается меньше или равно вероятности мутации, то данный бит инвертируется. То есть, бит, бывший О у родителя, становится 1 у ребенка, и наоборот. Мутация помогает сохранить разнообразие в популяции. Вероятность мутации обычно должна быть невелика (= 0,001), иначе алгоритм вырождается в случайный поиск. Однако по мере приближения алгоритма к оптимальному варианту, мутация приобретает все большее значение, ибо кроссовер не может сохранить генетическое разнообразие в столь локализованном объеме {п + 1)-мерного пространства.

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

Для примера рассмотрим реализацию генетического алгоритма с целевой функцией вида:

Y= 1500-(Х-15)2

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

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

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

Первое поколение

Индив. №

Двоичн. X

Коэфф. Приспос.

01010

1475

0,4751

00000

1275

01101

1496

0,5249

Теперь путем случайного отбора по приспособленности определяются Родители 1 и 3 первого поколения для Индивидуума 1 второго поколения (заметьте, что Родитель 2 с приспособленностью О погиб и не передаст далее своих генетических свойств). Предположим, что случайный кроссовер происходит после четвертого бита. Поэтому, наследуя первые четыре бита от Индивидуума 1 и последний бит от Индивидуума 3 первого поколения. Индивидуум 1 во втором поколении принимает вид 01011.

Предположим, что Индивидууму 2 второго поколения выпадают те же родители; кроссовер происходит только после первого и третьего битов. То есть он наследует бит О от Индивидуума 1 первого поколения, биты 11 в качестве второго и третьего битов от третьего индивидуума первого поколения и два последних бита от первого индивидуума первого поколения. В результате этого генетический код второго индивидуума второго поколения оказывается равным OHIO.

Предположим далее, что в оба родителя третьего индивидуума второго поколения попадает Индивидуум 1. То есть третий индивидуум во втором поколении получает точно такой же генетический материал, как у первого индивидуума первого поколения, а именно 01010.

Второе Поколение

Индивидуум №

Двоичный X

И 14 10

01011 01110 01010



Пусть далее путем случайной мутации изменился третий бит первого индивидуума. В результате для задания целевой функции имеем следующие данные:

Второе Поколение

Индив. №

Двоичн. X

Коэфф. Присное.

01110

1500

0,5102

01110

1499

0,4898

01010

1475

Обратите внимание, насколько во втором поколении поднялось, или эволюционировало, среднее значение У.

Важные замечания

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

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

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

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

Как только вы нашли оптимальный портфель, то есть нашли значения для / разделите эти значения на наибольший проифыш по соответствующим сценарным спектрам и определите /$ для этого конкретного сценарного спекфа. Это именно то, что мы делали в первой главе для того, чтобы определить, сколькими контрактами торговать в оптимальном портфеле.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42]