1. 서 론

자연현상을 모방한 최적화 알고리즘은 기존 고전적 수치 알고리즘이 갖는 복잡함과 초깃값에 대한 민감성 등과 같은 단점을 극복하고자 1970년대 이후 많이 고안되어 연구되었다^(1-4). 그 중 Harmony search(HS) 알고리즘은 즉흥적 음악 연주 시 연주자들이 화음을 개선해 나가는 방식을 모방한 비교적 최근에 개발된 메타 휴리스틱 최적화 기법이다⁽⁵⁾. 고전적 기법과 달리 HS는 비수학적 알고리즘으로 설계변수에 대한 초깃값을 요구하지 않으며 경사법(gradient search) 대신 확률변수 기법 (stochastic random search)을 기반으로 하고 있다. 또한 두 부모 벡터만 고려하는 GA와 달리 수집된 모든 벡터를 고려하여 새로운 벡터를 생성한다.

진화적 기법의 성능은 기존 정보를 활용(exploitation)하는 활용 능력과 새로운 영역을 탐색(exploration)하는 탐색 능력에 달려 있다. HS는 둘 간의 균형이 좋고 비교적 구현이 쉬워 다양한 최적화 문제 해결에 성공적으로 적용되어 왔다. 그러나 많은 장점에도 불구하고 알고리즘 매개변수를 고정된 값으로 설정한다거나 매개변수 값을 잘못 설정한 경우 국지 값으로 수렴하게 되는 단점이 있다. 이러한 단점을 극복하고 알고리즘 성능을 향상시키기 위한 많은 노력들이 있었다. 그 중 ⁽⁶⁾은 알고리즘 매개변수를 알고리즘 반복 수행 시마다 바뀌도록 하여 HS의 성능을 개선하였다. 이후 이 방식에 대한 여러 진전이 있어 왔다^(7-9). 또 다른 방법은 기존 HS의 구조나 요소를 변경하거나 이에 더해 다른 최적화 방법을 결합하는 방식이다^(10-12).

HS는 예비 해를 구성하는 개별 변수값을 기존의 값에서 선택하거나 무작위 값으로 결정한다. $HMCR$(harmony memory consideration rate)은 새로운 하모니를 구성할 때 변수값을 기존 값에서 선택할 확률을 나타내는 매개변수로 알고리즘 성능과 밀접한 관련이 있다. 이 값을 크게 할수록 기존 변수값의 활용이 크게 되며 최종값으로 수렴 속도와 해의 전역 성에 영향을 미친다. 따라서 주어진 문제의 차원이나 국지 최적값의 수에 따라 적절한 $HMCR$ 값을 선택하는 것은 매우 중요한 문제이다. 특히 국지적 최적값이 존재하는 경우 최종해의 전역 성에 많은 영향을 미친다. 그러나 지금까지 $HMCR$ 값을 선택하는 분석적인 방법과 기준이 없었으며 오로지 경험칙으로 결정해 왔다. 이러한 문제를 해결하기 위해 ⁽¹³⁾에서 2차 시스템을 대상으로 $HMCR$과 새로운 하모니 조합의 관계를 연구하였다.

본 논문에서는 이전의 연구 결과를 바탕으로 $HMCR$ 값에 따른 변수의 선택과 예비 해의 구성 및 그 확률을 $n$차 시스템으로 확대하였다. 세부적으로는 새로운 하모니를 변수 조합 방법에 따른 역할에 따라 ‘다각화성(diversification)’과 ‘강화성( intensification)’으로 분류하고 각각의 확률을 구하였다. 이를 바탕으로 문제에서 필요로 하는 새로운 하모니의 전역성 및 해의 강화성을 고려하여 $HMCR$ 값을 결정하는 해석적인 방법을 제시하였다.

2. HS

모든 메타 휴리스틱 알고리즘은 다각화(diversification)를 위한 새로운 영역의 탐색과 기존 정보를 활용한 해의 강화(intensification)라는 두 가지 과정으로 구성된다. 두 과정의 적절한 조화는 해의 전역성과 정확성 및 빠른 수렴에 있어 매우 중요한 요소이다⁽¹⁴⁾.

HS는 즉흥 연주 시 연주자들이 좀 더 좋은 하모니를 얻기 위해 악기의 피치를 조정해가는 방식을 모방한 것으로 연주자가 하나의 음을 즉흥적으로 낼 때는

① 연주자의 기억에 있는 음을 내거나

② 기억 속 음을 기준으로 그에 이웃한 음을 연주하거나

③ 기억에 의존하지 않고 악기의 음역에서 임의로 선택하여 연주한다.

HS 알고리즘은 이를 ‘기억회상’, ‘피치조정’ 및 ‘무작위’ 라는 세 가지 방식으로 모방하여 결정변수 값을 선택해 가며 해 벡터(solution vector)를 개선해 나간다. 구체적으로 다음과 같은 단계별 과정을 통해 구현된다.

Step 1. 최적화 문제와 알고리즘 매개변수를 초기화한다.

Step 2. HM(harmony memory)을 초기화한다.

Step 3. 새로운 하모니 즉 해 벡터를 생성한다.

Step 4. HM을 최신화한다.

Step 5. 중단 요건을 검사한다.

HM은 가장 최근의 좋은 화음을 기억하는 장소이다.

3. $HMCR$과 하모니

알고리즘 확률 매개변수 $HMCR$과 $PAR$은 새로운 하모니를 생성할 때 개별 변수에 대한 선택 확률이며 그동안 이로 인해 생성되는 하모니 조합과 그 확률에 대해서 연구가 없었으나 ⁽¹³⁾에서 2차 함수에 대해 생성되는 하모니 조합과 그 확률에 대해 연구하였다. 본 연구에서는 이를 $n$차 시스템으로 확장하고 개선하여 주어진 문제에 맞게 $HMCR$ 값을 결정하는 해석적인 방법을 제시하고자 한다.

식(1)의 하모니는 $n$개의 변수 조합으로 구성되며 각 변수는 앞에서 서술한 세 가지 방식 중 하나로 선택된다. 그러나 선택된 변수의 조합으로 생성되는 하모니 조합은 매우 다양하고 확률 또한 복잡하다. 앞에서 살펴본 하모니 구성을 위한 변수 선택 과정을 순서도로 나타내면 다음 그림 3과 같다.

순서도에 따라 결정되는 하모니 구성의 종류는 $3^{n}$으로 결정변수의 수에 따라 지수적으로 증가한다. $n=2$인 경우 하모니 종류 및 각 확률은 다음 표 1과 같다.

표에서 보듯이 하모니 조합은 모두 아홉($3^{2}=9$) 가지이며 크게 세 부분으로 구분할 수 있다. 첫째는 두 변수 모두 무작위로 선택되는 조합이고 두 번째는 HM을 기반으로 하는 기억회상 선택 간 조합이며 나머지 하나는 무작위 선택과 기억회상의 하이브리드 조합이다. 이들 세 부류의 하모니 조합 확률은 다음과 같다.

1) 무작위 하모니 확률 : $RSH=(1-HMCR)^{2}$

2) 하이브리드 하모니 확률 : $HYH=2(1-HMCR)\cdot HMCR$

3) 기억회상 하모니 확률 : $MCH=HMCR^{2}$

-기억선택 하모니 확률 : $MSH=HMCR^{2}\cdot(1-PAR)^{2}$

-피치조정 하모니 확률 : $PAH=HMCR^{2}\cdot PAR^{2}$

-기억선택/피치조정 하모니 확률 : $CH=2\cdot HMCR^{2}\cdot(1-PAR)\cdot PAR$

보는 바와 같이 세 부류의 하모니 확률은 $PAR$과 무관하며 각 하모니의 구성 확률은 $HMCR$ 값에 따라 비선형적으로 결정된다. 서로 다른 종류의 하모니는 해의 다각화와 강화 측면에서 역할의 정도가 다르다. 기존 값과 다른 변수 값의 무작위 결정은 변수 전 영역을 탐색해 값을 찾는 것으로 해를 다각화한다. 따라서 본 논문에서는 무작위 하모니와 하이브리드 하모니를 다각화 하모니라 부르기로 한다. 정의에 따라 다각화 하모니의 생성 확률은 다음 식과 같다.

결정변수의 수가 $n$인 경우 식(8)은 다음과 같이 표현된다.

그림 4는 $n=2,\:3,\:4$에 대해 몇몇 $HMCR$ 값과 다각화 하모니 $DIVR$의 관계를 그래프로 나타낸 것이다.

같은 값의 $HMCR$이라 하더라도 문제의 차수가 크면 다각화 확률도 크다는 것을 알 수 있다. $HMCR$의 값과 하모니의 다각화가 직결돼 있다는 것은 직관적이다. 그러나 지금까지 둘 관계에 대한 해석이 없이 $HMCR$ 값을 경험칙으로 결정했다.

본 논문에서는 하모니 다각화 확률에 대한 정의식 (9)를 이용하여 알고리즘 매개변수 $HMCR$을 결정하고자 한다. 즉, 주어진 문제를 고려해 원하는$DIVR$를 먼저 설정하고 이 값으로부터 $HMCR$을 다음과 같이 결정하기로 한다.

(10)식을 이용함으로써 주어진 문제의 국지해 특성과 결정변수의 수에 따라 알고리즘의 탐색 능력을 정량적으로 결정할 수 있다. 이는 최종해의 전역해로 수렴성이나 알고리즘 수행 속도를 향상하는데 기여할 수 있다.

다각화 하모니를 제외한 나머지 변수 조합은 HM 내 기존 값을 그대로 사용하거니 대역폭 범위 내에서 가감되어 구성되므로 해의 다각화보다는 기존 해의 강화와 밀접한 관련이 있다. 이 확률은 다음 식과 같다.

식(10)으로부터 다각화 하모니와 강화 하모니 생성 확률이 같기 위한 조건은 다음 식과 같다.

한편 강화성 하모니는 하모니 구성 값 모두를 기존의 값에서 선택하는 경우 구성 값 모두를 피치조정 하는 경우 및 이들의 조합으로 하모니 구성이 이루어지는 세 종류가 있으며 $HMCR$ 값이 결정되면 이후 $PAR$ 값에 따라 각 확률이 결정된다. 문제의 차수가 $n$인 경우 각각의 확률은 다음과 같다.

다음 그림 5는 $n=2$일 때 $0\le PAR\le 1$에 대한 3가지 종류 하모니의 확률을 나타낸다.

$PAR=0.5$일 때 $MSH$와 $PAH$ 값은 결정변수의 수와 무관하게 같으며 그 크기는 결정변수 수 $n$과 다음의 관계가 있다.

식에서 보듯이 $n$이 커짐에 따라 지수적으로 감소하는 반면 $CBH$는 지수적으로 증가한다. $PAR$를 결정할 때는 이러한 특성을 고려해 결정되어야 할 것이다.

4. 수치 예

본 논문에서는 HS 알고리즘의 하모니를 다각화성과 강화성으로 분류하고 $HMCR$ 값과 결정변수의 수에 의해 결정되는 각각의 확률을 정의하였다. 이를 바탕으로$HMCR$ 값을 다각화성 하모니 확률 $DIVR$이 크도록 결정하면 최종해가 전역해로 수렴할 가능성이 높다고 하였다. 이를 입증하기 본 장에서는 복수의 국지 최솟값을 갖는 최적화 시험 함수를 대상으로 다각화 하모니 확률 $DIVR$을 달리 하여 그 결과를 살펴보고자 한다. 또한 기존 HS에서는 결정변수의 수를 고려하지 않고 $HMCR$ 값을 결정해 왔다. 그러나 본 논문에서는 $HMCR$ 값이 같더라도 결정변수의 수가 다르면 다각화 하모니 확률값이 다르다는 것을 알 수 있었다. 따라서 결정변수의 수가 다른 경우 같은 값의 $HMCR$ 값을 사용하기보다 다각화 하모니 확률이 같도록 $HMCR$ 값을 결정하는 것이 합리적이라 하였다. 이을 입증하기 위해 동일 최적화 문제를 결정변수의 수를 달리하여 기존 방법과 제시한 방법을 비교하였다. 예시에서 최종해의 전역해로 수렴 여부는 허용 오차 범위 $err=10^{-6}$을 적용하여 판단하였다.

5. 결 론

본 논문에서는 HS 최적화 기법에서 $HMCR$과 하모니 생성 관계를 분석해 생성 하모니를 알고리즘의 탐색력을 향상 시켜 해의 다각화에 기여하는 다각화성과 알고리즘의 탐지력을 높여 기존 예비 해의 강화에 기여하는 강화성으로 구분하였다. 또한 두 부류 하모니 생성이 $HMCR$과 최적화 문제의 차수에 의해 결정된다는 것을 수식적으로 보였다.

정의된 수식을 이용하면 HS 알고리즘 구현 시 $DIVR$ 값을 임의로 설정할 수 있으며 이를 통해 알고리즘의 탐색 능력을 향상해 국지해가 많은 최적화 문제의 경우 최종해가 전역해로 수렴할 가능성을 매우 향상시킬 수 있음을 주장하였다. 이와 더불어 같은 $HMCR$ 값이라 하더라도 결정변수의 수가 다르면 $DIVR$ 값이 매우 다르다는 사실을 이용해 결정변수의 수가 변하더라도 $DIVR$ 값이 일관되도록 $HMCR$ 값을 변화시킬 것을 제안하였다.

마지막으로 본 논문의 주장을 뒷받침하기 위해 복수의 국지 최적값을 갖는 2개의 예시와 단일 최적 해를 갖고 결정변수의 수를 달리할 수 있는 2개의 예시에 제시한 방법을 적용하여 그 효과를 보이고자 하였다. 그 결과 복수의 국지해의 경우 본 논문에서 주장 한 바와 같이 $DIVR$을 통해 최종해의 전역해로 수렴성을 크게 향상시킬 수 있음을 확인할 수 있었다. 두 번째 예시는 결정변수의 수와 무관하게 고정된 $HMCR$ 값을 사용하던 기존의 방법과 결정변수의 수에 따라 $DIVR$ 값이 일정하게 유지되도록 $HMCR$ 값을 다르게 결정하여 그 결과를 비교하였다. 두 방법을 비교한 결과 본 논문에서 제시한 바와 같이 결정변수의 수에 따라 $HMCR$ 값을 달을 달리하는 것이 기존 방법에 비해 빠르게 최적값으로 수렴함을 보여 보다 효율적임을 알 수 있었다.