Задача о назначениях

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В ГОРОДЕ ТАГАНРОГЕ

кафедра САПР

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

Дисциплина: «Эволюционное моделирование и генетические алгоритмы»

Тема: «Задача о назначениях»

 

 

 

Выполнила:

Студентка гр. А-69

Журавлева В.А.

 

Проверил:

Запорожец Д. Ю.

 

 

 

 

 

 

 

 

 

 

Таганрог 2012

Содержание

1 Введение. 3

2 Анализ и  постановка задачи 5

3 Разработка  алгоритма 7

3.1 Кодирование  решения 8

3.2 Генерация  начальной популяции 9

3.3 Оператор  кроссинговера 9

3.4 Оператор  мутации 10

4 Разработка  программного продукта 12

5 Экспериментальное  исследование результатов 13

6 Заключение. 16

7 Список использованной  литературы 17

 

 

 

 

 

 

1 Введение.

Генетические алгоритмы (ГА) – это новая область исследований, которая появилась в результате работ Д. Холланда и его коллег. ГА, описанные Д. Холландом, заимствуют в своей терминологии многое из естественной генетики. Впервые ГА были применены  к таким научным проблемам, как  распознавание образов и оптимизация. Генетический алгоритм представляет собой  адаптивный поисковый метод, который  основан на селекции лучших элементов  в популяции, подобно эволюционной теории Ч. Дарвина [1]. То есть, генетический алгоритм позволяет получать хорошие решения за счет его следующих преимуществ:

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

2) в аспекте преобразования решение рассматривается как некоторая закодированная структура, а не как совокупность параметров. Это позволяет в некоторых случаях увеличить процесс обработки данных, т.е. быстродействие оптимизационного поиска;

3) для оценки пригодности решения наряду с использованием целевой функции дополнительно моделируются правила выживания в исследуемом множестве. Эти правила повышают разнообразие множества решений, которое необходимо для выполнения пункта “1”;

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

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

В отличие от остальных  оптимизационных методов ГА более  приспособлены для нахождения новых  решений за счет объединения квазиоптимальных решений из разных популяций и  обладают возможностями для выхода из локальных оптимумов.

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

В данной работе необходимо решить задачу о назначениях.

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

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

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

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

Для практической реализации алгоритма было разработано программное  обеспечение на языке программирования JAVA.

2 Анализ и постановка задачи

Имеется m групп людей численностью a₁, a₂, …, a_m, которые должны выполнять n видов работ объёмом b₁, b₂, …, b_n.

Известна оплата труда для  каждой i-й группы людей при выполнении каждого j-го вида работ c_ij, i = 1, 2, …, m, j = 1, 2, …, n.

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

    Математическая модель данной задачи выглядит следующим образом:

 

 

 

 

 

   Где: x_ij – число людей i – ой группы, занятых j – м видом работ.    

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

 

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

 

3 Разработка алгоритма

 

Блок схема алгоритма  представлена на рисунке 1.

 

 

 

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

 

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

3.1 Кодирование решения

 

Входным данным является матрица размером n×m (n=m).

Рассмотрим пример для  наглядности.

 

Соответственно в строках  – группы рабочих, в столбцах –  виды работ.

Теперь создаем хромосому:

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

 

 

А теперь создаем новый  массив для расчета целевой функции. Она составляется следующим образом: берем значение из ячейки из CH (1), затем находим в первой строке M столбец 1 и на пересечении находим значение и записываем его в MForCF.

 

Легко определить, что максимально возможный и целесообразный размер популяции равен: n²

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

3.2 Генерация начальной популяции

 

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

Процесс генерации новых  решений является ключевым звеном в  механизме ГА. Выделим два основных способа генерации новых решений:

1) путем перекомпоновки двух старых (родительских) решений;

2) путем случайной перестройки НИ отдельных индивидов.

Первый способ в механизмах ГА называется оператором кроссинговера (скрещивания), второй - оператором мутации. Рассмотрим подробнее основные генетические операторы.

3.3 Оператор кроссинговера

 

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

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

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

Реализация кроссинговера проста:

1) Выбирается точка разрыва

2) Далее происходит обмен  участками до точки разрыва;

3) После точки разрыва  происходит пошаговое добавление  нового гена хромосомы. 

Пример: пусть l= 10, а точка  разреза установлена после 5-го элемента

А : {0, 2, 1, 3, 4 | 6, 5, 6, 7, 8, 9}         А’: {0, 2, 1, 3, 4 | 0, 2, 7, 9, 8}

B : {3, 4, 1, 6 , 5 | 0, 2, 7, 9, 8}            B’: {3, 4, 1, 6 , 5 | 6, 5, 6, 7, 8, 9}

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

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

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

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

 3.4 Оператор мутации

 

Оператор мутации –  это языковая конструкция, позволяющая  на основе преобразования родительской хромосомы (или ее части) создавать  хромосому потомка [1].

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

То есть мутация – это  генетическое изменение, приводящее к  качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или  линейности. Генные мутации на молекулярном уровне – результат различных  повреждений в молекулах ДНК. В пределах одного гена за одно поколение  обычно встречаются единичные повреждения, редко – большие. Результатом  этого могут быть гибель клетки, изменения характера индивидуального  развития, изменение признаков и  т.д. Термин “мутация” охватывает все скачкообразные наследственные изменения. В зависимости от характера изменений, возникающих в генетическом материале, выделяют следующие типы мутаций:

• точечные;
• хромосомные перестройки;
• инверсии.

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

 

4 Разработка  программного продукта

 

Алгоритм, описанный выше, был реализован на языке Java, в среде NetBeans 6.8.

На рисунке 2 представлен интерфейс программы. Данные работы алгоритма отображены в консоли.

Рисунок 2 Интерфейс программы

 

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

• Количество работников и рабочих мест;
• Размер начальной популяции;
• Количество генераций;
• Вероятность кроссинговера и мутации.

 

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