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

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

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

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

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

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

кафедра САПР

 

 

 

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

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

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

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

 

 

 

Выполнила:

Студентка гр. А-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 Интерфейс программы

 

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

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

 

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

Рисунок 3 Графовое решение

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

 

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

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

 

 

Таблица 1 

Результаты экспериментальных  исследований

Вероятность		Результат – ЦФ на итерации			Лучшее значение ЦФ
Кроссинговера	Мутации	10	20	50
0.5	0.5	525	721	515	587
0.7	0.5	784	758	665	735,6
0.5	0.7	800	764	575	713
0.7	0.7	778	761	634	724,3
0.9	0.9	641	743	726	703,3

 

 

 

 

 

 

 

 

 

 

Анализируя полученные результаты можно прийти к выводу, что наилучшими значениями вероятностей оказались {0.5, 0.5}.

2. Увеличим значения входных данных.

Допустим,  количество групп  людей и рабочих мест  100,  мощность начальной популяции - 100, количество итераций – 50.

 

    Таблица 2                                                       

Результаты экспериментальных  исследований

Вероятность		Результат – ЦФ  на итерации			Среднее значение
Кроссинговера	Мутации	10	20	50
0.5	0.5	754	658	725	712,3333
0.7	0.5	721	752	712	728,3333
0.5	0.7	698	525	614	612,3333
0.7	0.7	745	652	744	713,6667
0.9	0.9	698	740	721	719,6667

 

При таком наборе начальных  условий достаточно хороший результат  был получен и при вероятностях {0.5,0.7}.

3. Теперь возьмем достаточно большой размер начальной популяции

Допустим,  количество групп  людей и рабочих мест  150,  мощность начальной популяции - 2000, количество итераций – 50.

Таблица 3                                                         

Результаты экспериментальных  исследований

Вероятность		Результат – ЦФ  на итерации			Среднее значение
Кроссинговера	Мутации	10	20	50
0.5	0.5	4521	4152	5424	4699
0.7	0.5	3698	4165	2888	3583,667
0.5	0.7	3254	2547	2145	2648,667
0.7	0.7	3989	5844	2999	4277,333
0.9	0.9	3678	2989	2664	3110,333

При таком наборе начальных  условий достаточно хороший результат  был получен и при вероятностях {0.5,0.7}.

После проведения опытов, один из них я представила в виде графика зависимости значения ЦФ от итерации.

Рисунок 4

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

 

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

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

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

 

 

 

 

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

 

1. Л.А. Гладков, В.М. Курейчик, В.В. Курейчик. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004г.
2. Курейчик В.М. Генетические алгоритмы и их применение: Монография. – Таганрог: Изд-во ВГТУ, 2002г.
3. Хорстман Г, Корнелл Дж. JAVA. Библиотека профессионала. – Москва: Изд-во «Вильямс», 2007г.
4. Курейчик В.М . Генетические алгоритмы решения экстремальных задач. – Воронеж: Изд-во ВГТУ, 1995г.