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

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

005058689

РОДЬКИНА Маргарита Борисовна

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

Специальность: 05.13.17-Теоретические основы информатики

АВТОРЕФЕРАТ

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

1 В МАЙ 2013

Воронеж-2013

005058689

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет»

Научный руководитель: доктор технических наук, профессор,

Леденёва Татьяна Михайловна

Официальные оппоненты: Матвеев Михаил Григорьевич,

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

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

Ведущая организация: Технологический институт федерального

государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге

Защита состоится «29» мая 2013 года в 15 час. 00 мин. на заседании диссертационного совета Д.212.038.24 в ФГБОУ ВПО «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., 1, ауд. 226.

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

Автореферат разослан «26» апреля 2013 года.

Ученый секретарь

диссертационного совета Чеботарев А. С.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновываются актуальность темы, научная новизна и значимость работы, а также приводятся цель и задачи исследования.

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

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

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

Рисунок 1 - Схема социального эволюционного алгоритма

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

Чем больше возраст и ниже приспособленность особи, тем выше вероятность её гибели. Эта вероятность для особи <т определяется по формуле:

Р**и И = пип

1,

!_. 1И-

дяе(<т) ' 1.5-а1р(Р)

шах/(су)

V ч У

где а1р{Р) - средняя продолжительность жизни (параметр популяции Р), а^е(ст) - возраст особи, /(сг) - приспособленность особи.

Чем выше приспособленность особи, тем выше её качества лидера, и тем больший вес имеет её мнение при принятии коллективных решений.

Популяция Р может находиться в трех состояниях: состоянии стабильности, упадка и гипертрофии, каждое из которых определяется соотношением численности популяции и параметров алгоритма (порог упадка Т(Р) и порог

гипертрофии Т(Р)), а также равновесием полов. Популяция находится в стабильном состоянии, если количество её особей принадлежит отрезку [Г(Р),Г(Р)], и отношение количества особей одного пола к количеству другого не превышает 1,5. Если численность популяции становится меньше Г, или равновесие полов нарушается, то популяция переходит в состояние упадка. Если численность популяции превышает Т, то популяция переходит в состояние гипертрофии. Если популяция теряет стабильность, она начинает предпринимать действия по возвращению в это состояние. Выбор её действий зависит от коллективного решения, принимаемого особями популяции. В состоянии упадка популяция может объявить войну другой популяции с целью захвата особей, некоторое время искусственно влиять на процесс размножения (тогда возрастает вероятность получения большего числа потомков при скрещивании, либо возникают направленные на выравнивание соотношения полов мутации) или принять решение о вырождении (тогда все особи мигрируют, и популяция исчезает). В состоянии гипертрофии часть популяции может отделиться с одним из лидеров и образовать новую популяцию.

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

Рисунок 2 - Схема самоадаптирующегося алгоритма

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

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

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

Задача решается в рамках следующих предположений.

1. Группа работ (я), ожидающих выполнения, известна всем сотрудникам. Каждая работа ; заключается в выполнении к, операций. Известно время

выполнения каждой операции _/' каждым сотрудником Сотрудник может принять на выполнение любую работу, находящуюся в его компетенции.

2. Каждая операция выполняется без прерываний и находится в компетенции хотя бы одного сотрудника,/ (1 еС;). Есть операции, которые могут

выполняться одновременно несколькими сотрудниками (¡еР), и независимые операции, во время выполнения которых сотрудник может одновременно выполнять другую операцию (/' е I).

3. Для каждой работы / установлен директивный срок .

Таблица 1 - Особенности хронологического эволюционного алгоритма

Параметр алгоритма РНК-мяр Клеточный этап Видовой этап Социальный этап

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

Начальная популяция формируется случайным образом наследуется из РНК этапа наследуется из клеточного этапа и разбивается на две по типу питания (травоядные и плотоядные) наследуется из видового этапа

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

Оператор кроссовера отсутствует отсутствует случайного вида (применяется к парам разнополых родительских особей одного типа питания) случайного вида (применяется к парам разнополых родительских особей)

Количество потомков совпадает с количеством родителей совпадает с количеством родителей от 0 до 5 от 0 до 5

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

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

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

4. Операции можно разделить на два непересекающихся подмножества: относящиеся к работам, последовательность операций которых строго фиксирована г е М,, и относящиеся к работам, операции которых могут выполняться в произвольном порядке г 6 М2. -< /2 означает ситуацию, когда операция /, должна быть выполнена раньше, чем начнёт выполняться операция г2.

Модель задачи имеет следующий вид:

где хок = 1, если операция / выполняется сотрудником к /-Й по порядку, х^ = 0 в противном случае; г°, - время начала и завершения операции /; / - момент завершения работы И - момент завершения всех п работ;

51 = ^к, - общее количество операций всех работ; величина д, показывает,

превысил ли момент завершения работы g директивный срок (¡е (если для конкретного решения дг = 0, то работа ^ завершается вовремя, иначе, она выполняется с превышением директивного срока).

Если две операции г", и /2 выполняются одновременно сотрудником к, то

полагается, что сотрудник занят ими на протяжении времени I = тах^ц,?ц).

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

и кг, зависит от их скоростей V и у . Если у сотрудника kJ появляется

/ ч,; / 'к,,

возможность полностью завершить операцию (невыполненная часть / < I/ ), то второй сотрудник освобождается от её выполнения, иначе, оба /'*„■

сотрудника затрачивают ещё одну единицу времени.

Фактор неопределённости учитывается в задаче за счёт интервального

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

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

^ д. —> тт, О —> тт,

(V = 1)А = 1)л (('> £ V (/2 е /)) = 1, /, ^ /2;

представлены интервалами Л =[Л'Л]' £ = 1>и- Вероятность нарушения каждого директивного срока можно задать в виде:

Каждому расписанию можно поставить в соответствие вектор вероятностей (и = (//1,...,//л). Чем меньше вероятность ¡.1е для каждой работы g, тем лучше расписание. Для решения задачи необходимо оптимизировать интервальную длину расписания и вектор //, поэтому в диссертационной работе предложены правила сравнения интервальных переменных и векторов ¡л.

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

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

Основными автоматическими процессами сервера являются: репликация, агенты по расписанию, программы (команды по расписанию). Расписание циклично и составляется на сутки. Чтобы задать расписание любого процесса а, необходимо определить для него три параметра: время первого запуска **(а)> время последнего запуска /Да) и период между запусками р{а). Значения всех параметров принадлежат множеству 2п[0,Гш], где Гтах - количество единиц времени в сутках. Каждый процесс использует для своей работы ресурсы сервера. Чем больше процессов запущено, тем выше загруженность сервера, и тем медленнее он работает. Чтобы снизить загруженность, для сервера определяют такой параметр, как максимальное количество одновременно работающих процессов. Если по расписанию подходит время автоматического процесса, и значение параметра на сервере достигнуто, то процесс становится в очередь ожидания. Для агентов и команд определяется также максимальное время работы, по достижении которого процесс прерывается. Для репликации такой параметр ввести нельзя, она идёт до полного завершения обмена данными. Загруженность сервера можно описать множеством параметров: объём использования оперативной памяти, количество запущенных процессов и т. п. Для простоты рассматривается всего один критерий -

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

Идеальная функция загруженности /</(*) описывает верхнюю границу загруженности сервера автоматическими процессами, при которой его быстродействие можно считать нормальным. Л/(*)е[0Д], /6[О,Г„]. График идеальной функции загруженности - идеальная линия.

Критическая функция загруженности К (г) описывает верхнюю границу загруженности сервера автоматическими процессами, при которой его быстродействие можно считать удовлетворительным. АТ(/)е[0,1], /6 [0,7^]. График критической функции загруженности - критическая линия.

На основе расписания можно вычислить суточную загруженность каждого сервера Л", ={*,(/)}.__ (рисунок 3). В диссертационной работе предложен

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

Загруженность сервера

О 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

-Запросы--И(0 ---К(9

Рисунок 3 - Соотношение графиков загруженности

В качестве критерия оценки расписания в каждый момент времени / используется аддитивная свёртка масштабированных отклонений загруженности сервера от значений идеальной (К2(ф и критической (АГ,(ґ)) функций: К0(?) = + сс2(\- К^)), где а, +а2= 1.

і 0, х. и)<К,и), /ч

*,(/)(1-М(/))!

Задача за счёт обмена данными между серверами и необходимости составления расписания для всей системы сразу относится к смешанным задачам теории расписаний. Ее модель имеет следующий вид:

D, (X) min, X = X(A,R)\

31 (/, (h) ±l-p(h)e [frata (h),mm{it(h),tmm (A)}]); где Х- суточное расписание; Ц.(Х) = —1—- обобщённые

■^шах ' 1=0

критерии; А = (я,.,.} определяет расписание агентов,

v J Мкл,

ач, =(1\аи)'Р{а:М{ал))' R = WiM*M ~ матрица репликации,

_ ¡{1ХгЛр(гЛ(М)\ если серверы i,j реплицируются, '' [О, иначе;

^min минималыюе количество запусков процесса j на сервере i;

['тп^ДСиД^,)] - промежуток времени на сервере I, в течение которого

процесс j должен быть запущен хотя бы один раз.

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

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

В четвертой главе описывается программный комплекс SEA: Scheduling Evolutionary Algorithm, реализованный в среде Borland Delphi 7.0 и предназначенный для решения задач теории расписаний и оптимизационных задач моделируемыми эволюционными алгоритмами. Структура комплекса включает в себя модули настройки ЭА и блок решения задач (рисунок 4).

Цель вычислительного эксперимента заключалась в исследовании эволюционных алгоритмов в следующих аспектах: 1) выявить влияние системы управления на поведение алгоритма; 2) определить параметры, оказывающие наибольшее воздействие на алгоритм. В эксперименте рассматривались тестовые функции разной размерности (De Jong 1-5, Rastrigin, Swhefel и др.). Для сравнения алгоритмов использовались следующие критерии:

1) количество обращений к целевой функции;

2) процентная доля нахождения глобального экстремума.

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

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

Таблица 2 - Результаты вычислительного эксперимента

Алгоритм Процентная доля нахождения глобального экстремума Среднее количество вычислений функции цели

Простой генетический 48,5 24 452

Социальный 62,2 26 654

Социальный самоадаптирующийся 51,4 27 235

Простой самоадаптирующийся 57,3 18 541

Хронологический 72,6 22 125

Хронологический самоадаптирующийся 65,6 23 516

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

1. На основе анализа различных вариантов эволюционных алгоритмов выявлены пути повышения их эффективности за счёт дополнительных параметров и операторов и предложены три модели: СЭА, САЭА и ХЭА. В ходе вычислительного эксперимента выявлено, что модели в достаточной степени универсальны и являются более гибкими, чем стандартные. При этом СЭА и ХЭА за счёт принятия решений популяциями корректируют свои параметры, то есть имитируют самоадаптацию социальных систем.

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

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

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

Рисунок 4 - Структура программного комплекса SEA

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. РодькинаМ. Б. Задача составления расписания серверных процессов терри-ториально-распределённой сети / Т. М. Леденева, М. Б. Родькина // Вестник Воронежского государственного технического университета. - 2012 г.- Т. 8,- №7-1,— С. 58-61.

2. Родькина М. Б. Модель задачи нахождения оптимального плана работ и генетический алгоритм для ее решения / М. Б. Родькина, Т. М. Леденева // Вестник Воронежского государственного университета, серия: Системный анализ и информационные технологии.-2011 г.-№1.-С. 172-178.

Публикации в других изданиях:

3. Родькина М. Б. Генетические алгоритмы в теории расписаний / М. Б. Родькина // Сб. материалов конф. молодых преподавателей и студентов Лискинского филиала ВГУ (Лиски, 28 апреля 2008 г.). - Воронеж: ВГПУ, 2008. - С. 50-55.

4. Родькина М. Б. Генетические алгоритмы в теории расписаний / М. Б. Родькина, А. Я. Аснина // Сб. тезисов XVI Междунар. конф. «Математика. Компьютер.

Образование.» (Пущино, 19-24 января 2009 г.). - Ижевск: Научно-издательский центр «Регулярная и хаотическая динамика», 2009. С. 75-76.

5. Родькина М. Б. Использование генетических алгоритмов в теории расписаний / А. Я. Ленина, М. Б. Родькина // Сб. трудов XVI Междунар. конф. «Математика. Компьютер. Образование.» (Пущино, 19-24 января 2009 г.).- Ижевск: Научно-издательский центр «Регулярная и хаотическая динамика», 2009. - С. 99-105.

6. Родькина М. Б. Использование генетических алгоритмов для решения задач теории расписаний в условиях неопределенности / Т. М. Леденева, М. Б. Родькина // Сб. трудов Междунар. конф. «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 20-22 сентября 2010 г.).- Воронеж: Издатель-ско-нолиграфический центр Воронежского государственного университета, 2010. -С. 315-318.

7. Родькина М. Б. Адаптация генетических алгоритмов с помощью динамической системы управления / М. Б. Родькина // Сб. трудов Междунар. конф. «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 26-28 сентября 2011 г.). — Воронеж: Издательско-полиграфический центр Воронежского государственного университета, 2011. - С. 338-341.

8. Родькина М. Б. Задача составления расписания серверных процессов терри-ториальио-распределённой сети / М. Б. Родькина // Сб. тезисов XIX Междунар. конф. «Математика. Компьютер. Образование.» (Дубна, 30 января-04 февраля 2012 г.). - Ижевск: Научно-издательский центр «Регулярная и хаотическая динамика», 2012.-С. 50-51.

9. Родькина М. Б. Управление параметрами эволюционного алгоритма с помощью продукционной системы управления / М. Б. Родькина, Т. М. Леденева // Сб. материалов всероссийской иругной школы «Инженерия знаний. Представление знаний: состояние и перспективы» (Воронеж, 29-30 июня 2012 г.). - Воронеж: Изда-тельско-полиграфический центр «Научная книга», 2012. - С. 76-77.

. 10. Родькина М. Б. Непрерывный эволюционный алгоритм планирования процессов распределённой сети / М. Б. Родькина // Сб. тезисов XX Междунар. конф. «Математика. Компьютер. Образование.» (Пущино, 28 января-02 февраля 2013 г.). -Ижевск: Научно-издательский центр «Регулярная и хаотическая динамика», 2013. -С. 36-37.

Зарегистрированные программы для ЭВМ

11. Родькина М. Б. Программа для ЭВМ «Arabesque» / К. С. Погосян, М. Б. Родькина // ФГБОУ ВПО «ВГУ». Per. № 2013611749 от 04.02.2013. Москва: РОСПАТЕНТ, 2013.

Подписано в печать 26.04.13. Формат 60x84 '/.6. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 406.

Отпечатано с готового оригинал-макета 1 типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

РОДЬКИНА МАРГАРИТА БОРИСОВНА

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

Специальность 05.13.17 - Теоретические основы информатики

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

04201358211

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

Научный руководитель:

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

Леденёва Татьяна Михайловна

Воронеж-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..............................................................................................................5

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ.......................................................17

1.1 Достоинства и недостатки эволюционных алгоритмов..............................18

1.2 Основные понятия и общие схемы ЭА.........................................................19

1.3 Основные модификации ЭА..........................................................................22

1.4 Задачи теории расписаний: терминология, методы решения....................26

1.5 Цель и постановка задач исследования........................................................29

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ............................................................................32

ГЛАВА 2. РАЗРАБОТКА И АНАЛИЗ УСЛОЖНЁННЫХ МОДЕЛЕЙ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ................................................................33

2.1 Алгоритм имитации развития социума СЭА...............................................33

2.1.1 Представление и характеристики особи....................................................34

2.1.2 Особенности эволюционных операторов..................................................36

2.1.3 Взаимодействие популяций СЭА...............................................................39

2.1.4 Общая схема и параметры алгоритма........................................................47

2.1.5 Экспериментальное тестирование СЭА....................................................49

2.2 Хронологический эволюционный алгоритм ХЭА...................................50

2.2.1 Этап РНК-мира.............................................................................................50

2.2.2 Клеточный этап............................................................................................52

2.2.3 Видовой этап.................................................................................................52

2.2.4 Социальный этап..........................................................................................55

2.2.5 Параметры и особенности этапов ХЭА.....................................................55

2.2.6 Экспериментальное тестирование ХЭА....................................................56

2.3 Самоадаптирующийся эволюционный алгоритм САЭА.........................57

2.3.1 Основные параметры алгоритмов..............................................................60

2.3.2 Экспериментальное тестирование самоадаптирующихся алгоритмов.. 61

ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ.........................................................................63

ГЛАВА 3. ЗАДАЧИ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ПЛАНА..............64

3.1 Задача планирования работы IT-отдела........................................................64

3.1.1 Планирование работ IT-отдела в условиях неопределённости...............69

3.1.2 Модификации эволюционного алгоритма для решения ЗПРО...............74

3.1.3 Планирование с учётом важности работ...................................................84

3.1.4 Результаты использования ЭА для решения ЗПРО..................................88

3.2 Задача оптимизации функционирования территориально-распределенной сети.............................................................................................91

3.2.1 Критерии оценки расписаний сети.............................................................94

3.2.2 Модель ЗОФТРС........................................................................................104

3.2.3 Оптимизация функционирования сети в условиях неопределённости 109

3.2.4 Модификации эволюционного алгоритма для решения ЗОФТРС.......112

3.2.5 Результаты использование ЭА для решения ЗОФТРС..........................118

ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ.........................................................................121

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС SEA: SCHEDULING EVOLUTIONARY ALGORITHM......................................................................123

4.1 Структура и назначение программного комплекса...................................123

4.2 Вычислительный эксперимент....................................................................128

4.2.1 Задача оптимизации...................................................................................129

4.2.2 Конвейерная задача теории расписаний..................................................131

4.3 Форма просмотра событий эволюционного алгоритма............................134

ВЫВОДЫ К ЧЕТВЕРТОЙ ГЛАВЕ...................................................................138

ЗАКЛЮЧЕНИЕ...................................................................................................139

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ......................141

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.........................................142

ПРИЛОЖЕНИЕ ДОКУМЕНТЫ О ВНЕДРЕНИИ...........................................151

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Модель задачи оптимизации функционирования территориально-распределённой сети, отличительной чертой которой является формализация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Популяция Р может находиться в трех состояниях: состоянии стабильности, упадка и гипертрофии, каждое из которых определяется соотношением численности популяции и параметров алгоритма (порог упадка Т(Р) и порог

гипертрофии Г(Р))5 а также равновесием полов. Популяция находится в стабильном состоянии, если количество её особей принадлежит отрезку и отношение количества особей одного пола к количеству другого

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

исчезает). В состоянии гипертрофии часть популяции может отделиться с одним из лидеров и образовать новую популяцию.

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