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

  Рет қаралды 37,148

Kirsanov2011

Kirsanov2011

Күн бұрын

Пікірлер: 51
@ИгорьАриничев-р9к
@ИгорьАриничев-р9к 7 жыл бұрын
На простых и ясных примерах объясняются сложные вещи. А ведь это самое главное - понять концепцию, принцип действия. А дальше можно и самим разобраться. Спасибо Вам большое.
@s1___
@s1___ 7 жыл бұрын
Отличный урок, хорошее сравнение с материалами ценой и прочими характеристиками
@Антон-р5м8ю
@Антон-р5м8ю 8 жыл бұрын
Большое спасибо за интересный материал!
@onocomments4115
@onocomments4115 6 жыл бұрын
Спасибо вам огромное!
@valeriyblinov1573
@valeriyblinov1573 2 жыл бұрын
Супер !! Надо понять!!! Спасибо Великому!!! V
@caseng1270
@caseng1270 4 жыл бұрын
Спасибо большое! Всё понятно
@freaxlover
@freaxlover Жыл бұрын
Спасибо Вам огромное! Отличное объяснение. Будьте здоровы❤️
@blackbigdeath
@blackbigdeath 3 жыл бұрын
Отличное видео, и спасибо за микрофон на пиджаке:)
@ynxela
@ynxela 6 жыл бұрын
Спасибо большое!
@ВладимирРемизов-о2к
@ВладимирРемизов-о2к 3 жыл бұрын
Наконец стало понятно! Правда почему то цифры соответствуют схеме только самой сильной (а) хромосоме. Но главное принцип понятен.
@СтаниславКавюк
@СтаниславКавюк 8 жыл бұрын
Прежде всего хочу сказать автору большое спасибо за работу, мне, как студенту было полезно просмотреть данное видео, однако я хочу заметить несколько особенностей(поправьте меня, если я не прав): 1)*Кроссовер*(crosover) - это и правда процесс скрещивания двух особей(хромосом) *Кроссинговер*(crossing over) - это *НЕ* кроссовер, а процесс повышения вероятности скрещивания в особях, которые являются лучшими в популяции. 2)Необходимо поподробней остановится на *оценочной функции* - показать ее роль более выразительно, а также показать сложность выбора этой функции в реальных нестандартных задачах, с большим числом параметров 3)Для предотвращения преждевременной сходимости рекомендуется использовать: *однородный кроссовер*(каждый ген имеет вероятность унаследоваться к одному потомку,а оставшиеся не унаследованные - к другому), и *принцип элитизма* (грубо говоря в новой популяции присутствует некоторое число родителей). 4)Также не было рассказано о *методах кодирования* информации, для представления информации в хромосому, как вектора - набора характеристик Например бинарное кодирование, схемы(shema),код Грея,... *PS*: Видео понравилось, если я где-то ошибся - простите, я только начал знакомство с этой темой. Отпишите, что Вы думаете.
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
Спасибо за внимание к моей скоромной работе. Многое, что Вами сказано, мне, конечно, известно. Но кое-что полезное мне напомнили просто. Учту.
@darkeliphant1843
@darkeliphant1843 7 жыл бұрын
Начальник Шоушенка объясняет генетический алгоритм, эт что-то новенькое
@Kirsanov2011
@Kirsanov2011 7 жыл бұрын
Где же новенькое? 3 года назад, дружище!
@hydrobusy8522
@hydrobusy8522 6 жыл бұрын
Kirsanov2011 я хотел бы уточнить понятие что каждое следующее поколение лучше. Я бы использовал другое слово, не лучше, а приспосОбленнее. Каждое следующее поколение более приспособленное к текущему внешнему миру. Но я не эксперт, это мои размышления. Что думаете по этому случаю?
@3121-n6q
@3121-n6q 5 жыл бұрын
@@hydrobusy8522 не согласен. Каждое следующее поколение именно лучше, а не более приспособленное. Например, к чему они приспосабливаются в примере, в видео?
@АлексСандрийский
@АлексСандрийский 5 жыл бұрын
)))
@antonio8778
@antonio8778 5 жыл бұрын
Могу ошибаться, но у вас есть ошибка в процессе применения кроссовера. 4:57. Обратите внимание на получения второго поколения. Согласно схемы применения кроссовера, первый ген второй хромосомы (b - хромосома, ген x), должен был отнаследоваться к хромосоме a второго поколения, ген x. Похоже, как и все остальные гены, по мимо наследования от хромосомы a первого поколения
@ramsakhmitzy6718
@ramsakhmitzy6718 4 жыл бұрын
да, перепутал местами столбики. Не важно, но тем не менее. Тягостное впечатление от всего этого. Не может ясно показать такие простые вещи. Хуже всего, что это дается как какое-то заклинание типа гарри поттера. А где рассуждения о сходимости, о скорости сходимости, и т.д. Почему вообще это будет работать? Ссылка на Дарвиновский отбор -это для идиотов. Надо программу демонстрировать с ответом. не важно джава-хуява или что - программа будет простой в этом случае. Пример лектора, который давно остановился в развитии, но уж наверно на ученых советах восседает в первых рядах...
@antonio8778
@antonio8778 4 жыл бұрын
@@ramsakhmitzy6718 Не могу говорить за Россию, но в Украине это ещё нормальный вариант преподавателя. Есть конечно и молодые, амбициозные, находящиеся постоянно в тренде, но часто встречаются и настоящие динозавры, как по возврасту, так и по характеру.
@stano.marochok
@stano.marochok Жыл бұрын
@@ramsakhmitzy6718 та хз тут задача была скорее принцип объяснить и мужик вроде нормально все объясняет
@maridat47
@maridat47 5 жыл бұрын
Я сделал программу по этому принципу и узнал, что максимум этой функции равен 0.5 примерно в точке x: 1.000362 y: -0.000275
@krenciak
@krenciak 4 жыл бұрын
У меня получилось 0.5 в (1; 0) Вот мой код: gist.github.com/balgor36/a5c8a834ba30d06ee07a59a6023498f2 Конечная популяция записывается в файл data.txt Для увеличения производительность можно использовать флаги оптимизации (например, O2).
@twobomb3
@twobomb3 4 жыл бұрын
Сделал на Javascirpt, визуальное нахождение jsfiddle.net/twobomb/63kLjq7z/
@nighthunter28
@nighthunter28 4 жыл бұрын
@@twobomb3 Math.round нужно заменить на Math.floor, а то также 4 элемент выбирается, который не нужен.
@МаркСтручков-з3ы
@МаркСтручков-з3ы 8 жыл бұрын
Как в итоге понять то, что достигнут нужный конечный результат?
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
Это условно все. Не меняется ответ (с точностью до некоторой малой величины) - значит конец работы. Но один из основных минусов подобных алгоритмов - возможность попадания в локальный минимум (экстремум).
@nRADRUS
@nRADRUS 8 жыл бұрын
если мутации будут в т.ч. сильными, то и из локального минимума можно выйти. также неплохо практиковать двойные-тройные-энные мутации, как и в природе, где гены белков повторяются многократно, что позволяет одним генам работать (и позволять организму жить), а другим - мутировать несколько раз, переносясь в очень дальние следующие поколения...
@volandku
@volandku 6 жыл бұрын
Ага. А как с ним бороться? Я на практике стокнулся с вырождением потомства в район локального экстремума, есть простые методы борьбы с этим?
@_den_
@_den_ 6 жыл бұрын
@@volandku "если мутации будут в т.ч. СИЛЬНЫМИ, то и из локального минимума можно выйти" из сообщения выше
@Amid_Vok
@Amid_Vok 2 жыл бұрын
2:25 Кроссинговер - Кроссоверинг
@MrGRMichael
@MrGRMichael 5 жыл бұрын
не понятнен источник самой функции. как выводится этот закон?
@alexandersobolev2769
@alexandersobolev2769 4 жыл бұрын
Какой закон? Это просто _какая-то_ функция, на примере которой демонстрируется генетический алгоритм поиска максимума функции. Можно взять _любую другую_ функцию нескольких переменных (лишь бы только у нее в принципе были точки максимумов или минимумов) и найти тем же алгоритмом точки максимума уже для этой другой функции
@nighthunter28
@nighthunter28 4 жыл бұрын
источник тут только один - матанализ, раздел экстремума функции, там узнаете про ваш "закон" и порядок (производной).
@denispashnev912
@denispashnev912 6 жыл бұрын
Где используют генетические алгоритмы? Какой от них толк?
@Kirsanov2011
@Kirsanov2011 6 жыл бұрын
Как раз именно они наиболее востребованы там, где много всяких факторов и надо найти экстремум. Фактически, это метод умного перебора. Область применения обширнейшая.
@denispashnev912
@denispashnev912 6 жыл бұрын
@@Kirsanov2011 можете привести пример? Реального приложения, которое использует генетические алгоритмы?
@wugu42
@wugu42 6 жыл бұрын
@@denispashnev912 Ты сам являешься результатом работы такого алгоритма. :)
@ТарасМаковейчук
@ТарасМаковейчук 4 жыл бұрын
А как насчёт устойчивости?
@elenagaranina5904
@elenagaranina5904 2 жыл бұрын
зависает в локальных экстремумах. Если их несколько, то надо насыпать много особей по всему пространству, чтобы хоть одна тварь да провалилась в глобальный. Если раньше не сдохнет. Частенько пространство такое, что все радостно ползут в уютный локальный экстремум потому что глобальный расположен неудобно. Сходится медленно. Ресурсы жрёт как не в себя. Одно достоинство - очень прост в реализации. Для простеньких задач норм.
@obrkn
@obrkn 6 жыл бұрын
Здравствуйте. Может, Вы поможете мне разобраться с этим моментом: Вероятность мутации это Pm. Она берется в диапазоне от 0 до 1. Каждому гену в хромосоме присваиваются случайные числа от 0 до 1. Если вероятность Pm больше либо равна этим числам то происходит мутация (с 0 на 1). Это то, что мне удалось понять о мутации. Но каким образом происходит присваивание случайных чисел каждому гену?
@Kirsanov2011
@Kirsanov2011 6 жыл бұрын
Не всегда ген это 0 или 1. Может быть и десятичное число. Ну и давайте случайному номеру гена случайное число.
@madiyetov
@madiyetov 8 жыл бұрын
При отборе из первого поколения, у=0 остался не использованным, а ведь если использовать этот ген максимизация была бы еще лучше, или я что то не понял?
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
Это конечно, сильно упрощенная схема. На практике хромосома длиннее, больше объектов, все используется в многочисленных итерациях. Я дал только суть.
@ЖандосКуандиков
@ЖандосКуандиков 8 ай бұрын
ИИ✔
@Валерка-о8ф
@Валерка-о8ф 5 жыл бұрын
Ну этот алгоритм больше похож на сортировку перебором. Если вы хотите провести аналогию с биологической эволюцией, то я вас немного поправлю.
@Валерка-о8ф
@Валерка-о8ф 5 жыл бұрын
Вы рассматриваете два гена тетраплоидного набора хромосом (четыре хромосомы) - четыре аллели двух генов. Проще наверное разбираться с диплоидным - двойным набором хромосом, это нагляднее и распространеннее в природе. Тогда х и у на вашей схеме - это две хромосомы от разных родителей. Получается по два аллеля каждого гена: -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] - такой вариант практически невозможен в этом примере, если мы говорим о биологическом алгоритме.
@Валерка-о8ф
@Валерка-о8ф 5 жыл бұрын
Не могу судить о том, какие алгоритмы лучше подходят для решения уравнений, но при моделировании алгоритма биологической эволюции нужно учитывать некоторые закономерности: 1. Рецессивный признак, как правило - умеренно вредная мутация, но вредная только на каком-то прошедшем отрезке эволюционного процесса, относительно стабильных условий на этом отрезке времени. При изменении условий эта мутация может обеспечить адаптацию. Условия в масштабах биологической эволюции это очень непостоянная переменная. Падение метеорита - и все носители, как вы говорите «хороших» или «сильных» генов вымрут за короткое время. А носители вредных вчера рецессивных генов, сегодня могут оказаться наиболее приспосабливаемыми к новым условиям. Естественный отбор уничтожает только категорически вредные мутации, в основном нежизнеспособные в принципе. Не слишком же вредные мутации уходят в подавленное состояние, но не покидают генный пул популяции - это гарантия выживания будущем. То есть при разработке алгоритма, если вы хотите в вашей симуляции не упереться в порог развития и не погубить популяции при смене условий, то нужно сохранять рецессивные признаки. И при симуляции среды для популяций нужно обязательно менять среду - универсальность адаптивности стратегически важнее, чем специализация адаптивности. Популяция может быть вытеснена в другие ниши, но будучи универсальной она выживет, в отличии от «узкоспециализированной» популяции. 2. Аллельные взаимодействия не бинарны - Менделю очень повезло, что в опытах с горохом ему попалось именно полное доминантное взаимодействие, иначе он не обнаружил бы закономерностей. Взаимодействия могут быть и другими: неполное дрминирование, кодоминировпние - пречислять и описывать не буду, но учитывать это надо, так как это тоже несет большое адатаптивное значение. Кроме этого существуют неаллельные взаимодействия, так за один и тот же белок или фермент или рнк монут отвечать гены из разных локусов хромосомы . 3. Нужно учитывать эффект инбридирга и аутбридинга. Чем родственнее генотипы особей, тем гомозиготнее и слабее будет их потомство. Менее родственные особи дадут более гетерозиготное и более сильное потомство. Эффект гетерозиса. 4. При симуляциях биологической эволюции нужно учитывать влияние других популяций, скрещивание с которыми невозможно, но в процессе симбиоза или паразитирования может произойти горизонтальный обмен генами - тоже мощнейший фактор изменчивости. 5. Нужно учитывать экзогенные мутации, которые происходят в процессе онтогенеза - это абсолютно случайные изменения генов под воздействием внешних небиологических факторов: вредностей, излучений итп. Ну примерно так будет довольно близко к биологической эволюции, без учёта эпигенетических и социальных факторов наследственной передачи. Это разумеется если нужно имитировать именно биологическую модель. Если алгоритм предназначен для решения конкретной прикладной задачи, то конечно больший вес будет иметь его адаптация именно к этой задаче, без стратегии предполагающей, что задача может измениться.
@balabuyew
@balabuyew 6 жыл бұрын
Мутация важней чем кроссовер. Так как у вас показано вообще работать не должно.
@edryahlov
@edryahlov 6 жыл бұрын
они работают в тандеме... одно без другого - хаос
ИМРС 4.4 Имитация отжига
14:54
Ivan Borisov
Рет қаралды 1,4 М.
黑天使被操控了#short #angel #clown
00:40
Super Beauty team
Рет қаралды 61 МЛН
人是不能做到吗?#火影忍者 #家人  #佐助
00:20
火影忍者一家
Рет қаралды 20 МЛН
Число маршрутов в графе
19:12
Kirsanov2011
Рет қаралды 6 М.
Метод отжига
25:51
Kirsanov2011
Рет қаралды 18 М.
Искусственная жизнь. Генетический алгоритм. Мир №1
20:15
Генетические алгоритмы
25:01
MoscowPython
Рет қаралды 5 М.
Муравьиный алгоритм
37:01
Kirsanov2011
Рет қаралды 45 М.
Алгоритм Дейкстры
10:35
Kirsanov2011
Рет қаралды 151 М.
Сеть Хопфилда
24:33
Kirsanov2011
Рет қаралды 78 М.
黑天使被操控了#short #angel #clown
00:40
Super Beauty team
Рет қаралды 61 МЛН