Представление генетических алгоритмов сетями Петри в задаче размещения

• Автор: Григорьев, Алексей Вениаминович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Казань
• Количество страниц: 171 с.

Содержание
Введение.

Глава 1. Математические модели задачи размещения

1.1. Математическая формулировка задачи размещения

1.2. Модель размещения на основе объектного подхода

1.3. Моделирование объектного подхода на сетях Петри.

1.4. Моделирование маскированного размещения сетями Петри.

Глава 2. Разработка генетических алгоритмов для задачи размещения

2.1. Генетические алгоритмы на сетях Петри

2.2. Алгоритм на оснсзе популяции квазиоптимальных решений.

2.3. Алгоритм на основе многоуровневых субпопуляций.

2.4. Сходимость алгоритмов на основе квазиоптимальных решений и многоуровневых субпопуляций
2.5. Алгоритмы вычисления составляющих функции приспособленности
Выводы.
Глава 3. Применение генетических алгоритмов в задаче составления расписания учебных занятий.
3.1. Задача составления расписания как задача размещения.
3.2. Функция приспособленности для задачи расписания
3.3. Проведение и анализ результатов эксперимента
Выводы.
Заключение.
Список использованной литературы


При размещении вручную (в некоторых задачах размещения) необходимо выполнить большую рутинную работу: поиск возможных вариантов размещения очередных требований с использованием материально-временных ресурсов, проверку соблюдения ограничений, поиск случайных ошибок в готовой схеме размещения, ее оформление на бумаге в виде различных таблиц [7]. Практически многие задачи размещения так или иначе решаются, поскольку программы и компьютерные сети работают, самолеты приземляются, поезда двигаются, занятия проводятся. Большинство этих решений уже математически описано в виде десятков и сотен моделей, реализовано программно, и все же до сих пор в них не решены задачи наилучшего размещения. Формально процесс размещения представляется следующим образом: из списка размещаемых требований по определенному принципу берется очередное требование и размещается с использованием существующих временных й материальных ресурсов. Конечно, подобная формализация не универсальна. В промышленности, транспорте, системах управления и общественной деятельности любая формализация размещения в виде математической модели и получение решения на ее основе бывают столь необходимыми, что окупаются впоследствии независимо от затраченных на это средств. В то же время, многие алгоритмы, примененные в этих сферах, весьма привлекательные на первый взгляд, оказывались бессильными при поиске наилучшего решения []. Следовательно, математическое моделирование и алгоритмизация размещения до сих пор являются актуальными проблемами исследования операций. Основным понятием задачи размещения является понятие требования. Размещение требований происходит с использованием существующих материальных и временных ресурсов. На каждую составляющую требования накладываются определенные ограничения. Каждая единица материального ресурса характеризуется наименованием, количественной характеристикой, видом, а временного - периодом, тактом, причем на материальные ресурсы накладываются определенные ограничения. Подлежащие выполнению требования определены и известны полностью. Это означает, что внешними по отношению к рассматриваемой системе пользователями заданы объем и характер требований. Известно также, каким образом выполняются эти требования и что существует по крайней мере по. Кроме этого, предполагается, что все заданные требования должны быть выполнены и ресурсы однозначно определены. В результате предварительного размещения может оказаться целесообразным изменение характеристик ресурсов (увеличение производительности оборудования, сроков размещения). Однако изучение целесообразности подобных мероприятий не входит в цели работы. Для составления математической модели задачи размещения требуется ее формализация. Например, з работе [] приведена формальная спецификация задачи размещения с несколькими типами ресурсов. К: АхМ~К), (1. К(а2,и) = (и2,з2,/)} -> их п и2 = 0, 1! ZweW, УаеА, И(а^)=:(и,$/г/1)/I Уд(д±)< Уа(а) . W=^Wl,w2# . А= {а 1, а2/. Ь={/ / . Э2, . Ъ— {т. Таблица 1. II -н О . П|_, к = 1 , . Пд . УдеС, УэбБ, I 0(ьц) = 8(9,3). Уае А, И (а, и) = {и, з, г, 1), деи} (1. Требуется найти размещение среди всех возможных, минимизирующее значение целевой функции []. С - множество ограничений к г, А, И. Необходимо оптимально разместить элементы множества Ъ , используя как минимум по одной единице ресурса из множеств А и И при условии выполнения конечного множества ограничений С. Б X Ь X О; • (1. А с А1 х Аа х Ак ; (1. И С % х Иц; (1. С с С8 х С , х Сд х Са, (1. А1,Ас. С5, С2, Сд,Са-множества ограничений на Э, Ъ, 0, А. Б с х Бк х ; (1. Ь с х Ь5; (1. С с 0, х Од/ (1. И с й х А х гдт . IА |, з=1,. А|, j=1,. И|; (1. К=>(гга, а, 1*3) ? А|, ,, щ=1,. Размещение, в котором учтены условия (1. При этом данные условия должны быть выполнены в обязательном порядке. Наилучшим будем считать размещение, которое кроме этих условий, удовлетворяет множеству всех ограничений С, отвечающих за качество размещения. Чем больше ограничений из этого множества будет удовлетворено размещением, тем качественнее оно будет.