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

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

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

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

Основний алгоритм Гармонійного пошуку

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

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

$\mathbf {HM} ={\begin{bmatrix}x_{1}^{1}&\cdots &x_{n}^{1}&|&f(\mathbf {x} ^{1})\\\vdots &\ddots &\vdots &|&\vdots \\x_{1}^{hms}&\cdots &x_{n}^{hms}&|&f(\mathbf {x} ^{hms})\\\end{bmatrix}}.$

• Крок 2: Згенерувати новий вектор $\mathbf {x} '$. Для кожної компоненти $x_{i}^{'}$,
  • з ймовірністю $hmcr$ (швидкість вибору значення з пам'яті гармонійного пошуку;0 ≤ $hmcr$ ≤ 1), вибрати збережене значення з hm $x_{i}^{'}\leftarrow x_{i}^{int(u(0,1)*hms)+1}$
  • з ймовірністю $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 _{i}^{9}\sum _{j}^{9}{S_{i},_{j}-45}+\sum _{j}^{9}\sum _{i}^{9}{S_{i},_{j}-45}+\sum _{k}^{9}\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 в згенерованому судоку. За допомогою цих двох рішень, ми можемо тепер використовувати гармонійний пошук, щоб знайти рішення (якщо воно існує) до даної судоку.

Області застосування алгоритму

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

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

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

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

• Класторування веб сторінки
• Узагальнення тексту
• Робототехніка

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

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

Застосування алгоритму у інших сферах

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

• Еволюційному моделюванні
• Метаалгоритмах
• Стохастичній оптимізації
• Оптимізація (математика)

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

• Еволюційний алгоритм, включаючи:
  • Генетичні алгоритми
• алгоритми Колективного інтелекту, включаючи:
  • Мурашиний алгоритм
  • Метод рою часток

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

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

Див. також

• Еволюційний алгоритм
• Колективний інтелект

Література

Загальна інформація

• Сайт алгоритму: Harmony Search Algorithm [Архівовано 22 серпня 2009 у Wayback Machine.]
• Book 1 Music-Inspired Harmony Search Algorithm, Springer 2009 [Архівовано 19 січня 2010 у Wayback Machine.]
• Book 2 Recent Advances in Harmony Search Algorithm, Springer 2010 [Архівовано 31 липня 2010 у Wayback Machine.]
• Book 3 Harmony Search Algorithms for Structural Design Optimization, Springer 2009
• Book 4 Optimal Design of Water Distribution Networks Using Harmony Search, LAP 2009
• Book 5 Engineering Optimization: An Introduction with Metaheuristic Applications, Wiley 2010 [Архівовано 25 лютого 2012 у Wayback Machine.]
• Book 6 Clever Algorithms: Nature-Inspired Programming Recipes, Lulu.com 2011 [Архівовано 15 лютого 2012 у Wayback Machine.]

Теорія гармонійного пошуку

• Original Harmony Search: Geem ZW, Kim JH, and Loganathan GV, A New Heuristic Optimization Algorithm: Harmony Search [Архівовано 10 червня 2010 у Wayback Machine.], Simulation, 2001.

• Stochastic Partial Derivative: Geem ZW, Novel Derivative of Harmony Search Algorithm for Discrete Design Variables, Applied Mathematics and Computation, 2008.

• Ensembled Harmony Search: Geem ZW, Improved Harmony Search from Ensemble of Music Players^{[недоступне посилання з листопадаа 2019]}, Lecture Notes in Artificial Intelligence, 2006.

• Continuous Harmony Search: Lee KS and Geem ZW, A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice, Computer Methods in Applied Mechanics and Engineering, 2005.

• Exploratory Power of Harmony Search: Das S, Mukhopadhyay A, Roy A, Abraham A, Panigrahi BK, Exploratory Power of the Harmony Search Algorithm: Analysis and Improvements for Global Numerical Optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 41(1), 2011.

• Improved Harmony Search: Mahdavi M, Fesanghary M, and Damangir E, An Improved Harmony Search Algorithm for Solving Optimization Problems, Applied Mathematics and Computation, 2007.

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

• Hybrid Harmony Search: Fesanghary M, Mahdavi M, Minary-Jolandan M, and Alizadeh Y, Hybridizing Harmony Search Algorithm with Sequential Quadratic Programming for Engineering Optimization Problems [Архівовано 7 жовтня 2008 у Wayback Machine.], Computer Methods in Applied Mechanics and Engineering, 2008.

• Parameter-Setting-Free Harmony Search: Geem ZW and Sim K-B, Parameter-Setting-Free Harmony Search Algorithm, Applied Mathematics and Computation, 2010.

• Multiobjective Harmony Search Algorithm Proposals: Juan Ricart, Germán Hüttemann, Joaquín Lima, Benjamín Barán. Multiobjective Harmony Search Algorithm Proposals, Electronic Notes in Theoretical Computer Science, 2011.

Застосування у інформатиці

• Music Composition: Geem, Z. W. and Choi, J. Y. Music Composition Using Harmony Search Algorithm^{[недоступне посилання з листопадаа 2019]}, Lecture Notes in Computer Science, 2007.

• Sudoku Puzzle: Geem, Z. W. Harmony Search Algorithm for Solving Sudoku^{[недоступне посилання з листопадаа 2019]}, Lecture Notes in Artificial Intelligence, 2007.

• Tour Planning: Geem, Z. W., Tseng, C. -L., and Park, Y. Harmony Search for Generalized Orienteering Problem: Best Touring in China^{[недоступне посилання з листопадаа 2019]}, Lecture Notes in Computer Science, 2005.

• Visual Tracking: J. Fourie, S. Mills and R. Green Visual tracking using the harmony search algorithm, Image and Vision Computing New Zealand, 2008 . 23rd International Conference

• Visual Tracking: Jaco Fourie, Steven Mills, Richard Green, Harmony Filter: A Robust Visual Tracking System Using the Improved Harmony Search Algorithm^{[недоступне посилання з серпня 2019]}, Image and Vision Computing (2010), doi:10.1016/j.imavis.2010 .05.006

• Visual Correspondence: J. Fourie, S. Mills and R. Green Directed correspondence search: Finding feature correspondences in images using the Harmony Search algorithm, Image and Vision Computing New Zealand, 23-25 Nov. 2009 . 24rd International Conference

• Image Deconvolution: J. Fourie, S. Mills and R. Green Counterpoint Harmony Search: An accurate algorithm for the blind deconvolution of binary images, Audio Language and Image Processing (ICALIP), 2010 International Conference on, Shanghai, China

Застосування у інженерії

• 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.

• Structural Design: Lee, K. S. and Geem, Z. W. A New Structural Optimization Method Based on the Harmony Search Algorithm, Computers & Structures, 2004.

• Structural Design: Saka, M. P. Optimum Geometry Design of Geodesic Domes Using Harmony Search Algorithm, Advances in Structural Engineering, 2007.

• Water Network Design: Geem, Z. W. Optimal Cost Design of Water Distribution Networks using Harmony Search, Engineering Optimization, 2006.

• Vehicle Routing: Geem, Z. W., Lee, K. S., and Park, Y. Application of Harmony Search to Vehicle Routing, American Journal of Applied Sciences, 2005.

• Ground Water Modeling: Ayvaz, M. T. Simultaneous Determination of Aquifer Parameters and Zone Structures with Fuzzy C-Means Clustering and Meta-Heuristic Harmony Search Algorithm, Advances in Water Resources, 2007.

• Soil Stability Analysis: Cheng, Y. M., Li, L., Lansivaara, T., Chi, S. C. and Sun, Y. J. An Improved Harmony Search Minimization Algorithm Using Different Slip Surface Generation Methods for Slope Stability Analysis, Engineering Optimization, 2008.

• Energy System Dispatch: Vasebi, A., Fesanghary, M., and Bathaeea, S.M.T. Combined Heat and Power Economic Dispatch by Harmony Search Algorithm, International Journal of Electrical Power & Energy Systems, 2007.

• Offshore Structure Mooring: Ryu, S., Duggal, A.S., Heyl, C. N., and Geem, Z. W. Mooring Cost Optimization via Harmony Search^{[недоступне посилання з липня 2019]}, Proceedings of the 26th International Conference on Offshore Mechanics and Arctic Engineering (OMAE 2007), ASME, San Diego, CA, USA, June 10-15 2007.

• Hydrologic Parameter Calibration: Kim, J. H., Geem, Z. W., and Kim, E. S. Parameter Estimation of the Nonlinear Muskingum Model using Harmony Search^{[недоступне посилання з липня 2019]}, Journal of the American Water Resources Association, 2001.

• Satellite Heat Pipe Design: Geem, Z. W. and Hwangbo, H. Application of Harmony Search to Multi-Objective Optimization for Satellite Heat Pipe Design, Proceedings of US-Korea Conference on Science, Technology, & Entrepreneurship (UKC 2006), CD-ROM, Teaneck, NJ, USA, Aug. 10-13 2006.

• Dam Scheduling: Geem, Z. W. Optimal Scheduling of Multiple Dam System Using Harmony Search Algorithm^{[недоступне посилання з листопадаа 2019]}, Lecture Notes in Computer Science, 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.

• Heat exchanger design: Fesanghary, M., Damangir, E. and Soleimani, I . Design optimization of shell and tube heat exchangers using global sensitivity analysis and harmony search, Applied Thermal Engineering, In press.

• Heat exchanger design: Doodman, A., Fesanghary, M. and Hosseini, R. A robust stochastic approach for design optimization of air cooled heat exchangers [Архівовано 29 вересня 2008 у Wayback Machine.], Applied Energy, In press.

• Heat exchanger network design: Khorasani, R.M., Fesanghary, M. A novel approach for synthesis of cost-optimal heat exchanger networks, Computers and Chemical Engineering, In press.

• Face milling: Zarei, O., Fesanghary, M., Farshi, B., Jalili Saffar, R. and Razfar, M.R. Optimization of multi-pass face-milling via harmony search algorithm, Journal of Materials Processing Technology, In press.

• Document Clustering:,Mahdavi., M., Chehreghania, H., Abolhassania, H., Forsati, R. Novel meta-heuristic algorithms for document clustering, AMC Journal

• Multicast Routing: Forsat, R., Haghighat, M., Mahdavi, M.,Harmony search based algorithms for bandwidth-delay-constrained least-cost multicast routing, Computer Communications, Elsevier

Посилання

• Реалізація алгоритму на CoffeeScript(JavaScript)-http://harry.me/2011/05/07/neat-algorithms---harmony-search/
• Реалізація алгоритму на C# — https://sites.google.com/site/fesangharyweb/downloads [Архівовано 14 листопада 2012 у Wayback Machine.]
• Реалізація алгоритму на С++ — https://sites.google.com/site/multiobjectivehs/ [Архівовано 1 квітня 2016 у Wayback Machine.]