Флэш Потрошитель этот | тот | 1.0

Пишет makc3d:
Давным давно в далёкой галактике Балаклаве, как раз перед тем, как уехать с ITSea 2011, я с Ростом пытался убедить знающих людей сделать доклад о генетических алгоритмах, однако все они отказались под предлогом того, что в этой теме слишком много математики. Разумеется, объяснить принципы генетических алгоритмов вполне возможно и без математики - как говорится, на пальцах - что я и попытаюсь сделать в этом посте.

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

Давайте рассмотрим этот процесс на примере решения следующей простой задачи: в начале координат стоит пушка и стреляет под углом 45° снарядом с начальной скоростью v; т.е. уравнения движения снаряда имеют знакомый из школьного курса вид x = vt/√2 и y = vt/√2 - gt²/2. Необходимо найти такое значение v, при котором снаряд упадёт на заданном расстоянии. Эта задача легко решается в явном виде, но в целях этого поста представим себя очень ленивыми математиками и используем генетический алгоритм.

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

Подытожим наш алгоритм:

// виртуальная "особь"
class Creature {
public var gene:Object;
public var fitness:Number;
...
// создаём популяцию из случайных особей
population = new Vector.<Creature> ();
...
// в каждой итерации:
// устанавливаем фитнес равным модулю высоты траектории над целью
for each (var c:Creature in population) c.fitness = ...
// сортируем популяцию по фитнесу
population.sort (...);
// заменяем особь-лузера на комбинацию годных особей,
// не забываем вносить случайные мутации
population [...].gene = 0.5 * (
Number (population [...].gene) +
Number (population [...].gene)
) + mutationRate * (Math.random () - Math.random ());


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