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

Рисунок 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г.