Мета-оптимізація

Концепція метаоптимізації.

В математичній оптимізації, «мета-оптимізація» — це використання одного методу оптимізації аби налаштувати інший метод оптимізації. Одне з перших використань мета-оптимізації було наприкінці 1970х в роботі Мерсера та Сампсона[1], задля знаходження оптимальних параметрів генетичного алгоритму.

В літературі мета-оптимізація та суміжні концепції відомі, як мета-еволюція, супер-оптимізація, автоматизоване калібрування параметрів, гіпер-евристика і.т.д.

Мотивація

Ландшафт продуктивності для диференціальної еволюції.

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

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

Методи

Метаоптимізація диференціальної еволюції.

Простий спосіб знаходження параметрів оптимізатора — імплементація нового оптимізатора, так званого мета-оптимізатора, над параметрами початкового оптимізатора. Є декілька різних підходів до застосування імплементації цього залежно від типу параметрів поведінки (дійсні, дискретні параметри) та функції обчислення ефективності.

Метаоптимізація параметрів генетичного алгоритму була виконана Грефенштеттом[2] і Кіном[3] та іншими дослідниками, а експерименти з метаоптимізацією, як параметрів, так і генетичних операторів були описані Беком.[4] Метаоптимізація алгоритму COMPLEX-RF була виконана Крусом і Андерсоном[5] і[6], де був введений і відбувся подальший розвиток індексу ефективності оптимізації на основі теорії інформації. Метаоптимізація оптимізації роїв часток була виконана Мейснером та ін.[7], Педерсеном і Чіпперфілдом[8] і Мейсоном та ін.[9]. Педерсен і Чіпперфільд застосували метаоптимізацію до диференціальної еволюції[10]. Біраттарі та інші[11][12] виконали метаоптимізацію оптимізації мурашиного алгоритму. Статистичні моделі також використовувалися, щоб дізнатися більше про зв'язок вибору параметрів поведінки та ефективності оптимізації, див., наприклад, Франсуа та Лаверня[13] та Наннена та Ейбена[14]. Сміт і Ейбен провели порівняння різних методів метаоптимізації[15].

Див. також

Примітки

  1. ↑ Mercer, R.E.; Sampson, J.R. (1978). Adaptive search using a reproductive metaplan. Kybernetes. 7 (3): 215—228. doi:10.1108/eb005486.
  2. ↑ Grefenstette, J.J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics. 16 (1): 122—128. doi:10.1109/TSMC.1986.289288. S2CID 23313487.
  3. ↑ Keane, A.J. (1995). Genetic algorithm optimization in multi-peak problems: studies in convergence and robustness. Artificial Intelligence in Engineering. 9 (2): 75—83. doi:10.1016/0954-1810(95)95751-Q.
  4. ↑ Bäck, T. (1994). Parallel optimization of evolutionary algorithms. Proceedings of the International Conference on Evolutionary Computation. с. 418—427.
  5. ↑ Krus, PK.; Andersson (Ölvander), J. (2003). Optimizing optimization for design optimization. Proceedings of DETC’03 2003 ASME Design Engineering Technical Conferences and Computers and Information in Engineering Conference Chicago, Illinois, USA.
  6. ↑ Krus, PK.; Ölvander(Andersson), J. (2013). Performance index and meta-optimization of a direct search optimization method (PDF). Engineering Optimization. 45 (10): 1167—1185. Bibcode:2013EnOp...45.1167K. doi:10.1080/0305215X.2012.725052. S2CID 62731978.
  7. ↑ Meissner, M.; Schmuker, M.; Schneider, G. (2006). Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training. BMC Bioinformatics. 7 (1): 125. doi:10.1186/1471-2105-7-125. PMC 1464136. PMID 16529661.{{cite journal}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом (посилання)
  8. ↑ Pedersen, M.E.H.; Chipperfield, A.J. (2010). Simplifying particle swarm optimization. Applied Soft Computing. 10 (2): 618—628. CiteSeerX 10.1.1.149.8300. doi:10.1016/j.asoc.2009.08.029.
  9. ↑ Mason, Karl; Duggan, Jim; Howley, Enda (2018). A Meta Optimisation Analysis of Particle Swarm Optimisation Velocity Update Equations for Watershed Management Learning. Applied Soft Computing. 62: 148—161. doi:10.1016/j.asoc.2017.10.018.
  10. ↑ Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PDF) (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group. S2CID 107805461. Архів оригіналу (PDF) за 13 лютого 2020.
  11. ↑ Birattari, M.; Stützle, T.; Paquete, L.; Varrentrapp, K. (2002). A racing algorithm for configuring metaheuristics. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). с. 11—18.
  12. ↑ Birattari, M. (2004). The Problem of Tuning Metaheuristics as Seen from a Machine Learning Perspective (PDF) (PhD thesis). Université Libre de Bruxelles.
  13. ↑ Francois, O.; Lavergne, C. (2001). Design of evolutionary algorithms - a statistical perspective. IEEE Transactions on Evolutionary Computation. 5 (2): 129—148. doi:10.1109/4235.918434.
  14. ↑ Nannen, V.; Eiben, A.E. (2006). A method for parameter calibration and relevance estimation in evolutionary algorithms (PDF). Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO). с. 183—190.
  15. ↑ Smit, S.K.; Eiben, A.E. (2009). Comparing parameter tuning methods for evolutionary algorithms (PDF). Proceedings of the IEEE Congress on Evolutionary Computation (CEC). с. 399—406.