[메타 휴리스틱] 가능해 보존전략(preserving strategy)

 

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

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

 

 

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

 

 

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

 

---

 

※ 가능해 보존전략은 제약이 있는 최적화문제에서, 특정 표현과 연산자를 사용하여 제약을 만족하는 가능해 만을 생산하는 전략입니다. 

 

 

이는 초기에 가능해(또는 가능해 집단)로 시작해야 합니다. 특정 문제, 예로 색칠하는 문제에서는 초기 가능해를 찾기가 쉽지 않습니다. 또한 제약이 강한 문제에서 항상 가능해를 생산하는 연산자를 개발하기도 쉽지 않습니다. 설사 이런 연산자가 개발되어도 알고리즘의 성능이 우수하다는 보장이 없습니다.

 

---

 

 

이 전략의 예를 보이기 위해서는 앞에서 사용한 작업할당 문제를 다시 관찰하였을 때, 작업선행 관계에 따라 2개의 가능한 두 작업할당 순서 P1=(1, 2, 3, 4, 5, 6, 7, 8, 9)와 P2= (2, 1, 5, 4, 7, 8, 3, 6, 9)를 보았을때, 이들 2개 가능해를 선행관계의 특성을 이용하여 다음과 같이 연산하면 가능해를 얻을 수 있습니다. 해 표현(개체)에서 임의로 두 절단점을 잡습니다. 두 절단점에 의해 앞부분, 중간부분, 뒷부분으로 나눌 수 있습니다.

 

한 개체(P1)의 앞부분과 뒷부분에 있는 작업(인자)을 새로운 해(자손)애개 상속해야 합니다. 그리고 다른 개체(P2)에서 부모 P1으로부터 상속된 인자를 모두 지우고, 남은 작업(인자)들을 부모 P2에서 나타난 순서대로 새로운 해(자손)의 중간부분에 차례로 상속하게 됩니다. 이러한 연산은 부모가 가능해이면 항상 가능해를 유지합니다.

 

두 절단점이 두 번째와 세 번째 인자 사이, 그리고 여섯 번째와 일곱 번째 사이라 하였을때, P1의 앞, 중간, 뒷부분은 각각(1, 2), (3, 4, 5, 6), (7, 8, 9)가 됩니다. 따라서 하나의 자손 개체는 (1, 2, *, *, *, *, 7, 8, 9)가 되고 중간부분은 P2에서 작업 1, 2, 7, 8, 9를 삭제하고남은 작업이 나타난 순서는 5, 4, 3, 6 입니다. 이를 자손 개체 중간부분에 삽입하면 (1, 2, 5, 4, 3, 6, 7, 8, 9)가 됩니다. 

 

또 다른 자손을 생산하려면 두 부모의 역할을 바꾸어 생산하고, 그러면 다른 새로운 개체는 앞부분과 뒷부분은 (2, 1, *, *, *, *, 3, 6, 9)가 되고, 중간부분은 P1에서 남은 작업이 나타난 순서 4, 5, 7, 8을 삽입하면 (2, 1, 4, 5, 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.