Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Тернопільський національний економічний університет
Інститут:
Не вказано
Факультет:
Факультет комп’ютерних інформаційних технологій
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки
Предмет:
Інтелектуальний аналіз даних
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ КОМП’ЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Кафедра комп’ютерних наук
МЕТОДИЧНІ ВКАЗІВКИ
ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
з дисципліни
"ІНТЕЛЕКТУАЛЬНИЙ АНАЛІЗ ДАНИХ”
для студентів спеціальності 6.080400
„Програмне забезпечення автоматизованих систем”
Тернопіль-2010
Л.І.Гончар, В.І. Манжула. // Методичні вказівки до виконання лабораторних робіт з дисципліни ”Інтелектуальний аналіз даних” для студентів напрямку „Комп’ютерні науки”.-Тернопіль, 2010.
Укладачі: Гончар Людмила Іванівна, доцент кафедри КН, ТНЕУ
Манжула Володимир Іванович, ст.. викладач кафедри КН, ТНЕУ
Відповідальний за випуск: Дивак Микола Петрович, д.т.н., професор,
завідувач кафедри КН, ТНЕУ
Шпак Володимир Богданович,
інженер кафедри КН, ТНЕУ
Рецензенти: завідувач кафедри Безпеки інформаційних технологій
ТНЕУ, д.т.н., професор Карпінський М.П.
доцент кафедри Біотехнічних систем Тернопільського
національного технічного університету імені І.Пулюя,
к.т.н., доцент Шадріна Г.М.
Затверджено на засіданні кафедри комп’ютерних наук ТНЕУ,
Протокол № від лютого 2010 р.
ЗМІСТ
ВСТУП ...........................................................................................................................................4
I. Генетичні алгоритми......................................................................................................5
1.1. Генетичні успадкування — концептуа льні засади генетичних алгоритмів.......................5
1.2. Загальна схема генетичних алгоритмів.................................................................................6
1.3. Доступне програмне забезпечення генетичних алгоритмів ...............................................9
Лабораторна робота № 1 …………………………………………………………………… 10
II. Доступне програмне забезпечення дейтамайнінгу POLYANALYST……………..29
Лабораторна робота № 2 ………………………………………………………………………29
ЛІТЕРАТУРА ..............................................................................................................................44
.
ВСТУП
Засоби сучасної інформаційної технології в останній час уможливили накопичення і зберігання великих обсягів даних про бізнесові процеси. Ці дані можуть знаходитися в корпоративних базах або сховищах даних. Вони містять важливі закономірності і зв’язки між системними характеристиками, які можуть бути використані для прийняття обгрунтованих управлінських рішень. Наразі виникла проблема розробки методів відкриття таких закономірностей, про існування яких користувачі можуть і не знати. Проте традиційний аналіз даних передбачує введення даних в стандартні або настроєні користувачем моделі, тобто в будь-якому випадку допускається, що зв'язки між різними показниками добре відомі і можуть бути виражені математично. Однак, в багатьох випадках зв'язки не можуть бути апріорі відомі. У таких ситуаціях моделювання стає неможливим і тут можна застосовувати дейтамайнінг (Data Mining) – інтелектуальний аналіз даних (ІАД). Тому, особливо важливим аспектом підготовки спеціалістів напрямку "Комп'ютерні науки” є успішне засвоєння ними дисципліни "Інтелектуальний аналіз даних”.
У результаті вивчення дисципліни “Інтелектуальний аналіз даних” студент повинен :
Знати - сутність та призначення Data Mining; характеристики процесів та активностей дейтамайнінгу;дерево методів дейтамайнінгу; доступне програмне забезпечення ІАД; призначення та основні характеристики генетичних алгоритмів і програмних агентів, ; вивчити основні методи генетичного пошуку.
Вміти - використовувати генетичні методи для розв’язку оптимізаційних задач.будувати дерево методів дейтамайнінгу; проводити кластерний аналіз засобами дейтамайнінгу;здійснювати вибір відповідних логічних методів із побудовою таблиці трансакцій;будувати крос-таблицю;вміло застосовувати доступне програмне забезпечення дейтамайнінгу.
Методвказівки до виконання лабораторних робіт з дисципліни “Інтелектуальний аналіз даних” включають 2 теоретичних розділи та дві лабораторних роботи, кожний із яких містить необхідний методичний матеріал для вивчення даного предмету.
I. Генетичні алгоритми
1.1. Генетичні успадкування —концептуа льні засади генетичних алгоритмів
У загальному значенні генетичні алгоритми (Genetic Algorithms) — це тип алгоритмів, інспірованих механізмами еволюції живої природи, які застосовуються, головно, до задач глобальної оптимізації (зокрема, задач комбінаторної оптимізації) і деякою мірою для дейтамайнінгу, зокрема, для комбіну вання шаблонів з правил індукції, які були відкриті до цього, навчання нейромереж, пошуку зразків у даних, відкриття шаб лонів у тексті тощо. Генетичні алгоритми належать нині до стан дартного інструментарію методів дейтамайнінгу.
Ідея генетичних алгоритмів запозичена з живої природи і по лягає в машинній організації еволюційного процесу створення, модифікації і відбору кращих розв'язків, виходячи з того, що в процесі відтворення і модифікації розв'язків кращі з них (подібно До процесу селекції в рослинництві й тваринництві) можуть дати ще ліпших «нащадків», тобто нові, прийнятніші варіанти розв'я зання задачі. Щоб краще зрозуміти концептуальні засади генети чних алгоритмів, зупинимося на короткому огляді механізмів природного добору і генетичного успадкування, що розглядаються в еволюційній теорії зародження і розвитку життя на нашій планеті. Ця теорія стверджує, що кожний біологічний вид ціле спрямовано розвивається й змінюється так, щоб у найкращий спосіб пристосуватися до навколишнього середовища.
Ключову роль в еволюції відіграє природний добір. Його суть полягає в тому, що найпристосованіші особи краще виживають і приносять більше потомства, ніж менш пристосовані. При цьому завдяки передаванню генетичної інформації, що називається ге нетичним успадковуванням, нащадки успадковують від батьків основні властивості. Проте слід зауважити, що сам по собі при родний добір ще не забезпечує розвитку біологічного виду. Дій сно, якщо передбачити, що всі нащадки народжуються приблиз но однаковими, то покоління будуть відрізнятися тільки за чисе льністю, але не за пристосованістю. Тому дуже важливо вивчити, у який спосіб відбувається успадкування, тобто як властивості нащадка залежать від властивостей батьків.
Майже в кожній клітині будь-якої тварини є ряд хромосом, що несуть інформацію про цю тварину. Основна частина хромосоми — нитка ДНК (молекула дезоксирибоза Нуклеїнової Кислоти), яка складається з чотирьох видів спеціальних з'єднань (молекул) — нуклеотидів, що чергуються в певній послідовності. Нуклеотиди позначають буквами А, Т, С і G, і саме порядок їх розміщеня є кодом усіх генетичних властивостей даного організму. Кажучи точніше, ДНК визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати ме. Отже, генетичний код окремого індивідуума — це просто дуже довгий рядок комбінацій із чотирьох букв А, Т, С і G, а сам ген — це відрізок ланцюга ДНК, що відповідає за певну власти вість особи, наприклад за колір очей, тип волосся, колір шкіри і т. д. Різні значення генів називають аллелями. Вся сукупність гене тичних ознак людини кодується за допомогою приблизно 60 тис. генів, які разом містять більше ніж 90 млн нуклеотидів.
У мейозі, зокрема, відбувається наступне: парні хромосоми со матичної клітини зближуються впритул, потім їх нитки ДНК розри ваються в кількох випадкових місцях і хромосоми обмінюються своїми ідентичними ділянками. Цей процес забезпечує появу нових варіантів хромосом І називається перехрещуванням хромосом або кросинговером (від анг. crossing-over). Кожна з хромосом, що знову з'явилася, виявиться потім усередині однієї зі статевих клітин, і її генетична інформація може реалізуватися в нащадках даної особи.
Другим важливим чинником, що впливає на спадковість, £ мута ції, тобто раптові спадкові зміни організму або його частин, ознак, властивостей, які виражаються у зміні деяких дільниць ДНК. Мутації також випадкові і можуть бути викликані різними зовнішніми чин никами, такими, наприклад, як радіоактивне опромінення. Якщо му тація сталася в статевій клітині, то змінений ген може передатися на щадку й виявитися у вигляді спадкової хвороби або в інших нових властивостях нащадка. Вважається, що саме мутації є причиною по яви нових біологічних видів, а кросинговер визначає мінливість уже всередині виду (наприклад, генетичні відмінності між людьми).
Важливе місце в еволюційній теорії відводиться поняттю по пуляції як елементарній еволюційній одиниці. Популяція — це сукупність особин певного виду організмів, які здатні до вільного схрещування, населяють певну територію і деякою мірою ізольо вані від сусідніх популяцій. У рамках кожної популяції відбува ється процес розмноження — репродукції (Reproduction), що являє собою комбінацію послідовностей (strings, хромосом) у опуляци для створення нової послідовності (нащадка). За реродукціі нащадок бере частини позицій генів від обох батьків, матиме частину ознак кожного із них. На рис. 9.13а) показана спрощена схема процесу репродукції, де ознаки батьків виражені хромосомою, котра складається з шести генів, що мають дві аллелі, позначені на схемі нулями і одиницями. Нащадок отримав чотири гени від другого батька (перша, друга, третя і шоста по зиція) і два від першого (четверта і п'ята позиції).
У генетичних алгоритмах важливе значення мають: форму вання початкового ряду елементів (популяції), операції кросинговера, що в теорії генетичних алгоритмів частіше називають кросовером (Cross-over), і мутації (Mutation).
Кросовер -— це комбінування (змішування) хромосом шляхом замін значень генів і утворення нових хромосом на їх місцях. На рис. 1. б) наведена спрощена схема кросовера, де показано, як шляхом заміни ідентичних ділянок двох батьків отримані два нащадки з новими ознаками.
Мутація — спонтанне перетворення (видозміна) символів (характерних особливостей) у послідовності (хромосомі). На рис. 1 в) показано, як у результаті мутації п'ятого гена (зна чення 0 замінено 1) отримана нова хромосома.
Рисунок 1. Схема генеративних процесів:
а) репродукції осіб популяції; б) кросовера осіб популяції; в) мутації хромосоми
ці процеси можуть комбінуватися для формування гібридних операторів, операцій репродукції (відтворення) і схрещування з тим, щоб бути спроможними створювати конкуренцію між попу ляціями.
1.2. Загальна схема генетичних алгоритмів
У концептуальному плані загальна схема генетичних алгоритмів досить проста. Спочатку генерується початкова попу ляція особин (індивідуумів, хромосом), тобто деякий ряд розв'язків задачі. Як правило, це робиться випадково. Потім не обхідно змоделювати розмноження всередині цієї популяції. Для цього випадково підбираються кілька пар індивідуумів, прово диться схрещування хромосом у кожній парі, а отримані нові хромосоми поміщають у популяцію нового покоління. У генетич ному алгоритмі зберігається засадний принцип природного до бору: чим пристосованіший індивідуум (чим більше відповідне йому значення цільової функції), тим з більшою ймовірністю він буде брати участь у схрещуванні.
Потім моделюються мутації в кількох випадково вибраних особинах нового покоління, тобто змінюються деякі гени. Після цього стара популяція частково або повністю знищується і ми пе реходимо до розгляду наступного покоління. Популяція наступно го покоління в більшості реалізацій генетичних алгоритмів містить стільки ж особин, скільки й початкова, але внаслідок відбору пристосованість (значення цільової функції) у ній в середньому вища. Операція доведення кількості особин поточної популяції до початково визначеної величини називається редукцією. Опи сані процеси відбору, схрещування і мутації повторюються вже Для цієї нової популяції.
У кожному наступному поколінні буде спостерігатися виник нення абсолютно нових розв'язків задачі. Серед них будуть як погані, так і кращі, але завдяки процедурі добору кількість кра щих розв'язків буде зростати. Зауважимо, що в природі не буває абсолютних гарантій, і навіть найпристосованіший тигр може за гинути від пострілу мисливця, не залишивши потомства. Імітую чи еволюцію в комп'ютері, можна уникати подібних небажаних подій і завжди зберігати життя кращому з індивідуумів поточно-0 покоління. Така методика називається «стратегією елітизму», коли в наступне покоління відбираються особини з найкращими показниками.
Описана послідовність дій за реалізації генетичних алгоритмів може перетворюватися в різні програмні реалізації залежно від типу розв'язуваної задачі і вибраних для цього підходів. Зокрема, в низці випадків може вводитися інша, ніж описана вище, єрархія базових понять, наприклад, кожний індивідуум може характери зуватися низкою хромосом, котрі, у свою чергу, містять різні ти пи генів. Пояснимо на прикладі.
Нехай розглядається завдання вибору плану вкладення коштів у вибрані наперед N інвестиційних проектів, причому потрібно визначити обсяги вкладень коштів у кожний проект так, щоб за гальний їх обсяг в усі проекти не перевищував величину D, а ви браний критерій ефективності, наприклад рівень рентабельності інвестицій (прибуток на капітал, ROI — Return on Investment), набував максимального значення. Розв'язуючи цю задачу за ге нетичним алгоритмом, вважатимемо, що кожен індивідуум — це інвестиційний план, який містить N хромосом, кожна з яких яв ляє собою вектор із нулів та одиниць — двійковий вираз обсягу вкладень у даний проект. Якщо довжина хромосоми дорівнює ві сьмом двійковим розрядам, то потрібне попереднє нормування всіх чисел на інтервалі від 0 до 255 (усього значень 28). Такі хромосоми називаються безперервними і уможливлюють подан ня значень довільних числових параметрів.
Мутації безперервних хромосом випадковим способом змі нюють у них один біт (ген), впливаючи у такий спосіб на значен ня параметра. Кросовер також можна здійснювати стандартно, об'єднуючи частини відповідних хромосом (з однаковими номе рами) різних індивідуумів. Особливістю цієї задачі є те, що зага льний обсяг капіталу, що інвестується, фіксований і дорівнює D. Очевидно, що із-за мутацій і схрещувань можна отримувати розв'язки, для реалізації яких потрібний капітал, більший або менший ніж D. У генетичному алгоритмі використовується спе ціальний механізм аналізування таких розв'язків, що дає змогу враховувати обмеження типу «сумарний капітал = D " за підра хунку пристосованості індивідуума. У процесі еволюції особини з суттєвим порушенням зазначених обмежень «вимирають». Унаслідок дії алгоритму отриманий розв'язок за сумарним капі талом може не дорівнювати точно, але бути близьким до заданої величини D. У процесі роботи генетичного алгоритму оцінюється значення цільової функції для кожного плану і здійснюється опе рація редукції для всієї популяції.
Цю саму задачу можна подати і в іншій генетичній інтерпре тації, якщо ввести умову, що кожний із інвестиційних проектів aбо цілком приймається, або відхиляється. Тоді кожний варіант плану (хромосому) можна подати у вигляді послідовності з N нулів та одиниць, причому, якщо на цьому місці в хромосомі сто їть одиниця, то це означає, що і-й проект (і - 1, 2, ..., ЛО вклю чений у план, а якщо нуль — не включений. Популяція склада ється із кількох варіантів планів. Визначення допустимості пла нів і оцінювання їх за вибраними критеріями проводиться ана логічно.
У загальному вигляді стратегію отримання рішень за допомо гою генетичних алгоритмів можна реалізувати такими кроками:
1) ініціалізуйте популяцію;
2) виберіть батьків для репродукції і оператори мутації і кросовера;
3) виконайте операції, щоб згенерувати проміжну популяцію індивідуумів і оцінити їхні придатності;
4) виберіть членів популяції для отримання нової генерації
(версії);
5) повторюйте кроки 1—З, поки не буде досягнуте деяке пра вило зупинки.
На рис. 2 показана узагальнена схема реалізації генетично го алгоритму. До його основних характеристик належать: розмір популяції, оператор кросовера і ймовірність його використання, оператор мутації і її ймовірність, оператор селекції, оператор ре дукції, правило (критерій) зупинки процесу виконання генетич ного алгоритму. Оператори селекції, кросовера, мутації і редукції ще називають генетичними операторами.
Критерієм зупинки процесу здійснення генетичного алгорит му може бути одна з трьох подій:
• сформовано задану користувачем кількість поколінь;
• популяція досягла заданої користувачем якості (наприклад, значення якості всіх особин перевищило задану порогову вели чину);
• досягнутий деякий рівень збіжності. Тобто особини в попу ляції стали настільки подібними, що дальше їх поліпшення відсувається надзвичайно повільно, і тому продовження здійснення ітерацій генетичного алгоритму стає недоцільним.
Після завершення роботи генетичного алгоритму з кінцевої популяції вибирається та особина, яка дає максимальне (або мі німальне) значення цільової функції і, отже, є результатом здій снення генетичного алгоритму. За рахунок того, що кінцева популяція краща, ніж початкова, отриманий результат являє собою поліпшене рішення.
Рисунок 2. Узагальнена схема реалізації генетичного алгоритму
1.3. Доступне програмне забезпечення генетичних алгоритмів
Генетичні алгоритми нині можна застосовувати в різ них галузях. їх успішно використовують для розв'язування низки великих і економічно важливих задач у бізнесі і в інженерних розробках. З їх допомогою були розроблені промислові проектні рішення, що уможливили багатомільйонну економію витрат. Фі нансові компанії широко використовують ці засоби у разі про гнозування розвитку фінансових ринків для управління пакетами цінних паперів. Нарівні з іншими методами генетичні алгоритми, зазвичай, використовуються для оцінювання значень безперерв них параметрів моделей великих розмірностей, для розв'язування комбінаторних задач, для задач з оптимізації, що містять одночас но безперервні і дискретні параметри. Іншою галуззю їх застосування є використання в системах добування нових знань із вели ких баз даних, створення і навчання стохастичних мереж, на вчання нейронних мереж, оцінювання параметрів у задачах бага товимірного статистичного аналізу, отримання початкових даних для виконання інших алгоритмів пошуку і оптимізації. Все це зумовило зростання заінтересованості фірм-розробників комер ційного програмного забезпечення стосовно генетичних алгорит мів, що в кінцевому результаті привело до появи на ринку бага тьох програмних продуктів такого виду.
Незважаючи на те, що розв'язання конкретної оптимізаційної за дачі часто потребує побудови генетичного алгоритму з унікальними значеннями параметрів, низка базових властивостей цих алгоритмів залишається постійною за розв'язання абсолютно різних задач. То му здебільшого для реалізації конкретного генетичного алгоритму не потрібно створювати окремий програмний продукт.
Опишемо кілька прикладів програмного забезпечення, що дає змогу реалізовувати широкий набір генетичних алгоритмів, які можна застосовувати для розв'язування найрізноманітніших за дач. Змінними параметрами генетичних алгоритмів у таких додат ках, зазвичай, є різні значення ймовірностей, розмір популяції і низка специфічних властивостей алгоритму. Проте реалізація ге нетичних операторів, як правило, єдина для всіх алгоритмів і прихована від користувача.
Пакет Evolver 4.0 компанії Palisade Corp. Пакет Evolver яв ляє собою доповнення до програми MS Excel версій 5.0 і 7.0. При цьому Excel використовується як засіб опису початкових даних алгоритму і розрахунків у процесі його виконання. У процесі установки Evolver додає в Excel додаткову панель інструментів, яка забезпечує доступ до пакета. Якщо Evolver не запущений для виконання, то панель інструментів не відображається. У разі за пуску Evolver додаток Excel запускається автоматично.
Пакет GeneHunter 1.0 компанії Ward System Group. Пакет GeneHunter багато чим схожий з пакетом Evolver. Він також є над будовою над MS Excel версій 5.0 і 7.0 і запускається з меню «Сер віс». Цей пакет русифікований і має низку додаткових настройок для генетичних алгоритмів: включення стратегій елітизму й різно манітності. Поля вікна GeneHunter практично такі самі як і в Evolver. Однак його вікно має низку відмінностей. Для установки параметрів алгоритму служить кнопка «Параметри...». Параметри генетичного алгоритму не зберігаються автоматично з файлом Eхсel. Для збереження параметрів служить кнопка «Модель», після натиснення на яку з'являється відповідне діалогове вікно.
Пакет Genetic Training Option (GTO) компанії California Scientific Software. Пакет GTO є додатковою утилітою, що поста вляється для нейропакета BrainMaker виробництва компанії «California Scientific Software». Він застосовується як для побу дови нейронних мереж, так і для поліпшення створеної за допо могою BrainMaker мережі. Але в обох випадках окремо від BrainMaker використовуватися не може.
Генетичні алгоритми складні для створення, але прості в засто суванні — потребують від користувача тільки формалізації задачі й формування початкових даних. Така ситуація багато в чому сприяє розширенню галузей застосування генетичних алгоритмів.
Лабораторна робота № 1 Методи генетичного пошуку
Мета роботи
1.1.1 Вивчити основні методи генетичного пошуку.
1.1.2 Навчитися використовувати генетичні методи для розв’язку оптимізаційних задач.
Основні теоретичні відомості
У багатьох технічних задачах актуальною є проблема знаходження глобального оптимуму цільової функції в багатомірному просторі керованих змінних. Традиційні методи багатомірної оптимізації є методами локального пошуку та сильно залежать від вибору початкової точки пошуку. Для знаходження глобального оптимуму доцільно використовувати методи генетичного пошуку.
Генетичні методи засновані на аналогії з природними процесами селекції та генетичними перетвореннями, і поєднують комп'ютерні методи моделювання генетичних процесів у природних і штучних системах.
Традиційно до генетичних методів відносять генетичні алгоритми, генетичні стратегії, генетичне програмування та еволюційне програмування.
Генетичний пошук як метод оптимізації
Генетичний пошук містить у собі групу багатомірних, стохастичних, евристичних оптимізаційних методів, вперше запропонованих Д. Холландом у 1975 р. і заснованих на ідеї еволюції за допомогою природного відбору. Генетичні методи були отримані в процесі узагальнення й імітації в штучних системах таких властивостей живої природи, як природний відбір, пристосованість до змінюваних умов середовища, спадкування нащадками життєво важливих властивостей від батьків і т.ін.
Під стандартним генетичним методом розуміють метод для вирішення оптимізаційних задач вигляду:
f (H) → min,
де f – функція пристосованості (функція придатності, цільова функція, фітнесс-функція);
H = {0; 1}L – хромосома, що містить в закодованому вигляді параметри цільової функції;
L – кількість розрядів у хромосомі.
Генетичні методи в процесі пошуку використають деяке кодування множини параметрів замість самих параметрів, тому вони можуть ефективно застосовуватися для рішення задач оптимізації, визначених як на числових множинах, так і на кінцевих множинах довільної природи.
Аналогія генетичних методів з поняттями генетики
Основна концепція класичної генетики – ген (реально існуюча, незалежна, комбінуюча та розщеплююча при схрещуваннях одиниця спадковості) була введена І.Г. Менделем з метою пояснення спостережуваної статистики спадкування. Носіями генів у клітинному ядрі особини є нитковидні тіла – хромосоми (структурні елементи клітинного ядра біологічних організмів, що є носіями генів). У генетичних методах терміни “хромосома” і “особина” використаються як синоніми. Місце, що займає ген у хромосомі, називається локусом. Схематично можна уявити собі хромосому як прямолінійний відрізок, а локуси – як послідовні ділянки, на які цей відрізок розбитий. Гени приймають значення, які називаються алелями.
Дії генів проявляються в досить великих співтовариствах організмів, що схрещуються між собою. Такі співтовариства називають популяціями. Популяції характеризуються набором хромосом кожного з об'єктів, сукупність яких визначає генофонд популяції.
Таким чином, генетичні методи запозичили з біології понятійний апарат, ідею колективного пошуку екстремуму, способи представлення генетичної інформації, способи передачі генетичної інформації в послідовності поколінь (генетичні оператори), ідею про переважне розмноження найбільш пристосованих особин.
Узагальнена схема роботи генетичних методів
Суть генетичного пошуку полягає в циклічній заміні однієї популяції наступною, більш пристосованою. Таким чином, популяція існує не тільки в просторі, але й у часі. Початкова популяція 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. Кінець.
У наш час запропоновано багато різних генетичних методів, і в більшості випадків вони мало схожі на наведений генетичний метод. Із цієї причини під терміном “генетичні методи” мається на увазі досить широкий клас методів, часом мало схожих один на одного.
Використання генетичного пошуку для рішення практичних задач передбачає:
– вибір методу представлення вхідних даних для генетичного пошуку (кодування параметрів, що оптимізуються);
– визначення цільової функції, що використовується для оцінки хромосом;
– вибір оператору відбору хромосом, що будуть використані для генерації нових рішень за допомогою схрещування й мутації;
– вибір методів одержання нових рішень (операторів схрещування й мутації);
– завдання параметрів пошуку, таких як кількість особин у популяції, імовірнісні характеристики генетичних операторів, максимально припустима кількість ітерацій генетичного пошуку, кількість елітних особин при використанні стратегії елітизму.
Моделі генетичного пошуку
Крім узагальненої схеми функціонування генетичного методу, розглянутої вище, використовують також інші технології генетичного пошуку. Вибір моделі генетичного методу залежить від типу розв'язуваної задачі.
Виділяють наступні методи й моделі генетичного пошуку:
– канонічні моделі (репродуктивний план Холланда, генетичний метод Девиса, генетичний метод Гольдберга);
– модель Genitor (Д. Уітлі);
– гібридні генетичні методи;
– модель CHC;
– генетичний метод зі змінним часом життя особин;
– мобільний генетичний метод;
– паралельні й багаторівневі генетичні методи (однопопуляційні генетичні методи, острівна модель, дрібноструктурні генетичні методи, ієрархічні гібриди);
– генетичний пошук зі зменшенням розміру популяції.
Ініціалізація та запуск генетичного пошуку
Кодування параметрів, що оптимізуються
Будь-який організм може бути представлений своїм фенотипом, що фактично визначає, чим є об'єкт у реальному світі, і генотипом, що містить всю інформацію про об'єкт на рівні хромосомного набору. При цьому кожний ген, тобто елемент інформації генотипу, має своє відображення у фенотипі. Таким чином, для розв’язку задач необхідно представити кожну ознаку об'єкта у формі, що підходить для використання в генетичному методі. Все подальше функціонування механізмів генетичного методу відбувається на рівні генотипу, що дозволяє обходитися без інформації про внутрішню структуру об'єкту, що й обумовлює широке застосування генетичного пошуку в самих різних задачах.
За методами представлення генів хромосоми можна умовно розділити на три групи:
1. Бінарні хромосоми – хромосоми, гени яких можуть приймати значення 0, або 1.
2. Числові хромосоми – гени можуть приймати значення в заданому інтервалі.
Числові хромосоми можна розділити на гомологічні та негомологічні.
Гомологічними називають хромосоми, що мають загальне походження, морфологічно та генетично подібні, і тому не утворюють неприпустимих рішень при застосуванні стандартних генетичних операторів. У гомологічних числових хромосомах кожний ген може приймати цілі значення в заданому інтервалі. Для різних генів можуть бути задані різні інтервали. Бінарна хромосома є гомологічною числовою хромосомою, кожний ген якої може приймати цілі значення в інтервалі [0, 1].
У негомологічних хромосомах гени можуть приймати значення в заданому інтервалі; при цьому інтервал однаковий для всіх генів, але в хромосомі не може бути двох генів з однаковим значенням. Для негомологічних хромосом застосовуються різні спеціальні генетичні оператори, що не створюють неприпустимих рішень. Негомологічні хромосоми, як правило, застосовуються при розв’язку задач комбінаторної оптимізації.
3. Векторні хромосоми – хромосоми, гени яких представляють собою вектор цілих чисел.
Ген у векторних хромосомах має властивості негомологічної хромосоми, тобто числа у векторі можуть приймати значення в заданому інтервалі, і вектор не може містити двох однакових чисел. Проте, хоча гени у векторних хромосомах негомологічні, самі векторні хромосоми є гомологічними.
Процес кодування параметрів, що оптимізуються, можна виконати в наступній послідовності кроків.
Крок 1. Визначення параметрів, що оптимізуються, – генів.
Крок 2. Вибір числа розрядів у кожному гені.
Крок 3. Вибір методу кодування.
Варто врахувати, що занадто велика довжина кодування прискорює процес збіжності всіх членів популяції до кращого знайденого рішення. Часто такий ефект є небажаним, оскільки при цьому більша частина простору пошуку залишається недослідженою. Передчасна збіжність може не привести до оптимального рішення, крім того, швидка збіжність до однієї області не гарантує виявлення декількох рівних екстремумів. До того ж застосування довгих кодувань зовсім не гарантує, що знайдене рішення буде мати необхідну точність, оскільки цього, в принципі, не гарантує сам генетичний метод.
Тому в питанні вибору оптимальної довжини кодування потрібно досягти деякого компромісного рішення – з одного боку довжина хромосоми повинна бути досить великою, щоб все-таки забезпечити швидкий пошук, з іншого боку – по можливості малою, щоб не допускати передчасної збіжності й залишити методу шанс відшукати кілька оптимальних значень.
Наведемо варіанти кодування генів у деяких задачах, розв'язуваних за допомогою генетичних методів:
– оптимізація функцій: гени – незалежні змінні;
– апроксимація: гени – параметри-константи апроксимуючих функцій;
– задача відбору інформативних ознак: гени ідентифікують значимість відповідних ним ознак (наприклад, якщо значення гену дорівнює одиниці, то відповідна йому ознака вважається інформативною);
– настроювання ваг штучної нейронної мережі: гени відповідають синоптичним вагам нейронів;
– штучне життя (Artificial Life): гени відповідають характеристикам особини (сила, швидкість, і т.ін.), також повинні бути незмінні гени, що позначають тип особини (рослина або тварина);
– задача про найкоротший шлях: гени – пункти пересування. Вся хромосома представляє собою маршрут з початкової точки в кінцеву, причому не завжди існуючий.
Невдалий вибір упорядкування та кодування бітів у хромосомі може викликати передчасну збіжність до локального оптимуму. Для подолання цього недоліку можна вибирати спосіб кодування, ґрунтуючись на додаткової інформації про задачу.
Варто відзначити, що використання різних варіантів кодування розподіляє точки в просторі пошуку по-різному. У найбільш розповсюдженій різновиді генетичного пошуку для представлення генотипу об'єкту використовуються бітові рядки. При цьому кожному атрибуту об'єкту у фенотипі відповідає один ген у генотипі об'єкта. Ген є бітовим рядком, найчастіше фіксованої довжини, що являє собою значення цієї ознаки.
Кількість розрядів r у гені для кодування ознаки визначається за формулою:
,
де ceil(x) – найближче більше або рівне х ціле число;
wmax і wmin – максимально й мінімально можливі значення ознаки (параметра, незалежної змінної);
ε – задана похибка визначення оптимального значення ознаки.
Розрядність хромосоми L визначається як сума розрядностей генів. У випадку, якщо задані однакові значення wmax, wmin і ε для всіх n генів, розрядність хромосоми може бути обчислена за формулою:
L = n · r.
Після того, як обрані параметри, їх кількість та розрядність, необхідно вирішити, як безпосередньо записувати дані, тобто вибрати метод кодування. Можна використати звичайне кодування або коди Грея. Незважаючи на те, що використання кодів Грея призводить до кодування/декодування даних, вони дозволяють уникнути деяких проблем, які з'являються в результаті звичайного кодування.
Перевага коду Грея в тому, що якщо два числа відрізняються на 1, то і їхні двійкові коди відрізняються тільки на один розряд, а у двійкових кодах не все так просто. Так, наприклад, числа 7 і 8 у бітовому поданні відрізняються в чотирьох позиціях (710=01112, 810=10002), що затрудняє функціонування генетичного методу й збільшує час, необхідний для його збіжності, а в коді Грея ці числа відрізняються всього на одну позицію (710=0100Г, 810=1100Г).
Варто відзначити, що кодувати й декодувати у коди Грея досить зручно. Кодування/декодування з бінарного коду в код Грея можна виконати в такий спосіб.
Крок 1. Скопіювати старший розряд кодуємого (декодуємого) числа в старший розряд декодуємого (кодуємого) числа.
Крок 2. Виконати перетворення за формулами:
– із двійкового коду в код Грея: ;
– з коду Грея у двійковий: ,
де G[i] – i-ий розряд коду Грея;
B[i]– i-ий розряд бінарного коду.
Наприклад, послідовність чисел від 0 до 15 у двійковому коді: {0000, 0001 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001 1010, 1011, 1100, 1101, 1110, 1111}, а в кодах Грея: {0000, 0001 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101 1111, 1110, 1010, 1011, 1001, 1000}.
Кодування ознак, яким відповідають числа із плаваючою комою.
Найпростіший спосіб кодування – використання бітового представлення. Однак такий варіант має ті ж недоліки, що й при кодуванні цілих чисел. Тому на практиці застосовується наступна послідовність дій.
Крок 1. Розбивається весь інтервал допустимих значень ознаки на ділянки з необхідною точністю.
Крок 2. Приймається значення гена як ціле число, що визначає номер інтервалу (використовуючи код Грея).
Крок 3. В якості значення параметра приймається число, що є серединою цього інтервалу.
Завдання цільової функції
Цільова функція – це функція, оптимум якої необхідно знайти. Генетичний метод вимагає, щоб хромосоми оцінювалися за допомогою цільової функції (фітнесс-функцій, функції пристосованості, функції оцінки) задачі.
Наприклад, для задачі апроксимації, цільовою функцією може бути середнє відхилення значень вихідного параметру, розрахованих за утвореною моделі, від його реальних значень.
Можна відзначити, що обчислення фітнесс-функції – один з найбільш важливих етапів генетичного пошуку.
Тому при виборі цільової функції потрібно враховувати наступне.
1. Функція пристосованості повинна бути адекватна задачі. Це означає, що для успішного пошуку необхідно, щоб розподіл значень фітнесс-функціх збігався з розподілом реальної якості рішень (не завжди “якість” рішення еквівалентна його оцінці за фітнесс-функцією).
2. Фітнесc-функція повинна мати рельєф. Крім того, рельєф повинен бути різноманітним. Це означає,
16.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора