Генетический алгоритм
HTML-код
- Опубликовано: 8 окт 2014
- Описание работы генетического алгоритма на примере поиска максимума функции двух переменных. Берем 4 случайные хромосомы (4 случайные точки), отбираем лучшую с точки зрения максимума функции. Затем лучшая хромосома (в данном случае - точка) наследует новому поколению все свои гены (координаты х и у). Худшая вылетает из процесса. И т.д.
На простых и ясных примерах объясняются сложные вещи. А ведь это самое главное - понять концепцию, принцип действия. А дальше можно и самим разобраться. Спасибо Вам большое.
Отличный урок, хорошее сравнение с материалами ценой и прочими характеристиками
Большое спасибо за интересный материал!
Спасибо вам огромное!
Спасибо большое!
Спасибо большое! Всё понятно
Супер !! Надо понять!!! Спасибо Великому!!! V
Отличное видео, и спасибо за микрофон на пиджаке:)
Спасибо Вам огромное! Отличное объяснение. Будьте здоровы❤️
Начальник Шоушенка объясняет генетический алгоритм, эт что-то новенькое
Где же новенькое? 3 года назад, дружище!
Kirsanov2011 я хотел бы уточнить понятие что каждое следующее поколение лучше. Я бы использовал другое слово, не лучше, а приспосОбленнее. Каждое следующее поколение более приспособленное к текущему внешнему миру. Но я не эксперт, это мои размышления. Что думаете по этому случаю?
@@hydrobusy8522 не согласен.
Каждое следующее поколение именно лучше, а не более приспособленное.
Например, к чему они приспосабливаются в примере, в видео?
)))
Наконец стало понятно! Правда почему то цифры соответствуют схеме только самой сильной (а) хромосоме. Но главное принцип понятен.
Я сделал программу по этому принципу и узнал, что максимум этой функции равен 0.5 примерно в точке x: 1.000362 y: -0.000275
У меня получилось 0.5 в (1; 0)
Вот мой код: gist.github.com/balgor36/a5c8a834ba30d06ee07a59a6023498f2
Конечная популяция записывается в файл data.txt
Для увеличения производительность можно использовать флаги оптимизации (например, O2).
Сделал на Javascirpt, визуальное нахождение jsfiddle.net/twobomb/63kLjq7z/
@@twobomb3 Math.round нужно заменить на Math.floor, а то также 4 элемент выбирается, который не нужен.
Здравствуйте. Может, Вы поможете мне разобраться с этим моментом:
Вероятность мутации это Pm. Она берется в диапазоне от 0 до 1. Каждому гену в хромосоме присваиваются случайные числа от 0 до 1. Если вероятность Pm больше либо равна этим числам то происходит мутация (с 0 на 1). Это то, что мне удалось понять о мутации. Но каким образом происходит присваивание случайных чисел каждому гену?
Не всегда ген это 0 или 1. Может быть и десятичное число. Ну и давайте случайному номеру гена случайное число.
Прежде всего хочу сказать автору большое спасибо за работу, мне, как студенту было полезно просмотреть данное видео, однако я хочу заметить несколько особенностей(поправьте меня, если я не прав):
1)*Кроссовер*(crosover) - это и правда процесс скрещивания двух особей(хромосом)
*Кроссинговер*(crossing over) - это *НЕ* кроссовер, а процесс повышения вероятности скрещивания в особях, которые являются лучшими в популяции.
2)Необходимо поподробней остановится на *оценочной функции* - показать ее роль более выразительно, а также показать сложность выбора этой функции в реальных нестандартных задачах, с большим числом параметров
3)Для предотвращения преждевременной сходимости рекомендуется использовать:
*однородный кроссовер*(каждый ген имеет вероятность унаследоваться к одному потомку,а оставшиеся не унаследованные - к другому),
и *принцип элитизма* (грубо говоря в новой популяции присутствует некоторое число родителей).
4)Также не было рассказано о *методах кодирования* информации, для представления информации в хромосому, как вектора - набора характеристик
Например бинарное кодирование, схемы(shema),код Грея,...
*PS*: Видео понравилось, если я где-то ошибся - простите, я только начал знакомство с этой темой.
Отпишите, что Вы думаете.
Спасибо за внимание к моей скоромной работе. Многое, что Вами сказано, мне, конечно, известно. Но кое-что полезное мне напомнили просто. Учту.
Как в итоге понять то, что достигнут нужный конечный результат?
Это условно все. Не меняется ответ (с точностью до некоторой малой величины) - значит конец работы. Но один из основных минусов подобных алгоритмов - возможность попадания в локальный минимум (экстремум).
если мутации будут в т.ч. сильными, то и из локального минимума можно выйти. также неплохо практиковать двойные-тройные-энные мутации, как и в природе, где гены белков повторяются многократно, что позволяет одним генам работать (и позволять организму жить), а другим - мутировать несколько раз, переносясь в очень дальние следующие поколения...
Ага. А как с ним бороться? Я на практике стокнулся с вырождением потомства в район локального экстремума, есть простые методы борьбы с этим?
@@volandku "если мутации будут в т.ч. СИЛЬНЫМИ, то и из локального минимума можно выйти"
из сообщения выше
При отборе из первого поколения, у=0 остался не использованным, а ведь если использовать этот ген максимизация была бы еще лучше, или я что то не понял?
Это конечно, сильно упрощенная схема. На практике хромосома длиннее, больше объектов, все используется в многочисленных итерациях. Я дал только суть.
Могу ошибаться, но у вас есть ошибка в процессе применения кроссовера.
4:57. Обратите внимание на получения второго поколения.
Согласно схемы применения кроссовера, первый ген второй хромосомы (b - хромосома, ген x), должен был отнаследоваться к хромосоме a второго поколения, ген x.
Похоже, как и все остальные гены, по мимо наследования от хромосомы a первого поколения
да, перепутал местами столбики. Не важно, но тем не менее. Тягостное впечатление от всего этого. Не может ясно показать такие простые вещи. Хуже всего, что это дается как какое-то заклинание типа гарри поттера. А где рассуждения о сходимости, о скорости сходимости, и т.д. Почему вообще это будет работать? Ссылка на Дарвиновский отбор -это для идиотов. Надо программу демонстрировать с ответом. не важно джава-хуява или что - программа будет простой в этом случае. Пример лектора, который давно остановился в развитии, но уж наверно на ученых советах восседает в первых рядах...
@@ramsakhmitzy6718 Не могу говорить за Россию, но в Украине это ещё нормальный вариант преподавателя. Есть конечно и молодые, амбициозные, находящиеся постоянно в тренде, но часто встречаются и настоящие динозавры, как по возврасту, так и по характеру.
@@ramsakhmitzy6718 та хз тут задача была скорее принцип объяснить и мужик вроде нормально все объясняет
2:25 Кроссинговер - Кроссоверинг
Где используют генетические алгоритмы? Какой от них толк?
Как раз именно они наиболее востребованы там, где много всяких факторов и надо найти экстремум. Фактически, это метод умного перебора. Область применения обширнейшая.
@@Kirsanov2011 можете привести пример? Реального приложения, которое использует генетические алгоритмы?
@@denispashnev912
Ты сам являешься результатом работы такого алгоритма. :)
не понятнен источник самой функции. как выводится этот закон?
Какой закон? Это просто _какая-то_ функция, на примере которой демонстрируется генетический алгоритм поиска максимума функции.
Можно взять _любую другую_ функцию нескольких переменных (лишь бы только у нее в принципе были точки максимумов или минимумов) и найти тем же алгоритмом точки максимума уже для этой другой функции
источник тут только один - матанализ, раздел экстремума функции, там узнаете про ваш "закон" и порядок (производной).
А как насчёт устойчивости?
зависает в локальных экстремумах. Если их несколько, то надо насыпать много особей по всему пространству, чтобы хоть одна тварь да провалилась в глобальный. Если раньше не сдохнет. Частенько пространство такое, что все радостно ползут в уютный локальный экстремум потому что глобальный расположен неудобно. Сходится медленно. Ресурсы жрёт как не в себя. Одно достоинство - очень прост в реализации. Для простеньких задач норм.
ИИ✔
Ну этот алгоритм больше похож на сортировку перебором. Если вы хотите провести аналогию с биологической эволюцией, то я вас немного поправлю.
Вы рассматриваете два гена тетраплоидного набора хромосом (четыре хромосомы) - четыре аллели двух генов. Проще наверное разбираться с диплоидным - двойным набором хромосом, это нагляднее и распространеннее в природе.
Тогда х и у на вашей схеме - это две хромосомы от разных родителей. Получается по два аллеля каждого гена: -2,0 -1,-2 0,-1 2,1
Лучшее вообще для простоты пока заменим всё на бинарное обозначение 1 - доминантный аллель, 0 - рецессивный
Например, есть генотип одного диплоидного родителя:
2 хромосомы х и у и 5 генов (по две аллели каждого гена)
х[0,0,1,0,1]
У[1,1,1,0,0]
Если аллельное взаимодействие полное доминантное, то фенотип особи будет
[1,1,1,0,1]
при этом
1,2 и 5-й признаки - доминантные гетерозиготные.
4-й признак - как раз то, о чем вы говорили, в фенотипе проявился именно гомозиготный рецессивный признак
3-й признак доминантный гомозиготный.
Теперь если рассмотреть кроссинговер, то при образовании половых клеток (гаплоидных гамет с одной хромосомой, которые получаются при разделении двух хромосом диплоидного организма) происходит обмен участками между хромосомами.
При этом процесс этот случаен - клетка не знает какой ген лучше, ведь она не знает какие условия её ждут. Поэтому эволюционный принцип это создать разнообразие - случайную рекомбинацию (что-то да выживет). Механизм аллельного доминирования лишь подавляет рецессивные признаки, так как условия не меняются резко, то в процессе отбора со временем менее подходящий условиям ген подавляется, но не убирается из генотипа как плохой. Ничто не уходит в небытие. Стратегически выгодно сохранять в генотипе всё разнообразие, и при смене условий может оказаться полезным именно рецессивный признак и при смене условий со временем он закрепится в популяции как доминантный.
Генотип накапливая разнообразные мутации и варианты генов обеспечивает себе большую изменчивость и свободу в адаптации к условиям в будущем. Будущее предсказать невозможно, поэтому решить, какой ген хороший а какой плохой тоже невозможно, их адаптационная значимость одинакова.
То есть кроссинговер происходит абсолютно случайным образом. Единственная закономерность в том, что обмен происходит не отдельными генами, а целыми участками хромосом. И чем ближе друг к другу расположены гены, тем выше вероятность того, что они будут «перенесены» вместе - это единственный параметр который можно рассчитать.
Благодаря этому если гены двух разных признаков находятся рядом, то вероятность того, что они будут рекомбинироваться вместе высока. Поэтому в классической селекции это основная из задач - если нужно проводить отбор по скрытому признаку (например по содержанию крахмала в плодах) то можно обнаружить близкий по локации ген, проявляющийся в фенотипе и вести отбор по этому связанному признаку. Например установив, что ширина листа и содержание крахмала - связанные признаки, можно не дожидаясь плодов чтобы сделать анализ, вести отбор по ширине листа, что возможно на ранних стадиях.
Таким образом основной смысл диплоидности - подавление рецессивных генов (но с их сохранением), а основной смысл кроссинговера - создание максимальной наследственной изменчивости.
Если рассмотреть наш пример с родительской особью
х[0,0,1,0,1]
У[1,1,1,0,0]
То в процессе кроссинговера
к примеру меняются местами участки содержащие 1-й ген: 1,0 меняется на 0,1
Таким образом при разделении хромосом получатся две гаплоидные гаметы
х[1,0,1,0,1] и
у[0,1,1,0,1]
Они несут родительские признаки, но в рекомбинированном виде.
При этом вероятность того, что в этот же участок обмена попадёт 2-й ген намного выше, чем то, что туда попадет 5-й ген.
Т.е вероятность того,
Что хромосомы разделятся как
х[1,1,1,0,1]
у[0,0,1,0,0] намного выше, чем если они разделятся как
х[1,0,1,0,0]
у[0,1,0,0,1] - такой вариант практически невозможен в этом примере, если мы говорим о биологическом алгоритме.
Не могу судить о том, какие алгоритмы лучше подходят для решения уравнений, но при моделировании алгоритма биологической эволюции нужно учитывать некоторые закономерности:
1. Рецессивный признак, как правило - умеренно вредная мутация, но вредная только на каком-то прошедшем отрезке эволюционного процесса, относительно стабильных условий на этом отрезке времени. При изменении условий эта мутация может обеспечить адаптацию.
Условия в масштабах биологической эволюции это очень непостоянная переменная. Падение метеорита - и все носители, как вы говорите «хороших» или «сильных» генов вымрут за короткое время. А носители вредных вчера рецессивных генов, сегодня могут оказаться наиболее приспосабливаемыми к новым условиям. Естественный отбор уничтожает только категорически вредные мутации, в основном нежизнеспособные в принципе. Не слишком же вредные мутации уходят в подавленное состояние, но не покидают генный пул популяции - это гарантия выживания будущем.
То есть при разработке алгоритма, если вы хотите в вашей симуляции не упереться в порог развития и не погубить популяции при смене условий, то нужно сохранять рецессивные признаки. И при симуляции среды для популяций нужно обязательно менять среду - универсальность адаптивности стратегически важнее, чем специализация адаптивности. Популяция может быть вытеснена в другие ниши, но будучи универсальной она выживет, в отличии от «узкоспециализированной» популяции.
2. Аллельные взаимодействия не бинарны - Менделю очень повезло, что в опытах с горохом ему попалось именно полное доминантное взаимодействие, иначе он не обнаружил бы закономерностей. Взаимодействия могут быть и другими: неполное дрминирование, кодоминировпние - пречислять и описывать не буду, но учитывать это надо, так как это тоже несет большое адатаптивное значение.
Кроме этого существуют неаллельные взаимодействия, так за один и тот же белок или фермент или рнк монут отвечать гены из разных локусов хромосомы .
3. Нужно учитывать эффект инбридирга и аутбридинга. Чем родственнее генотипы особей, тем гомозиготнее и слабее будет их потомство. Менее родственные особи дадут более гетерозиготное и более сильное потомство. Эффект гетерозиса.
4. При симуляциях биологической эволюции нужно учитывать влияние других популяций, скрещивание с которыми невозможно, но в процессе симбиоза или паразитирования может произойти горизонтальный обмен генами - тоже мощнейший фактор изменчивости.
5. Нужно учитывать экзогенные мутации, которые происходят в процессе онтогенеза - это абсолютно случайные изменения генов под воздействием внешних небиологических факторов: вредностей, излучений итп.
Ну примерно так будет довольно близко к биологической эволюции, без учёта эпигенетических и социальных факторов наследственной передачи.
Это разумеется если нужно имитировать именно биологическую модель. Если алгоритм предназначен для решения конкретной прикладной задачи, то конечно больший вес будет иметь его адаптация именно к этой задаче, без стратегии предполагающей, что задача может измениться.
Мутация важней чем кроссовер. Так как у вас показано вообще работать не должно.
они работают в тандеме... одно без другого - хаос