CLAIM – научно-образовательный кластер
 |
|
|
|
|
|
Учебный курс "Интеллектуальные системы"
Лабораторная работа № 4.
Решение задач с помощью генетических алгоритмов
1. Цель работы.
Ознакомиться с подходом к решению оптимизационных задач с помощью генетических алгоритмов (ГА).
2. Порядок выполнения работы.
2.1. Изучить теоретическое введение.
2.2. Последовательно выполнить все задания к лабораторной работе.
2.3. Проверить правильность выполнения заданий не менее чем на пяти примерах.
2.4. Оформить отчет по лабораторной работе.
3. Задания к лабораторной работе
3.1. В рамках лабораторной работы необходимо разработать компьютерную программу, которая осуществляет поиск кратчайшего пути для информационного пакета (сообщения) в компьютерной сети с помощью генетических алгоритмов.
3.2. Для проведения серии экспериментов программа должна позволять пользователю задавать топологию сети (пропускные способности каналов связи), содержащей не менее 10 компьютеров (серверов), а также указывать компьютер-отправитель и компьютер-получатель. На экране должны отображаться все представители (хромосомы) одного поколения до и после применения каждого оператора (скрещивания, селекции, редукции и мутации). Переход к следующему поколению должен осуществляться при нажатии соответствующей кнопки или в автоматическом режиме.
3.3. Рекомендации.
- Рекомендуется в качестве хромосомы выбрать постоянную по длине последовательность вершин или дуг. Длину можно выбрать произвольную, но не меньше, чем N–2, где N –общее количество компьютеров в сети.
- Для упрощения расчетов граф сети лучше сделать полносвязанным (каждая пара вершина имеет связь). Для обозначения отсутствия связи (соединения) нужно выбрать очень большое значение веса дуги, а для петли (дуги, соединяющей вершину с самой собой) – значение веса равное 0. Такой подход позволит искать пути, которые по длине меньше, чем размер хромосомы.
- Если в качестве хромосомы используется последовательность вершин (узлов сети), то необходимо либо исключить первую и последнюю вершину (т.е. задавать только вершины пути), либо не изменять в результате применения генетических операторов первую и последнюю вершины, либо реализовать направленный оператор мутации, который всегда устанавливает заданные на входе вершины, соответствующие компьютеру-отправителю и компьютеру-получателю.
- Допускается использование в качестве генов числа в десятеричной системы. В этом случае рекомендуется количество серверов брать равное 10 (номера 0-9). Если используется битовая строка, то для удобства лучше выбрать количество серверов равное 2n (16, 32, 64 и т.д.). Это позволит избежать формирования в результате скрещивания и мутации несуществующих номеров вершин (узлов, серверов).
- Если в исходной популяции не представлены все возможные вершины (гены), то они могут появиться только в результате мутации, поэтому рекомендуется в начальной выборке представить весь генофонд.
- Если выбранный алгоритм скрещивания меняет только правую (левую) часть хромосомы или только 4 гена из 10, то его эффективность невысока (т.к. часть генов не будет изменяться), и единственная надежда на алгоритм мутации и удачные исходные данные.
4. Содержание отчета
4.1. Название и цель работы
4.2. Задание
4.3. Краткое описание предметной области и выбранной задачи
4.4. Блок-схема с пояснениями выбранного ГА и каждого оператора в отдельности
4.5. Протоколы проведенных экспериментов
4.6. Выводы и рекомендации по использованию разработанных ГА.
4.7. См. также требования к оформлению электронных отчетов.
© НОК CLAIM. Замечания, вопросы и сведения об ошибках просим сообщать в форуме или присылать администратору сайта.