See discussions, stats, and author profiles for this publication at: [Link]

net/publication/307963525

Методы стохастической оптимизации

Book · March 2016

CITATIONS READS
0 14,217

3 authors, including:

Pavel V Matrenin Vg Sekaev

Novosibirsk State Technical University 5 PUBLICATIONS 14 CITATIONS
80 PUBLICATIONS 180 CITATIONS
SEE PROFILE
SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Global optimization and Topological methods with applications in Materials science View project

All content following this page was uploaded by Pavel V Matrenin on 10 September 2016.

The user has requested enhancement of the downloaded file.

 Министерство образования и науки Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
_______________________________________________________________________

П.В. МАТРЕНИН, М.Г. ГРИФ, В.Г. СЕКАЕВ

МЕТОДЫ
СТОХАСТИЧЕСКОЙ
ОПТИМИЗАЦИИ
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия

Новосибирск
2016
УДК 519.856(075.8)
М 346

Рецензенты:
канд. техн. наук, доц. А.В. Гаврилов;
канд. техн. наук, доц. В.С. Поздняков

Работа подготовлена на кафедре

автоматизированных систем управления
для студентов дневного отделения по курсу взаимосвязанных
дисциплин «Интеллектуальные системы» и «Интеллектуальные
системы и технологии» (ООП по направлениям 09.04.01
«Информатика и вычислительная техника» (магистерская программа
«Компьютерное моделирование систем», квалификация «магистр»),
09.03.01 «Информатика и вычислительная техника»
(квалификация «бакалавр»)

Матренин П.В.
М 346 Методы стохастической оптимизации: учебное пособие /
П.В. Матренин, М.Г. Гриф, В.Г. Секаев. – Новосибирск: Изд-во
НГТУ, 2016. – 67 с.
ISBN 978-5-7782-2861-0
Учебное пособие раскрывает принципы, модели и методы стоха-
стической оптимизации, рекомендации по их реализации и примене-
нию на практике, дает примеры использования. Кроме того, пособие
содержит описание практической работы по данной теме.
Адресовано студентам и специалистам, изучающим методы опти-
мизации и системы искусственного интеллекта.

УДК 519.856(075.8)

ISBN 978-5-7782-2861-0  Матренин П.В., Гриф М.Г.,

Секаев В.Г., 2016
 Новосибирский государственный
технический университет, 2016
 ОГЛАВЛЕНИЕ

Введение ..................................................................................................................5
1. Описания алгоритмов .........................................................................................7
1.1. Термины и обозначения ..............................................................................7
1.2. Случайный поиск, поиск с возвратом......................................................10
1.3. Алгоритм имитации отжига .....................................................................11
1.4. Генетический алгоритм.............................................................................12
1.5. Алгоритм роя частиц .................................................................................15
1.6. Алгоритм роя пчел ....................................................................................18
1.7. Алгоритм поиска косяком рыб .................................................................21
1.8. Алгоритм колонии муравьев ....................................................................25
2. Практическое использование алгоритмов .....................................................29
2.1. Области применения .................................................................................29
2.2. Машинное обучение..................................................................................30
2.2.1. Задача машинного обучения ...........................................................30
2.2.2. Признаки...........................................................................................31
2.2.3. Виды задач и примеры ....................................................................32
2.2.4. Методы машинного обучения и оценка качества .........................33
2.2.5. Обучение как задача оптимизации.................................................33
2.2.6. Примеры использования стохастической оптимизации для
задач обучения .................................................................................35
2.3. Рекомендации по реализации алгоритмов ..............................................38
3. Практическая работа по стохастической оптимизации ................................45
3.1. Описание ....................................................................................................45
3.2. Описание программного обеспечения визуализации............................46
3.3. Практическое задание ...............................................................................50
3.3.1. Начало работы..................................................................................50
 3.3.2. Демонстрация алгоритма роя частиц .............................................53
3.3.3. Демонстрация алгоритма роя пчел.................................................55
3.3.4. Демонстрация алгоритма имитации отжига..................................56
3.3.5. Демонстрация генетического алгоритма .......................................58
3.3.6. Индивидуальные задания................................................................59
Контрольные вопросы ..........................................................................................61
Библиографический список .................................................................................63

4
 ВВЕДЕНИЕ
Детерминированные эвристические (жадные) методы основаны на
идее локально оптимальных выборов на каждом шаге. Принцип жад-
ного выбора может дать оптимальное решение, если последователь-
ность таких выборов дает глобально оптимальное решение [15], т. е.
на каждом шаге алгоритм делает выбор такого варианта, который ка-
жется наилучшим на данном шаге. Выбор, сделанный в жадном алго-
ритме, может зависеть от сделанных ранее выборов, но он никак не
зависит от выборов на последующих шагах или от решений последу-
ющих подзадач, в отличие от метода динамического программирова-
ния. Такие методы позволяют получать решения очень быстро, так
как формируют лишь один вариант решения задачи на основе неко-
торых правил, но полученное таким образом решение может оказать-
ся как наилучшим, так и очень далеким от наилучшего в зависимости
от экземпляра задачи.
Например, для задачи календарного планирования, в которой нуж-
но определить наилучшую последовательность выполнения этапов,
реализация жадного алгоритма может быть, например, такой: «выби-
рать на каждом шаге этап, выполнение которого завершится как можно
раньше». Существуют более сложные жадные эвристические алгорит-
мы, основанные на назначении требованиям приоритетов в зависимо-
сти от многих факторов, а также на использовании нескольких эври-
стических правил для совершения выбора на каждом шаге. Однако да-
же сложные эвристические правила могут быть эффективными только
в сочетании с другими более мощными оптимизационными алгорит-
мами. Во многих задачах оптимизации эффективность жадных алго-
ритмов очень сильно зависит от условий конкретной задачи.
Стохастические (рандомизированные) эвристические методы также
не гарантируют получение точного решения, но они, как правило, поз-
воляют находить достаточно близкие для практического использова-
ния решения за приемлемое время. При этом стохастическая природа

5
большинства методов делает их применение нетривиальной задачей,
поскольку для каждой алгоритмической реализации и для каждого
класса задач оптимизации эффективность, быстродействие, сходи-
мость, влияние условий задачи и параметров алгоритма требуют тща-
тельного исследования. Сказанное здесь относится только к стохасти-
ческим методам, основанным на некоторых эвристиках. Кроме них
существуют и очень простые стохастические методы, такие как слу-
чайный поиск.
Рассматриваемые далее алгоритмы роевого интеллекта, эволюци-
онные алгоритмы и алгоритм имитации отжига имеют одну основу, а
именно конечные цепи Маркова. Однако рассмотренные алгоритмы
появились не в результате изучения цепей Маркова или их применения
для решения задач оптимизации. Они стали результатом моделирова-
ния, например, поведения птиц в стае (алгоритм роя частиц) или изу-
чения принципов поведения муравьев (алгоритм «колонии муравьев»
или «муравьиный алгоритм»). Уже после распространения генетиче-
ского алгоритма и других к ним были применены различные матема-
тические модели, в том числе и цепи Маркова. Использование цепей
Маркова позволяет доказать сходимость рассматриваемых алгоритмов
к глобальному оптимуму только теоретически при устремлении вре-
мени работы алгоритма к бесконечности. Однако такой подход не объ-
ясняет показанную в многочисленных экспериментах высокую эффек-
тивность рассматриваемых стохастических алгоритмов оптимизации
для решения практических задач с ограничениями по времени. Рас-
сматриваемые алгоритмы называют алгоритмами дискретной оптими-
зации, поскольку они работают пошагово, по итерациям, а не непре-
рывно. Область же применения включает в себя и задачи дискретной
оптимизации (комбинаторные), и задачи непрерывной оптимизации, и
гибридные задачи.

6
 1. ОПИСАНИЯ АЛГОРИТМОВ

1.1. Термины и обозначения

Среди стохастических методов оптимизации особенно хорошо за-
рекомендовали себя на практике методы, использующие закономерно-
сти и принципы, заимствованные у самой природы, такие как методы
эволюционной оптимизации, методы роевого интеллекта, алгоритмы
имитации отжига. Первые две группы относятся к так называемым по-
пуляционным методам, поскольку используют системы, состоящие из
агентов (популяций агентов).
Как правило, под агентом понимается некоторая точка в простран-
стве поиска решений задачи, а процесс оптимизации заключается в
перемещении агентов в этом пространстве. При этом методы эволюци-
онной оптимизации предполагают создание на каждом шаге новых по-
пуляций агентов с учетом опыта, полученного предыдущими популя-
циями. Методы роевого интеллекта используют некоторые правила,
задающие косвенный обмен информацией между агентами. Алгорит-
мы роевого интеллекта принципиально отличаются от эволюционных,
поскольку не требуют создания на каждом шаге новых популяций пу-
тем отбора и скрещивания агентов предыдущей популяции, а исполь-
зуют коллективные децентрализованные перемещения агентов одной
популяции, без процедур отбора, уничтожения старых и порождения
новых агентов. Способ определения, относится ли тот или иной попу-
ляционный алгоритм к роевому интеллекту, предложен в [11]: в фор-
мулах, задающих поведение (перемещения, миграцию) агентов роя,
должен присутствовать объект, обеспечивающий косвенный обмен
информацией между агентами.
К эволюционным алгоритмам относятся:
– алгоритм растущих деревьев;
– алгоритм эволюции разума;
– бактериальная оптимизация;

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

Введем следующие обозначения [11]:

f(X) – скалярная целевая функция (фитнесс-функция), для которой
требуется найти экстремальное значение;
X – вектор варьируемых параметров;
D – область допустимых значений X, D  R|X|;
G(X) – функция, задающая ограничения на X;
|S| – количество агентов популяции;
S = {s1, s2,…, s|S| } – множество всех агентов;
Xij – вектор варьируемых параметров i-го агента на j-й итерации ал-
горитма;
Xopt – наилучшее значение вектора варьируемых параметров;
f opt – наилучшее значение целевой функции;
φ(X)= f(X) – значение фитнесс-функции в положении X (фитнесс-
агента).

8
 Рассматривается задача максимизации, которая легко сводится к
задаче минимизации:

f opt  f ( X opt )  max f ( X ) . (1)

X D

Генетический алгоритм и алгоритм имитации отжига хорошо опи-

саны в литературе, а в описании алгоритмов роевого интеллекта суще-
ствуют некоторые трудности из-за отсутствия четкой общепринятой
классификации и путаницы в терминах, поэтому эти алгоритмы описа-
ны подробнее.
На основании проведенного анализа [11] предлагается единая схе-
ма обобщенного описания алгоритмов роевого интеллекта, предпола-
гающая представление алгоритма в следующем виде:
SI = {S, M, A, P, I, O}, (2)
где S – множество агентов роя; М – объект для обмена опытом между
агентами S; A – правила работы роевого алгоритма; P – параметры, ис-
пользуемые в правилах А; I и O – порты (входы и выход) роевого алго-
ритма, посредством которых он взаимодействует с окружающей сре-
дой и управляющей системой.
Любой алгоритм роевого интеллекта включает в себя следующие
этапы, определяемые правилами A:
1) инициализация начальных состояний агентов S;
2) вычисление фитнесс-функции для каждого агента;
3) миграция (перемещение) агентов S с учетом правил А, вектора
параметров P и объекта обмена опытом между агентами M.
По этой схеме и будут даны описания алгоритмов роя пчел, роя ча-
стиц, колонии муравьев и алгоритма поиска косяком рыб.
Ниже кратко рассмотрены семь распространенных стохастических
алгоритма дискретной оптимизации:
– случайный поиск и поиск с возвратом;
– алгоритм имитации отжига (Simulated Annealing),
– генетический алгоритм (Genetic Algorithm),
– алгоритм роя части (Particle Swarm Optimization),
– алгоритм роя пчел (Art Bee Colony),
– алгоритм колонии муравьев,
– алгоритм поиска косяком рыб.
Каждый из этих алгоритмов имеет большое количество модифика-
ций, поэтому даются базовые описания.

9
 1.2. Случайный поиск, поиск с возвратом
Самым простым методом поиска является произвольная выборка
решений. Случайным образом генерируются и оцениваются произ-
вольные решения X до тех пор, пока не будет найдено достаточно хо-
рошее решение или не пройдет заданное время или число итераций
алгоритма. В качестве результата выбирается наилучшее решение из
всех, которые были сформированы в процессе выборки. Основным до-
стоинством метода является простота, хотя выбор произвольных ре-
шений с одинаковой вероятностью может быть нетривиальной зада-
чей. Существуют некоторые условия, при выполнении которых метод
случайного поиска можно успешно применять [15]:
– пространство решений содержит высокую долю удовлетвори-
тельных решений;
– пространство решений не является однородным. Иными словами,
нельзя определить признаки приближения к оптимальному решению.
Простые числа длинами в несколько сотен цифр часто получают
путем случайной генерации чисел и проверки их на простоту, так как
такие числа встречаются относительно часто и сложно выделить при-
знаки близости известного произвольного числа к ближайшему неиз-
вестному простому числу.
Случайный поиск неэффективен для задач, пространство решений
которых не является однородным. Можно устранить этот недостаток,
если на каждой итерации алгоритма учитывать качество предыдущего
решения (поиск с возвратом). Для этого в пространстве оптимизируе-
мых параметров делается шаг в случайном направлении. Если значе-
ние критерия в новом состоянии не лучше, чем ее значение на преды-
дущем шаге, то поиск возвращается в предыдущее состояние, после
чего снова делается шаг в случайном направлении. Если же шаг уда-
чен, т. е. новое состояние лучше предыдущего, то последующий шаг
делается уже из нового состояния. Эффективность метода низкая, так
как при попадании в локальный экстремум длина шага может быть не-
достаточной для выхода из него.
Два рассмотренных метода имеют очень ограниченную область
эффективного использования по сравнению с рассмотренными далее
методами, однако приемы генерации случайного решения, выполнения
шага для перехода в новое состояние и возврата так или иначе исполь-
зуются во всех стохастических методах.

10
 1.3. Алгоритм имитации отжига
Алгоритм возник в середине 1980-х годов, его основатели: Скотт
Киркпатрик, Даниель Желатт, Марио Вечи и Владо Церни [27]. Алго-
ритм основан на аналогии с процессом кристаллизации вещества,
например, при отжиге металла. В ходе этого процесса температура ве-
щества понижается, оно отвердевает, при этом замедляется скорость
движения частиц вещества.
Кристаллическую решетку можно представить как систему частиц,
а ее энергетическое состояние – совокупностью состояний частиц. Ча-
стицы переходят из одного энергетического состояния в другое произ-
вольным образом, но вероятность переходов зависит от температуры
системы. Вероятность перехода из высокоэнергетического состояния в
низкоэнергетическое велика при любой температуре, также существу-
ет отличная от нуля вероятность перехода в состояние с более высоким
значением энергии. Эта вероятность тем выше, чем меньше разница
между состояниями и чем выше температура системы.
Если в роли физической системы представить задачу оптимизации,
в роли энергии системы – значение целевой функции f(X), а в роли ча-
стиц – управляющие переменные X, то можно решать задачу оптими-
зации функции f(X), используя механизмы и законы, которые опреде-
ляют процесс отвердевания. Необходимо задать закон, по которому
будет меняться температура системы, закон, по которому будет слу-
чайным образом изменяться значение координат в пространстве реше-
ния, и правило определения перехода частицы в точку с новыми коор-
динатами. Кроме того, нужно выбрать начальную и конечную темпе-
ратуру (T0 и Tf).
Ниже приведены шаги алгоритма.
1. Генерация случайного начального состояния.
2. Сравнение значения функции с наилучшим найденным, если те-
кущее (X) лучше, то оно принимается в качестве лучшего.
3. Вычисление случайного нового состояния (Xnew) и определение
значения функции для него. Закон распределения может быть любым,
например, экспоненциальным:
x = x + r1Mxln(r2),

где x – одна из координат состояния X; r1 – случайное число (–1

или +1); r2 – случайное число, равномерно распределенное от 0 до 1;

11
Mx – параметр алгоритма, от которого зависит, как далеко от текущей
точки может переместиться процесс поиска за один шаг.
4. Если новое состояние лучше текущего, система переходит в
новое состояние (X = Xnew), иначе случайным образом принимается
решение о переходе или не переходе в новое состояние. При этом в
случае максимизации может быть использовано следующее условие
перехода:

( X new )  ( X )
r,
T

где T – текущая температура; r – случайное число, равномерно распре-

деленное от 0 до 1.
5. Если температура достигла конечной, алгоритм завершается,
иначе температура понижается и происходит переход на шаг 2. Новое
значение температуры на i-м шаге может быть вычислено как

T0
T ,
eivt

где vt – коэффициент, влияющий на скорость снижения температуры.

При завершении алгоритма сохраненное в памяти наилучшее ре-
шение и будет результатом работы алгоритма.
Алгоритм имитации отжига прост в реализации и показывает вы-
сокую эффективность в решении самых разных задач оптимиза-
ции [15]. Однако для получения высокой эффективности может потре-
боваться тщательная настройка формулы понижения температуры как
численных параметров, так и самого вида зависимости, кроме того,
часто температуру меняют не на каждой итерации алгоритма, а через
определенное число итераций.

1.4. Генетический алгоритм

Впервые компьютерным моделированием эволюционного отбора
занялся Нильс Баричелли в 1954 году. Признание генетического алго-
ритма как метода решения оптимизационных задача произошло в
1960–70 годах в результате работ Инго Рехенберга и Джона Голланда

12
[24]. Генетический алгоритм (ГА) относится к стохастическим методам
и основан на принципе естественного эволюционного отбора. Идея
генетических алгоритмов заимствована у живой природы и состоит в
моделировании эволюционного процесса, конечной целью которого
является получение оптимального решения сложной комбинаторной
задачи. В описании метода используются упрощенные биологические
термины.
Основной идеей ГА является борьба за существование между ре-
шениями задачи [24]. Каждое решение записывается в виде некоторого
вектора значений (аллелей), который называется хромосомой, или осо-
бью. Совокупность решений называют популяцией. Каждая особь в
популяции оценивается значением целевой функции, рассчитанной на
основе значений из хромосомы. Более перспективные решения прохо-
дят в следующую стадию и оказывают влияние на «потомство», т. е. на
вновь генерируемые решения.
Необходимо представить задачу таким образом, чтобы ее решение
можно было бы записать в виде генотипа, т. е. вектора значений (ге-
нов). Например, для поиска максимума функции десяти аргументов
y(x1, x2,…, x10) генотип будет состоять из десяти чисел (значений x1,
x2,…, x10), а значение функции y от этих чисел характеризует приспо-
собленность генотипа, поэтому оптимизируемая функция также назы-
вается функцией приспособленности, или фитнесс-функцией.
Стандартный ГА начинает свою работу с формирования начальной
популяции как конечного набора допустимых решений задачи (хромо-
сом). Эти решения могут быть выбраны как случайным образом, так и
с помощью приближенных алгоритмов. На каждом шаге эволюции
формируется новая популяция с помощью вероятностного оператора
селекции. Для каждой новой особи популяции выбираются два реше-
ния, или «родители» (в общем случае родителей может быть и больше
двух). Вероятность выбора решения в качестве родительского прямо
пропорциональна его качеству. В ходе скрещивания двух особей они
по какому-либо правилу обмениваются элементами хромосом (такой
обмен называют кроссинговером). Кроссинговер (употребляется также
название кроссовер, или скрещивание) создает из родительских хромо-
сом одну или несколько новых хромосом. В простейшем случае крос-
синговер в генетическом алгоритме реализуется путем разрезания век-
тора хромосом родителей в случайной позиции и обмене частями век-
торов (рис. 1).

13
 03142570 03142551

76233051 76233070

Рис. 1. Пример кроссинговера

Оператор скрещивания по этим решениям строит новое решение,

которое затем подвергается небольшим случайным модификациям
(мутациям). Мутация – преобразование хромосомы, случайно изменя-
ющее одну или несколько ее позиций (генов). Наиболее распростра-
ненный вид мутаций – случайное изменение только одного из генов
хромосомы. Мутациям подвергаются не все хромосомы, а только вы-
бранные с определенной вероятностью. В результате получается новая
популяция, а старая полностью или частично уничтожается. Популя-
ция следующего поколения в большинстве реализаций генетических
алгоритмов содержит столько же особей, сколько и начальная, но в
силу отбора приспособленность в ней в среднем выше. Теперь описан-
ные процессы отбора, скрещивания и мутации повторяются уже для
этой популяции и т. д.
В каждом следующем поколении наблюдается возникновение но-
вых хороших и плохих решений рассматриваемой задачи. Благодаря
тому что более хорошие решения отбираются с большей вероятно-
стью, их число увеличивается. Иногда в ГА сохраняют несколько луч-
ших хромосом текущего поколения (элитные хромосомы). Схема ра-
боты ГА может быть представлена следующим образом.
1. Генерация начальной популяции.
2. Вычисление целевой функции по каждой особи (хромосоме).
3. Выбор особей и их скрещивание (кроссинговер).
4. Случайные изменения особей (мутация).
5. Если условие завершения выполнено, то конец работы, иначе пе-
рейти к п. 2.

14
 1.5. Алгоритм роя частиц
Специалист в области компьютерной графики Крейг Рейнольдс
создал в 1986 году компьютерную модель для визуальной имитации по-
ведения стаи птиц, основанную на том, что движение каждой птицы
описывается рядом простых правил, связанных с ориентацией на
остальных птиц стаи. Модель заинтересовала ученых и в 1995 году
Джеймс Кеннеди и Рассел Эберхарт предложили метод для оптимиза-
ции непрерывных функций, названный ими алгоритмом роя частиц [26].
Стая птиц всегда действует скоординированно, каждая птица дей-
ствует согласно простым правилам, следит за другими птицами и согла-
сует свое движение с ними. Найдя источник пищи, птица сообщает о
нем всей стае. Именно этот факт создает коллективное поведение и рое-
вой интеллект. Источники пищи обычно расположены случайным обра-
зом, и одной птице очень сложно быстро найти их. Только в том случае,
если птицы будут обмениваться информацией, вся стая сможет выжить.
При переходе к модели слово «птица» заменено на слово «частица»
и вводятся следующие положения:
– частицы существуют в мире, где время дискретно;
– частицы оценивают свое положение с помощью фитнесс-функ-
ции;
– каждая частица знает позицию в пространстве, в которой она
нашла наибольшее количество пищи (своя наилучшая позиция);
– каждая частица знает позицию в пространстве, в которой найдено
наибольшее количество пищи среди всех позиций, в которых были все
частицы (общая наилучшая позиция);
– частицы имеют тенденцию стремиться к лучшим позициям, в ко-
торых были сами, и к общей наилучшей позиции;
– частицы случайным образом меняют свою скорость, так что опи-
санная тенденция определяет лишь усредненное движение частиц;
– частицы обладают инерцией, поэтому их скорость в каждый мо-
мент времени зависит от скорости в предыдущий момент;
– частицы не могут покинуть заданную область поиска.
Основная идея метода заключается в перемещении частиц в про-
странстве решений. Пусть решается задача нахождения минимума
(максимума) функции вида f(X), где X – вектор варьируемых парамет-
ров, которые могут принимать значения из некоторой области D. Тогда
каждая частица в каждый момент времени характеризуется значением
параметров X из области D (координатами точки в пространстве реше-
ний) и значением оптимизируемой функции f(X) (привлекательностью

15
данной точки). При этом частица «помнит» наилучшую точку в про-
странстве решений, в которой была, и стремится в нее вернуться, но
подчиняется также закону инерции и имеет склонность к небольшому
стохастическому изменению направления движения. Однако этих пра-
вил недостаточно для перехода к системе, так как не заданы связи
между элементами. В качестве связи используется так называемая об-
щая память, благодаря которой каждая частица знает координаты
наилучшей точки среди всех, в которых была любая частица роя.
В итоге на движение частицы влияют стремление к своему наилучше-
му положению, стремление к наилучшему среди всех частиц положе-
нию, инерционность и случайные отклонения.
Алгоритм завершается при достижении заданного числа итераций
либо при достижении удовлетворительного решения, либо после исте-
чения отведенного на работу времени. Таким образом, алгоритм мож-
но записать следующим образом.
1. Случайно распределить частицы в области решения, назначить
нулевые начальные скорости.
2. Значения оптимизируемой функции по каждой частице c обнов-
лением при необходимости локальных и глобальных лучших решений.
3. Вычислить новые значения скоростей по каждой частице.
4. Вычислить новые координаты частиц.
5. Если выполнено условие завершения, закончить алгоритм, иначе
перейти на шаг 2.
Результатом работы алгоритма является глобальное лучшее ре-
шение.
Согласно формуле (2) алгоритм роя частиц PSO = {S, M, A, P, I, O}.
1. Множество агентов (частиц) S = {s1, s2,…,s|S| }, |S| – количество
частиц. На j-й итерации i-я частица характеризуется состоянием
   
sij  X ij , Vij , X ijbest , где X ij  x1ij , xij2 , ..., xij – вектор варьируемых
параметров (положение частицы); Vij  v1ij , vij2 , ..., vij  – вектор скоро-

стей частицы; X ijbest  bij1 , bij2 , ..., bij  – наилучше по значению фитнесс-
функции положение частицы среди всех положений, которые она за-
нимала в процессе работы алгоритма от 1-й до j-й итераций; ℓ – коли-
чество варьируемых параметров.
2. Вектор M  X best
j – наилучшее значение вектора варьируемых
параметров, которое было получено среди всех частиц от 1-й до

16
j-й итерации алгоритма. Этот вектор обеспечивает косвенный обмен
опытом между частицами.
3. Алгоритм A описывает механизмы функционирования роя ча-
стиц. Существуют различные модификации этого алгоритма. Далее
представлено описание базового алгоритма.
3.1. Генерация начальных положений и скоростей (j = 1):

X i1  rand (G ( X )), i  1,,| S | ,

где rand(G(X)) – вектор равномерно распределенных случайных вели-

чин, отвечающих ограничениям на область поиска;

Vi1  rand (Vmin , Vmax ), i  1,,| S | ,

где rand(Vmin, Vmax) – вектор равномерно распределенных случайных

величин в диапазоне (Vmin, Vmax).

X ibest
1  X ij , i  1,,| S | .

Произвольно выбирается наилучшая позиция (при вычислении

фитнесс-функций будет определена действительно наилучшая пози-
ция):
X 1best  X 11 .

3.2. Вычисление фитнесс-функций и определение наилучшего по-

ложения:
X ijbest  X ij , ( X ijbest )  ( X ij ) , i  1,,| S | ,

X best
j  X ij , ( X best
j )  ( X ij ) , i  1,,| S | .

Вычисление φ(X) = f(X) происходит во внешней среде с помощью

обмена данными по обратной связи (Ioc, Ooc).
3.3. Перемещения частиц:

 
Vij 1  Vij   1 X ijbest  X ij rnd1   2 ( M  X ij )rnd 2 , i  1,, | S | ,

17
 Vij 1 ,Vmin  Vij 1  Vmax ,

Vij 1   Vmin ,Vij 1  Vmin , i  1,, S ,

 Vmax ,Vij 1  Vmax ;

 X ij  Vij 1 , G ( X ij  Vij 1 )  1,
X ij 1   i  1,, | S | ,
 X ij , G ( X ij  Vij 1 )  0,

где rnd1 и rnd2 – случайные числа, равномерно распределенные в ин-

тервале [0,1); G(X) здесь используется как предикат, который показы-
вает, принадлежит ли X области допустимых значений D.
3.4. Если на j-й итерации выполнено условие остановки, то значе-
ние X best best
final  X j подается на выход O1. Иначе происходит переход к
итерации 2.
4. Вектор P = {α1, α2, ω} – коэффициенты алгоритма А, которые ис-
пользуются в формуле и влияют на перемещения частиц в простран-
стве поиска. Коэффициенты α1 и α2 определяют соответственно сте-
пень учета индивидуального и группового опыта агентов. Коэффици-
ент ω характеризует инерционные свойства частиц.
5. Идентификаторы I и O – описанные выше вход и выход роя, ко-
торые не зависят от реализации алгоритмов роевого интеллекта.

1.6. Алгоритм роя пчел

Алгоритм роя пчел (Artificial Bee Colony Algorithm или Bees Algo-
rithm) разработан в 2005 году несколькими авторами [28]. Метод осно-
ван на симуляции поведения пчел при поиске нектара. Рой пчел от-
правляет несколько разведчиков в случайных направлениях для поиска
нектара. Вернувшись, разведчики сообщают о найденных на поле
участках с цветами, содержащими нектар, и на них вылетают осталь-
ные пчелы. При этом чем больше на участке нектара, тем больше пчел
к нему устремляется. Однако при этом пчелы могут случайным обра-
зом отклоняться от выбранного направления. После возвращения всех
пчел в улей вновь происходит обмен информацией и отправка пчел-
разведчиков и пчел-рабочих. Фактически разведчики действуют по
алгоритму случайного поиска.

18
 Для перехода к формальному описанию алгоритма необходимо
представить поле с цветами как пространство поиска решения, а коли-
чество нектара как критерий задачи оптимизации, т. е. целевую функ-
цию. На каждом шаге работы алгоритма среди всех агентов выбирает-
ся nb лучших по значению целевой функции. Среди прочих выбирается
еще ng лучших, так называемых «выбранных», или «перспективных»
(здесь верхние индексы не являются показателем степени). В некото-
рых вариантах алгоритма требуется, чтобы расстояния между каждой
парой позиций в объединенном множестве лучших и выбранных пози-
ций не превышали определенной величины. Иными словами, если есть
две близкие позиции, то худшая из них по значению целевой функции
отбрасывается, вместо нее берется позиция другого агента, подходя-
щая под условия.
Определенные таким образом позиции (множество лучших Nb, и
множество выбранных Ng) запоминаются, и на следующем шаге в
окрестность каждой лучшей позиции высылается cb пчел, а каждой вы-
бранной cg. Пчела, посылаемая в окрестность участка, попадает в слу-
чайную точку внутри окрестности, например, в двумерном простран-
стве окрестность позиции с центром в точке (x, y) представляет область
([x – rx; x+rx], [y – ry; y+ry]), где rx и ry – параметры алгоритма. Воз-
можно использование одного коэффициента rx по всем измерениям
или вектора RX. Пчелы-разведчики в количестве ns высылаются в слу-
чайные позиции по всему пространству поиска на каждой итерации.
Алгоритм завершается при достижении заданного числа итераций
либо при достижении удовлетворительного решения, либо после ис-
течения отведенного на работу времени. Ниже приведены шаги алго-
ритма.
1. Послать ns разведчиков в случайные точки и вычислить значения
оптимизируемой функции в них.
2. Отобрать из полученных участков Nb лучших и Ng выбранных с
учетом пересечений. Может оказаться, что участков меньше Nb + Ng,
тогда выбрать все имеющиеся с учетом пересечений.
3. Послать в окрестность каждого лучшего участка cb пчел и в
окрестность каждого выбранного участка cg пчел с вычислением целе-
вой функции.
4. Послать ns разведчиков.
5. Если выполнено условие окончания алгоритма, то завершение
алгоритма, иначе переход на шаг 2.
Лучшее из всех полученных на всех итерациях решение и будет ре-
зультатом работы алгоритма.

19
 Согласно формуле (2) для получения обобщенного описания алго-
ритм роя пчел необходимо представить в виде
ABCO = {S, M, A, P, I, O}

и описать каждый элемент.

1. Множество агентов (пчел) S = {s1, s2, …, s|S|}, |S| – количество
агентов. На j-й итерации i-й агент характеризуется состоянием
sij = {Xij}, где Xij = {x1ij, x2ij, …, xℓij,} – вектор варьируемых параметров
(положение агента); ℓ – размерность пространства поиска решений.
2. Средством косвенного обмена M является список лучших и пер-
спективных позиций, найденных на j-й итерации. Нужно отметить, что
в отличие от эволюционных алгоритмов отбираются не агенты, а толь-
ко соответствующие позиции в пространстве поиска, M = {Nijb, Nkjg},
i = 1, ..., nb, k = 1, ..., ng.
3. Алгоритм согласно формуле (1), реализующий правила A, опи-
сывает механизмы функционирования роя пчел, в общем виде может
быть записан следующим образом.
3.1. Инициализация начальных положений (j = 1) выполняется
только для разведчиков:
X i  rand (G ( X )), i  1, ..., n s ,

где ns – количество пчел-разведчиков.

3.2. Вычисление фитнесс-функций каждого агента на текущей j-й
итерации:
( X ij )  f ( X ij ) i  1, ..., S .

3.3. Миграция агентов. После формирования списков лучших и

перспективных, найденных на (j – 1)-й итерации (Nijb, Nkjg), в окрестно-
сти позиций отправляются пчелы-рабочие. В окрестность каждой луч-
шей позиции отправляется cb пчел, в окрестность каждой перспектив-
ной cg пчел. В некоторых вариантах алгоритма число отправляющихся
в окрестность участка пчел зависит от его качества с точки зрения це-
левой функции, но в данном описании это не используется. Таким об-
разом, позиции всех пчел-рабочих определяются следующим образом:

X  Nijb1  Rnd  rad , i  1, ..., nb , k  1, ..., cb , (3)

(i 1) cb  k j

20
 X  Nijg1  Rnd  rad , i  1, ..., n g , k  1, ..., c g , (4)
nb cb  (i 1) cb  k j

где Rnd – вектор, состоящий из l равномерно распределенных случай-

ных величин в интервале от –1 до 1.
Пчелы-разведчики в этом случае отправляются в случайные пози-
ции, координаты которых являются случайными величинами, равно-
мерно распределенными на всем допустимом диапазоне значений:

X  rand (G ( X )), i  1, ..., n s .

nb c b  n g c g  i j

4. Коэффициенты (параметры) алгоритма, используемые в данном

описании и формулах (3) и (4) образуют вектор коэффициентов алго-
ритма P = {ns, nb, ng, сb, cg, rad, rx} – коэффициенты алгоритма, кото-
рый согласно формуле (2) использует правила А. Коэффициент rad
определяет рассеяние агентов при отправлении на лучшие и перспек-
тивные позиции, коэффициент rx задает минимально возможные рас-
стояния между этими позициями. Значение выражения ns + nbсb + ngсg
равно общему количеству агентов роя |S|. От выбора параметров алго-
ритма значительно зависит качество получаемых решений, поэтому
для повышения эффективности алгоритма необходимо адаптировать
значения параметров.
5. Идентификаторы I и O – вход и выход роя, которые не зависят от
реализации алгоритма роевого интеллекта.

1.7. Алгоритм поиска косяком рыб

Алгоритм поиска косяком рыб (Fish School Search, FSS) создан на
основании моделирования движения косяка рыб и представлен Б. Фи-
ло и Л. Нето в 2008 году [6]. В косяке рыбы двигаются в одном
направлении с близкими скоростями, поддерживая согласованное
движение и приблизительно одинаковое расстояние между соседями.
Такой способ коллективного движения помогает эффективнее пере-
мещаться на большие расстояние, находить пищу и защищаться от
хищников. Как и для алгоритма роя частиц, агенты (рыбы) перемеща-
ются в пространстве поиска решений, но правила перемещения и сред-
ство косвенного обмена информацией значительно отличаются.
Каждый агент выполняет несколько видов движений: во-первых,
движения на основании только своего собственного опыта, во-вторых,

21
на основании опыта всего косяка. Второй вид движения разделяется на
две фазы, описанные ниже. В отличие от алгоритма роя частиц косяк
рыб «помнит» только результаты предыдущей итерации, а не наилуч-
шие найденные результаты за весь процесс. Для применения алгорит-
ма требуется, чтобы целевая функция была неотрицательна на всем
пространстве поиска: f(X) ≥ 0, X  D.
Согласно формуле (1) для получения обобщенного описания алго-
ритма поиска косяком рыб его необходимо представить в виде FSS =
={S, M, A, P, I, O}.
Затем требуется поочередно описать каждый элемент FSS и дей-
ствия на отдельных этапах работы алгоритма: инициализацию, вычис-
ление фитнесс-функций и миграцию.
1. Множество агентов (рыб) S = {s1, s2, …, s|S|}, |S| – количество
агентов. На j-й итерации i-й агент характеризуется состоянием
sij = {Xij, Vij, wij}, где Xij = {x1ij, x2ij, …, xℓij,} – вектор варьируемых пара-
метров (положение агента); ℓ – размерность пространства поиска ре-
шений; Vij = {v1ij, v2ij, …, vℓij} – вектор скоростей агента; wij – вес i-го
агента на j-й итерации.
2. Средством косвенного обмена M является вектор из двух эле-
ментов. Первый из них является скаляром и определяет взвешенную
сумму индивидуальных перемещений рыб, а второй – вектором дли-
ной l и представляет взвешенный центр тяжести всего косяка, M =
= {mSj, Сj}.
3. Реализация правил A определяет механизм функционирования
косяка рыб и согласно используемой схеме описания должна включать
в себя инициализацию, вычисление фитнесс-функций и миграцию.
Существуют различные вариации алгоритма поиска косяком рыб. Да-
лее представлена схема алгоритма в соответствии с описанием.
3.1. Инициализация начальных положений (j = 1):

X i1  rand (G ( X )), i  1, ..., | S | ,

где rand(G(X)) – вектор равномерно распределенных случайных вели-

чин, отвечающих ограничениям на область поиска;
wmax
wi1  , i  1, ..., S ,
2
где wmax – один из параметров алгоритма.

22
 3.2. Вычисление фитнесс-функций каждого агента на текущей
j-й итерации:
( X ij )  f ( X ij ) i  1, ..., S .

3.3. Миграция, т. е. перемещения агентов в рамках одной итерации,

включает в себя несколько стадий, в данное описание вводится проме-
жуточная между итерациями j и j + 1 итерация с индексом j + 0.5. Этот
индекс введен для упрощения формул и показывает, что соответству-
ющие значения скорости i-й частицы Vij+0.5, ее положения Xij+0.5 и инер-
ции wij+0.5 являются промежуточным в расчетах.
3.3.1. Индивидуальные перемещения агентов между итерациями j
и j + 1 выполняются независимо для всех агентов и состоят из трех ша-
гов. На первом шаге задается случайное значение скорости:

Vij  0.5  rnd  Vmax , i  1, ..., S ,

где rnd – случайное число, равномерно распределенное в интерва-

ле [0,1]; Vmax – вектор максимальных скоростей по каждому измерению
области поиска Vmax = {v1max, v2max, …, vℓmax}. Вектор может быть заме-
нен скалярной величиной vmax в случае равенства всех его элементов.
На втором шаге выполняется перемещение с найденной скоростью
в пределах области допустимых значений:
 X ij  Vij 0.5 , G ( X ij  Vij 0.5 )  1,
X ij 0.5   i  1, ..., S , (5)
 X ij , G ( X ij  Vij 0.5 )  0,

где G(X) здесь используется как предикат, который показывает, при-

надлежит ли X области допустимых значений D.
Последний третий шаг возвращает агента на предыдущую пози-
цию, если значение целевой функции в новой позиции оказалось хуже:
 X ij 0.5 , ( X ij  0.5 )  ( X ij ),
X ij 0.5   i  1, ..., S .
 X ij , ( X ij 0.5 )  ( X ij ),
3.3.2. Инстинктивно-коллективное плавание выполняется всеми
рыбами в одном направлении и с одинаковой скоростью. На этом этапе
используется объект косвенного взаимодействия mSj:

23
 m Sj 
i(Vij 0.5 (( X ij 0.5 )  ( X ij )))
i(( X ij 0.5 )  ( X ij ))
Каждая рыба после этого перемещается на данную величину:

X ij  0.5  X ij  0.5  m Sj , i  1, ..., S .

Если какой-либо элемент Xij+0.5 выходит за границу области допу-

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

( X ij  0.5 )  ( X ij )
wij  0.5  wij  i  1, ..., S ,
max(( X ij  0.5 ), ( X ij ))

с учетом ограничения
1  wij 0.5  wmax .

Если в результате индивидуального и инстинктивно-коллективного

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

Cj 
iwij 0.5 X ij 0.5 i  1, ..., S . (6)
iwij 0.5
Перемещения при коллективно-волевом плавании выполняется по
следующему правилу:
 X ij 0.5  vol ( X ij 0.5  C j ), ws j 0.5  ws j 0.5 ,
X ij 1   i  1, ..., S ,
 X ij 0.5  vol ( X ij  0.5  C j ), ws j 0.5  ws j 0.5 ,

24
где wsj+0.5 – сумма весов всех агентов на текущей стадии (знаменатель
в формуле (6)), wsj – 0.5 является аналогичной суммой на предыдущей
итерации, а vol определяет величину шага перемещений и вычисляется
как
vol  rnd  volmax ,

где volmax – максимально возможный размер шага; rnd – случайная ве-

личина, равномерно распределенная в интервале [0, 1].
Чтобы получить окончательные позиции агентов на итерации j + 1,
нужно учесть границы области допустимых значений аналогично фор-
муле (5).
4. Коэффициенты (параметры) алгоритма образуют вектор P =
= {vmax, wmax, volmax}. Эти коэффициенты определяют поведение роя,
выбор их значений является особой задачей, которая решается с по-
мощью различных методов адаптации.
5. Идентификаторы I и O – вход и выход роя, которые не зависят от
реализации алгоритма роевого интеллекта.

1.8. Алгоритм колонии муравьев

Алгоритм основан на модели, симулирующей процесс поиска му-
равьями кратчайших путей от муравейника до источников пищи, и
разработан М. Дорино в 1990-е годы [20, 21]. Муравьи решают задачи
поиска путей с помощью химической регуляции. Каждый муравей
оставляет за собой на земле дорожку особых веществ – феромонов.
Другой муравей, почуяв след на земле, устремляется по нему. Чем
больше по одному пути прошло муравьев, тем заметнее для них след, а
чем более заметен след, тем большее желание пойти в ту же сторону
возникает у муравьев. Поскольку муравьи, нашедшие самый короткий
путь к «кормушке», тратят меньше времени на путь туда и обратно, их
след быстро становится самым заметным. Он привлекает большее чис-
ло муравьев, таким образом, процесс поиска более короткого пути
быстро завершается. Остальные пути – менее используемые – посте-
пенно пропадают. Можно сформулировать основные принципы взаи-
модействия муравьев: случайность, многократность, положительная
обратная связь.
Так как каждый муравей выполняет примитивные действия, то и
алгоритм получается очень простым и сводится к многократному об-

25
ходу некоторого графа, дуги которого имеют не только вес, но и до-
полнительную динамически меняющуюся количественную характери-
стику, называемую количеством феромона или просто феромоном.
Итерационный алгоритм включает в себя построение решения все-
ми муравьями, улучшение решения методом локального поиска, об-
новление феромона. Построение решения начинается с пустого
частичного решения, которое расширяется путем добавления к нему
новой допустимой компоненты решения. В отличие от алгоритма роя
частиц, который описывается как алгоритм для нахождения экстрему-
мов непрерывных функций, муравьиный алгоритм в классической
формулировке решает комбинаторные задачи, например, задачу ком-
мивояжера. Поэтому вектором варьируемых параметров в муравьином
алгоритме обычно является последовательность узлов в графе, опти-
мальный способ обхода которого нужно найти (в задаче коммивояже-
ра – последовательность городов в искомом маршруте). Тем не менее
представленная в формуле (2) структура полностью сохраняется.
Согласно формуле (2) алгоритм колонии муравьев ACO = {S, M, A,
P, I, O}. Для удобства будем считать, что решается задача минимиза-
ции (так как муравьи ищут наикратчайший путь).
Множество агентов (муравьев) S = {s1, s2,…,s|S| }, |S| – количество
муравьев. На j-й итерации i-й муравей характеризуется состоянием
sij = {Xij, Tij}, где Xij = {x1ij, x2ij,…, xℓij} – вектор варьируемых парамет-
ров (последовательность узлов графа), Tij = {t1ij, t2ij,…, tℓij} – вектор бу-
левых переменных, которые показывают, был ли ℓ-й узел посещен
i-м муравьем на j-й итерации (в начале каждой итерации все его ком-
поненты равны 0).
Граф M = {F, R} – граф, каждая дуга которого имеет два веса: пе-
ременный (количество феромона) и постоянный (характеризующий
задачу, например, в задаче коммивояжера – это расстояние между го-
родами). Поэтому граф М можно представить в виде двух графов с
одинаковыми структурами, но разными весами дуг (F и R):
 11  1l   r11  r1l 
   
F     , R     ,
    r  r 
 l1 ll   l1 ll 

где τk1k2 – количество феромона на дуге, соединяющей k1-й и k2-й узлы

графа F, rk1k2 – вес (длина) дуги, соединяющей k1-й и k2-й узлы графа R,
при этом в общем случае τk1k2 ≠ τk2k1 и rk1k2 ≠ rk2k1.

26
 Алгоритм А описывает механизмы функционирования колонии му-
равьев.
1. Генерация начальных положений. В зависимости от задачи каж-
дый муравей может быть создан в случайном узле графа или в задан-
ном. Если муравей помещен в узел k, то

xi11  k , tik1  1.

На каждую дугу наносится некоторое ненулевое количество феро-

мона τij = τmin .
2. В алгоритме колонии муравьев на первой итерации (j = 1) второй
шаг пропускается, так как для вычисления фитнесс-функций необхо-
димо выполнить перемещения агентов.
Для остальных шагов выполняются следующие действия:
– вычисление целевых функций:

( X ij )  f ( X ij ), i  1, | S | ,

после каждого вычисления целевой функции происходит сравнение ее

значения с ( X best
j ) аналогично формуле X j
best
 X ij , ( X best
j )  ( X ij ),
i  1,,| S | ;
– определение количества феромона, которое нужно нанести на ду-
гу, соединяющую узлы k1 и k2 (феромон для i-го муравья наносится
только на те дуги, которые вошли в маршрут Xij):

 γ
 , в X ij k1 следует сразу за k2 ,
ijk1k2   φ(X ij ) i  1, ... S ,
 0, если не следует сразу за k ,
 2

k1  1,..., l , k2  1,..., l ;

– пересчет количества феромона на всем графе с учетом испарения

и ограничений:

θ  ρτ kj1k2  τijk1k2 , k1  1,, l , k2  1,, l ,

27
  ,   min ,
kj1k2  
 min ,   min .

3. Перемещения агентов. В каждом узле k муравей выбирает, в ка-

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

 (τ km )α (η(rkm ))β
 l , tm  0,
 
Pm    z 1, t 0 (τ kz )α (η(rkz ))β
z

 0, tm  1.

Здесь (rkm) – некоторая функция от веса дуги, в простейшем случае

(rkm) = rkm.
После вычисления вероятностей с помощью розыгрыша по жребию
происходит определение, в какой узел m должна переместиться части-
ца. При этом tm = 1, номер узла добавляется в маршрут частицы. После
окончания обхода вектор T обнуляется.
4. Если на j-й итерации выполнено условие остановки, то значение
X final  X best
best
j подается на выход O1. Иначе происходит переход к ите-
рации 2.
Вектор P = {α, β, γ, ρ} – коэффициенты алгоритма А. Коэффици-
ент α определяет степень влияния количества феромона на дуге на ве-
роятность того, что муравей выберет эту дугу. Коэффициент β опреде-
ляет степень влияния веса дуги графа на вероятность ее выбора. Коэф-
фициент γ – коэффициент интенсивности выделения феромона. Коэф-
фициент ρ влияет на испаряемость феромона, принимает значения от 0
(нет испарения) до 1 (испаряется до минимального уровня после каж-
дой итерации).
Идентификаторы I и O – вход и выход роя, которые не зависят от
реализации алгоритмов роевого интеллекта.

28
 2. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ
АЛГОРИТМОВ
Раздел посвящен программной реализации алгоритмов стохастиче-
ской оптимизации и их применению. Особое внимание уделено ис-
пользованию алгоритмов в такой области искусственного интеллекта,
как машинное обучение.

2.1. Области применения

Благодаря своей гибкости и универсальности стохастические мето-
ды оптимизации широко применяются во многих областях, некоторые
из которых перечислены ниже.
1. Биоинформатика. Стохастическая оптимизация используется в
диагностике некоторых болезней, таких как рак, болезнь Паркинсона, в
разработке медицинских препаратов, в задачах анализа генетических
последовательностей.
2. Построение телекоммуникационных сетей: выбор наиболее эф-
фективных схем различных видов сетей, оптимизация управления по-
токами данных в сети, разработка структур сетей GPS. Особенно эф-
фективны в этой области алгоритмы роевого интеллекта.
3. Решение комбинаторных задач в планировании производствен-
ных и логистических процессов, таких как задача коммивояжера,
транспортная задача, задача о назначениях, задачи календарного пла-
нирования, задачи раскроя и упаковки, раскраски графов, задача о
клике и многие другие.
4. Управление и контроль в автоматических и автоматизирован-
ных системах: разработка контроллеров, включая ПИД-контрол-
леры, управление транспортными потоками, контроль работы дви-
гателей.
5. Поиск наилучших параметров и конфигураций двигателей, лета-
тельных аппаратов, электрических сетей, сплавов и т. д.
6. Анализ изображений и видео. Распознавание лиц, идентифика-
ция людей по изображению глаза, сегментация изображений, поиск
изображений, обнаружение движений, слияние изображений, распо-
знавание символов, повышение контрастности, MPEG-оптимизация.
Среди других областей применения можно выделить энергетику,
компьютерную графику и визуализацию, робототехнику, обработку

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

2.2. Машинное обучение

В настоящем разделе дается очень краткое введение в теорию обу-
чения машин и приводится пример использования стохастических ме-
тодов оптимизации в качестве инструмента для машинного обучения.
Машинное обучение (Machine Learning, теория обучения машин) –
один из важнейших разделов искусственного интеллекта на современ-
ном этапе развития науки. Сфера применений машинного обучения
постоянно расширяется из-за распространения информационных тех-
нологий и накопления огромных объёмов данных. Наиболее тесно тео-
рия машинного обучения связана с интеллектуальным анализом дан-
ных (Data Mining).
Теория машинного обучения возникла в конце 1950 годов и разви-
вается на стыке прикладной статистики, численных методов оптими-
зации, комбинаторики, дискретного анализа, вычислительной матема-
тики [2]. Сейчас машинное обучение является самостоятельным и
быстроразвивающимся разделом математики и имеет большую прак-
тическую ценность. Ни один серьезный проект по распознаванию ре-
чи, изображений или видео, по созданию интеллектуальных систем
управления, ни одна крупная социальная сеть или интернет-магазин не
обходятся без применения машинного обучения. Так, например, появ-
ление электронной коммерции привело к возможности собирать све-
дения о клиентах, чтобы затем извлекать из полученных данных новые
знания о предпочтениях людей. Поэтому сегодня специалисты в обла-
сти машинного обучения востребованы во всех крупных IT-компаниях
и во многих научных институтах.

2.2.1. Задача машинного обучения

Как правило, машинное обучение направлено на решение задачи
следующего вида [2].
1. Пусть V – множество объектов, W – множество допустимых от-
ветов и существует некоторая неизвестная зависимость между объек-
тами и ответами w: V → W, т. е. w ставит каждому объекту из V в со-
ответствие некоторый ответ из W (например, если V – множество изоб-

30
ражений отдельных цифр, а W – множество {0, 1, 2, …, 9}, то w – неко-
торый черный ящик, определяющий цифру по изображению).
2. Для некоторого подмножества V* = {v1, v2, …, vk} известны отве-
ты wi = w(vi*). Пары (vi, wi) называют прецедентами, а все множество
пар (vi, wi), i = 1, …, k называют обучающей выборкой (training sample).
3. Необходимо построить такое отображение (функцию, алгоритм,
модель) a: V → W, которое было бы как можно ближе к неизвестной
зависимости w(v) на всем множестве объектов V (не только на обуча-
ющей выборке). При этом отображение a должно быть реализуемо на
компьютере (машине) и работать автоматически, без участия человека.

2.2.2. Признаки
Каждый элемент v из множества V можно назвать объектом. Объ-
ект v имеет ряд характеристик (свойств), называемых признаками.
Например, у человека есть такие признаки, как возраст, рост, вес, пол.
Для изображения в формате BMP признаком будет является матрица
пикселей, для слова признаком является количество букв, какая буква
стоит в каждой позиции слова – тоже признак.
Выделяют следующие виды признаков:
– бинарные (0 или 1);
– номинальные (признак принимает значения из некоторого конеч-
ного множества);
– количественные (вещественные значения).
Таким образом, у объекта имеется вектор признаков {p1, p2,…, pn}.
Тогда множество объектов V* можно представить матрицей
 p1 (v1 )  pn (v1 ) 
* 
V     .
 p (v )  pn (vk ) 
 1 k
Например, ставшая классической в литературе по машинному обу-
чению задача ирисов Фишера заключается в построении алгоритма,
определяющего вид ириса (Iris setosa, Iris virginica или Iris versicolor)
по четырем признакам:
– длине наружной доли околоцветника (sepal length);
– ширине наружной доли околоцветника (sepal width);
– длине внутренней доли околоцветника (petal length);
– ширине внутренней доли околоцветника (petal width).

31
 Пример матрицы для этой задачи легко найти по запросу «класси-
фикация ирисов», или «ирисы Фишера».
Для упрощения формул часто объект и вектор его параметров
отождествляют, так что vi = {p1(vi), p2(vi),…, pn(vi)}, в этом случае под
записью f(vi) понимают функцию от всех признаков f(p1(vi), p2(vi),…,
pn(vi)).

2.2.3. Виды задач и примеры

Множество ответов W может иметь различный вид в зависимости
от вида задачи машинного обучения.
1. Классификация непересекающихся классов. Множество W =
= {1, …, m}, каждый объект v принадлежит одному и только одному из
классов. Такие задачи называют задачами распознавания образов. К
ним относятся определение символов на изображениях, распознавание
жестов, определение надежности клиентов и компаний, классификация
документов (в частности, фильтрация спама), определение заболевания
по данным анализов.
2. Классификация пересекающихся классов. Упомянутая задача
определения заболевания (диагностики) может быть отнесена и к клас-
сификации пересекающихся классов, поскольку одновременно воз-
можно наличие нескольких болезней, в этом случае W = {0,1}m. Задача
часто возникает при диагностике оборудования, поиске причин собы-
тий, разделении документов на пересекающиеся группы.
3. Восстановление регрессии. Множество W принадлежит множе-
ству вещественных чисел. Например, по известным параметрам дома и
статистике продаж (какие дома за какие суммы были куплены) нужно
определить наиболее подходящую цену данного дома. Особенно часто
такая задача возникает при прогнозировании. Например, задача про-
гнозирования потребительского спроса на определенный товар, пред-
сказание процесса распространения эпидемий.
Задачи классификации можно также разделить на задачи собствен-
но классификации и задачи кластеризации. В задачах классификации
заранее известны возможные классы и множество прецедентов (vi, wi),
i = 1, …, k. В задачах кластеризации ни по одному из объектов неиз-
вестно, к какому классу он принадлежит, т. е. нет множества прецеден-
тов и, как правило, неизвестно и количество классов. Кластеризация
помогает выявлять социологические группы, разбивать изображения
на отдельные объекты, выполнять поиск групп семантически близких
документов или сообщений. Задача кластеризации стала особенно

32
актуальной с развитием электронной коммерции, поскольку разделе-
ние клиентов на группы позволяет создавать для каждой группы спе-
цифические стратегии продвижения товаров и услуг.

2.2.4. Методы машинного обучения и оценка качества

Существует множество методов решения задач классификации,
кластеризации и восстановления регрессии. Ниже перечислены наибо-
лее эффективные и распространенные:
– деревья решений (Decision Tree);
– метод опорных векторов (Support Vector Machine, SVM);
– метод k ближайших соседей (k-Nearest Neighbor, kNN);
– нейронные сети (искусственные нейронные сети, Artificial Neural
Networks);
– глубокое обучение (Deep Learning), которое обычно используется
для нейронных сетей;
– наивный Байесовский классификатор (Naive Bayes classifier);
– EM-алгоритм (Expectation-maximization);
– построение решающих правил (Decision rule algorithms);
– для повышения качества методов часто используют техники бу-
стинга (boosting) и баггинга (bagging), позволяющие объединять набо-
ры алгоритмов a в так называемые комитеты или ансамбли.
Чтобы построить хорошо работающий алгоритм a: V → W, необхо-
димо уметь определять качество алгоритма. Часто используют следу-
ющий функционал качества алгоритма a на выборке V*:
1 k
Q ( a,V * )   q(a, vi ) .
k i 1
Функция q(a, v) показывает ошибку распознавания алгоритма a при
анализе объекта v. Это может быть бинарная функция, принимающая
значение 0, если q(a, v) = wi, может быть модуль разности или квадрат
разности q(a, v) и wi. Чем меньше ошибок допустит алгоритм a, тем
выше его качество Q(a, V*).

2.2.5. Обучение как задача оптимизации

Алгоритм a имеет некоторую основу и ряд параметров, значения
которых нужно подобрать, чтобы обеспечить наилучшее качество ре-
шения задачи. Подбор параметров и называют обучением.

33
 В качестве простого примера можно взять задачу классификации
на два непересекающихся класса, W = {–1, +1}. Рассмотрим метод ли-
нейной классификации, при котором алгоритм a можно представить в
следующем виде:
 n 
a(v, X )  sign   x j p j (v)  x0  ,
 j 1 
 
где X = {x0, x2, …, xn} – параметры алгоритма (веса признаков p1(v),
p2(v), …). Таким образом, каждый признак объекта v умножается на
вес признака, затем полученные произведения суммируются, и к ним
прибавляется параметр x0. Если полученная сумма больше 0, то
объект v будет отнесен к классу –1, иначе +1. Пример такого класси-
фикатора показан на рис. 2.

Рис. 2. Пример линейного классификатора

Объекты класса –1 показаны кружками, а класса +1 треугольника-
ми. По осям абсцисс и ординат отложены значения признаков p1 и p2
соответственно. Для каждого объекта значение признаков p1 и p2 зада-

34
ют координаты его центра на плоскости P1P2. Линейный классифика-
тор, показанный линией, разделяющей классы, имеет вид (x0 = 10,
x1 = 5, x2 = –2):
a(v, {5, 2,10})  sign (5 p1 (v)  2 p2 (v) 10) .
Все объекты, расположенные выше черты на рис. 2, будут отнесе-
ны к классу кружков, расположенные ниже – к классу треугольников.
Черту называют разделяющей плоскостью.

2.2.6. Примеры использования стохастической оптимизации

для задач обучения
Для задачи, показанной на рис. 2, подобный классификатор можно
построить вручную, хотя линейный классификатор рассматриваемого
вида не способен дать 100 %-е качество для этой задачи. Обратите
внимание, что классификатор допускает одну ошибку (треугольник с
центром в точке (1.8, 14) отнесен к классу кружков.
На практике решаются проблемы на порядок сложнее и для них
подобрать параметры алгоритма вручную уже невозможно. Невозмож-
но выполнить и полный перебор всех возможных значений, так как на
это уйдет слишком много времени. Так, если нужно подобрать значе-
ния 10 параметров в диапазоне от –100 до 100 с шагом 0.1, то потребу-
ется построить и оценить примерно 1×1033 возможных комбинаций
значений параметров. Поэтому часто для подбора параметров (обуче-
ния) используют стохастические методы оптимизации. В этом случае
задача обучения алгоритма a, имеющего вектор параметров X, на вы-
борке V*может быть записана так:
1 k 
X  argmin  q (a ( X ), vi )  ,

X D  k i 1


где D – область допустимых значений вектора X параметров алгорит-
ма a(X), а k – количество объектов в обучающей выборке V*. Таким
образом, задача обучения алгоритма заключается в минимизации оши-
бок, которые алгоритм допускает на обучающей выборке.
При решении задачи алгоритмом роевого интеллекта, показанной
на рис. 2, каждый агент будет представлять некоторую разделяющую
плоскость, а его фитнесс-функция будет равняться количеству совер-
шенных ошибок классификации. В процессе работы алгоритма опти-

35
мизации агенты будут перемещаться, стремясь снизить количество
ошибок, в итоге будет определена разделяющая плоскость, дающая
минимум ошибок (создание приложения визуализации процесса обу-
чения можно порекомендовать в качестве полезного учебного приме-
ра, позволяющего потренироваться и в машинном обучении, и в опти-
мизации, и в компьютерной графике).
Необходимо отметить, что в общем случае мера качества алгорит-
ма зависит не только от количества ошибок, однако этот вопрос не
входит в рамки рассмотрения данного пособия, как и многие другие
аспекты машинного обучения (явление переобучения, разделение тре-
нировочной выборки на собственно тренировочную и тестовую с пере-
крестной проверкой алгоритмов, дополнительные критерии эффектив-
ности и др.), которые можно изучить по материалам, например,
К.В. Воронцова [2]. Приведенный линейный классификатор является
одним из самых простых, для других алгоритмов классификации век-
тор параметров может задавать не только численные параметры, но и
саму структуру алгоритма, например, число узлов скрытого слоя
нейронной сети.
В качестве еще одного примера рассмотрим решение задачи кла-
стеризации алгоритмом имитации отжига. При этом в качестве векто-
ра X можно взять не параметры алгоритма кластеризации, а вектор,
показывающий, к какому кластеру какой объект обучающей выборки
относится. Положим, что число кластеров известно и равно m (сами
кластеры обозначим 1, 2, 3, … m), тогда вектор X будет иметь длину m,
а значение xi будет определять кластер объекта vi, xi {1, 2, …m},
i = 1,…m. Критерием оптимальности может быть сумма расстояний
между объектами одного кластера и сумма расстояний между объек-
тами разных классов:
m k k k k
f ( X )    d (v j , vl )    d (v j , vl ) .
i 1 j 1l 1,l  j j 1l 1,l  j
x j  xl i x j  xl

Формула показывает, что для каждого из кластеров определяется

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

36
собами. Одним из наиболее популярных является евклидово расстоя-
ние
n
1
d (v j , vl ) 
n
 ( ph (v j )  ph (vl ))2 .
h 1

Конечно, не нужно каждый раз при вычислении критерия опреде-

лять расстояния, достаточно сделать это один раз и сохранить расстоя-
ния между всеми объектами в матрицу.
Алгоритм имитации отжига начинает работу с генерации произ-
вольного разбиения объектов множества V* на классы. Для получен-
ного разбиения, заданного вектором X, определяется значение крите-
рия f(X). Затем произвольно выбирается элемент xi вектора X и его зна-
чение меняется на любое другое из множества {1, 2, …, m}, что соот-
ветствует перемещению объекта vi из одного кластера в другой. В ре-
зультате получается вектор Xnew, для которого тоже определяется зна-
чение критерия (для этого нужно учесть перемещение только одного
объекта, не пересчитывая все выражение). Затем определяется, выпол-
нить переход к полученному разбиению (X = Xnew) или вернуться к
предыдущему (см. раздел 1.3 «Алгоритм имитации отжига»). На этом
итерация завершается, выполняется понижение температуры и вновь
выбирается случайный элемент вектора X и его значение случайным
образом меняется, и так далее, пока не будет выполнено условие за-
вершения алгоритма. На первых итерациях, когда температура высока,
объекты будут постоянно перемещаться из одного кластера в другой с
небольшой тенденцией к улучшению разбиения на кластеры (поиск
приблизительного решения). На последних итерациях, когда прибли-
зительные разбиения будут получены и температура будет низкой,
объекты будут перемещаться редко, но почти все перемещения будут
приводить к улучшению разбиения, пока это возможно (стадия деталь-
ного уточнения). Чтобы получить высокую эффективность, нужно
грамотно настроить график понижения температуры и установить до-
статочное количество итераций. Подбор графика понижения темпера-
тур выполняется исходя из экспериментов, опыта работы со стохасти-
ческими алгоритмами.
В настоящее время для применения машинного обучения на прак-
тике не требуется реализовывать алгоритм классификации и алгорит-
мы обучения самостоятельно. Существует множество готовых инстру-
ментов: Weka, KINME, RapidMiner, PredictionIO, различные библиоте-

37
ки для языков программирования R и Python, которые наиболее часто
применяются для интеллектуального анализа данных. Однако для их
успешного применения все же необходимо знать математические ос-
новы машинного обучения и методов оптимизации.

2.3. Рекомендации по реализации алгоритмов

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

Интерфейс. Для повышения скорости реализации алгоритмов,

гибкости и масштабируемости разрабатываемых программных систем
необходимо избегать зависимости между алгоритмами, интерфейсами
к ним и решаемыми задачами.
В рамках объектно-ориентированного программирования каждый
алгоритм оптимизации можно рассматривать как класс. Полезно ис-
пользовать единые интерфейсы таких классов, чтобы применение того
или иного алгоритма выполнялось единообразно. В этом случае можно
применить шаблон проектирования «Template method», который задает
общую структуру поведения связанных классов. При этом детали по-
ведения отдельного алгоритмов задаются в реализации дочерних клас-
сов. Общими для дочерних классов будут методы управления алго-
ритмами, настройки, инициализации, перемещения агентов и возвра-
щения результатов работы. Пример базового класса на языке програм-
мирования C++ приведен ниже.
class Optimizator
{
public:
virtual void start() = 0;
virtual void stop() = 0;
void setIterationNumber(int ni); //установка
количества итераций
void setAgentsNumber(int na); //установка
количества агентов
virtual void setParameters(double *arrParams) = 0;
//установка параметров
void setCriterion(ICreator *pCreator);//этот
метод будет описан ниже

38
 double getBest(double *bestSolution);//возврат
// найденного решения
// (в bestSolution записывается вектор
// искомых переменных, метод возвращает
// значение критерия
virtual ~Optimizator () {}

protected:
virtual void initialization() = 0;
virtual void move() = 0;

int numberAgents;
int numberIterations;
double *bestSolution;
ICreator *creator;
//указатель на описанный ниже объект для
//вычисления критерия
};
Для обеспечения единообразной работы алгоритмов оптимизации с
различными задачами можно реализовать некоторый интерфейс, обо-
значенный здесь как ICreator, имеющий метод getCriterion, который
соответствует критерию f(X) и принимает управляющие переменные, а
возвращает значение целевой функции. Можно разбить вектор X на
целочисленную и непрерывную части. Например, на языке програм-
мирования С++ реализация такого интерфейса с помощью абстрактно-
го класса может быть следующей:
class ICreator
{
public:
virtual double getCriterion(double *arrayDouble,
int *arrayInt) = 0;
virtual ~ICreator() {}
};

В языке Java реализация интерфейса немного короче:

public interface ICreator

{
double getCriterion(double [] arrayDouble,
int [] arrayInt);
};

Затем в любом классе, представляющем модель задачи оптимиза-

ции, нужно реализовать метод getCriterion, а сам класс должен насле-

39
доваться от класса ICreator (в C++) или реализовать интерфейс
ICreator (в Java), например, для задачи Химмельблау:
//C++
class Test : public ICreator
{
public:
virtual double getCriterion(double *arrDouble,
int *arrInt);
};

double Test::getCriterion(double *arrDouble, int *arrInt)

{
double x0 = arrDouble[0], x1 = arrDouble[1];
return pow((x0*x0 + x1 – 11.), 2)
+ pow((x0+ x1*x1 – 7.), 2);
}

//Java
public class Test implements ICreator
{
double getCriterion(double [] arrayDouble,
int [] arrayInt);
double x0 = arrDouble[0], x1 = arrDouble[1];
return [Link]((x0*x0 + x1 – 11.), 2)
+ [Link]((x0+ x1*x1 – 7.), 2);
}

Сам класс, представляющий модель задачи, может быть только

оболочкой для целой архитектуры, если рассматривается оптимизация
сложного объекта управления. Но каким бы сложным ни была внут-
ренняя логика расчета критерия, для алгоритма оптимизации она цели-
ком будет сокрыта интерфейсом ICreator. Если в приведенном приме-
ре нужно будет заменить целевую функцию, это никак не повлияет на
интерфейс ICreator и код алгоритмов оптимизации.
Выше в коде класса Optimizator есть метод setCriterion и указатель
на объект класса ICreator. Объект, вычисляющий целевую функцию,
передается по указателю в класс Optimizator через метод setCriterion, в
этом методе данный объект связывается с указателем creator. В ре-
зультате благодаря полиморфизму в классах, реализующих алгоритмы
оптимизации, можно вызывать вычисление целевой функции через
метод getCriterion интерфейса ICreator независимо от класса, в кото-
ром будет производиться это вычисление. Таким образом, код алго-
ритма оптимизации никак не связан с кодом класса, реализующего ре-
шаемую задачу оптимизации.

40
 Использование параллельных вычислений. Согласно закону
Амдала, параллельные вычисления тем эффективнее, чем больше доля
расчетов, выполняемых параллельно:
1
S ( p)  ,
1 a
a
p
где S(p) – теоретическое ускорение, т. е. эффект от распараллеливания;
p – количество используемых процессоров (ядер); a – доля операций,
которые нужно выполнять последовательно.
Как правило, в рамках одной итерации процесс перемещения аген-
тов популяционных алгоритмов легко поддается распараллеливанию,
так как при этом не происходит конфликтов чтения данных и каждый
процессор просто работает со своей частью популяции. Но это не все-
гда верно, например, в муравьином алгоритме процесс обновления фе-
ромона на ребрах графа может приводить к конфликтам потоков.
Можно предложить более универсальный и часто более эффективный
другой подход – каждый процессор работает со своим экземпляром
алгоритма, а обмен результатами происходит лишь время от времени.
В простейшем случае, если не происходит обмена данными между эк-
земплярами алгоритмов, это равносильно последовательному запуску
алгоритмов с точки зрения полученных решений задачи, а ожидаемое
повышение скорости работы будет близко к количеству используемых
процессоров, так как доля последовательно выполняемых операций
очень мала.

Взаимодействие с пользователем. Близким к предыдущему явля-

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

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

Выбор используемых структур данных. Общеизвестно, что в

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

42
 Настройка параметров. Многие исследования показывают, что
для стохастических методов необходима настройка, учитывающая
особенности задач [6, 10, 15, 29]. Для выполнения такой настройки
можно использовать различные метаэвристические способы адапта-
ции. При этом один алгоритм оптимизации подбирает параметры дру-
гого алгоритма, который, в свою очередь, решает прикладную задачу
оптимизации. Такой подход называют мета-оптимизацией. Для задач
автоматического оперативного управления, которые требуют получе-
ния решения в реальном времени наискорейшим образом, использова-
ние адаптивных алгоритмов может быть затруднено из-за высоких за-
трат времени на расчеты.
В некоторых задачах адаптивные алгоритмы целесообразно приме-
нять, поскольку в этих задачах время, сэкономленное на решении,
обычно намного меньше потерь времени и других ресурсов от неэф-
фективных решений, например, в планировании работ. Но даже и для
задач, которые необходимо решать быстро, полезно использовать ма-
шинное обучение, чтобы опыт решения предыдущих задач помогал
эффективнее решать новые, поскольку для одного объекта управления
или для одного типа задач можно ожидать достаточно близкие усло-
вия, чтобы параметры алгоритмов, настроенные по предыдущим зада-
чам, дали хорошие результаты для новых задачах.

Учет постоянной составляющей целевой функции. Во многих

алгоритмах оптимизации значение целевой функции используется не
только для качественного, но и для количественного управления алго-
ритмом. Например, в формулах для алгоритма роя частиц f(X) исполь-
зуется только качественно для определения лучшей позиции в про-
странстве поиска решений. А в формулах для алгоритма колонии му-
равьев от значения целевой функции пропорционально зависит коли-
чество феромона, наносимое на граф, а следовательно, и вероятности
выбора ребер графа. В генетическом алгоритме от значения целевой
функции агента зависит вероятность выбора этого агента для скрещи-
вания.
Очень часто при реализации стохастических алгоритмов не обра-
щают внимания на тот факт, что целевая функция может иметь неко-
торую постоянную составляющую fconst, значение которой намного
больше, чем диапазон изменяемой части fvar(X), т. е.
f ( X )  f const  f var ( X ), f const  max f var ( X )  min f var ( X ) .
X D X D

43
 В этом случае относительные различия между значениями фит-
несс-функций агентов малы, например, если постоянная составляющая
в 100 раз больше диапазона изменяемой части, то максимально воз-
можная разница между фитнессами агентов составит всего 1 %.
Из двух приведенных выше абзацев следует простой вывод: если
целевая функция количественно влияет на процесс работы алгоритма и
ее постоянная часть намного превышает изменяемую часть, то эффек-
тивность алгоритма может очень сильно упасть. Например, для гене-
тического алгоритма такая ситуация приведет к тому, что вероятность
отбора всех агентов на этапе селекции будет примерно одинаковой
независимо от качества их позиций в пространстве поиска решений. А
в алгоритме колонии муравьев количество феромона, наносимое на
ребра графа, будет также почти одинаковым независимо от эффектив-
ности найденного каждым агентом маршрута. Таким образом, алго-
ритмы лишаются одного из своих главных свойств – учета опыта, по-
лученного на предыдущих итерациях.
Для устранения этого негативного эффекта можно использовать
различные способы. В общем случае можно на первой итерации вы-
брать наименьшее найденное решение, принять его за примерную по-
стоянную величину (fappr) и затем вычитать его на всех итерациях из
полученных значений целевой функции. Либо после окончания работы
алгоритма сохранить наилучшее значение целевой функции, и при
следующем запуске вычитать это значение для определения фитнессов
агентов. Нужно учесть, что не все алгоритмы корректно работают с
отрицательными значениями целевой функции, которые могут появ-
ляться в данном подходе, если фитнесс какого-либо агента окажется
меньше величины fappr.

Прочие рекомендации. При оптимизации часто большая часть

вычислений связана с расчетом целевой функции f(X). Целевая
функция вычисляется для каждого агента популяционного алгорит-
ма на каждой итерации, т. е. если задано 100 агентов и 1000 итера-
ций, то целевая функция будет рассчитана 105 раз. Для задач ком-
мивояжера это может быть некритично, но вычисление целевой
функции может оказаться очень трудоемким процессом, например,
в задачах календарного планирования, где для вычисления ЦФ
необходимо составить сложное расписание, или в задачах, исполь-
зующих сложные модели объектов управления, таких как система
энергоснабжения или производственная линия. Поэтому нужно об-

44
ращать особое внимание на эффективную реализацию модели зада-
чи оптимизации.
Иногда в задачах оптимизации можно использовать целочисленные
вычисления там, где кажется необходимым применить вычисления с
плавающей точкой, особенно в комбинаторных задачах. Например,
если в задаче коммивояжера расстояния заданы нецелыми числами, но
точность расстояний составляет два знака после запятой, то можно,
умножив все расстояния на 100, перейти к целочисленным вычислени-
ям. Однако нужно учесть, что скорость вычислений с разными типами
данных зависит от множества факторов (язык программирования, ком-
пилятор, процессор).
Выбор языка программирования и вовсе является отдельной об-
ширной темой, можно только указать, что опыт убеждает в преимуще-
стве языка программирования C++ для реализации алгоритмов опти-
мизации [10, 15, 29].

3. ПРАКТИЧЕСКАЯ РАБОТА
ПО СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ

3.1. Описание
Практическая работа по стохастическим методам дискретной оп-
тимизации направлена на ознакомление студентов с наиболее распро-
страненными алгоритмами, которые часто применяются для решения
практических оптимизационных задач и могут в дальнейшем быть ис-
пользованы студентами в их научно-исследовательских работах. Дан-
ная работа не предполагает самостоятельную реализацию алгоритмов
оптимизации. Студентам предлагается использование готового про-
граммного продукта «Система визуализации стохастических алгорит-
мов оптимизации» (свидетельство о регистрации программы для ЭВМ
№ 2015613847, автор Матренин П.В., 2015 г.) для визуального анализа
работы алгоритмов и проведения экспериментов.
В ходе работы студенты изучают четыре стохастических алгоритма
дискретной оптимизации: генетический алгоритм, алгоритм имитации
отжига и два алгоритма роевого интеллекта (алгоритм роя пчел и алго-
ритм роя частиц).

45
 Приведенные далее указания содержат описание работы с про-
граммным обеспечением, пошаговую инструкцию проведения экспе-
риментов, самостоятельные задания и контрольные вопросы для защи-
ты. Перед выполнением работы необходимо изучить теоретическую
часть (см. в разделе «Описание алгоритмов»).
Объем работы в часах и уточненное задание на работу опреде-
ляются преподавателем, ориентировочно работа рассчитана на че-
тыре часа. За отведенное время студенты должны выполнить и за-
щитить работу. К работе студенты приступают после домашней
подготовки и предварительного изучения теории. После выполне-
ния работы студент предъявляет оформленный отчет с указанными
ниже результатами. Допустима работа в группах по 2–4 человека,
защита индивидуальная.

3.2. Описание программного обеспечения

визуализации
Для визуализации алгоритма имитации отжига, генетического
алгоритма и алгоритмов роя частиц и пчел в двумерном простран-
стве, ознакомления пользователей и демонстрации влияния пара-
метров алгоритма на процесс поиска решений были созданы четыре
соответствующих приложения. Приложения имеют типизированный
интерфейс, написаны на языке С++ в среде Qt и могут быть исполь-
зованы в операционных системах семейств Windows, Linux и
Mac OS. Для наглядности было решено использовать задачи вида

 z  f ( x, y ),
x  x x ,
 min max

 ymin  y  ymax ,
 z  max,

для которых процесс поиска можно представить как перемещение те-

кущих решений на плоскости XY.
Общее представление об интерфейсе приложений (рис. 3 для Win-
dows, рис. 4 для Linux) приведено для алгоритма роя частиц.

46
 Рис. 3. Интерфейс приложения визуализации Windows
Сверху расположена основная расчетная формула, ссылка на файл
справки и метка для вывода результата. Ниже находится поле для вво-
да задачи, справа от которого расположен элемент для выбора функ-
ций списка. Большую часть формы занимает поле для визуализации
процесса работы алгоритма, слева расположены элементы для ввода
параметров. Текущее лучшее решение обозначается на поле красным
крестиком.
Для запуска алгоритма необходимо выбрать задачу из раскрываю-
щегося списка сверху справа или ввести свою, нажать кнопку «Старт»
внизу слева, пауза позволяет поменять параметры алгоритма и про-
должить работу. Кнопка «Стоп» прерывает работу. Если в поле «Itera-
tions» ввести 0, то алгоритм будет работать до нажатия кнопки «Стоп»,
иначе алгоритм выполнит заданное число итераций, если его не пре-
рвать.

47
 Рис. 4. Интерфейс приложения визуализации Linux

Пользователь может вводить свои функции z(x,y) на языке Qt Script

(стандарт ECMAScript, он же JavaScript 2.0). Кроме арифметических
действий доступны указанные в табл. 1 математические функции и
константы (указывать перед ними имя объекта Math не нужно). Кроме
того, можно использовать условные операторы (if-else), циклы (for,
while).
Заданные пользователем задачи обрабатываются медленнее встро-
енных тестовых задач из-за необходимости интерпретации введенного
пользователем кода.

48
 Таблица 1
Константы и функции, доступные для использования в веденных задачах
Обозначение Описание
E Число e (константа Эйлера)
LN2 Натуральный логарифм числа 2
LN10 Натуральный логарифм числа 10
LOG2E Логарифм числа e по основанию 2
LOG10E Логарифм числа e по основанию 10
PI Число π
SQRT1_2 Квадратный корень из 1/2
SQRT2 Квадратный корень из числа 2
abs(a) Модуль числа
ceil(a) Округление в большую сторону
floor(a) Округление в меньшую сторону
round(a) Округление до ближайшего целого
max(a,b,c,…) Максимальный из переданных аргументов
min(a, b, c,…) Минимальный из переданных аргументов
pow(a, n) Возведение в указанную степень
sqrt(a) Квадратный корень
random() Генератор случайных чисел от 0 до 1
sin(a) Синус
cos(a) Косинус
tan(a) Тангенс
asin(a) Арксинус
acos(a) Арккосинус
atan(a) Арктангенс
log(a) Натуральный логарифм

Каждый шаг алгоритма запускается встроенным в программу тай-

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

49
 3.3. Практическое задание
3.3.1. Начало работы
Прочитайте описание четырех стохастических алгоритмов, приве-
денное выше и описание программного обеспечения для визуализации
этих алгоритмов. Если вы вначале прочитаете и поймете основные
теоретические положения, выполнение работы будет намного проще и
быстрее.
Запустите [Link], убедитесь, что вам понятно, как рабо-
тать с приложением. Проверьте на любых задачах, соответствует ли
показанный процесс работы алгоритма вашему представлению, сло-
жившемуся после прочтения его описания. Аналогично запустите
AnnealingDemo, BeesDemo, GeneticDemo и понаблюдайте за работой
алгоритмов. При наведении на элементы для ввода параметров появля-
ется всплывающая подсказка, если назначение каких-либо элементов
вам непонятно, обратитесь к преподавателю.
Для алгоритма роя частиц на любой из тестовых задач определите
и укажите в отчете, при каком порядке количества частиц (агентов) и
максимальной скорости отображения возникают задержки между ите-
рациями более 0.5 с.
Далее по каждому из алгоритмов описаны шаги, которые необхо-
димо выполнить для более подробной демонстрации принципов рабо-
ты алгоритмов. Для каждого из алгоритмов сделайте и вставьте в отчет
2–3 снимка экрана приложения, на которых будут отражены различ-
ные этапы работы. Чтобы понимать процесс работы алгоритмов, необ-
ходимо представлять себе структуры решаемых задач, для этого нужно
построить поверхность z(x, y) с помощью любого удобного вам сред-
ства (наиболее просто это сделать, скопировав формулу из строки ре-
дактирования в верхней части экрана и вставив ее в строку поиска
«Google», затем поставить нужные диапазоны по всем осям). Некото-
рые поверхности показаны на рис. 5–9, но статичные 2D изображения
не так наглядны, как интерактивные псевдо-3D.
Частично процесс работы алгоритма поясняется, однако для полно-
го понимания работы часть объяснений пропущена, чтобы вы могли
проконтролировать, насколько хорошо понимаете данные алгоритмы.
В описании заданий по каждому алгоритму есть выделенные указания
о том, что включить в отчет, и вопросы, ответы, на которые нужно ука-
зать в отчете (достаточно кратких ответов в одно предложение).

50
Рис. 5. Поверхность к задаче Розенброка

Рис. 6. Поверхность к задаче Sin(x, Sin(y))

51
 Рис. 7. Поверхность к задаче Ex_180.422

Рис. 8. Поверхность к задаче Химмельблау

52
 Рис. 9. Поверхность к задаче Sin(x, Y)

3.3.2. Демонстрация алгоритма роя частиц

Запустите SwarmDemo, выберите задачу Розенброка (см. рис. 5),
поставьте 500 частиц, коэффициенты w, a1, a2, Max Vx, Max Vy, рав-
ными 1.1, 0.1, 0.0, 0.01, 0.01 соответственно. Флаг «V(to) = 0» снимите.
Запустите алгоритм, частицы должны образовать дугу, после этого по-
ставьте на паузу. Так как коэффициент a2, отвечающий за взаимодей-
ствие между частицами, равен нулю, каждая частица действует незави-
симо, поэтому многие из них находятся не в оптимальной позиции.
Увеличьте коэффициент w до 1.3 и запустите алгоритм – дуга станет
шире. Затем верните коэффициенту w предыдущее значение, а коэф-
фициент a1 сделайте равным 0.3, и продолжите работу алгоритма.
Каждая частица после этого будет стремиться быть ближе к своему
локальному оптимуму. Последним шагом поставьте значение a2, рав-
ное 1. Теперь частицы используют обмен своим опытом и многие ча-
стицы быстро переместятся в окрестность глобального оптимума
функции, другие же образуют отдельно расположенную группу, из ко-
торой будут постепенно по одной-две переходить в окрестность гло-
бального оптимума. Объясните в отчете, почему не все частицы

53
сразу переместились к глобальному оптимальному решению? По-
сле этого прекратите работу алгоритма.
Выберите задачу «sin (x, sin(y))» (см. рис. 6). Число частиц нужно
сделать равным 5000. Поставьте коэффициенты равными 1.2, 0.3, 0, 1 и 1
и запустите алгоритм. Затем поставьте a2 равным 0.3 и посмотрите,
как изменится форма образованных частицами синусоид. Видно, что
несмотря на сближение частиц, форма синусоид в искаженном виде
сохранилась. Постепенно повышайте коэффициент a2 (с шагом 0.5) и
посмотрите, как рой будет все больше сжиматься.
Последняя демонстрационная задача для роя частиц называется
«Ex_180.422» (см. рис. 7). Запустите на ней алгоритм с коэффициента-
ми 1, 1, 1, 1 и 1, 50 агентами и 1000 итераций (флаг «V(to) = 0» устано-
вите). Сделайте 10 запусков и запишите в отчет полученные значе-
ния z. Они будут сильно отличаться друг от друга и от оптимального
значения 180.422. Можете повысить число итераций, но это не приве-
дет к существенному улучшению. В таких случаях говорят о прежде-
временной сходимости или «застревании» алгоритма поиска в локаль-
ном экстремуме. Рой нашел локальный экстремум, и при данных пара-
метрах вероятность выйти из него очень мала (но не равна 0). Для ре-
шения этой трудности есть два пути: увеличить число агентов в
надежде, что какой-либо из них успеет попасть в окрестность глобаль-
ного оптимума до застраивания алгоритма, либо регулировать пара-
метры алгоритма, чтобы он мог выходить из таких ситуаций.
Попробуйте поставить число агентов 1000. Теперь даже при числе
итераций меньше 500 алгоритм будет находить близкие к оптимально-
му решения, выпишите 10 результатов. Но такой подход не всегда
является применимым, поскольку при увеличении числа частиц воз-
растает вычислительная трудоемкость, особенно для сложных задач, в
которых вычисление целевой функции может требовать длительного
времени. Если для задачи размерности 2 потребовалась 1000 частиц, то
для задач размерности выше 100 количество частиц для подобного
охвата всего пространства решений окажется слишком велико.
Теперь поставьте всего 25 частиц и 1000 итераций, но увеличьте
максимальные скорости до 10, а коэффициент a2 сделайте равным 0.5.
Это позволит частицам, во-первых, с большей вероятностью «выска-
кивать» из локальных экстремумов благодаря возможности набрать
высокую скорость, а во-вторых, каждая частица имеет больше индиви-
дуальности и частицы менее стремятся собраться вместе (a1 в два раза
больше, чем a2). С такими коэффициентами будут получаться резуль-

54
таты, близкие к оптимальному (укажите в отчете 10 результатов),
намного ближе, чем в первом варианте и намного быстрее, чем во вто-
ром (при визуализации скорость расчетов не очень заметна, поскольку
этап рисования занимает значительное время, поэтому оцените и ука-
жите в отчете повышение скорости работы третьего варианта отно-
сительно второго исходя из предпосылки, что большую часть времени
работы алгоритма занимало бы вычисление целевой функции). Но это
не означает, что повышение скорости всегда повышает эффективность
алгоритма, потому что при слишком высокой скорости частицы могут
«проскакивать» мимо экстремумов.

3.3.3. Демонстрация алгоритма роя пчел

Запустите BeesDemo и откройте задачу Химмельблау (см. рис. 8) и
запустите алгоритм с параметрами по умолчанию. Вы не увидите ка-
кой-либо логики в перемещениях агентов. Дело в соотношении разме-
ров пространства поиска и параметров RadX и RadY. Когда пчела от-
правляется на участок, она может отклониться от него на случайную
величину, равномерно распределенную от –RadX до RadX по оси X, и
от –RadY до RadY по оси Y, в данном случае размер области, в которую
может попасть пчела, превышает размер области поиска, поэтому дви-
жение пчел носит характер, близкий к случайному поиску. Уменьшите
во время паузы RadX и RadY до 0.1 и продолжите работу алгоритма.
Вы увидите, что теперь можно наблюдать небольшие группы пчел.
Поставьте количество пчел, посылаемых на лучшие и выбранные
участки, равными 50 и 10 (CN и CM), в этом случае в группах будет
больше пчел, а размер групп позволит отличать лучшие участки от вы-
бранных. Если вы посмотрите на график функции Химмельблау, то
увидите, что функция имеет четыре экстремума, а групп пчел сейчас
больше четырех. Поставьте количество лучших участков 3, а выбран-
ных 1 (N и M) и запустите алгоритм. Вы увидите три больше группы и
одну небольшую (возможно, для этого придется снизить скорость).
Обратите внимание, что распределение групп по окрестностям экстре-
мумов не статично – в любом из экстремумов может быть то большая
группа, то небольшая. Объясните, почему так произошло, и почему
часть пчел продолжают хаотичные перемещения по всему про-
странству поиска.
Следующая задача – Розенброка (см. рис. 5). При тех же парамет-
рах, которые были в последнем этапе на предыдущей задаче, вновь

55
можно видеть четыре группы пчел, хотя график этой функции имеет
только один экстремум. Разделение по группам связано на этот раз с
коэффициентами dX и dY, влияющими на расстояние между центрами
участков. Измерьте примерное расстояние между центрами групп по
осям X и Y. Попробуйте подобрать величины dX и dY, чтобы между
группами пчел не было заметно промежутков, укажите эти величины
в отчете и напишите, можно ли было сразу определить их значе-
ния, не проводя экспериментов, исходя только из параметров алгорит-
ма и условий задачи.
Последнее задание для алгоритма роя пчел связано с задачей
«Sin(x, sin(y))» (см. рис. 6). Запустите алгоритм с параметрами по
умолчанию (для этого можно перезапустить BeesDemo). Вы не увидите
синусоид, как это было для алгоритма роя частиц. Попробуйте подо-
брать параметры алгоритма так, чтобы синусоиды были видны. Под-
сказка: потребуется менять и число агентов, но слишком много ставить
не обязательно (N*CN + M*CM <=1000). Вставьте снимок экрана и
значения параметров в отчет. Задача с синусоидами не имеет прямо-
го отношения к оптимизации, но и алгоритмы роевого интеллекта (рой
частиц и рой пчел) используются не только для решения задач оптими-
зации. Алгоритмы роевого интеллекта часто применяются для интел-
лектуального управления группами роботов, для визуализации в играх
и фильмах движений большого количества объектов и других задач,
требующих гибкого децентрализованного управления множеством
элементов. Задача «Sin (x, sin(y))» как раз демонстрирует, как возника-
ет коллективное поведение агентов роя и как можно влиять на него.

3.3.4. Демонстрация алгоритма имитации отжига

Запустите AnnealingDemo. Откройте задачу «Sin(x, y)» (см. рис. 9,
не «Sin(x, sin(y))»), запустите алгоритм на не самой высокой скорости с
500 агентами, параметрами M[x] и M[y], равными 2, To – 10000, Tf – 1,
vTo – 0.01. Понаблюдайте, как точки будут постепенно сходиться в
экстремумы. При начальных значениях температуры вероятность пе-
рехода агента в новое состояние, несмотря на его качество, очень вы-
сока, поэтому точки как будто хаотично перемещаются по простран-
ству решений, что напоминает колебания частиц в кристаллической
решетке при высоких температурах. При уменьшении температуры
точки будут оказываться все ближе к экстремумам, продолжая совер-
шать колебания, т. е. их движение не будет на каждом шаге направле-

56
но к экстремумам. При некотором уровне температуры на экране будут
четко видны все экстремумы функции, но заметные колебания точек
не прекратятся до конца работы алгоритма. Алгоритм не предполагает
использование нескольких агентов, в данном случае 100 агентов ис-
пользуется только для визуализации, они никак не взаимодействуют
между собой. Используя аналогию с процессом кристаллизации веще-
ства, на которой основан алгоритм имитации отжига, можно сделать
вывод, что в алгоритме должно быть задействовано много агентов, как
частиц в веществе, однако классический алгоритм имитации отжига и
большинство его модификаций не используют многоагентный (его еще
называют «популяционный») подход. А запуск алгоритма имитации
отжига с n агентами равен параллельной работе n независимых алго-
ритмов или последовательному запуску алгоритма n раз. Вы должны
понимать, что для трех других приведенных алгоритмов это категори-
чески не так, они относятся к популяционным алгоритмам, в которых
ключевой особенностью является взаимодействие агентов.
Количество итераций алгоритма имитации отжига можно задавать
явно, а можно через остановку алгоритма при опускании температуры
ниже некоторой отметки. Выведите и запишите в отчет зависимость
числа шагов алгоритма от начала до завершения от его параметров
(формула понижения температуры приведена в описании алгоритма
выше).
Откройте задачу Химмельблау (см. рис. 8) и запустите алгоритм с
параметрами, которые использовали до этого, и одним агентом. Запу-
стите алгоритм пять раз (скорость можно вернуть на максимальную) и
запишите результаты. При работе алгоритма не будет заметно суже-
ния области, в которой производится поиск, как это было для преды-
дущего примера, а результаты не очень близки к нулю. Поставьте ко-
нечную температуру в 100 раз ниже и повторите пять запусков, выпи-
сывая результаты. Время работы алгоритма увеличилось, но резуль-
таты остались не очень хорошими. Теперь верните значение конечной
температуры, равное 1, а коэффициенты M[x] и M[y] поставьте 0.1.
Снова выполните пять запусков и запишите результаты. Эффектив-
ность алгоритма значительно повысилась. Снижение коэффициентов,
влияющих на максимальное расстояние, на которое может переме-
ститься поиск из текущего состояния, позволило алгоритму больше
времени потратить на «исследование» окрестности экстремумам и
найти точки, которые ближе к нему. При высоких значениях этих ко-
эффициентов алгоритм перемещался в среднем на расстояние в 20 раз

57
больше, таким образом, поиск «рассеивался» слишком далеко вокруг
экстремума. Однако высокие значения коэффициентов M[x] и M[y]
могут быть полезны для других задач, в которых алгоритму сложнее
попасть в окрестность экстремума.
Поставьте значение параметра T0, равное 1000, Tf, равное 0.01 и от-
кройте задачу Розенброка (см. рис. 5). Запустите алгоритм 10 раз
и укажите полученные результаты в отчете. Теперь поставьте зна-
чения коэффициентов M[x] и M[y] 0.01 и снова запустите алгоритм
10 раз, выписывая результаты. Посмотрите на график задачи Розен-
брока и сопоставьте его с показанным процессом поиска решения, по-
сле этого напишите, какой из вариантов параметров и почему дал
более эффективные результаты по среднему значению, по лучшему
значению.

3.3.5. Демонстрация генетического алгоритма

Запустите GeneticDemo. Параметры с метками «Pm x» и «Pm y»
определяют вероятность мутации в хромосоме (мутации гена, пред-
ставляющего значение x, и гена, представляющего значение y). Пара-
метры с метками «Vm x» и «Vm y» задают максимально возможное
отклонение значения соответствующего гена при мутации, например,
значение 0.1 означает, что ген может измениться на величину от 0 до
10 % в большую или меньшую сторону с равной вероятностью (конеч-
но, с учетом того, что значение гена не может выйти из допустимого
диапазона). При значении 0 ген при мутации может принять любое
допустимое значение с равной вероятностью.
Откройте задачу Химмельблау (см. рис. 8) и запустите алгоритм на
невысокой скорости с 1000 агентов (хромосом), вероятностью мутации
1% (0.01), значения коэффициентов VmX и VmY оставьте равными ну-
лю. Вы должны увидеть четыре центра, вокруг которых собираются
особи, по одному в каждой четверти пространства поиска. Поставьте
алгоритм на паузу, уменьшите вероятности мутаций в 10 раз и про-
должите работу – через некоторое время точек в пространстве поиска
станет намного меньше, а если снова приостановить алгоритм и поста-
вить вероятности мутаций 20 %, точек снова станет много и при этом
уже не будут заметны четыре отдельные группы особей. Объясните,
что произошло при уменьшении и увеличении вероятностей мута-
ции в отчете.
Следующая демонстрационная задача – sin(x, sin(y)) (см. рис. 6).
Для алгоритмов роя частиц, пчел и отжига на этой задаче можно было

58
увидеть, как агенты образуют синусоиды. Поставьте 1000 особей и ве-
роятности мутации 5 % и посмотрите, образуют ли особи синусоиды
на этот раз? Укажите в отчете, почему.
Выберите задачу Розенброка (см. рис. 5), поставьте 100 особей,
1000 итераций, вероятности мутации 5 %. Выполните пять запусков
алгоритма и запишите в отчет полученные результаты. Затем по-
вторите пять запусков с параметрами VmX и VmY, равными 0.1 (т. е.
при мутации ген не может измениться более чем на 10 %), также ука-
зав результаты в отчете. Ограничение на степень мутации приведет к
быстрому сокращению разнообразия популяции и снижению средней
эффективности алгоритма (популяцией называют набор особей или
хромосом на текущей итерации алгоритма). Однако в других типах
задач ограничение на степень мутации может повысить эффектив-
ность. Убедитесь в этом на задаче «Abs», для этого выполните по пять
запусков с теми же параметрами, что в двух прошлых вариантах (100
особей, вероятности 5 %, Vm =0 в первом варианте и Vm = 0.1 во вто-
ром), а чтобы сделать это быстрее, число итераций сократите до 100,
ведь задача является очень простой. Укажите полученные результа-
ты двух вариантов в отчете. С большой вероятностью эффективность
второго варианта окажется выше, поскольку в этой задаче всего один
экстремум и ограничение на изменение генов приводит к концентра-
ции особей вокруг него, окрестность экстремума обрабатывается
большим количеством особей, это повышает вероятность попадания
особей во все более близкие к оптимуму позиции, в то время как от-
сутствие ограничений на мутацию постоянно переводило бы часть
особей в произвольные точки пространства поиска. Трудность заклю-
чается в том, что, как правило, заранее структура пространства реше-
ний неизвестна либо нет времени на исследование условий задачи, по-
этому нельзя сказать, какие параметры алгоритма будут эффективнее.
Для разрешения этого затруднения используются различные способы
автоматической адаптации стохастических алгоритмов под условия
задач.

3.3.6. Индивидуальные задания

Заключительная часть работы предполагает проведение самостоя-
тельных экспериментов с указанными для каждого варианта задачами
и алгоритмами (табл. 2).
В каждом варианте необходимо провести некоторое число простых
экспериментов, т. е. запусков алгоритма на указанной задаче, меняя

59
параметры. Число агентов и число итераций нужно выбрать самостоя-
тельно, но произведение числа агентов на число итераций должно быть
равно 50 000. Нужно выбрать число агентов и итераций, зафиксировать
и провести 10 экспериментов с разными значениями параметров, ста-
раясь добиться как можно лучших значений целевой функции. Каждый
эксперимент состоит в запуске алгоритма три раза c фиксированными
параметрами и определении лучшего по трем запускам. Затем нужно
поменять число агентов хотя бы в четыре раза в большую или мень-
шую сторону, определить число итераций, чтобы произведение оста-
лось равным 50 000, и провести еще 10 аналогичных экспериментов
(по три запуска) с теми же параметрами, что использовались в 10
предыдущих экспериментах.
! Скорость проведения экспериментов можно в разы повысить, ес-
ли отключить визуализацию работы алгоритмов (снять галочку
“Visualization”).
Результаты (количество агентов, итераций, параметры, значение
целевой функции) нужно занести в таблицу. Для алгоритма имитации
отжига можно сэкономить время, если не по три раза запускать алго-
ритм с одним агентом и выбирать лучший, а поставить трех агентов и
запустить один раз. Объяснения полученных экспериментальных ре-
зультатов в отчет вносить не требуется, но для защиты работы нужно
подготовить выводы из экспериментов.
Таблица 2
Варианты заданий
Вариант Задача Алгоритм Число агентов
1 Гринвока Роя частиц Agents
2 Гринвока Роя пчел N*CN + M*CM + S
3 Гринвока Имитации отжига 1 (один)
4 Гринвока Генетический Agents
5 Растригина Роя частиц Agents
6 Растригина Роя пчел N*CN + M*CM + S
7 Растригина Имитации отжига 1 (один)
8 Растригина Генетический Agents
9 Ex_180.422 Роя частиц Agents
10 Ex_180.422 Роя пчел N*CN + M*CM + S
11 Ex_180.422 Имитации отжига 1 (один)
12 Ex_180.422 Генетический Agents

60
 Контрольные вопросы
1. Объясните, какие алгоритмы оптимизации относятся к стохасти-
ческим, почему они так называются?
2. В чем особенности стохастических алгоритмов, их преимуще-
ства и недостатки?
3. Какие классы стохастических алгоритмов можно выделить?
4. Почему даже для задач оптимизации, которые можно решить
точными методами, часто применяют стохастические алгоритмы?
5. В чем преимущества и недостатки жадных эвристик?
6. Приведите примеры практических задач, в которых имеет смысл
применять стохастические методы оптимизации.
7. Кратко опишите, как работает метод случайного поиска и поиска
с возвратом?
8. Кратко опишите работу алгоритма имитации отжига.
9. Кратко опишите работу генетического алгоритма.
10. Кратко опишите работу алгоритма роя частиц.
11. Кратко опишите работу алгоритма роя пчел.
12. Кратко опишите работу алгоритма поиска косяком рыб.
13. Кратно опишите работу алгоритма колонии муравьев.
14. Как алгоритмы роевого интеллекта используют случайный
поиск?
15. Как генетический алгоритм используем случайный поиск?
16. Как алгоритм имитации отжига использует случайный поиск?
17. Как вы думаете, является ли усложнение правил работы агентов
популяционных алгоритмов хорошим способом повышения их эффек-
тивности?
18. Какие алгоритмы оптимизации относятся к популяционным, в
чем их основное отличие?
19. Почему генетический алгоритм не относится к алгоритмам рое-
вого интеллекта, как это проявляется при визуальном наблюдении за
его работой?
20. В чем преимущества и недостатки алгоритма имитации отжига,
использующего одного агента по сравнению с многоагентными алго-
ритмами?
21. С какой целью авторы алгоритма роя пчел ввели в него агентов-
разведчиков? Есть ли недостатки у такого приема?
22. Каким образом инерция влияет на поведение алгоритма роя ча-
стиц, как вы думаете, зачем введено это свойство?

61
 23. Почему при нулевой начальной скорости и нулевом коэффици-
енте a1 рой частиц остается неподвижен?
24. Как бы изменилась эффективность алгоритма имитации отжи-
га, если бы температура была постоянной?
25. Как вы думаете, при каком условии равняется единице вероят-
ность обнаружения глобального экстремума произвольной задачи оп-
тимизации с помощью любого из перечисленных алгоритмов?
26. Как изменится работа алгоритма имитации отжига при исполь-
зовании линейного графика понижения температуры вместо экспонен-
циального?
27. В чем роль скрещивания в генетическом алгоритме?
28. Стоит ли всегда оставлять в популяции генетического алгорит-
ма особь (хромосому) с наилучшей приспособленностью?
29. Как вы думаете, какой из рассмотренных в работе алгоритмов
эффективнее для решения задач оптимизации с динамически меняю-
щимися во времени условиями? Какой наименее эффективен?
30. Что означают слова «преждевременная сходимость»?
31. Оцените рассмотренные алгоритмы с точки зрения простоты и
эффективности распараллеливания.
32. Каким образом можно использовать генетический алгоритм
для решения комбинаторных задач оптимизации? Запишите структуру
хромосомы для задачи коммивояжера.
33. Каким образом можно использовать алгоритм имитации отжига
для комбинаторных задач? Запишите структуру состояния системы для
задачи коммивояжера.
34. Каким образом можно использовать алгоритм роя частиц для
комбинаторных задач? Запишите вид позиции частицы для этой задачи
коммивояжера.
35. Каким образом можно использовать алгоритм роя пчел для
комбинаторных задач? Запишите вид позиции пчелы для задачи ком-
мивояжера.
36. Укажите важные моменты, которые нужно учитывать при реа-
лизации стохастических алгоритмов оптимизации.
37. Каким образом можно реализовать стохастические алгоритмы
оптимизации, чтобы обеспечить гибкость и переносимость их про-
граммного кода?
38. Сравните два любых описанных в пособии алгоритма с точки
зрения эффективности и простоты их распараллеливания.

62
 39. Какие существуют способы повышения скорости работы сто-
хастических алгоритмов?
40. Объясните понятие «машинное обучение».
41. Напишите формальную постановку задачи машинного обуче-
ния.
42. Какие виды задач машинного обучения вы знаете?
43. Покажите связь между задачей машинного обучения и задачей
оптимизации.
44. Как можно использовать стохастические методы оптимизации
для обучения линейного классификатора?

63
 БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Алгоритмы: построение и анализ: пер. с англ. / Т. Кормен [и др.]. –
2-е изд. – М. : Издательский дом «Вильяме», 2005. – 1296 с. : ил.
2. Воронцов К.В. Машинное обучение: курс лекций [Электронный ресурс]
// [Link]
3. Гладков Л.А. Генетические алгоритмы/ Л.А. Гладков, В.В. Курейчик,
В.М. Курейчик; под ред. В.М. Курейчика. – 2-е изд., испр. и доп. – М.: ФИЗ-
МАТЛИТ, 2006. – 320 с.
4. Гриф М.Г. Гибридная экспертная система проектирования человеко-
машинных систем и принятия решений ИНТЕЛЛЕКТ-3: учеб. пособие. – Но-
восибирск: Изд-во НГТУ, 2007. – 162 с.
5. Гэри М. Вычислительные машины и труднорешаемые задачи: пер. с
англ. / М Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
6. Карпенко А.П. Популяционные алгоритмы глобальной оптимизации.
Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Инфор-
мационные технологии». – 2012. – № 7. – С. 1–32.
7. Карпов В.Э. Методологические проблемы эволюционных вычислений //
Искусственный интеллект и принятие решений. – № 4. – 2012. – C. 95–102.
8. Кочетов Ю.А. Вероятностные методы локального поиска для задач
дискретной оптимизации. Дискретная математика и ее приложения: сб. лек-
ций молодежных и научных школ по дискретной математике и ее приложени-
ям. – М.: Изд-во центра прикладных исследований при механико-математи-
ческом факультете МГУ, 2000. – С. 87–117.
9. Курейчик В.М. Использование роевого интеллекта в решении NP-труд-
ных задач/ В.М. Курейчик, А.А. Кажаров // Известия ЮФУ. Технические
науки. – 2011. – № 7 (120). – С. 30–37.
10. Матренин П.В., Секаев В.Г. Оптимизация адаптивного алгоритма му-
равьиной колонии на примере задачи календарного планирования // Про-
граммная инженерия. – 2013. – № 4. – С. 34–40.
11. Матренин П.В. Секаев В.Г. Системное описание алгоритмов роевого
интеллекта // Программная инженерия. – 2013. – № 12. – С. 39–45.
12. Матренин П.В. Описание и реализация алгоритмов роевого интеллек-
та с использованием системного подхода // Программная инженерия. – 2015. –
№ 3. – С. 27–34.
13. Матренин П.В. Разработка приложений для визуализации методов
стохастической оптимизации // Сборник научных трудов SWorld. Материалы
международной научно-практической конференции «Современные проблемы
и пути их решения в науке, транспорте, производстве и образовании'2012». –
Вып. 4. Том 12. – Одесса: КУПРИЕНКО, 2012. ЦИТ:412-0099. – С. 28–35.
14. Панченко Т.В. Генетические алгоритмы: учеб.-метод. пособие /
Т.В. Панченко; под ред. Ю.Ю. Тарасевича. – Астрахань: Издательский дом
«Астраханский университет», 2007. – 87 с.

64
 15. Скиена С. Алгоритмы. Руководство по разработке: пер. с англ. / Сти-
вен Скиена. – 2-е изд. – СПб.: БХВ-Петербург, 2013. – 720 с.: ил.
16. Штовба С.Д. Муравьиные алгоритмы/ С.Д. Штовба // Exponenta Pro.
Математика в приложениях. – 2003. – № 4. – С. 70–75.
17. Andrew Ng. Artificial intelligence | machine learning [Электронный ре-
сурс] // Stanford engineering everywhere. URL: [Link]
see/[Link]?coll=348ca38a-3a6d-4052-937dcb017338d7b1.
18. Beni G. From Swarm Intelligence to Swarm Robotics, Swarm Robotics.
Lecture Notes in Computer Science, 2005, vol. 3342, pp. 1-9.
19. Bertsimas D. Simulated Annealing / D. Bertsimas, J. Tsitsiklis // Statistical
Science, Vol.8, No 1, 1993. P. 10-15.
20. Dorigo M. The Ant System: Optimization by a colony of cooperating
agents. IEEE Transactions on Systems, Man, and Cybernetics – Part B. 1996. V. 26.
No. 1. P 29-41.
21. Dorigo M., Birattari M., Stutzle T. Ant Colony Optimization. Artificial
Ants as a Computational Intelligence Technique // IRIDIA. Technical Report Se-
ries. Technical Report No. TR/IRIDIA/2006-023. Brussels, Belgium. 2006. 14 p.
22. Glover F. Future Paths for Integer Programming and Links to Artificial In-
telligence / F. Glover // Computers and Operations Research. 13 (5), 1986.
P. 533–549.
23. Glover F. Tabu search / F. Glover, M. Laguna // Vol. 22. Boston: Kluwer
academic publishers, 1997.
24. Holland J.H. Adaptation in natural and artificial systems / J.H. Holland //
University of Michigan Press, Ann Arbor, 1975.
25. Karaboga D. An idea based on honey bee swarm for numerical optimiza-
tion [Электронный ресурс] // Technical report TR06. Erciyes University, Engi-
neering Faculty, Computer Engineering Department. 2005. URL:
[Link] abc/pub/tr06_2005.pdf.
26. Kennedy J. Particle Swarm Optimization / J. Kennedy, R. C. Eberhart //
Proc. of IEEE International Conference on Neural Network, Piscataway, NJ. 1995
P. 1942–1948.
27. Kirkpatrick S. (1983). Optimization by Simulated Annealing / S. Kirkpat-
rick, Jr. Gelatt, M.P. Vecchi // Science 220 (4598): 671–680.
28. Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees
Algorithm – A Novel Tool for Complex Optimisation Problems [Электронный
ресурс] //Technical Note. Manufacturing Engineering Centre. Cardiff University.
UK. 2005. URL: [Link]
Pham06%20-%20The%20Bee%[Link].
29. Pedersen M. Simplifying Particle Swarm Optimization / M. Pedersen,
A. Chipperfield // School of Engineering Sciences, University of Southampton, UK.
Applied Soft Computing, 2009. P. 618–628.

65
 30. Poli R. An Analysis of Publications on Particle Swarm Optimisation Appli-
cations. Department of Computer Science [Электронный ресурс] / R. Poli // Uni-
versity of Essex. Technical Report CSM-469. May 2007.
31. Sahin E. Swarm robotics: From sources of inspiration to domains of appli-
cation, Swarm Robotics. Lecture Notes in Computer Science, 2005, vol. 3342,
pp. 10–20.
32. Shi Y. A Modified Particle Swarm Optimizer / Y. Shi, R. Eberhart // De-
partment of Electrical Engineering Indiana University Purdue University Indianapo-
lis. Indianapolis, IN 46202-5160.
33. Wolpert D.H. No Free Lunch Theorems for Optimization / D.H. Wolpert,
W.G. Macready // IEEE Transactions on Evolutionary Computation 1, 1997.
P. 67–82.

66
 Матренин Павел Викторович
Гриф Михаил Геннадьевич
Секаев Виктор Гилячевич

МЕТОДЫ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ

Учебное пособие

Редактор Л.Н. Ветчакова

Выпускающий редактор И.П. Брованова
Дизайн обложки А.В. Ладыжская
Компьютерная верстка С.И. Ткачева
Налоговая льгота – Общероссийский классификатор продукции
Издание соответствует коду 95 3000 ОК 005-93 (ОКП)

Подписано в печать 14.03.2016. Формат 60  84 1/16. Бумага офсетная. Тираж 100 экз.
Уч.-изд. л. 3,95. Печ. л. 4,25. Изд. № 345/15. Заказ № 401. Цена договорная

Отпечатано в типографии
Новосибирского государственного технического университета
630073, г. Новосибирск, пр. К. Маркса, 20

67

View publication stats