Задача з генетичними алгоритмами

Приклад розв’язування економічних задач генетичними алгоритмами

  Генетичні алгоритми нині можна застосовувати в різних галузях. Їх успішно використовують для розв’язування низки великих і економічно важливих задач у бізнесі і в інженерних розробках. З їх допомогою були розроблені промислові проектні рішення, що уможливили багатомільйонну економію витрат. Фінансові компанії широко використовують ці засоби у разі прогнозування розвитку фінансових ринків для управління пакетами цінних паперів. Нарівні з іншими методами генетичні алгоритми, зазвичай, використовуються для оцінювання значень безперервних параметрів моделей великих розмірностей, для розв’язування комбінаторних задач, для задач з оптимізації, що містять одночасно безперервні і дискретні параметри.

  Однією з проблемних областей практичного застосуванняв бізнес-застосуваннях є розподіл інвестицій. Хромосоми у цій задачі виступають інвестиції, початкового (стартовою) популяцією – портффель проектів інвестицій, а генами – обсяги вкладення інвестицій у кожний із проектів. Областю змін окремого гена є є мінімальний та максимальний обсяги вкладення в кожній із проектів. Прибутковість окремого проекту розглядається як пристосованість істоти до умов існування. Цільоовю функцією, що підлягає максимізації, є сумарний дохід інвестора.
Засосування ГА свідчить, що за малих сумарних обсягів інвестицій інвестуються тільки прибуткові проекти за мінімальних вкладень. Прибутковість проектів у процесі генетичного пошуку зростає, і з'являються більш вигіднішша варіанти інвестування.

38. Поняття штучних нейронних мереж

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

ШНМ являють собою систему з'єднаних між собою простих процесорів(штучних нейронів), які взаємодіють. Такі процесори зазвичай достатньо прості, особливо в порівнянні з процесорами, що використовуються в персональних комп'ютерах. Кожен процесор схожої мережі має справу тільки з сигналами, які він періодично отримує, і сигналами, які він періодично посилає іншим процесорам. І тим не менш, будучи з'єднаними в досить велику мережу з керованою взаємодією, такі локально прості процесори разом здатні виконувати достатньо складні завдання. З точки зору машинного навчання, нейронна мережа являє собою окремий випадок методів розпізнавання образів, дискримінантного аналізу, методів кластеризації тощо З математичної точки зору, навчання нейронних мереж — це багатопараметрична задача нелінійної оптимізації. З точки зору кібернетики, нейронна мережа використовується в задачах адаптивного управління і як алгоритми для робототехніки. З точки зору розвитку обчислювальної техніки та програмування, нейронна мережа — спосіб вирішення проблеми ефективного паралелізму . А з точки зору штучного інтелекту, ШНМ є основою філософської течії коннективізму і основним напрямком в структурному підході з вивчення можливості побудови (моделювання) природного інтелекту за допомогою комп'ютерних алгоритмів. Нейронні мережі не програмуються в звичайному розумінні цього слова, вони навчаються. Можливість навчання — одна з головних переваг нейронних мереж перед традиційними алгоритмами. Технічно навчання полягає в знаходженні коефіцієнтів зв'язків між нейронами. У процесі навчання нейронна мережа здатна виявляти складні залежності між вхідними даними і вихідними, а також виконувати узагальнення. Це означає, що у разі успішного навчання мережа зможе повернути вірний результат на підставі даних, які були відсутні в навчальній вибірці, а також неповних та / або «зашумлених», частково перекручених даних.

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

Головним елементом нервової системи людини є нервові  клітини клітини – нейрони розміром від 0,01 до 0,1 мм. Нейрон може перебувати в спокійному або збудженому стані – короткий електричний імпульс.

За допомогою мікроскопа можна розгледіти таку структуру: тіло клітини, дендриди, синапси та аксон. Всі ці частини мають оболонку і клітинну мембрану.

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

Синапси 0 це поточні ділянки клітинної мембрани до яких впритул наближені кінцеві потовщення аксонів – синаптичні бляшки.

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

Імпульс збудження нейрона – це електрохімічний процес, який поширується вздовж аксона у вигляді хвилі зі швидкістю 1-100 м/с.

Інформація поступає через дендриди і поступає в ядро завдяки контактам між дендридом і синапсом.

Подібно до біологічного нейрону, нейрон Мак-КАллок і Піттса (МР-нейрон) виконує прийом, елементарне перетворення й передавання інформації іншим нейронам. Подібно до біологічного нейрону, він має n входів, один вихід у і складається із блоку локальної пам*яті, яка зберігає ваги синапсів wi(i=1…,n), суматора S  і блоку нелінійного перетворення f(s).

Вхідні (рецепторні) сигнали xi (i= 1…,n), які надходять через синапси з вагами wi,перетворюються у нейроні у зважені сигнали xi, wi. З них формується сумарний сигнал s=

Подібно до біологічного нейрона, штучний нейрон також може перейти у збуджений стан, якщо величинв сумарного сигналу s стане більше за деяке граничне значення (поріг) s*

40. Модель штучного нейрону

Штучний нейрон - вузол штучної нейронної мережі, що є спрощеною моделлю природного нейрона. Математично, штучний нейрон зазвичай представляють як деяку нелінійну функцію від єдиного аргументу - лінійної комбінації всіх вхідних сигналів. Цю функцію називають функцією активації або функцією спрацьовування,передавальною функцією. Отриманий результат посилається на єдиний вихід. Такі штучні нейрони об'єднують в мережі - з'єднують виходи одних нейронів з входами інших. Штучні нейрони та мережі є основними елементами ідеального нейрокомп'ютеру.

41. Модель однорівневого персептрону

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

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

,                                           

де  – вагові коефіцієнти входів лінійного нейронного елементу,  – вхідні дані,  – поріг нейрону. Для навчання однорівневого персептрону використовується правило Відроу-Хоффа, яке базується на методі градієнтного спуску в просторі вагових коефіцієнтів і порогів НМ. Згідно з цим правилом, необхідно здійснити мінімізацію середньо-квадратичної помилки.

42. Модель багаторівневого персептрону

Багаторівневим персептроном називають нейроні мережі прямого розповсюдження. Вхідний сигнал в таких мережах розповсюджується  в прямому напрямку, від шару до шару. Багаторівневий  персептрон в загальному представлені складається з таких елементів:

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

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

43. Модель «вікон» для прогнозування числових рядів штучною мережею

Метод вікон передбачає використання двох вікон Wi і Wo з фіксованими розмірами n і m відповідно. Ці вікна, здатні переміщатися з деяким кроком по часовій послідовності історичних даних, починаючи з першого елемента, і призначені для доступу до даних часового ряду, причому перше вікно Wi, отримавши такі дані, передає їх на вхід нейронної мережі, а друге-Wo-на вихід. 

Отримувана на кожному кроці пара Wi -> Wo (2.1) використовується як елемент навчальної вибірки (розпізнаваний образ, або спостереження).

 Наприклад, нехай є дані про щотижневі продажах ріжучого інструменту (k = 16): 100 94 90 96 91 94 95 99 95 98 100 97 99 98 96 98 (2.2)

Весь ряд дивися додаток 1.Зададім n = 4, m = 1, s = 1. За допомогою методу вікон для нейронної мережі буде згенерована наступна навчальна вибірка:

100 94 90 96 -> 91

94 90 96 91 -> 94

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

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

Використовується для здійснення довгострокового прогнозу і призначено для визначення основного тренду і головних точок зміни тренда для деякого проміжку часу в майбутньому. При цьому система, що прогнозує використовує отримані (вихідні) дані для моментів часу k +1, k +2 і т.д. в якості вхідних даних для прогнозування на моменти часу k +2, k +3 і т.д.

Припустимо, система навчилася на часовій послідовності (3.2). Потім вона спрогнозувала k +1 елемент послідовності, наприклад, рівний 95, коли на її вхід був поданий останній з відомих їй образів (99, 98, 96, 98). Після цього вона здійснює подальше прогнозування і на вхід подається наступний образ (98, 96, 98, 95). Останній елемент цього образу є прогнозом системи. І так далі.

44. Алгорим навчання штучних нейронних мереж (зворотного розповсюдження помилок)

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

Алгоритм зворотнього розповсюдження використовується для навчання багаторівневих нейронних мереж з послідовними зв’язками. Нейрони в таких мережах (рис. 1б) поділяються на групи з загальним вхідним сигналом – рівні. На кожний нейрон першого рівня подаються всі елементи вхідного сигналу. Всі виходи нейронів  -го рівня подаються на кожний нейрон рівня  . Нейрони виконують зважене сумування елементів вхідних сигналів. До суми елементів вхідних сигналів, перемножених на відповідні вагові коефіцієнти (синапси) додається зміщення (поріг) нейрона. Над результатом сумування виконується нелінійне перетворення – функція активації (передавальна функція).

Вихід кожного нейрону попереднього рівня персептрону з’єднаний синапсами зі входами всіх нейронів наступного рівня. Таким чином, персептрон має однорідну та регулярну структуру.

45. Алгоритм розпізнавання алфавітно цифрової інформації штучними нейронними мережами

На вхідний пристрій персептрону послідовно проектуються зображення, що належать одному з двох образів, наприклад різні написи літер «А» і «Б». Навчальна система в залежності від правильної або неправильної реакції впливає на ваги зв'язків. Для тоги щоб персептрон міг розпізнавати більше число образів, наприклад усі літери алфавіту, потрібно збільшити кількість R-елементів. На кожному R-елементі будуть підсумовуватися сигнали, що відповідають визначеним ознакам об'єкту. Перша розпізнаюча машина, названа «Марк-1 », була створена у 1958 р. під керівництвом Ф. Розенблата.

Наступним кроком моделювання сприйняття і розпізнавання було використання перехресних зв'язків між А-елементами і створення чотирьохслойних персептронів. Чотирьохслойні персептрони мають два шари асоціативних елементів

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

46. Поняття образу, класифікація образів

Об’єкт, що піддається класифікації, називається образом (pattern).

Образом може бути цифрова фотографія (розпізнавання зображень), буква або цифра (розпізнавання символів), запис мови (розпізнавання мови) тощо.

В межах теорії штучного інтелекту розпізнавання образів включається в

більш широку наукову дисципліну — теорію машинного навчання (machine learning), метою якої є розробка методів побудови алгоритмів, що здатні навчатися.

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

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

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

47. Класифікація задач розпізнавання образів

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

Розпізнавання образів є однією з найфундаментальніших проблем теорії інтелектуальних систем. З іншого боку, задача розпізнавання образів має величезне практичне значення. Замість терміну "розпізнавання" часто використовується інший термін — "класифікація". Ці два терміни у багатьох випадках розглядаються як синоніми, але не є повністю взаємозамінюваними. Кожний з цих термінів має свої сфери застосування, і інтерпретація обох термінів часто залежить від специфіки конкретної задачі.

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

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

3.        Кластерний аналіз, який полягає в розділенні заданого набору об'єктів на класи — групи об'єктів, схожі між собою за тим чи іншим критерієм. Цю задачу часто називають класифікацією без учителя, оскільки, на відміну від задачі 2, класи апріорно не задані.

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

48. Проблема навчання при розпізнаванні образів

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

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

В цілому проблема розпізнавання образів складається з двох частин:

        навчання;

        розпізнавання.

Навчання здійснюється шляхом показу окремих об'єктів з вказанням їх приналежності тому або іншому образу. В результаті навчання розпізнаюча система повинна набути здатність однаково реагувати на всі об'єкти одного образу і по-різному – на всі об'єкти різних образів. Дуже важливо, що процес навчання повинен завершитися лише шляхом показів скінченого числа об'єктів без будь-яких інших підказок. Об'єктами навчання можуть бути або картинки, або інші візуальні зображення (букви), або різні явища зовнішнього світу, наприклад звуки, стани організму тощо. Важливо, що в процесі навчання вказуються лише самі об'єкти і їх приналежність образу. За навчанням слідує процес розпізнавання нових об'єктів, який характеризує дії вже навчанної системи. Автоматизація цих процедур і складає проблему навчання розпізнаванню образів. У випадку, коли людина сама розгадує або придумує, а потім нав'язує машині правило класифікації, проблема розпізнавання вирішується частково, оскільки основну і головну частину проблеми (навчання) людина бере на себе.

49. Геометричні та структурні підходи розпізнавання образів

Будь-яке зображення, яке виникає в результаті спостереження якого об'єкта в процесі навчання або іспиту, можна представити у вигляді вектора, а значить і у вигляді точки деякого простору ознак. Якщо стверджується, що при показі зображень можливо однозначно віднести їх до одного з двох (або кількох) образів, то тим самим стверджується, що в деякому просторі існує дві (або декілька) області, що не мають спільних точок, і що зображення - точки з цих областей. Кожній такій області можна приписати найменування, тобто дати назву, яка відповідає образу.

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

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

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

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

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