со-основатель Hexlet.io
202,7
рейтинг
1 ноября 2013 в 10:42

Разработка → Эволюция и генетические алгоритмы

Позвали прочитать открытую лекцию в алматинскую «Ракетную фирму». Ограничений в темах не было, поэтому я решил в очередной раз попробовать рассказать про эволюцию и генетические алгоритмы.

Почему верить в эволюцию – глупо, почему эволюция это не «всего лишь теория», где же все связующие звенья среди ископаемых, почему мы не происходили от обезьян и как работают генетические алгоритмы.



P.S. Лекция записывалась на камеру (полную версию в не очень хорошем качестве можно посмотреть здесь), поэтому извиняюсь за не самое хорошее качество звука.
Рахим Давлеткалиев @freetonik
карма
508,5
рейтинг 202,7
со-основатель Hexlet.io
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (20)

  • +2
    9:30
    Вроде выживает не самый сильнейший, а тот, кто лучше адаптируется?..
    Это не обязательно Дарвин сказал, но идея, как мне кажется, вполне резонная.
    • +1
      Да, конечно, тот кто лучше адаптируется. «Выживает сильнейший» просто сказано в качестве популярного «описания» эволюции. Сила у многих видов является способом адаптации.
      • +2
        Ну это понятно. =))
        Просто такие «популярные описания» культивируют культ силы, что ИМХО не есть хорошо…
        Я здесь говорю не конкретно про студентов, а вообще, как сложилось в обществе.
        Может стоит потихоньку уходить от этого или делать дополнительные разъяснения по этому поводу?
        Вот как я например тут прицепился к вам. =))
        • +1
          Вы правы, конечно. Уходить стоить, и в этой лекции стоило поднять эту тему.
          • +1
            Вы уж простите мне мои придирки. =))
            А вообще лекция очень интересная, спасибо.
            • +1
              Что вы, это не придирки, а справедливая критика.
              Спасибо вам!
  • +8
    Критика от биолога — извиняюсь за занудство, но вижу подобные ошибки уже не в первый раз и поэтому решил высказаться :)

    С одной стороны, я понимаю, что целью этой лекции не является детальное объяснение теории эволюции — целью являются генетические алгоритмы. С другой стороны, первую часть лекции автор говорит именно о биологической эволюции, «развенчивая» мифы и тд. К изложению генетических алгоритмов вопросов нет, вопросы есть к изложению теории эволюции.

    Во-первых, изложение теории эволюции очень поверхностное, на уровне конца 19 века :) Про 20й век забыли, не упомянут, например, ключевой для современного понимания эволюции нейтрализм Кимуры, опущен самый важный акцент СТЭ — единицей эволюции является популяция, а не особь (возможно, потому что в генетических алгоритмах эволюционируют именно особи — что является еще одной иллюстрацией того, что генетические алгоритмы весьма далеки от механизмов реальной биологической эволюции)

    К вопросу о наблюдении эволюции — то, что микроэволюция наблюдается за 16-18 часов, например, на фагах, это абсолютная правда. А макроэволюция уже тоже наблюдается? ;)

    В «минутку мракобесия» набраны какие-то старые стереотипы. Есть же по-настоящему интересные проблемы, например: переходит ли большое количество микроэволюционных событий в полноценную макроэволюцию (образование новых родов, например)? Плюс старая проблема эволюции сложных систем (irreducible complexity и все такое).
    Еще есть вопрос численных оценок времени, требуемого для эволюции. Если кратко, сейчас можно оценить, с одной стороны, частоту мутаций (количество мутаций за единицу времени), с другой — необходимое число мутаций для того, чтобы образовалась разница между геномами двух достаточно далеких друг от друга организмов. Дальше делается численная оценка времени, необходимого для такой эволюции — и она никак не совпадает с наблюдаемой, разрыв в несколько порядков. Пичалька. То-ли считаем неправильно (хотя peer-reviewers прокол найти не могут), то-ли есть неизвестные науке механизмы, ускоряющие эволюцию, то-ли Творец все-таки существует :)

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

    Подытожу: автор говорит о теории эволюции с целью подвести слушателей к идее генетических алгоритмов. Так как генетические алгоритмы построены на принципах, заметно отличающихся от современного понимания принципов и механизмов эволюции, то и рассказ о биологической эволюции получился не очень корректным. Что с этим делать, непонятно — вроде как, на самом деле, глупо вначале говорить вначале об одних принципах для биологической эволюции, а потом говорить, что генетические алгоритмы построены на немного других принципах. Если же оставлять рассказ об эволюции в текущей форме — он получается некорректным с научной точки зрения, эволюция работает слегка по-другому.

    Как-то так…
    • +1
      Большое спасибо за ваш комментарий!

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

      В «минутку мракобесия» набраны какие-то старые стереотипы.

      Старые, но все еще очень распространенные (опять же – особенно в США). Ну, и опять же – лекция больше попсовая, чем научная, поэтому были выбраны наиболее «раздражающие» и «желтые» стереотипы.

      Олег, а вы случайно не преподаете? Приходите к нам в hexlet.org :)
      • +1
        Я в лаборатории работаю, плюс студентов/аспирантов работать учу.

        Лекции я бы с удовольствием почитал, но времени на постоянное чтение лекций нет :(
        Если время появится, то приду, спасибо за приглашение! :)
        • +2
          Хорошо!
          Я буду время от времени напоминать вам, если вы не против :)
    • +2
      Согласен про преподавание на хекслете. Я бы послушал с удовольствием курс по современным представлениям о теории эволюции.
    • +2
      опущен самый важный акцент СТЭ — единицей эволюции является популяция, а не особь (возможно, потому что в генетических алгоритмах эволюционируют именно особи — что является еще одной иллюстрацией того, что генетические алгоритмы весьма далеки от механизмов реальной биологической эволюции)

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

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

      Опять же можно подробнее указать, в чем на ваш взгляд основное отличие, и почему оно принципиально?

      • +1
        Про наследственность, изменчивость и отбор — все верно. Если они есть, какая-то эволюция будет. Весь вопрос в более тонких механизмах, которые работают в реальной биологии. В биологии очень сложно организованные системы выживают в сложных условиях среды (где нет однозначно заданной целевой функции), поэтому есть куча мелких нюансов в реальных механизмах эволюции. В генетических алгоритмах — есть четко определенная целевая функция, «хромосома» особей организована очень просто — система является очень простой моделью.

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

        Например, есть области генома, в которых мутации происходят чаще, в других — реже. Это связано не столько с отбором, сколько напрямую с локальной структурой ДНК — в некоторых местах ошибки при репликации возникают чаще, чем в других. Понятно, что все эти тонкости не учитываются в генетических алгоритмах. Есть регуляторные участки ДНК — мутации в них не меняют структуры белков, но меняют уровень или время и место синтеза одного или нескольких белков. Это важно для реальной эволюции, но не важно для решения оптимизационных задач генетическими алгоритмами.

        Сейчас становится понятно, что мутаций (SNP и прочее) много. Однако большинство из них — нейтральны для данных условий среды. Только вот условия среды порой меняются, и тогда нейтральные мутации уже становятся значимыми — дают преимущество, или наоборот. По современному представлению, эволюция работает примерно так. Есть популяция — набор особей, живущих в одном месте и скрещивающихся. Эта популяция является по сути пулом генетической информации, в котором есть множество вариантов одного и того же гена, чаще всего эти отличия нейтральны или минорны, но есть и существенно отличающиеся варианты. Дальше начинаются новые уровни сложности, связанные с комбинаторикой: один ген влияет на много признаков, каждый признак определяется несколькими генами, но отбор идет по признакам, а не генам!
        В результате у конкретных особей возможны очень интересные игры, основанные на комбинациях. Например, мутация гена А — условно «смертельна», мутация другого гена Б — «смертельна», а комбинация А и Б — прекрасно жизнеспособна. Поэтому даже «плохие» гены остаются в популяции, есть рецессивные признаки и так далее. Если же условия среды меняются, то нейтральные ранее признаки становятся значащими, «плохие» для старых условий гены могут стать «полезными» в новых — изменение условий приводит к интенсивному изменению генетического пула. Пул — штука динамическая, меняется со временем — меняются соотношения разных вариантов генов. Эволюция — это процесс, происходящий со всем пулом, а не с отдельными особями-носителями конкретных вариантов генов. Нужно поддержание разнообразия генетического пула — иначе популяция не сможет пережить изменение условий среды. Собственно, у природы и нет задачи вывести наиболее приспособленного «супермена» — приспособленный к одним условиям «супермен» окажется инвалидом в новых измененных условиях. В реальной природе среда меняется достаточно часто, так что некое «равновесное» состояние для популяции может никогда и не наступить — изменение условий выбивает систему из равновесия, запуская новый виток приспособления — это и есть эволюция.

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

        Я абсолютно согласен, что все эти сложности не нужны для решения реальных задач типа поиска на графах. Однако отсутствие этих сложностей в генетических алгоритмах не позволяет назвать их хорошими моделями для биологической эволюции. Это крайне упрощенные модели для решения гораздо более простых задач, чем превращение бактерии в человека :)
        • 0
          Согласен с перечисленными вами эффектами, но мне все-таки кажется вывод вы делаете не совсем корректный. Сначала вы пишите
          Так как генетические алгоритмы построены на принципах, заметно отличающихся от современного понимания принципов и механизмов эволюции, то и рассказ о биологической эволюции получился не очень корректным.

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

          . По современному представлению, эволюция работает примерно так. Есть популяция — набор особей, живущих в одном месте и скрещивающихся. Эта популяция является по сути пулом генетической информации, в котором есть множество вариантов одного и того же гена

          Ну так в ГА как правило тоже самое. Особи популяции скрещиваются между собой, в результате гены как правило представлены большим числом копий. А если присутствует фактор случайности, то отдельная особь даже с идеальными генами может не оставить потомства. В ГА, как и в природе, популяций может быть несколько и они лишь изредка обмениваются генетическим материалами. Это называется «островная модель».

          Например, мутация гена А — условно «смертельна», мутация другого гена Б — «смертельна», а комбинация А и Б — прекрасно жизнеспособна.

          Ну в генетическом программировании, например, тоже вполне может быть, что два различных участка программы взаимодействуют нетривиальным образом их синхронное изменение дает совсем не такой эффект как по отдельности.

          Изменение условий можно сравнить с изменением целевой (оценочной) функции — однако для реальных задач, решаемых генетическими алгоритмами, такое изменение вряд ли будет полезно :)

          Ну тут опять же зависит от задачи. Например, читал что-то про эксперимент, где системе ГП подсовывали сначала какие-то простенькие задачи, а потом уже меняли на более сложные. И результат был лучше, чем если бы сразу давали сложные, т.к. особи в популяциях использовали свои «наработки» в решении более сложной задачи. Или же, допустим, есть задача найти алгоритм поведения в игре. Тогда можно заставить особей играть друг с другом (так, например, сделано у нас в амёбах). Получается что приспособленность зависит от поведения других особей, и они естественно будут меняться со временем.

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

          Ну генетическому алгоритму тоже вообще-то ничего не надо, просто есть процедура отбора, которая куда-то тащит систему. Это создателю алгоритма может быть что-то надо от алгоритма :) И то не факт, что он получит именно то, что хотел.

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

    • 0
      Еще есть вопрос численных оценок времени, требуемого для эволюции. Если кратко, сейчас можно оценить, с одной стороны, частоту мутаций (количество мутаций за единицу времени), с другой — необходимое число мутаций для того, чтобы образовалась разница между геномами двух достаточно далеких друг от друга организмов. Дальше делается численная оценка времени, необходимого для такой эволюции — и она никак не совпадает с наблюдаемой, разрыв в несколько порядков. Пичалька. То-ли считаем неправильно (хотя peer-reviewers прокол найти не могут), то-ли есть неизвестные науке механизмы, ускоряющие эволюцию, то-ли Творец все-таки существует :)


      а где можно про это почитать или узнать поподробнее?
  • –3
    сегодня однозначно понятно что в биологических организмах используется язык программирования
    и его пока никому не удается понять

    любой адекватный программист знает что никакой язык программирования не может возникнуть сам
    и что программа не может создать более совершенную программу

    теория эволюции и самозарождения всего — это для дураков
    в рабовладельческом обществе элите нужно чтобы люди верили в рай или в коммунизм или в самоорганизацию и самоулучшение
    • +3
      Аргумент от сложности — всего лишь домысел. При чем, кучу раз уже опровергнутый.
      1) Эволюция не создает сложное из простого посредством какой-то магии. Это закономерное накапливание маленьких улучшений
      2) Данный аргумент предполагает, что не существует объектов, которые могут производить более сложные объекты, чем они сами. Если бы это было так, то человеческие возможности постепенно деградировали бы со временем, поскольку каждое поколение было бы проще предыдущего
      3) Имеется множество примеров сложности, происходящей из простоты. Фракталы, например. Поразительно сложные кристаллы образуются сами.

      В рабовладельческом обществе же необходима именно фундаментальная религия, а не попытки осознать мир. Через научные теории людьми управлять невозможно.
      • 0
        Через научные теории людьми управлять невозможно.


        А как же «озоновые дыры» и «глобальное потепление»? :)
        Я уже не говорю об экономике.
  • 0
    Для задачи коммивояжёра не используется одноточечный и многоточечный кроссовер. Много мёртвых особей. Долго сходится. Очень долго
  • 0
    Мне показалось очень уместным привести здесь ссылку на лекцию Северинова(это один из монструознейших биологов мира :) Где как раз разбираются поднятые вопросы…

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.