Методичні вказівки до виконання лабораторних робіт з дисципліни " сучасний штучний інтелект" для студентів спеціальності 080403



Сторінка1/13
Дата конвертації04.02.2017
Розмір1,55 Mb.
ТипМетодичні вказівки
  1   2   3   4   5   6   7   8   9   ...   13


Міністерство освіти і науки України

Запорізький національний технічний університет



Методичні вказівки

до виконання лабораторних робіт

з дисципліни

СУЧАСНИЙ ШТУЧНИЙ ІНТЕЛЕКТ

для студентів спеціальності 8.080403

“Програмне забезпечення автоматизованих систем”

напряму підготовки 6.050103 “Програмна інженерія”

(всіх форм навчання)

2007

Методичні вказівки до виконання лабораторних робіт з дисципліни “Сучасний штучний інтелект” для студентів спеціальності 8.080403 “Програмне забезпечення автоматизованих систем” напряму підготовки 6.050103 “Програмна інженерія” (всіх форм навчання) / С.О. Субботін, А.О. Олійник. – Запоріжжя: ЗНТУ, 2007. – 62 с.




Видання підготовлено за Міжнародним проектом

Європейсько-український ступінь магістра з програмного забезпечення”



(JEP 26182 2006) за програмою “TEMPUS” Європейської комісії.

Автори: Сергій Олександрович Субботін,

кандидат технічних наук, доцент,

лауреат премії Президента України


Андрій Олександрович Олійник,

асистент


Рецензент: Г.В. Табунщик, к.т.н., доцент

Відповідальний

за випуск: А.В. Притула, к.т.н., доцент



Затверджено

вченою радою інституту

інформатики та радіоелектроніки
Протокол № 3

від 02.10.2007 р.



Затверджено

на засіданні кафедри

“Програмні засоби”
Протокол № 1

від 28.09.2007 р.




ЗМІСТ



Вступ 5

1 Лабораторна робота № 1 Методи еволюційного пошуку 6

1.1 Мета роботи 6

1.2 Основні теоретичні відомості 6

1.2.1 Генетичний пошук як метод оптимізації 6

1.2.2 Аналогія генетичних методів з поняттями генетики 7

1.2.3 Узагальнена схема роботи генетичних методів 8

1.2.4 Моделі генетичного пошуку 10

1.2.5 Ініціалізація та запуск генетичного пошуку 10

1.2.5.1 Кодування параметрів, що оптимізуються 10

1.2.5.2 Завдання цільової функції 14

1.2.5.3 Ініціалізація 15

1.2.6 Відбір 16

1.2.6.1 Пропорційний відбір 17

1.2.6.2 Відбір ранжируванням 18

1.2.6.3 Турнірний відбір 19

1.2.6.4 Відбір з використанням порогу 19

1.2.7 Схрещування 19

1.2.7.1 Вибір батьківської пари 20

1.2.7.2 Оператори схрещування 23

1.2.8 Мутація 26

1.2.8.1 Проста мутація 27

1.2.8.2 Мутація гомологічних числових хромосом 28

1.2.9 Формування нового покоління 30

1.2.10 Критерії зупинення 32

1.2.11 Генетичний пошук в пакеті Matlab 33

1.3 Завдання до роботи 34

1.4 Зміст звіту 36

1.5 Контрольні питання 36



2 Лабораторна робота №2 Статистичний аналіз результатів еволюційної оптимізації 39

2.1 Мета роботи 39

2.2 Основні теоретичні відомості 39

2.3 Завдання до роботи 41

2.4 Зміст звіту 43

2.5 Контрольні питання 44



3 Лабораторна робота №3 Комбінаторна оптимізація за допомогою еволюційних методів 47

3.1 Мета роботи 47

3.2 Основні теоретичні відомості 47

3.2.1 Оператори схрещування для негомологічних числових хромосом 48

3.2.1.1 Впорядковуючий оператор схрещування 48

3.2.1.2 Схрещування із частковим відображенням 49

3.2.1.3 Циклове схрещування 50

3.2.1.4 Жадібний оператор схрещування 50

3.2.1.5 Схрещування методом дихотомії 51

3.2.1.6 Оператор сегрегації 52

3.2.2 Оператори мутації 52

3.2.2.1 Мутація обміну 52

3.2.2.2 Інвертування 55

3.2.2.3 Транслокація, вставка та делеція 56

3.3 Завдання до роботи 57

3.4 Зміст звіту 58

3.5 Контрольні питання 59

Література 61



Вступ

Дане видання призначене для вивчення та практичного освоєння студентами усіх форм навчання основ сучасного штучного інтелекту.

Відповідно до графіка студенти перед виконанням лабораторної або самостійної роботи повинні ознайомитися з конспектом лекцій та рекомендованою літературою.

Для одержання заліку по кожній роботі студент здає викладачу цілком оформлений звіт, а також 3,5-дюймову дискету у форматі MS – DOS / Windows, перевірену на відсутність вірусів, з текстами розроблених програм, файлами програм, що виконуються, файлами даних і текстом звіту.

Звіт має містити:

– титульний аркуш;

– мету, варіант i завдання роботи;

– лаконічний опис теоретичних відомостей;

– текст програми, що обов'язково містить коментарі;

– вхідні та вихідні дані програми;

– змістовний аналіз отриманих результатів та висновки.

Звіт виконують на білому папері формату A4 (210 x 297 мм). Текст розміщують тільки з однієї сторони листа. Поля сторінки з усіх боків – 20 мм. Аркуші скріплюють за допомогою канцелярських скріпок. Для набору тексту звіту використовують редактор MS Word 97: шрифт Times New Roman, 12 пунктів. Міжрядковий інтервал: полуторний – для тексту звіту, одинарний – для листингів програм, таблиць і роздруківок даних.

Під час співбесіди студент повинний виявити знання про мету роботи, по теоретичному матеріалу, про методи виконання кожного етапу роботи, по змісту основних розділів розробленого звіту з демонстрацією результатів на конкретних прикладах. Студент повинний вміти правильно аналізувати отримані результати. Для самоперевірки при підготовці до виконання і здачі роботи студент повинний відповісти на контрольні питання, приведені наприкінці опису відповідної роботи. Загальний залік студент одержує після виконання і здачі останньої роботи.

  1. Лабораторна робота № 1
    Методи еволюційного пошуку




    1. Мета роботи


1.1.1 Вивчити основні методи еволюційного пошуку.

1.1.2 Навчитися використовувати еволюційні методи для розв’язку оптимізаційних задач.



    1. Основні теоретичні відомості


У багатьох технічних задачах актуальною є проблема знаходження глобального оптимуму цільової функції в багатомірному просторі керованих змінних. Традиційні методи багатомірної оптимізації є методами локального пошуку та сильно залежать від вибору початкової точки пошуку. Для знаходження глобального оптимуму доцільно використовувати методи еволюційного пошуку.

Еволюційні методи засновані на аналогії з природними процесами селекції та генетичними перетвореннями, і поєднують комп'ютерні методи моделювання еволюційних процесів у природних і штучних системах.

Традиційно до еволюційних методів відносять генетичні алгоритми, еволюційні стратегії, генетичне програмування та еволюційне програмування.

      1. Генетичний пошук як метод оптимізації


Генетичний пошук містить у собі групу багатомірних, стохастичних, евристичних оптимізаційних методів, вперше запропонованих Д. Холландом у 1975 р. і заснованих на ідеї еволюції за допомогою природного відбору. Генетичні методи були отримані в процесі узагальнення й імітації в штучних системах таких властивостей живої природи, як природний відбір, пристосованість до змінюваних умов середовища, спадкування нащадками життєво важливих властивостей від батьків і т.ін.

Під стандартним генетичним методом розуміють метод для вирішення оптимізаційних задач вигляду:



f (H) → min,

де f – функція пристосованості (функція придатності, цільова функція, фітнесс-функція);



H = {0; 1}L – хромосома, що містить в закодованому вигляді параметри цільової функції;

L – кількість розрядів у хромосомі.

Генетичні методи в процесі пошуку використають деяке кодування множини параметрів замість самих параметрів, тому вони можуть ефективно застосовуватися для рішення задач оптимізації, визначених як на числових множинах, так і на кінцевих множинах довільної природи.



      1. Аналогія генетичних методів з поняттями генетики


Основна концепція класичної генетики – ген (реально існуюча, незалежна, комбінуюча та розщеплюча при схрещуваннях одиниця спадковості) була введена І.Г. Менделем з метою пояснення спостережуваної статистики спадкування. Носіями генів у клітинному ядрі особини є нитковидні тіла – хромосоми (структурні елементи клітинного ядра біологічних організмів, що є носіями генів). У генетичних методах терміни “хромосома” і “особина” використаються як синоніми. Місце, що займає ген у хромосомі, називається локусом. Схематично можна уявити собі хромосому як прямолінійний відрізок, а локуси – як послідовні ділянки, на які цей відрізок розбитий. Гени приймають значення, які називаються алелями.

Дії генів проявляються в досить великих співтовариствах організмів, що схрещуються між собою. Такі співтовариства називають популяціями. Популяції характеризуються набором хромосом кожного з об'єктів, сукупність яких визначає генофонд популяції.

Таким чином, генетичні методи запозичили з біології понятійний апарат, ідею колективного пошуку екстремуму, способи представлення генетичної інформації, способи передачі генетичної інформації в послідовності поколінь (генетичні оператори), ідею про переважне розмноження найбільш пристосованих особин.

      1. Узагальнена схема роботи генетичних методів


Суть генетичного пошуку полягає в циклічній заміні однієї популяції наступною, більш пристосованою. Таким чином, популяція існує не тільки в просторі, але й у часі. Початкова популяція P0 створюється на етапі ініціалізації генетичного пошуку.

Подальша робота генетичного методу представляє собою ітераційний процес виконання генетичних операторів відбору, схрещування й мутації. Генетичні оператори необхідні для того, щоб застосувати принципи спадковості й мінливості до популяції. Генетичні оператори мають властивість імовірності, тобто вони не обов'язково застосовуються до всіх рішень, що вносить додатковий елемент невизначеності в процес пошуку рішення.

Кожне рішення (хромосома) оцінюється мірою пристосованості. Пристосованість хромосоми визначається як обчислена цільова функція. Правила відбору прагнуть залишити тільки ті рішення, де досягається оптимум цільової функції. Найбільш пристосовані хромосоми одержують можливість відтворювати нащадків за допомогою схрещування з іншими хромосомами популяції. Це призводить до появи нових хромосом, які сполучають у собі деякі характеристики, наслідувані ними від батьків. Найменш пристосовані рішення з меншою ймовірністю зможуть відтворити нащадків, у результаті чого властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції.

Схрещування найбільш пристосованих хромосом приводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. В остаточному підсумку популяція буде сходитися до оптимального рішення задачі.

Після схрещування іноді відбуваються мутації – спонтанні зміни в генах, які випадковим чином розкидають рішення по всьому простору пошуку.

У результаті схрещування й мутації розмір популяції збільшується. Однак для наступних перетворень необхідно скоротити число хромосом поточної популяції. Як правило, наступна популяція формується з нащадків, отриманих у поточній популяції в результаті схрещування й мутації, а також елітних хромосом, що володіють найкращою пристосованістю.

Узагальнений метод генетичного пошуку можна записати в такий спосіб.

Крок 1. Встановити лічильник ітерацій (часу): t = 0.

Крок 2. Згенерувати початкову популяцію хромосом P(t).

Крок 3. Обчислити функцію пристосованості для всіх хромосом у популяції f(P(t)).

Крок 4. Перевірити умови закінчення пошуку (час, число ітерацій, значення функції пристосованості і т.ін.). Якщо критерії зупину задоволені, перейти до кроку 12.

Крок 5. Збільшити лічильник ітерацій (часу): t = t + 1.

Крок 6. Вибрати частину популяції (батьківські хромосоми) для схрещування P'.

Крок 7. Схрестити обрані батьківські хромосоми P'(t).

Крок 8. Застосувати оператор мутації до хромосом P'(t).

Крок 9. Обчислити нову функцію пристосованості популяції f(P'(t)).

Крок 10. Вибрати хромосоми, що вижили, виходячи з рівня пристосованості.

Крок 11. Перейти на крок 4.

Крок 12. Кінець.

У наш час запропоновано багато різних генетичних методів, і в більшості випадків вони мало схожі на наведений генетичний метод. Із цієї причини під терміном “генетичні методи” мається на увазі досить широкий клас методів, часом мало схожих один на одного.

Використання генетичного пошуку для рішення практичних задач передбачає:

– вибір методу представлення вхідних даних для генетичного пошуку (кодування параметрів, що оптимізуються);

– визначення цільової функції, що використовується для оцінки хромосом;

– вибір оператору відбору хромосом, що будуть використані для генерації нових рішень за допомогою схрещування й мутації;

– вибір методів одержання нових рішень (операторів схрещування й мутації);

– завдання параметрів пошуку, таких як кількість особин у популяції, імовірнісні характеристики генетичних операторів, максимально припустима кількість ітерацій генетичного пошуку, кількість елітних особин при використанні стратегії елітизму.




      1. Каталог: subject -> mag SShI
        subject -> «Правова освіта і правове виховання»
        subject -> Тема. Проблеми мирного врегулювання з колишніми союзниками Німеччини в Європі
        mag SShI -> Робоча навчальна програма
        subject -> Робоча програма дисципліни "Експертні системи " для студентів спеціальності
        subject -> Міністерство освіти і науки України Запорізький національний технічний університет Інститут інформатики та радіоелектроніки
        subject -> Робоча програма дисципліни "нейроінформатика" для студентів магістратури спеціальності
        subject -> Міністерство освіти і науки України Запорізький національний технічний університет Інститут інформатики та радіоелектроніки
        subject -> Міністерство освіти і науки України Запорізький національний технічний університет Інститут інформатики та радіоелектроніки
        subject -> Міністерство освіти і науки України Запорізький національний технічний університет Інститут інформатики та радіоелектроніки


        Поділіться з Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   13


База даних захищена авторським правом ©refos.in.ua 2019
звернутися до адміністрації

увійти | реєстрація
    Головна сторінка


завантажити матеріал