Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой

 

 

А.П. Карпенко 

 

СОВРЕМЕННЫЕ АЛГОРИТМЫ 
ПОИСКОВОЙ ОПТИМИЗАЦИИ 

Алгоритмы, вдохновленные 
природой 
 
 
Допущено Учебно-методическим объединением вузов 
по университетскому политехническому образованию 
в качестве учебного пособия для студентов высших учебных 
заведений, обучающихся по направлению подготовки 
230100 «Информатика и вычислительная техника» 
 
2-е издание 
 
 
 
 
 
 
 
 

 
 

 

УДК 519.6 
ББК 22.19 
К26 

Р е ц е н з е н т ы :   
заведующий кафедрой «Информационные технологии в управлении» 
Российской академии народного хозяйства и государственной службы 
при Президенте Российской Федерации д-р техн. наук, проф. А.Н. Данчул; 
профессор кафедры физико-математических методов управления 
МГУ им. М.В. Ломоносова, Главный научный сотрудник лаборатории 
оптимизации управляемых систем ИПУ им. В.А. Трапезникова РАН,  
 д-р техн. наук Н.Б. Филимонов  

 
Карпенко, А. П. 

 
К26 
Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой : учебное пособие / А. П. Карпенко. — 2-е изд. — 
Москва : Издательство МГТУ им. Н. Э. Баумана, 2017. — 446, [2] с. : ил. 

 
 
ISBN 978-5-7038-4634-6 
Учебное пособие посвящено, преимущественно, рассмотрению современных стохастических популяционных алгоритмов решения однокритериальной задачи оптимизации. Рассмотрены методы повышения эффективности 
этих алгоритмов путем их гибридизации и метаоптимизации. Наряду с однокритериальной рассматривается задача многокритериальной оптимизации и 
популяционные алгоритмы ее решения. Представлены методы распараллеливания указанных алгоритмов. Содержит большое число примеров решения 
тестовых и практически значимых задач оптимизации.  
Для студентов высших учебных заведений, обучающихся по направлению 230100 «Информатика и вычислительная техника». Может быть полезно 
для всех студентов, изучающих курс «Методы оптимизации» и близкие по 
тематике курсы. Материал пособия представляет интерес также для аспирантов и специалистов, использующих в своей работе методы, алгоритмы и программы оптимизации.  
 
  

 
 
УДК 519.6 
ББК 22.19 

© Карпенко А. П.,  2014  
© Оформление. Издательство МГТУ 
ISBN 978-5-7038-4634-6                                                     им. Н.Э. Баумана, 2017 

Моим любимым дочерям. 
Главное, что вы есть!

Предисловие

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

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

Пособие ориентировано, в первую очередь, на студентов высших учебных 

заведений, обучающихся по направлению 230100 «Информатика и вычислительная техника». В то же время оно может быть полезным для всех студентов, 
изучающих курс «Методы оптимизации» и близкие по тематике курсы. Материал пособия представляет интерес также для аспирантов и специалистов, 
использующих в своей работе методы, алгоритмы и программы оптимизации.

Предисловие

Пособие в значительной степени использует материалы лекций по курсу 

«Методы оптимизации», который автор в течение ряда лет читает студентам 
старших курсов специальности «Системы автоматизированного проектирования» МГТУ им. Н. Э. Баумана.

Автор благодарит своих аспирантов и студентов Абрамова Д. О., Антух А. Э., Бензу Н. Н., Березина Д. В., Гришина А. А., Егорова А. И., Карипова Д. Р., Комарова С. В., Кудряшова А. М., Митину Е. В., Мишина С. Н., 
Мурсякаева М. А., Мухлисуллина Э. Т., Овешникова А. А., Плякина Д. А., Семенихина А. С., Синяговскую О. А., Сорокина А. С., Сундукова К. В., Хасанову Р. В., Чернобривченко К. А., Шурова Д. Л. за помощь в проведении вычислительных экспериментов, результаты которых представлены в книге. Автор 
отмечает особенно большую помощь в подготовке книги Селиверстова Е. Ю. 
и выражает ему отдельную благодарность.

Модель объекта управления (п. 2.13) заимствована из книги: Федоренко Р. П. Приближенное решение задач оптимального управления. – М.: Наука, 
1978. – 488 с. Задача, рассмотренная в п. 3.1.6, предоставлена И. М. Губайдуллиным (Институт нефтехимии и катализа РАН, г. Уфа). Модель системы «двигатель–генератор» взята из книги Александрова А. Г. Оптимальные и адаптивные системы. – М.: Высшая школа, 1989. – 263 с. Тестовая задача оптимизации 
конструкции консольной балки, рассмотренная в п. 5.1.3, заимствована из работы Lee KS., Geem ZW. A new meta-heuristic algorithm for continuous engineering 
optimization: harmony search theory and practice // Computational Methods Applied 
Mechanics Engineering, 2005, Vol. 194, pp. 3902–3933.

Основные обозначения

( )
abs ⋅  – символ абсолютного значения числа

,
X
X
D D
R
⊂
 – множества допустимых значений вектора варьируемых 

парамет ров X
F
F
D
R
⊂
 – множество достижимости многоцелевой задачи оптимизации

F
F
D
D
∗ ⊂
 – фронт Парето многоцелевой задачи оптимизации

X
X
D
D
∗ ⊂
 – множество Парето многоцелевой задачи оптимизации

1
2
(
)
( (
),
(
),...,
(
))
E
E X
e X
e
X
e
X
=
 – (
1)
E ×
­ограничивающая вектор­функция, 

с помощью которой задаются ограничения типа равенств на вектор 
варьируемых параметров X

( , )
E a b
ν
 – (
1)
ν×
­вектор независимых вещественных случайных чисел, распределенных по экспоненциальному закону 
1
( )
exp
2
x
a
x
b
b


−
ξ
=
−




 , 

,
0
a b >  , 
(
,
)
x∈ −∞ ∞

(
)
1
2
| |
(
)
(
),
(
),...,
(
)
F
F X
f X
f
X
f
X
=
 – целевая вектор­функция (векторный критерий опти мальности) со значениями в пространстве 

F
R

(
)
F X
F
∗
∗
=
 – искомый целевой вектор

(
)
f X  – скалярная целевая функция (критерий оптимальности) со значениями 

в пространстве 
1
R

(
)
f X
f
∗
∗
=
 – искомое оптимальное значение целевой функции 
(
)
f X

f ∗  – приближенное значение оптимума целевой функции 
(
)
f X

1
2
(
)
(
(
),
(
),...,
(
))
G
G X
g X
g
X
g
X
=
  – (
1)
G ×
­ограничивающая вектор­функция, с помощью которой задаются ограничения типа неравенств 
на вектор варьируемых параметров X

H = 
1
2
( ,
,...,
)
H
h h
h
 – хромосома (закодированный вектор X ), соответствующая текущему положению агента в пространстве поиска

g
i
H =  
,
(
,
[1:
])
g
i j
i
h
j
H
∈
 – ген, соответствующий компоненте 
ix  вектора X

( )
Lν λ  – (
1)
ν×
­вектор независимых вещественных случайных чисел, распределенных по закону Леви; используется в  полетах Леви

( ,
)
N
m
ν
σ  – (
1)
ν×
­вектор независимых вещественных случайных чисел, 

распределенных по нормальному закону с математическим ожиданием 
m и средним квадратичным отклонением σ

fn  – число испытаний (вычислений значений целевой функции)

fn  – среднее число испытаний

Null  – пустое множество

| |A
R
 – |
|
A ­мерное арифметическое пространство

Основные обозначения

( )
( ,
[1:
])
i
S
S t
s i
S
=
=
∈
 – текущая популяция

( )
i
i
s
s t
=
 – агент популяции S

(
1)
( ,
[1:
])
i
S
S t
s i
S
′
′
=
+
=
∈
 – следующая популяция

(
1)
i
i
s
s t
′ =
+
 – агент популяции S′

(
)
,
[1:
]
iS i
=
∈
S
S
 – мультипопуляция

iS  – субпопуляция мультипопуляции S

( )
sign a – знак числа a

T – символ транспонирования
ˆt  – максимальное допустимое число поколений (итераций)
t – номер текущего поколения (итерации)

end
t
 – поколение (итерация), соответствующее началу стагнации вычислений

end
t
 – среднее по числу запусков мультистарта число поколений (итераций)
( ; )
U
a b
ν
 – (
1)
ν×
-вектор независимых вещественных случайных чисел, 

равно мерно распределенных в интервале [ ; ]
a b ; а, b – вещественные 

числа; b
a
>

1
2
(
:
)
U
n
n
ν
 – (
1)
ν×
-вектор независимых целых случайных чисел, равномерно 

распределенных в интервале 
1
2
[
:
]
n
n
; 
1
2
,
n n  – целые числа; 
2
1
n
n
>

0
sign
u
 – случайная величина, с равной вероятностью принимающая значения 

(–1), (0), (1)

1
sign
u±  – случайная величина, с равной вероятностью принимающая значения 

(1), (–1)

1
2
|
|
( ,
,...,
)
X
X
x x
x
=
 – (
1)
X ×
-вектор варьируемых параметров

,1
,2
,|
|
(
,
,...,
)
i
i
i
i X
X
x
x
x
=
 – (
1)
X ×
-вектор варьируемых параметров, определяющий положение агента 
is
S
∈
; 
[1:
]
i
X
∈

,1
,2
,|
|
(
,
,...,
)
i
i
i
i X
X
x
x
x
′
′
′
′
=
 – (
1)
X ×
-вектор варьируемых параметров, определяющий положение агента 
is
S
′
′
∈
; 
[1:
]
i
X
∈

X ∗ – искомый оптимальный вектор варьируемых параметров X
X ∗
  – приближенный вектор X ∗

tδ  –  критерий стагнации вычислительного процесса: если в течение данного 

числа поколений значение фитнес-функции не меняется, то считают, 
что имеет место стагнация вычислений

(
)
( )
(
)
X
s
H
ϕ
= ϕ
= ϕ
 – фитнес-функция (функция приспособленности, приспособленность) агента s. Если не оговорено противное, то имеется в виду 
минимизация этой функции
1,
0,
( )
0,
0
x
x
x
≥

χ
= 
<


 – функция Хевисайда

1
2
{ ,
,...}
c c
 – совокупность (множество) элементов 
1
2
,
,...
c c

|
|
A  – размерность вектора A
|
|
B  – число элементов во множестве B

Основные обозначения

v
 
   – ближайшее целое большее v
v
 
   – ближайшее целое меньшее v

,v w



  – ближайшее целое меньшее v  и кратное w

⋅  – векторная норма

E
⋅   – евклидова векторная норма

(
)

2

1
2
1,
2,
1
,

A

i
i
E
i
A A
a
a

=
=
−
∑
 – евклидово расстояние между целочисленными 

или вещественными векторами 
1
2
,
A A  размерности A

1
2
,
H
B B
 – расстояния Хемминга между бинарными векторами 
1
2
,
B B , равное 

числу различающихся битов в одноименных разрядах указанных 
векторов

(
)

1

1
2
1,
2,
1
,

A

i
i
M
i
A
A
abs a
a

=
=
−
∑
 – манхэттенское расстояние между целочисленными или вещественными векторами 
1
2
,
A A  размерности A

(
)

1

1
2
1,
2,
1
,

A
A
A
A

i
i
M
i
A
A
abs a
a

=



=
−






∑
 – 
A
L ­манхэттенское расстояние между 

цело численными или вещественными векторами 
1
2
,
A A  размерности A

(
)
(
)
(
)
(
)

1
2
...

T

X
X
X
X
X
X
X

f
X
f
X
f
X
f
X
x
x
x
′
′
=
=
′
=



∂
∂
∂


′
∇
= 

∂
∂
∂



 –  градиент функции 
(
)
f X  

в точке X′

( ,
)
A B  – скалярное произведение векторов 
,
A B , имеющих одинаковую размерность
(
)
1
1
2
2
...
A
B
A
B
a b
a b
a
b
⊗
=
 – прямое произведение векторов 
,
A B  одинаковой размерности A
B
=

П={
|
}
{
|
,
[1:
]}
i
i
i
X X
X
X
X x
x
x
i
X
−
+
−
+
≤
≤
=
≤
≤
∈
 – гиперпараллелепипед 

допустимых значений вектора варьируемых параметров

ЛПР – лицо, принимающее решения
ОДУ – система обыкновенных дифференциальных уравнений
Замечание. В силу того, что любой программный генератор случайных чисел 
в действительности генерирует псевдослучайные числа, вместо слов «случайный вектор», «случайная величина» и так далее следовало бы писать «псевдослучайный вектор», «псевдослучайная величина» и т. д. В книге для компактности письма этот нюанс опущен.

Введение

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

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

Для эффективного решения задач глобальной оптимизации в 1980­х гг. начали интенсивно разрабатывать класс стохастических поисковых алгоритмов 
оптимизации, которые в разных публикациях называют поведенческими, интеллектуальными, метаэвристическими, вдохновленными (инспирированными) природой, роевыми, многоагентными, популяционными и т. д. Последний 
термин наиболее отвечает сути этих алгоритмов.
Популяционные алгоритмы (population algorithms) предполагают одновременную обработку нескольких вариантов решения задачи оптимизации и представляют собой альтернативу классическим «траекторным» поисковым алгоритмам, в которых в области поиска эволюционирует только один кандидат 
на решение этой задачи.

Подавляющее большинство рассматриваемых алгоритмов опубликовано 

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

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

Введение

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

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

По способу определения направления движения к экстремуму алгоритмы 

поисковой оптимизации разделяют на алгоритмы детерминированного (регулярного) поиска (например, классический алгоритм наискорейшего спуска) 
и алгоритмы стохастического (случайного) поиска. Все рассматриваемые популяционные алгоритмы относятся к классу стохастических.

Алгоритмы поисковой оптимизации разделяют еще на два следующих 

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

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

В качестве общего названия членов популяции используем термин агент 
(agent). В различных популяционных алгоритмах агенты называются индивидами, особями, частицами, муравьями, пчелами и т. д.

Общая схема популяционных алгоритмов включает в себя следующие этапы.
1. Инициализация популяции. В области поиска тем или иным образом создаем некоторое число начальных приближений к искомому решению задачи – 
инициализируем популяцию агентов.
2. Миграция агентов популяции. С помощью некоторого набора миграционных операторов, специфических для каждого из популяционных алгоритмов, перемещаем агентов в области поиска таким образом, чтобы в конечном 
счете приблизиться к искомому экстремуму оптимизируемой функции.

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

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

Миграцию агентов, например, в генетическом алгоритме, который мы также относим к популяционным алгоритмам, реализуют генетические операторы 
скрещивания, мутации и другие.

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

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

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

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

• Децентрализация – отсутствие агентов, управляющих процессом поиска 

в целом.

• Коммуникабельность – агенты тем или иным способом могут обмениваться между собой информацией о топологии (ландшафте) оптимизируемой 
функции, выявленной в процессе исследования своей части области поиска.

Даже если стратегия поведения каждого из агентов популяции достаточно проста, указанные свойства агентов обеспечивают формирование так называемого роевого интеллекта (swarm intelligence) популяции, проявляющегося в самоорганизации и сложном поведении популяции в целом.

Одной из особенностей популяционных алгоритмов оптимизации является 

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

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