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

Лабораторная работа

по курсу 

"Интеллектуальные системы":

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

Выполнил 

студент группы ИУ5-81

Баришок Н.И.

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

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

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

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

Блок-схема генетического алгоритма

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

Оценивание приспособленности - расчет функции приспособленности для каждой хромосомы этой популяции (чем больше значение функции, тем "выше" качество хромосом).

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

Селекция хромосом - выбор хромосом для участия создания потомков. Существуют различные методы селекции, в данном случае был выбран турнирный метод.

Применение генетических операторов, в данном алгоритме применяются 2 типа операторов: оператор скрещивания и оператор мутации. Виды скрещивания и мутации бывают различными.

Выбор новой популяции - хромосомы, которые дошли до данного этапа формируют новую родительскую популяцию.

Пример разработанной программы:

• скриншоты

начальный экран

заполненная матрица расстояний между компьютерами

Параметры алгоритма, выбранные инициализированные особи 

Результаты алгоритма на 50й шаг

Итоговый результат

Также можно скачать проект с решением

При выполнении ЛР были использованы следующие источники:

-"интеллектуальная" часть:

+Рутковская Д., Пилиньский М., Рутковский Л. - Нейронные сети, генетические алгоритмы и нечеткие системы (2006)

+конспекты лекций

-программная часть:

+msdn.microsoft.com

+stackoverflow.com

+статьи по теме: mvvm-pattern in wpf

Описание разработки:

-язык программирования: C#

-техннология: WPF

-среда разработки: VS 2010

* для корректной работы прораммы на ПК необходимо установить:

-.net frameork v4.0

-entity framework v4.2