Олег Макаренко (olegmakarenko.ru) wrote,
Олег Макаренко
olegmakarenko.ru

Categories:

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

Задача из реальной жизни. Маленький пузатый гоблин хочет добраться из точки А в точку Б. Как ему выбрать самый лучший маршрут?

Программистам известны тысячи способов решения этой задачи. Можно, например, квадратно-гнездовым способом перебрать все возможные варианты. Заставить гоблина бегать из точки А в точку Б разными маршрутами, и каждый раз смотреть с секундомером, в какое время он уложится. Этот способ, конечно, требует огромного количества времени, однако на маленьких картах он таки работает.

Второй способ. Засеять карту сухой травой. Поджечь точку А. Смотреть, как кольцо пожара будет расширяться и увидеть, каким маршрутом огонь придёт в точку Б.

Третий способ. Подвести к точке А плюс пять вольт, а к точке Б, наоборот, минус пять вольт. Посмотреть, какой маршрут выберет электрический ток.

Короче, решений много. Для справки: эта задача — выбор оптимального пути движения для монстров — и по сей день ни разу не решена создателями компьютерных игр (достаточно быстрого алгоритма не придумано). Ресурсов процессора на обсчёт маршрутов тратится очень много, а монстры всё равно нередко умудряются запутаться «в трёх соснах».

Так вот. Одним из хитровыдуманных способов поиска лучшего маршрута является «генетический алгоритм», подсмотренный у «природы».

Работает генетический алгоритм примерно так (я сильно упрощаю, конечно же). Выбираем наугад двадцать маршрутов. Облучаем эти маршруты радиацией, а потом скрещиваем между собой, чтобы они дали потомство. Подвергаем выводок наплодившихся маршрутов «естественному обору»: умерщвляем неудачные маршруты, а удачным разрешаем поскрещиваться между собой ещё раз. Через несколько поколений имеем качественные, короткие маршруты. Причём — обратите особое внимание — при весьма скромных затратах процессорного времени на обсчёт.

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

Теперь плавно переходим на спор эволюционистов с креационистами. Казалось бы: эволюционисты гордо потрясают генетическими алгоритмами и пляшут от радости. Это победа: идеи Дарвина не просто моделируются на компьютере, но и помогают решать реальные задачи из жизни. Ставим эволюционистам сочный плюс?

Не будем спешить.

Влезем сначала в шкуру Б-га. Допустим, у нас есть задача: создать собаку. Не абы какого четвероногого уродца, а сильное, «конкурентоспособное» и клыкастое существо, которому будет уютно в лесах средней полосы. И в тундре. И в саванне. И в джунглях…

Понимаете проблему, да? Побреем собаку налысо — будет мёрзнуть зимой. Сделаем густую длинную шерсть — будет страдать от блох и застревать в кустарнике. Научим отращивать шерсть зимой и линять летом? Тоже совсем не панацея. Чтобы определить, какой должна быть собака нашей мечты, нам нужно сначала понять, где она будет жить. А где конкретно будет жить наша собака мы не знаем.

Решение задачи, впрочем, очевидно. Закладываем в собаку кучу «плавающих» параметров. Длину шерсти, например, ставим от нуля до тридцати сантиметров. Рост — от пятнадцати сантиметров до полутора метров. Толщина костей, форма ушей, объём мускулатуры… список получится внушительным.

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

Собака живёт в лесу и питается крольчатиной? Отлично. Через двести поколений станет тощей и быстрой. Потомки нашей собаки переселились в горы? Нет проблем. Генетический алгоритм снова вступит в действие. Собака отрастит себе толстую защитную шкуру и разовьёт тонкий нюх, позволяющий находить под слоем снега заплутавших лыжников.

Собственно, всё это мы наблюдаем сейчас, в реальном времени. Породы собак появляются и исчезают, бабочки меняют свой окрас от поколения к поколению, тли-монофаги становятся стереофагами. Могучий генетический алгоритм бдит за конкурентоспособностью животных. Красивая, экспериментально подтвержаемая, связная и логичная картина мира.

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

1. Если Б-г заложил в собаку определённые «ползунки» (примерно как на картинке к посту), значит за пределы этих ползунков собака выскочить не может. Таким образом, пытаясь вывести с помощью селекции, например, самую длиннохвостую собаку, мы довольно быстро упрёмся в предел длины хвоста. У потомков этой собаки хвост расти дальше уже не будет.

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

3. Если Б-г чего-то не предусмотрел на пульте управления собакой, «само собой» это что-то не появится. Собака может меняться не как хочет, а только в границах, заложенных Б-гом. Таким образом, собака не превратиться в кошку никогда, сколько её ни учи мяукать.

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

Подступаемся к самому весёлому. Насколько мне известно, опыты по всем этим четырём пунктам уже неоднократно ставились. В общем, выясняется, что все четыре следствия имеют место быть. Границы возможностей у селекции и в самом деле существуют, эволюция и в самом деле работает довольно оперативно, а любимый мной Шапошников даже сумел показать своим знаменитым экспериментом с тлями обратимость эволюции. Единственная проблема с третьим пунктом: на предложение «покажите превращение собаки в кошку» эволюционисты ехидно предлагают обратиться к ним через миллион лет.

Подвожу итог

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

Вместе с тем, факт использования генетического алгоритма в компьютерах вселяет в моё сердце гордость за программистов человечества, которые сумели приручить один из инструментов Б-га.
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 405 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →