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 -

Ва-

Название

Интервал

Функция

ри-

фунции

ант

1

De Jong

[ 2.048,

max F (3905.93)

2

x2 )

2

(1 x1 )

2

100(x1

2.048]

2

Goldstein

[ 2, 2]

min F [1 (x1 x2 1)

2

(19 14x1

2

14x2

2

&

3x1

6x1 x2 3x2 )]

2 (18 32x1

12x12 48x2

36x1 x2 27x22 )]

Price

[30 (2x1 3x2 )

3

Branin

[ 5, 10]

min F a(x

2

bx

2

cx

d)2 e(1 f ) cos(x

) e

1

1

1

5.1

1 2

5

1

a 1, b

, c

, d 6, e 10,

f

4

8

4

Martin

&

[0, 10]

min F (x1

x2 )

2

((x1

x2

10) / 3)

2

Gaddy

5

Rosenbrock

(a)[ 1.2, 1.2]

2

x2 )

2

(1 x1 )

2

min F 100(x1

(b) [ 10, 10]

6

Rosenbrock[

-1.2, 1.2]

min F {100( xi2

xi 1 ) 2 (1 xi ) 2 }

3

i 1

7

Hyper

[-5.12, 5.12]

min F xi2

6

sphere

i 1

8

Griewangk

[-512, 512]

max F

1

10

x

2

10

x

i

i

0.1

cos

1

i 14000

i 1

i

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

- 35 -

СПИСОК ЛИТЕРАТУРЫ

1. Ярушкина Н. Г. Основы теории нечётких и гибридных систем. М.: Финансы и статистика, 2004.

2.Рассел С., Норвиг П. Искусственный интеллект: современный подход. 2- е изд.; пер. с англ. М.: Изд. дом «Вильямс», 2006.

3.Горячев А. В., Новакова Н. Е. Основы искусственного интеллекта: учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2014.

4.Горячев А. В., Кравчук Д. К., Новакова Н. Е. Многокритериальная оптимизация: теория и применение: учеб. пособие. СПб.: Изд-во СПбГЭТУ

«ЛЭТИ», 2011.

5.Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. М.: ФИЗМАТЛИТ, 2007.

6.Горячев А. В., Новакова Н. Е. Управление знаниями в распределенной информационной среде: учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ»,

2009.

7.А. А. Барсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод. Методы и модели анализа данных: OLAP и Data Mining/: – СПб.: БХВ-Петер-

бург, 2004.

8.Макконнелл Дж. Основы современных алгоритмов. 2-е изд., доп. М.: Техносфера, 2004.

9.Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. СПб.: Лань, 2010.

- 36 -

Содержание

ЛАБОРАТОРНЫЕ РАБОТЫ.........................................................................................	- 3 -
Работа 1. НЕЙРОННАЯ СЕТЬ ХЕММИНГА ...............................................................	- 3 -
Работа 2. НЕЙРОННАЯ СЕТЬ ХЕББА........................................................................	- 12 -
Работа 3. НЕЙРОННАЯ СЕТЬ ХОПФИЛДА..............................................................	- 25 -
Работа 4. НЕЙРОННАЯ СЕТЬ КОХОНЕНА ..............................................................	- 25 -
Работа 5. ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА............................	- 26 -
Работа 6. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА МОДЕЛИРОВАНИЯ
ПЕРЕМЕЩЕНИЯ БАКТЕРИЙ.....................................................................................	- 27 -
Работа 7. РЕАЛИЗАЦИЯ МЕТОДА ПЧЕЛИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ
ЗАДАЧИ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ.............................................................	- 28 -
Работа 8. ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ В ЗАДАЧАХ
ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ. РЕШЕНИЕ ЗАДАЧИ О
КОММИВОЯЖЁРЕ .......................................................................................................	- 28 -
Работа 9. РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЁРЕ С ПОМОЩЬЮ АЛГОРИТ-
МА ИМИТАЦИИ ОТЖИГА.........................................................................................	- 30 -
Работа 10. РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЁРЕ С ПОМОЩЬЮ
МУРАВЬИНОГО АЛГОРИТМА..................................................................................	- 30 -
ПРАКТИЧЕСКИЕ ЗАДАНИЯ......................................................................................	- 31 -
ИНДИВИДУАЛЬНОЕ ДОМАШНЕЕ ЗАДАНИЕ.....................................................	- 33 -
СПИСОК ЛИТЕРАТУРЫ.............................................................................................	- 35 -

Горячев Александр Вадимович,

Новакова Наталия Евгеньевна

Технологии искусственногоинтеллекта

Учебно-методическое пособие Редактор Э. К. Долгатов

——————————————————————————————————

Подписано в печать 28.12.18. Формат 60 × 84 1/16. Бумага офсетная. Печать офсетная. Гарнитура «Times New Roman». Печ. л. 2.25.

Тираж 64 экз. Заказ .

——————————————————————————————————

Издательство СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5