Генетический алгоритм

из "Новый подход к управлению капиталом "

По сравнению с этим генетический алгоритм много проще. Здесь у нас имеется одна целевая функция, которую мы пытаемся удовлетворить. Поэтому, хотя мы и говорим, что генетический алгоритм скопирован в природе, он настолько проще происходящего в природе, что вряд ли заслуживает своего названия. [c.190]
Возводим 2 в степень 0 и прибавляем 2 в следующей степени, пока не дойдем до степени, равной количеству битов минус 1 (т. е. 11, в данном случае). Если имеется, скажем, три сценарных спектра и на каждый из них мы используем длину в двенадцать битов, то длина гена каждого варианта решения есть 12 3 = 36 бит. То есть ген в данном случае — это строка из 36 двоичных битов. [c.191]
Обратите внимание, что данный способ кодирования двоичных строк подходит только для целых величин. Но мы можем приспособить его и для чисел с плавающей запятой с помощью некоторого постоянного делителя. Так, если мы выберем постоянный делитель равным, скажем, 1000, то сможем представлять числа от 0/1000 до 4095/1000, или от 0 до 4,095, с точностью до 0,001. [c.192]
Теперь нам понадобится процедура преобразования вариантов решений в кодовые двоичные строки и обратно. [c.192]
Инициализация. Требуется исходная популяция - популяция вариантов решений. Битовые строки этого первого поколения закодированы случайным образом. Более высокая численность популяции повышает вероятность того, что мы найдем хорошее решение, но при более высокой численности требуется большее время обработки. [c.192]
Ранжирование по приспособленности. Теперь ранжируются значения целевой функции. Для этого сначала выявляется наименьшая целевая функция всех вариантов решений, и эта величина вычитается из всех вариантов решений. Полученные результаты суммируются. Разделив на эту сумму результаты вычитания из каждой целевой функции наименьшей, получают коэффициенты приспособленности, содержащиеся в интервале от 0 до 1. Отсюда сумма всех коэффициентов приспособленности будет равна 1,0. [c.192]
И так продолжают далее, пока верхняя граница последнего варианта не окажется на 1,0. [c.193]
Далее генерируются два случайных числа в интервале от О до 1, нужные для определения на основе предыдущей схемы отбора, какими будут два родителя. Теперь для каждого варианта решения следующего поколения нужно выбрать двух родителей. [c.193]
Кроссовер. Последовательно формируется каждый бит ребенка — нового варианта решения популяции. Начинают с копирования первого бита первого родителя в первый бит ребенка. Одновременно с этим вы должны генерировать случайное число. Если это случайное число оказывается меньше или равно вероятности кроссовера, деленной на длину гена, то переключаемся на копирование битов от другого родителя. Так, если у нас три сценарных спектра с двенадцатью битами для каждой переменной, то длина гена равна тридцати шести. Если используемая нами вероятность кроссовера равна 0,6, то для переключения на копирование кода другого родителя в последующих битах, генерируемое при каждом бите случайное число должно быть меньше 0,6/36, или 0,01667. Это продолжается до тех пор, пока все биты не будут скопированы в коде ребенка. Данную операцию нужно проделать для всех новых членов популяции. [c.193]
Обычно вероятности кроссовера находятся в интервале от 0,6 до 0,9. Так, вероятность кроссовера 0,9 означает, что шансы возникновения кроссовера у ребенка будут равны 90%, в среднем то есть 10% шансов будет за то, что ребенок будет точной копией одного из родителей. [c.193]
Для простоты в этом примере у нас будет только одна переменная, то есть каждый член популяции будет нести двоичный код только для этой одной переменной. [c.194]
Присмотревшись к целевой функции, легко заметить, что оптимальная величина X равна 15, что приводит к значению Y, равному 1500. Какими бы редкими ни были случаи, когда доведется узнать оптимальные значения переменных, в этом простом примере нам будет полезно знать оптимум, чтобы можно было проследить, как к нему нас приведет алгоритм. [c.194]
Теперь путем случайного отбора по приспособленности определяются Родители 1 и 3 первого поколения для Индивидуума 1 второго поколения (заметьте, что Родитель 2 с приспособленностью 0 погиб и не передаст далее своих генетических свойств). Предположим, что случайный кроссовер происходит после четвертого бита. Поэтому, наследуя первые четыре бита от Индивидуума 1 и последний бит от Индивидуума 3 первого поколения, Индивидуум 1 во втором поколении принимает вид 01011. [c.195]
Предположим, что Индивидууму 2 второго поколения выпадают те же родители кроссовер происходит только после первого и третьего битов. То есть он наследует бит 0 от Индивидуума 1 первого поколения, биты Ив качестве второго и третьего битов от третьего индивидуума первого поколения и два последних бита от первого индивидуума первого поколения. В результате этого генетический код второго индивидуума второго поколения оказывается равным 01110. [c.195]
Предположим далее, что в оба родителя третьего индивидуума второго поколения попадает Индивидуум 1. То есть третий индивидуум во втором поколении получает точно такой же генетический материал, как у первого индивидуума первого поколения, а именно 01010. [c.195]
Обратите внимание, насколько во втором поколении поднялось, или эволюционировало, среднее значение Y. [c.196]

Вернуться к основной статье