하이퍼휴리스틱 알고리즘 소개

최근 지능형 컴퓨팅 분야가 발전하면서 하이퍼 휴리스틱 알고리즘(Hyper-Heuristic Algorithm)이라는 새로운 형태의 알고리즘이 등장했다. 최근에는 지능형 컴퓨팅 분야의 유명한 국제 학회(GECCO 2009, CEC 2010, PPSN 2010)[1]에서 하이퍼 휴리스틱 알고리즘에 관한 워크숍이나 세션이 각각 개최되었습니다. GECCO 2011을 시작으로 하이퍼휴리스틱 알고리즘 관련 연구가 정식으로 학회의 한 분야가 되었습니다(self* search-new frontier track). 지능형 컴퓨팅 분야의 저명한 국제학술지인 Journal of Heuristics와 Evolutionary Computation 역시 2010년과 2012년에 하이퍼 휴리스틱 알고리즘 관련 연구 진행 상황을 집중적으로 특집호로 정리했습니다.

정의 1. 하이퍼 휴리스틱 알고리즘은 일련의 하위 수준 휴리스틱 알고리즘(Low-Level Heuristics, LLH)을 조작하거나 관리하여 특정 상위 수준 전략(High-Level Strategy, HLS)을 제공합니다. 새로운 경험적 알고리즘을 얻습니다. 이러한 새로운 휴리스틱 알고리즘은 다양한 NP-hard 문제를 해결하는 데 사용됩니다.

위 그림은 하이퍼휴리스틱 알고리즘의 개념 모델을 개략적으로 나타낸 것이다. 그림에서 볼 수 있듯이 하이퍼휴리스틱 알고리즘은 두 가지 수준으로 나뉩니다. 문제 도메인 수준에서 응용 도메인 전문가는 배경 지식을 기반으로 문제 정의, 평가 기능 및 기타 정보와 일련의 LLH를 제공해야 합니다. 상위 수준 전략 동일한 수준에서 지능형 컴퓨팅 전문가는 효율적인 조작 및 관리 메커니즘을 설계하고 문제 도메인에서 제공하는 문제 특성 정보와 LLH 알고리즘 라이브러리를 사용하여 새로운 휴리스틱 알고리즘을 구축합니다. 이 두 수준 사이에는 엄격한 도메인 차폐가 구현되므로 문제 도메인의 문제 정의와 LLH, 평가 기능 등 도메인 관련 정보를 수정하는 것만으로 하이퍼 휴리스틱 알고리즘을 신속하게 새로운 문제로 마이그레이션할 수 있습니다. 따라서 하이퍼휴리스틱 알고리즘은 도메인 간 문제를 해결하는 데 특히 적합합니다. 슈퍼 휴리스틱 알고리즘을 연구하는 목적은 지능형 컴퓨팅 전문가를 대체하는 것이 아니라 지능형 컴퓨팅 기술을 더 많은 응용 분야에 더 빠르게 전파하는 동시에 휴리스틱 알고리즘 설계의 어려움을 효과적으로 줄여 연구 초점을 효과적으로 나누는 것입니다. 도메인 전문가 및 지능형 컴퓨팅 전문가. 그림 1에 따르면 지능형 컴퓨팅 전문가는 하이퍼 휴리스틱 알고리즘 설계에서 주로 상위 수준 전략에 중점을 두는 반면 도메인 전문가는 문제의 목적 함수 및 LLH에 중점을 두는 것을 볼 수 있습니다.