Прикладне програмування

Матеріал з USIC Wiki

Перейти до: навігація, пошук

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

Портал:Інформаційні науки

Перелік питань

Зміст

1 Метод Монте-Карло
2 Марковські ланцюги
3 Google page rank
4 Генетичний алгоритм (Genetic Algorithm) – принцип роботи, модифікації
5 Алгоритм мурашиної колонії (Ant colony)
6 Метод відпалу (Simulated annealing)
7 Метод табу (Tabu Search)
8 Рестарт аналіз
9 Метод вектора спада
10 Імунний алгоритм
- 10.1 Загальні відомості
- 10.2 Алгоритм
11 Стохастичний метод гілок та границь (Branch&Bound)
12 Нейронні мережі. (Neural networks) Їх застосування до задач оптимізації

Метод Монте-Карло

Є тут - Метод_Монте-Карло і tut - Monte_Carlo_method

Марковські ланцюги

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

Конкретно

Авторегресивний процес порядку n AR[n]: $X t = a 1 * X t - 1 + a 2 * X t - 2 + ... + a n * X t - n + e t$ Стан $X t$ в часі t лінійно залежить від n попередніх станів і деякого випадкового елемента et. Авторегресивний процес AR[1] $X t = a * X t - 1$ + e_t називається процесом Маркова. Кожен процес Маркова залежить лише від попереднього стану. Починаючи з початкового стану $X 0$ і часу t=0, ланцюг Маркова будується успішними застосуваннями вказаної формули.

Евристика Маркова починає свою роботу в початковій конфігурації і будує ланцюг Маркова шляхом зміни конфігурації. Нехай початкова конфігурація $q 0$ . Міняємо конфігурацію згідно з набором правил на $q 1$ . Постає питання - чи приймати $q 1$ ? Якщо крок $q_0 \to q_1$ приймається, ми запам"ятовуємо конфігурацію $q 1$ , інакше встановлюємо, що $q 1 = q 0$ . Далі аналогічним чином міняємо $q 1$ на $q 2$ і вирішуємо, чи приймати її. Виконуючи такі ітерації, ми будуємо послідовність $q i$ . Оскільки кожен крок залежить лише від двох конфігурацій - поточної і ймовірної, а решта конфігурацій не запам"ятовується, ми будуємо процес Маркова.
Крок - опис того, як можна змінити конфігурацію. Не кожен крок приймається. Кожна евристика має певні правила, які визначають принцип, за яким нова конфігурація g приймається або відхиляється. Евристики Маркова відрізняються вибором правил прийняття. Цей вибір повністю визначається ймовірнісною функцією переходу p(q $\to$ g).

Тривіальні функції прийняття

Random Walk (RW) - найтривіальніша функція прийняття. У цьому випадку сусідня конфігурація, в яку здійснюватиметься перехід, обирається випадковим чином Кожен крок приймається, бо p(q $\to$ g) = 1. RW використовується у випадках, коли нема великих структур у енергетичному просторі.
Жадібний алгоритм - обираємо лише ті кроки, які ведуть до не гірших конфігурацій. Сусідня конфігурація також обирається випадковим чином.

$Δ H$ = H(g) - H(q) - різниця енергій між двома конфігураціями, які беруть участь у перевірці. Тоді p(q $\to$ g) = 1 if $Δ H$ <=0; else 0. Часто використовуються дещо змінені правила: приймаємо лише кроки, які ведуть до покращення, відхиляємо всі кроки, що ведуть до погіршення; кроки, які не міняють стан, обираємо з певною ймовірністю 0..1. Фігня полягає в проблемі локільних мінімумів: алгоритм застрягає в таких мінімумах досить легко.<

Введення контрольного параметра

Контрольний параметр вводиться для того, аби уникнути проблеми локальних мінімумів. При великих значеннях контрольного параметра система приймає майже будь-який хід, незалежно від того, призводить він до погіршення чи покращення (практично, Random Walk). По мірі зменшення контрольного параметру, зменшується і кільість прийняття ходів, які призводять до погіршення. Коли контрольний параметр досягає свого фінального значення (напр. 0), система приймає лише ходи, які призводять до покращення. Таким чином, система прямує до мінімуму і застрягає там. Нагадує метод СИМУЛЮВАННЯ ВІДПАЛУ.
Крім глобального контрольного параметру, можливе використання локального. Він може змінюватися тоді, коли глобальний параметр залишається сталим. Таким чином, можна прогрнати процес оптимізації на певній ділянці, і результат прийняти або відхилити згідно з глобальним параметром.

Підхід теплої ванни

На відміну від вищевказаних моделей, підхід теплої ванни працює таким чином. Розглядаються всі сусідні конфігурації $g i$ поточного рішення q. Для кожної з них рахуються ймовірності переходу p(q $\to$ gi). Нехай P - сума цих ймовірностей. Генерується рівномірно розподілене випадкове число від 0 до 1. Конфігурація $g_{\acute{i}}$ вибирається за нову, якщо $\sum^{i'-1}_{i=1}{p(q \to g_{\text{i}})} < r \times P <= \sum^{\acute{i}}_{i=1}(p(q \to g_{\text{i}}))$
Перевага методу теплої ванни: система завжти перестрибує до нової конфігурації. Динаміка швидша, як в стандартному підході Маркова. Недолік: якщо система перебуває в локальному оптимумі, метод теплої ванни змусить її вийти звідти навіть коли є маленькі перехідні ймовірності до сусідніх конфігурацій.
В загальному випадку, цей метод знаходить гірші результати, як класичний метод.

Google page rank

Загальні відомості

Google PageRank - алгоритм розрахунку авторитетності сторінки, що застосовується системою Google. PageRank - числова величина, що характеризує "важливість" сторінки в Google. Чим більше посилань на сторінку, тим вона "важливіша". Алгоритм може бути застосований до будь-якого набору сутностей із взаємними посиланнями.

Google розцінює кожна посилання сторінки А на сторінку Б як голос А за Б. Чим більш "важливою" є сторінка А, тим більше важить її голос. Кожній сторінці Google присвоює ваговий коефіцієнт з проміжку 0-10. Цей коефіцієнт визначає важливість сайту в системі Google.

Алгоритм

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

Нехай маємо простір з чотирьох сторінок: А, B, C і D. Нехай початковий PR кожного документа - 0.25. В початковому варіанті алгоритму початковий PR для кожної сторінки був 1.

Якщо кожна сторінка B, C і D посилалася лише на А, вони б давали по 0.25 голосів сторінці А. Весь PR у цій системі збиратиметься в А, тому що всі посилання вказують на А. PR(А) = PR(B) + PR(C) + PR(D). Це рівне 0.75.

Далі, припустимо, що B також має посилання на сторінку C, а сторінка D має лінки на всі три сторінки. Значення голосів розділяється між вихідними посиланнями на сторінці. Перерахуємо PR для А: PR(А) = $\frac {\text{PR(B)}}{2} + \frac {\text{PR(C)}}{1} + \frac{\text{PR(D)}}{3}$ . В загальному випадку, PR будь-якої сторінки u виражається так: PR(u)= $\sum_{v \in B_u}{\frac{\text{PR(v)}}{\text{L(v)}}}$ , де L(v) - номалізована кількість вихідних посилань сторінки v.

Фактор затухання

Кожна людина, яка переходить за посиланнями на різні сайти, врешті-решт зупиниться. Ймовірність (на будь-якому кроці), що людина продовжить переходити за посиланнями - фактор затухання d. Експериментально встановлено, що він знаходиться поблизу значення 0.85. Отож, наша формула набуде вигляду: PR(A) = $\frac{1-d}{N} + d(\frac{\text{PR(B)}}{L(B)} + \frac{\text{PR(C)}}{L(C)} + ...)$ , де N - кількість документів у наборі. PageRank великою мірою залежить від PageRank інших сторінкок. Фактор затухання дещо понижує це значення. Google перераховує PageRank сторінок кожного разу, коли відбувається цикл "Google Dance". По мірі того, як збільшується кількість сторінок в системі, зменшується початкове значення PageRank для всіх документів.

Дана формула емулює роботу уявного користувача, який випадковим чином переходить за посиланнями. PageRank відображає ймовірність того, що цей користувач перейде на сторінку, клікаючи на посилання. Це може бути зображено як марковський ланцюг, в якому станами є сторінки, а переходи всі рівноможливі і є посиланнями між сторінками. Якщо сторінка не має посилань на інші сторінки, вона перериває процес випадкового переходу за посиланнями. Вихід такий - при потраплянні на таку сторінку, користувач рендомом обирає інший УРЛ і продовжує процес. PR(pi) = $\frac{1-d}{N} + d * \sum_{p_j \in \text{M}(p_i)}(\frac{\text{PR}(p_j)}{\text{L}(p_j)}$ ), де $p 1, p 2,... p N$ - сторінки, що розглядаються, $M(p i)$ - набір сторінок, які посилаються на $p i$ , $L(p j)$ - кількість вихідних посилань на сторінці $p j$ , N - загальна кількість сторінок.

Генетичний алгоритм (Genetic Algorithm) – принцип роботи, модифікації

Алгоритм мурашиної колонії (Ant colony)

Метод відпалу (Simulated annealing)

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

Ідея

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

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

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

Визначення

Сусіди стану називаються ходами-кандидатами. Ймовірність виконання переходу з поточного стану s до стану-кандидату s' визначається функцією ймовірностей прийняття P(e, e', T), e = E(s), e' = E(s'), Т - температура:

Р ненульова, навіть коли е > е'
Коли Т -> 0, то і P(e, e', T), коли е' > e, теж прямує до 0. Коли е' < e - навпаки
Р часто обирається таким чином, щоб ймовірність прийняття кроку зменшувалася, коли різниця e' - e збільшується (менші кроки до зростання більш імовірні, аніж більші)
Грубо кажучи, зміна стану чутлива до великих коливань енергії, коли температура Т велика, і до більш дрібних коливань, коли Т мала.

Розклад відпалу

Розклад відпалу - план пониження температури протягом процесу симулювання. Визначається користувачем Спочатку Т присвоюється дуже велике значення (можливо, нескінченність) Кінцева умова розкладу - Т = 0.

Псевдокод

s:=s0; e:=E(s)

sb:=s; eb:=e
k:=0
while k<kmax and e>emax
sn:=neighbours(s)
en:=E(sn)
if en<eb
sb:=sn; eb:=en
if P(e, en, temp(k/kmax))>random()
s:=sn; e:=en
k:=k+1
return sb

початковий стан та енергія

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

Вибір параметрів. Рекомендації

Простір станів
Цільова функція енергії Е()
Функція генерування кандидата neighbour()
Функція ймовірності прийняття Р()
Розклад відпалу temp()

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

P(e, e', T) = 1, e'<=e; $\frac{e'-e}{T}$ , e'>e

Перезапуски. Інколи краще повернутися до розв'язку, який був значно кращий, ніж завжди рухатися від поточного стану. Це називається перезапуском:
- s = sb, e = eb
- Перезапускаємо розклад відпалу

Метод табу (Tabu Search)

Рестарт аналіз

Метод вектора спада

Імунний алгоритм

Загальні відомості

Невідомий оптимальний розв'язок є ідеальним антитілом, яке найкраще розпізнає антиген, тобто найкраще розв'яже проблему оптимізації. Допустимі, але не оптимальні, розв'язки задачі є антитілами, в ході роботи алгоритму імунної оптимізації вони еволюціонують, щоб краще розпізнати патоген, тобто краще задовольнити проблемі задачі. Мірою оптимальності розв'язку є Affinity (біол. "схожість"), тобто наскільки антитіло добре розпізнає патоген. Імунний Алгоритм (ІА) - це один з наближених оптимізаційних алгоритмів, які імітують імунну систему живого організму. Його можна застосувати до алгоритму евристичного пошуку для знаходження наближеного розв'язку нелінійних оптимізаційних проблем. Пошуковий процес імунного алгоритму схожий зі схемою генетичного алгоритму (ГА). Імунний алгоритм має декілька характеристик, які роблять його кращим за генетичний в пошуку розв'язків. Головними характеристиками імунного алгоритму є комірки імунної пам'яті та різноманітність кандидатів на розв'язок. Вони мають забезпечити ефективний пошук розв'язку та уникнути падінь у локальні оптимальні розв'язки.

Алгоритм

[Крок 1] Визначення проблеми: антиген та антитіло визначаються відповідно до поставленої оптимізаційної задачі. Антиген відповідає цільовій функції, антитіло відповідає розв'язку задачі.
[Крок 2] Створення початкової групи антитіл: формується початкова група антитіл. Кожне антитіло в початковій групі створюється випадково.
[Крок 3] Обчислення "ефективності" кожного антитіла: обчислюється "ефективність" кожного антитіла відносно антигену. Вона відповідає ефективності боротьби антитіла проти антигену. Більше того обчислюється "схожість" між двома антитілами. Вона відповідає "близькості" двох антитіл.
[Крок 4] Поновлення комірки пам'яті: антитіло, яке має найбільшу ефективність, заноситься до комірки пам'яті, воно витісняє з пам'яті антитіло яке є найбільш "близьким" до нього.
[Крок 5] Вибір антитіл для відновлення: антитіла, які відновлюються у наступному поколінні вибираються довільно. Ймовірність відновлення для кожного антитіла відповідає його "ефективності". В цьому процесі високі ймовірності призначаються антитілам, які мають високу "ефективність" відносно антигену та низьку близькість з іншими антитілами. Ймовірність відновлення обчислюється наступним чином:
$e_v=\frac{ax_v}{c_v}$ ;
$c_v=\frac{1}{p}*\sum^{p}_{w=1}{ac_{v,w}};$
$a c v, w = 1$ if $a y v, w$ >= Tacl else 0;
$a x v$ - ефективність антитіла v до антигена
$a y v, w$ - близькість розв"язків v i w
p - кількість антитіл у групі
Tacl - означає важливість близькості в оцінюванні антитіл
[Крок 6] Схрещування та мутація: декілька пар антитіл схрещуються для створення нових антитіл. Цей процес носить характер обміну інформацією. Більше того мутація застосовується до кожного гена антитіла з певною ймовірністю. Таким чином формується нова група антитіл.
[Крок 7] Обчислення цільової функції: значення цільової функції обчислюються для всіх антитіл.
[Крок 8] Поновлення групи антитіл: щоб запобігти зупинки у певному локальному оптимумі, виконується поновлення групи антитіл кожні 50 ітерацій. Частина антитіл в групі заміняється на антитіла вибрані з комірки пам'яті.
[Крок 9] Перевірка критерію збіжності: кроки 3-8 повторяються доки не задовольняється критерій збіжності чи кількість ітерацій перевищує ліміт. Якщо задовольняється критерій збіжності, то антитіло, яке має найкращу "ефективність" по відношенню до антигену визнається як наближений розв'язок проблеми.

Стохастичний метод гілок та границь (Branch&Bound)

Загальна ідея

Загальна ідея – пошук max та min f(x) на множині допустимих значень x, де f(x) та x мають довільну природу

В основу метода гілок і границь покладено той факт, що для отримання розв’язку задачі оптимізації на деякій допустимій множині можна розбити дану множину на підмножини, знайти розв’язок задачі на кожній з підмножин і у якості відповіді взяти найкращий з отриманих розв’язків, у відповідності з критерієм якості задачі (найбільшим чи найменшим значенням цільової функції). Розвиваючи описану ідею можна прийти до висновку, що замість знаходження точного розв’язку задачі на підмножині (що може бути надзвичайно складно) можна знаходити лише його оцінку, а потім уточнювати її шляхом подрібнення складових підмножин. Іншою особливістю методу є можливість відкидання так званих «безперспективних» підмножин, тобто підмножин, на яких гарантовано не може бути розв’язку вихідної задачі. Фізично метод складається з двох процедур: процедура розгалуження та процедура знаходження оцінок(границь)/процедура обмеження

Процедура розгалуження (розбиття)

Область можливих рішень $S={S_1, S_2 \dots S_n}$ , де $S i$ також можна розбити на підмножини $S_i={S_{i1}, S_{i2} \dots S_{i3}}$ , причому $min f (x)$ на $S = \min {v_1, v_2 \dots v_n}$ , де $\forall v_i=\min f(x)$ для $S i$

Рекурсивний виклик процедури розбиття створює дерево пошуку (дерево гілок та границь) де вузлами дерева є побудовані підмножини S

Процедура оцінки

Шукає верхні та нижні границі (оцінки) для оптимального значення на підмножині допустимих рішень S
Основна ідея для задачі мінімізації: якщо нижня границя підмножини А більша ніж верхня границя деякої іншої вже розглянутої підмножини B, то А можна викреслити з подальшого розгладу – правило відсіву
global m – мінімальна з отриманих верхніх оцінок
Будь-який вузол дерева для якого $\lim_{znyzu} S_i >m$ виключається з подальшого розгладу Якщо нижня межа вузла дорівнює верхній (абослютно чи з певною точністю), то це є мінімумом функції і досягається на відповідній підмножині

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

Алгоритм гілок та границь працює за наступною схемою:

Крок 0. Початкове розбиття допустимої множини на декілька підмножин і обрахунок

для кожної з них оцінок зверху і знизу мінімального значення цільової функції.

Крок 1. Визначення рекордної підмножини шляхом відшукання найменшої серед

оцінок знизу на підмножинах.

Крок 2. Перевірка умови зупинки алгоритму шляхом порівняння різниці між оцінками

зверху і знизу на черговій рекордній підмножині з заданою точністю  . Якщо точність досягнута, то перехід до кроку 6.

Крок 3. Розбиття рекордної підмножини на нові підмножини, і обчислення оцінок

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

Крок 4. Визначення найменшої оцінки зверху на підмножинах і відкидання тих

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

Крок 5. Перехід до кроку 1.
Крок 6. В якості відповіді можна взяти центр ваги поточної рекордної підмножини.

Ефективність методу

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

Використання методу

Паралельне та розподілене обчислення (програмування)

NP-важкі задачі (псевдополіноміальні задачі):

Задача про комівояжера
Задача про рюкзак
Лінійне/нелінійне програмування
Пошук найближчого сусіда

Евристичні задачі (альфабета відтинання – ігрові задачі)

Нейронні мережі. (Neural networks) Їх застосування до задач оптимізації

Прикладне програмування

Матеріал з USIC Wiki

Зміст

Метод Монте-Карло

Марковські ланцюги

Конкретно

Тривіальні функції прийняття

Введення контрольного параметра

Підхід теплої ванни

Google page rank

Загальні відомості

Алгоритм

Фактор затухання

Генетичний алгоритм (Genetic Algorithm) – принцип роботи, модифікації

Алгоритм мурашиної колонії (Ant colony)

Метод відпалу (Simulated annealing)

Ідея

Визначення

Розклад відпалу

Псевдокод

Вибір параметрів. Рекомендації

Метод табу (Tabu Search)

Рестарт аналіз

Метод вектора спада

Імунний алгоритм

Загальні відомості

Алгоритм

Стохастичний метод гілок та границь (Branch&Bound)

Загальна ідея

Процедура розгалуження (розбиття)

Процедура оцінки

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

Ефективність методу

Використання методу

Нейронні мережі. (Neural networks) Їх застосування до задач оптимізації

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти