Наука ryder
1 532

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

Статья несет более информативный характер, поэтому если вы прочли название и у вас не возник вопрос "Че это ваще такое", то для вас полезными скорее всего могут быть только ссылки в конце.

В закладки

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

В первую очередь интересен последний пункт. Многие, думаю, подметили, что технологии нередко черпают вдохновление у природы. Самолеты - это гигантские металические птицы. Водолазы используют ласты, подобные плавникам морских жителей. И этому есть вполне логическое объяснение: люди на Земле существуют порядка 150 тыс. лет, в то время, как эволюция идет уверенной поступью в будущее уже четвертый миллиард лет.

Лапки гекконов - удивительный механизм, схожих с которым не найти. Уже сейчас инженеры мира создают прототипы роботов, способных карабкаться по вертикальным поверхностям, подражая геккону.

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

Что же такое генетический алгоритм и какое он вообще имеет отношение к играм?

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

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

Нагло сворованная картинка, которая очень простыми словами объясняет работу алгоритма

Поколение - выборка экземпляров, которые существуют одновременно, и соревнуются друг с другом за виживание путем решения поставленной задачи (ну или попыток решения).

Характеристика - один из параметров, которыми обладает образец. Если есть некоторая функция, которая выполняется для достижения цели, то характеристики являются переменными, которые приходят в эту функцию (извините за программирование).

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

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

Кроссинговер - механизм, который наравне с мутацией "двигает прогресс". Может быть также назван скрещиванием. Обычно используется перед мутацией, иногда вместо. Суть состоит в обмене некоторыми характеристиками между образцами. Решает одну из главных проблем алгоритма - отсутствие разнообразия.

Еще одна сворованная картинка, которая показывает последовательность этапов алгоритма

Что это все за слова и как они связаны друг с другом?

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

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

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

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

Довольно круто этот алгоритм задействован здесь. Неплохая иллюстрация алгоритма в игре.

Итак, я прочитал все это, но для меня не было ничего нового.

Техническую часть алгоритма можно подробнее изучить вот тут.

Намного подробнее и с разноцветными картинками об алгоритме здесь.

Дублирую ссылку о прохождении игр алгоритмом, которая где-то была в статье.

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

Ну и поскольку ссылок уже достаточно, то я кину еще одну, которая тоже относится к прохождения игр алгоритмом.

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

#long

Материал опубликован пользователем. Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "ryder", "author_type": "self", "tags": ["long"], "comments": 23, "likes": 58, "favorites": 33, "is_advertisement": false, "subsite_label": "science", "id": 37511, "is_wide": false, "is_ugc": true, "date": "Wed, 23 Jan 2019 20:26:35 +0300" }
{ "id": 37511, "author_id": 62420, "diff_limit": 1000, "urls": {"diff":"\/comments\/37511\/get","add":"\/comments\/37511\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/37511"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 112327 }

23 комментария 23 комм.

Популярные

По порядку

Написать комментарий...
5

Хочу добавить\подправить:
1. Генетический алгоритм используется в тех задачах, где нет возможности найти решение за адекватный промежуток времени. Он не находит наилучшее решение — он пытается выдать близкое к нему, но гарантии никакой нет.
2. Сравнение самолётов с птицами в данном контексте не совсем корректное. Классический генетический алгоритм симулирует сами процессы эволюции, а не пародиует какое-либо животное (но есть и "животноподобные", которые черпали вдохновение с генетического, к примеру: https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D1%80%D0%B0%D0%B2%D1%8C%D0%B8%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC)
3.
Решает одну из главных проблем алгоритма - отсутствие разнообразия.

Слишком странно звучит. Неотъемлемая часть алгоритма решает проблему алгоритма.. Это как "число 4 в утверждении "4х = 8 при х = 2" решает одну из главных проблем утверждения — некорректность"
4. Имхо. Довольно странно было описывать "характеристику" образца. Опять таки, в классическом генетическом алгоритме "характеристика" образца есть его геном. А геном можно представить в виде нулей и единиц. Но сами по себе эти 0 и 1 ничего не стоят, "качество" генома определяет функция приспособленности, которую Вы либо упомянули достаточно косвенно, либо не упомянули в принципе. Функция приспособленности берёт геном и преобразовывает его в вариант решения конкретной задачи, на выходе выдавая число, которое описывает насколько решение было хорошим. Именно результаты этой функции сравниваются для различных геномов во время селекции. *тут было бы не лишним привести пример, но тогда размер моего коммента будет почти таким же как статья:)*
5. Было бы довольно занятным привести примеры успешного практического использования алгоритма. Например антенны, форма которых была создана геналгоритмом, рекомендованные для установки на спутник. Но было сказано о нейронных сетях и их применениях в играх, хотя сети имеют довольно косвенное отношение к самому принципу геналгоритма.
6.
Тут сразу можно подметить один из главных минусов как генетического, так и эвристического алгоритма - как только он пошел по определенному вектору, сместить его довольно трудно.

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

Ответить
0

2. Хотел подметить, что довольно часто люди находят решение проблем в природе, привел довольно очевидные ситуации
3. Я почему-то был уверен, что в некоторых вариациях действует только мутация, без скрещивания. В первом варианте статьи даже написано, что мутация - альтернатива скрещивания, потом убрал.
5. Приведенные мной примеры имели отношения к игровой индустрии ввиду тематики сайта.
6. Недостаток относится только к генетическому алгоритму, исправлю в статье.

Со всем остальным согласен. Спасибо за дополнение.

Ответить
2

Неплохая иллюстрация алгоритма в игре

Чёрт, я на сон грядущий породил популяцию бешеных табуретов. Как это развидеть теперь?

Ответить
0

Теперь живите с этим.

Ответить

Комментарий удален

0

Статьи о генетике - это первый шаг к расизму, если вы понимаете о чем я. :)

Ответить
0

Как бы нет, лол.

Ответить
1

Генетика - наука подразумевающая присабливаемость организмов к существованию в окружающих условиях. Европейцам надо было думать, где достать еду зимой, по этому выживали самые умные. Африканцам надо было быстро бегать с копьем за газелями, по этому выживали самые быстрые.

Нет, я не расист, т.е. предвзятого мнения к другим рассам у меня нет, это научные факты, с которыми нельзя спорить.

Ответить
2

Ваше утверждение не столько однозначно верно, как выглядит на первый взгляд.

Если попытаться применить ваши рассуждения, то необходимо сравнивать двух человек одного вида - Homo Sapiens. Около ста тысяч лет назад жило минимум 6 видов Homo - Sapiens, Erectus, Neanderthalensis и другие. Разница между ними была генетическая - различные виды человека ( в том числе и умершие к расчётной дате) существовали параллельно и развивались около 2.5 миллионов лет - это достаточный срок для проявления эволюционных различий и получения эволюционных навыков. Эти навыки могут быть разнообразными - от прямохождения до умения пользоваться палкой. Ключевая особенность в том, что научившись пользоваться палкой эволюционным путем особь будет ещё миллион лет пользоваться этой палкой и не догадается приделать к ней камень. До тех пор, пока у неё, условно, не появится ген "палки с острым камнем на конце". Получения эволюционных навыков очень длительное.

Около пятидесяти лет назад, с видом сапиенс произошло чудо, которое так же могло произойти с любым другим видом человека - они смогли думать абстрактно. Это явления называется когнитивной революцией. Помимо абстрактного мышления, оно принесло большое количество плюсов вроде возможности объединения в большие группы и разработки более тщательных планов. Именно после этого Homo Sapiens смог истребить всех других видов людей, и остаться одним из себеподобных. После этого, для того, чтобы додуматься затачивать маленький камень, надевать его на тонкую ветку и стрелять им из гибкой ветки не пришлось тратить миллион лет; всего за 50.000 лет Homo Sapiens смог дойти до интернета и компьютеров. Это - когнитивные навыки.

Я все это долги пишу, чтобы показать - разница в навыках чёрных Homo Sapiens, которые бегали в Африке и белых Homo Sapiens, часть из которых жила на севере когнитивная. 100.000 лет - слишком малые промежуток времени для эволюционных навыков. Серьезных генетических отличий, отвечающих за умственные и спортивные особенности, насколько я знаю, не обнаружено.

Ответить
0

Физические различия между черными и белыми очевидны, их не требуется доказывать. Мое сообщение - это не предположение, что они отличаются, а попытка объяснить, почему они отличаются.

Ответить
0

Так это статья не о генетике а об алгоритме, но я понял вашу отсылку

Ответить
1

Не знаю, насколько относится к науке, но как по мне, тема очень интересная и не сложная в понимании.

Ответить
3

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

Ответить
1

Отлично относится, спасибо

Ответить
0

не сложная в понимании.

Тем не менее автор смог.

Ответить
1

Хех, диплом по этой штуке писал. Воспоминания...

Ответить
1

ಠ⌣ಠ

Ответить
0

Тема интересная, статья тоже, только одна просьба - пожалуйста, вычитывайте статью перед публикацией. Много очепяток.

Ответить
0

Хмм... странно, ведь я два раза перечитал. Можете, пожалуйста, ткнуть носом.

Ответить
1

Так дофига же...
Ладно, на пунктуацию забью, я сам её чисто интуитивно ставлю. Далее, парами, оригинал - исправленное. Допускаю, что некоторые моменты спорны (я не претендую на абсолютную истину и не являюсь филологом).
-----------------------------------
"Лапки гекконов - удивительный механизм, схожих которому не найти. Уже сейчас инженеры мира создают прототипы роботов, способных карабкаться по вертикальным поверхностям, подражая геккону." - "схожих с которым"
-----------------------------------
"Что же об эвристике - она вступает в игру когда все математические формулы, все логические способы решения задачи не привели к ожидаемому результату, либо полученный результат не есть оптимальным." - "не есть оптимальный результат" или "не является оптимальным".
-----------------------------------
"Алгоритм, который должен достичь поставленой цели, используя какие-угодно способы и решения" - "Алгоритм, который должен достичь поставленной цели, используя какие угодно способы и решения"
-----------------------------------
"Они будут знакомы с теории эволюции и значение будут иметь схожее." - скорее уж тогда "они знакомы по теории эволюции", хотя выражение всё равно... как песок на зубах.
-----------------------------------
"Нагло сворованная картинка, которая очень простыми словами показывает работу алгоритма" - "Нагло сворованная картинка, которая очень простыми словами объясняет работу алгоритма." Ну или "Нагло сворованная картинка, которая очень наглядно показывает работу алгоритма." Слова - объясняют, картинка показывает. Не наоборот.
-----------------------------------
"Поколение - выборка экземпляров, которые существуют одновременно, и соревнуются друг с другом за виживание путем решения поставленной задачи (ну или попытками решения)." - "Поколение - выборка экземпляров, которые существуют одновременно, и соревнуются друг с другом за выживание путем решения поставленной задачи (ну или попыток решения)."
-----------------------------------
"Характеристика - один из параметров, которым обладает образец." - "Характеристика - один из параметров, которыми обладает образец."
-----------------------------------
"Данный механизм есть движущей силой всего алгоритма." - "Данный механизм есть движущая сила всего алгоритма." или "Данный механизм является движущей силой всего алгоритма."
-----------------------------------
"Кроссинговер - механизм, который наравне з мутацией "двигает прогресс". - "Кроссинговер - механизм, который наравне с мутацией "двигает прогресс".
-----------------------------------
"можно использовать космичекие шумы" - "можно использовать космические шумы"
-----------------------------------
"Как уже можно было подметить, действие алгоритма можно разбить на "чекпойнты" или вехы развития." - "Как уже можно было подметить, действие алгоритма можно разбить на "чекпойнты" или вехи развития."
-----------------------------------
"Как только в следствии мутации либо кроссинговера был найден обазец, который на голову лучше предшественником справляется с задачей, вся популяция через несколько поколений составляет те или иные вариации революционного экземпляра, то есть происходит полировка." - "Как только вследствие мутации либо кроссинговера был найден образец, который на голову лучше предшественника справляется с задачей, вся популяция через несколько поколений составляет те или иные вариации революционного экземпляра, то есть происходит полировка."

Ответить
0

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

Ответить
0

Ничего не понял, но было интересно читать

Ответить
0

Спасибо, отличная статья, но тут не говорится о том что решение не обязательно правильное, алгоритм лишь приближает нас к нему

Ответить
0

В комментарии повыше пришел человек, более компетентный, чем я, и подметил это

Ответить
0

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjog" } } }, { "id": 10, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-250597-0", "render_to": "inpage_VI-250597-0-1134314964", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=clmf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudo", "p2": "ftjf" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvc" } } } ]
Гейб Ньюэлл наконец-то анонсировал то,
чего все так долго ждали
Подписаться на push-уведомления