Програмне забезпечення інтелектуальних систем-2

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Клітинна модель самовідтворення. Конфігурація райського саду

Клітинна або стільнико-подібна структура визначається як п'ятірка:

(N, T, S, q₀, f)

• N - додатнє ціле, розмір простору
• T - власне стільники, розбиття n-вимірного евклідового простору на комірки
• S - скінченна множина станів

Кожна комірка - це n-вимірний одиничний куб з цілочисловими координатами центру

• q₀ - стан спокою
• f - функція, яка відображає множину ставнів комірки та її сусідів в момент часу t-1 у стан комірки в момент t

Сусідами комірки є всі ті комірки, включаючи і її саму, кожна координата збігається не більше ніж на одну

Функція f має бути однаковою для всіх комірок на площині. Функція повинна бути такою, що якщо всі комірки в часі t-1 знаходяться в стані спокою, то сама комірка переходить в стан спокою в момент t

В початковий момент часу t₀ всі комірки, за виключенням скінченної кількості, перебувають в стані спокою.

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

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

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

Конфігурація - це машина, здатна сама себе відтворювати

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

Конфігурації С називається копією конфігурації С', якщо існує перенесення площини, яке переводить блок С в блок С', так що кожна комірка блоку С має той же стан, що й відповідна комірка в блоці С'

Конфігурація С* містить n-копій конфігурацій С, якщо у блока С* існує n-підмножин, що не перетинаються, кожна з яких є копією блоку С.

Конфігурація райського саду

Конфігурація райського саду - конфігурація, яка існує тільки в момент часу t=0

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

Жодна конфігурація, яка містить конфігурацію райського саду не буде здатна до самовідтворенння

Модифікації алгоритму зворотнього поширення помилки

1. Введеня інертного члена

• Δw_ij(n + 1) = ησ_jo_j + αΔw_ij(n)
• w_ij(n + 1) = w_ij(n) + Δw_ij(n + 1)

2. Згладжування

• w_ij(n + 1) = (1 − α)σ_jo_i + αΔw_ij(n)
• w_ij(n + 1) = w_ij(n) + ηΔw_ij(n + 1)
• α приблизно дорівнює 1 і з часом зменшується до 0

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

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

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

Приклади:

• метод відпалу
• метод Коші

Недоліки алгоритму зворотнього поширення помилки

Основний недолік - невизначено тривалий термін навчання може ніколи не навчитись

1) параліч мережі - величина вагових коефіцієнтів стає дуже великою

net_j - може стати великим, значення похідної буде дуже малим

Щоб запобігти паралічу мережі використовуються різні евристики

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

2. обмеження діапазону зміни вагових коефіцієнтів

3. рандомізація ваг тих нейронів що опинилися в стані насичення

$w_{ij}^{new}=\frac{-5+10}{1+e^{-\frac{w_{ij}}{S}}}, (-5; 5)$

2. припинення поточного процесу навчання та запуск із новими ваговими коефіцієнтами на початку S - велике а потім поступово зменшується

Штучне життя: визначити два підходи, напрями дослідженнь

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

Мета Штучного Життя - розробити універсальну теорію життя

Кріс Лантон - сильне штучне життя (ШЖ, створення людиною нових форм)

Сильне Штучне Життя - розглядає створення істоти як реалізацію життя, слабке ШЖ розглядає створення істоти як моделювання життя.

Основні напрями:

1) Еволюційні алгоритми

2) Синтез ... про поведінку

3) Штучна хімія

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

Паралельна реалізація генетичного алгоритму

Типи паралельних ГА.

1) ПГА1 - параметри ГА на основі популяції (глобальні ГА)

Ці алгоритми використовують модель фермер-робітник

2) ПГА2 - ГА на основі підпопуляції (острівна модель)

Переваги:

1) Ймовірність зупинки в локальному оптимумі є меншою

2) середовище острівного типу є більш захищеним від збоїв

Параметри ПГА2:

• обмеження на мінімальний розмір популяції
• степінь обміну індивідумами
• структура міграції індивідумів між популяціями (кожен з кожним - зірка)

Через певний час відбувається кросинговер між популяціями

• Топологія зв'язків між популяціями:

1)кільце

2)повний граф

3) суміжна топологія

2а) ПГА2 - гібридний підхід:

розпаралелення на підпопуляції. Кожна підпопуляція розпаралелюється на основі глобльного підходу.

3)ПГА3 - на основі індивідів (дифузійна модель)

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

Алгоритм відпалу і оптимізаційна задача

Алгоритм відпалу

Основою процесу є керування графіком охолодження

Завжди тримаємо поточний та робочий розв'язки.

Схема:

1. Створити початковий розв'язок

T=const(100), N- кількість ітерацій при заданій температурі

2. Скопіювати початковий розв'язок в поточний розв'язок

3. Оцінити поточний розв'язок

4. u:=0

5. Скопіювати поточний розв'язок в робочий розв'язок

6. Змінити робочий розв'язок випадковим чином

7. Оцінити новий розв'язок

8. Якщо робочий розв'язок кращий за поточний, то скопіювати робочий розв'язок в поточний і перейти на крок 10. Інакше перейти на крок 9.

9. Критерій допуску на крок 5.

10. Якщо u<N, то n++, перейти на крок 5, інакше на крок 11.

11. Зменшення Т, перейти на крок 4.

T_i+1=αT_i, 0<α<1, 0,8 ≤ α ≤ 0,99

Оцінка розв'язку складається з декодування розв'язку та зведені до мінімуму енергетичної функції (виражає відхилення розв'язку від шуканого)

• E_{робочий} < E_{поточний} - приймаємо поточний за робочий
• $P(\Delta E)=e^{-\frac{\Delta E}{T}}$ - ймовірність прийняття поганого розв'язку.
• ΔE = E_{робочий} - E_{поточний} > 0

Роєвий інтелект. Оптимізація часток роєм і модифікації алгоритму

Оптимізація часток роєм

PSO (particle swarm optimization)

Агенти розпорошуються в просторі.

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

0) Кодування розв'язків.

1) Ініціалізація.

2) Ітераційний процес для кожної частки:

2.1) Обчислення функції здоров'я та модифікіція локального та голобального найкращих розв'язків.

2.2) Обчислення вектора швидкості.

2.3) Обчислення нової позиції.

2.4) перехід на пункт 2.1.

3.) Завершення роботи

• $X_i=(x_{i1}, x_{i2}, \dots, x_{iN})$ - точка в N-вимірному просторі
• $V_i=(v_{i1}, v_{i2}, \dots, v_{iN})$ - вектор швидкості
• $P_i=(p_{i1}, p_{i2}, \dots, p_{iN})$ - локальний найкращий розв'язок

• $G=(g_1, g_2, \dots, g_N)$ - глобальний найкращий розв'язок (max p_i)

1. Координати генеруються випадковим чином (x-рівномірно, v=0)

$f(x_i) > f(p_i) \Rightarrow p_i:=x_i$

$f(x_i) > f(G) \Rightarrow G:=x_i$

 : $V_{m_i}^{new}=V_{m_i}^{old} + \Gamma_1 \times r_1(p_{m_i}-x_{m_i}^{old})+ \Gamma_2 \times r_2(g-x_{m_i}^{old})$

• r₁,r₂ - незалежны випадковы величини рівномірно розподілені в [0, 1]
• Γ₁,Γ₂ - навчальні множини

Γ₁ - когнітивний параметр (контролює вплив пізнавальної компоненти)

Γ₂ - соціальний параметр (вплив соціальної компоненти)

$\Gamma_1, \Gamma_2 \approx 2$

$X_{m_i}^{new}=V_{m_i}^{old} +V_{m_i}^{new})$

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

Модифікація алгоритму

(стохастичність вносить невизначеність, r1, r2 випадкові)

1) $| V_{m_i} | < V_{max}$

2) обмежена множина допустимих розв'язків.

- підхід поглинають стіни

- якщо частка дійшла φ межі, то її швидкість обнуляється = підхід відштовхують стіни

- підхід поглинають стіни

3) введення інерційної ваги

$V_{m_i}^{new}=w \cdot V_{m_i}^{old} + \Gamma_1 \cdot r_1(p_{m_i-x_{m_i}^{old}}) +\Gamma_2 \cdot r_2 (g_i -x_{m_i}^{old})$

4) введення стискаючого множника

5) $V_{m_i}^{new}=V_{m_i}^{old} + \Gamma_1 \cdot r_1(p_{m_i-x_{m_i}^{old}}) +\Gamma_2 \cdot r_2 (g_i -x_{m_i}^{old}) + \Gamma_3 \cdot r_3 (p_{l_i}-x_{m_i}^{old})$

• $p_{l_i}$ - найкращий сусід

6) бінарний варіант алгоритму

простір розв'язків кодується бінарними значеннями

Значення V max так само, як і в звичайному.

$S(V_{m_i})=\frac{1}{1+e^{-V_{m_i}}}$

$x_{m_i}=1$.

шуидкість - ймовірність набуття біноміального значення.

Еволюційне програмування

Пошук розв'язків не на рівні фенотипу, а на генотипу.

Використовується лише оператор мутації

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

0) Кодування

1) Ініціалізація

1.1) Оцінка для мутації

2) Моделювання еволюційного процесу (репродукція)

2.1) Застосування генетичних операторів (рекомбінація)

2.2)Оцінювання

2.3) Відбір

2.4)Перехід на пункт 2.1

3) Завершення роботи.

Всі члени популяції можуть брати участь у породженні нащадків:

F:Rⁿ -> R

Простий генетичний алгоритм

0: двійкове кодування послідовностей фіксованої довжини

1: Початкова популяція |P|=n

2: Ітерація

2.1: $\forall x: f(x) \ge 0, max f(x)$ Якщо виконується умова зупинки, то переходимо на крок 3

2.1.2: Генерується популяція батьків |P|=n, для відбору використовується метод "рулетки": $P(x)=\frac{f(x)}{\Sigma f(x)}$- кожна хромосома відбирається в батьківський пул з ймовірністю функції пристосованості.

$n=N \frac{f(x_j)}{x}$-очікувана кількість копій в батьківському пулі

2.2:

2.2.1: кросинговер

P з використанням одноточкового кросинговера

Точка схрещування випадково з [1; l-1]. Кожна пара обмінюється частинами з ймовірністю P_c

2.2.2: З P енеруємо P шляхом застосування щільнісної мутації з ймовірністю P_m

Параметри алгоритму P_c, P_m:

• 0,5 ≤ P_c ≤ 1
• 0 ≤ P_m ≤ 0,1

2.2.3: Перейти на 2.1.1

3: Заверешення роботи, вибір найкращої хромосоми

Генетичні алгоритми в задачах багатокритеріальної оптимізації

$\begin{cases} y_k=f_k(x) \to max\\ k=1 \dots m, m>1\\ x \in X \in R \end{cases} x, x' \in R^n$

Визначення1 (домінування Парето)

Вектор x' домінується в смислі Парето з x:

$x {}^p > x' <=> \forall i=\overline{1, n} | x_i \ge x_i' and \exist j: x_j>x_j'$

(13246)^p > (12246)

(2489)^p > (1379)

Визначення 2

Розв'язок х' домінується в смислі Парето з x

$x {}^p > x' <=> \forall i=\overline{1, m} f_i(x) \ge f_i(x') and \exist j: f_j(x)>f_j(x')$

Визначення 3

Розв'язок x називається парето-оптимальним (оптимальним в смислі Парето) якщо він не домінується жодним іншим розв'язком.

Приклади

$f_1(x,y)=x \to max$

$f_2(x,y)=y \to max$

Методи критеріальної оптимізації:

1) Метод зваженої функції

2) Метод послідовних поступок - критерії ранжуються, шукається max по f₁

3) Метод послідовних обмежень:

$f'=(f_1' \dots f_m')$ - ідеальний вектор

Далі шукаємо максимум зваженої суми. Якщо кожний критерій сильно відрізняється від суми, то ми будемо шукати суму з певними обмеженнями на k.

4)метод одночасних обмежень

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

Популяція розбивається на m- підпопуляцій однакового розміру.

Кожна підпопуляція відповідає за свою функцію пристосованості.

Селекція проводиться автономно для кожної групи.

Кросинговер виконується між групами.

Генетичні алгоритми - застосування

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

Алгоритми ніш та видів і генетичний алгоритм у комбінаторних задачах

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

Для відбору використовується не тільки функція пристосованості, а й розподіл особин в просторі пошуку.

S(d_ij)- функція співучасті - функція визначає рівень близькості на степінь співучасті для кожної хромосоми в популяції.

d_ij - міра відстані між хромосомами x_i та xd_j (може бути введена у просторі генотипу та фенотипу)

$d_{ij}=\sqrt{\sum_{k=1}^{p}\frac{(x_i^k-x_j^k)}{(x_{max}^k-x_{min}^k)^2}}$ - у просторі фенотипу

x_i: x_i¹, x_i², ..., x_i^p (i-та хромосома що кодує p параметрів)

Умови, що накладаються на функцію співучасті:

1) $\forall d_{ij}, 0 \le S(d_{ij}) \le 1$

2) S(0) = 1

3) $\lim_{d_{ij} \to \infty}S(d_{ij})=0$

Вводять ще параметр σ - розмір ніші та накладають $\forall d_{ij} > \sigma , S(d_{ij})=0$

дописати: Picture 64

Теорема схем

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

У випадку бінарного кодування схемою є рядок довжини l.

{0, 1, *}

10**1

10001

10011

10101

10111

Хромомсома належить до даної схеми, якщо для $\forall j \in \overline{1,l}$ символ, що перебуває в j-ій позиції

хромосоми відповідає символу, що міститься в j-ій позиції

хромосоми відповідає символу, що міститься в j-ій позиції схеми.

Порядок схеми - кількість визначених бітів у схемі

O(10**1)=3

O(**01**11)=4

O(*****)=0

O=l-m(*)

Визначальна довжина схеми - відстань між крайніми визначеними бітами схеми

σ(10**1)=4

σ(**01**11)=5

σ(**1**)=0

Пристосованість схеми - це середнє значення пристосованості хромосом що міститься в ній:

$f(H)=\frac{\sum_{x \in \tilde{m}(H)}f(x)}{m(H)}$

$|\tilde{m}(H)|=m(H)$

Схема з високою пристосованістю короткою визначальною довжиною та низьким порядком має більше шансів перейти з покоління в покоління і називається корисною (за Холландом)

• m(H, t) - кількість прикладів схеми H у поколінні t
• $P(H)\frac{f(H)}{\sum_{i=1}^n f(x_i)}=m(H,t) \frac{f(H)}{\overline{f}}$ - ймовірність схеми бути обраною
• $p_c \cdot \frac{\sigma (H)}{l-1}$ - ймовірність що кросинговер зруйнує схему
• 1 − P_m + O(H) - ймовірність того,що мутація не зруйнує схему

Теорема Схем. Простий генетичний алгоритм збільшує кількість корисних схем експоненційно.

$f(H)=\overline{f} \cdot (1+c)$

m(H,t)(1 + c)

Роєвий алгоритм

Взаємодія між індивідами

Ройовий інтелект - методи ШІ в основу яких покладено вивчення колективної поведінки в децентралізованій системі.

Приклад - Алгоритм Мурашки

Генетичне програмування

Особина кодує програму

Основна відмінність - оцінка здоров'я. Треба запустити програму

Треба за виходом (y) та входом (x) відновити F(x)

0 Кодування

Кожна хромосома кодує програму.

Вводяться множини термінальних символів Т та функціональних символів F

• Т складається з проблемно-орієнтовних змінних, констант або директив

• F складається з елементарних функцій, які використовують інші термінальні функції.

Кожна комп'ютерна програма є композиційною функцією з множини F та терміналів з Т

Множини F та Т повинні задовольняти властивості замкненості

Є декілька видів кодування геномів - лінійне, деревовидне.

Кодування геномів у вигляді дерев

Внутрішні вузли - функціональні символи, листки -термінальні символи

T={2,x,y,4,7}

F={+,*,%}

[Зображення:genetic_programming] $2+\frac{4*x}{7}$

1 Ініціалізація

• Корінь - з множини F
• Листя - з множини T

Правила побудови:

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

2. Правило повноти - наперед визначена висота дерева. Весь час обирають функціональні символи, лише на нижньому рівні обирають термінальні символи.

2 Оцінювання

Для оцінювання розв'язку береться середньоквадратична похибка

$f_i=\sqrt{\frac{1}{N-1}\sum_{k=1}^{n}(y_i-t_i)^2}$

• N -розмір тестової вибірки
• y_i - експерементальні дані
• t_i - обраховані дані

3 Генетичні оператори

Основний генетичний оператор - кросинговер

Випадковим чином обирається піддерева (2ох) батьків і відбувається обмін піддеревами

В результаті можлива зміна висоти дерева (довжина хромосоми змінюється)

Особливостікросинговера:

1) дерево саме з собою => отримуємо інше дерево

2) зміна довжини хромосоми

3) щоб запобігти постійному обміну термінальними символами, в якості піддерев брати 10%-терміналів, а 90%-функціональних символів

4) Поява та нокопичення інтронів - ділянок коду, які нічого не роблять (тільки впливають на довжину хромосоми)

$A_i(t+1) \sim A_i(t) \cdot \frac{\Phi(a_i)}{\Phi(t)} \cdot (1-p_i \cdot f \frac{c_l}{c_a} \cdot \frac{a_i}{a_1})$

Мутація -видаляє випадково обране піддерево і замінює його іншим, або просто замінюється листок

p_m << 1

4 Завершення

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

Параметри алгоритму

• розмір популяції
• частота застосування Генетичних операторів
• Генетичні Оператори
• максимальна глибина дерева

Класифікація штучних нейронних мереж

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

За топологією

1) мережі прямого поширення - вихідний сигнал елемента в майбутньому не може повернутися на його вхід

• шарові мережі - нейрони розміщуються в декілька шарів

2) мережі зворотнього поширення (рекурентні мережі) - є зворотні зв"язки (вихідний сигнал може в майбутньому повернутися на вхід).

• повнов"язні мережі - вхідні сигнали подаються на всі нейрони, працюють певну кількість тактів, знімають вихід з певних

• шарово-циклічні мережі - шари замкнені в кільце

• шарово-повнов"язні мережі - кожен з шарів є повнов"язною мережею. Виділяють окремо фази прийому сигналу для кожного шару, обміну сигналами всередині шару і передачу сигналу

• повнов"язно-шарові

За апроксимацією до вирішення заданої задачі

1) мережі що конструюються

2) мережі що навчаються

2.1) ті, що спостерігаються (supervised)

2.2)ті, що не спостерігаються (неконтрольоване навчання)

2.3)гібридні (змішані)

Приклад нейронної мережі, що моделює відношення XOR

$F(net)= \begin{cases} \\1, net>0 \\0, net \le 0 \end{cases}$

• net₃=0*(-1)+1(-1)+1,5=0,5
• net₄=0*(-1)+1*(-1)+0,5=-0,5

F(net₅)=1

F(net₄)=0

• net₅=0*(-1)+1*1+(-0,5)=-0,5

F(net₅)=1

Перцептрони та їх обчислювані можливості

• обчислювальні можливості

Елементарний перцептрон є нейроелементом з n- входами, лінійною функцією стану і пороговою функцією активації

За допомогою елементарного перцептрона можна конструювати базові логічні функції:

• диз"юнкція
• заперечення

В багатьох випадках дозволяє проводити бінарну класифікацію

• маса > 0,8 AND швидкість < 0,55 - бомбардувальник
• маса < 0,9 AND швидкість > 0,25 - винищувач

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

Навчання елементарного перцептрона

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

• Δw_ij = ηx_iy_j - правило Хеба
• η-коефіцієнт норми начання від 0 до 1 керує середньою величиною зміни коефіцієнтів
• Δw_ij - величина, на яку змінюється вага
• x_i - сигнал від і-того нейрону
• y_i - бажана величина активації