Генетический алгоритм – это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора.
При разработке генетических алгоритмов преследуются две главные цели:
1) абстрактное и формальное объяснение процессов адаптации в естественных системах;
2) проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.
Основные отличия ГА от других алгоритмов оптимизации:
1) используются не параметры, а закодированные множества параметров;
2) поиск осуществляется не из единственной точки, а из популяции точек;
3) в процессе поиска используются значения целевой функции, а не ее приращения;
4) применяются вероятностные, а не детерминированные правила поиска и генерации решений;
5) выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.
В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов. Классическая генетика обосновала наследственность и изменчивость благодаря созданию фундаментальной теории гена, основные положения которой формулируются следующим образом:
1. все признаки организма определяются наборами генов;
2. гены – это элементарные единицы наследственной информации, которые находятся в хромосомах;
3. гены могут изменяться – мутировать;
4. мутации отдельных генов приводят к изменению отдельных элементарных признаков организма, или фенов.
Термины, взятые из генетики, трактуются а ГА следующим образом:
Генетика | Генетические алгоритмы |
Хромосома | Решение, стринг, строка, последовательность, родитель, потомок |
Популяция | Набор решений (хромосом) |
Локус | Местоположение гена в хромосоме |
Ген | Элемент, характеристика, особенная черта, свойство, детектор |
Поколение | Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений |
Аллель | Значение элемента, характеристики |
Эпистасис | Множество параметров, альтернативные решения |
Каждое решение из множества возможных можно представить набором информации, который может быть изменен путем введения в него элементов другого решения. Другими словами, возможные решения соответствуют хромосомам, состоящим из генов, причем в ходе оптимизации происходит обмен генами между хромосомами – рекомбинация. Рекомбинация используется для накопления в конечном решении лучших функциональных признаков, какие имелись в наборе исходных решений.
Хромосомы – это нитевидные структуры, находящиеся в клеточном ядре, которые являются носителями наследственности. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет определенное, постоянное количество хромосом. Каждая клетка содержит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара – 3.
Ген определяется как структурная единица наследственной информации, далее неделимая в функциональном отношении. Комплекс генов, содержащихся в наборе хромосом одного организма, образует геном.
Существует несколько типов рекомбинации участков хромосом. В генетических алгоритмах наибольшее распространение получила операция кроссинговера, заключающаяся в разрыве гомологичных хроматид с последующим соединением их в новом сочетании. Он приводит к появлению нового сочетания сцепленных генов. Схема кроссинговера, демонстрирующая образование двух новых хромосом после обмена генетическим материалом, приведена на рис. 10.2. Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков в одном решении.
Рисунок 10.2 – Схема кроссинговера:
а) родительские хромосомы до кроссинговера,
б) хромосомы-потомки после кроссинговера.
Кроссинговер может происходить в нескольких точках. Пример двойного кроссинговера между хромосомами приведен на рис. 10.3.
Рисунок 10.3 – Схема двойного кроссинговера:
а) до кроссинговера, б) во время кроссинговера,
в) после кроссинговера.
Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция, генная инженерия.
Под мутацией понимается генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала. Применение операции мутации в генетических алгоритмах направлено на получение решений, которые не могут быть улучшены качественно посредством кроссинговера.
Инверсия, транслокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При перемещении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция — это выпадение отдельных участков хромосом, дупликация – повторение участка генетического материала. Кроме перечисленных, существуют другие разновидности хромосомных мутаций.