Кошмар Дженкина и генетические алгоритмы

[B3LYP]

https://ru.wikipedia.org/wiki/Кошмар_Дженкина

Цитата:

В июне 1867 года в журнале «North British Review» вышла в свет статья Дженкина под названием «Происхождение видов», где критиковалась идея естественного отбора как движущей силы эволюции[1]. Главный пункт возражения Дженкина — поглощающее влияние свободного скрещивания. Чтобы понять его суть, предположим, что в популяции появилась особь с более удачным признаком, чем у существующих особей. Но скрещиваться она вынуждена будет только с особями с «нормальными» признаками. Поэтому через несколько поколений удачное новоприобретение неизбежно будет поглощено «болотом» обычных признаков[2].

Цитата:

…Представим себе белого человека, потерпевшего кораблекрушение на острове, населённом неграми… Наш выживший герой, возможно, станет среди них королём; он убьёт очень много чернокожих людей в борьбе за выживание; он заведёт очень много жён и детей, в то время как множество его подданных будут жить холостяками и умрут холостяками… Качества и способности нашего белого человека несомненно помогут ему дожить до глубокой старости, но даже его длинной жизни явно не хватит для того, чтобы кто-то из его потомков в каком-либо поколении стал полностью белым… В первом поколении будет несколько дюжин смышлёных молодых мулатов, чей ум будет в среднем превосходить негритянский. Нас не удивит, что трон в течение нескольких поколений будет принадлежать более или менее желтокожему[Ком. 1] королю; но сможет ли поверить кто-то, что население всего острова постепенно станет белым или пусть даже жёлтым?..

В нашем случае признак попал в исключительно благоприятные условия, способствующие его сохранению, — способствующие, и всё же неспособные закрепить и сохранить его.

Возможно я не очень понял суть идеи Дженкина, но такое ощущение что он сам не совсем корректно сформулировал то, что интуитивно почувствовал. Это вопрос из области кибернетики. Мы считаем что мозг – это некое сложное устройство, в чём-то похожее на искусственную нейросеть. Предположим, у какого-то человека мозг работает особенно эффективно. Если он женится на обычной женщине, то мозг ребёнка должен быть некой мешаниной двух конструкций. Это подобно тому, как мы купили две соковыжималки, случайно перемешали их детали и пытаемся из них создать гибридную соковыжималку. Другая аналогия: насколько я знаю, ДНК это вообще “программный код”, последовательность инструкций. Если мы возьмём две программы и случайно перемешаем их фрагменты – получится что-то работающее? Очевидно что нет.
У меня вопрос к знатокам Computer science: генетические алгоритмы не подразумевают никакого скрещивания, обмена фрагментами кода, полового отбора?

[Aritaborian]

А почему же они, по-вашему, называются генетическими? И скрещивание есть, и мутации, и отбор. Насчёт полового отбора только не уверен.

[EUgeneUS]

B3LYP в сообщении #1589642 писал(а):

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

Не подобно.

[mihaild]

В генетических алгоритмах не программный код перемешивается. А вводится какое-то пространство параметров, описывающих интересующий нас объект, и вот эти параметры перемешиваются.
Полового отбора как правило нет, потому что тип скрещивания обычно один.
Игрушечная иллюстрация генетического алгоритма - построение 2d машинок https://rednuht.org/genetic_cars_2/.

[ozheredov]

B3LYP в сообщении #1589642 писал(а):

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

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

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

[B3LYP]

mihaild в сообщении #1589649 писал(а):

В генетических алгоритмах не программный код перемешивается. А вводится какое-то пространство параметров, описывающих интересующий нас объект, и вот эти параметры перемешиваются.

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

ozheredov в сообщении #1589657 писал(а):

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

Вы серьёзно? В генетических алгоритмах есть скрещивания?

Я это не очень всё понимаю. Программисты часто берут друг у друга фрагменты кода, но это невозможно без эвристики, понимания где что поправить. Наверно никто не вставляет в свой код случайный фрагмент чужого кода. Я сам программист если что.
Ещё по теме: читал, что бесполые бактерии могут обмениваться участками ДНК, возможно это называется кроссинговером, а Марков называет это "сексом". Если биологи изучили как это работает, это был бы ответ на мой вопрос.

[mihaild]

B3LYP в сообщении #1589705 писал(а):

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

А Вы почитайте код, понятнее станет:) В частности, генерацию нового поколения.
Если совсем на пальцах - объект (машинка в данном случае) описывается некоторой структурой с фиксированным набором полей. Теперь мы берем две машинки, и делаем из них третью, выбирая каждое поле случайно из первой или второй.

[Aritaborian]

B3LYP в сообщении #1589705 писал(а):

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

Перестаньте цепляться за неверное представление об «обмене фрагментами кода». Вам уже объяснили, что всё совсем не так работает.

[Dmitriy40]

А я вот подумываю иногда замутить эволюцию именно что кусков кода (с точностью до отдельной команды процессора), вдруг мой слабенький ЕИ не может додуматься до какой-то хитрой комбинации пары десятков команд, дающей существенный прирост скорости вычислений ... Причём основания для этого есть: не так уж давно придумал как изменением всего нескольких команд увеличить скорость в разы, хотя до этого проц и так был занят на 80%-90%. Останавливают три вещи: а) лень, слишком много писанины без надежды на результат; б) не вполне понятна функция отбора, если оставлять в живых только правильно работающие программы, то они все умрут в первом же поколении, а неправильно работающих больше на порядки; в) 100% взаимозависимость вычислительного куска кода с подготовительным (генерации таблиц и констант), который в разы длиннее, менять только один бессмысленно, но как менять оба ещё большой вопрос, да и сложность (количество вариантов) резко растёт, а скорость поиска решений падает.

[B3LYP]

mihaild в сообщении #1589706 писал(а):

А Вы почитайте код, понятнее станет:) В частности, генерацию
нового поколения.

Вы предлагаете разобрать только функцию nextGeneration? Немного лень думать над кодом, тем более что я не знаток C++.

mihaild в сообщении #1589706 писал(а):

Если совсем на пальцах - объект (машинка в данном случае) описывается некоторой структурой с фиксированным набором полей. Теперь мы берем две машинки, и делаем из них третью, выбирая каждое поле случайно из первой или второй.

Ну так и под обменом участками кода я имел в виду примерно то же - не обмен машинным кодом или ассемблерными вставками, а обмен функциями, классами и т.д. Всё равно же это не получится.
Попробую ещё раз сформулировать свою мысль. Полагаю, в кибернетике должно быть что-то вроде "теоремы о необходимости самосогласованности составных элементов": в той же соковыжималке размеры всех деталей подогнаны друг к другу с точностью до микрометра, поэтому если взять детали разных соковыжималок, собрать ничего не получится.
Должны быть признаки, реализованные по-разному с точки зрения кибернетики. Например, рост - признак с высокой наследуемостью и без таких проблем. Когда мать и отец рожают ребёнка, его рост будет примерно усредненным по их росту(естественно с поправкой на половой диморфизм). Если бы интеллект был таким же признаком как рост, никакого "кошмара Дженкина" не было бы. Т.е. в популяции мужчина с IQ 120 женился бы на женщине с IQ 100, у их ребёнка был бы IQ 110, и если иметь высокий IQ выгодно - таких детей рождалось бы в среднем больше, соответственно средний IQ рос бы. Но Дженкин очевидно имел в виду другое.

[B3LYP]

B3LYP в сообщении #1589793 писал(а):

тем более что я не знаток C++

Сорри, в смысле javascript.

[EUgeneUS]

Dmitriy40 в сообщении #1589753 писал(а):

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

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

[mihaild]

B3LYP в сообщении #1589793 писал(а):

Ну так и под обменом участками кода я имел в виду примерно то же - не обмен машинным кодом или ассемблерными вставками, а обмен функциями, классами и т.д. Всё равно же это не получится.

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

B3LYP в сообщении #1589793 писал(а):

Если бы интеллект был таким же признаком как рост, никакого "кошмара Дженкина" не было бы.

Кошмар Дженкинса совершенно про другое, а именно про размывание признаков. В Вашем примере - после смерти мужчины с IQ 120 в популяции уже не остается, и никогда не будет, IQ выше 110. А после смерти его детей, если их супруги тоже были из местных с IQ 110 - не останется никого с IQ выше 105.
Рассуждения правильные, но исходят из неверной посылки - непрерывности признаков. На самом же деле признаки наследуются дискретно, и у пары с IQ 120 и 100 вместо детей с IQ 110 будет часть детей с IQ 120 и часть с IQ 100. Дальше предположительно дети с IQ 120 тоже оставят больше потомства, и в итоге у всех будет IQ 120.
(тут конечно всё сильно сложнее, потому что IQ задается кучей генов, а не одним, и для одного гена есть как минимум три состояния - два гомозиготных и одно гетерозиготное; но общая идея такая; к генетическим алгоритмам это, впрочем, имеет отдаленное отношение)

[B3LYP]

mihaild в сообщении #1589847 писал(а):

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

Мне было бы интересно понять как это конкретно реализовано, хотя я не буду доставать всех вопросами, надеюсь со временем узнаю больше; пока такой вопрос - может ли это быть интересно практически мне как программисту, для решения каких-то задач? Или, если уж так ставить вопрос, надо изучать нейросети/ансамбли а вовсе не GA?

Вот тут написано, что генетические алгоритмы не имеют никакой практической ценности:

https://vas3k.blog/blog/machine_learning/

mihaild в сообщении #1589847 писал(а):

Кошмар Дженкинса совершенно про другое, а именно про размывание признаков. В Вашем примере - после смерти мужчины с IQ 120 в популяции уже не остается, и никогда не будет, IQ выше 110. А после смерти его детей, если их супруги тоже были из местных с IQ 110 - не останется никого с IQ выше 105.

Как я уже сказал, ощущение что Дженкин сам не смог сформулировать идею, которую он почувствовал интуитивно. Грубо говоря, если живёт популяция людей, за счёт мутаций некоторые из них получают IQ выше среднего, допустим 102%; далее они женятся и у их детей остаётся 101%, и далее размывается как вы описали; но мужчины с IQ ниже среднего, грубо говоря 98%, оставляют в среднем меньше детей, чем мужчины с 102%, соответственно за счёт естественного отбора средний IQ повышается.

mihaild в сообщении #1589847 писал(а):

Рассуждения правильные, но исходят из неверной посылки - непрерывности признаков. На самом же деле признаки наследуются дискретно, и у пары с IQ 120 и 100 вместо детей с IQ 110 будет часть детей с IQ 120 и часть с IQ 100. Дальше предположительно дети с IQ 120 тоже оставят больше потомства, и в итоге у всех будет IQ 120.

Я уже слышал, что открытия Менделя и их подтверждения из генетики типа опровергли тезисы Дженкина. Я это совершенно не понимаю, и мои аргументы сводятся всё к тем же соковыжималкам. Надеюсь, меня тут не запишут в креационисты.

[Geen]

B3LYP в сообщении #1589857 писал(а):

мои аргументы сводятся всё к тем же соковыжималкам

Живые организмы даже близко не похожи на соковыжималки. Поэтому перестаньте повторять этот "аргумент".