Генетический алгоритм

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра САПР

Пояснительная записка

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

по дисциплине: "Прикладная теория систем"

Тема: "Генетический алгоритм"

2009

Цель работы

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

Задача:

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

В интерфейсе программы предусмотреть возможность ввода параметров:

объём популяции;

число поколений;

коэффициент скрещивания;

коэффициент мутации;

для дифференциального кроссовера коэффициенты k,c;

для задачи коммивояжёра ввод [4. .40] числа городов и их расстановку вручную и автоматически;

для биологической задачи возможность ввода названий характеристик [10.15], их значений [4. .40], значимости и веса [0.1] каждой характеристики.

Результаты работы программы должны включать:

на каждом шаге отображать номер поколения и лучшее значение фитнес-функции в этом поколении;

лучшее значение фитнес-функции за все поколения и соответствующую ей структуру особи;

для биологической задачи и задачи оптимизации функции график зависимости значения целевой функции от номера поколения;

для задачи коммивояжёра на каждом поколении графически отображать лучщий маршрут.

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

Вариант задания:

Тип задачи - коммивояжёр

Выбор пары - панмиксия

Кроссовер - двухточечный

Мутация - перестановка

Отбор - элитный

Критерий останова - количество поколений

Выходные данные – карта.

Анализ результатов моделирования на основе разработанной программы представляется в виде таблицы:

№ эксперимента	Кол-во маршрутов	Число поколений	Коэф. скрещивания	Коэф. мутации	Фитнес- функция (min)
1	100	500	0,5	0,001	3110
2	150	500	0,5	0,001	2783
3	200	500	0,5	0,001	2697
4	200	1000	0,5	0,001	3034
5	200	1500	0,5	0,001	2817
6	200	2000	0,5	0,001	3088
7	200	500	1	0,001	3282
8	200	500	1,5	0,001	3296
9	100	500	1	0,001	3334
10	100	500	0,5	0,01	3025
11	200	500	0,5	0,01	2511
12	100	500	1	0,01	2852
13	200	500	1	0,01	2749
14	100	500	0,5	0,1	3221
15	200	500	1	0,1	2497

Вывод:

Анализируя полученные результаты моделирования приходим к выводу, что оптимальным количеством маршрутов можно считать 200, число поколений, нет необходимости повторять алгоритм больше 500 раз (поколений), чтобы получить хороший результат. Также на значение фитнес-функции влияет коэффициент скрещивания: оптимальный коэффициент скрещивания - 1, коэффициент мутации также играет большую роль в моделировании генетического алгоритма, оптимальный коэффициент мутации - 0,1. Как видно из таблицы самое лучшее значение фитнес-функции, а значит самое минимальное расстояние за которое можно объехать 20 городов, получают за счет параметров, которые указаны в таблице в строке под номером 15.

Руководство пользователя.

Для того, чтобы открыть программу необходимо мышью дважды кликнуть по файлу “Коммивояжёр. exe”. Также необходимо проверить наличие графического документа под названи

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать