Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
Пояснительная записка
к курсовой работе
по дисциплине: "Прикладная теория систем"
Тема: "Генетический алгоритм"
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 раз (поколений), чтобы получить хороший результат. ............
