메타휴리스틱스 - [126화 1교시]

메타휴리스틱스(metaheuristics)는 전역최적화를 위한 근사해법으로 1960년대 중반부터 여러 기법이 개발되었습니다. metaheuristic이라는 용어는 Glover(1986)에 의해 처음 사용이 되었습니다. 접두어 'meta'는 그리스어 'higher level' 또는 'beyond'라는 의미이고, 'heuristic'은 'to find', 'to know', 'to discover'라는 의미를 가지고 있습니다.

 

메타휴리스틱은 '상위 수준의 휴리스틱'이라는 뜻입니다. 메타휴리스틱은 '특정 휴리스틱 구축을 위한 일반적인 구조와 전략을 안내하는 범용 알고리즘 틀(framework)'을 말합니다. 따라서 메타 휴리스틱은 특정 휴리스틱을 개발 할 때 알고리즘의 기본 틀로 사용할 수 있는 상위 휴리스틱입니다.

 

메타휴리스틱스는 근사해법으로 전역최적해나 어떤 수준 이상의 근사 최적해의 탐색을 보장하지 못합니다. 그러나 메타휴리스틱이 여러 분야에서 복잡하고 어려운 문제를 해결하는 데 성공적인 결과를 보여 줌으로써 지난 사반세기 동안 큰 관심을 가지게 되었습니다.

 

적용 분야에는 조합최적화, 연속최적화, 신경망 학습, 패턴인식, 데이터 마이닝, 인공지능, 화상처리, 공학 구조 최적화 등의 공학 분야 뿐만 아니라, 자연과학과 사회과학 등이 포함되었습니다. 많은 연구자들은 이들 분야에서 메타휴리스틱스의 적용성과 효율성을 보여 주었습니다.

 

 

 

 

컴퓨터 과학과 수학 최적화에서 메타휴리스틱은 특히 불완전하거나 불완전한 정보나 제한된 계산능력으로 최적화 문제에 충분히 좋은 해결책을 제공할 수 있는 휴리스틱스(부분 검색 알고리즘)를 찾거나 생성 또는 선택하도록 설계된 상위 수준의 절차 또는 휴리스틱이다.[1][2]메타휴리스틱스는 그렇지 않으면 너무 커서 완전히 열거하거나 탐구할 수 없는 해결책의 일부를 표본으로 추출한다.메타휴리스틱스는 해결 중인 최적화 문제에 대해 비교적 적은 가정을 할 수 있으므로 다양한 문제에 사용할 수 있다.

 

최적화 알고리즘과 반복적인 방법에 비해 메타휴리스틱스는 어떤 종류의 문제에서 전지구적으로 최적의 솔루션을 찾을 수 있다고 보장하지 않는다. 많은 메타휴리스틱스는 어떤 형태의 확률적 최적화를 구현하기 때문에 발견된 솔루션이 생성된 랜덤 변수 집합에 의존한다. 조합 최적화의 경우, 실현 가능한 대규모 솔루션 세트를 검색함으로써 메타휴리스틱스는 종종 최적화 알고리즘, 반복적 방법 또는 단순한 휴리스틱스보다 계산 노력이 덜한 좋은 솔루션을 찾을 수 있다. 이와 같이, 그것들은 최적화 문제에 유용한 접근법이다.

 

메타휴리스틱스에 관한 대부분의 문헌은 컴퓨터 실험을 바탕으로 한 경험적 결과를 알고리즘으로 기술하는 등 본질적으로 실험적이다.그러나 정합화 및 글로벌 최적화를 찾을 수 있는 가능성에 관한 몇 가지 공식적인 이론적 결과도 이용할 수 있다. 많은 메타휴리스틱 방법들이 새로움과 실용적인 효능을 주장하면서 출판되었다.이 분야에는 수준 높은 연구도 있지만, 많은 출판물들은 질이 좋지 않았다. 결점들로는 애매함, 개념적인 정교함의 결여, 빈약한 실험, 이전 문학에 대한 무지 등이 있다.

 

특징
메타휴리스틱스는 검색 과정을 안내하는 전략이다.
검색 공간을 효율적으로 탐색하여 최적의 솔루션을 찾는 것이 목표다.
메타휴리스틱 알고리즘을 구성하는 기법은 단순한 로컬 검색 절차부터 복잡한 학습 과정까지 다양하다.
메타휴리스틱 알고리즘은 근사적이며 일반적으로 결정적이지 않다.
메타휴리스틱스는 문제에만 국한되지 않는다.

분류
로컬 검색 대 글로벌 검색
한 가지 접근방식은 검색 전략의 유형을 특성화하는 것이다.[3]검색 전략의 한 종류는 단순한 로컬 검색 알고리즘의 개선이다.잘 알려진 지역 검색 알고리즘은 지역 최적점을 찾기 위해 사용되는 힐 클라이밍 방법이다.그러나, 언덕 등반은 전세계적으로 최적의 해결책을 찾는 것을 보장하지는 않는다.
로컬 검색 기반이 아닌 다른 글로벌 검색 메타휴리스틱스는 일반적으로 모집단 기반 메타휴리스틱스다.그러한 메타휴리스틱스에는 개미 군집 최적화, 진화 연산, 입자 군집 최적화, 유전 알고리즘 및 라이더 최적화 알고리즘이 포함된다.

단일 솔루션 대 인구 기반
단일 솔루션 접근법은 단일 후보 솔루션을 수정하고 개선하는 데 초점을 맞추고 있으며, 단일 솔루션 메타휴리스틱스에는 시뮬레이션된 어닐링, 반복된 로컬 검색, 가변적인 근린 검색 및 안내된 로컬 검색이 포함된다. 모집단 기반 접근방식은 다중 후보 솔루션을 유지하고 개선하며, 종종 모집단 특성을 사용하여 검색을 안내한다. 모집단 기반 메타휴리스틱스에는 진화 연산, 유전 알고리즘 및 입자 군집 최적화 등이 포함된다. 메타휴리스틱스의 또 다른 범주는 집단이나 집단에서 분산되고 자체 조직된 에이전트들의 집단 행동인 Mirb intelligence이다.개미 군집 최적화, 입자 군집 최적화, 사회 인지 최적화가 이 범주의 예다.

Hybridization 및 Menmetic 알고리즘
하이브리드 메타휴리스틱은 메타휴리스틱과 수학 프로그래밍, 제약 프로그래밍, 머신러닝 등의 다른 최적화 접근법을 결합한 것이다. 하이브리드 메타휴리스틱의 두 구성 요소는 동시에 실행될 수 있으며 검색을 가이드 하기 위해 정보를 교환할 수 있다.
반면에, Memetic 알고리즘은 문제 검색을 위한 별도의 개별 학습이나 지역적 개선 절차로 진화적 또는 인구 기반 접근법의 시너지 효과를 나타낸다. Menmetic 알고리즘의 예로는 진화 알고리즘에서 기본적인 돌연변이 연산자 대신 로컬 검색 알고리즘을 사용하는 것이 있다.

병렬 메타휴리스틱스
병렬 메타휴리스틱스는 병렬 프로그래밍 기술을 사용해 여러 메타휴리스틱스 검색을 병렬로 실행하는 것이다. 이것은 간단한 분산 체계에서부터 전체 솔루션을 개선하기 위해 상호 작용하는 동시 검색 실행에 이르기까지 다양하다.

자연에서 영감을 받은 은유적 메타휴리스틱스
주요 기사:집단 지능과 은유에서 영감을 받은 메타휴리스틱스 목록
자연은 복잡한 계산 문제를 다루기 위한 인공 컴퓨터 시스템의 설계에 대한 개념, 메커니즘 및 원리의 원천으로 작용한다. 그러한 메타휴리스틱스에는 시뮬레이션된 어닐링, 진화 알고리즘, 개미 군집 최적화 및 입자 군집 최적화 등이 포함된다.최근 은유에 영감을 받은 많은 수의 메타휴리스틱스가 정교한 은유 뒤에 새로운 것의 결여를 숨겼다는 이유로 연구계에서 비판을 받기 시작했다.

적용점들
메타휴리스틱스는 최적의 솔루션이 개별 탐색 공간에서 찾는 조합 최적화에 사용됩니다. 예시적인 문제는 후보 솔루션의 검색 공간이 문제의 크기가 증가함에 따라 후보 솔루션의 검색 공간이 기하 급수적으로 증가하는 여행자 문제로, 최적의 솔루션에 대한 최적의 솔루션에 대한 철저한 검색을 합니다. 또한, 형태 찾기 및 행동 찾기와 같은 엔지니어링의 대부분의 설계 문제를 포함한 다차원 조합 문제는 차원의 저주로 인해, 철저한 검색이나 분석 방법에 대해 불가능하게 됩니다. 메타휴리스틱스는 또한 JobShop Scheduling 및 Job Selection 문제에도 널리 사용됩니다. 조합 문제에 대한 인기있는 전이에는 Kirkpatrick et al., Holland et al., Scatter Search 및 Tabu Search의 Glover에 의한 유전자 알고리즘이 포함됩니다.