[논문]다중 배낭 문제를 위한 라그랑지안 휴리스틱

윤유림; 김용혁

doi:10.5391/jkiis.2010.20.6.755

다중 배낭 문제를 위한 라그랑지안 휴리스틱
A Lagrangian Heuristic for the Multidimensional 0-1 Knapsack Problem 원문보기

한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.20 no.6, 2010년, pp.755 - 760

윤유림 (서울대학교 컴퓨터공학부) , 김용혁 (광운대학교 컴퓨터소프트웨어학과)

초록
AI-Helper

일반적으로 이산 최적화에서의 라그랑지안 방법은 제약조건을 쉽게 다루기 위한 기법이다. 이 방법은 전형적으로 분지한계법에서 상한을 찾을 때 사용한다. 본 논문은 여러 개의 제약조건이 있는 다중 배낭 문제를 위한 새로운 라그랑지안 방법을 제안한다. 기존 라그랑지안 접근법과는 달리 제안한 방법은 라그랑지안 벡터의 새로운 특징에 기초하여 품질 좋은 하한(즉, 가능 해)을 효율적으로 찾을 수 있다. 잘 알려진 큰 규모의 벤치마크 데이터에서 실험을 하였고 제안한 라그랑지안 방법은 기존 방법의 성능을 개선하였다.

Abstract ▼ AI-Helper

In general, Lagrangian method for discrete optimization is a kind of technique to easily manage constraints. It is traditionally used for finding upper bounds in the branch-and-bound method. In this paper, we propose a new Lagrangian search method for the 0-1 knapsack problem with multiple constraints. A novel feature of the proposed method different from existing Lagrangian approaches is that it can find high-quality lower bounds, i.e., feasible solutions, efficiently based on a new property of Lagrangian vector. We show the performance improvement of the proposed Lagrangian method over existing ones through experiments on well-known large scale benchmark data.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

라그랑지안 방법은 제약식이 있는 최적화 문제에 널리 이용되어 왔다. 다중 배낭 문제와 같은 조합 최적화 문제에서는 보통 좋은 상한 값을 얻는 목적으로만 주로 사용되어 왔는데 이 논문에서는 좋은 가능 해를 찾는 새로운 라그랑지안 방법을 제안하였다. 벤치마크 데이터를 사용한 실험에서는 기존의 라그랑지안 방법들보다 개선된 결과를 얻을 수 있었다.
하지만 이 유전 알고리즘 방법은 단지 기존의 라그랑지안 방법을 자신의 알고리즘에서 평가 함수로만 이용했을 뿐이지 새로운 라그랑지안 방법을 제시한 것은 아니었다. 본 논문에서는 Magazine과 Oguz의 결과를 개선한 연구결과를 제시할 것이다.
이 절에서는 그동안 이산 최적화 문제를 풀기 위해 제안되었던 라그랑지안 방법들에 대해 좀 더 자세히 검토한다. 이산 최적화 문제에 사용되는 라그랑지 승수는 미분이 불가능하다는 성질이 있어서 연속 공간의 최적화 문제에 비해 많은 제한이 있게 된다.
이 절에서는 라그랑지 승수 공간의 탐색을 통해 좋은 가능 해를 찾는 새로운 방법을 제안한다. 제안한 방법의 주된 틀은 적당한 라그랑지 승수 벡터를 찾아 그림 1을 적용하여 얻은 새로운 용량 b^*가 원래 주어진 문제 인스턴스의 용량 b에 최대한 가까우면서 어느 하나라도 주어진 용량을 초과하지 않도록 하는 데에 있다.

가설 설정

두 개의 라그랑지 승수 벡터 λ, λ′가 주어져 있는데 여기에서 λ′은 λ와 k 번째 원소만 다른 값이고(λk ≠ λk′) 나머지 원소는 모두 같다고 가정하자.

제안 방법

라그랑지 승수의 변화량은 이러한 반복이 지속됨에 따라 점차 감소하게 하였다. 단순히 겉으로 드러난 알고리즘 절차의 차원에서 서브그래디언트 알고리즘과 비교를 한다면, 본 논문에서 제안된 방법은 각 단계마다 오직 하나의 라그랑지 승수만을 변화시키는 반면 서브그래디언트 알고리즘은 모든 라그랑지 승수들을 어떤 벡터에 비례하는 양 만큼을 바꾸어 준다는 차이점을 가지게 된다. 기존의 연구인 MO-CONS를 변형한 알고리즘의 시간 복잡도는 O(n²m)이고 (부록 A 참고) 그림 1에 주어진 함수 F(λ)의 계산 복잡도는 O(nm)이므로 제안한 방법의 시간 복잡도는 O(nm(n+N))이 된다.
다중 배낭 문제를 해결하기 위한 방법들이 과거에 많이 연구되어 왔으나 [6-13] 이들 연구는 이산 해 공간을 바로 다루는 접근 방식이 대부분이었다. 이 논문에서는 이산 해 공간을 직접 다루는 대신에 문제의 탐색 공간을 실수 공간으로 변환한 다음에 그 변환된 해 공간을 다루어 간접적인 탐색을 수행한다. 다중 배낭 문제는 여러 개의 제약식이 있는 최적화 문제이다.
이 절에서는 기존의 연구인 MO-CONS 알고리즘[11]의 보다 자세한 절차를 알고 싶어 하는 독자를 위해 조금 더 구체적인 정보를 제공한다. 그림 4는 MO-CONS의 방법을 의사 코드로 표현한 내용이다.
기존의 MO-CONS는 결정적 알고리즘인데 이는 변화시킬 라그랑지 승수가 매 단계마다 유일하게 결정되기 때문이다. 일단 본 논문에서는 매 단계마다 변화시킬 라그랑지 승수를 임의로 정하게 하는 변형된 MO-CONS(구체적인 내용은 부록 A와 그림 4 참고)를 이용하여 라그랑지 승수 벡터를 초기화하였다. 여기에서 시작하여 정해진 회수 N만큼 다음 단계를 반복 수행한다.
그림 2는 이 논문에서 제안한 새로운 라그랑지안 방법(NLS)을 보여준다. 제안한 방법은 반복적으로 임의의 하나의 라그랑지 승수를 변화시키는 방법이다. 기존의 MO-CONS는 결정적 알고리즘인데 이는 변화시킬 라그랑지 승수가 매 단계마다 유일하게 결정되기 때문이다.

대상 데이터

실험은 OR-Library에 있는 제약식을 30개 가지고 있는 잘 알려진 벤치마크(benchmark) 데이터를 가지고 수행하였다[28]. 이들은 총 90개의 문제 인스턴스(instance)로 구성된다.

데이터처리

각 수치는 30개 인스턴스 결과의 평균치를 의미한다. 변형된 MO-CONS와 NLS는 실행할 때마다 결과가 달라지는 비결정적(non-deterministic) 알고리즘이므로 1,000번씩 수행하여 얻은 결과들의 평균 값(Avg)과 제일 좋은 값(Best)을 구해 통계 내었다. 변형된 MO-CONS는 단일 수행으로는 MO-CONS를 능가하지 못했지만 여러 번 수행하면 MO-CONS보다 더 좋은 결과를 얻을 수 있음을 확인할 수 있었다.
이 논문에서 제안한 방법 NLS와 가능 해를 찾는데 이용된 기존 라그랑지안 방법의 성능을 비교한다. 비교 대상의 하나는 실행할 때마다 늘 같은 결과를 내는 결정적(deterministic) 알고리즘인 MO-CONS[11]이고 다른 하나는 본 논문에서 변형시킨 비결정적 MO-CONS이다.

이론/모형

배낭 문제(knapsack problem)는 오직 하나의 제약조건이 있는 문제로 그 문제 형태가 단순하여 단순한 휴리스틱 알고리즘도 매우 잘 작동하며 지금껏 근사최적해(near-optimal solution)를 찾기 위한 효율적인 근사(approximation) 알고리즘에 대한 연구도 많이 이루어져 왔다[2-5]. 이 논문에서는 탐색이 그리 쉽지 않은, 둘 이상의 제약조건이 있는 다중 배낭 문제(multidimensional 0-1 knapsack problem)를 다룬다.

성능/효과

다중 배낭 문제와 같은 조합 최적화 문제에서는 보통 좋은 상한 값을 얻는 목적으로만 주로 사용되어 왔는데 이 논문에서는 좋은 가능 해를 찾는 새로운 라그랑지안 방법을 제안하였다. 벤치마크 데이터를 사용한 실험에서는 기존의 라그랑지안 방법들보다 개선된 결과를 얻을 수 있었다. 현재는 제안한 방법의 결과가 다중 배낭 문제를 풀이하기 위해 제안된 최고 성능(state-of-the-art)의 알고리즘[12,28]보다는 성능이 개선되었다고 말할 수 있는 수준이 아니지만 제안된 방법을 다른 방법과 결합함으로써 더 개선할 수 있을 것이다.
변형된 MO-CONS와 NLS는 실행할 때마다 결과가 달라지는 비결정적(non-deterministic) 알고리즘이므로 1,000번씩 수행하여 얻은 결과들의 평균 값(Avg)과 제일 좋은 값(Best)을 구해 통계 내었다. 변형된 MO-CONS는 단일 수행으로는 MO-CONS를 능가하지 못했지만 여러 번 수행하면 MO-CONS보다 더 좋은 결과를 얻을 수 있음을 확인할 수 있었다. 변형된 MO-CONS의 결과를 초기해로 시작하는 NLS는 MO-CONS와 변형된 MO-CONS보다 월등히 좋은 결과를 보여주었다.
변형된 MO-CONS는 단일 수행으로는 MO-CONS를 능가하지 못했지만 여러 번 수행하면 MO-CONS보다 더 좋은 결과를 얻을 수 있음을 확인할 수 있었다. 변형된 MO-CONS의 결과를 초기해로 시작하는 NLS는 MO-CONS와 변형된 MO-CONS보다 월등히 좋은 결과를 보여주었다. 절대적수치만 본다면 라그랑지안 방법에서는 물건의 개수가 많아질수록 성능이 더 좋은 것을 볼 수 있다.
제안된 라그랑지안 방법은 제약식이 더 많을수록, 물건의 개수가 더 많을수록 더 좋은 성능을 보이는 경향을 가지고 있는데 문제 크기가 커질수록 문제가 더 어려워진다는 일반적인 사실을 깨는 직관적이지 않은 행동 패턴을 보이고 있다. 이러한 특성에 관한 더 자세한 실험적인 관찰과 이에 대한 이론적인 분석을 앞으로의 연구 과제로 남긴다.

후속연구

예를 들어, 제안된 방법으로 얻어진 가능 해들을 다른 메타 휴리스틱의 초기해로 사용할 수도 있다. 또한 제안된 방법은 MO-CONS를 월등히 개선한 방법이므로 Raidl의 유전 알고리즘[24]에서 MO-CONS 대신에 본 논문에서 제안된 NLS를 사용한다면 더 월등한 성능 향상을 보일 것으로 기대한다. 이런 다른 휴리스틱과의 결합을 통해 더 좋은 결과를 얻을 수 있는 가능성이 많으므로 앞으로 연구할 가치가 충분히 있다.
물론 제약식이 있는 모든 조합 최적화 문제에 적용 가능한 것은 아니다. 라그랑지 승수를 사용하여 완화된 문제의 최적해를 쉽게 구할 수 있는 문제들, 예를 들면 일반화된 할당 문제(generalized assignment problem)나 다중 컨테이너 패킹 문제(multiple container packing problem) 등과 같은 문제는 이미 라그랑지안 방법의 적용이 용이한 문제로 알려져 있으며 이들 문제에 본 논문의 접근 방식과 유사한 라그랑지안 탐색 방법을 사용하면 좋은 가능 해를 얻을 수 있을 것으로 기대한다.
본 논문의 연구 결과는 또한 제약조건이 있는 다른 조합 최적화 문제에도 적용될 수 있다. 물론 제약식이 있는 모든 조합 최적화 문제에 적용 가능한 것은 아니다.
제안된 라그랑지안 방법은 제약식이 더 많을수록, 물건의 개수가 더 많을수록 더 좋은 성능을 보이는 경향을 가지고 있는데 문제 크기가 커질수록 문제가 더 어려워진다는 일반적인 사실을 깨는 직관적이지 않은 행동 패턴을 보이고 있다. 이러한 특성에 관한 더 자세한 실험적인 관찰과 이에 대한 이론적인 분석을 앞으로의 연구 과제로 남긴다.
또한 제안된 방법은 MO-CONS를 월등히 개선한 방법이므로 Raidl의 유전 알고리즘[24]에서 MO-CONS 대신에 본 논문에서 제안된 NLS를 사용한다면 더 월등한 성능 향상을 보일 것으로 기대한다. 이런 다른 휴리스틱과의 결합을 통해 더 좋은 결과를 얻을 수 있는 가능성이 많으므로 앞으로 연구할 가치가 충분히 있다.
벤치마크 데이터를 사용한 실험에서는 기존의 라그랑지안 방법들보다 개선된 결과를 얻을 수 있었다. 현재는 제안한 방법의 결과가 다중 배낭 문제를 풀이하기 위해 제안된 최고 성능(state-of-the-art)의 알고리즘[12,28]보다는 성능이 개선되었다고 말할 수 있는 수준이 아니지만 제안된 방법을 다른 방법과 결합함으로써 더 개선할 수 있을 것이다. 예를 들어, 제안된 방법으로 얻어진 가능 해들을 다른 메타 휴리스틱의 초기해로 사용할 수도 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	서브그래디언트 알고리즘은 무엇을 생성하기 위해 사용되나?	그동안의 연구는 이러한 문제를 극복하려는 시도로 주로 서브그래디언트(subgradient) 알고리즘에 초점을 두어 왔다. 서브그래디언트 알고리즘은 분지 한계법을 위한 상한(upper bound)을 생성하기 위해 사용된다. 이러한 방법을 라그랑지안 완화법(Lagrangian relaxation)이라 부른다[19,25].
	배낭 문제는 무엇인가?	다중 배낭 문제는 NP-완전(complete) 문제로 잘 알려진 배낭 문제의 확장된 형태로 이해할 수 있다[1]. 배낭 문제는 크기(size)와 가치(profit)를 갖는 물건(object)의 집합이 주어지면 배낭의 용량(capacity)을 넘지 않는 선에서 가치가 최대가 되도록 물건을 배낭에 담는 방법을 찾는 문제이다. 다중 배낭 문제의 경우에는 용량에 대한 제약조건이 둘 이상이 된다.
	이 논문에서 제안한 새로운 라그랑지안 방법은 어떤 방법인가?	그림 2는 이 논문에서 제안한 새로운 라그랑지안 방법(NLS)을 보여준다. 제안한 방법은 반복적으로 임의의 하나의 라그랑지 승수를 변화시키는 방법이다. 기존의 MO-CONS는 결정적 알고리즘인데 이는 변화시킬 라그랑지 승수가 매 단계마다 유일하게 결정되기 때문이다.

참고문헌 (28)

M. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
A. Caprara, H. Kellerer, U. Pferschy, and D. Pisinger, "Approximation algorithms for knapsack problems with cardinality constraints," European Journal of Operational Research, Vol.123, pp. 333-345, 2000.

상세보기
H. Kellerer and U. Pferschy, "A new fully polynomial approximation scheme for the knapsack problem," In Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 123-134, 1998.
E. L. Lawler, "Fast approximation algorithms for knapsack problems," In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pp. 206-213, 1997.
S. Sahni, "Approximate algorithms for the 0/1 knapsack problem," Journal of the ACM, Vol. 22, pp. 115-124, 1975.

상세보기
C. Chekuri and S. Khanna, "A PTAS for the multiple knapsack problem," In Proceedings of the Symposium on Discrete Algorithms, pp.213-222, 2000.
P. C. Chu, A genetic algorithm approach for combinatorial optimization problems. PhD thesis, The management school, imperial college of science, London, 1997.
A. Freville and G. Plateau, "An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem," Discrete Applied Mathematics, Vol. 49, pp. 189-212, 1994.

상세보기
A. M. Frieze and M. R. B. Clarke, "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses," European Journal of Operational Research, Vol. 15, pp. 100-109, 1984.

상세보기
B. Gavish and H. Pirkul, "Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality," Mathematical Programming, Vol. 31, pp. 78-105, 1985.

상세보기
M. J. Magazine and O. Oguz, "A heuristic algorithm for the multidimensional zero-one knapsack problem," European Journal of Operational Research, Vol. 16, pp. 319-326, 1984.

상세보기
G. R. Raidl, "An improved genetic algorithm for the multiconstrained 0-1 knapsack problem," In Proceedings of the IEEE Conference on Evolutionary Computation, pp. 207-211, 1998.
M. Vasquez and J.-K. Hao, "A hybrid approach for the 0-1 multidimensional knapsack problem," In Proceedings of the 17th International Joint Conference on Articial Intelligence, pp. 328-333, 2001.
D. G. Luenberger, Optimization by Vector Space Methods. John Wiley & Sons, Inc., 1969.
G. L. Nemhauser and L. A. Wolsey, Inter and Combinatorial Optimization. John Wiley & Sons, Inc., 1988.
L. A. Wolsey, Integer Programming, John Wiley & Sons, Inc., 1998.
Y.-J. Chang and B. W. Wah, "Lagrangian techniques for solving a class of zero-one integer linear programs," In Proceedings of the Computer Software and Applications Conference, pp. 156-161, 1995.
B. Gavish, "On obtaining the 'best' multipliers for a Lagrangean relaxation for integer programming," Computers & Operations Research, Vol. 5, pp. 55-71, 1978.

상세보기
A. M. Geoffrion, "Lagrangian relaxation for integer programming," Mathematical Programming Study," Vol. 2, pp. 82-114, 1974.
D. Schuurmans, F. Southey, and R. C. Holte, "The exponentiated subgradient algorithm for heuristic boolean programming," In Proceedings of the International Joint Conferences on Artificial Intelligence, pp. 334-341, 2001.
B. W. Wah and Y. Shang, "A discrete Lagrangian-based global-search method for solving satisability problems," In D.-Z. Du, J. Gu, and P. Pardalos, editors, Satisability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 365-392. 1997.
B. W. Wah and Z. Wu, "The theory of discrete Lagrange multipliers for nonlinear discrete optimization," In Principles and Practice of Constraint Programming, pp. 28-42, 1999.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., 1990.
G. R. Raidl, "Weight-codings in a genetic algorithm for the multiconstraint knapsack problem," In Proceedings of the Congress on Evolutionary Computation, Vol. 1, pp. 596-603, 1999.
R. K. Martin, Large Scale Linear and Integer Optimization: A Unified Approach. Kluwer Academic Publishers, 1998.
M. L. Fisher, "The Lagrangian relaxation method for solving integer programming problems," Management Science, Vol. 27, No. 1, pp. 1-18, 1981.

상세보기
J. F. Shapiro, "A survey of Lagrangian techniques for discrete optimization," Annals of Discrete Mathematics, Vol. 5, pp. 113-138, 1979.
P. C. Chu and J. E. Beasley, "A genetic algorithm for the multidimensional knapsack problem," Journal of Heuristics, Vol. 4, pp. 63-86, 1998.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증