Комп'ютерні моделі ДС. Генетичні алгоритми

Комп’ютерна модель – це імітаційна модель реального процесу або явища, виконана комп’ютерними засобами.

Комп’ютерні моделі

Клітинкові автомати

Нейронні мережі

Генетичні алгоритми

I zUvOT8nMS7dVCg1x07VQUiguScxLSczJz0u1VapMLVayt+PlAgAAAP//AwBQSwMEFAAGAAgAAAAh AIfldmLEAAAA3AAAAA8AAABkcnMvZG93bnJldi54bWxEj8FKw0AQhu+C77CM4M3uVlBq2m0pgljw IKa17XHIjkkwOxuy22x8e+cgeBz++b/5ZrWZfKdGGmIb2MJ8ZkARV8G1XFs47F/uFqBiQnbYBSYL PxRhs76+WmHhQuYPGstUK4FwLNBCk1JfaB2rhjzGWeiJJfsKg8ck41BrN2AWuO/0vTGP2mPLcqHB np4bqr7LixeNsPj0r+V4ym8P8XA0MVfn92zt7c20XYJKNKX/5b/2zll4MmIrzwgB9PoXAAD//wMA UEsBAi0AFAAGAAgAAAAhAASrOV4AAQAA5gEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEACMMYpNQAAACTAQAACwAAAAAAAAAAAAAAAAAxAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEAMy8FnkEAAAA5AAAAEgAAAAAAAAAAAAAAAAAuAgAAZHJz L3BpY3R1cmV4bWwueG1sUEsBAi0AFAAGAAgAAAAhAIfldmLEAAAA3AAAAA8AAAAAAAAAAAAAAAAA nwIAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPcAAACQAwAAAAA= ">

Вступ до генетичних алгоритмів. Генетичні алгоритми є новим напрямком в алгоритмах. Вони здатні не тільки вирішувати та скорочувати перебір в складних задачах, але і легко адаптовуватися до зміни проблеми.

Спочатку ГА–функція генерує визначену кількість можливих рішень, а потім вираховує для кожного "рівень виживання" (fitness) – близькість до істини. Ці рішення дають нащадків. Ті з них, хто є "сильнішими", тобто більше підходять, мають більший шанс до відтворення, а "слабші" поступово відмирають. Іде еволюція.

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

Схема генетичного алгоритму:

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

2. Обчислення коефіцієнта виживання (fitness). Кожному розв'язку (хромосомі) підставляється певне числове значення, залежне від близькості до відповіді.

3. Відтворення. Хромосоми, які мають високу здатність до виживання (fitness), потрапляють до нащадків (які потім можуть мутувати) з більшою вірогідністю. Нащадок, результат злиття "батька" та "матері", являє собою комбінацію їх генів. Цей процес називається "схрещення" або "кросинговер (кросовер)" (crossing over).

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

67.Гра "Життя". Модель Вінера–Розенблюта

Гра "Життя". “Всесвіт” поділено на клітинки, у кожній з яких є або немає життя. У кожний дискретний момент часу стан клітинки визначається станом восьми її сусідів за правилами:

q Пуста клітина, що має 3 “живих” сусіди – “оживає”;

q Якщо сусідів менше двох (“одинокість”), або більше трьох (“перенасе–лення”) “життя” у ній зникає.

Ці прості правила призводять до виникнення величезної кількості різноманітних форм, кожна з яких має дещо спільне з попередньою. На цей час склалася така система їхньої класифікації:

Стійкі фігури – фігури, які залишаються незмінними за кожної ітерації.

Періодичні фігури – фігури, стан яких повторюється через деяку кількість поколінь.

Фігури, що рухаються – фігури, у яких стан повторюється, але з деяким зсувом у просторі.

Гармати – фігури у яких стан повторюється, але кожен цикл вони додатково створюють фігури, що рухаються.

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

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

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

Формально клітинковий автомат визначимо як модель Α (λ, ε, ν, φ), що складається з:

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

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

ν (с) – множина сусідів, які мають вплив на центральну клітину (с);

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

φ: et (ν (с))→ et+1 (с), де eЄ ε.

Клітинковий автомат є імітаційною математичною моделлю, де дискретними є не тільки незалежні змінні, а й шукані розв’язки.

Модель Вінера–Розенблюта. Злагодженість роботи численних механізмів людського організму контролюється нервовою системою за допомогою своєчасної подачі керуючих сигналів у мережі з більш як 14 млрд. клітин–нейронів. Спосіб передачі збудження заснований на наявності у нейрона трьох станів: спокою, активності та рефрактерності. Прийнявши від сусіда сигнал активації, спокійний нейрон збуджується і певний час τ_е передає імпульси іншим сусіднім нейронам. Після цього впадає на час τ_r у стан рефрактерності (відпочинку), у якому не подає і не приймає зовнішних сигналів. За цей час він “відпочиває” і не дає хвилі збудження повернути назад. Далі він знову переходить у стан спокою і готовий до наступної активації.

Рис.11

Змоделюємо мережу нейронів двовимірною чотирикутною регулярною сіткою λ_ij (i=1..x, j=1..y) (рис.11). Стан кожної соти визначається впливом 8–ми найближчих сусідів. Множина ε містить три значення – спокій, збудження та рефрактерність. Стан автомата у кожний момент часу описуватимемо матрицею з наступними правилами переходу:

Перший рядок цих правил задає значення елементів матриці Ф_ij як кількість кроків по часу, які минули від часу збудження відповідного нейрона. Другий рядок визначає, що після збудження та рефрактерності (τ_e+τ_r кроків по часу) елемент переходить у режим спокою. Два наступні рядки вказують на порядок активації нейрона. У розгляд вводиться додаткова матриця u_ij, елементи якої містять рівень активації нейронів, отриманої з сигналами від своїх сусідів. Клітинка автомата активізується тільки після досягнення нею певного порогу збудження h.

Правила зміни рівня рівня активації визначаються наступним чином

,

де q – деякий параметр часової релаксації збудження, а коефіцієнт C_kl визначає величину сигнала активації від сусіда, наприклад у найпростішому випадку:

Оскільки сигнали активації можуть надходити лише від збуджених нейронів, то

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

Збої проходження сигналів у нервовій системі є першопричиною багатьох захворювань людського організму. Частина таких збоїв пов’язана із матеріальними пошкодженнями у нейронній структурі нервової системи і у першу чергу вивчається сучасною медициною. Проте пошкодження керуючої інформації може відбуватись і в абсолютно здоровій нейронній мережі через ті чи інші зовнішні чинники, або, навіть, випадкові флуктуації у нормальній роботі нейронів. Покажемо цей процес на клітинковому автоматі Вінера–Розенблюта.

Чотири верхніх квадрати на рис.12 демонструють проходження плоскої хвилі збудження за рахунок почергової зміни стану нейронів: «спокій» → «збудження» → «рефрактерність» → «спокій». Хвиля рефрактерності «підпирає» ззаду фронт збудження, заставляючи його рухатись вперед. Це нормальний процес передачі сигналу.

Рис. 12. Проходження плоскої хвилі збудження в однорідному нейронному середовищі.

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

Рис.13. Анігіляція автохвиль

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

Відносна простота реалізації клітинкових автоматів спричинила появу значного числа програмних продуктів для розв’язування різноманітних задач. Як приклад наводимо одну з реалізацій автомата Вінера–Розенблюта.

Рис. 14. Програмна реалізація клітинкового автомата Вінера–Розенблюта.

Дата добавления: 2015-05-08