28. Основні режими роботи експертних систем
У роботі ЭС можна виділити два основних режими: режим придбання знань і режим рішення задачі (режим консультації або режим використання ). У режимі придбання знань спілкування з ЭС здійснює експерт (за допомогою інженера знань).
Використовуючи компонент придбання знань, експерт описує проблемну область у виді сукупності фактів і правил. Іншими словами, "наповняє" ЭС знаннями, що дозволяють їй самостійно вирішувати задачі з проблемної області.
Відзначимо, що цьому режимові при традиційному підході до програмування відповідають етапи: алгоритмізації, програмування і налагодження, виконувані програмістом. Таким чином, на відміну від традиційного підходу у випадку ЭС розробку програм здійснює не програміст, а експерт, що не володіє програмуванням.
У режимі консультацій спілкування з ЭС здійснює кінцевий користувач, якого цікавить результат і (або) спосіб його одержання. Необхідно відзначити, що в залежності від призначення ЭС користувач може:
не бути фахівцем у даній предметній області, і в цьому випадку він звертається до ЭС за результатом, що не вміє одержати сам;
бути фахівцем, і в цьому випадку він звертається до ЭС з метою прискорення одержання результату, покладаючи на ЭС рутинну роботу.
Слід зазначити, що на відміну від традиційних програм ЭС при рішенні задачі не тільки виконують запропоновану алгоритмом послідовність операцій, але і сама попередньо формує неї.
Добре побудована ЭС має можливість самонавчатися на розв'язуваних задачах, поповнюючи автоматично свою БЗ результатами отриманих висновків і рішень.
29. Послідовність виконання етапів розробки експертної системи
Технологія їхньої розробки ЭС, містить у собі шість етапів (мал.5): етапи ідентифікації, концептуалізації, формалізації, виконання, тестування, досвідченої експлуатації.
1) На етапі ідентифікації необхідно виконати наступні дії:
· визначення задачі, що підлягають рішенню і меті розробки,
· визначення експертів і типу користувачів.
2) На етапі концептуалізації:
· проводиться змістовний аналіз предметної області,
· виділяються основні поняття і їхні взаємозв'язки,
· визначаються методи рішення задач.
3) На етапі формалізації:
· вибираються програмні засоби розробки ЭС,
· визначаються способи представлення усіх видів знань,
· формалізуються основні поняття.
4) На етапі виконання (найбільш важливе і трудомісткому) здійснюється наповнення експертом БЗ, при якому процес придбання знань розділяють:
· на "витяг" знань з експерта,
· на організацію знань, що забезпечує ефективну роботу ЭС,
· на представлення знань у виді, зрозумілому для ЭС.
Процес придбання знань здійснюється інженером по знаннях на основі діяльності експерта.
5) На етапі тестування експерт і інженер по знаннях з використанням діалогових і пояснювальних засобів перевіряють компетентність ЭС. Процес тестування продовжується доти, поки експерт не вирішить, що система досягла необхідного рівня компетентності.
6) На етапі досвідченої експлуатації перевіряється придатність ЭС для кінцевих користувачів. За результатами цього етапу можлива істотна модернізація ЭС.
Процес створення ЭС не зводиться до строгої послідовності цих етапів, тому що в ході розробки приходиться неодноразово повертатися на більш ранні етапи і переглядати прийняті там рішення.
30. Поняття генетичного алгоритму. Еволюційна теорія.
Генетичний алгоритм являє собою метод, що відображає природну еволюцію методів вирішення проблем, і в першу чергу задач оптимізації. Генетичні алгоритми — це процедури пошуку, засновані на механізмах природного відбору і спадкоємства. У них використовується еволюційний принцип виживання найбільш пристосованих особин. Вони відрізняються від традиційних методів оптимізації декількома базовими елементами. Зокрема, генетичні алгоритми:
обробляють не значення параметрів самого завдання, а їх закодовану форму;
здійснюють пошук рішення виходячи не з єдиної точки, а з їх деякої популяції;
використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію;
застосовують імовірнісні, а не детерміновані правила вибору.
Перераховані чотири властивості, які можна сформулювати також як кодування параметрів, операції на популяціях, використання мінімуму інформації про завдання і рандомізація операцій приводять у результаті до стійкості генетичних алгоритмів і до їх переваги над іншими широко вживаними технологіями.
31. Поняття природного відбору в генетичному алгоритмі
Ключову роль в еволюційній теорії грає природний відбір. Його суть полягає в тому, що найбільш пристосовані особини краще виживають і приносять більше нащадків, ніж менш пристосовані. Зауважимо, що сам по собі природний відбір ще не забезпечує розвиток біологічного виду. Тому дуже важливо зрозуміти, яким чином відбувається спадкування, тобто як властивості нащадка залежать від властивостей батьків.
У цьому, завдяки передачі генетичної інформації (генетичному спадкуванню) нащадки успадковують від своїх батьків основні його якості. Отже, нащадки сильних індивідуумів також будуть добре пристосованими і частка у загальній масі особин зростатиме. Після зміни кілька десятків чи сотень поколінь середня пристосованість особин цього виду помітно зрастає.
У кожній клітці будь-якї тварини міститься вся генетична інформація цієї особини. Ця інформація записана як набір аж надто довгих молекул ДНК. Кожна молекула ДНК - це ланцюжок, що складається з молекул нуклеотидів чотирьох типів. Власне, інформацію несе порядок прямування нуклеотидів в ДНК. У тваринній клітині кожна молекула ДНК оточена оболонкою - таке утворення називається хромосомой.
Кажне вроджена якість особини (колір очей, спадкові хвороби, тип волосся тощо.) кодується певної частини хромосоми, що називається геном даної властивості. Наприклад, ген кольору очей містить інформацію, що кодує певний колір очей. Різні значення гена називаються його аллелями.
При розмноженні тварин відбувається злиття двох батьківських статевих клітин та їх ДНК взаємодіють, створюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросенговері ДНК предків діляться на частини, та обмінюються своїми половинками.
При успадкування можливі мутації через радіоактивності чи інших впливів, у яких можуть змінитися деякі гени в статевих клітинах одного із батьків. Змінені гени передаються нащадку і надають йому нові властивості. Якщо такі нові властивості корисні, вони, швидше за все, збережуться в даному виді – і станеться стрибкоподібне підвищення пристосованості вида.
32. Основні поняття генетики живих організмів і їх аналогії в технічних реалвзаціях у генетичних алгоритмах.
Популяція – це скінчена множина особин. Особини, що входять в популяцію в генетичних алгоритмахпредставляються хромосомами і закодованими в них множиною параметрів задачі, тобто рішень.
Хромосоми – це впорядкована послідовність генів. Майже в кожній клітині, будь-якої особини є набір хромосом, що несуть інформацію про особину. Основна частина хромосоми – це нитка ДНК, яка визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватисяя, які функції виконуватиме і скільки часу буде жити.
Ген – це відрізок ланцюжка ДНК, що відповідає за визначену властивість особини, наприклад колір очей, пігмент шкіри, тип волосся, темперамент і т.д. Вся сукупність генетичних ознак людини кодується за допомогою приблизно 60 тис. Генів, всі вони включаються в 46 хромосомах.
Генотип – набір хромосом певної особини. Особами популяції можуть бути генотипи.
Фенотип – набір значень, які відповідають деякому генотипу.
Алель – це значення конкретного гена.
Локус – вказує місце розміщення гена в хромосомі.
Функція пристосованості – представлення міри пристосованості особин в популяції. Ця функція відіграє важливу роль, оскільки дозволяє оцінити ступінь пристосованості конкретних особин в популяції і вибрати з цієї популяції найбільш пристосованих особин, для забезпечення еволюційних властивостей.
33. Постановка оптимізаційних задач. Розв'язок оптимізаційних задач в генетичних алгоритмах
Нерідко перед нами виникає завдання знайти найкраще оптимальне рішення завдання – найкращий результат.
У процесі проектування ставиться, звичайно, задача визначення найкращих, у деякому значенні, структури або значення параметрів об'єктів. Така задача називається оптимізаційною. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною. Задача вибору оптимальної структури є структурною оптимізацією.
Еволюція є процесом оптимізації життєдіяльності об*єктів. Відповідно до еволюційної теорії розвитку світу кожна істота у природі прагне вижити й залишити після себе чисельніше потомство. Досягти цієї мети можуть лише найсильніші істо ти і популяції живого світу. Наскільки популяція пристосована до середовища існування, настільки благополучно вона розвивається, судять із динаміки змін її чисельності. Живі істоти, які краще пристосовані до навколишнього середовища, мають більше можливостей для виживання й розмноження, ніж менш пристосовані.
Розв*язують оптимізаційні задачі в генетичних алгоритмах за допомогою декількох кроків: ініціалізація, оцінка пристосованості, перевірка умови зупинку алгоритму, селекція хромосом, застосування генетичних операторів, формування нової популяції, вибір «найкращої хромосоми».
34. Алгоритм роботи генетичних алгоритмів
Початок – Ініціалізація – формування вхідної популяції – полягає у виборі заданої кількості хромомсом, представлені двійковими послідовностями фіксованої довжини.
Оцінка пристосованості – полягає у розрахунках функції пристосованості для кожної хромосоми даної популяції
Перевірка умови ззупинки алгоритму – аналіз значень пристосованості особин. Визначення умов зупинки генетичного алгоритму залежить від його конкретного застосування. Зупинка алгоритму може відбутися у випадку, коли його виконання не призводить до кращого вже досягнутого знасення. Він може зупинитися, коли вийшов певний час виконання або після виконання заданої кількості ітерацій. Якщо умови зупинку виконуються, то відбувається перехід до завершаючого етапу вибору «найкращих» хромосом. В іншому випадку на наступному кроці виконується селекція.
Селекція хромосом полягає у відборі тих хромосом, які братимуть участь у створенні нащадків для наступних популяцій, такий відбір здійснюються згідно принципу природного відбору, по якому найбільші шінси значення функціїпристосованості. Існують різні методи селекції. Найбільш популярним вважається так званий метод рулетки – кожній хромосомі може бути зіставлений секторами рулетки, величини якого встановлюються пропорційно значеню ф-ї пристосованості даної хромосоми. Тому чим більше значень ф-ї пристосованості, тим більший сектор на колесі рулетки. Розміп сектора рулетки – Ps=F(chi)/
, де Ps – ймовірність селекції хромосом, F(chi)– значення функції пристосованості хромосомами chi.V(chi) – сектор рулетки: V(chi)= Ps(chi) *100%.
Застосування генетичних операторів до хромосом відбувається за допомогою селекції. Є два основних оператори схрещування та оператор мутації.
Формування нової популяції. Хромосоми отримані в результаті пристосування генетичних операторів до хромосом тимчасової батьківської популяції включаються в склад нової популяції. Вона стає поточною популяцією для даної ітерації генетичного алгоритму. На кожній черговій ітерації розраховується ф-я пристосованості для усіх хромосом цієї популяції, після чого перевіряється умова зупинки алгоритму і фіксується результат у вигляді хромосоми з найбільшою ф-ю пристосованості або переходимо до селекції знову.
Вибір «найкращої» хромосоми. Якщо умова зупинки алгоритму виконується, то потрібно вивести результат роботи, тобто представити шукане рішення задачі. Кращим рішенням задачі вважається хромосома з найбільшим значенням функції пристосованості.
35. Задача «комівояжера» її розв*язок генетичними алгоритмами
Задача «Комівояжера» полягає у в тому щоб знайти найкоротший шлях обходу всіх пунктів, побудувавши в кожному з них один раз.
На графі цієї задачі зазначені ваги ребер як відстані між пунктами. Ця задача розв*язується в такий спосіб:1. Описується множина станів задачі у вигляді списків пунктів, які комівояжер уже відвідав до даного часу. Наприклад, список АВС означає, що він ужже побував у пункті В і знаходиться в пункті С. Дозволеними є тільки ті описи станів, у яких кожен пункт повторюється лише один раз, за винятком пункту А, що може знаходитися на початку і в кінці списку.
2. Визначаються оператори задачі, кожен з яких описує рух до одного із пунктів. Наприклад оператор №1 – рух до пункту А, оператор №2 – рух до пункту В і. т.д.
3. Будується формалізована модель розв*зуваної задачі у вигляді дерева графа простору станів, де вказуються усі ходи від початку до кінця і вказується вага шляху.
4. Виконується аналіз отриманого графа з погляду заданого критерію оптимальності. Таким критерієм у цій задачі є мінімум довжини шляху комівояжера при проходженні всіх пунктів.
36. Задачі генетичних алгоритмів
Генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з
Генетичні алгоритми застосовуються для вирішення наступних завдань:
оптимізація функцій, оптимізація запитів в базах даних, різноманітні завдання на графах (задача комівояжера, розфарбування, знаходження паросполучення), налагодження та навчання штучної нейронної мережі, завдання компонування, складання розкладів, ігрові стратегії, теорія наближень, штучне життя, біоінформатика (фолдінг білків), синтез кінцевих автоматів, налаштування ПІД регуляторів.
37. Приклад розв*язування економічних задач генетичними алгоритмами
Генетичні алгоритми нині можна застосовувати в різних галузях. Їх успішно використовують для розв’язування низки великих і економічно важливих задач у бізнесі і в інженерних розробках. З їх допомогою були розроблені промислові проектні рішення, що уможливили багатомільйонну економію витрат. Фінансові компанії широко використовують ці засоби у разі прогнозування розвитку фінансових ринків для управління пакетами цінних паперів. Нарівні з іншими методами генетичні алгоритми, зазвичай, використовуються для оцінювання значень безперервних параметрів моделей великих розмірностей, для розв’язування комбінаторних задач, для задач з оптимізації, що містять одночасно безперервні і дискретні параметри.
Однією з проблемних областей практичного застосуванняв бізнес-застосуваннях є розподіл інвестицій. Хромосоми у цій задачі виступають інвестиції, початкового (стартовою) популяцією – портффель проектів інвестицій, а генами – обсяги вкладення інвестицій у кожний із проектів. Областю змін окремого гена є є мінімальний та максимальний обсяги вкладення в кожній із проектів. Прибутковість окремого проекту розглядається як пристосованість істоти до умов існування. Цільоовю функцією, що підлягає максимізації, є сумарний дохід інвестора.
Засосування ГА свідчить, що за малих сумарних обсягів інвестицій інвестуються тільки прибуткові проекти за мінімальних вкладень. Прибутковість проектів у процесі генетичного пошуку зростає, і з'являються більш вигіднішша варіанти інвестування.
38. Поняття штучних нейронних мереж
Штучні нейронні мережі (ШНМ) — математичні моделі, а також їхня програмна та апаратна реалізація, побудовані за принципом функціонування біологічних нейронних мереж — мереж нервових клітин живого організму. Системи, архітектура і принцип дії базується на аналогії з мозком живих істот. Ключовим елементом цих систем виступає штучний нейрон як імітаційна модель нервової клітини мозку — біологічного нейрона. Цей термін виник при вивченні процесів, які відбуваються в мозку, та при спробі змоделювати ці процеси. Першою такою спробою були нейронні мережі Маккалока і Піттса. Як наслідок, після розробки алгоритмів навчання, отримані моделі стали використовуватися в практичних цілях: в задачах прогнозування, для розпізнавання образів, в задачах керування та інші.
ШНМ являють собою систему з'єднаних між собою простих процесорів(штучних нейронів), які взаємодіють. Такі процесори зазвичай достатньо прості, особливо в порівнянні з процесорами, що використовуються в персональних комп'ютерах. Кожен процесор схожої мережі має справу тільки з сигналами, які він періодично отримує, і сигналами, які він періодично посилає іншим процесорам. І тим не менш, будучи з'єднаними в досить велику мережу з керованою взаємодією, такі локально прості процесори разом здатні виконувати достатньо складні завдання. З точки зору машинного навчання, нейронна мережа являє собою окремий випадок методів розпізнавання образів, дискримінантного аналізу, методів кластеризації тощо З математичної точки зору, навчання нейронних мереж — це багатопараметрична задача нелінійної оптимізації. З точки зору кібернетики, нейронна мережа використовується в задачах адаптивного управління і як алгоритми для робототехніки. З точки зору розвитку обчислювальної техніки та програмування, нейронна мережа — спосіб вирішення проблеми ефективного паралелізму . А з точки зору штучного інтелекту, ШНМ є основою філософської течії коннективізму і основним напрямком в структурному підході з вивчення можливості побудови (моделювання) природного інтелекту за допомогою комп'ютерних алгоритмів. Нейронні мережі не програмуються в звичайному розумінні цього слова, вони навчаються. Можливість навчання — одна з головних переваг нейронних мереж перед традиційними алгоритмами. Технічно навчання полягає в знаходженні коефіцієнтів зв'язків між нейронами. У процесі навчання нейронна мережа здатна виявляти складні залежності між вхідними даними і вихідними, а також виконувати узагальнення. Це означає, що у разі успішного навчання мережа зможе повернути вірний результат на підставі даних, які були відсутні в навчальній вибірці, а також неповних та / або «зашумлених», частково перекручених даних.
1 2 3 4 5