Лекция #17. GA (Генетические Алгоритмы + addon). [Лектор - xmvlad] (2 стр)

Автор: Vladislav Gusev

<xmvlad> 9. Мутация.
<xmvlad> Мутация позволяет вносить что-то новое в популюцию. Проще говоря эффективно борется с застреванием популяции в локальных минимумах фитнес-функции.
<xmvlad> Важно понять что мутация это компромисс
<xmvlad> С одной страны - "загнивание"(застой) в локальном минимуме если мутация слишком маленькая с другой стороны "деградация" популяции.
<xmvlad> Деградация популяции может происходить при слишком больших значениях мутации. То есть необходимо понимать, что кроссинговер - КЛЮЧЕВАЯ сила в развитии популяции, слишком большая мутация просто "засевает" популяцию рэндомными особями. (то что я говорил в самом начале, сохранятся должны лучшие)
<xmvlad> <aloha_hawaii> сколько должно быть детей от каждой пары родителей?
<xmvlad> один обычно так
<xmvlad> но может и большь
<xmvlad> рекомендуют одного
<xmvlad> <aloha_hawaii> всегда думал что должно быть 4 и больше, тк при 1м ребенке велика верояность вырождения, потери полезной информации родителей.
<xmvlad> нет если будет элитаризм, то у нас уже будет 20% хороших особей, который родят "хороших" детей.
<xmvlad> гарантировано
<xmvlad> Рассмотримм процесс мутации более подробно.
<xmvlad> У нас уже есть хромосома ребенка полученная в результате кроссинговера.
<xmvlad> а) выбираем некоторую небольшую вероятность 0.005-0.05, с которой мы будем производить мутацию, то есть мутации будет подвергаться лишь небольшое количество детей иначе возможна деградация.
<xmvlad> б) производим мутацию хромосомы, для каждого гена с некоторой небольшой вероятностью(0.001-0.05) выбираем будет ли этот ген мутировать или нет.
<xmvlad> и так способы мутации:
<xmvlad> а) если это бинарная строка, можно инвертировать соответствующий ген (бит)
<xmvlad> б) униформный сэмплинг пространства возможных значений гена, то есть просто рэндомно выбираем другое значени и присваиваем гену
<xmvlad> <aloha_hawaii> при скрещивании родителей не будет ли целесообразнее перебрать несколько вариантов скрещивания, чтобы гарантированно получить особь, унаследовавшую лучшие признаки обоих родителей. случайное смешивание может это пропустить.
<xmvlad> кхм, суть в том что у нас и так есть 20% лучших, более эффективно дать другим родить детей, что бы большее количество эффективной генетической информации перешло в следующую популяцию(размер которое может быть сильно ограничен), чем "засевать" популяцию детьми одних и тех же родителей.
<xmvlad> возвращаясь к мутации в) можно просто прибавить к текущему значению гена некоторое небольшое число, тогда мутация будет более "гладкой", новые значения генов будут лежать в некоторой окрестности предыдущих значений
<xmvlad> 10. Мы получили одного ребенка, повторяй выше указанный процесс селекция, кроссинговер, мутация, для другой пары родителей, получаем еще одного ребенка. И так пока не "засеем" полностью новую популяцию.
<xmvlad> 11. Новая популяция становится текущей. Процесс итеративно повторяется начиная с пункта 5 (расчет фитнес функции).
<xmvlad> 12. Когда это все заканчивается.
<xmvlad> а) при достижении некоторого заданного значения фитнес-функции
<xmvlad> б) при схождении популяции, когда подавляющее большинство особей содержат одни и те же значения в хромосомах.
<xmvlad> все перерыв
<xmvlad> обсуждение, я пойду чайку попью
<aloha_hawaii> а еще лекция будет?
<Sark7> хм
<Sark7> я вот нипонял
<Zeux> будет продолжение, видимо
<Sark7> 20% лучших, от них дети
<Sark7> а 80% выкидываем?
<aloha_hawaii> да
<Sark7> т.е. в новой популяции только дети. или те 20 тоже есть?
<Zeux> да
<Zeux> фхлам
<VoidEx> дети
<Zeux> естественный отбор
<VoidEx> а как же гуманизм ?
<Sark7> дык не сразу же помирают предки
<VoidEx> вот так взяли
<VoidEx> и выкинули ?
<VoidEx> :)
<Sark7> 2 поколения должно быть
<neteraser> а где тут было про игры?
<Sark7> по идее
<Sark7> в смысле особь жыть 2 поколения )
<aloha_hawaii> вообще должна быть цифра 25/75, но 20/80 близко
<Qiller> neteraser - <xmvlad> Disclaimer to kas: лектор предупреждает, что информация полученная в результате прослушивания это лекции, может не иметь прямого отношения к геймдеву, хотя лектор постарается привести жизненные примеры. :)
<Sark7> а ето кстати забавно
<Sark7> можно так в игре делать
<Qiller> Ага. А теперь в духе Spore, научите ходить скелету через ГА? %)
<Sark7> типа те злыдни которых игрок не убил
<Sark7> скрещиваюцо
<Sark7> и получаюцо супер-злыдни
<Zeux> и получаются убер-монстры!
<Sark7> атож
<aloha_hawaii> недостатки га в том, что он находит все возможности, даже заведомо читерские.
<Xunter> злыдни которых игрок не нашел =)
<Sark7> т.е. в новой популяции только дети. или те 20 тоже есть?
<Sark7> вот ето мне интересно
<Sark7> т.е. новое поколение полностью из детей, или часть предыдущего тоже остаецо?
<xmvlad> только дети, имеет смысл скопировать может быть лишь 1-2 самых лучших
<xmvlad> на всякий запасный :)
<xmvlad> если эволюция ошибется :)
<Sark7> примеры интересуют )
<xmvlad> ну продолжим, какие есть пожилания?
<xmvlad> 1. Как подбирать параметры.
<xmvlad> Очевидные параметры которые у нас есть(в порядке важности, и степени воздействия): вероятность мутации, вероятность мутации гена, размер популяции.
<xmvlad> Для того что бы подобрать параметры необходимо НАБЛЮДАТЬ за популяцией и понимать что в ней происходит и почему, так сказать быть мини-богом на этапе настройки. Наблюдать - прежде всего следить за значениями фитнес-функции особей и за тем как они изменяются от популяции к популяции.
<xmvlad> Возможны следующие сценарии развитися событий:
<xmvlad> а) Деградация популяции. Симптомы: значения фитнеса у лучших особей предыдущих популяций лучше чем у особей последующих популяций. Происходит так сказать вырождение, "лучшие" вымирают а не переходят в новую популяцию.
<xmvlad> Причина: слишком большое воздействие мутации.
<xmvlad> Действия: попробовать уменьшить значения вероятностей мутации особей/генов.
<xmvlad> б) Застой популяции. Значения фитнеса становится "постоянным"(или незначительно улучшается) в течении большого количества популяции.
<xmvlad> Причина: в популяции не вносятся "новая информация".
<xmvlad> Действия: увеличить размер популяции, увеличить вероятность мутации, позволить особям с более низким значением фитнеса размножатся(плохой сейчас - может иметь ценнуц ген информацию в будущем)
<xmvlad> То есть необходим постаратся так подобрать параметры, что бы процесс шел между этими двумя крайностями, застой и деградация, желательно полностью не переходся ни в то ни в другое
<xmvlad> Теперь про стратегию инцеста, которая позволяет бороться с "застоем".
<xmvlad> Если популяция сходится, мы увеличиваем мутацию, например по экспоненте.
<xmvlad> Следующий важный вопрос. Способ кодирования.
<xmvlad> Пожалуй одновременно и самы сложный. Правильное кодирование - половина успеха. Кодирование должно обладать следующими свойствами:
<xmvlad> а) позволять производить операции кроссинговера. (самое важное) подумайте как вы сумеете скрестить две особи и получить _корректный_ результат.
<xmvlad> б) кодирование так же должно быть "гладким" по отношению к предметной области, сложно объяснить но это значит примерно следующее: незначительные изменениям в предметной области должны вести к незначительным измененям в кодировании и НАОБРОТ.
<xmvlad> То есть не должно буть так что бы в результате изменения одного гена из носорога получался слон.
<xmvlad> Это очень важно, хорошее, "гладкое" кодирование  - залог успеха в применении ГА. [\b]
<xmvlad> <aloha_hawaii> как я понял данный алгоритм один в один повторяет природный аналог, однако в природе фитнес функция в процессе алгоритма постоянно меняется . Нет ли каких "оптимизациий" с учетом постоянства фитнес функции?
<xmvlad> по этому поводу хочется сказать что в природе фитнес функция в масштабах популяций достаточно постоянно, а резкие изменения - ведут к массовым ввымираниям, вспомним динозавров :)
<xmvlad> в общем про такие оптимизации я не знаю, хотя возможно они и есть.
<xmvlad> живые остались?
<xmvlad> откликнитесь кто жив %)
<aloha_hawaii> я тут
<aloha_hawaii> хорошая лекция, понятно все
<aloha_hawaii> последний вопрос
<xmvlad> так теперь обещанный пример
<aloha_hawaii> по генетичскому алгоритму смысл жызни в чем?
<xmvlad> :)))
<xmvlad> чей смысл? особи?
<xmvlad> или бога? :)
<aloha_hawaii> людей
<aloha_hawaii> мы ж по нему появились
<xmvlad> ну не людей а особей
<xmvlad> пока особь не приобритет осознание того что она особь, она тупой инструмент в руках эволюции :)
<xmvlad> суть в том что генетика
<xmvlad> медленный механизм адаптации
<aloha_hawaii> ну осознание сути не меняет
<xmvlad> когда условия начинают менятся быстрее, начинает рулить адаптация во время жизни - нейронка :)
<aloha_hawaii> ясно
<xmvlad> но это все философия конечно :)
<xmvlad> вот пример кода (оптимизация мозга гнома): http://www.gamedev.ru/download/file.php?id=3119

9 марта 2006