Impact of diversity on bounded archives for multi-objective local search

당신이 완벽한 메뉴를 만들기 위해 노력하는 셰프라고 상상해 보세요. 당신에게는 두 가지 목표가 있습니다. 음식이 맛있어야 하고(목표 1), 동시에 건강해야 한다(목표 2)는 것입니다.

문제는 '완벽한' 요리가 단 하나만 존재하는 것이 아니라는 점입니다. 수천 가지의 조합이 존재할 수 있습니다. 어떤 요리는 정말 맛있지만 너무 헤비하고, 어떤 요리는 매우 건강하지만 맛이 심심할 수 있습니다. '파레토 프런트(Pareto Front)'는 한쪽을 더 좋게 만들려면 반드시 다른 한쪽을 희생해야 하는, 즉 최적의 균형을 이룬 요리들의 목록입니다.

이제, 당신의 주방은 하나의 **메타휴리스틱(metaheuristic, 똑똑한 탐색 알고리즘)**이 되어 이 완벽한 요리들을 찾아내려 합니다. 요리를 할수록, 당신은 새롭고 놀라운 레시피들을 계속해서 발견하게 됩니다. 하지만 곧, 기억해야 할 레시피가 너무 많아지는 문제가 발생합니다. 모든 레시피를 다 간직하려고 하면, 주방은 혼란스러워지고 속도가 느려질 것입니다. 이것이 바로 이 논문이 다루는 첫 번째 문제인 '너무 많은 비지배 해(non-dominated solutions)' 문제입니다.

이 문제를 해결하기 위해, 셰프들은 **유계 아카이브(Bounded Archive)**를 사용합니다. 이것은 레스토랑 쇼윈도에 진열된 "Top 20" 전시 케이스와 같습니다. 여기에는 한 번에 20개의 요리만 담을 수 있습니다. 새로운 요리가 들어오면, 당신은 결정해야 합니다. 이 새 요리를 보관할 것인가, 아니면 자리를 만들기 위해 기존의 요리 하나를 버릴 것인가?

기존 방식: 오직 "맛"만을 바라보기

이전에는 대부분의 셰프(알고리즘)들이 오직 맛과 건강 점수(목표 공간, Objective Space)만을 보고 무엇을 남길지 결정했습니다.

• 적응형 그리드 아카이빙(Adaptive Grid Archiving, AGA): 그들은 메뉴를 여러 구역(예: "매운 맛", "단 맛", "짭짤한 맛")으로 나누었습니다. 만약 특정 구역이 너무 붐비면, 자리를 만들기 위해 무작위로 요리 하나를 내보냈습니다.
• 하이퍼볼륨 아카이빙(Hypervolume Archiving, HA): 그들은 메뉴의 전체적인 "풍미 커버리지(flavor coverage)"를 계산했습니다. 만약 새로운 요리가 기존의 것보다 더 독특한 풍미 커버리지를 더해준다면, 그것을 교체했습니다.

결함: 이러한 방법들은 오직 결과(맛/건강 수치)만을 보았습니다. 그들은 요리가 어떻게 만들어졌는지를 무시했습니다.

• 비유: 상상해 보세요. 맛과 건강 점수가 완전히 똑같은 두 가지 요리가 있습니다. 하나는 연어 구이이고, 다른 하나는 **연어 팬 시어링(Pan-Seared Salmon)**입니다. 메뉴판상으로는 동일해 보이지만(목표 공간), 이들은 매우 다르게 만들어졌습니다(해 공간, Solution Space). 만약 당신이 메뉴판(결과)만 본다면, 이 둘이 서로 다르다고 생각하여 둘 다 보관하거나, 혹은 메뉴판상으로는 달라 보일지라도 실제로는 같은 요리인 두 개의 "연어 구이" 레시피를 실수로 중복해서 보관하게 될 수도 있습니다.

새로운 방식: "레시피"를 바라보기

이 논문의 저자들은 이렇게 말합니다. "잠깐만요! 우리는 최종적인 맛/건강 수치(목표 공간)가 아니라, **재료와 조리법(해 공간)**을 살펴봐야 합니다."

그들은 **해밍 거리 아카이빙(Hamming Distance Archiving, HDAA)**이라는 새로운 다양성 측정 방식을 도입했습니다.

• 비유: "이 두 요리의 맛이 다른가?"라고 묻는 대신, "이 두 레시피 사이의 재료가 얼마나 다른가?"라고 묻는 것입니다.
• 만약 "연어 구이"와 "연어 팬 시어링"이 있다면, 해밍 거리는 작습니다 (조리법만 바뀌었을 뿐입니다).
• 만약 "연어 구이"와 "채소 두부 볶음"이 있다면, 해밍 거리는 매우 큽 (거의 모든 것이 다릅니다).

이 "레시피 체크"를 사용함으로써, 알고리즘은 'Top 20' 전시 케이스에 담긴 요리들이 단순히 맛만 다른 것이 아니라, 만드는 방식에서도 진정으로 서로 다양하도록 보장합니다.

연구 결과

연구진은 복잡한 퍼즐인 **외판원 문제(Traveling Salesman Problem, 배달 트럭의 최적 경로 찾기)**를 사용하여, 이 새로운 "레시피 체크" 방식이 기존의 "맛 체크" 방식들과 어떻게 다른지 테스트했습니다.

그 결과는 다음과 같습니다:

1. 새로운 방식의 승리: "해밍 거리" 방식(HDAA)은 특히 크고 복잡한 문제에서 더 다양하고 고품질인 해(solution) 목록을 유지하는 데 더 뛰어났습니다.
2. 결과만이 전부가 아니다: 해 공간(레시피/구조)에 집중하는 것은 목표 공간(맛/점수)에 집중하는 것만큼이나 중요합니다.
3. 효율성: 진정으로 다양한 "레시피"를 유지함으로써, 탐색 알고리즘은 똑같은 요리를 반복해서 만드는 루프에 빠지지 않고 효율적으로 작동했습니다.

핵심 요약

이 논문은 복잡한 문제를 여러 목표를 가지고 해결하려 할 때, 단순히 최종 숫자만을 봐서는 안 된다고 주장합니다. 당신은 그 숫자를 얻기 위해 어떻게 했는지를 살펴봐야 합니다. "재료"(해의 구조)를 확인하여 다양성을 확보함으로써, 단순히 최종 점수만을 보는 것보다 훨씬 더 훌륭하고 견고한 해답 세트를 얻을 수 있습니다.

요약하자면: 책의 표지(점수)로만 판단하지 말고, 페이지(해의 구조)를 읽어서 당신이 똑같은 이야기를 두 번 읽고 있는 것은 아닌지 확인하세요.