Гармонійний пошук

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Алгоритм пошуку гармонії має такі критерії:

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

Основний алгоритм Гармонійного пошуку[ред.ред. код]

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

  • Крок 1: Згенерувати випадкові вектори, стільки, скільки є місця у пам'яті гармонійного пошуку (hms), потім зберегти ці вектори у пам'яті гармонійного пошуку (hm).

\mathbf{HM} =
\begin{bmatrix}
x^1_1 & \cdots & x^1_n & | & f(\mathbf{x}^1)\\
\vdots & \ddots & \vdots & | & \vdots\\
x^{hms}_1 & \cdots & x^{hms}_n & | & f(\mathbf{x}^{hms})\\
\end{bmatrix}.
  • Крок 2: Згенерувати новий вектор \mathbf{x}'. Для кожної компоненти x^'_i,
    • з ймовірністю hmcr (швидкість вибору значення з пам'яті гармонійного пошуку;0 ≤ hmcr ≤ 1), вибрати збережене значення з hm x^'_i \leftarrow x^{int(u(0, 1)*hms)+1}_i
    • з ймовірністю 1-hmcr, вибрати випадкове значення в межах допустимого діапазону.
  • Крок 3: Виконання додаткових робіт, якщо значення в кроці 2 прийшло від hm.
    • з ймовірністю par (крок регулювання швидкості; 0 ≤ par ≤ 1), змінити x^'_i на малу величину: x^'_i \leftarrow x^'_i + \delta чи x^'_i \leftarrow x^'_i - \delta для дискретного значення; чи x^'_i \leftarrow x^'_i + fw \cdot u(-1, 1) для безперервної змінної.
    • з ймовірністю 1-par, нічого не робити.
  • Крок 4: Якщо \mathbf{x}^' краще, ніж найгірший вектор \mathbf{x}^{Worst} у hm, замінити \mathbf{x}^{Worst} на \mathbf{x}'.
  • Крок 5: Повторення з кроку 2 до кроку 4, поки критерій не буде виконано

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

  • hms : Розмір пам'яті гармонійного пошуку. Як правило, варіюється від 1 до 100 . (Стандартне значення = 30)
  • hmcr : Швидкість вибору значення з пам'яті гармонійного пошуку. Як правило, варіюється від 0,7 до 0,99. (Стандартне значення = 0,9)
  • par : Швидкість вибору сусідніх значеннь. Як правило, варіюється від 0,1 до 0,5. (Стандартне значення = 0,3)
  • \delta : Обсяг між двома сусідніми значеннями в дискретному наборі кандидатів.
  • fw (пропускна здатність) : Сума максимальної зміни кроку настройки. Це може бути (0,01 × допустимого діапазону) до (0,001 × допустимого діапазону).

Приклад застосування[ред.ред. код]

Пазл судоку у процессі розв'язання

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

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

  • Зелені комірки не порушують правила
  • Червоні комірки клітин порушують або рядок або стовпець
  • Білі комірки були дані головоломкою
  • Сірі комірки мають тільки одне значення при даному розташуванні зелених та красних комірок

Зелені, сірі та червоні комірки представляють вибір для невідомих комірок.

Далі, ми вирішуємо, як оцінити якість даного рішення. Найочевидніший спосіб для оцінення алгоритму є наступним: підрахувати тільки кількість порушень в головоломці (підрахувати кількість червоних комірок). Оптимальне вирішення це глобальний мінімум функції Q, де Q=\sum^{9}_{i}\sum^{9}_{j}{S_i,_j-45}+\sum^{9}_{j}\sum^{9}_{i}{S_i,_j-45}+\sum^{9}_{k}\sum_{_(i,j)inB^k}{S_i,_j-45}, \,

де S_i,_j — комірка, де i — кількість комірок враховуючи зліва, j — згори, B_k — усі клітини у k-му блоці.

Вища евристична функція дає нам детальнішу міру вирішення оптимального рішення. Вона працює наступним чином: бере суму кожного ряду і віднімає 45, що являє собою суму чисел від 1 до 9. Якщо певний ряд складається з двох 1 замість 1 і 2, сума чисел у рядку не буде 45, і Q не буде мінімальним. Правильне рішення для судоку матиме Q = 0. Важливо бачити, що сума рядків може бути 45, хоча номери в ньому, точно не встановлені ​​від 1 до 9. Наприклад, може статися наступне сума {1,2,2,5,5,6,7,8,9} = 45. Однак, якщо цей випадок має місце в одному рядку, то сума для стовпців, що проходять через ряд, або суму на один з блоків, що містять рядки не буде 45, рухаючи остаточне значення Q від 0, отже, це позначає субоптимальну якість відповідно до наших побажань. Єдиний спосіб щоб отримати в рядку, стовпці і блоці суму 45 — це єдиний варіант мати 1 — 9 в кожному контейнері. Таким чином, ноти для гармонії це множина значень невідомих комірок, а якість гармонії це оцінка функції Q в згенерованому судоку. За допомогою цих двох рішень, ми можемо тепер використовувати гармонійний пошук, щоб знайти рішення (якщо воно існує) до даної судоку.

Області застосування алгоритму[ред.ред. код]

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

Застосування у реальному світі:

  • Оптимальне рішення судоку
  • Планування оптимального розкладу
  • Логістичні проблеми

У Інформатиці:

У електронній інженерії:

  • Системи диспетчеризації
  • Фотоелектронне виявлення
  • Проектування системи живлення
  • Проектування системи мобільного зв'якзу

Застосування алгоритму у інших сферах[ред.ред. код]

Гармонійний пошук може застосовуватися в:

У еволюційних методах:

У метаалгоритмах, включаючи:

Див. також[ред.ред. код]

Література[ред.ред. код]

Загальна інформація[ред.ред. код]

Теорія гармонійного пошуку[ред.ред. код]

  • Particle-Swarm Harmony Search: Omran MGH and Mahdavi M, Global-Best Harmony Search, Applied Mathematics and Computation, 2008 .

Застосування у інформатиці[ред.ред. код]

Застосування у інженерії[ред.ред. код]

  • Fuzzy Data Clustering: Malaki, M.,Pourbaghery, JA, A Abolhassani, H. A combinatory approach to fuzzy clustering with harmony search and its applications to space shuttle data, Proceedings of the SCIS & ISIS,17-21,2008 .
  • Offshore Structure Mooring: Ryu, S., Duggal, A.S., Heyl, C. N., and Geem, Z. W. Mooring Cost Optimization via Harmony Search, Proceedings of the 26th International Conference on Offshore Mechanics and Arctic Engineering (OMAE 2007), ASME, San Diego, CA, USA, June 10-15 2007 .
  • Ecological Conservation: Geem, Z. W. and Williams, J. C. Ecological Optimization Using Harmony Search, Proceedings of American Conference on Applied Mathematics, Harvard University, Cambridge, MA, USA, March 24-26, 2008 .

Посилання[ред.ред. код]