Учебный курс "Интеллектуальные системы" > Практика > Лабораторные работы
it-claim.ru

GA-1: Решение оптимизационных задач с помощью генетических алгоритмов

Краткое описание
Разработка программы, которая осуществляет поиск кратчайшего пути для информационного пакета (сообщения) в компьютерной сети с помощью генетических алгоритмов.
1. Цель работы
Ознакомиться с подходом и приобрести практический навык решения оптимизационных задач с помощью генетических алгоритмов (ГА)

2.

Порядок выполнения работы

  • Изучить теоретическое введение.
  • Самостоятельно разработать компьютерную программу (среда разработки выбирается студентом самостоятельно).
  • Провести серию из 5+ испытаний для изучения принципов работы ГА.
  • Оформить отчет по лабораторной работе.
3.

Требования к функциональности компьютерной программы

  • Возможность задания топологии сети с указанием ее размерности и пропускной способностью каналов.
  • Настройки работы генетического алгоритма: размер популяции, количество поколений, варианты кроссовера, вероятность мутации и др.
  • Указание исходных данных (компьютер-отправитель и компьютер-получатель) и автоматическое заполнение исходных данные топологии сети.
  • Два режима работы:
    • пошаговый - на экране должны отображаться все представители (хромосомы) одного поколения до и после применения каждого оператора (скрещивания, селекции, редукции и мутации).
    • циклический - на экране должны отражаться только агрегированные данные по каждому поколению и итоговый набор хромосом.
  • На одной из экранных форм должны быть указаны ФИО и e-mail автора приложения, ссылка на учебный курс и год разработки. Эти данные должны быть продублированы в тексте программы (каждого программного модуля).
  • Дополнительно необходимо реализовать возможность динамического изменения исходных данных (матрицы связанности графа) во время пошагового режима работы алгоритма.

 

4.

Рекомендации по реализации

  • Рекомендуется в качестве хромосомы выбрать постоянную по длине последовательность вершин или дуг. Длину можно выбрать произвольную, но не меньше, чем N–2, где N –общее количество компьютеров в сети.
  • Для упрощения расчетов граф сети лучше сделать полносвязанным (каждая пара вершина имеет связь). Для обозначения отсутствия связи (соединения) нужно выбрать очень большое значение веса дуги, а для петли (дуги, соединяющей вершину с самой собой) – значение веса равное 0. Такой подход позволит искать пути, которые по длине меньше, чем размер хромосомы.
  • Если в качестве хромосомы используется последовательность вершин (узлов сети), то необходимо либо исключить первую и последнюю вершину (т.е. задавать только вершины пути), либо не изменять их в результате применения генетических операторов. Можно также реализовать направленный оператор мутации, который всегда устанавливает заданные на входе вершины, соответствующие компьютеру-отправителю и компьютеру-получателю.
  • Допускается использование в качестве генов букв или чисел в десятеричной системе. Если используется битовая строка, то для удобства лучше выбрать количество серверов равное 2n (16, 32, 64 и т.д.). Это позволит избежать формирования в результате скрещивания и мутации несуществующих номеров вершин (узлов, серверов).
  • Если в исходной популяции не представлены все возможные вершины (гены), то они могут появиться только в результате мутации, поэтому рекомендуется в начальной выборке представить весь генофонд.
  • Если выбранный алгоритм скрещивания меняет только правую (левую) часть хромосомы или только 4 гена из 10, то его эффективность невысока (т.к. часть генов не будет изменяться), и единственная надежда - на алгоритм мутации и удачные исходные данные.
  • Стоит также помнить, что повторяющиеся (идентичные) хромосомы лучше исключать (удалять, мутировать) на начальных этапах. Если размер популяции фиксированный, то это может быть неизбежным при сходимости алгоритма и вырождения популяции.

 

5.

Содержание отчета

  • Название и цель работы
  • Задание, краткое описание предметной области и выбранной задачи
  • Блок-схема с пояснениями реализованного ГА и каждого оператора в отдельности
  • Протоколы проведенных экспериментов (5+), представленные в форме графиков (допускаются скриншоты в случае программной реализации эту функциональности)
  • Выводы и рекомендации по использованию разработанных ГА
6. Дополнительная функциональность
  • Графическая визуализация результатов обучения
1+
Консультация в форуме  
Лабораторные работы
(старая версия)
Практические упражнения
Требования к оформлению электронных отчетов  
Учебный проект в области ИИ
Статьи и кейсы студентов
Серебряков А.М. Пример реализации и исследование эффективности ГА
Пример лабораторной работы
(по требованиям 2005 г.)
Дополнительные лабораторные работы
GA-2: Обучение нейронной сети с помощью генетических алгоритмов
GA-3: Сравнение ГА с другими методами поиска решения
GA-4: Решение задачи коммивояжера с помощью ГА
GA-5: Исследование генетических операторов
По согласованию можно выполнить лабораторные работы, представленные в учебном пособии [Гладков, 2004].
Дополнительная функциональность
Графическая визуализация результатов обучения 1+

 

 

 

© НОК CLAIM. Замечания, вопросы и сведения об ошибках просим сообщать в форуме или присылать администратору сайта.
OZON.ru Rambler's Top100 Раздел создан при поддержке гранта Благотворительного фонда В.Потанина