메타휴리스틱스

제1부 메타휴리스틱스 서론
제1장 메타휴리스틱스와 최적화 / 19
제2부 단일해 기반 메타휴리스틱스
제2장 시뮬레이티드 어닐링 / 39
제3장 타부서치의 개요 / 57
제4장 타부서치의 주요 주제 / 77
제5장 반복지역탐색, 가변이웃탐색, 유도지역탐색 / 95
제3부 진화알고리즘
제6장 유전알고리즘의 개요 / 113
제7장 유전표현, 유전연산자, 선택전략 / 131
제8장 유전알고리즘의 변형과 확장 / 161
제9장 진화전략, 진화프로그래밍, 유전프로그래밍 / 179
제10장 공진화알고리즘 / 197
제11장 다목적 진화알고리즘 / 231
제12장 진화알고리즘의 적용 / 259
제4부 입자군집최적화
제13장 입자군집최적화의 개요 / 275
제14장 기본 PSO의 변형과 입자 궤적 / 291
제15장 제약 다루기, 군집 다양화, 이산 PSO / 309
제16장 Multimodal PSO와 다목적 PSO / 323
제5부 개미군체최적화
제17장 개미군체최적화의 개요 / 339
제18장 기본 ACO 알고리즘 / 353
제19장 ACO 알고리즘의 수렴 / 371
제20장 여러 형태의 ACO 알고리즘 / 381
제21장 ACO의 적용 / 403
제6부 그 외의 집단 기반 메타휴리스틱스
제22장 차분진화 / 415
제23장 벌군체최적화 / 433
제24장 화음탐색 / 445
참고문헌 / 452
찾아보기 / 470

머리말

저자는 1992년 연암재단의 지원으로 노스캐롤라이나 주립대학에 방문교수로 있으면서 자연 현상을 모방한 새로운 개념의 최적화기법들을 접하게 되었다. 당시에 자연의 진화과정을 모방한 유전알고리즘, 인간의 기억과정과 고체물리학의 어닐링과정을 각각 모방한 타부서치와 시뮬레이티드 어닐링 기법이 개발되어 이에 관한 연구와 적용이 활발히 이루어지고 있었다. 경영과학을 전공하고, 산업현실에서 일어나는 제약이 많고 복잡도가 높은 문제의 해결을 위한 방법론을 찾고 있던 저자에게 이들 기법은 대단히 매력적이었다.
노스캐롤라이나 주립대학에서 1년간의 연구년을 마치고, 전남대학교로 돌아와 대학원생들과 함께 이들 기법에 대한 연구를 시작하였다. 이들 이론의 확장과 함께 조립라인의 계획과 운영, 생산일정계획, 통신시스템의 설계와 운영에의 적용에 중점을 두었다. 이에 관한 여러 연구결과들을 국내외 학술지에 발표하였다. 이들 중에서 혼합모델 조립라인의 투입순서 결정에 유전알고리즘을 적용한 논문으로 1994년 대한산업공학회에서 백암논문상을 받았다. 그리고 1997년 홍익대학교 윤복식 교수, 서경대학교 이상복 교수와 함께 유전알고리즘, 시뮬레이티드 어닐링, 타부서치를 다룬 ‘메타휴리스틱’(영지문화사)을 출간하였다. 이 책에서 저자는 이때까지 우리 실험실에서 연구한 결과를 토대로 유전알고리즘 편을 집필하였다. 그 후 우리 실험실에서 유전알고리즘의 이론과 적용을 확장해 가면서 연구를 계속하여 그 결과를 국내외 전문학술지에 발표하였다. 이들 결과를 정리하여 2011년 ‘진화알고리즘’(전남대학교출판부)을 출판하였다. 이 책은 2012년도 대한민국학술원 우수학술도서로 선정되었다.
1990년대 이후 학계에서는 메타휴리스틱에 대한 연구와 적용이 활발히 이루어졌다. ‘메타휴리스틱’(영지문화사, 1997)에서 다룬 고전적 메타휴리스틱 이외에 여러 기법들이 새로이 개발되고 확장되었다. 그럼에도 2010년까지 메타휴리스틱스를 보다 폭 넓게 다룬 서적이 국내에서 출판되지 않고 있었다. 이에 저자는 ‘진화알고리즘’(전남대학교출판부, 2011) 출간 후, 널리 적용되고 있는 개미군체최적화와 입자군집최적화에 대해 먼저 정리를 시작하였다. 그 이후 이들 내용을 보완하고 다른 여러 메타휴리스틱 기법들을 추가하다 보니 준비를 시작한 지 5년이 지나서야 본서 ‘메타휴리스틱스’(metaheuristics)를 출간하게 되었다.
Metaheuristic에서 접두어 ‘meta’는 그리어로 ‘higher level’ 또는 ‘beyond’라는 의미이고, ‘heuristic’은 ‘to find’, ‘to know’, 또는’ ‘to discover’라는 의미이다. 메타휴리스틱은 ‘상위 수준의 휴리스틱’이란 뜻이다. 부연하면 메타휴리스틱은 ‘특정 휴리스틱 구축을 위한 일반적인 구조와 전략을 안내하는 범용 알고리즘 틀(framework)’을 말한다. 메타휴리스틱은, 그 구조와 전략 관점에서, 지역최적을 벗어나고 해공간을 강건하게 탐색할 수 있는 구조를 포함하며, 이를 위하여 지역개선 절차와 더 높은 수준의 전략이 조화롭게 상호작용하는 해법으로 볼 수 있다. 메타휴리스틱은 탐색 과정에서 발견한 좋은 해 주위를 집중적으로 탐색할 수 있는 전략과 함께, 찾은 지역최적에서 벗어나 탐색하지 않은 해 공간의 탐색 영역을 넓혀가면서 탐사를 할 수 있는 전략을 가지고 있어야 한다. 이들 두 형태의 전략이 한쪽으로 치우침이 없이 균형을 이루면서 탐색 할 수 있도록 알고리즘이 설계되어야 한다.
메타휴리스틱은 일종의 근사해법으로 전역최적해나 어떤 수준 이상의 근사 최적해를 보장하지 못한다. 그러나 지난 사반세기 동안 메타휴리스틱 기법은 복잡도가 높은 여러 유형의 어려운 최적화문제에서 만족할 만한 성과를 보여 주었다. 그 적용 범위는 조합최적화, 연속최적화, 신경망 학습, 패턴인식, 데이터 마이닝, 인공지능, 화상처리, 공학 구조 최적화 등의 공학 분야뿐 아니라, 시스템의 최적화, 학습, 적응과 관련된 자연과학과 사회과학 분야를 포함한다.
본서에서는 메타휴리스틱스(metaheuristics)의 주요 기법들을 소개한다. 이들 기법의 개념과 이론과 특징, 그리고 그 적용을 쉽게 이해할 수 있도록 설명한다. 특히 메타휴리스틱의 적용에 있어서 알고리즘의 설계와 구현에서 고려해야 하는 요소들에 관심을 갖는다. 본서는 메타휴리스틱스를 하나의 해를 운용하는 기법과 해의 집단을 운용하는 기법으로 크게 나누어 구성되었다. 지금까지 제안된 모든 메타휴리스틱 기법을 다루지 못하지만, 가능한 대표적인 기법들은 소개하려 노력하였다. 단일해 기반의 메타휴리스틱스로는 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search), 반복지역탐색(iterated local search), 가변이웃탐색(variable neighborhood search), 유도지역탐색(guided local search)을 다루고 있으며, 집단 기반의 메타휴리스틱스로는 진화알고리즘(evolutionary algorithms), 입자군집최적화(particle swarm optimization), 개미군체최적화(ant colony optimization), 차분진화(differential evolution), 벌군체최적화(bee colony optimization), 화음탐색(harmony search)을 다루고 있다.
본서는 6부 24장으로 구성되어 있다. 제1부는 하나의 장에서 메타휴리스틱스와 최적화에 대한 개요를 설명한다. 제2부는 단일해 기반 메타휴리스틱스로 2장에서 4장에서 고전적 기법인 시뮬레이티드 어닐링과 타부서치를, 그리고 5장에서 반복지역탐색, 가변이웃탐색, 유도지역탐색 기법을 소개한다. 제3부는 진화알고리즘으로 6장에서 12장에서 여러 형태의 진화알고리즘과 그 적용을 소개한다. 특히 이웃 유전알고리즘, 진화전략, 진화프로그래밍, 유전프로그래밍, 공진화알고리즘, 다목적 진화알고리즘을 포함하고 있다. 제4부는 입자군집최적화에 대해 13장에서 16장에서, 제5부는 개미군체최적화에 대해 17장에서 21장에서 비교적 자세히 다루고 있다. 그리고 제6부는 그 외의 집단기반 메타휴리스틱스로 22장에서 24장까지 각 장에서 차분진화, 벌군체최적화, 화음탐색을 다루고 있다.
본서가 산업공학과 컴퓨터공학에서 최적화와 인공지능 분야의 전공자 뿐 아니라, 시스템의 최적화와 적응에 관심이 있는 공학, 자연과학, 사회과학 분야의 연구자에게도 도움이 되기를 기대한다.
지금까지 많은 메타휴리스틱 기법들이 제안되었고, 이를 변형한 알고리즘 또한 아주 많다. 좀 더 많은 기법들을 소개하지 못한 아쉬움이 남는다. 그리고 어려움 중의 하나는 전문 용어의 선택이었다. 전문용어의 번역은 그 의미가 가능한 쉽고 명확히 독자에게 전달될 수 있어야 한다. 용어에 나름 신중을 기하였으나 적절하지 못한 선택도 있을 것이다. 이점 독자 여러분께 양해를 구한다.
본서가 나오기 까지 많은 분의 도움이 있었다. 본서에 인용된 여러 연구를 함께 하면서 힘든 시간을 보낸 자랑스러운 우리 ‘시스템 최적화와 통합’ 실험실 출신, 김용주, 이수연, 현철주, 고재상, 신경석, 김준혁, 이태옥, 김재윤, 송원섭, 김선진 박사와 석사 출신 박기태, 서광언, 김인수, 이효영, 이현수, 이원균, 김형수, 조준영, 이상선 군에게 고마움을 전한다. 특히 전남대학교 경영학부 김재윤 교수는 시뮬레이티드 어닐링과 타부서치에 대한 저술에 많은 도움을 주었다. 자료 수집과 출판 교정에 수고하여 준 학부생 신현주 양과 윤혜주 양에게 고맙게 생각한다. 출판을 맡아준 전남대학교출판부와 편집과 교정에 정성을 다해준 출판부 윤화정님과 배광현님께 깊이 감사를 드린다. 책 표지와 간지 디자인은 며느리 우지영이 하였다. 잘 해 주어 참으로 고맙다. 그리고 이 책의 출판에 도움을 준 전남대학교 로봇연구소와 박종오 소장님께 진심으로 감사를 드린다.
오늘이 있기까지 따뜻한 마음으로 격려해주고 도와준 동료 교수님, 벗님, 선배님, 후배님께 깊은 감사를 드린다.
저자는 올 8월에 정년을 맞는다. 이에 가족에게 고마운 마음을 전하고, 본서가 출판되는 기쁨을 함께하고 싶다. 지금까지 묵묵히 제 자리를 지켜준 내자에게 고마움을 전한다. 아들과 딸에게 마음을 많이 써 주지 못했음에도 잘 성장하여 화목한 가정을 이루고 사회에서 제 몫을 다 하는 데 대해 정말 자랑스럽고 고맙다. 밝게 살아가는 그리고 책 표지 디자인을 예쁘게 해준 며느리와 착하고 성실하며 항상 배려하는 사위에게 고마운 마음을 표하고 싶다. 손녀 예담과 지아가 밝고 지혜롭고 건강하게 자라기를 기원한다. 그리고 항상 한없는 사랑으로 돌보아 준 누나와 자형께 진심으로 감사를 올린다.
끝으로 본서가 후학들의 학문진전에 조금이나마 도움이 되기를 다시 한 번 간절히 소망한다.
이 긴 시간의 모음이 어느 오솔길의 작은 돌이 되길 바라면서.

2017년 1월
저자 씀

제1부 메타휴리스틱스 서론

제1장 메타휴리스틱스와 최적화

이 장에서는 메타휴리스틱스의 개요를 설명한다. 이를 위해 먼저 메타휴리스틱을 정의하고, 메타휴리스틱이 최적화기법에서 차지하는 위치에 대해 알아본다. 또한 메타휴리스틱의 기본적인 성질과 특성을 소개한다. 메타휴리스틱에 대한 이해를 돕기 위하여 여러 관점에서 분류하고 이를 설명한다. 그리고 메타휴리스틱스에서 공통으로 고려되는 기본 요소와 제약을 다루는 일반적인 방법을 소개한다.

1.1 서론
최적화문제는 크게 연속(continuous)변수와 이산(discrete)변수를 갖는 문제로 분류할 수 있다. 이산변수를 갖는 문제를 조합(combinatorial)문제라 부른다. 연속문제에서는 일반적으로 실수의 집합을 찾고, 조합문제에서는 유한의 집합, 예로 정수, 순열, 그래프 등을 찾는다. 또한 연속변수와 이산변수를 동시에 갖는 혼합문제도 있다. 연속문제를 해결하는 최적화기법은 크게 선형과 비선형으로 나눌 수 있고, 조합문제의 최적화기법은 전역최적(global optimum)을 구할 수 있는 정확한(exact) 해법과 최적에 가까운 좋은 해를 구하는 근사(approximate) 해법으로 분류할 수 있다. 최적화기법은 [그림 1-1]과 같이 분류할 수 있다(Feoktistov, 2006). 이 책에서 사용되는 용어로 방법, 기법, 해법, 그리고 이들이 체계적인 반복 절차를 갖는 경우에 알고리즘이라는 용어는 크게 차이를 두지 않고 사용한다.
선형문제의 해결을 위한 선형계획법이나 이산문제를 위한 분지한계법(branch-and-bound method)과 동적계획법과 같은 정확한 해법은 여러 적용 문제에서 효율적이다. 그러나 이들 해법은 변수가 많고 높은 비선형성을 갖는 연속문제에서는 최적해를 찾기는 매우 어렵다. 또한 문제의 크기에 따라 계산량이 지수적으로 증가하는 대형 조합문제를 정확한 해법으로 해결하는 것은 현실적으로 불가능하다.
최적화는 과학, 공학, 경제학, 경영학 분야에서 일어나는 현실 문제에 많이 적용된다. 이들 적용 문제는 주로 규모가 큰 조합이거나 높은 비선형의 최적화문제가 된다. 이러한 최적화문제는 앞에서 언급했듯이 합리적인 시간 내에 전역최적을 찾는 것은 거의 불가능하다. 이 경우 대안으로 허용하는 시간 내에 전역최적은 아니지만 수락할 수 있는 정도의 좋은 해를 구하는 알고리즘을 사용하는 것이다. 근사해법에 속하는 휴리스틱(heuristic)은 이를 위한 하나의 대안이다. 휴리스틱은 합리적인 계산시간 내에 최적해를 보장하지 못하지만 좋은 해를 찾을 가능성이 높은 방법이다. 적용하는 문제에 따라 그 방법이 달라진다. 일반적으로 휴리스틱이란 특정한 형태의 문제 해결에 적합하도록 설계된 ‘특정 휴리스틱’을 말한다.
메타휴리스틱스(metaheuristics)는 전역최적화를 위한 근사해법으로 1960년대 중반부터 여러 기법이 개발되었다(<표 1-1> 참조). Metaheuristic이란 용어는 Glover(1986)에 의해 처음 사용되었다. 접두어 ‘meta’는 그리어로 ‘higher level’ 또는 ‘beyond’라는 의미이고, ‘heuristic’은 ‘to find’, ‘to know’, 또는’ ‘to discover’라는 의미이다(Beheshti & Shamsuddin, 2013). 메타휴리스틱은 ‘상위 수준의 휴리스틱’이란 뜻이다. 메타휴리스틱은 ‘특정 휴리스틱 구축을 위한 일반적인 구조와 전략을 안내하는 범용 알고리즘 틀(framework)’을 말한다. 따라서 메타휴리스틱은 특정 휴리스틱을 개발할 때 알고리즘의 기본 틀로 사용할 수 있는 상위 휴리스틱으로 볼 수 있다.
메타휴리스틱스는 근사해법으로 전역최적해나 어떤 수준 이상의 근사 최적해의 생산을 보장하지 못한다. 그러나 메타휴리스틱이 여러 분야에서 복잡하고 어려운 문제를 해결하는 데 성공적인 결과를 보여 줌으로써 지난 사반세기 동안 큰 관심을 가지게 되었다. 적용 분야에는 조합최적화, 연속최적화, 신경망 학습, 패턴인식, 데이터 마이닝, 인공지능, 화상처리, 공학 구조 최적화 등의 공학 분야뿐 아니라, 자연과학과 사회과학 등이 포함되었다. 많은 연구자들은 이들 분야에서 메타휴리스틱스의 적용성과 효율성을 보여 주었다.
메타휴리스틱스의 특징에 대해 좀 더 알아보자.
첫째, 메타휴리스틱스는 좋은 해를 탐색함과 동시에 지역최적에서 벗어나 해공간을 강건하게 탐색할 수 있는 프로세스와 전략을 갖는다. 메타휴리스틱스는 탐색 과정에서 발견한 좋은 해 주위의 탐색을 강화하는 전략과 함께, 찾은 지역최적에서 벗어나 탐색하지 않은 해 공간으로 탐색 영역을 다양화하는 전략을 갖는다. 탐색을 강화하면 탐색의 다양화가 약화된다. 그 역도 성립한다. 따라서 메타휴리스틱 설계에서 상충되는 이들 두 전략의 조화로운 상호작용에 초점을 둔다.

둘째, 여러 메타휴리스틱스는 ‘자연 현상’을 모방하고 있으며, 과거 탐색에서 얻은 경험이나 정보를 ‘기억’하거나 ‘전달’하여 다음 탐색에 이를 이용하고 있다.
셋째, 메타휴리스틱스에서는 해 탐색 과정을 ‘반복’하는 데, 매 반복에서 기존의 지역탐색처럼 ‘단일해를 기반(single-solution based)’으로 하는 경우도 있으나, 여러 메타휴리스틱스는 ‘해 집단을 기반(population-based)’으로 하고 있다. 해 집단을 운용함으로써 해 공간의 여러 지역을 동시에 탐색할 수 있다. 단일해를 운용하는 메타휴리스틱은 이웃(neighborhood) 탐색기법을 주로 사용하고 있다.
이들 특징을 요약하면, 대부분의 메타휴리스틱스는 자연 현상에서 영감을 얻어 개발되었고, 예외도 있지만 대부분 과거 탐색(경험)에서 얻은 정보를 다음 탐색에 이용한다. 또한 효율적이고 효과적인 탐색을 위하여, 지역최적을 벗어나 지금까지 탐색하지 않았거나 탐색이 적게 이루어진 영역을 탐색할 수 있는 전략과 더불어, 탐색에서 발견한 좋은 해 주위를 집중적으로 탐색할 수 있는 전략을 가지고 있어야 한다.
어떤 방법이 범용 알고리즘의 틀(메타휴리스틱)로 사용되기 위해서는 다음 조건들을 만족해야 한다(Hansen et al., 2010). 먼저, 단순성, 명확성, 일반성이다. 원리는 가능한 단순 명료해야 하며, 절차는 명확해야 하고, 적용분야는 넓고 다양해야 한다. 다음은 효율성과 효과성으로, 다양한 유형의 문제에 대해 적절한 계산시간 내에(효율성) 최적해나 근사 최적해를 제공(효과성)할 수 있어야 한다. 또한 해의 품질을 높이기 위하여 사용자가 문제에 관한 지식을 알고리즘에 반영(상호작용성)할 수 있어야 한다.
이들 메타휴리스틱스가 갖추어야 할 조건은 바로 메타휴리스틱스의 장점으로 볼 수 있다. 이 외에도 메타휴리스틱스는 목적함수의 변경과 제약식의 추가가 용이하여 적용의 유연성이 높다는 강한 장점을 가지고 있다. 이는 위에서 언급한 적용의 일반성에 해당한다. 고전적 최적화기법에서는 목적함수와 제약식에 따라 문제 해결을 위한 기법이 달라진다. 이에 반해 메타휴리스틱은 목적함수와 제약식에 대한 특정 요건을 요구하지 않는다. 또한 메타휴리스틱 알고리즘 중에는 연속최적화보다는 조합최적화에 더 적합하거나 또는 그 반대인 경우도 있으나, 여러 메타휴리스틱스(예로 진화알고리즘)는은 두 유형의 문제에 모두 적용 가능하다. 그리고 메타휴리스틱은 다봉(multimodal) 최적화와 다목적(multiobjective) 최적화에서 각각 여러 지역최적해와 다양한 비지배된(nondominated) 해를 구하는 데 효과적이다.
메타휴리스틱스는 이러한 강점과 함께 약점을 가지고 있다. 효율적인 메타휴리스틱의 설계를 위해서는 적용 문제에 적합한 전략들을 필요로 한다. 적합한 전략을 구축하기 위해서는 적용 문제의 해공간과 해의 특징을 잘 이해해야 한다. 또한 각 메타휴리스틱에는 제어 파라미터가 존재한다. 메타휴리스틱스의 성능은 대부분 이들 파라미터에 민감하므로, 구현할 때 이를 조심스럽게 조정해야 한다. 그리고 메타휴리스틱스는 전역최적해로의 강한 수렴을 보장하지 못한다는 점이다. 지역최적에 빠지면 수렴 속도가 느려지고 긴 계산시간이 소요되기도 한다. 이 또한 메타휴리스틱스의 단점이다. 일부 메타휴리스틱 알고리즘에서 이론적으로 최적해로의 수렴이 입증되나 이는 무수한 반복(계산소요시간이 무한대)이라는 조건에서 가능하다. 현실 적용에서 이러한 수렴성은 그 의미가 크지 않다.

1.2 메타휴리스틱스의 분류
지역탐색(local search: LS)법은 가장 오래되고 단순한 최적화기법이다. 지역탐색은 가능해 영역에서 하나의 임의 초기해로 시작한다. 이 초기해를 현재해(current solution)로 둔다. 현재해의 이웃(neighborhood)에서 목적함수를 개선하는 해를 찾는다. 목적함수를 개선하는 이웃해를 찾으면 이를 현재해로 둔다. 이러한 반복은 이웃에서 더 좋은 해를 찾을 수 없을 때 끝낸다.
여러 지역최적이 있는 문제에 지역탐색법을 적용하면, 하나의 지역최적(local optimum)에 도달하면 끝난다. 도달하는 지역최적은 초기해에 의해 결정된다. 전역최적(global optimum)에 도달할 수 있는 초기해의 영역은 한정되어 있다.
지역탐색법의 단점은 지역최적에 도달하면 이 지역최적을 벗어나지 못하고 절차를 끝내는 것이다. 이를 극복하는 방법으로, 초기해를 ‘임의로’ 달리하면서 지역탐색을 여러 번 반복 수행하는 방법을 고려해 볼 수 있다. 초기해를 달리하면 다른 지역최적에 도달할 수 있다. 이 방법은 지역탐색보다 더 좋은 해를 찾을 수 있고, 목적함수 형태가 비교적 단순하면 전역최적도 찾을 수 있다. 그러나 이러한 방법은 복잡도가 높고 지역최적이 많은 최적화문제에서는 비효율적이고 우연에 기대는 것이 된다. 중복 탐색을 가능한 회피하고 전역최적을 찾을 가능성이 더 높은 체계적인 방법이 필요하다.
지역탐색법은 현재해의 이웃을 집중 탐색하여 지역최적을 찾을 수 있다는 강점이 있으나, 지역최적을 벗어나지 못하여 해공간의 ‘탐사(exploration)’ 능력이 매우 약하다는 치명적인 약점을 갖고 있다. 넓은 해공간에서 좋은 해 또는 전역최적을 찾기 위해서는 탐색에서 찾은 좋은 해를 ‘이용(exploitation)’하여 지역 탐색을 ‘강화(intensification)’하는 한편, 새로운 해 영역 또는 지역 탐색이 상대적으로 적게 이루어진 영역을 ‘탐사’하여 탐색 영역을 ‘다양화(diversification)’해야 한다. 탐색의 ‘강화’와 탐색 공간의 ‘다양화’는 상충된다. 지역탐색은 탐색의 ‘강화’만을 강조하고, 임의 탐색(random search)은 탐색의 ‘다양화’만을 강조한다. 메타휴리스틱스에서 탐색의 ‘강화’와 ‘다양화’의 균형은 매우 중요하다. 이는 해 공간의 ‘탐사’와 좋은 해의 ‘이용’의 조화를 의미하기도 한다.
복잡도가 높은 대형의 최적화문제를 해결하는 데 합리적 시간 내에 사용자가 수락할 수 있는 해(최적해 또는 근사 최적해)를 구하는 것은 매우 의미가 있다. 이러한 문제는 공학, 자연과학, 사회과학 등 여러 분야에서 쉽게 찾아 볼 수 있다.
1960년대 중반부터 현재까지 메타휴리스틱의 여러 알고리즘이 꾸준히 제안되어 오고 있고(Beheshti et al., 2013), 그 적용 또한 확대되고 있다. <표 1-1>은 주요 메타휴리스틱 기법들을 보여 주고 있다. 이들 메타휴리스틱이 모방한 현상에 따라 분류하면 (1) 자연의 진화과정을 모방한 진화알고리즘(evolutionary algorithm: EA), (2) 군집(swarm 또는 colony) 생활하는 생물들의 행위를 모방한 알고리즘, 이들 외에 (3) 자연 및 사회 현상을 모방한 알고리즘, 그리고 (4) 체계적인 반복으로 이웃을 탐색하는 알고리즘으로 나누어 볼 수 있다.
첫째, 자연의 진화 과정을 모방한 알고리즘에는 진화전략(evolution strategy: ES), 진화프로그래밍(evolutionary programming: EP), 유전알고리즘(genetic algorithm: GA), 유전프로그래밍(genetic pro- gramming: GP), 차분진화(differential evolution: DE) 등이 있다. 이들 알고리즘을 진화알고리즘이라 부른다.
둘째, 개미, 벌, 물고기, 새 등 군집(swarm 또는 colony) 생활하는 생물들의 행동을 모방한 알고리즘으로 개미군체최적화(ant colony optimization: ACO), 입자군집최적화(particle swarm optimi- zation: PSO), 벌군체최적화(Bee Colony Optimization: BCO), 인공벌군체(artificial bee colony: ABC) 등이 있다. 이들 외의 자연 및 사회 현상을 모방한 알고리즘으로
셋째, 열역학의 어닐링과정을 모방한 시뮬레이티드 어닐링(simulated annealing: SA), 기억 과정을 모방한 타부서치(tabu search: TS), 면역시스템을 모방한 인공면역시스템(artificial immune system: AIS), 음악의 화음 조율과정을 모방한 화음탐색(harmony search: HS) 알고리즘이 있다.
넷째, 체계적인 반복으로 이웃을 탐색하는 알고리즘에는 반복지역탐색(iterated local search: ILS), 가변이웃탐색(variable neighborhood search: VNS), 유도지역탐색(guided local search: GLS) 등이 있다.
또한 메타휴리스틱스를 이와는 달리 아래와 같이 분류하여 볼 수 있다(Birattari et al., 2001; Beheshti & Shamsuddin, 2013). 이러한 다른 분류는 메타휴리스틱스의 여러 성질과 특징을 이해하는 데 도움이 될 것이다.

(1) ‘자연’에서 영감을 얻은 메타휴리스틱스: 많은 메타휴리스틱은 자연현상을 모방하고 있다. 진화알고리즘(진화전략, 진화프로그래밍, 유전알고리즘, 유전프로그래밍, 차분 진화)과 인공 면역시스템은 생물학에서, ACO, PSO, ABC는 군집 지능에서, SA는 고체물리학에서 영감을 얻었다.
자연 현상을 모방한 알고리즘의 주요 특징은 개체(해)가 하나가 아닌 집단을 이룬다는 것이고, 자연 현상은 필연(규칙)뿐 아니라 우연(임의 또는 확률)에도 기인하고 있다는 것이다. 집단에서 나타나는 창발성과 자기조직화의 개념을 복잡한 문제 해결에 적용하고자 한다. 여기서 창발성은 낮은 수준의 상호 작용의 결과로서 나타나는 새로운 전체적인 패턴을 의미하며, 자기조직화는 시스템 안에 있는 수많은 요소들이 상호관계를 통해서 끊임없이 재구성하며 환경에 적응해 나가는 것을 말한다. 또한 자연에서는 필연과 우연이 혼재하면서 질서가 파괴되고, 이로부터 새로운 질서가 창조되는 과정을 반복한다는 것이다. 자연에서 나타나는 이러한 현상을 메타휴리스틱스는 모방하고 있다.
(2) 집단 기반과 단일해 기반 메타휴리스틱스: 매 반복에서 운용하는 후보해(candidate solutions)의 수에 따라 집단 기반 메타휴리스틱스(population-based metaheuristics: P-MHs)와 단일해 기반 메타휴리스틱스(single-solution based metaheuristics: S-MHs)로 분류할 수 있다. 매 반복(세대)에서 복수의 후보해로 구성된 집단을 운용하는 집단 기반 메타휴리스틱스에는 진화알고리즘(EA), ACO, PSO, HS, ABS, AIS 등 많은 알고리즘이 있다.
메타휴리스틱스의 가장 큰 특징 중 하나는 많은 알고리즘들이 집단 기반을 사용하고 있다는 것이다. 여러 개체(후보해)로 구성된 집단을 운용함으로써 자연스럽게 여러 해공간을 동시에 ‘탐사’할 수 있는 강점을 갖는다. 또한 이들 집단 기반 메타휴리스틱에는 여러 개체가 탐색에서 얻은 정보를 다음 세대의 탐색에 이용하여 더 좋은 해나 전역최적으로 향하도록 하는 메커니즘이 내재되어 있다.
매 반복에서 단일해를 운용하는 메타휴리스틱은 현재해의 이웃에서 해를 탐색하여 해를 이동시키는 기법으로, 지역탐색에 기반을 둔 알고리즘이다. 이를 이웃 메타휴리스틱이라 부르기도 한다([그림 1-1] 참조). SA, TS, ILS, VNS, GLS가 이에 속한다. 이들 기법의 핵심은 지역최적을 벗어나 효과적인 ‘탐사’를 할 수 있는 전략이다. 이들 알고리즘에는 지역탐색의 강점인 지역탐색을 ‘강화’하는 전략과, 지역 최적을 벗어날 수 있는 탐색의 ‘다양화’ 전략(‘탐사’ 전략)이 결합되어 있다. 그리고 흔히 지역최적을 탐색하는 데 많은 계산시간이 소요되기 때문에 이를 줄이는 전략이 고려된다.
대부분의 S-MHs에서는 지역탐색을 먼저 행하여 지역최적을 찾고, 다음 해공간의 탐색 ‘다양화’가 고려된다. 반면에 P-MHs는 집단의 해로 탐색을 동시에 행하기 때문에 해공간의 탐색 ‘다양화’가 탐색에서 발견한 좋은 해의 ‘이용’(탐색의 ‘강화’)보다 우선시 된다고 볼 수 있다. S-MHs은 탐색의 ‘강화’에, P-MHs는 탐색의 ‘다양화’에 좀 더 무게를 두고 있다. 따라서 각 기법이 갖는 강점을 이용하여 다른 메타휴리스틱 또는 수리계획법, 기계학습기법, 데이터마이닝기법 등과 결합한 다양한 형태의 잡종(hybrid) 메타휴리스틱이 제안되고 있다.
(3) 과거 탐색 ‘기억’을 이용하는 메타휴리스틱스: 대부분의 메타휴리스틱에서는 과거 탐색 경험을 저장 또는 기억하여 미래의 탐색에 이용한다. 이는 해공간의 효율적 탐색을 위한 것으로 메타휴리스틱의 중요한 성질 중 하나이다. 타부서치는 기억을 명시적으로 사용(단기기억, 중기기억, 장기 기억)하여 탐색한다. ACO에서는 과거 탐색 정보를 축척하여 이용하고, PSO에서는 자신과 군집의 가장 좋은 경험을 기억하여 이용한다. 또한 진화알고리즘에서는 염색체에 과거 탐색정보(조상의 유전자)가 자손에게 상속되면서 그 기억이 부분적으로 이용된다고 볼 수 있다. 반복지역탐색(ILS)에도 기억을 이용할 수 있으며, 유도지역탐색(GLS)에도 과거의 지역탐색 결과를 이용하고 있다. 기억을 이용하지 않는 알고리즘에는 SA와 지역탐색(local search)이 있다. 이들 두 탐색에서 다음 탐색은 단지 현 탐색에 의해서만 영향을 받는다.
메타휴리스틱스에서 과거 탐색 정보(기억)가 미래 탐색에 어떻게 영향을 미치는 지에 대한 이해가 중요하다. 즉 이들 정보가 탐색의 ‘다양화’와 ‘강화’(또는 해 공간의 ‘탐사’와 좋은 해의 ‘이용’)에 작용하는 메커니즘에 대한 이해가 중요하다.
(4) 확률적 또는 확정적 메타휴리스틱스: 초기해가 같으면 항상 같은 결과가 산출되는 알고리즘은 확정적이고, 초기해가 같아도 매번 다른 결과가 나올 수 있으면 확률적이다. 대부분의 메타휴리스틱은 확률적(stochastic)이다. 단지 타부서치(TS)는 파라미터가 변하지 않는다면 확정적 알고리즘이 된다.
확률적 메타휴리스틱의 매 반복에서 새로운 후보해(들)를 생성할 때, 즉 해가 이동할 때 좋은 해로의 ‘지역’적 이동과 새로운 해 영역으로의 ‘전역’적 이동이 확률적으로 고려된다. 메타휴리스틱은 ‘우연’의 성질을 갖는 확률적 탐색으로 다양한 해 공간의 ‘탐사’ 능력을 높인다. 이 ‘탐사’는 발견한 좋은 해의 ‘이용’과 적절한 균형을 이루어야 한다. 해 공간의 확률적 탐색은 메타휴리스틱의 주요 특징 중 하나이다.
(5) 복수의 이웃 구조와 단일 이웃 구조: S-MHs에서 현재해는 이웃에서 해(이웃해)를 발생하여 탐색을 계속한다. 따라서 이들 알고리즘에서 탐색은 이웃 구조에 의해 결정된다. ILS와 GLS은 하나의 이웃을 사용하나, 가변이웃탐색(VNS)은 다양한 형태의 여러 이웃을 사용한다. 여러 이웃 구조의 사용은 지역탐색의 ‘강화’가 주 목적이다. 또한 초기해를 다른 형태의 이웃에서 임의로 발생하면 탐사 영역이 ‘다양화’될 수 있다.
(6) 동적 또는 정적 목적함수: 대부분의 메타휴리스틱스에서는 탐색 중에 목적함수 형태가 변하지 않는다. 그러나 유도지역탐색(GLS)에서는 탐색에서 지역최적을 찾으면 그 주위는 증대된 목적함수로 변환한다. 또한 입자군집최적화(PSO)에서도 이미 찾은 지역최적해 주위의 목적함수 값을 증대시켜 이 지역이 재 탐색되는 것을 막는 방법이 제안되었다. 이는 지역최적에서 벗어나 다른 영역의 탐사를 유도하기 위함이다.
이 책에서는 단일해 기반과 집단 기반의 분류에 따라 S-MHs를 먼저 다루고, 다음 P-MHs 를 다룬다. 지금까지 많은 메타휴리스틱 기법이 제안되었으나 이 책에서는 많은 연구자들이 관심을 갖고 발전시키고 적용한 대표적인 기법만을 다룬다. 이 책의 제2부(제2장～제5장)에서는 단일해 기반 메타휴리스틱스로 시뮬레이티드 어닐링, 타부서치, 반복지역탐색, 가변이웃탐색, 유도지역탐색을 차례로 소개한다. 제3부(제6장～제12장)에서는 진화알고리즘을, 제4부(제13장～제16장)에서는 입자군집최적화를, 제5부(제17장～제21장)에서는 개미군체최적화를, 제6부(제22장에서 23장)에서는 그 외의 집단 기반 메타휴리스틱스로 차분진화, 벌군체최적화, 화음탐색을 다룬다.

1.3 메타휴리스틱스의 공통 요소
앞에서 언급했듯이 메타휴리스틱은 범용 알고리즘의 틀이다. 따라서 이를 기반으로 하여 특정 문제의 해결을 위한 알고리즘을 설계할 때, 모든 메타휴리스틱에서 공통으로 고려되는 기본 요소에 대해 알아보자. 이들 요소에는 해의 표현, 목적함수, 초기해, 파라미터 조정, 종료조건 등이 있다. 이에 대해 설명한다. 그리고 S-MHs의 기본요소인 이웃에 대해 설명한다.
1) 표현
특정 문제의 해결을 위해 사용할 메타휴리스틱이 결정되면, 문제에 적합한 알고리즘을 설계하게 된다. 이때 제일 먼저 고려해야 할 요소는 해의 표현(representation 또는 encoding)이다. 표현방법에는 이진수, 실수 벡터, 이산 값 벡터, 순열, 그룹, 행렬, 랜덤 키(random key), 그래프 등 다양한 표현이 가능하다. 이들 표현은 각 메타휴리스틱을 다루면서 좀 더 구체적으로 설명한다. 특히 각 표현 방법에 대해서는 3.2절과 7.1절을 참조할 수 있다.
표현은 알고리즘의 성능에 크게 영향을 미친다. 따라서 해의 표현을 선택할 때는 사용하는 메타휴리스틱의 특성, 관련 연산자와 그 운영 방법, 그리고 적용 문제가 갖는 성질 등을 고려하여 결정해야 한다. 사용하려는 메타휴리스틱에서 어떤 정보가 어떤 메카니즘으로 이용되면서 해 공간을 탐색하여 가는 지를 이해하여, 그 특성을 잘 반영할 수 있는 표현을 선택해야 한다. 또한 표현은 해를 자연스럽게 그리고 비중복적으로 나타내는 것이 바람직하다. 자연스런 표현은 해석이 용이하고 해의 특성을 쉽게 파악할 수 있으며, 이것은 과거 탐색 정보의 효과적 이용을 가능하게 한다. 표현 방법은 앞으로 각 메타휴리스틱을 다루면서 좀 더 설명하기로 한다.
2) 목적 함수
메타휴리스틱에서 후보해들을 평가하는 함수가 필요하다. 이 평가는 흔히 목적함수에 의해 이루어진다. 목적함수 값에 의해 해의 품질 또는 적합도(fitness)가 결정된다. 진화알고리즘에서는 ‘fitness’를 생물학의 용어인 ‘적응도’로 번역한다. 목적함수는 좋은 해가 있는 탐색 영역으로 탐색을 유도하는 역할을 한다.
대부분의 최적화문제에서 해는 절대적이고 고정된 값을 갖는 목적함수에 의해 평가된다. 이 경우 좋은 해로의 탐색을 촉진하기 위하여 목적함수를 변형한 ‘평가함수’를 사용하기도 한다. 그러나 게임문제나 협조 또는 경쟁 공진화알고리즘에서 해의 평가는 다른 해와 상대적이거나 경쟁적으로 평가된다. 이 경우에는 효과적이고 효율적으로 해를 평가할 수 있는 평가전략과 평가함수를 고려해야 한다. 이에 대해서는 제10장 공진화알고리즘에서 다룬다.
3) 초기해
모든 메타휴리스틱에서 알고리즘을 시작하기 위해서는 초기해가 필요하다. S-MHs에서는 하나의 초기해를, P-MHs에서는 집단의 초기해를 필요로 한다.
S-MHs에서 탐색을 시작하기 위해서는 초기해를 설정해야 한다. 생성 방법은 임의(random) 생성과 휴리스틱(또는 greedy) 생성으로 나눌 수 있다. 임의 방법은 빠른 시간에 초기해를 구하지만 수렴하는 데 많은 시간이 소요될 수 있다. 탐색 속도를 높이기 위하여, 휴리스틱 방법을 사용할 수 있다. 이 방법은 대부분의 경우 지역최적에 빨리 도달한다. 그러나 좋은 초기해가 항상 더 좋은 지역최적해를 찾지는 않는다. 두 방법에는 해의 품질과 계산소요시간의 절충(trade-off)관계가 있다. 초기해를 찾는 휴리스틱이 단순하거나 효과적이지 않는 경우에는 임의 방법이 좋다. 제약이 강하면 임의 방법으로 가능해를 찾기가 어려울 수 있다. 이 경우에는 가능해를 생성할 수 있는 휴리스틱을 사용할 수 있다.
P-MHs에서는 해집단을 운용함으로써 해 공간에 있는 여러 지역을 동시에 탐사할 수 있다. 이들 알고리즘에서 ‘집단의 다양성(population diversity)’ 유지는 해의 개선에 결정적 역할을 한다. 해집단이 정체되면, 즉 다양성을 잃게 되면 탐사능력이 약화되어 좋은 해를 탐색하지 못하게 된다. 따라서 P-MHs에서 초기 해집단을 생성할 때, 좋은 해들의 집단보다는 집단의 다양성에 중점을 두어야 한다. 집단의 다양성은 해들이 얼마나 서로 다른지에 따라 평가된다.
P-MHs에서 초기해집단은 집단의 다양성을 위해 흔히 임의로 생성한다. 이 방법은 연속문제인 경우 각 변수(해의 원소) 값의 범위에서 임의의 값을 생성하여 해를 구성하는 것이다. 이산문제의 경우에도 해의 각 원소가 가질 수 있는 유한개의 이산 값 중에서 임의로 값을 추출하여 해를 구성하는 방법이다. 이 과정을 집단의 크기만큼 반복하여 해 집단을 구성한다. 이와 같은 임의 방법 이외에 집단의 다양성을 높이는 여러 방법이 있을 수 있다. 연속문제의 경우, 해 공간을 집단의 크기만큼 균등하게 블록으로 나누어, 각 블록에서 하나의 해를 임의로 생성하는 방법을 사용할 수 있다. 집단의 다양성을 최적화하는 것 자체가 하나의 최적화문제가 된다. 초기집단의 다양화를 위해 계산시간이 너무 많이 소요되는 것은 피해야 한다.