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

Описание работы генетического алгоритма на примере поиска максимума функции двух переменных. Берем 4 случайные хромосомы (4 случайные точки), отбираем лучшую с точки зрения максимума функции. Затем лучшая хромосома (в данном случае - точка) наследует новому поколению все свои гены (координаты х и у). Худшая вылетает из процесса. И т.д.

[@user-bx5xv7gg6k]

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

[@s1___]

Отличный урок, хорошее сравнение с материалами ценой и прочими характеристиками

[@user-bi4mr3wi8i]

Большое спасибо за интересный материал!

[@onocomments4115]

Спасибо вам огромное!

[@valeriyblinov1573]

Супер !! Надо понять!!! Спасибо Великому!!! V

[@ynxela]

Спасибо большое!

[@freaxlover]

Спасибо Вам огромное! Отличное объяснение. Будьте здоровы❤️

[@caseng1270]

Спасибо большое! Всё понятно

[@blackbigdeath]

Отличное видео, и спасибо за микрофон на пиджаке:)

[@user-jl3ci9zv1n]

Наконец стало понятно! Правда почему то цифры соответствуют схеме только самой сильной (а) хромосоме. Но главное принцип понятен.

[@maridat47]

Я сделал программу по этому принципу и узнал, что максимум этой функции равен 0.5 примерно в точке x: 1.000362 y: -0.000275

[@krenciak]

У меня получилось 0.5 в (1; 0) Вот мой код: gist.github.com/balgor36/a5c8a834ba30d06ee07a59a6023498f2 Конечная популяция записывается в файл data.txt Для увеличения производительность можно использовать флаги оптимизации (например, O2).

[@twobomb3]

Сделал на Javascirpt, визуальное нахождение jsfiddle.net/twobomb/63kLjq7z/

[@nighthunter28]

@@twobomb3 Math.round нужно заменить на Math.floor, а то также 4 элемент выбирается, который не нужен.

[@darkeliphant1843]

Начальник Шоушенка объясняет генетический алгоритм, эт что-то новенькое

[@Kirsanov2011]

Где же новенькое? 3 года назад, дружище!

[@hydrobusy8522]

Kirsanov2011 я хотел бы уточнить понятие что каждое следующее поколение лучше. Я бы использовал другое слово, не лучше, а приспосОбленнее. Каждое следующее поколение более приспособленное к текущему внешнему миру. Но я не эксперт, это мои размышления. Что думаете по этому случаю?

[@user-ce8yq6so3z]

@@hydrobusy8522 не согласен. Каждое следующее поколение именно лучше, а не более приспособленное. Например, к чему они приспосабливаются в примере, в видео?

[@user-xh7hw4ck9z]

)))

[@obrkn]

Здравствуйте. Может, Вы поможете мне разобраться с этим моментом: Вероятность мутации это Pm. Она берется в диапазоне от 0 до 1. Каждому гену в хромосоме присваиваются случайные числа от 0 до 1. Если вероятность Pm больше либо равна этим числам то происходит мутация (с 0 на 1). Это то, что мне удалось понять о мутации. Но каким образом происходит присваивание случайных чисел каждому гену?

[@Kirsanov2011]

Не всегда ген это 0 или 1. Может быть и десятичное число. Ну и давайте случайному номеру гена случайное число.

[@user-ix9nv7th8g]

Прежде всего хочу сказать автору большое спасибо за работу, мне, как студенту было полезно просмотреть данное видео, однако я хочу заметить несколько особенностей(поправьте меня, если я не прав): 1)*Кроссовер*(crosover) - это и правда процесс скрещивания двух особей(хромосом) *Кроссинговер*(crossing over) - это *НЕ* кроссовер, а процесс повышения вероятности скрещивания в особях, которые являются лучшими в популяции. 2)Необходимо поподробней остановится на *оценочной функции* - показать ее роль более выразительно, а также показать сложность выбора этой функции в реальных нестандартных задачах, с большим числом параметров 3)Для предотвращения преждевременной сходимости рекомендуется использовать: *однородный кроссовер*(каждый ген имеет вероятность унаследоваться к одному потомку,а оставшиеся не унаследованные - к другому), и *принцип элитизма* (грубо говоря в новой популяции присутствует некоторое число родителей). 4)Также не было рассказано о *методах кодирования* информации, для представления информации в хромосому, как вектора - набора характеристик Например бинарное кодирование, схемы(shema),код Грея,... *PS*: Видео понравилось, если я где-то ошибся - простите, я только начал знакомство с этой темой. Отпишите, что Вы думаете.

[@Kirsanov2011]

Спасибо за внимание к моей скоромной работе. Многое, что Вами сказано, мне, конечно, известно. Но кое-что полезное мне напомнили просто. Учту.

[@madiyetov]

При отборе из первого поколения, у=0 остался не использованным, а ведь если использовать этот ген максимизация была бы еще лучше, или я что то не понял?

[@Kirsanov2011]

Это конечно, сильно упрощенная схема. На практике хромосома длиннее, больше объектов, все используется в многочисленных итерациях. Я дал только суть.

[@user-xu7mf5iw9s]

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

[@Kirsanov2011]

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

[@nRADRUS]

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

[@volandku]

Ага. А как с ним бороться? Я на практике стокнулся с вырождением потомства в район локального экстремума, есть простые методы борьбы с этим?

[@_den_]

@@volandku "если мутации будут в т.ч. СИЛЬНЫМИ, то и из локального минимума можно выйти" из сообщения выше

[@antonio8778]

Могу ошибаться, но у вас есть ошибка в процессе применения кроссовера. 4:57. Обратите внимание на получения второго поколения. Согласно схемы применения кроссовера, первый ген второй хромосомы (b - хромосома, ген x), должен был отнаследоваться к хромосоме a второго поколения, ген x. Похоже, как и все остальные гены, по мимо наследования от хромосомы a первого поколения

[@ramsakhmitzy6718]

да, перепутал местами столбики. Не важно, но тем не менее. Тягостное впечатление от всего этого. Не может ясно показать такие простые вещи. Хуже всего, что это дается как какое-то заклинание типа гарри поттера. А где рассуждения о сходимости, о скорости сходимости, и т.д. Почему вообще это будет работать? Ссылка на Дарвиновский отбор -это для идиотов. Надо программу демонстрировать с ответом. не важно джава-хуява или что - программа будет простой в этом случае. Пример лектора, который давно остановился в развитии, но уж наверно на ученых советах восседает в первых рядах...

[@antonio8778]

@@ramsakhmitzy6718 Не могу говорить за Россию, но в Украине это ещё нормальный вариант преподавателя. Есть конечно и молодые, амбициозные, находящиеся постоянно в тренде, но часто встречаются и настоящие динозавры, как по возврасту, так и по характеру.

[@stano.marochok]

@@ramsakhmitzy6718 та хз тут задача была скорее принцип объяснить и мужик вроде нормально все объясняет

[@Amid_Vok]

2:25 Кроссинговер - Кроссоверинг

[@denispashnev912]

Где используют генетические алгоритмы? Какой от них толк?

[@Kirsanov2011]

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

[@denispashnev912]

@@Kirsanov2011 можете привести пример? Реального приложения, которое использует генетические алгоритмы?

[@wugu42]

@@denispashnev912 Ты сам являешься результатом работы такого алгоритма. :)

[@MrGRMichael]

не понятнен источник самой функции. как выводится этот закон?

[@alexandersobolev2769]

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

[@nighthunter28]

источник тут только один - матанализ, раздел экстремума функции, там узнаете про ваш "закон" и порядок (производной).

[@user-ub6wt5nl5b]

А как насчёт устойчивости?

[@elenagaranina5904]

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

[@user-ob1yb6xs3w]

ИИ✔

[@user-sz2fz2ij8r]

Ну этот алгоритм больше похож на сортировку перебором. Если вы хотите провести аналогию с биологической эволюцией, то я вас немного поправлю.

[@user-sz2fz2ij8r]

Вы рассматриваете два гена тетраплоидного набора хромосом (четыре хромосомы) - четыре аллели двух генов. Проще наверное разбираться с диплоидным - двойным набором хромосом, это нагляднее и распространеннее в природе. Тогда х и у на вашей схеме - это две хромосомы от разных родителей. Получается по два аллеля каждого гена: -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] - такой вариант практически невозможен в этом примере, если мы говорим о биологическом алгоритме.

[@user-sz2fz2ij8r]

Не могу судить о том, какие алгоритмы лучше подходят для решения уравнений, но при моделировании алгоритма биологической эволюции нужно учитывать некоторые закономерности: 1. Рецессивный признак, как правило - умеренно вредная мутация, но вредная только на каком-то прошедшем отрезке эволюционного процесса, относительно стабильных условий на этом отрезке времени. При изменении условий эта мутация может обеспечить адаптацию. Условия в масштабах биологической эволюции это очень непостоянная переменная. Падение метеорита - и все носители, как вы говорите «хороших» или «сильных» генов вымрут за короткое время. А носители вредных вчера рецессивных генов, сегодня могут оказаться наиболее приспосабливаемыми к новым условиям. Естественный отбор уничтожает только категорически вредные мутации, в основном нежизнеспособные в принципе. Не слишком же вредные мутации уходят в подавленное состояние, но не покидают генный пул популяции - это гарантия выживания будущем. То есть при разработке алгоритма, если вы хотите в вашей симуляции не упереться в порог развития и не погубить популяции при смене условий, то нужно сохранять рецессивные признаки. И при симуляции среды для популяций нужно обязательно менять среду - универсальность адаптивности стратегически важнее, чем специализация адаптивности. Популяция может быть вытеснена в другие ниши, но будучи универсальной она выживет, в отличии от «узкоспециализированной» популяции. 2. Аллельные взаимодействия не бинарны - Менделю очень повезло, что в опытах с горохом ему попалось именно полное доминантное взаимодействие, иначе он не обнаружил бы закономерностей. Взаимодействия могут быть и другими: неполное дрминирование, кодоминировпние - пречислять и описывать не буду, но учитывать это надо, так как это тоже несет большое адатаптивное значение. Кроме этого существуют неаллельные взаимодействия, так за один и тот же белок или фермент или рнк монут отвечать гены из разных локусов хромосомы . 3. Нужно учитывать эффект инбридирга и аутбридинга. Чем родственнее генотипы особей, тем гомозиготнее и слабее будет их потомство. Менее родственные особи дадут более гетерозиготное и более сильное потомство. Эффект гетерозиса. 4. При симуляциях биологической эволюции нужно учитывать влияние других популяций, скрещивание с которыми невозможно, но в процессе симбиоза или паразитирования может произойти горизонтальный обмен генами - тоже мощнейший фактор изменчивости. 5. Нужно учитывать экзогенные мутации, которые происходят в процессе онтогенеза - это абсолютно случайные изменения генов под воздействием внешних небиологических факторов: вредностей, излучений итп. Ну примерно так будет довольно близко к биологической эволюции, без учёта эпигенетических и социальных факторов наследственной передачи. Это разумеется если нужно имитировать именно биологическую модель. Если алгоритм предназначен для решения конкретной прикладной задачи, то конечно больший вес будет иметь его адаптация именно к этой задаче, без стратегии предполагающей, что задача может измениться.

[@balabuyew]

Мутация важней чем кроссовер. Так как у вас показано вообще работать не должно.

[@edryahlov]

они работают в тандеме... одно без другого - хаос