메타휴리스틱

3. 메타휴리스틱의 분류

• -^[15]

3. 1. 탐색 전략

3. 2. 해의 개수

3. 3. 하이브리드 및 밈 알고리즘

3. 4. 병렬 메타휴리스틱

3. 5. 자연 모방 메타휴리스틱

4. 무임소 점심 정리 (No Free Lunch Theorem)

무료 점심 정리에 의해 평균적으로 어떤 탐색 기법도 동일한 성능을 보인다는 것이 증명된 이후, "가장 뛰어난 메타휴리스틱스"를 찾는 것은 무의미하다는 것이 제시되었다.^[1] 이 정리는 종종 "만능 탐색 알고리즘은 존재하지 않는다"라고 표현되며, 메타휴리스틱스에 대한 반(反) 테제로 사용된다.^[1]

그러나 무료 점심 정리는 어디까지나 "모든 문제에 대한 평균"이며 문제 공간을 어느 정도까지 제한했을 때의 성능의 좋고 나쁨은 논할 수 없다.^[1] 또한 실제로 메타휴리스틱스를 구현할 때는 탐색 효율을 높이기 위해 해당 문제의 사전 지식을 더 포함하는 경우가 많다.^[1] 따라서, 이 정리만으로 메타휴리스틱스 자체에 불필요론을 제기할 수는 없다.^[1]

5. 메타휴리스틱의 예시

메타휴리스틱의 예시로는 다음과 같은 알고리즘들이 있다.

• 진화 연산
• 군집 지능
• 차분 진화
• 풍력 구동 최적화
• 브레인스토밍 최적화
• 소용돌이 최적화

5. 1. 진화 연산

• 진화 알고리즘

• 군집 지능

• 차분 진화
• 풍력 구동 최적화
• 브레인스토밍 최적화
• 소용돌이 최적화

6. 응용 분야

메타휴리스틱은 연속 최적화부터 혼합 정수 문제, 조합 최적화 또는 이들의 조합에 이르기까지 모든 유형의 최적화 문제에 사용된다.^[3][29][30] 조합 최적화에서는 이산 탐색 공간에서 최적의 솔루션을 찾는다. 한 예로 외판원 문제가 있는데, 이 문제의 크기가 증가함에 따라 후보 솔루션의 탐색 공간이 기하 급수적으로 증가하여 최적의 솔루션을 위한 전수 조사를 비현실적으로 만든다.^[31][32] 또한, 형태 찾기 및 행동 찾기와 같은 공학^{[41][33][34][35]} 분야의 대부분의 설계 문제를 포함한 다차원 조합 문제는 차원의 저주로 인해 전수 조사나 해석적 해법을 사용할 수 없게 된다.

메타휴리스틱은 스케줄링 문제에도 자주 적용된다. 이러한 조합 작업의 예로는 작업장 스케줄링이 있으며, 모든 작업이 정시에, 그리고 전체적으로 가능한 최단 시간에 완료되도록 작업의 작업 단계를 처리 스테이션에 할당하는 작업이다.^[36][37] 실제로는 제한 사항을 준수해야 하는 경우가 많은데, 예를 들어 미리 정의된 워크플로우^[38]를 통해 작업 단계의 허용 가능한 순서를 제한하거나, 자원 활용과 관련하여 에너지 수요 평탄화의 형태로 제한할 수 있다.^[39][40] 조합 문제에 대한 인기 있는 메타휴리스틱에는 Holland 등의 유전자 알고리즘, Glover의 분산 탐색 및 타부 탐색이 있다.

연속 또는 혼합 정수 탐색 공간에서의 최적화 작업도 주요 응용 분야이다. 여기에는 설계 최적화^[41][42][43] 또는 다양한 엔지니어링 작업이 포함된다.^[44][45][46] 조합 및 연속 최적화의 혼합 예는 산업용 로봇의 유리한 움직임 경로 계획이다.^[47][48]

7. 메타휴리스틱 최적화 프레임워크

메타휴리스틱 최적화 프레임워크(MOF)는 "일련의 메타휴리스틱의 정확하고 재사용 가능한 구현을 제공하고, 특정 문제 인스턴스를 제공된 기술을 사용하여 해결하는 데 필요한 파트너 하위 휴리스틱(솔루션 인코딩 및 기술별 연산자 포함 가능)의 구현을 가속화하는 기본 메커니즘을 제공하는 소프트웨어 도구 세트"로 정의할 수 있다.^[49]

다양한 기능을 가진 MOF로 간주될 수 있는 많은 최적화 도구가 있다. 다음은 그 예시이다:^[49]

Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO, Pisa, Watchmaker, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, UOF.

위 도구들은 자세히 비교 및 평가되었다.^[49] 2010년대 후반부터는 특히 병렬 구현 지원에 대한 다수의 간행물이 있었다.^{[23][24][50][51][52]}

일반적으로 특정 문제에 대한 "해법"이 존재할 때, 해당 해법을 적용할 수 있는 범위는 해당 문제에 국한된다. 그러나 근사 알고리즘처럼 엄밀한 답이 아닌, 최대한 "답에 가까운" 수준까지 범위를 넓히면, 지역 탐색법이나 탐욕법 등 여러 문제에 사용할 수 있는 기법이 존재한다.

메타휴리스틱은 특정 문제에 국한되지 않고, 어떤 문제에도 범용적으로 대응할 수 있도록 설계된 알고리즘의 기본적인 틀을 의미한다. 다시 말해, 휴리스틱 알고리즘 중에서 특정 문제에 의존하지 않고 기법만 독립적인 것이다. 따라서 모든 문제에 적용할 수 있다.

NP-난해와 같이 다항 시간 내에 최적해를 구하는 알고리즘이 존재하지 않는 것으로 보이는 문제 등에 유효하다. 다만, 일반적으로 메타휴리스틱은 특정 문제 전용 휴리스틱보다 평균적인 해의 정확도가 떨어지는 경우가 많다. 이는 범용적인 탐색을 위해서는 문제에 대한 사전 지식 없이 구현해야 하므로, 이를 유효하게 사용하여 해를 탐색하는 방법에 비해 불리한 입장에서 탐색을 진행해야 하기 때문이다.

8. 주요 기여

• 1952년: 로빈스와 몬로가 확률적 최적화 방법에 대한 연구를 수행했다.
• 1954년: 바리첼리는 진화 과정의 첫 번째 시뮬레이션을 수행하여 이를 일반적인 최적화 문제에 적용했다.
• 1963년: 라스트리긴이 무작위 탐색을 제안했다.
• 1965년: 마티아스가 무작위 최적화를 제안했다.
• 1965년: 넬더와 미드가 심플렉스 휴리스틱을 제안했으며, 파월은 이 방법이 일부 문제에서 비정상적인 점으로 수렴함을 보였다.
• 1965년: 잉고 레첸베르크가 최초의 진화 전략 알고리즘을 발견했다.
• 1966년: 포겔 등은 진화 프로그래밍을 제안했다.
• 1970년: 헤이스팅스가 메트로폴리스-헤이스팅스 알고리즘을 제안했다.
• 1970년: 카비키오는 최적화기의 제어 매개변수 적응을 제안했다.
• 1970년: 커니건과 린은 변수 깊이 탐색 및 금지 기반 (탭) 탐색과 관련된 그래프 분할 방법을 제안했다.
• 1975년: 홀랜드는 유전 알고리즘을 제안했다.
• 1977년: 글로버는 스캐터 탐색을 제안했다.
• 1978년: 머서와 샌슨은 다른 최적화기를 사용하여 최적화기 매개변수를 조정하기 위한 메타 최적화를 제안했다.
• 1980년: 스미스는 유전 프로그래밍을 설명했다.
• 1983년: 키르크패트릭 등은 시뮬레이티드 어닐링을 제안했다.
• 1986년: 글로버는 탭 탐색을 제안했으며, 이 때 처음으로 '메타휴리스틱'이라는 용어가 언급되었다.
• 1989년: 모스카토는 밈 알고리즘을 제안했다.
• 1990년: 모스카토와 폰타나리,^[53] 듀크와 슈어,^[54]는 독립적으로 시뮬레이티드 어닐링에 대한 결정적 업데이트 규칙을 제안하여 탐색 속도를 높였다. 이로 인해 임계값 수용 메타휴리스틱이 등장했다.
• 1992년: 도리고는 박사 학위 논문에서 개미 집단 최적화를 소개했다.^[21]
• 1995년: 울퍼트와 매크레디는 무상의 점심 없음 정리를 증명했다.

참조

_[1] 서적 Complex Scheduling https://link.springe[...] Springer 2012
_[2] 서적 Combinatorial Optimization: Algorithms and Complexity Dover Publ., corrected, unabridged new edition of the work published by Prentice-Hall in 1982. 1998
_[3] 간행물 Particle Swarm Optimization Algorithm and Its Applications: A Systematic Review 2022
_[4] 간행물 Evolution strategies for continuous optimization: A survey of the state-of-the-art https://linkinghub.e[...] 2020
_[5] 문서 Metaheuristic optimization Scholarpedia
_[6] 간행물 Future paths for integer programming and links to artificial intelligence https://leeds-facult[...] 1986-01
_[7] 간행물 Self-adaptive mutations may lead to premature convergence https://ieeexplore.i[...] 2001
_[8] 간행물 Metaheuristics—the metaphor exposed https://onlinelibrar[...]
_[9] 웹사이트 Why we fell out of love with algorithms inspired by nature https://theconversat[...] 2024-08-30
_[10] 서적 Evolution and optimum seeking Wiley 1995
_[11] 간행물 A new optimizer using particle swarm theory https://ieeexplore.i[...] IEEE 1995
_[12] 간행물 Distributed Optimization by Ant Colonies https://www.research[...] Elsevier Publ. 1991
_[13] 간행물 Ant colony optimization for continuous domains https://linkinghub.e[...] 2008
_[14] 간행물 Constrained Combinatorial Optimization with an Evolution Strategy http://link.springer[...] Springer Berlin Heidelberg 2024-08-24
_[15] 웹사이트 Classification of metaheuristics http://metah.nojhan.[...]
_[16] 간행물 A Unified View on Hybrid Metaheuristics http://link.springer[...] Springer Berlin Heidelberg 2024-08-24
_[17] 간행물 Metaheuristics 2015
_[18] 웹사이트 Classification of Metaheuristics and Design of Experiments for the Analysis of Components. https://api.semantic[...] 2001
_[19] 간행물 RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits https://ieeexplore.i[...]
_[20] 간행물 Optimize railway crew scheduling by using modified bacterial foraging algorithm https://www.scienced[...] 2023-06-01
_[21] 문서 Optimization, Learning and Natural Algorithms
_[22] 서적 Efficient and Accurate Parallel Genetic Algorithms http://link.springer[...] Springer US 2001
_[23] 간행물 Parallel Evolutionary Algorithms http://link.springer[...] Springer 2024-09-04
_[24] 간행물 A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics https://dl.acm.org/d[...] ACM 2020-11-02
_[25] 웹사이트 A Research Agenda for Metaheuristic Standardization https://api.semantic[...] 2024-08-30
_[26] 웹사이트 Journal of Heuristic Policies on Heuristic Search Research https://link.springe[...] 2024-09-01
_[27] 웹사이트 Aims and scope https://link.springe[...] 2024-09-01
_[28] 웹사이트 Aims and scope https://link.springe[...] 2024-09-01
_[29] 서적 Hybrid Metaheuristics https://link.springe[...] Springer 2006
_[30] 서적 Handbook of Memetic Algorithms http://link.springer[...] Springer Berlin Heidelberg 2012
_[31] 간행물 Ant colony system: a cooperative learning approach to the traveling salesman problem https://ieeexplore.i[...] 1997-04
_[32] 간행물 Memetic Algorithms for the Traveling Salesman Problem https://www.research[...] 2002
_[33] 간행물 Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. http://www.mdpi.com/[...] 2013
_[34] 간행물 Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production 2013-03-01
_[35] 서적 2011 IEEE International Conference on Control System, Computing and Engineering 2011-11-01
_[36] 서적 Metaheuristics for production scheduling https://www.wiley.co[...] ISTE 2013
_[37] 서적 Metaheuristics for Scheduling in Industrial and Manufacturing Applications http://link.springer[...] Springer Berlin Heidelberg 2008
_[38] 논문 Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing 2013-04-22
_[39] 논문 An Ensemble of Meta-Heuristics for the Energy-Efficient Blocking Flowshop Scheduling Problem 2019
_[40] 논문 A metaheuristic for energy adaptive production scheduling with multiple energy carriers and its implementation in a real production system 2019
_[41] 논문 Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems https://linkinghub.e[...] 2021
_[42] 간행물 Optimization of a Micro Actuator Plate Using Evolutionary Algorithms and Simulation Based on Discrete Element Methods https://www.research[...] Computational Publications 2002
_[43] 간행물 Strategies for the Integration of Evolutionary/Adaptive Search with the Engineering Design Process http://link.springer[...] Springer 2023-07-17
_[44] 서적 Applications of Metaheuristics in Process Engineering https://link.springe[...] Springer International Publishing 2014
_[45] 서적 Industrial Applications of Evolutionary Algorithms http://link.springer[...] Springer 2012
_[46] 서적 Engineering Applications of Modern Metaheuristics https://link.springe[...] Springer International Publishing 2023
_[47] 간행물 Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM http://link.springer[...] Springer 2023-07-17
_[48] 간행물 Multiobjective Trajectory Planning of a 6D Robot based on Multiobjective Meta Heuristic Search https://dl.acm.org/d[...] ACM 2018-12-14
_[49] 논문 Metaheuristic optimization frameworks: a survey and benchmarking 2012-03
_[50] 간행물 evospace-js: asynchronous pool-based execution of heterogeneous metaheuristics ACM 2017-07-15
_[51] 논문 Efficient Hierarchical Parallel Genetic Algorithms using Grid computing 2007-05
_[52] 간행물 Design and architecture of the jMetaISP framework ACM 2017-07-15
_[53] 논문 Stochastic versus deterministic update in simulated annealing 1990
_[54] 논문 Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing 1990