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

Введение к работе

Актуальность темы исследования и степень разработанности проблемы. В современных вычислительных и производственных системах любой процесс характеризуется наличием большого количества параметров, а следовательно, значительной размерностью, необходимостью решать задачи оперативного управления для коротких временных промежутков и часто в условиях неполноты или отсутствия информации о некоторых параметрах. Эта специфика значительно усложняет постановку задач и обусловливает актуальность разработки специальных методов их решения. По некоторым оценкам более 80% задач планирования являются NP-трудными. В этой связи значительный интерес представляют субоптимальные решения, полученные за приемлемое время различными эвристическими алгоритмами, к которым относятся в числе прочих эволюционные алгоритмы (ЭА). Среди достоинств ЭА выделяют то, что они не накладывают ограничений на вид целевой функции и область определения задачи, и большинство их моделей универсальны. Однако существуют недостатки, связанные с отсутствием общих рекомендаций по настройке параметров, необходимой для успешной работы этих алгоритмов. Обычно параметры подбираются эмпирически, но для задач большой размерности это сделать сложно. Усовершенствованию алгоритмов посвящено множество работ, в которых прослеживаются три основных подхода: особые способы кодирования и представления особей (D. E. Goldberg, А. Н. Скурихин и др.), изменение структуры основных эволюционных операторов (Ю. Ю. Петров, B. J. Park и др.) и модификация архитектуры, в том числе за счёт динамического изменения параметров (В. М. Курейчик, Т. С. Шаповалов, G. Wang и др.). Наличие большого числа параметров накладывает на алгоритм дополнительные ограничения и увеличивает его вычислительную сложность, что отрицательно сказывается на эффективности. Практически не проводятся исследования, связанные с подробной имитацией естественных систем, особенно социальных. Хотя можно сделать предположение, что, если алгоритм сильно приблизить к поведению самоорганизующейся системы, то он сможет направленно корректировать свои параметры. Таким образом, актуальность темы диссертационного исследования обусловлена необходимостью изучения возможностей усовершенствования эволюционных алгоритмов за счет направленного изменения параметров, в том числе при решении нетривиальных задач теории расписаний.

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

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

Предмет исследования - параметры эволюционных алгоритмов как имитации естественных систем.

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

Для достижения цели решались следующие задачи:

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

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

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

4. Разработка структуры программного комплекса для проведения вычислительных экспериментов и решения практических задач с использованием предложенных алгоритмов.

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

Основные результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

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

   Диссертационная работа соответствует следующим пунктам паспорта специальности 05.13.17 «Теоретические основы информатики»: п. 1 «Исследование, в том числе с помощью средств вычислительной техники, информационных процессов, информационных потребностей коллективных и индивидуальных пользователей», п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур», п. 13 «Применение бионических принципов, методов и моделей в информационных технологиях».

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

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

   Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на конференциях и семинарах различного уровня, среди которых основными являются: Международная конференция «Математика. Компьютер. Образование» (Пущино, 2009; Дубна, 2012; Пущино, 2013); Международная научная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2010-2012); Всероссийская научная школа «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 2012).

   Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 2 работы [1,2] - в изданиях, рекомендованных ВАК РФ. В работах, выполненных в соавторстве: в [1, 2] предложены модель и алгоритм решения задачи составления расписания серверных процессов распределенной сети; в [4,5,6] построены модели эволюционного алгоритма для решения задач конвейерного типа теории расписаний; в [9] построена модель самоадаптирующегося эволюционного алгоритма, основанного на использовании продукционной системы управления для корректировки параметров.

   Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 78 наименований и приложения. Изложена на 141 странице основного текста и включает 36 рисунков и 27 таблиц.

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

   

   Разработка и исследование нейросетевых алгоритмов решения задач навигации интеллектуальными мобильными агентами в нестационарных средахПриемко Андрей Анатольевич

   

   Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходеКосовская, Татьяна Матвеевна

   

   Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

   Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединенийОрлов Николай Николаевич

   

   Разработка и исследование алгоритмов установления пиксельных соответствий на стереопарах для решения задачи восстановления рельефаЧумаченко Александр Викторович

   

   Разработка моделей и методов нечёткого логического вывода для управления производственными объектами в условиях априорной неопределенностиСинявская Екатерина Дмитриевна

   

   Разработка и исследование схем оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравненийЗаика Ирина Викторовна

   Комбинированные алгоритмы решения задачи одномерной упаковкиНаумова Ольга Анатольевна

   

   Итерационные методы и алгоритмы решения задачи сильной отделимостиЕршова, Арина Владимировна

   Нейросетевые алгоритмы для решения задач кодирования изображений с использованием технологии CUDAНгуен Виет Хунг