Машинное обучение: метаэвристики дифференциально-векторного движения

 
 
 
 
 
 
 
 
 
 
 
 
 
 
С. И. Родзин  
О. Н. Родзина 
 
МАШИННОЕ ОБУЧЕНИЕ: МЕТАЭВРИСТИКИ 
ДИФФЕРЕНЦИАЛЬНО-ВЕКТОРНОГО ДВИЖЕНИЯ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Чебоксары  
Издательский дом «Среда» 
2024 

 
УДК 004(075.8) 
ББК 32.813я73 
        Р60 
Авторы: 
С.И. Родзин – канд. техн. наук, доцент, профессор ФГАОУ ВО 
«Южный федеральный университет» (ЮФУ), г. Таганрог; 
О.Н. Родзина – старший преподаватель ФГАОУ ВО «Южный 
федеральный университет» (ЮФУ), г. Таганрог 
 
Рецензенты: 
д-р техн. наук, профессор, заместитель директора Ростовского  
филиала научно-исследовательского и проектно-конструкторского 
Института информатизации, автоматизации и связи  
на железнодорожном транспорте 
С.М. Ковалев; 
д-р технических наук, профессор, заместитель директора по науке 
Санкт-Петербургского филиала ФГБУН «Институт земного  
магнетизма, ионосферы и распространения радиоволн 
им. Н. В. Пушкова РАН 
А.Г. Коробейников 
 
Р60 
Родзин С.И. 
  
Машинное обучение: метаэвристики дифференциальновекторного движения: учебное пособие / С.И. Родзин, 
О.Н. Родзина. – Чебоксары: Среда, 2024. – 140 с. 
 
ISBN 978-5-907830-17-2 
Метаэвристические алгоритмы, инспирированные природой, являясь одним из 
направлений в искусственном интеллекте и машинном обучении, в последние 
десятилетия стали мощным инструментом оптимизации, широко используются при 
распознавании образов и компьютерном зрении, технической и медицинской 
диагностике, прогнозировании, биоинформатике, фильтрации спама, анализе фондового 
рынка, в поисковых системах, в аффективных вычислениях, компьютерных играх. В 
учебном пособии рассматривается современное состояние, проблемы и области 
применения метаэвристик. Представлены алгоритмы дифференциально-векторного 
движения: дифференциальной эволюции, синуса-косинуса, эгоистичного стада 
животных, летучих мышей, империалистической конкуренции, роя саранчи, 
гравитационного поиска, светлячковый, бабочки монарха, червей, COVID-19, 
бактериальный, межнейронного взаимодействия, оптимизации группового обучения.  
Пособие адресовано бакалаврам и магистрам направлений «Информатика и 
вычислительная техника», «Информационные системы и технологии», «Программная 
инженерия», «Прикладная информатика», а также аспирантам специальности 
«Искусственный интеллект и машинное обучение». 
 
ISBN 978-5-907830-17-2 
                            © Родзин С.И., Родзина О.Н., 2024 
DOI 10.31483/a-10610 
                                  © ИД «Среда», оформление, 2024 
 

 
ОГЛАВЛЕНИЕ 
Предисловие 
............................................................................................. 5 
ВВЕДЕНИЕ ................................................................................................... 7 
1. СОВРЕМЕННОЕ СОСТОЯНИЕ  И ПРОБЛЕМЫ 
МЕТАЭВРИСТИК ..................................................................................... 14 
1.1. Терминология и классификация метаэвристик .......................... 14 
1.2. Тестирование метаэвристик .......................................................... 26 
1.3. Области применения метаэвристик ............................................. 32 
1.4. Резюме 
.............................................................................................. 38 
2. МЕТАЭВРИСТИКИ ДИФФЕРЕНЦИАЛЬНО- ВЕКТОРНОГО 
ДВИЖЕНИЯ, ИСПОЛЬЗУЮЩИЕ  РЕПРЕЗЕНТАТИВНЫХ 
АГЕНТОВ ПОПУЛЯЦИИ 
........................................................................ 43 
2.1. Алгоритм дифференциальной эволюции .................................... 43 
2.2. Синус-косинусный алгоритм ........................................................ 45 
2.3. Алгоритм эгоистичного стада 
....................................................... 54 
2.4. Алгоритм летучих мышей 
............................................................. 64 
2.5. Алгоритм империалистической конкуренции 
............................ 71 
2.6. Резюме 
.............................................................................................. 73 
3. МЕТАЭВРИСТИКИ ДИФФЕРЕНЦИАЛЬНО- ВЕКТОРНОГО 
ДВИЖЕНИЯ, ИСПОЛЬЗУЮЩИЕ  ВСЮ ПОПУЛЯЦИЮ 
АГЕНТОВ .................................................................................................... 78 
3.1. Алгоритм роя саранчи.................................................................... 78 
3.2. Алгоритм колонии пауков 
............................................................. 84 
3.3. Гибридный алгоритм модифицированных алгоритмов  роя 
саранчи и колонии пауков .................................................................... 87 
3.4. Алгоритм гравитационного поиска 
.............................................. 90 
3.5. Светлячковый алгоритм ................................................................ 92 
3.6. Резюме 
.............................................................................................. 94 
4. МЕТАЭВРИСТИКИ ДИФФЕРЕНЦИАЛЬНО- ВЕКТОРНОГО 
ДВИЖЕНИЯ, ИСПОЛЬЗУЮЩИЕ  СУБПОПУЛЯЦИЮ АГЕНТОВ
 
........................................................................................................................ 97 
4.1. Алгоритм бабочки-монарха .......................................................... 97 
4.2. Алгоритм червей 
........................................................................... 101 
4.3. Алгоритм Ковид-19 ...................................................................... 103 
4.4. Резюме 
............................................................................................ 109 
3 

Машинное обучение: метаэвристики дифференциально-векторного движения 
 
5. МЕТАЭВРИСТИКИ ДИФФЕРЕНЦИАЛЬНО- ВЕКТОРНОГО 
ДВИЖЕНИЯ, ИСПОЛЬЗУЮЩИЕ  АГЕНТОВ ИЗ НЕКОТОРОЙ 
ОКРЕСТНОСТИ 
....................................................................................... 112 
5.1. Бактериальный алгоритм ............................................................. 
112 
5.2. Алгоритм межнейронного взаимодействия .............................. 
114 
5.3 Алгоритм оптимизации группового обучения 
........................... 
119 
5.4. Резюме ............................................................................................ 
127 
Заключение ................................................................................................ 130 
СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ 
................................ 132 
Список литературы .................................................................................. 134 
 
 
 
4 

Родзин С. И., Родзина О. Н. 
 
Предисловие 
В основу учебного пособия положены материалы лекционных и 
практических занятий в рамках односеместровых курсов, которые Сергей Родзин в течение нескольких лет читает в Южном федеральном 
университете в Институте компьютерных технологий и информационной безопасности (https://ictis.sfedu.ru/) на кафедре математического 
обеспечения и применения ЭВМ (https://vk.com/sed_announce). Курсы 
под названием «Искусственный интеллект и анализ данных» и «Разработка приложений для систем искусственного интеллекта» задумывались для аспирантов и магистрантов, но оказались полезными 
также для бакалавров программ «Технологии искусственного интеллекта», «Методы и средства разработки программного обеспечения». В учебное пособие вошли также материалы некоторых научных статей авторов, используемых в проектной и исследовательской 
деятельности студентов. 
О чем учебное пособие? В самых общих словах это учебное пособие о метаэвристических алгоритмах, инспирированных природой, как об одном из направлений в искусственном интеллекте и 
машинном обучении. Но акцент сделан на эффективных алгоритмах из класса дифференциально-векторного движения, использующих в процессе обучения для генерации новых решений как всю 
популяцию, так и репрезентативных агентов, субпопуляцию или 
агентов из некоторой окрестности. Авторы сознательно стремились уделять больше внимания содержательным аспектам алгоритмов, их особенностям и сравнительным оценкам. Кроме того, в 
книге принят подход, согласно которому многие практические задачи иллюстрируют и поясняют метаэвристические алгоритмы. 
Ниже перечислены основные рассматриваемые темы. 
1. Современное состояние и проблемы метаэвристик, включая 
терминологию и классификацию, тестирование и области применения метаэвристик. 
2. Метаэвристики дифференциально-векторного движения, использующие в процессе обучения и генерации новых решений репрезентативных агентов популяции, включая алгоритм дифференциальной эволюции, синус-косинусный алгоритм, алгоритм эгоистичного стада, алгоритм летучих мышей и алгоритм империалистической конкуренции. 
5 

Машинное обучение: метаэвристики дифференциально-векторного движения 
 
3. Метаэвристики дифференциально-векторного движения, использующие в процессе обучения и генерации новых решений всю 
популяцию агентов, включая алгоритм роя саранчи, алгоритм колонии пауков, гибридный алгоритм роя саранчи и колонии пауков, 
алгоритм гравитационного поиска и светлячковый алгоритм. 
4. Метаэвристики дифференциально-векторного движения, использующие в процессе обучения и генерации новых решений субпопуляцию агентов, включая алгоритм бабочки монарха, алгоритм 
червей и алгоритм Ковид-19. 
5. Метаэвристики дифференциально-векторного движения, использующие в процессе обучения и генерации новых решений 
агентов из некоторой окрестности, включая бактериальный алгоритм, алгоритм межнейронного взаимодействия и алгоритм оптимизации группового обучения. 
Требования к читателю. 
Для полного понимания изложенного в учебном пособии материала мы рекомендуем следующее. 
1. Прослушать курс по дискретной математике, теории вероятностей и математической статистике. 
2. Иметь знания об информатике, структурах данных и алгоритмах в университетском объеме. 
3. Иметь знания о программных системах, программной инженерии и языках программирования. 
Благодарности. 
Слова глубокого уважения и признательности авторы адресуют профессору ЮФУ В.М. Курейчику, которого считают своим наставником 
и другом, чья научная эрудиция и широта интересов всегда служили 
образцом для подражания. 
Авторы выражают искреннюю благодарность рецензентам пособия – доктору технических наук, профессору С.М. Ковалеву, доктору технических наук, профессору А.Г. Коробейникову, а также 
своему коллеге по работе в Институте компьютерных технологий и 
информационной безопасности, доктору технических наук, профессору В.В. Курейчику, которые взяли на себя нелегкий труд ознакомиться с рукописью и высказали немало ценных советов и конструктивных замечаний, способствовавших устранению неточностей и 
улучшению содержания пособия. 
 
 
6 

Родзин С. И., Родзина О. Н. 
 
ВВЕДЕНИЕ 
Машинное обучение – это направление в искусственном интеллекте, которое исследует алгоритмы, способные обучаться и самостоятельно улучшаться по мере накопления опыта, извлекать закономерности из данных и делать прогнозы на их основе. Машинное 
обучение также тесно связано с математической статистикой и оптимизацией, с интеллектуальным анализом данных и распознаванием образов. Технологии и методы машинного обучения широко 
используются при распознавании образов и компьютерном зрении, 
технической и медицинской диагностике, прогнозировании, биоинформатике, фильтрации спама, обнаружении мошенничества, категоризации документов, кредитном скоринге и анализе фондового 
рынка, хемоинформатике, в поисковых системах, в аффективных 
вычислениях (сбор данных из выражений лица, голосовых сообщений и языка тела для измерения уровня человеческих эмоций), Интернет-рекламе, компьютерных играх. Причем сфера применений 
алгоритмов машинного обучения постоянно расширяется. Цифровизация приводит к накоплению огромных объёмов данных в науке, 
производстве, бизнесе, транспорте, здравоохранении. Возникающие 
при этом задачи анализа данных, прогнозирования, управления и поиска оптимальных решений часто сводятся к обучению по прецедентам. Раньше, когда таких данных не было, эти задачи либо вообще 
не ставились, либо решались совершенно другими методами. 
В зависимости от характера обучающего «сигнала» или «обратной 
связи» задачи машинного обучения обычно подразделяются на обучение с учителем, обучение без учителя и обучение с подкреплением. 
При обучении с учителем компьютеру предъявляются примеры 
входных данных и их желаемые выходные данные (обучающая выборка), заданные «учителем», и цель состоит в том, чтобы найти общее правило, которое сопоставляет входные данные с выходными. 
При обучении без учителя алгоритму обучения не присваиваются метки, он должен самостоятельно найти структуру во входных данных или обнаружить скрытые закономерности в данных. 
При обучении с подкреплением компьютерная программа взаимодействует со средой, в которой она должна выполнять определенную 
задачу, без явного указания учителя о том, приблизилась она к своей 
цели или нет. Откликом среды на принятые решения являются сигналы 
7 

Машинное обучение: метаэвристики дифференциально-векторного движения 
 
подкрепления, поэтому такое обучение является частным случаем обучения с учителем, но учителем является среда или ее модель. 
Другая классификация задач машинного обучения возникает в 
зависимости от выходных данных в результате машинного обучения. 
В частности, если при классификации входные данные разделяются 
на два или более классов, то необходимо построить модель, которая 
относит входные данные к одному или нескольким классам. Например, фильтрация спама является примером классификации, где входными данными являются сообщения электронной почты (или другие), 
а классами являются «спам» и «не спам». При решении регрессионной задачи выходные данные должны быть непрерывными, а не дискретными. При решении задачи кластеризации набор входных данных должен быть разделен на заранее неизвестное число групп. 
Основная цель алгоритмов машинного обучения – обобщение 
своего опыта. Обобщение опыта – это способность обучающей машины правильно решать новые задачи после изучения набора обучающих данных. Поскольку набор обучающих данных является конечным, то для оценки эффективности алгоритмов машинного обучения обычно используется дисперсия в качестве способа количественной оценки ошибки обобщения. В дополнение к этому также 
используется временная оценка сложности алгоритмов машинного 
обучения (в теории машинного обучения алгоритм считается выполнимым, если он может быть выполнен за полиномиальное время). 
Перечень современных алгоритмов машинного обучения включает: 
• деревья принятия решений, структура которых включает 
«листья» и «ветки». На ветках дерева решения записываются признаки, от которых зависит целевая функция, в листьях записываются значения целевой функции, а в остальных узлах – признаки, 
по которым различаются примеры. Чтобы классифицировать новый пример, надо спуститься по дереву до листа и выдать соответствующее значение. Метод деревьев принятия решений отличается 
простотой, не требует специальной подготовки данных, работает с 
категориальными и с интервальными переменными, получаемые 
результаты можно объяснить при помощи булевой логики (в отличие от нейронных сетей) и оценить при помощи статистических тестов, позволяет работать с большим объёмом информации. Однако 
следует иметь в виду, что проблема получения оптимального дерева решений является NP-полной задачей, при построении дерева 
8 

Родзин С. И., Родзина О. Н. 
 
решений могут создаваться слишком сложные конструкции, которые недостаточно полно представляют данные; 
• поиск ассоциативных правил для обнаружения интересующих 
нас связей между переменными в большой базе данных. Алгоритм генерирует также новые правила по мере анализа данных и создает возможность нахождения ассоциаций из новых неклассифицированных 
данных. Широко применяется при анализе рыночной корзины, в областях Web mining, а также для обнаружения вторжений, и биоинформатике. Одним из ограничений стандартного подхода к обнаружению 
ассоциаций является то, что при поиске в большом числе возможных 
ассоциаций множества объектов есть определенный риск нахождения 
случайных ассоциаций. Предложено много алгоритмов для генерации 
ассоциативных правил (Apriori, Eclat, FP-Growth), но они делают 
только половину работы, поскольку предназначены для отыскания часто встречающихся наборов объектов; 
• обучение искусственной нейронной сети (ИНС). Некоторые 
ИНС обучаются без учителя (например, сети Хопфилда), они просматривают выборку только один раз. Другие (например, сети Кохонена), а также сети, обучающиеся с учителем, просматривают выборку множество раз (эпохи обучения). При обучении с учителем 
набор исходных данных делят на две части – собственно обучающую выборку и тестовые данные; принцип разделения может быть 
произвольным. Обучающие данные подаются сети для обучения, а 
проверочные используются для расчета ошибки сети (проверочные 
данные никогда для обучения сети не применяются). Таким образом, 
если на проверочных данных ошибка уменьшается, то сеть действительно выполняет обобщение. Если ошибка на обучающих данных 
продолжает уменьшаться, а ошибка на тестовых данных увеличивается, значит, сеть перестала выполнять обобщение и просто «запоминает» обучающие данные. Это явление называется переобучением сети (оверфиттинг). В таких случаях обучение обычно прекращают. В процессе обучения могут проявиться другие проблемы, такие как паралич или попадание сети в локальный минимум поверхности ошибок. Невозможно заранее предсказать проявление той или 
иной проблемы, равно как и дать однозначные рекомендации к их 
разрешению. Это относится только к итерационным алгоритмам поиска нейросетевых решений. Для них действительно нельзя ничего 
гарантировать и нельзя полностью автоматизировать обучение 
9 

Машинное обучение: метаэвристики дифференциально-векторного движения 
 
нейронных сетей. Наряду с итерационными алгоритмами обучения, 
существуют алгоритмы, обладающие очень высокой устойчивостью 
и позволяющие полностью автоматизировать процесс обучения. В 
целом современные нейронные сети – это инструменты нелинейного 
статистического моделирования данных. Они используются для моделирования сложных взаимосвязей между входными и выходными 
данными, для поиска закономерностей в данных и других задач. 
Примерами использования нейросетей также являются нейроуправление, предсказание финансовых временных рядов, психодиагностика, хемоинформатика, экономика, роботы, беспилотные автомобили и дроны, распознавание образов и анализ текста, рекомендательные системы и нейрокомпьютеры; 
• индуктивное логическое программирование (ИЛП) использует логику для представления примеров, фоновых знаний и гипотез. Алгоритм системы ИЛП состоит из двух частей: поиска гипотезы и выбора гипотезы. Получив описания уже известных фоновых знаний и множества примеров, представленных как логическая 
база фактов, ИЛП может породить логическую программу в форме 
гипотез, объясняющую все положительные примеры и ни одного 
отрицательного. Базовые знания излагаются в виде логики, обычно 
в форме предложений Хорна. Возникают вопросы о высокой вычислительной сложности (NP-полная задача), о полноте процедуры 
поиска гипотез в конкретной системе ИЛП. Индуктивно-логическое программирование особенно полезно в биоинформатике, обработке естественного языка, медицине и фармакологии. Обычно 
реализации ИЛП делаются на языке Prolog; 
• машины опорных векторов (SVM) представляют собой набор 
связанных алгоритмов обучения с учителем, используемых для задач классификации и регрессии. Принадлежит семейству линейных классификаторов. Основная идея SVM – перевод исходных 
векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с наибольшим зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей классы. Разделяющей гиперплоскостью будет гиперплоскость, создающая наибольшее расстояние до двух параллельных гиперплоскостей. Алгоритм основан на 
допущении, что чем больше разница или расстояние между этими 
параллельными гиперплоскостями, тем меньше будет средняя 
10