[논문]일반화된 배정 문제의 k-opt 교환 최적화 알고리즘

이상운

doi:10.7236/jiibc.2023.23.5.151

초록
AI-Helper

NP-난제로 다항시간으로 최적 해를 찾는 알고리즘이 제안되지 않고 있는 일반화된 배정 문제에 대해 기존에는 전적으로 메타휴리스틱 기법들에 치중하여 연구가 진행되었다. 반면에, 본 논문에서는 해를 찾아가는 규칙을 가진 휴리스틱 탐욕 알고리즘을 제안한다. 첫 번째로, m대의 기계(용기)에 n개의 작업(물품)을 담을 수 있도록 l = n/m개가 되도록 각 기계의 용량 b_i에 대해 가중치 w_ij ≤ b_i/l 데이터로 축소시킨다. 축소된 데이터들을 대상으로 각 작업의 최대 이득 작업을 해당 기계에 배정하였다. 두 번째로, 각 기계에 배정된 가중치 합이 기계 용량을 초과하지 않도록 배정을 조정하였다. 마지막으로 이득을 최대화시키기 위해 k-opt 교환 최적화를 수행하였다. 제안된 알고리즘을 50개 벤치마킹 데이터들에 적용한 결과 약 1/3 데이터에 대해서는 알려진 최적 해를 찾을 수 있었으며, 나머지 2/3 데이터에 대해서는 메타휴리스틱 기법들과 견줄만한 결과를 보였다. 따라서 제안된 알고리즘은 GAP에 대해 다항시간으로 해를 찾아가는 규칙이 존재할 가능성을 보여 NP-난제에서 P-문제로 될 수 있음을 실험을 통해 증명하였다.

Abstract ▼ AI-Helper

The researchers entirely focused on meta-heuristic method for generalized assignment problem(GAP) that is known as NP-hard problem because of the optimal solution within polynomial time algorithm is unknown yet. On the other hand, this paper proposes a heuristic greedy algorithm with rules for findi...

The researchers entirely focused on meta-heuristic method for generalized assignment problem(GAP) that is known as NP-hard problem because of the optimal solution within polynomial time algorithm is unknown yet. On the other hand, this paper proposes a heuristic greedy algorithm with rules for finding solutions. Firstly, this paper reduces the weight matrix of original data to wij ≤ bi/l in order to n jobs(items) pack m machines(bins) with l = n/m. The maximum profit of each job was assigned to the machine for the reduced data. Secondly, the allocation was adjusted so that the sum of the weights assigned to each machine did not exceed the machine capacity. Finally, the k-opt swap optimization was performed to maximize the profit. The proposed algorithm is applied to 50 benchmarking data, and the best known solution for about 1/3 data is to solve the problem. The remaining 2/3 data showed comparable results to metaheuristic techniques. Therefore, the proposed algorithm shows the possibility that rules for finding solutions in polynomial time exist for GAP. Experiments demonstrate that it can be a P-problem from an NP-hard.

주제어

표/그림 (5)

그림 그림 1. GAP-1 예제 Fig. 1. Example of GAP-1
그림 그림 2. k-opt 교환 최적화 Fig. 2. k-opt swap optimization
그림 그림 3. GAP-1 문제에 대한 k-opt SOA Fig. 3. k-opt SOA for GAP-1 example problem
표 표 1. 실험 데이터의 해 Table 1. Solution for experimental data
그림 그림 4. GAP 실험데이터의 k-opt SOA Fig. 4. k-opt SOA for GAP experimental data

AI 본문요약
AI-Helper

문제 정의

따라서 본 연구는 GAP은 다항시간으로 최적 해를 찾아가는 규칙이 존재하지 않는다는 전제하에 컴퓨터의 도움을 받아 메타휴리스틱 기법들로 다항시간으로 근사 해를 찾아가는 방식에서 탈피하여 역발상으로 다항시간 정확한 알고리즘의 존재 가능성에 대한 연구 방향을 전환시킬 수 있는 토대를 제시하였다는 점에서 연구 의의를 찾을 수 있다.
본 논문은 NP-난제로 분류된 GAP에 대해 다항시간으로 근사 해를 찾아가는 규칙인 휴리스틱 탐욕 알고리즘을 제안하였다.

제안 방법

용량을 초과한 상자의 물품을 여유가 있는 상자로 옮겨 모든 상자의 용량 제약조건을 충족시켰다. 마지막으로 GAP에 특화된 이득을 극대화시키는 k-opt 교환 최적화 기법을 제안하여 적용하였다.
제안된 방법은 이득 극대화와 가중치 충족의 2가지 목표를 모두 만족하는 대상 선정 기준을 적용하여 데이터를 축소시킨 후 이들 중 각 열에서 최대 이득을 가진 데이터를 선택하여 상자를 채웠다. 용량을 초과한 상자의 물품을 여유가 있는 상자로 옮겨 모든 상자의 용량 제약조건을 충족시켰다.

대상 데이터

제안된 알고리즘을 GAP 벤치마킹 데이터들에 적용한 결과 1/3 데이터는 기존에 알려진 최적 해를 찾는데 성공하였으며, 나머지 2/3 데이터는 근사 해를 구하였다. 이는 GAP에 적용될 수 있는 다항시간 탐욕 알고리즘인 k-opt를 가시적, 수기식으로 적용한 결과 k-opt(k≥3)의 판단 어려움으로 인해 발생된 현상으로, 만약 이를 프로그래밍으로 구현한다면 보다 좋은 결과를 얻을 수 있으리라 기대된다.

성능/효과

50개의 GAP 벤치마킹 데이터들 중에서 18개 데이터에 대해서는 기존에 알려진 최적 해를 찾는데 성공하였다. 나머지 32개 데이터에 대해서는 기존에 메타휴리스틱 기법들로 찾은 최적 해에 편차를 가진 근사한 결과를 얻을 수 있었다.
나머지 32개 데이터에 대해서는 기존에 메타휴리스틱 기법들로 찾은 최적 해에 편차를 가진 근사한 결과를 얻을 수 있었다. 결론적으로 메타휴리스틱 기법의 MMAS와 GRASP에 비해서는 보다 좋은 결과를 나타내어 10개 알고리즘 중 8위로 메타휴리스틱 기법들과 경쟁할 수 있는 수준의 결과를 보였다.

후속연구

본 논문에서 제안된 k-opt 알고리즘을 보다 향상시킨 진화된 k-opt(advanced k-opt)를 적용한다면 모든 데이터들에 대해 최적 해를 찾을 수 있을 것으로 판단된다. 따라서 추후 이 분야의 연구를 지속적으로 수행할 예정이다.
본 논문에서 제안된 k-opt 알고리즘을 보다 향상시킨 진화된 k-opt(advanced k-opt)를 적용한다면 모든 데이터들에 대해 최적 해를 찾을 수 있을 것으로 판단된다. 따라서 추후 이 분야의 연구를 지속적으로 수행할 예정이다.
이는 GAP에 적용될 수 있는 다항시간 탐욕 알고리즘인 k-opt를 가시적, 수기식으로 적용한 결과 k-opt(k≥3)의 판단 어려움으로 인해 발생된 현상으로, 만약 이를 프로그래밍으로 구현한다면 보다 좋은 결과를 얻을 수 있으리라 기대된다.

참고문헌 (12)

P. C. Chu and J. E. Beasley, "A Genetic Algorithm for the Generalized Assignment Problem," Computers & Operations Research, Vol. 24, No. 1, pp. 17-23, Jan. 1997, https://doi.org/10.1016/S0305- 0548(96)00032-9？

상세보기
L. Ozbakir, A. Baykasoglu, and P. Tapkan, Pinar, "Bees Algorithm for Generalized Assignment Problem," Applied Mathematics and Computation, Vol. 215, No. 11, pp. 3782-3795, Feb. 2010, https://doi.org/10.1016/j. amc.2009.11.018？

상세보기
R. M. Nauss, "Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach," Informs Journal on Computing, Vol. 15, No. 3, pp. 249-266, Aug. 2003, https://doi.org/10.1287/ijoc.15.3.249.16075？

상세보기
P. Avella, M. Boccia, and I. Vasilyev, "A Computational Study of Exact Knapsack Separation for the Generalized Assignment Problem," Computational Optimization and Applications, Vol. 45, No. 3, pp. 543-555, Apr. 2010, https://doi.org/10.1007/s10589-008-9183-8？

상세보기
I. H. Osman, "Heuristics for the Generalised Assignment Problem : Simulated Annealing and Tabu Search Approaches," Operations Research Spektrum, Vol. 17, pp. 211-225, Dec. 1995.？

상세보기
S. U. Lee, "Time-Cost Optimization Algorithm for Generalized Assignment Problem," Journal of KIIT, Vol. 14, No. 5, pp. 147-153, May 2016, http://doi.org/10.14801/jkiit.2016.14.5.147？

상세보기
H. R. Lourenco and D. Serra, "Adaptive Approach Heuristics for the Generalized Assignment Problem," Economics Working Papers 288, pp. 1-28, Department of Economics and Business, Universitat Pompeu Fabra. May 1998, http://hdl. handle.net/10230/292？
K. Supriya, B. Kajla, and M. Sathi, "Solution of a Class of Generalized Assignment Problem," Journal of Intelligent & Fuzzy Systems, Vol. 33, No. 3, pp. 1687-1697, Aug. 2017, https://doi.org/10.3233/JIFS-17086？

상세보기
M. B. Akbulut and E. Yilmaz "A Modified Genetic Algorithm for the Generalized Assignment Problem," Istanbul University - Journal of Electrical and Electronics Engineering, Vol. 9, No. 2, pp. 951-958, Jul. 2009.？
J. E. Beasley, "OR-Library : Generalized Assignment Problem," http://people.brunel.ac.uk/~astjjb/eb/orlib/gapinfo.html, Retrieved Jul. 2021.？
T. H. Man, "An Algorithm for Multi-Objective Assignment Problem," Master Thesis, Chinese University of Hong Kong, Jun. 2005.？
SAS, "SAS Optimization 8.3 Mathematical Optimization Procedures: Chapter 18. The Decomposition Algorithm, Example 18.2. Generalized Assignment Problem," pp. 902-908, SAS, Jul. 2018.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

일반화된 배정 문제의 k-opt 교환 최적화 알고리즘
Optimization Algorithm for k-opt Swap of Generalized Assignment Problem 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (5)

표/그림 (5)

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

일반화된 배정 문제의 k-opt 교환 최적화 알고리즘 Optimization Algorithm for k-opt Swap of Generalized Assignment Problem 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (5) 모든 표/그림 보기

표/그림 (5) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

이상운 (190)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

일반화된 배정 문제의 k-opt 교환 최적화 알고리즘
Optimization Algorithm for k-opt Swap of Generalized Assignment Problem 원문보기

초록
AI-Helper

표/그림 (5)

표/그림 (5)

AI 본문요약
AI-Helper