Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

 
 
 

---

112 
Применение генетических алгоритмов
 
Генетические алгоритмы носят эвристический характер. Можно 
предположить, что генетический алгоритм способен осуществлять 
эффективный поиск оптимального решения, при условии, что: 
-
пространство поиска достаточно велико, и предполагается, что 
целевая функция не является гладкой и унимодальной в области поиска, т. е. 
не содержит один гладкий экстремум; 
-
нет необходимости в поиске универсального оптимального 
решения, достаточно быстро найти подходящее решение.
Если 
целевая 
функция 
обладает 
свойствами 
гладкости 
и 
унимодальности, то любой градиентный метод, такой как метод 
наискорейшего спуска, будет более эффективен. Генетический алгоритм 
является в определенном смысле универсальным методом, в связи с тем, что 
не учитывает специфику задачи. Если существует возможность получить 
сведения о целевой
функции и сведения о пространстве поиска, то 
становится возможным использование эвристического поиска, который 
превосходит по эффективности универсальный алгоритм. 
Сегодня генетические алгоритмы успешно применяются для решения 
классических NP
-
полных задач, задач оптимизации в пространствах с 
большим количеством измерений, ряда экономических задач оптимального 
характера, например, задач распределения инвестиций. 
Использование эволюционных алгоритмов вместе с параллельными 
вычислениями позволяет эффективно решать задачи оптимизации, размер 
которых превышает 2
100
. Такие эволюционные алгоритмы называются 
распределенными генетическими алгоритмами.
Можно выделить два способа применения параллельных технологий к 
генетическим алгоритмам
[3]: 
1. 
Изменение структуру алгоритма (технология 
master-slave
). При 
использовании этого способа параллельной обработке подвергаются такие 
независимые элементарные операции, как: 

---

113 
-
построение особи, в операторе создания начальной популяции;
-
построение потомка и его мутация, в
операторе воспроизводства;
-
оценка приспособленности особи.
Технология 
master-slave 
предполагает, что работа над популяцией 
осуществляется на главном процессоре, а приспособленность особей 
вычисляется на подчиненных процессорах. Недостатком данного метода 
является возможное снижение эффективности вычислений при увеличении 
количества процессоров. Это происходит за счет потери времени на обмен 
данными между главным процессором и подчиненным
и потери времени на 
ожидание завершения работы всех подчиненных процессоров для 
продолжения вычислений.
2. 
Изменение структуры алгоритма в результате применения 
ограничений 
возможности 
скрещивания 
(мелкоструктурированный 
параллельный 
генетический 
алгоритм 
и 
крупноструктурированный 
параллельный 
генетический 
алгоритм. 
Крупноструктурированный 
параллельный 
генетический 
алгоритм 
имеет 
отношение 
к 
мултипопуляционным моделям, таким как метод случайных иммигрантов в 
исследованиях 
Grefenstette
, метод ниш и островным моделям. При таком 
способе вычислений популяция делится на локальные популяции, развитие 
которых происходит параллельно и независимо, но при этом сохраняется 
возможность обмена особями между популяциями. Особи разных локальных 
популяций не могут образовывать брачные пары. Естественный отбор 
действует только внутри локальной популяции. Каждая локальная популяция 
обрабатывается на отдельном процессоре. Основой алгоритма является 
определенный метод разбиения популяции. Для минимизации затрат на 
обмен данными, топология связи между локальными популяциями отражает
топологию
связи между процессорами или компьютерами вычислительной 
системы. Большое количество связей между популяциями снижает 
эффективность вычислений. А уменьшение количества связей приводит к
преждевременной сходимости в ряде локальных популяций и потери 

---

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