1. 서 론
공학 설계와 같은 현실적인 문제들은 종종 의사 결정자의 다양한 요청에 수반되는 다수의 목적함수들이 있는 다목적 최적화 문제(multi-objective optimization problems)로 공식 화된다. 상충하는 모든 목적함수들을 동시에 최적화하는 해가 존재하지 않기 때문에, 다목적 최적화에서는 Pareto 해(Pareto solutions)[15]가 대안으로 사용되고, 그 중에서 의사결정자들의 의도에 맞는 해를 선택하게 된다[6, 14, 16]. 특히, Pareto 해집합을 생성하는 것을 목적으로 하는 유전자 알고리즘이 광범위하게 연구되었다[1, 2, 7, 10, 13, 17].
다목적 유전자 알고리즘(multi-objective genetic algorithms) 은 여러 목적을 가진 최적화 문제에서 생물의 진화 과정의 형태를 모방하여 비지배해(non-dominated solution) 를 탐색하는 기법이다. 모집단(population)을 이용하여 모 집단 내의 개체들에 대하여 적합도(fitness)를 평가하고, 이 평가를 바탕으로 다음 세대구성을 위한 선택(selection), 교 차(crossover), 돌연변이(mutation) 연산을 반복한다. 이 과 정에서 얻어진 비지배해를 평가함으로써 최적해를 효율적 으로 도출할 수 있고, 이런 장점으로 인해 다목적 유전자 알고리즘은 공학, 자연과학, 경영학 등 수리적인 방법을 적용하는 다양한 영역에서 다목적 최적화 문제를 다루는 기법으로 많이 활용되고 있다[3, 11, 12, 20]. 다목적 최적 화 문제에서는 여러 개의 목적함수들이 서로 상충되는 관 계가 있기 때문에 이들을 고려하여 해를 얻는 것이 중요하 다. 이는 해의 다양성을 유지하면서 실제 Pareto 해에 얼마 나 빨리 접근하는가의 수렴성을 의미하고, 이 두 가지의 목적을 달성함에 있어서 중요한 것이 개체의 적합도 평가 이다. 개체 사이의 우위 관계를 기반으로 하는 Pareto 순위 방식은 적합성 평가에 널리 활용돼 왔다. Goldberg [5], Fonseca et al.[4], Zitzler et al.[19]에 의한 순위 결정 방법 들이 대표적인 평가법들이다. 그러나 Pareto 순위에 따른 평가방법은 개체집단의 분포에 의해 많은 영향을 받는다.
따라서, 본 연구에서는 다목적 유전자 알고리즘을 이용 하여 해의 다양성과 수렴성을 향상시키고, 탐색성능 향상을 위해 목표값을 향한 성취도에 따른 적합도 평가방법을 제안 한다. 수치 예제와 벤치마크 문제를 사용하여 성취도를 고 려한 제안된 방법과 순위에 기존의 대표적인 평가방법인 Pareto 순위방법을 비교한다. 이 비교를 바탕으로 제안된 방법이 실제의 Pareto 해에 더 빨리 수렴되고, 다양한 해집합 을 생성할 수 있음을 검증한다. 또한, 다목적 유전자 알고리 즘에 대한 대부분의 연구는 Pareto 해집합의 생성에 주안점 을 두며, 최종해의 선택에 대해 논의된 연구는 거의 없는 실정이다. 본 연구에서는 다목적 의사결정 지원체계 구축을 위해, 의사결정자의 만족도를 통합한 시각화된 균형 분석을 기반으로 한 대화형 의사결정 과정을 제안한다.
2. 성취도 수준에 따른 적합성 평가를 위한 제안
다음 식 (1)과 같은 다목적 최적화 문제를 고려한다.
여기서 x는 설계(design)변수이고 X는 실행(feasible) 가능 한 해들의 집합이다. f 와 g 는 각각 목적함수와 제약함수 를 나타내며, q 는 목적함수의 개수를 의미하고 m은 제약 함수의 개수이다.
다목적 최적화 문제에 대한 해의 개념 중 하나인 Pareto 해는 다음과 같이 정의된다.
정의. 만약 다음의 식 (2)를 만족하는 x ∈X가 없다면
그러면 ∈X는 Pareto 해라고 부르며, 그것들의 집합은 Pareto frontier라고 한다. 이는 <Figure 1>에서 실선 부분으 로 표현한 것에 해당한다.
유전자 알고리즘의 기본 아이디어는 <Figure 2>와 같다[9].
다목적 최적화 문제에 대한 Pareto 해집합 생성에서 유 전자 알고리즘을 적용할 때 중요한 문제는 탐색 과정의 해의 다양성과 수렴성을 유지하는 것이다. 해의 탐색성능 을 향상시키기 위하여 목표값까지의 성취도 수준 식 (3)으 로 구성된 다각형의 면적 식 (4)와 둘레를 나타내는 식 (5) 에 대한 적합성 평가를 제안한다.
목표값까지의 성취도 수준:
여기서, 와 는 각각 목적함수에서 최악의 경우의 값과 최고의 값으로 주어진다. 본 연구에서, 그것 들은 모집단에서 i번째 목적함수의 최대값과 최소값이다.
다각형의 면적:
다각형의 둘레:
위의 식에서 q개의 목적함수가 있을 때, 다각형은 총 (q - 1)!/2개의 순환순열의 형태를 갖는다. 본 연구에서는 각 다각형 형태에 대해 면적 S 와 둘레 L 을 구하고, 그 평 균 S 와 L 을 기준으로 다음과 같은 척도를 제안한다.
예를 들어, <Figure 3>은 성취도 수준으로 구성된 다각 형의 면적과 둘레를 나타낸다.
<Figure 3>의 (i = 1,⋯, 4)는 목표값에 대한 각 목 적함수의 성취도 수준(모두 1이 됨)을 나타내며, 주어진 개체의 목표값까지의 성취도 수준은 fi로 표시된다. 더 큰 성취도 수준 fi은 더 큰 영역 S 에 해당하며, 더 큰 값 V는 식 (6)에 의해 얻어진다. <Figure 3>의 그림 (a)와 (b)에서 볼 수 있듯이, 목적함수 값 사이의 더 나은 균형 은 동일한 영역 S 에 관계없이 더 작은 둘레 L 과 더 큰 V 값을 얻게 된다. 목표값을 영역 S , 둘레 L 까지의 성취 도 수준을 도입하면, 해의 생성과정에서 수렴성을 얻을 수 있을 뿐 아니라 다양한 해를 생성할 수 있을 것으로 판단된다.
한편, 특정 목적함수에 대한 성취도 수준이 매우 높은 경우에는 면적이 더 작고 둘레가 더 커지게 되므로, 식 (6) 에 의한 평가도 더 나빠지게 된다. 그러나 해의 다양성을 유지하기 위해서도 이러한 해가 필요하다. 따라서 평가된 값 V를 Fonseca et al.[4]이 제안한 방법에서 얻은 순위 R 로 나누고 다음과 같이 적합성 평가방법을 제안한다.
3. 수치 예제들의 결과
이 절에서는 식 (7)에서 제안된 적합도 평가방법의 효율성 을 조사하기 위하여 벤치마크 문제를 사용하고 Goldberg[5, 8], Fonseca et al.[4], Zitzler et al.[19]의 순위방법들(이하, “Rank G”, “Rank F”, “Rank S”)을 비교한다.
3.1 DTLZ1 문제 [1]의 수치 예제
시뮬레이션에서 목적함수의 수는 M = 3으로 주어지고, 차원의 수는 n = 7로 설정되며, 유전자 알고리즘의 구조와 모수 설정에 대해 동일한 조건에서 100의 초기 개체들을 무작위로 생성하고 최대 100세대에 대해 10회 실험을 수 행하였다.
<Figures 4>~<Figure 6>은 각 시행에서 얻어진 목적함 수 공간의 해집합들을 보여준다. 단, Rank G로 얻은 결과 는 그래프에 표시할 수 있는 해를 생성하지 않기 때문에 비교에서 제외한다.
<Table 1>은 Pareto 개체 백분율(individual percentages) 을 나타낸다. 각각 A와 B방법으로 얻은 해집합 XA와 XB 을 추가하여 Pareto 해집합 XP에 존재하는 해집합 XA와 XB의 해의 개수 NA와 NB를 얻는다. <Table 1>은 |XP|에 대한 NA와 NB의 percentages를 보여준다. 즉, 해가 실제 Pareto frontier에 얼마나 더 근접한지를 나타내고 있다.
결과에서 보듯이, 제안된 방법에서 얻어진 해집합은 전 체 목적함수 공간에 널리 분포되어 있으며, 다양한 해가 생성된다. 더욱이 DTLZ1 문제의<Table 1>에서 50세대의 제안된 방법과 Rank F의 결과를 비교한 결과, 해당 Pareto 개체 백분율이 각각 88%, 12%인 것으로 나타났다. 따라 서, 제안된 방법은 실제 Pareto frontier에 더 가까운 해들을 생성하기 때문에 성능이 우수하다고 볼 수 있다. 또한, Rank F와 Rank S에 의해 생성된 해집합보다 더 좋은 해집 합은 더 적은 세대(Rank F와 S는 최대 100세대까지 필요) 로 생성될 수 있다.
3.2 Cantilever Welded Beam Design[18] 예제
빔 높이 t, 빔 폭 b, 용접 길이 l 및 용접 두께 h의 네 가지 설계변수에 대해 총 비용, 팁 변형률, 전단 응력 및 휨 응력을 최소화하는 캔틸레버 용접 빔 설계 <Figure 7>를 사용한다.
설계문제는 아래와 같은 다목적 함수식으로 나타난다.
여기서
우리는 그 결과를 대표적인 다목적 유전자 알고리즘 방 법인 NSGA-II[1]와 SPEA2[19]의 결과와 비교한다.
<Figure 8>은 무작위로 100명의 개별 개체들을 생성하 고 50세대까지 10회 실험을 진행함으로써 얻어진 해집합 을 보여준다. 결과는 두 목적함수 사이의 그래프 형태로 표시된다. <Figure 8>에서 x축은 각 방법의 모든 결과를 결합한 집합의 Pareto 해를 나타낸다.
NSGA-II 및 SPEA2의 결과와 비교하면, 제안된 방법에 의해 얻어진 해집합은 목적함수 공간 전체에 널리 분포되 어 있다. 또한, 제안된 방법에 의해 얻어진 해집합은 30세 대까지만 얻었고 NSGA-II와 SPEA2에 의해 얻어진 해집 합 50세대까지 구한 것을 비교한다.
Pareto 개체 백분율은 <Table 2>에 표현되어 있다. 제안 된 방법에 대한 백분율이 높았고, 실제 Pareto 해에 더 밀 접한 해집합을 적은 세대에서 얻을 수 있었다.
4. 만족도에 기반한 의사결정의 제안
목적함수가 2개 또는 3개인 경우에, 각각의 목적함수들 사이의 trade-off 관계는 도시된 Pareto 해를 기반으로 시각 적으로 결정될 수 있어 최종 의사결정 해법의 선택이 용이 하다. 그러나, 4개 혹은 그 이상의 목적함수가 있는 경우, trade-off 관계를 쉽게 시각화할 수 없으며, 많은 Pareto 해 들에서 의사결정자의 선호도를 만족하는 해를 찾기 어려 워진다. 여기서 의사결정자에 의해 주어지는 희구 수준 (aspiration level)에 기반하는 만족도를 계산하고 trade-off 관계에 대한 시각화를 통해 최종적인 대안을 선택하는 방 법을 제안한다.
4.1 만족도 기반의 의사결정방법 절차
3.2절에 설명된 cantilever welded beam 설계의 예를 가 지고 제안하는 방법의 과정은 다음과 같다:
[Step 0]
해집합 는 성취도 수준 기반 다목 적 유전자 알고리즘으로부터 생성된다.
[Step 1]
-
이상점(ideal point) 는 집합 Ps로부터 구한다.
-
의사결정자의 희구 수준 f가 설정된다.
-
희구 수준 f에 대한 주어진 해 f (xj)의 만족도는 다 음의 식 (8)과 같이 정의된다:
[Step 2]
해집합Ps에서 희구 수준에 가장 가까운 제안 A0와 각각 의 목적함수에 대한 만족도에 가장 가까운 제안 Ai 가 대안 으로 선택된다. 이 때, A0와 Ai 는 식 (9)와 같이 정의된다.
이 예에서 이상점(ideal point) 및 대안은 다음과 같다.
또한, 희구 수준은 아래와 같이 주어진다.
따라서, 위의 대안들에 대한 만족도 수준을 얻는다. 그 결과는 <Figure 9>에 나타나 있다.
만약 의사결정자가 A0에서 A4까지의 제안들 중에서 하 나에 만족한다면, 의사결정 과정은 종료된다. 그렇지 않으 면 과정은 다음 단계로 진행된다.
희구 수준에 관한 첫 번째 제안인 A0에서 각 목적함수에 대한 만족도는 음의 값을 갖는다. 이는 희구 수준의 집합이 실행 불가능함을 의미한다. 예를 들어, 제안 A0에 만족하지 않고 그들의 만족도가 f4에 대해 가장 낮다고 가정하면 의 사결정자는 목적함수 f4를 개선하기를 희망할 것이다.
[Step 3]
Trade-off 분석이 수행되고 만일 주어진 목적함수가 향 상되면 희생될 목적함수가 결정된다.
목적함수 f4에 대해 A0보다 더 높은 만족도를 가지는 해들을 해집합 Ps에서 선택한다. 결과는 <Figure 10>에서 확인할 수 있다. f4의 향상은 f1및 f3에 대한 만족도의 상 당한 감소로 이어진다는 것이 관찰할 수 있다. 두 목적함 수 f1과 f3가 희생될 수 있는 허용 범위가 결정되고, 그 과정은 다음 단계로 진행된다. 여기서 f1은 -5에서 희생될 수 없고 f3은 -7에서 희생될 수 없다고 가정한다.
[Step 4]
최종 제안은 희구 수준과 의사결정자의 요청에 따라서 제안된다. 만일 의사결정자가 만족하는 해가 없거나 타협 할 수 있는 해가 없는 경우에, 새로운 희구 수준이 설정되 고 과정은 [Step 1]으로 돌아간다.
<Figure 11>은 본 예제에서 최종 대안의 만족도를 보여 준다. 결과들로부터 목적함수들 사이의 trade-off 관계를 쉽게 이해할 수 있고, 해의 선택이 쉬워진다.
5. 결 론
본 논문에서는 실제 다목적 공학 설계 문제에 대해 의 사결정자에 의해 주어진 희구 수준을 기반으로 최종해를 선택하기 위한 만족도 기반의 진화 다목적 의사결정의 과 정을 제안하였다. 첫째, 다목적 유전자 알고리즘의 성능을 향상시키기 위해, 성취도 수준에 따른 개체별 적합성 평가 방법을 제안하였고, 이를 확인하기 위하여 수치 예제를 이 용하여 제안한 방법의 효율성을 검증하였다. 결과는 다양 성을 유지하면서 더 적은 세대수를 가지고 실제 Pareto 해 에 더 밀접한 해집합을 생성할 수 있음을 보였다. 다음으 로, 시각화된 trade-off 분석을 기반으로 의사결정자의 만 족도를 반영한 대화형 의사결정 과정을 제안했다.
향후 본 연구에서 도출된 결과들의 추가와 또 다른 의 사결정자들의 의견을 반영할 수 있는 기법들을 추가하면 다목적 의사결정 지원 시스템 구축에 유용한 도구가 될 것으로 판단된다.