В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов. Хромосомы — это нитевидные структуры, находящиеся в клеточном ядре, которые являются носителями наследственности.
Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет определенное, постоянное количество хромосом. Каждая клетка содержит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара — 3.
На процесс наследования признаков существенно влияет поведение хромосом при делении клеток. Существует митозное и мейозное деление клеток. Митозное деление обеспечивает распределение исходных хромосом между двумя образующимися дочерними клетками, которые будут иметь равноценные наборы хромосом и будут очень похожи друг на друга. При этом происходит редупликация исходных хромосом, вследствие чего к моменту деления клетки каждая хромосома состоит из двух копий исходной материнской хромосомы — сестринских хроматид.
Во время мейоза происходит два последовательных деления: редукционное и эквационное. Мейоз приводит к образованию клеток, у которых число хромосом вдвое меньше по сравнению с исходной клеткой.
В фазе редукции хроматиды обмениваются генами, т. е. участками дезоксирибонуклеиновой кислоты (ДНК). После этого клетка разделяется на две новые, причем каждая из них содержит удвоенный набор хромосом, структуры которых отличаются от исходных. Механизм обмена генами называется кроссинговером.
В результате эквационного деления из двух получившихся клеток образуются четыре клетки, каждая из которых содержит одиночный набор хромосом (см. рис. 6.2).
Таким образом, митоз обеспечивает возобновление клеток, а мейоз отвечает за передачу наследственной информации и способствует генетическому разнообразию организмов данного вида.
Классическая генетика обосновала наследственность и изменчивость благодаря созданию фундаментальной теории гена, основные положения которой формулируются следующим образом:
Ген определяется как структурная единица наследственной информации, далее неделимая в функциональном отношении.
В задачах поиска оптимальных решений каждое решение из множества возможных можно представить набором информации, который может быть изменен путем введения в него элементов другого решения. Другими словами, возможные решения соответствуют хромосомам, состоящим из генов, причем в ходе оптимизации происходит обмен генами между хромосомами (рекомбинация). При построении генетических алгоритмов важен выбор принципа генетической рекомбинации. Существует несколько типов перераспределения наследственных факторов:
Для построения генетических алгоритмов наибольший интерес представляет третий тип рекомбинации, который используется для накопления в конечном решении лучших функциональных признаков, какие имелись в наборе исходных решений. Существует несколько типов рекомбинации участков хромосом: кроссинговер, сайт, иллегальная рекомбинация.
Кроссжговер соответствует регулярной рекомбинации, при которой происходит обмен определенными участками между гомологичными хромосомами. Он приводит к появлению нового сочетания сцепленных генов.
Сайт — это вид рекомбинации, при которой на коротких специализированных участках хромосом происходит обмен генофоров (генных носителей), часто различных по объему и составу генетической информации.
Иллегальная рекомбинация допускает негомологичные обмены, к которым относятся транслокации, инверсии и случаи неравного кроссинговера. Такие способы могут оказаться полезными при генерации новых решений.
В генетических алгоритмах наибольшее распространение получила операция кроссинговера, заключающаяся в разрыве гомологичных хроматид с последующим соединением их в новом сочетании.
Схема кроссинговера, демонстрирующая образование двух новых хромосом после обмена генетическим материалом, приведена на рис. 6.3.
Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков в одном решении.
Рис. 6.3. Схема кроссинговера: а — родительские хромосомы А, В до кроссинговера; б — хромосомы-потомки А’, В ‘после кроссинговера
Кроссинговер может происходить в нескольких точках. Пример двойного кроссинговера между хромосомами/и w приведен на рис. 6.4.
Рис. 6.4. Схема двойного кроссинговера:
а — до кроссинговера; б— во время кроссинговера; в — после кроссинговера
Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция (инбридинг и гибридизация), генная инженерия.
Под мутацией понимается генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Свойство дискретности позволяет выделить в исходном генетическом материале отдельные фрагменты, контролирующие те или иные функции. Непрерывность означает, что определенные комбинации генов совместно контролируют некоторую функцию. Линейность проявляется в определенной последовательности генов в пределах группы сцепления.
Процессы мутации ведут к получению более разнообразного генетического материала. В связи с этим применение операции мутации в генетических алгоритмах направлено на получение решений, которые не могут быть улучшены качественно посредством кроссинговера.
Инверсия, транслокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При перемещении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция — это выпадение отдельных участков хромосом, дупликация — повторение участка генетического материала. Кроме перечисленных, существуют другие разновидности хромосомных мутаций.
Селекция представляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Установлено, что массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем индивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. Применение процедуры селекции в генетических алгоритмах оптимизации способствует ускорению процесса синтеза искомого решения.
Генная инженерия представляет собой совокупность методов для получения рекомбинантной ДНК и операции над нею. Рекомбинантная ДНК получается путем объединения фрагментов ДНК различных организмов. Использование подходов генной инженерии позволяет в ряде задач значительно быстрее находить желаемое решение.
Механизм эволюции основан на трех повторяющихся процессах: отборе, амплификации (процесс производства потомков) и мутации. Он используется в качестве механизма случайно направленного комбинаторного перебора при решении задач оптимизации и слабоструктурированных проблем принятия решений.
Генетический алгоритм — это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции.В генетических алгоритмах используются специфические термины, взятые из генетики, которые трактуются следующим образом.
Генетика Генетические алгоритмы
Хромосома Решение, стринг, строка, последовательность, родитель, потомок
Популяция Набор решений (хромосом)
Локус Местоположение гена в хромосоме
Поколение Цикл работы генетического алгоритма, впроцессе которого сгенерировано множество решений
Ген Элемент, характеристика, особенная черта,свойство, детектор
Аллель Значение элемента, характеристики
Фенотип Структура
Эпистасис Множество параметров, альтернативные решения
Скрещивание, рекомбинация Оператор рекомбинации, кроссинговер
Мутация Оператор модификации
При разработке генетических алгоритмов преследуются две главные цели:
Основные отличия ГА от других алгоритмов оптимизации:
Если основа оригинала (карты пли плана) прозрачна, то копию можно снять при помощи стола со…
Определение координат точки. Пусть точка А (рис. 32) находится в квадрате, абсциссы и ординаты вершин…
Рельефом местности называется совокупность неровностей физической поверхности земли. В зависимости от характера рельефа местность делят…
Для обозначения на планах и картах различных предметов местности, применяются специально разработанные условные знаки. Для обличения…
В инженерной геодезии чаще всего пользуются топографическими картами. Их составляют в масштабах 1:10000, 1:25000, 1:50000…