автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка и исследование оптимизационных алгоритмов эволюционных вычислений на основе унификации методов гибридизации

9 15-5/1044

На правах рукописи

/

СЫТНИК Кирилл Игоревич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ

АЛГОРИТМОВ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ НА ОСНОВЕ УНИФИКАЦИИ МЕТОДОВ ГИБРИДИЗАЦИИ

Специальность 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Воронеж - 2015

Работа выполнена в ФГБОУ ВПО «Липецкий государственный технический университет»

Научный руководитель: Блюмин Семён Львович, доктор физико-

математических наук, профессор

Официальные оппоненты: Демидова Лилия Анатольевна, доктор

технических наук, профессор, ФГБОУ ВПО «Рязанский государственный радиотехнический университет», профессор кафедры вычислительной и прикладной математики;

Ерёменко Юрий Иванович, доктор технических наук, профессор, Старооскольский технологический институт им. A.A. Угарова (филиал) ФГОУ ВПО «НИТУ «Московский институт стали и сплавов», декан факультета автоматизации и информационных технологий

Ведущая организация: ФГБОУ ВПО «Воронежский государственный университет»

Защита диссертации состоится 21 декабря 2015 г. в 11:00 на заседании диссертационного совета Д 212.037.01 при ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет» и на сайте www.vorstu.ru.

Автореферат разослан 21 октября 2015 г.

Учёный секретарь диссертационного совета

Барабанов Владимир Федорови

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 1 ----

Актуальность темы. В настоящее время широко исследуются и применяются методы оптимизации, созданные по образу существующих в природе биологических систем и использующие принципы, отработанные природой за долгие годы эволюции. Существуют различные наименования таких оптимизационных методов: роевые, интеллектуальные, стохастические, биоинспи-рированные, в данной работе используется термин «алгоритмы эволюционных вычислений». Согласно терминологии В.М. Курейчика, В.В. Курейчика и С.И. Родзина, эволюционные вычисления как математические преобразования, трансформирующие, согласно принятой модели, входной поток информации в выходной, основаны на правилах имитации механизмов эволюционного синтеза, а также на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. Большинство алгоритмов эволюционных вычислений являются популяционными; моделируя поведение, эволюцию популяции особей, они преобразуют конечное множество альтернативных кандидатов на решение задачи, приближая его к оптимумам. Это метод роя частиц, муравьиный алгоритм, пчелиный алгоритм, генетический алгоритм и другие. Такие методы легко распараллеливаются, повышая своё быстродействие и надёжность.

Термин «гибридизация» (комбинирование) использовался ещё в работах Л.А. Растригина, который понимал под ним процесс синтеза новых алгоритмов с использованием уже существующих. А.П. Карпенко также широко использует данный термин, в его трактовке гибридный алгоритм может объединять либо различные алгоритмы, либо одинаковые алгоритмы, но с различными значениями свободных параметров. Гибридизация методов оптимизации позволяет уменьшить время нахождения оптимума, упростить трудоёмкую настройку параметров и достичь ещё большей универсальности, то есть успешной работы на большем количестве разнообразных функций. Следует особо отметить, что до сих пор не определён общепринятый подход к гибридизации. Существует множество классификаций способов комбинирования алгоритмов, но при этом отсутствует унифицированная запись моделей гибридизации, а сама задача построения таких моделей остаётся без должного внимания.

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

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

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

Диссертационная работа соответствует научным направлениям ФГБОУ ВПО «Липецкого государственного технического университета» «Вычислительная математика», «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

Задачи исследования. В соответствии с целью были поставлены и решались следующие задачи:

- обзор и исследование существующих оптимизационных методов эволюционных вычислений;

развитие теоретических основ описания и функционирования оптимизационных методов эволюционных вычислений, преобразующих популяцию решений путём унификации их формализованной записи;

- развитие теоретических основ описания и построения гибридных оптимизационных методов эволюционных вычислений на основе унификации формализованной записи методов гибридизации;

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

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

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

- практическая апробация разработанного программного комплекса на предприятии, анализ результатов внедрения.

Методы исследования. В работе использовались методы математического моделирования, методы оптимизации, теория интеллектуальных систем, теория управления, теория вероятностей и математическая

статистика, теория множеств, теория комбинаторного анализа, объектно-ориентированное программирование, вычислительные эксперименты.

Тематика работы. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»: п. 2. «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; п. 5 «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента».

Научная новизна. В диссертации получены характеризующиеся научной новизной результаты:

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

- унифицированное формализованное описание гибридизации оптимизационных методов эволюционных вычислений, отличающееся введением понятия «оператор гибридизации», который задаёт способ взаимодействия комбинируемых методов;

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

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

и гибридизационный подход позволяют исследовать существующие и синтезировать новые методы эволюционных вычислений, улучшая их универсальность и эффективность. С помощью разработанного подхода был синтезирован новый гибридный оптимизационный метод, отличающийся эффективностью на различных задачах. Разработана структура программного обеспечения, реализующая синтезированные методы и предназначенная для решения широкого класса оптимизационных задач. Компоненты математического и программного обеспечения прошли государственную регистрацию в Отраслевом фонде алгоритмов и программ, а также в ФГБУ «Федеральный институт

промышленной собственности» (РОСПАТЕНТ).

Реализация и внедрение результатов работы. На основе разработанной структуры реализован комплекс программ, который используется в ПАО Ростелеком для составления и оптимизации многосменных рабочих графиков операторов са11-центра, соответствующих прогнозу клиентской нагрузки, а также для оптимального распределения по исполнителям заявок на установку оборудования. С помощью разработанного комплекса составляется расписание операторов, соответствующее прогнозу клиентской нагрузки, минимизируется общее время, затрачиваемое на установку клиентского оборудования, что позволяет как увеличить эффективность обслуживания клиентов, так и снизить производственные затраты. Теоретические результаты диссертации используются в учебном процессе в ФГБОУ ВПО «Липецкий государственный технический университет» при подготовке бакалавров по направлению «01.03.04 Прикладная математика» и магистров по направлениям «01.04.04 Прикладная математика» и «09.04.01 Информатика и вычислительная техника», выполнении дипломных и курсовых проектов.

Апробация. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях и форумах: VI, IX Всероссийских школах-конференциях молодых ученых «Управление большими системами» (Ижевск, 2009; Липецк, 2012), Международной летней научной школе «Парадигма» (Варна, Болгария, 2015) а также на научных семинарах кафедры прикладной математики Липецкого государственного технического университета (Липецк, 2010-2015). Работа выполнялась при финансовой поддержке Фонда развития малых форм предприятий «Участник молодежного научно-инновационного конкурса» «У.М.Н.И.К» (тема №2189ГУ1/2014, 2014-2015).

Публикации. Основные результаты диссертационного исследования опубликованы в 9 научных работах, в том числе 2 — в изданиях, рекомендованных ВАК РФ, 1 свидетельство на программу для ЭВМ. В работах, опубликованных в соавторстве, лично соискателю принадлежат следующие результаты: [2,8] - разработка модели оптимизационного метода эволюционных вычислений, модели гибридизации методов, гибридного алгоритма «Отжиго-вая эволюция роя», проведение вычислительных экспериментов, '[9].....разработка моделей и алгоритмов оптимизации многосменных расписаний, а также структура и реализация программного комплекса.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения и списка использованной литературы. Основная часть работы изложена на 126 страницах машинописного текста, содержит 30 рисунков и 11 таблиц. Список литературы содержит 109 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, сформулированы цель и задачи исследования, определены научная новизна и практическая значимость результатов .работы.

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

В общем случае решается задача оптимизации функции нескольких переменных:

/(£) opt,

< х£Х, (1)

X Х\7 ...jXij ...хп.

Функция представляет собой «черный ящик», то есть её характер заранее неизвестен. Задано поисковое пространство, для каждой точки которого известно как вычислить значение ф = f(x). Цель оптимизации - нахождение решения (то есть точки поискового пространства) с наилучшим значением функции ф за ограниченное время. Отношение качества найденного решения к потраченному времени определяет эффективность поиска.

Рассматриваются такие известные методы эволюционных вычислений как:

- ABC (Artificial Вее Colony) - алгоритм искусственной пчелосемьи;

- АСО (Ant Colony Optimisation) - муравьиный алгоритм;

- ВА (Bats Algorithm) - алгоритм летучих мышей;

- CS (Cuckoo Search) - алгоритм кукушки;

- CMA-ES (Covariation Matrix Adaptation Evolution Strategy) - эволюционная стратегия с адаптацией матрицы ковариаций;

- FSS (Fish School Search) - оптимизация косяком рыб;

- PSO (Particle Swarm Optimisation) - оптимизация роем частиц;

- SA (Simulated Annealing) - метод имитации отжига;

- SbPPA (Strawberry Plant Propagation Algorithm) - алгоритм земляничной поляны.

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

Примеры эволюционных операторов, оператор выбора альтернативного решения х' метода БА:

0s/ : хп = х1 + Sign{rnd - 0.5) • temp* ■ ((1 + l/iemp')2^"1 - 1), где Sign - функция определения знака:

{Sign(rnd — 0.5) = —1 при rnd < 0.5, Sign(rnd — 0.5) = 1 иначе.

(2)

(3)

Здесь и далее rnd € [0; 1) - равномерно распределённая случайная величина. В операторе производится изменение координаты в некоторой окрестности, размер которой зависит от температуры отжига temp1.

Оператор вероятностного принятия альтернативного решения метода SA:

Osxa{F', F, temp) :

F* = НХ*)-,1* = f(Xl)-,d = F* - F*, если e~d/tempt > rnd, то = x'\

(4)

rt+1

иначе x

Новое положение x' частицы принимается с некоторой вероятностью, зависящей от разницы новой и предыдущей целевой функции и текущей температуры отжига temp1.

Оператор выбора новой точки метода PSO:

вычислить центр и радиус гиперсферы, окружающей хь : д1с = хг + ф-гп й- {Ьг + 11- 2х*)/3,

взять случайную точку в гиперсфере

х' = д1с + д\-(2гЫ-\), (о)

вычислить новую скорость

QPSO

„4+1

= и • vl + х' — хг;

вычислить новые координаты

v.t + 1

= х' + и> ■ V1.

Оператор скрещивания вА, плоский кроссовер:

двл , I м/2 раз выбираются родители рьрг;

^генерируется ген потомка х' 6 [тт{х[, х%)] тпах(а%\ х^)}-

Оператор отбора вА, например,

nGA J заменить худшие Л родительских решений

UXsel '■ S

lJ

[ лучшими потомками.

(?)

Разнообразие оптимизационных методов эволюционных вычислений и способов их описания обосновывает необходимость введения универсальной записи их моделей с использованием описанного понятия эволюционного оператора.

Во второй главе унифицировано формализованное описание оптимизационного метода эволюционных вычислений и формализованное описание гибридизации оптимизационных методов.

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

А = {Х\ ОХ) = (Х\ {0,5, С)), при * > 0 Xм = ОХ{Х% (8)

где Хг - популяция решений в момент времени t, то есть состояние модели метода, ОХ - эволюционная модель преобразования популяции,

0 =< 0\,..., О г > - кортеж эволюционных операторов, последовательно преобразующих популяцию, 5 - множество структур, необходимых для функционирования операторов из кортежа О, С - набор параметров, используемых операторами из кортежа О. Как правило, данная модель функционирует в дискретном времени t £ И, которое представляет собой номер итерации, при

1 = 0 популяция Х° инициализируется некоторым внешним воздействием, при £ > 0 популяция преобразуется согласно модели эволюции ОХ, которая может как зависеть от времени (если во времени изменяются параметры, структуры или операторы), так и не зависеть (в обратном случае).

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

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

Уровень абстракции Высокий А = (Х\ ОХ) = {ХК (О,5, С))

у.Х:.

\

Средний Аххх = {X*, (< Ои ..., Ок >, (5Ь ..., S,), (Ci> ■ ■ ■, Сп))

\

Низкий х'м =xl + temp4 • ((1 + 1 /temp1)2™*-1 - 1) ■■• хм =x' + w vl -Рис. 1: Иерархически раскрываемая запись

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

Гибридизация, воплощающая коэволюционный подход, для двух алгоритмов А\ = (Х\,ОХ\),А2 = (Xi, ОХ г) в описанной терминологии будет записываться как

-4-1,2 = (Х1,Х2,ОХиОХ2,ОНи2), (9)

где ОН\ 2 - кортеж операторов гибридизации, определяющий каким образом распределяются вычислительные ресурсы между операторами эволюционных моделей OXi и ОХ2 и каким образом связаны популяции Xi и Х2. Коэволюционная гибридизация означает, что каждый алгоритм будут преобразовывать свою популяцию, но популяции будут некоторым образом взаимодействовать. Гибридизация вложением будет записываться следующим образом:

М,2 = (X, OXh2) = (X, (ОХьОХ2, ОЯЫ), (Ю)

где ОН 1,2 - оператор, преобразующий кортежи операторов исходных алгоритмов в кортеж операторов гибридного алгоритма, OXi<2 = OHit2(OXi,OX2).

Как было отмечено ранее, структуры, параметры или операторы могут как зависеть от t, изменяясь в процессе эволюции (например, температура отжига tempt в методе SA), так и не зависеть (например, социальный и инерционный параметры ф, и в PSO). Пример гибридного (имитации отжига и роя частиц) алгоритма, полученного с помощью гибридизации вложением: ^вложение PSO Ш SA = {X*, (0PSO, 0SA, Sl, С)) = (Р(, (< 0L, 0G,0x

sa

Ox jF,F', temp\, Ov, 0F, 0B, Otopol >, {L\ G1,^, V\ Fl, B\ Topol4), (ф, w))).

sa sa

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

Пример гибридного (имитации отжига и роя частиц) алгоритма, производится коэволюционная гибридизация:

■^коэволюция PSO S SA — (^54> XpsO' (О, S\ Ct)sA, {О, S\ С)PSO, OHi¡2) =

(■^SA> XpsO' (< ОН\2, OH 1.2 >> < OxOy, Ox-Otemp >SA, < Ol, Oq, 0X, Oy , Op, 0¡}, OT0P0L >PSO, (F\ X'\ F*)sa, {L\ G\ VK F\ B\ Торо1г)рзо, (temp1, a)SA, (Ф, u)PS0)),

где оператор гибридизации OH\ может, например, на каждом шаге сравнивать результаты работы алгоритмов, увеличивая размер популяции победителя или уменьшая размер популяции проигравшего:

если результат PSO на последнем шаге оказался лучше:

min{XiPSo} < min{XjSA}, где i £ mPSo,j € mSA,

__rr то размеры популяций меняются так: , .

ОН i : < (11)

mSA = mSA - 1, mpso = mpso + 1,

иначе размеры популяций изменяются в пользу SA: TOSA = "ISA + 1-, "ipso = mpso - 1.

а оператор гибридизации ОН2 может, например, заменять худшее решение проигравшего алгоритма лучшим решением победителя.

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

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

1. Производится сравнение на тестовых задачах исходных алгоритмов оптимизации.

2. Согласно выбранному критерию отбираются наиболее успешные алгоритмы.

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

4. Согласно составленной таблице проводится гибридизация и тестирование.

5. Если принимается решение продолжить гибридизацию, то производится переход на шаг 2.

Рис. 2: Гибридизационный подход

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

Согласно предложенному подходу с помощью гибридизации вложением был реализован новый алгоритм, названный Отжиговая эволюция роя (для единообразного наименования алгоритмов будет использоваться сокращение от английского названия, Annealed evolution of swarm, AES) и сочетающий элементы PSO. SA и GA (исследования и модификации этих методов по отдельности, а также конвейерная гибридизация проводились автором ранее).

Существующие алгоритмы PRSA и PSO-B-SA можно считать прообразами AES, при этом предложенный гибрид отличается от PRSA использованием

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

Для демонстрации отличий можно записать модели эволюции алгоритмов в предложенной формализации с высоким уровнем абстракции:

Oprsa =< OGxi0SS, 0gxí¿F\ Ft+1) >, (12)

opso-b-sa=<osxa,opxso>, (13)

Oaes =< Of, Opxso{F, F>, temp), 0GxAaott, 0GAel > . (14)

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

Aaes = (Х\ (Оaes, &,(?)) =

= (Х\ (< ofOpxso{F, F', temp), 0Gxtss, 0GAel >, S\ Сf)) (15) множество' структур запишется как

S\es = (^,Ь\С\У\В\Торо1[,Х'1^п). (16)

pso sa

Множество параметров

Caes = templa, j^X). (17)

pso sa ga

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

0?А : = х* + Sign(rnd - 0.5) • G^, g^), (18)

где G(n,cr) - функция нормального распределения с математическим ожиданием ¡л и дисперсией ст. Затем с вероятностью, зависящей от разницы новой и предыдущей целевой функции и текущей температуры отжига temp1 (аналогично (4)), выполняется оператор метода роя частиц Opso (5). Применяется оператор скрещивания, например, плоский кроссовер 0G^.oss (6) Выполняется некоторая стратегия эволюционного отбора, например,

OfU (7).

Запись синтезированного алгоритма Отжиговой эволюции роя в псевдокоде выглядит следующим образом (при t > 0, после инициализации):

Алгоритм 1. Отжиговая эволюция роя (АЕБ) Дано: t - номер итерации, п - размерность поискового пространства, ограничения пространства поиска зтг„, втах, х - решение, кодируемое текущими координатами частицы, Ь - лучшее решение, достигнутое частицей Для каждой частицы в рое выполнять {

Определить лучшее достигнутое решение среди соседей в нише Р Для каждого измерения поискового пространства выполнять{ ере —0.5)-С(0.5/(1+пег,а/),£етр/£етрта1) • (йтат -^тт)

х' <— хг + ере Проверить ограничения: Если х' < Зт1п ТО х' 5'тгп Если х' > 5тах ТО х1 Эшах хм Дх4+1) - /(I')

Если Ехр(—й/Ьетр) < гпв, то

Для каждого измерения пространства поиска выполнять{ Вычислить центр гиперсферы: Если Ь1 = I1 то

С? <- х1 + ф • (б4 - хг)/2 Иначе

в* X* + ф ■ гпй ■ (Ь* + 1г - 2 • хь)/2 Вычислить радиус гиперсферы г |С?г — х1\ Взять случайную точку в ней: х' <г- С + г • (2 ■ гпй - 1)

Вычислить новую скорость и> ■ V1 + х' — хг

Вычислить новые координаты хн+1 ш ■ ьг + х' Проверить выполнение ограничений.

}

Если /(¿с*+1) < /(£) то Ьм х Иначе

Если /(^+1) < /(?) то Ъм «-р+1.

}

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

}

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

Если не найдено решение лучше предыдущего то

Обновить топологии ниш, в которых произошло улучшение глобальной оценки /(^+1)

Для сравнения алгоритмов проводилась минимизация на шести тестовых функциях, приведенных в таблице 1. Первые пять функций многоэкстремальны. Функции были сдвинуты в пространстве координат таким образом, чтобы глобальный оптимум достигался в точке х* = 1.0, для исключения достижения оптимума при последовательном уменьшении переменных. Для всех функций значение в точке глобального оптимума равно 0.

Таблица 1: Тестовые функции

Функция Формула Индекс

Розенброка 1X7 [100 • (xj+i - х2)2 + (1 - Xi)2 fx

Растригина Т,г-1 (Хг - l)a - 10 • С08(27г(а* - 1)) + 10 h

Гриванка i + EIU^-n^cos^) h

Экли 20 + е - 20ехр (-0.2^ £?=1(х, - I)2) -ехР (n £Г=1 соэ(27г(х; — 1))) U

Швефеля 1.2 £?=i(£Ute -1))2 h

Сфера h

Таблица 2: Использованные параметры для тестовых функций

Функция Пространство поиска Пространство инициализации Лимит времени

Розенброка -30; 30 15; 30 60с

Растригина -5.12; 5.12 2.56; 5.12 20с

Гриванка -600; 600 300; 600 20с

Экли -32; 32 16; 32 60с

Швефеля 1.2 -100; 100 50; 100 40с

Сфера -25; 25 12.5; 25 30с

Сравнивались описанные в предыдущих главах классические алгоритмы и их гибриды, список приведён в таблице 3.

Таблица 3: Сравниваемые методы

Сокращение Полное название

PS02011 Particle Swarm optimization (Метод роя частиц)

SA Simulated Annealing (Имитация отжига)

GA Genetic Algorithm (Генетический алгоритм)

PRSA Parallel Recombinative Simulated Annealing (Параллельная рекомбинационная имитация отжига)

PSOBSA (1,2) Hybrid Particle Swarm-Based-Simulated Annealing Optimization Techniques (Гибридизация оптимизации роем частиц и имитацией отжига)

AES Гибридный алгоритм, предложенный в данной работе: Отжиговая эволюция роя

Ограничения поискового пространства и интервалы инициализации алгоритмов приведены в таблице 2, поиск проводился для 30 измерений. Размер популяции для каждого из алгоритмов был равен 100 решениям. Было проведено 100 испытаний, в каждом из них поиск производился до истечения заданного для соответствующей функции времени.

В таблице 4 приведено среднее достигнутое решение за 100 испытаний.

Таблица 4: Сравнение эффективности методов

PS02011 SA GA PRSA PSOBSA1 PSOBSA2 AES

/1 7,8Е-04 3.9Е-01 3,4Е—00 1,8Е-03 1.5Е+02 4,6Е-03 3,8Е-09

к 2.6Е-11 8,9Е-07 2.5Е+01 7,9Е-04 1Е+02 9,4Е^-01 8,5Е-13

/з 2.9Е-10 1,6Е-07 4,5Е-04 2,2Е-05 4,8Е-04 5,2Е-07 2.4Е-16

/4 8Е-09 5.8Е-01 2.4Е-01 8Е-02 3,6Е-09 9,6Е-01 6ДЕ-08

/о 8ДЕ-08 9,ЗЕ-01 7.8Е-01 5,8Е-04 8,5Е-05 ЗДЕ-ОЗ 9.4Е-13

/б 3.6Е-06 5,4Е-02 2.2Е+00 5.5Е-06 3,7Е-08 4.3Е-10 8.7Е-15

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

Четвёртая глава посвящена описанию структуры проблемно-ориентированного программного комплекса оптимизации рабочих графиков методами эволюционных вычислений «ОРГ», а также его апробации на комбинаторных задачах оптимизации, возникших в ПАО Ростелеком.

Программный комплекс, реализованный в среде разработки Microsoft Visual Studio 2012 на языке программирования состоит из следующих модулей (рис. 3):

- модули «CallCenter_Data» и «Installers_Data» преобразуют исходные данные задачи составления многосменного расписания (прогноз клиентской нагрузки, допустимые шаблоны смен) и задачи распрёделения заявок по установщикам оборудования (необходимое оборудование и навыки, матрица временных затрат) в вид многомерных задач оптимизации;

- модуль «Optimization» реализует синтезированные гибридные методы оптимизации эволюционных вычислений, в том числе Отжиговую эволюцию роя, в нём происходит решение задач, заданных в предыдущих проблемно-ориентированных модулях;

- модуль «Optimization_Settings» позволяет настраивать параметры методов оптимизации модуля «Optimization»;

- модули «CallCenter_Output» и «Installers_Output» графически отображают результаты оптимизации соответственно предметной области.

Рис. 3: Структура программного комплекса «ОРГ»

На схеме модули «CallCenter_Data» и «Installers_Data», а также «CallCenter_Output» и «Installers_Output» объединены для наглядности, так как выполняют одинаковые функции для разных задач.

Далее в четвёртой главе рассматривается решение задач оптимизации, возникших в ПАО Ростелеком. Задача №1 - автоматизировать распределение рабочих смен по операторам. Многомерная задача линейного программирования. Задачу необходимо решать ежемесячно, но могут быть исключения, требующие срочного решения.

Имеется прогноз требуемого количества работников Y = [Уо, -.J/i, ••■, ут-\] на т €. N интервалов времени, где т/, £ N - количество работников, необходимых для выполнения прогнозной работы в интервал

времени г. Имеется набор из к Е N шаблонов рабочих смен S = ■•■ , для

>->fc-i J

каждого из которых с помощью булевого вектора Sj = [so,j, ■••> Siji ■■■■. Sm-ij] определено, какие интервалы являются рабочими, а какие нет. Искомое решение представляется следующим образом: X = \xq,...,Xj,...,Xk], к -число шаблонов рабочих смен, Xj € N - количество работников, работающих расчётный период по смене j. Задача - назначить работникам определённые смены так, чтобы наиболее полно удовлетворить прогнозную потребность:

шах | ^ min ^уг, ^(xjSij)'J j (19)

и минимизировать при этом максимальные абсолютную и относительную

нехватку работников в г-й интервал рассматриваемого периода

тт |тах - ¿^(х^)^ |; тт |гашс ^-—-11 . (20)

Графический пример оптимального решения приведён на рис. (4).

Овчин "воатк» Мвкежикиа» »•вв'п« Сг»»«| >. ;л:*асв Млталмл»««» ;ж«>

¿00 ' 1333 "' ■ «435845 % Я ! »6330 I М1 5.« Ов »01

«всогасч»«» о1»ое."вг»»ч» о&ыч» и» су!** -«и-чрв«л

Рис. 4: Оптимальное расписание для 800 сотрудников с использованием 20 и 200 смен в сравнении

Благодаря применению ПК «ОРГ» появилась возможность эффективно использовать несколько сотен рабочих смен, что позволило существенно поднять уровень обслуживания клиентов.

Задача №2 - автоматизировать распределение заявок по установщикам. Открыто-закрытая транспортная задача с временными окнами и множеством ограничений. Задачу необходимо решать ежедневно.

Имеется п заявок клиентов на установку оборудования и к команд установщиков (1 или 2 человека). У каждой заявки и команды есть свойства, соответствие которых необходимо обеспечить при распределении для обеспечения возможности выполнения заявки. Все установщики стартуют в одной точке, в зависимости от наличия уникального оборудования им может требоваться возврат в начальную точку в конце рабочего дня, иначе маршрут заканчивается на последней выполненной заявке. Необходимо минимизировать совокупное время передвижения команд установщиков по городу и обеспечить справедливость распределения (в простейшем случае иод справедливостью понимается пропорциональность количества заявок количеству заявленных интервалов рабочего времени). Для учёта времени строятся две матрицы временных затрат (одна для пешеходов, вторая для автомобилистов) размера (п +1) х (п+1) (из каждой точки в каждую). Маршрут команды г выглядит так: = [хо, - количество точек маршрута.

Таким образом, общий вид задачи без учёта проверки ограничений:

Г к-1 / ¡Х,:-1 \ к-1

Е *«>, чо) + Е + ^ ' Е = *> (2!)

[ ¿=0 \ .7=1 / J г=0

где г(01;,) - затраты времени на перемещение от пункта а до пункта Ь согласно соответствующей матрице временных затрат Z. Если маршрут группы не содержит заявок, требующих уникального оборудования, то г\аск = 0, иначе г\аск = Благодаря применению ПК «ОРГ», использующего алгоритм «Отжиговая эволюция роя», появилась возможность справедливо распределять клиентские заявки и обеспечить их своевременное выполнение, минимизировав время перемещения исполнителей более чем на 15%.

В заключении сформулированы выводы и приведены основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложено унифицированное формализованное описание гибридизации оптимизационных методов эволюционных вычислений, отличающееся введением понятия «оператор гибридизации», который задаёт способ взаимодействия комбинируемых методов.

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

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

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

6. Компоненты программного комплекса прошли государственную регистрацию в ФГБУ «Федеральный институт промышленной собственности» (РОСПАТЕНТ).

7. Программный комплекс внедрён ПАО Ростелеком для составления и оптимизации многосменных расписаний работ сотрудников.

'5-11220

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

Публикации в изданиях, рекомендованных ВАК РФ

1. Sytnik K.I. Particle swarm optimization in details /7 Вести высших учебных заведений Черноземья. - 2014. - № 3(37). - С. 44-48.

2. Сытник К.И. Гибридизация оптимизационных методов эволюционных вычислений / Блюмин С.Л., Сытник К.И. // Системы управления и информационные технологии. - 2015. - №3(61). - С. 8-13.

Свидетельства на программу для электронных вычислительных

машин

3. Сытник К.И. ОРГ (Оптимизация рабочих графиков) / К.И. Сытник - М.: ФГБУ ФИПС. - 2015. Госрегистрация № 2015613851 от 26.03.2015.

Статьи и материалы конференций

4. Сытник К.И. Генетические алгоритмы в комбинаторной оптимизации Современные проблемы науки и образования. - 2009. - Xs 3. - С. 133-135.

5. Сытник К.И. Аспекты организации оптимизационных генетических алгоритмов // Управление большими системами: сборник трудов VI Всероссийской школы-семинара молодых ученых. - Том 1. - Ижевск: ООО Информационно-издательский центр «Бон Анца». - 2009. - С. 325-328.

6. Сытник К.И. Разработка структуры системы оптимизации многосменных рабочих графиков // Управление большими системами: материалы IX Всероссийской школы-конференции молодых учёных. - Том 1. - Тамбов-Липецк: изд-во Першина Р.В. - 2012. - С. 114-117.

7. Сытник К.И. Модификации генетического алгоритма и метода имитации отжига // Информационные технологии моделирования и управления. -2013. - Том 83. - № 5. - С. 454-460.

8. Блюмин С.Л., Сытник К.И. Новый гибридный метод оптимизации - от-жиговая эволюция роя // Международная летняя научная школа «Парадигма». - Том 1. - Варна: ЦНИИ «Парадигма» - 2015. - С. 28-33.

9. Сытник К.И. Составление и оптимизация графиков работ / Блюмип С.Л.. Сытник К.И. // М.: ОФАП. - 2011. Госрегистрация № 50201150668 от 27.04.2011.

Подписано в печать 19.10.2015. Формат бумаги 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 500.

2015670943

2015670943