Многокритериальная задача о раскраске на предфрактальных графах имеет широкий диапазон приложений. К этой задаче сводятся задачи о размещении (загрузке), распределении ресурсов, составлении графиков осмотра (проверки) в социально-экономических системах со сложной многоэлементной изменяющейся структурой. Фрактальные (предфрактальные) графы моделируют класс систем с изменяющейся структурой.
Задача составления расписаний является одной из наиболее распространённых задач, решаемых каждым человеком (осознанно или нет) практически ежедневно. В общей постановке она представляет собой процесс распределения некоторого конечного набора событий во времени в условиях ресурсных и других ограничений. Таким образом, простой человек, планируя рабочий день, и диспетчер, составляя расписание занятий в вузе или график работ на предприятии, решают задачу составления расписания. Но если в первом случае задача может решаться интуитивно на основе жизненного опыта, то во втором она может оказаться непосильно сложной даже для группы специалистов. Такая ситуация возникает из-за вовлечённости в расписание большого количества людей со своими интересами и требованиями, удовлетворение которых часто приводит к конфликтным ситуациям.
Поэтому с развитием вычислительных технологий ведутся разработки автоматизированных систем составления расписания. В некоторых частных случаях удалось разработать алгоритмы, способные найти решение за приемлемое время. В то же время большинство реальных задач составления расписания относятся к классу NP-полных. Это делает разработку алгоритма, способного решить их за допустимое время, действительно сложной задачей, даже если соответствующую предметную задачу можно поставить как однокритериальную. Ситуация существенно усугубляется тем, что большинство реальных задач составления расписаний многокритериальны.
Различные задачи составления расписаний могут иметь много общего. Например, в задачах составления расписания занятий в вузе и графика работ на предприятии можно провести следующие аналогии между ресурсами: группы студентов и служащие, преподаватели и смены, аудитория и квалификация служащих, предметы и работодатели . Поэтому методы, разработанные для одного подкласса задач, часто можно перенести на другие.
Задачу составления расписания можно рассматривать как задачу раскраски графа. Напомним, что задачей раскраски графа называют поиск хроматического числа графа или, другими словами, поиск минимального числа цветов, необходимых для раскраски вершин некоторого графа с использованием для каждой пары соседних вершин различных цветов. Сама задача поиска хроматического числа представляет собой NP-полную задачу, для решения которой в большинстве случаев используются различные жадные алгоритмы.
Для постановки задачи составления расписания как задачи раскраски графа строится граф, в котором каждая вершина представляет собой запланированное учебным планом занятие. В том случае, если между какими-то двумя вершинами возможны конфликты, например, оба занятия проводятся в одной аудитории или с одним преподавателем, то они соединяются ребром. Это эквивалентно запрету одновременного проведения этих занятий. Тогда задача составления расписания представляется как минимизация числа цветов, необходимых для раскраски графа. Каждый цвет соответствует одному периоду расписания.
Применение этого подхода для решения реальных задач, по-видимому, малоэффективно. В то же время, задача раскраски графа при составлении расписаний может оказаться полезной в случае её комбинации с другими алгоритмами.
Генетические алгоритмы это стохастические эвристические оптимизационные методы, основная идея которых взята из теории эволюционного развития видов. Основным механизмом эволюции является естественный отбор, суть которого состоит в том, что более приспособленные особи имеют больше шансов на выживание и размножение и, следовательно, приносят больше потомства, чем менее приспособленные особи. При этом благодаря передаче генетической информации потомки наследуют от родителей основные их качества. Носителями генетической информации индивидуума выступают молекулы ДНК. При размножении животных происходит слияние двух родительских половых клеток. Их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия кроссинговер. При кроссинговере ДНК предков делятся на две части, а затем обмениваются своими половинками. При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде и при этом произойдёт скачкообразное повышение приспособленности вида.
Первым шагом при разработке математической модели, основанной на генетическом алгоритме, является разработка структуры хромосомы, в которой будет храниться решение. Выбранная структура должна учитывать все особенности и ограничения, предъявляемые к искомому решению, а также то, что от её выбора напрямую зависят реализации алгоритмов кроссинговера и мутации. В конечном счёте, выбор хромосомы влияет не только на скорость, но и на сходимость алгоритма вообще.
Структура хромосомы удобна тем, что уже на этапе задания начальных данных можно исключить заведомо неудачные решения, заблокировав соответствующие ячейки.
На следующем шаге алгоритма создаётся начальная популяция, размер которой зависит от размерности задачи и составляет обычно несколько сотен решений.
Для организации оптимизирующего процесса необходимо создать направляющую силу развития популяции. В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции. Обычно в качестве её используется аддитивный показатель оптимальности, основанный на штрафах, устанавливаемых каждому решению за какой либо неудобный. Преимуществом такого выбора является возможность настройки алгоритма под конкретную задачу путём варьирования коэффициентов и, тем самым, изменения приоритетов при поиске оптимального решения.
Таким образом, поместив начальную популяцию в созданную нами искусственную среду и реализовав процессы селекции, кроссинговера и мутации, мы получим итерационный алгоритм поиска оптимального решения, на каждой итерации которого выполняются следующие действия:
1. Каждая особь популяции оценивается с помощью фитнес функции.
2. Лучшие решения копируются в новую популяцию без изменения. Такой принцип (принцип элитизма) предотвращает потери лучших решений и обеспечивает повышенную сходимость алгоритма.
3. На основе пропорционального отбора из текущей популяции выбираются два решения, которые подвергаются рекомбинации. Для этого хромосомы родителей обмениваются соответствующими участками.
4. Если новая популяция сформирована, то старая удаляется, после чего переходим к этапу 1. В противном случае переходим к этапу 3.
Рассмотренный алгоритм является не только устойчивым к локальным минимумам, но и благодаря внутреннему параллелизму, выраженному в работе не с отдельными решениями, а с целыми классами решений, обеспечивает относительно быстрый поиск оптимального решения.
Методы исследования в своей основе используют итерационную технику улучшения результатов. В течение одной итерации они ищут решение, лучшее в окрестностях данного. Если такое решение найдено, оно становится текущими начинается новая итерация. Это продолжается до тех пор, пока прирост целевой функции не уменьшится практически до нуля или не выполнится заданное количество итераций. Очевидно, что такие методы ориентированы на поиск только локальных оптимумов, причём положение найденного оптимума зависит от стартовой точки. Глобальный же оптимум может быть найден только случайно. Для повышения вероятности нахождения глобального оптимума используется множественный эксперимент с различными начальными точками, что существенно увеличивает время поиска.
В связи с этим представляет интерес разработка алгоритмов, сохраняющих преимущества описанных методов и свободных от указанного недостатка. К таким алгоритмам относятся генетические алгоритмы.
Литература:
1. Кононова Наталия Владимировна. Многокритериальная задача о раскраске на предфрактальных графах. Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 05.13.18 — математическое моделирование, численные методы и комплексы программ. — Ставрополь: Ставропольский государственный университет, 2008.
