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

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

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

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

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

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

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

• Название и цель работы
• Задание, краткое описание предметной области и выбранной задачи
• Блок-схема с пояснениями реализованного ГА и каждого оператора в отдельности
• Протоколы проведенных экспериментов (5+), представленные в форме графиков (допускаются скриншоты в случае программной реализации эту функциональности)
• Выводы и рекомендации по использованию разработанных ГА

• Графическая визуализация результатов обучения