고객지원
기술문의
Dispatcher 관련 문의
- 강경환
- 2004.08.03
- 조회수 1,535
KSTEC의 무궁한 발전을 기원합니다.
귀사의 ILOG product가 연구에 많은 도움이 되고 있습니다.
Dispatcher에 나오는 improvement 과정에서 적용되는 휴리스틱을 아래와 같이 코딩했을때 그 적용방법은 어떻게 되나요?
IloNHood nhood = IloTwoOpt(env)
+ IloOrOpt(env)
+ IloRelocate(env)
+ IloExchange(env)
+ IloCross(env);
즉
1. twoopt를 마치고 oropt, relocate, exchange, cross 의 순서대로 적용이 되는지,
2. 아니면 랜덤하게 적용이 되는지,
3. 아니면 local optimum에 왔을경우 heuristic이 바뀌는지요?
3번같은 경우에 메타휴리스틱의 코드상에는 그러한 옵션을 조정하게하는 코드가 없더군요.
매뉴얼에도 각 heuristic별 적용방법은 나와있으나, 제가 궁금한 내용은 없습니다. 혹시 알고계시면 리플부탁드립니다. 아울러 관련 문헌이 있으면 같이 부탁드립니다.
감사합니다.
귀사의 ILOG product가 연구에 많은 도움이 되고 있습니다.
Dispatcher에 나오는 improvement 과정에서 적용되는 휴리스틱을 아래와 같이 코딩했을때 그 적용방법은 어떻게 되나요?
IloNHood nhood = IloTwoOpt(env)
+ IloOrOpt(env)
+ IloRelocate(env)
+ IloExchange(env)
+ IloCross(env);
즉
1. twoopt를 마치고 oropt, relocate, exchange, cross 의 순서대로 적용이 되는지,
2. 아니면 랜덤하게 적용이 되는지,
3. 아니면 local optimum에 왔을경우 heuristic이 바뀌는지요?
3번같은 경우에 메타휴리스틱의 코드상에는 그러한 옵션을 조정하게하는 코드가 없더군요.
매뉴얼에도 각 heuristic별 적용방법은 나와있으나, 제가 궁금한 내용은 없습니다. 혹시 알고계시면 리플부탁드립니다. 아울러 관련 문헌이 있으면 같이 부탁드립니다.
감사합니다.
댓글 3
-
- 김용환2004-08-03
- 안녕하세요~
Dispatcher에 대해서 공부를 많이 하신듯 하네요 ^^
질문에 답변부터 드리면 골의 순서에 따라서 탐색하게 됩니다.
즉 골의 순서가
IloNHood nhood = IloTwoOpt(env)
+ IloOrOpt(env)
+ IloRelocate(env)
+ IloExchange(env)
+ IloCross(env);
이것일 때 TwoOpt -> OrOpt -> Relocate ... 순으로 탐색을 하게 됩니다.
즉 TwoOpt의 골에서 해의 개선이 더이상 이루어지지 않으면 OrOpt 골이 실행 됩니다.
참고로 TwoOpt나 OrOpt 는 경로내 개선 방법이기 때문에 경로간 개선 골을 우선 하시는게 개선 속도가 훨씬 빠릅니다.
즉,
IloNHood nhood = IloRelocate(env)
+ IloExchange(env)
+ IloCross(env)
+ IloTwoOpt(env)
+ IloOrOpt(env);
이렇게 하시는게 좋구요.
그리고 Local에 빠진후 자동으로 다른 골로 변경 되는것은 아니구요, Dispatcher에서 제공하고 있는 GLS, Tabu 등 여러가지 MetaHeuristics가 제공하고 있으니 메뉴얼을 참조 하시면 될듯합니다.
좋은 하루 되세요~
-
- 강경환2004-08-04
- 친절한 답변에 감사드립니다.김용환님.
한가지 추가적 질문을 드릴께요.
GLS에서 local minimum에 빠졌을 경우 기존의 목적함수 c 에다가
w*p 의 패널티 비용을 더한 c+wp의 목적함수를 줄이기 위해 현재의 해에서 이동을 한다고 매뉴얼에 되어있더군요.
<질문>
1. 이때 w의 경우는 계수로서 작용하는것 같구요. 코드에 이렇게 나와있는 부분이 맞는지요? w=0.1 같은데요?
IloDispatcherGLS dgls(env, 0.1);
2. p의 경우는 코드상에서 조정할 수있는 부분이 없는것 같은데요.
p의 의미는 무엇이고, GLS에서 어떻게 영향을 미치게 되나요?
감사합니다. 좋은 하루 되시기 바랍니다.
-
- 김용환2004-08-04
- 안녕하세요~
먼저 Tabu 서치를 이해하고 계시면 그것과 비교해서 설명 드리는게 이해가 빠를듯합니다.
Tabu Search: 해를 가장 많이 개선시키는 Factor가 수정되려고 할때 tabu를 부여하여 지역해를 탈출 하려고 시도
GLS: 이전에 탐색했던 지역해를 다시 탐색하려고 할때 목적함수에 금지비용을 더하여 지역해를 탈출 시도
즉 Tabu는 해를 가장 많이 개선 시킨 factor에 관심을 가지는 반면 GLS는 목적함수 자체에 관심을 가지는것이 다릅니다.
그리고 언급하신 수식이 정확한 것은 아니지만 대략 c+wp 의 의미만을 놓고 보면 w는 페널티 인자 입니다.
IloDispatcherGLS dgls(env, 0.1); 에서 0.1이 w 이구요 ^^
대략 0.1 ~ 0.3 안에서 좋은 값을 가지며 0.2에서 가장 좋은 값을 가진다고 합니다.
실제로 실험을 해보면 같은 결과를 나타냅니다.
그렇다면 페널티 인자가 작을때(0.1)의 의미와 클때의 의미(0.3)는 어떻게 다른가 라는 질문이 있을수 있는데 작은경우에는 해가 difversification하게 되며, 큰경우에는 intensification 하게 됩니다.
따라서 문제의 특성에 따라서 값을 바꿔가며 실험 하시면 될듯합니다.
p의 의미는 구성요소가 페널티를 받은 횟수를 의미합니다.
즉, 말씀하신대로 파라메터로 값을 주는것이아니라 내부적으로 계산되는 값입니다.
덧붙여서 좋지 않은 구성요소에 페널티가 집중되어 해가 국지에 머무는것을 방지하기 위해서 c/(p+1)과 같은 방법으로 페널티를 주게 됩니다.
알고리즘에 대한 이해는 디스페쳐 메뉴얼만을 보고는 이해하시기가 힘들듯합니다. 사실 머리가 아프기도 하구요 ^^
좀더 깊이 있는 이해를 원하신다면 첨부한 논문을 참고 하시거나 별도로 공부하시는게 좋을듯 합니다.
수고하세요~ ^^
목록
확인