Плоидность

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Введение n-плоидности в генетический алгоритм)
м
 
(9 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{редактирую}}
+
'''Пло́идность''' ('''полиплоидность''', '''n-плоидность''') – число самодостаточных наборов генов в каждой особи популяции генетического алгоритма. Плоидность является дальнейшим усовершенствованием [[классический генетический алгоритм|классического генетического алгоритма]] (в котором все [[классический генетический алгоритм|особи]] '''гаплоидны''', то есть несут в себе одиночный [[классический генетический алгоритм|набор генов]]), которое, возможно, улучшает его поисковые способности.
-
 
+
-
'''Пло́идность''' (полиплоидность, n-плоидность) – число самодостаточных наборов генов в каждой особи популяции генетического алгоритма. Плоидность является дальнейшим усовершенствованием [[классический генетический алгоритм|классического генетического алгоритма]] (в котором все [[классический генетический алгоритм|особи]] '''гаплоидны''', то есть несут в себе одиночный [[классический генетический алгоритм|набор генов]]), которое, возможно, улучшает его поисковые способности.
+
=== Соотношение понятия "плоидность" с естественной генетикой ===
=== Соотношение понятия "плоидность" с естественной генетикой ===
Строка 11: Строка 9:
=== Гипотезы ===
=== Гипотезы ===
-
# Полиплоидность увеличивает информационную “ёмкость” популяции, позволяя обходиться меньшим размером популяции;
+
# Полиплоидность увеличивает информационную «ёмкость» популяции, позволяя обходиться меньшим размером популяции;
-
# Полиплоидность позволяет накопить пул мутаций, которые сделают популяцию менее подверженной “скатыванию в локальный экстремум”;
+
# Полиплоидность позволяет накопить пул мутаций, которые сделают популяцию менее подверженной «скатыванию в локальный экстремум»;
# Полиплоидность ускоряет поиск, разбивая гены на стабильные (доминантные) и на нестабильные (рецессивные).
# Полиплоидность ускоряет поиск, разбивая гены на стабильные (доминантные) и на нестабильные (рецессивные).
 +
 +
=== Эксперименты ===
 +
Известен лишь один эксперимент, использующий полиплоидность (см. третью ссылку). В нём утверждается, что этот эффект помогал избежать локальных экстремумов.
=== Введение n-плоидности в генетический алгоритм ===
=== Введение n-плоидности в генетический алгоритм ===
Строка 26: Строка 27:
# ''Скрещивание: Из популяции каким-либо образом выбираются будущие родители. От каждой родительской особи, путём [[классический генетический алгоритм|кроссинговера]] родительских наборов генов, получаем новый набор генов будущего потомка. Наборы генов потомка собираются в новой особи, которая объявляется потомком''
# ''Скрещивание: Из популяции каким-либо образом выбираются будущие родители. От каждой родительской особи, путём [[классический генетический алгоритм|кроссинговера]] родительских наборов генов, получаем новый набор генов будущего потомка. Наборы генов потомка собираются в новой особи, которая объявляется потомком''
-
: Число родителей имеет смысл брать равным величине плоидности. Т.к. в этом случае родители фактически друг с другом не взаимодействуют, лишь поставляя гаметы (гаплоидные половые клетки) своему потомку. В отличии от [[классический генетический алгоритм|классического генетического алгоритма]], здесь [[классический генетический алгоритм|кроссинговер]] происходит внутри родительских особях, а не между ними. Это может быть дополнительным подспорьем в распараллеливании при реализации алгоритма.
+
: Число родителей имеет смысл брать равным величине плоидности, т.к. в этом случае родители фактически друг с другом не взаимодействуют, лишь поставляя гаметы (гаплоидные половые клетки) своему потомку. В отличии от [[классический генетический алгоритм|классического генетического алгоритма]], здесь [[классический генетический алгоритм|кроссинговер]] происходит внутри родительских особей, а не между ними. Это может быть дополнительным подспорьем в распараллеливании при реализации алгоритма.
# ''Экспрессия: Фенотип особи определяется согласно всем наборам генов, из которых эта особь состоит''
# ''Экспрессия: Фенотип особи определяется согласно всем наборам генов, из которых эта особь состоит''
-
: Можно проявлять фенотип лишь от одного набора генов в особи. Можно проявлять фенотип от конкретного набора случайным образом. Либо усреднять от всех. Но все эти три тактики, видимо, не приводят к какому-либо ускорению поисковых способностей алгоритма. Скорее наоборот. Информация о том, доминантен ли ген или рецессивен, должна, видимо, генерироваться параллельно самим эволюционным процессом, либо каким-то более определённым образом. В этом случае, среди параллельных генов (аллелей) проявляется в фенотипе только тот ген (или с большим вкладом, чем его "конкурент"), которым несёт в себе информацию о своей доминантности. Если же все параллельные гены доминантны (или рецессивны), то кто проявляется в фенотипе определяется случайным образом.
+
: Можно проявлять фенотип лишь от одного набора генов в особи. Можно проявлять фенотип от конкретного набора случайным образом. Либо усреднять от всех. Но все эти три тактики, видимо, не приводят к какому-либо ускорению поисковых способностей алгоритма. Скорее наоборот. Информация о том, доминантен ли ген или рецессивен, должна, видимо, генерироваться параллельно самим эволюционным процессом, либо каким-то более определённым образом. В этом случае, среди параллельных генов (аллелей) проявляется в фенотипе только тот(или с большим вкладом) ген, который несёт в себе информацию о своей доминантности. Если же все параллельные гены доминантны (или рецессивны), то кто проявляется в фенотипе определяется случайным образом.
 +
 
 +
=== Предлагаемый алгоритм определения рецессивности/доминантности ===
 +
Предлагаю следующих алгоритм определения рецессивности/доминантности генов.
 +
Пусть набор генов - битовая строка. Информацию о доминатности представим также в виде битовой строки, в которой 1 означает «соответствующий бит доминантен». Далее:
 +
 
 +
* При первой генерации особи, доминантная битовая строка, как и битовая строка генов, выбирается случайной;
 +
* При мутации бита в гене, доминантность его выставляется в 0;
 +
* При прохождении бита в следующее поколение, его доминантность выставляется в 1 с вероятностью p, примерно равной 0.5;
 +
* (?) Если кроссинговер k-точечный, то какую-то дельта-окрестность бит точек разреза отметить рецессивностью;
 +
* (?) Если кроссинговер сплошной случайный, то каждый бит доминантности выставить в 0 с вероятностью k, где k примерно равно 0.1.
 +
 
 +
Таким образом, более новые гены будут рецессивными, а более стабильные - доминантными.
 +
 
 +
=== Преимущества и недостатки плоидности ===
 +
Преимущества:
 +
* Позволяет избегать локальных экстремумов;
 +
* Добавляет больше простора для распараллеливания.
 +
 
 +
Недостатки:
 +
* Увеличение объёма хранимой информации в разы;
 +
* Увеличение сложности кода;
 +
* Введение новых и непонятных эвристик.
 +
 
 +
=== Почему инцест помогает избежать локальных экстремумов? ===
 +
 
 +
Инцест - скрещивание близкородственных особей.
 +
 
 +
Если частота мутаций недостаточно большая, а целевая функция располагает, то популяция может выродиться в локальную окрестность, в которой будет очень много схожих особей. Скрещивание их в гаплоидном ГА непременно приведёт лишь к усилению застревания популяции в этой точке. В полиплоидном же случае инцест приводит к тому, что начнут себя проявлять рецессивные, ранее не проявляющиеся в фенотипе гены. Таким образом механизм инцеста в полиплоидных организмах позволяет легче выбираться из локальных экстремумов.
=== Источники информации ===
=== Источники информации ===
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%BE%D0%B8%D0%B4%D0%BD%D0%BE%D1%81%D1%82%D1%8C Статья "Плоидность" в Википедии]
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%BE%D0%B8%D0%B4%D0%BD%D0%BE%D1%81%D1%82%D1%8C Статья "Плоидность" в Википедии]
-
* [http://neuroschool.narod.ru/books/evogrbn.html Демон Дарвина...] -- Отлично рассмотрен с точки зрения математики накопительный эффект от рецессивности (см. выше "плоидность");<br />
+
* [http://neuroschool.narod.ru/books/evogrbn.html Демон Дарвина...] -- Отлично рассмотрен с точки зрения математики накопительный эффект от рецессивности;<br />
* [http://masters.donntu.edu.ua/2005/fvti/trubarov/library/kpi_ga.pdf Г. К. Вороновский и др., ''Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности''] -- пример положительного эффекта диплоидности на качество схождения ГА в глобальном экстремуме.<br />
* [http://masters.donntu.edu.ua/2005/fvti/trubarov/library/kpi_ga.pdf Г. К. Вороновский и др., ''Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности''] -- пример положительного эффекта диплоидности на качество схождения ГА в глобальном экстремуме.<br />
 +
 +
[[Категория:Эволюционные алгоритмы]]

Текущая версия

Пло́идность (полиплоидность, n-плоидность) – число самодостаточных наборов генов в каждой особи популяции генетического алгоритма. Плоидность является дальнейшим усовершенствованием классического генетического алгоритма (в котором все особи гаплоидны, то есть несут в себе одиночный набор генов), которое, возможно, улучшает его поисковые способности.

Содержание

Соотношение понятия "плоидность" с естественной генетикой

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

Родительские половые клетки являются гаплоидными. При слиянии они образуют диплоидную клетку – потомка. Совместная экспрессия генов в цепочках ДНК каждого из родителей влияет на фенотип. Но очень часто каждый из параллельных генов в цепочках может доминировать (либо быть затенённым, то есть быть рецессивным) по отношению к другому гену. Тем самым влиять либо нет на финальный фенотип. Механизмы доминантности/рецессивности генов очень разнообразны и до сих пор плохо изучены.

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

Гипотезы

  1. Полиплоидность увеличивает информационную «ёмкость» популяции, позволяя обходиться меньшим размером популяции;
  2. Полиплоидность позволяет накопить пул мутаций, которые сделают популяцию менее подверженной «скатыванию в локальный экстремум»;
  3. Полиплоидность ускоряет поиск, разбивая гены на стабильные (доминантные) и на нестабильные (рецессивные).

Эксперименты

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

Введение n-плоидности в генетический алгоритм

  1. Хранение: Каждая особь популяции владеет n-кратным набором генов (или цепочками ДНК, или n набором хромосом);
  2. Скрещивание: Из популяции каким-либо образом выбираются будущие родители. От каждой родительской особи, путём кроссинговера родительских наборов генов, получаем новый набор генов будущего потомка. Наборы генов потомка собираются в новой особи, которая объявляется потомком;
  3. Экспрессия: Фенотип особи определяется согласно всем наборам генов, из которых эта особь состоит.

Рассмотрим эти три пункта поподробнее:

  1. Хранение: Каждая особь популяции владеет n-кратным набором генов (или цепочками ДНК, или n набором хромосом)
Число n обычно равно двум. Не ясно, имеет ли смысл его брать больше этого значения. В природе оно почти всегда есть 2. Кроме самих генов, необходимо также хранить информацию о доминантности/рецессивности для каждого гена из каждого набора генов, что обычно даёт 2n-кратный рост памяти, занимаемой особью по сравнению с гаплоидной версией. Информация о доминантности сцеплена с геном. Она, также как и гены, подвергается мутациям и перемешивается в процессе кроссинговера. Без этой информации полиплоидность, возможно, бессмысленна.
  1. Скрещивание: Из популяции каким-либо образом выбираются будущие родители. От каждой родительской особи, путём кроссинговера родительских наборов генов, получаем новый набор генов будущего потомка. Наборы генов потомка собираются в новой особи, которая объявляется потомком
Число родителей имеет смысл брать равным величине плоидности, т.к. в этом случае родители фактически друг с другом не взаимодействуют, лишь поставляя гаметы (гаплоидные половые клетки) своему потомку. В отличии от классического генетического алгоритма, здесь кроссинговер происходит внутри родительских особей, а не между ними. Это может быть дополнительным подспорьем в распараллеливании при реализации алгоритма.
  1. Экспрессия: Фенотип особи определяется согласно всем наборам генов, из которых эта особь состоит
Можно проявлять фенотип лишь от одного набора генов в особи. Можно проявлять фенотип от конкретного набора случайным образом. Либо усреднять от всех. Но все эти три тактики, видимо, не приводят к какому-либо ускорению поисковых способностей алгоритма. Скорее наоборот. Информация о том, доминантен ли ген или рецессивен, должна, видимо, генерироваться параллельно самим эволюционным процессом, либо каким-то более определённым образом. В этом случае, среди параллельных генов (аллелей) проявляется в фенотипе только тот(или с большим вкладом) ген, который несёт в себе информацию о своей доминантности. Если же все параллельные гены доминантны (или рецессивны), то кто проявляется в фенотипе определяется случайным образом.

Предлагаемый алгоритм определения рецессивности/доминантности

Предлагаю следующих алгоритм определения рецессивности/доминантности генов. Пусть набор генов - битовая строка. Информацию о доминатности представим также в виде битовой строки, в которой 1 означает «соответствующий бит доминантен». Далее:

  • При первой генерации особи, доминантная битовая строка, как и битовая строка генов, выбирается случайной;
  • При мутации бита в гене, доминантность его выставляется в 0;
  • При прохождении бита в следующее поколение, его доминантность выставляется в 1 с вероятностью p, примерно равной 0.5;
  • (?) Если кроссинговер k-точечный, то какую-то дельта-окрестность бит точек разреза отметить рецессивностью;
  • (?) Если кроссинговер сплошной случайный, то каждый бит доминантности выставить в 0 с вероятностью k, где k примерно равно 0.1.

Таким образом, более новые гены будут рецессивными, а более стабильные - доминантными.

Преимущества и недостатки плоидности

Преимущества:

  • Позволяет избегать локальных экстремумов;
  • Добавляет больше простора для распараллеливания.

Недостатки:

  • Увеличение объёма хранимой информации в разы;
  • Увеличение сложности кода;
  • Введение новых и непонятных эвристик.

Почему инцест помогает избежать локальных экстремумов?

Инцест - скрещивание близкородственных особей.

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

Источники информации

Личные инструменты