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

Sdílet
Vložit
  • čas přidán 8. 10. 2014
  • Описание работы генетического алгоритма на примере поиска максимума функции двух переменных. Берем 4 случайные хромосомы (4 случайные точки), отбираем лучшую с точки зрения максимума функции. Затем лучшая хромосома (в данном случае - точка) наследует новому поколению все свои гены (координаты х и у). Худшая вылетает из процесса. И т.д.

Komentáře • 51

  • @user-bx5xv7gg6k
    @user-bx5xv7gg6k Před 6 lety +16

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

  • @user-bi4mr3wi8i
    @user-bi4mr3wi8i Před 8 lety +22

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

  • @s1___
    @s1___ Před 6 lety +9

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

  • @onocomments4115
    @onocomments4115 Před 6 lety +3

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

  • @valeriyblinov1573
    @valeriyblinov1573 Před rokem

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

  • @caseng1270
    @caseng1270 Před 3 lety +1

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

  • @ynxela
    @ynxela Před 5 lety +3

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

  • @blackbigdeath
    @blackbigdeath Před 3 lety +1

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

  • @freaxlover
    @freaxlover Před rokem

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

  • @user-jl3ci9zv1n
    @user-jl3ci9zv1n Před 3 lety

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

  • @maridat47
    @maridat47 Před 5 lety +10

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

    • @krenciak
      @krenciak Před 4 lety +1

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

    • @twobomb3
      @twobomb3 Před 4 lety +2

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

    • @nighthunter28
      @nighthunter28 Před 4 lety

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

  • @darkeliphant1843
    @darkeliphant1843 Před 6 lety +25

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

    • @Kirsanov2011
      @Kirsanov2011  Před 6 lety +6

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

    • @hydrobusy8522
      @hydrobusy8522 Před 6 lety +2

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

    • @user-ce8yq6so3z
      @user-ce8yq6so3z Před 4 lety

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

    • @user-xh7hw4ck9z
      @user-xh7hw4ck9z Před 4 lety

      )))

  • @Amid_Vok
    @Amid_Vok Před rokem

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

  • @obrkn
    @obrkn Před 6 lety

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

    • @Kirsanov2011
      @Kirsanov2011  Před 6 lety +1

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

  • @madiyetov
    @madiyetov Před 7 lety

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

    • @Kirsanov2011
      @Kirsanov2011  Před 7 lety

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

  • @antonio8778
    @antonio8778 Před 4 lety +2

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

    • @ramsakhmitzy6718
      @ramsakhmitzy6718 Před 3 lety

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

    • @antonio8778
      @antonio8778 Před 3 lety

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

    • @stano.marochok
      @stano.marochok Před 6 měsíci

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

  • @user-xu7mf5iw9s
    @user-xu7mf5iw9s Před 7 lety +2

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

    • @Kirsanov2011
      @Kirsanov2011  Před 7 lety +2

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

    • @nRADRUS
      @nRADRUS Před 7 lety +2

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

    • @volandku
      @volandku Před 5 lety +1

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

    • @_den_
      @_den_ Před 5 lety

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

  • @user-ix9nv7th8g
    @user-ix9nv7th8g Před 7 lety +1

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

    • @Kirsanov2011
      @Kirsanov2011  Před 7 lety +3

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

  • @denispashnev912
    @denispashnev912 Před 5 lety

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

    • @Kirsanov2011
      @Kirsanov2011  Před 5 lety +4

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

    • @denispashnev912
      @denispashnev912 Před 5 lety

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

    • @wugu42
      @wugu42 Před 5 lety +11

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

  • @user-sz2fz2ij8r
    @user-sz2fz2ij8r Před 4 lety

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

    • @user-sz2fz2ij8r
      @user-sz2fz2ij8r Před 4 lety +3

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

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

  • @user-ub6wt5nl5b
    @user-ub6wt5nl5b Před 4 lety

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

    • @elenagaranina5904
      @elenagaranina5904 Před rokem

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

  • @MrGRMichael
    @MrGRMichael Před 4 lety +1

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

    • @alexandersobolev2769
      @alexandersobolev2769 Před 4 lety +2

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

    • @nighthunter28
      @nighthunter28 Před 4 lety +1

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

  • @user-ob1yb6xs3w
    @user-ob1yb6xs3w Před 2 měsíci

    ИИ✔

  • @balabuyew
    @balabuyew Před 6 lety

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

    • @edryahlov
      @edryahlov Před 6 lety +1

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