Генетические алгоритмы

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

При разработке генетических алгоритмов преследуются две главные цели:

1) абстрактное и формальное объяснение процессов адаптации в естественных системах;

2) проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.

Основные отличия ГА от других алгоритмов оптимизации:

1) используются не параметры, а закодированные множества параметров;

2) поиск осуществляется не из единственной точки, а из популяции точек;

3) в процессе поиска используются значения целевой функции, а не ее приращения;

4) применяются вероятностные, а не детерминированные правила поиска и генерации решений;

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

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

1. все признаки организма определяются наборами генов;

2. гены – это элементарные единицы наследственной инфор­мации, которые находятся в хромосомах;

3. гены могут изменяться – мутировать;

4. мутации отдельных генов приводят к изменению отдельных элементарных признаков организма, или фенов.

Термины, взятые из генетики, трактуются а ГА следующим образом:

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

Хромосомы – это нитевид­ные структуры, находящиеся в клеточном ядре, которые являют­ся носителями наследственности. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет опреде­ленное, постоянное количество хромосом. Каждая клетка содер­жит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара – 3.

Ген определяется как структурная единица наследственной информации, далее неделимая в функциональном отношении. Комплекс генов, содержащихся в наборе хромосом одного орга­низма, образует геном.

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

Рисунок 10.2 – Схема кроссинговера:
а) родительские хромосомы до кроссинговера,
б) хромосомы-потомки после кроссинговера.

Кроссинговер может происходить в нескольких точках. При­мер двойного кроссинговера между хромосомами приведен на рис. 10.3.

Рисунок 10.3 – Схема двойного кроссинговера:
а) до кроссинговера, б) во время кроссинговера,
в) после кроссинговера.

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

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

Инверсия, транслокация, транспозиция, делеция и дуплика­ция относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При переме­щении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция — это выпадение отдельных участков хромосом, дупликация – повторе­ние участка генетического материала. Кроме перечисленных, су­ществуют другие разновидности хромосомных мутаций.