[메타 휴리스틱] 해독 전략(decoding strategy)

 

이번 글의 내용은 전남대학교 산업공학과 김여근 교수님의 메타휴리스틱 교재 정리 및 참조하였음을 먼저 밝힙니다.

(다른 참조한 논문과 자료들은 아래에 기재되어 있습니다.) 

 

 

이 포스트는 "메타 휴리스틱" 책의 내용을 참조 및 공부한 것을 바탕으로 제가 이해한 정보를 추가하여 쓰여졌습니다.  

 

 

혹시 제가 잘못 알고 있는 점이나 보완할 점 있다면 댓글로 알려주시면 감사하겠습니다. 

 

---

 

 

※ 해독전략은 각 표현을 해독하여 가능해로 변환시키는 전략입니다. 

 

이 전략은 표현(encoding)이 간접적일 때 사용됩니다. 이 전략이 효과적이기 위해서는 간접적인 표현이 적용 문제의 특성을 반영할 수 있어야 하고, 이 표현에 사용되는 연산자도 연산 후 표현의 해독 결과가 과거의 주요 탐색 정보가 다음 세대의 자손(해)에게 상속될 수 있는 의미 있는 연산을 수행할 수 있어야 합니다.

 

---

 

 

작업 선행공정도

 

예를 위해서 다시 작업 선행공정도 그림을 보았을때, 작업 1부터 9까지 나열된 순열 표현에서 나타난 작업의 순서는 절대적 작업 할당 순서가 아니라 상대적인 순서를 나타낸다고 합니다. 이러한 순열이 (2, 7, 1, 4, 5, 6, 3, 8, 9)로 둡니다. 이 표현을 다음과 같이 해독하여 가능해를 유도할 수 있습니다. 초기에 할당된 작업집합은 공집합입니다. 이때 선행관계에 의해 할당가능 작업집합은 {1, 2} 입니다.

 

표현에서 작업 2가 작업 1보다 앞에 있으므로 작업(2)를 할당합니다. 작업 2가 할당된 후 선행관계에 의해 다음 할당가능 작업은 {1, 5}이고 표현에서 작업 1이 작업 5앞에 있으므로 작업 1을 할당하여 (2, 1)이 됩니다. 같은 방법으로 다음 할당가능 작업집합은 {3, 4, 5}이고 이들 작업 中에서 표현에서 작업 4가 가장 앞에 나타나므로 작업 4를 할당하여 (2, 1, 4)가 됩니다. 같은 방법으로 반복하면 가능해 (2, 1, 4, 5, 7, 3, 6, 8, 9)를 얻습니다.

 

또한 상대적 할당 순서를 범위 (0, 1)의 난수로 나타내고, 큰 값이 할당 순위가 높다는 것을 의미한다고 합니다. 이러한 표현을 해독하여 가능해를 생성할 수 있습니다. 예로 표현 (0.46, 0.86, 0.12, 0.29, 0.88, 0.36, 0.23, 0.91, 0.42)를 보았을때, 앞의 설명에서와 유사하게, 처음 할당가능작업집합은 {1, 2}이고, 첫째와 둘째 위치에 있는 난수가 0.46과 0.86입니다.

 

이 중에서 큰 값 (0.86)을 갖는 난수의 위차가 두 번째이므로 작업 2를 할당합니다. 다음 할당가능집합은 {1, 5}이고 첫째와 다섯째 위치에 있는 난수는 각각 0.46, 0.88 이므로 더 큰 값을 갖는 위치의 작업 5을 할당합니다. 그러면 할당작업과 순서는 (2, 5)가 됩니다. 같은 방법으로 다음 할당가능 작업집합은 {1}로 유일하여 이를 할당하면 (2, 5, 1)이 됩니다. 같은 방법으로 반복하면 선행제약을 만족하는 작업할당 순서(2, 5, 1, 4, 7, 8, 3, 6, 9)를 얻습니다.

 

 

 

 

긴글 읽어주셔서 감사합니다.

 

---

 

 

[References]

 

 

[1] Y. Kim. (2017). 메타휴리스틱스, Metaheuristics

 

[2] Nanda, S. J., & Panda, G. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary Computation, 16, 1–18.