Плоидность

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

Версия 23:36, 5 февраля 2011

Шаблон:Редактирую

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

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

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

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

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

Гипотезы

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

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

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

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

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

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

1. Хранение: Каждая особь популяции владеет n-кратным набором генов (или цепочками ДНК, или n набором хромосом)

Число n обычно равно двум. Не ясно, имеет ли смысл его брать больше этого значения. В природе оно почти всегда есть 2. Кроме самих генов, необходимо также хранить информацию о доминантности/рецессивности для каждого гена из каждого набора генов, что обычно даёт 2n-кратный рост памяти, занимаемой особью по сравнению с гаплоидной версией. Информация о доминантности сцеплена с геном. Она, также как и гены, подвергается мутациям и перемешивается в процессе кроссинговера. Без этой информации полиплоидность, возможно, бессмысленна.

1. Скрещивание: Из популяции каким-либо образом выбираются будущие родители. От каждой родительской особи, путём кроссинговера родительских наборов генов, получаем новый набор генов будущего потомка. Наборы генов потомка собираются в новой особи, которая объявляется потомком

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

1. Экспрессия: Фенотип особи определяется согласно всем наборам генов, из которых эта особь состоит

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

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

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

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

Недостатки:

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

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

• Статья "Плоидность" в Википедии
• Демон Дарвина... -- Отлично рассмотрен с точки зрения математики накопительный эффект от рецессивности (см. выше "плоидность");
  
• Г. К. Вороновский и др., Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности -- пример положительного эффекта диплоидности на качество схождения ГА в глобальном экстремуме.