Материал: Sb97955

-30 -

6.Листинг программы с детальными комментариями. Программа

должна быть реализована в виде Windows Forms или WPF-приложения на языке С#.

7.Результаты тестирования программы.

8.Выводы к лабораторной работе.

Работа 9. РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЁРЕ С ПОМОЩЬЮ АЛГОРИТМА ИМИТАЦИИ ОТЖИГА

Цель работы – исследование особенностей решения задачи о коммивояжёре с помощью алгоритма имитации отжига.

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

1.Формализовать задачу о коммивояжёре с помощью алгоритма имитации отжига.

2.Подготовить контрольный пример, используя взвешенный орграф (рисунок).

3.Найти кратчайший гамильтонов цикл.

4.Сравнить решение задачи о коммивояжёре с помощью алгоритма ближайшего соседа.

Содержание отчёта для реализации алгоритма имитации отжига аналогично содержанию отчёта работы 8.

Работа 10. РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЁРЕ С ПОМОЩЬЮ МУРАВЬИНОГО АЛГОРИТМА

Цель работы – исследование особенностей решения задачи о коммивояжёре с помощью муравьиного алгоритма.

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

1.Формализовать задачу о коммивояжёре с помощью муравьиного алгоритма.

2.Подготовить контрольный пример, используя взвешенный орграф.

3.Найти кратчайший гамильтонов цикл.

4.Сравнить решение задачи о коммивояжере с помощью муравьиного алгоритма.

Содержание отчёта для реализации муравьиного алгоритма аналогично содержанию отчёта работы 8.

- 31 -

ПРАКТИЧЕСКИЕ ЗАДАНИЯ Занятие 1. Изучение средств представления знаний и механизмов

управления логическим выводом

Цель задания – исследование языков представления знаний и механизмов логического вывода.

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

1.Формализовать знания в выбранной и согласованной с преподавателем предметной области.

2.Представить описание предметной области с помощью семантической сети, фреймов, правил продукций [6].

3.Описать механизм логического вывода.

4.Сравнить полученные в пп. 2 и 3 результаты.

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

1.Цель задания.

2.Краткое описание языков представления знаний и механизмов логического вывода на основании материала лекций, книг [6] и учебного пособия [2].

3.Описание схемы представления знаний для формализации предметной области.

4.Выводы к практическому заданию.

Занятие 2. Решение задачи с применением нечёткой логики. Исследование методов выбора альтернатив в нечёткой среде.

Цель задания – изучение нечёткой логики.

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

1.Разработать программу, управляющую нечёткими правилами [6].

Программа должна имитировать действия робота, обходящего препятствия. Робот должен двигаться по полю, разбитому на клетки ( m n клеток, где m

–длина Вашего имени, а n – фамилии); в эти клетки помещаются препятствия. Размер робота устанавливается чуть меньше размера клетки.

2.Подробно описать используемые правила.

3.Добиться того, чтобы робот проходил в коридоры шириной в одну клетку и при этом не испытывал колебаний.

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

1.Цель работы.

2.Детальное пошаговое описание алгоритма.

3.Детальное описание программной реализации.

- 32 -

4. Выводы по заданию.

Занятие 3. Реализация вероятностных алгоритмов

Цель задания – исследование особенностей вероятностных алгоритмов для решения задач оптимизации.

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

1.Изучить особенности вероятностных алгоритмов.

2.Написать программу поиска минимума функции, выбрав вариант тестовой функции из таблицы на с.26-27.

3.Протестировать программу на выбранной тестовой функции.

4.Результат моделирования сохранить в файле.

5.Написать отчёт.

Содержание отчёта для реализации вероятностных алгоритмов аналогично содержанию отчёта работы 8.

Занятие 4. Решение задач интеллектуальной раскопки данных

Цель задания – исследование алгоритмов Data Mining.

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

1.Изучить особенности алгоритмов Data Mining [7]. Выбрать алгоритм

всоответствии с номером варианта.

2.Написать программу, реализующую алгоритм Data Mining.

3.Протестировать программу на основе подготовленной выборки дан-

ных.

4.Результат работы программы сохранить в файле.

5.Написать отчёт.

Содержание отчёта для реализации алгоритма Data Mining аналогично содержанию отчёта лабораторной работы 8.

Занятие 5. Исследование БСД

Цель задания – исследование байесовских сетей доверия (БСД).

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

1.Формализовать знания в выбранной и согласованной с преподавателем предметной области.

2.Представить описание предметной области с помощью БСД [6].

3.Описать механизм обработки данных в БСД.

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

1. Цель задания.

-33 -

2.Краткое описание БСД на основании материала лекций, книг [2] и

учебного пособия [6].

3.Описание схемы представления знаний для формализации предметной области.

4.Выводы по заданию.

ИНДИВИДУАЛЬНОЕ ДОМАШНЕЕ ЗАДАНИЕ

В каждом задании указываются 2 комбинаторные задачи оптимизации (например, поиск кратчайшего пути на графе, задача о коммивояжёре, задача о рюкзаке и т. п.), несколько алгоритмов поискового искусственного интеллекта (файл variants-v5.doc) и номер варианта тестовой функции (тестовые функции в отдельном файле).

1.Необходимо кратко описать эти задачи и способы их решения.

2.Необходимо представить реферат всех алгоритмов из заданного списка. Если для решения задачи существует классический способ решения (например, метод ветвей и границ, алгоритм Дейкстры, венгерский алгоритм и т. п.), описать и его [8].

3.Из списка алгоритмов априори выбрать по 2 алгоритма, наиболее подходящих для решения задач дискретной оптимизации, и 2 алгоритма поиска оптимума указанной функции [9]. Всего должно быть реализовано 6 алгоритмов: по 2 для каждой задачи дискретной оптимизации и 2 для поиска минимума (максимума) функции.

4.Программно реализовать решение задач для выбранных алгоритмов и классическое решение.

5.Подробно описать решение задач с помощью выбранных алгоритмов. Сравнить полученные результаты с решением этих задач классическими методами решения.

6.Для работы с функцией должен быть использован парсер. Программа должна обеспечивать возможность варьирования параметров.

7.Реализация программы должна быть выполнена на языке C#. Пользовательский интерфейс Windows Forms или WPF.

Тестовые функции представлены в таблице.

- 34 -

Порядок выдачи, выполнения и оценки индивидуального домашнего задания определяется методикой текущего контроля.