[논문]분산 시뮬레이티드 어닐링을 이용한 복합 재료 재단

홍철의

분산 시뮬레이티드 어닐링을 이용한 복합 재료 재단
Composite Stock Cutting using Distributed Simulated Annealing 원문보기

정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용, v.29 no.1/2, 2002년, pp.20 - 29

초록
AI-Helper

복합 재료로 구성된 원판으로부터 여러 가지 패턴을 버려지는 부분이 최소화되게 배치시킨 후 절단하는 문제를 복합 재료 재단 문제라 부른다. 본 논문은 목적 함수의 비용 오류를 감내하는 영역 분할 분산 시뮬레이티드 어닐링 알고리즘을 MPI 환경하에서 복합 재료 재단 문제에 적용한다. 비용 오류 감내기법은 최적해 접근 특성을 유지하기 위하여 스트림 길이를 동적으로 변화하며 상태변환을 비동기적으로 수행한다. 또한 복합 재료 재단 도구 개발을 위한 여러 가지 모양을 가진 패턴의 정보 및 친화도 생성, 목적함수, 상태변환 방법, 어닐링 스케줄 및 이를 위한 효율적인 자료 구조에 대하여 정의한다. 배치될 패턴은 정형이나 convex 다각형으로 제한되어 있지 않고 어떠한 모양도 가능하며 원판은 복합 재료의 성격상 2 또는 4 방향으로 고정되어 있다.

Abstract ▼ AI-Helper

The composite stock cutting problem is to allocate rectangular and/or irregular patterns onto a large composite stock sheet of finite dimensions in such a way that the resulting scrap will be minimized. In this paper, the distributed simulated annealing with the new cost error tolerant spatial decomposition is applied to the composite stock cutting problem in MPI environments. The cost error tolerant scheme relaxes synchronization and chooses small perturbations on states asynchronously in a dynamically changed stream length to keep the convergence property of the sequential annealing. This paper proposes the efficient data structures for representation of patterns and their affinity relations and also shows how to determine move generations, annealing parameters, and a cost function. The spatial decomposition method is addressed in detail. This paper identifies that the final quality is not degraded with almost linear speedup. Composite stock shapes are not constrained to convex polygons or even regular shapes, but the rotations are only allowed to 2 or 4 due to its composite nature.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 복합 재료 재단에 관한 문제 정의 및 이에 대한 분산 어닐링 스케줄에 대하여 기술하였다. 복합 재료 재단 문제에 대한 도구 설계 시 고려하여 할 사항을 체계적으로 접근하였으며, 복함 재료 재단 문제에 특성화된 어닐링 스케줄을 연구함으로써 새로운 응용 분야에 대한 시뮬레이티드 어닐링의 적용 가능성을 타진하띴다- 싶혐 결과 시뮽레이티드 어닐링을 이용한 복합 재료의 패킹 밀도는 어닐링의 온도를 0으로 하여 hill-climb 상태변환을 허용하지 않는 순환 향상 기법에 비하여 평균 10% 정도의 향상온 보였다.
99, Markov 체인 길이는 5,000에서 20, 000 까지 변화 하였다. 클러스터 항의 가중치룔 친화도항의가증치와 같게 하며 춰적의 호!종 결과를 얻도록 하였다. 또한, 프보세서 수 변화에 대한 수행 시간외 향상 怎Medup)을 (그림 11)에 표시하였다.

제안 방법

수 있게 한다. 또한, 시뮬레이터드 어널림의 단섬인입력에 따른 어닐링 변수의 변화에 데한 문제를 해결하여 시뮬레이티드 어널림을 실생활에 사书'하도록 한다.
. 또한, 패턴의 새로운 장소로의 이동 후 이돔된 위치에서 허용된 모든 방향에 대하여 휘전올 수행하여 패턴의 중복이 발생하지 않뉸 방향올 선택함으로써 상태변환 허웅률을 높이도록 하였다.
먼저 16개의 비정형 패턴을 4개의 프로세서에서 Markov 체인 길이는 500으로 고정하여 순차 알고리즘 봐 분산 알고리즘온 비교하였다. 시 (2)의 비묭 오류는 친화 도항 메서만 발생하므로 비용 오류가 어닐링 알고리즘에 미치는 영향을 알아보기 위하여 본 실험에서는 친화 도항에 대한 가중치를 클러스터 항메 내한 가중치모다 높게 정하쪘다, <표 에서 보듯이 분산 말고리즘과순차 알고리즘의 최종 결봐는 비슷하게 나타났다.
. 본 논문에 사용된 비웅 오류 감내 분산 시뮬레이터드어닐링 알고리즘은 각 온도에서 스트림 길이를 동적으로 조절하여 프로세서간 비동기적 수햄으로 발생하는비욤 오류를 감내한다. 스트림 길이에 대한 계수는 5% 로 고정하였다.
본 실험은 16개의 프로세서에 대하여 128개의 비정형 패턴을 사용하였으며 각 항목 당 5번씩 수행하여 평균 올 구하였다.<표 4>에서 알 수 있듯이 스트럼 길이가 증가함에 따라 수행시간은 감소하나 최종 비용은 증가하여 최적해에 도달하지 않는 것으로 나타났다.
세 번째 실험에서는 스트림 길이에 대한 비용 오류의 특성을 알아보기 위하여 스트림 길이를 변화시켜 보았다. 본 실험은 16개의 프로세서에 대하여 128개의 비정형 패턴을 사용하였으며 각 항목 당 5번씩 수행하여 평균 올 구하였다.
이와 같이 위의 방법은 전역 칙적 상태를 찾지 못하거나 현실적으로 다양한 응용 분야에 적용될 수 없기 때문에 본 논문에서는 영역 분할 분산 시뮬레이터드 어닐링 기법을 이용하여 항상 최적 배치는 아니더라도 현싶적으로 받아들일 수 있는 근사 히적 배치를 찾는다.

이론/모형

최적해에 영향을 크게 미치는 임계 영역은 비용 오류 감내 알고리즘올 미용하여 찾아내었다.

성능/효과

<표 4>에서 알 수 있듯이 스트럼 길이가 증가함에 따라 수행시간은 감소하나 최종 비용은 증가하여 최적해에 도달하지 않는 것으로 나타났다. 반면에 본 논문에서 사용한 스트림 길이롤 동적으로 조절하는 비용 오류 감내 기법은 짧은 시간 안에 최적의 결과를 보여 주었다. 즉, 스트림 길이가 고정된 종래의 기법에 비하여 향상된 죄져 값을 유지하면서 6-3배외 전혁갱신올 절약하는 互괴를 보였다, 수행시간 향상(s”edup) 측면에서는 스트림 길이가 고정된 기범이 10.
복합 재료 재단 문제에 대한 도구 설계 시 고려하여 할 사항을 체계적으로 접근하였으며, 복함 재료 재단 문제에 특성화된 어닐링 스케줄을 연구함으로써 새로운 응용 분야에 대한 시뮬레이티드 어닐링의 적용 가능성을 타진하띴다- 싶혐 결과 시뮽레이티드 어닐링을 이용한 복합 재료의 패킹 밀도는 어닐링의 온도를 0으로 하여 hill-climb 상태변환을 허용하지 않는 순환 향상 기법에 비하여 평균 10% 정도의 향상온 보였다.
또한, 사각형 및 원과 같은 정형의 패턴만이 배치되는 것이 아니라 임외의 부정형의 패턴도 함께 哪치되어야 하므로 이블 최적화하는 작업은 더욱 더 힘들어 진다. 복합 재료의 재단믄 항 곰 및 철징-, 지동차 등의 산업에서 중요한 기계적 공정이다, 뽁합 재료로 구성된 원판으로부터 여러가지 패턴음 버려 치는 부분이 최소화되게 배치시킨 후 썰단하눈 복합 재료체단 문제는 방향성을 가진 일종의 2차원 2진 패킹 문제로 NP-Cowplete 군으로 분류된다[3L 따라서, 본 분제를 주어진 시간 안에 해결할 다항식 알고리즘은 존재하지 않으므로 본 논문은 경험척 알고리즘의 하나인 시뮬레이티드 어닐링 기법을 사용하여 항상 전역 최적 값은 아니더라도 사용 가능한 배치를 가지는 근사 최적해를 찾는다. 제2절에서는 재료 재단 문제에 대한 기존의 연구를 정비한다- 제3절에서 복합 재료 재단문제의 자료구조를 정의하고, 제4절에서 시믈레이디드 어닐링의 병렬화에 대하여 설병한다' 마지막으로 제5절에서 실험 결과플 분석한다.
본 논문에서 사용한 비용 오류 감내 기법은 speedup 측면에서의 이익과 함께 고정된 스트림 기법에 비하여 최적 스트림을 잦기 위한 수많은 실험이 펄요하지 않다-즉, 고정된 스트림 기법에서는 최적의 스트렴 개수를 찿기 위해서 많은 수의 전 넌계 싶행이 필요하나, 제안한 비용 오류 감내 기법은 고온과 저온 부분에서는 스트림길이가 크며, 임계 영역 부분메서는 스트림 길이가 줄어서, 온도메 따라 스트럼 길이가 동적으로 변화됨을 뽈수 있다.
상태변한은 많아야 이웃한 2개의 프로세서만이 관여하도뽁 함으로서 프로그램을 간단하게 하고 프로세서의 비동기 수행을 원활하게 한다、서로 협력히는 프로세서률 이뭇한 2개 프로세서 이하부 제한하는 것은 패턴의 이동성을 제약하나 싶험 결과 하나의 표로세서가 4개 이상의 패턴에 대하여 상때변환을 수행한 때 최적해 결과에 영향을 미치지 않는 것으로 나타났다.
안의 임의의 장소로 이동한다. 새로운 상태의 허용률에 1하라서 이동 범위를 동적으로 조절하여 허용률을 40%750%의 범위를 유지하게 하였다. 높은 온도에서는 미동성이 활발하게 보장되는 것이 좋으나, 낮은 온도로 갈수록 너무 광범위한 이동성은 믄 비횸 변화를 尧래하여 새로문 상태가 허용될 확률이 적어지므로 바람직하지 못하디.
분산 알고리즘온 비교하였다. 시 (2)의 비묭 오류는 친화 도항 메서만 발생하므로 비용 오류가 어닐링 알고리즘에 미치는 영향을 알아보기 위하여 본 실험에서는 친화 도항에 대한 가중치를 클러스터 항메 내한 가중치모다 높게 정하쪘다, <표 에서 보듯이 분산 말고리즘과순차 알고리즘의 최종 결봐는 비슷하게 나타났다.
본 실험은 16개의 프로세서에 대하여 128개의 비정형 패턴을 사용하였으며 각 항목 당 5번씩 수행하여 평균 올 구하였다.<표 4>에서 알 수 있듯이 스트럼 길이가 증가함에 따라 수행시간은 감소하나 최종 비용은 증가하여 최적해에 도달하지 않는 것으로 나타났다. 반면에 본 논문에서 사용한 스트림 길이롤 동적으로 조절하는 비용 오류 감내 기법은 짧은 시간 안에 최적의 결과를 보여 주었다.
두 패턴의 위치 교환은 높은 비용의 변화를 초래하므로 온도에 叫라서 이동 대 교환 비율을 적절하게 죠:절하여야 한다. 이동 대 교환 비율은 높은 온도에서 낮은 온도로 갈수록 20:1에서 5:1로 변화 시키는 것이 새로운 상태에 대한 수락율이 잘 보장되었다.
반면에 본 논문에서 사용한 스트림 길이롤 동적으로 조절하는 비용 오류 감내 기법은 짧은 시간 안에 최적의 결과를 보여 주었다. 즉, 스트림 길이가 고정된 종래의 기법에 비하여 향상된 죄져 값을 유지하면서 6-3배외 전혁갱신올 절약하는 互괴를 보였다, 수행시간 향상(s”edup) 측면에서는 스트림 길이가 고정된 기범이 10.6이고 새로운 비용 오휴 감내 기법이 12.9로 좋은 결과를 얻었다.

후속연구

시뮬레이터드 어닐링은 일반적으로 시간이 오래 걸리므로 상태변환 및 비욤 함수를 효율적으로 계산할 수 있는 qu角dtr飾나 pyramid와 같은 자료구조에 대한 연구가 앞으로 필요하다、또한, 비용 함수 계산 시 친화도를 매 상태변환마다 계산한다면 많은 시간이 소요되므로 임의의 두 패턴의 허용된 각 방량에 대하여 친화도를 미리 계산하여 저장하고 있으면 실행 시간을 현저하게 줄일 수 있다.
앞으로, 임계 영역에 대한 자동 탐지 푼제, 온도 감소율이 최적 값에 미치는 영향을 조사하여 어떠한 종류의 재단 문제에 대해서도 자몽적으로 어널링 스케줄을 조정할 수 있게 한다. 또한, 시뮬레이터드 어널림의 단섬인입력에 따른 어닐링 변수의 변화에 데한 문제를 해결하여 시뮬레이티드 어널림을 실생활에 사书'하도록 한다.

참고문헌 (15)

Kirkpatrick, S., Gellatt Jr. C. D., and Vecci, M. P., Optimization by simulated annealing, Science, Vol. 220, pp. 975-986, 1983

상세보기
Lee, S and Lee, K, Synchronous and asynchronous parallel simulated annealing, with multiple Markov chains, IEEE Trans. on Parallel and Distributed Systems, Vol.7, No. 10, pp. 993-1008, 1996

상세보기
Fowler, R.J., Paterson, M.S., and Tanimoto, S.L., Optimal Packing and covering in the plane are NP-complete. Information Processing Letters, Vol.12, No.3, pp. 133-137, 1981

상세보기
Balas, E., Ceria, S., Cornuejols, G., and Natraj, N., Gomery cut revisited, Operations Research Letters 19, pp. 1-9, 1996

상세보기
Degraeve, Z., and Vandebroek, M., A mixed integer programming model for solving a layout problem in the fashion industry, Management Science 44, pp. 301-310, 1998

상세보기
Stoyan, Y.G., Novozhilova, M. V., and Kartashov, Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem, European Journal of Operational Research 92, pp. 193-210, 1996

상세보기
Beasley, J. E. An exact two-dimensional nonguillotine cutting tree search procedure, Operations Research, Vol.33, No. 1, pp. 49-64, 1985

상세보기
Morabito, R., and Arenales, M. N., Staged and constrained two-dimensional guillotine cutting problcms: An AND/OR-graph approach, European Journal of Operational Research 94, pp. 548-560. 1996

상세보기
Baker, B.S., Coffman, E.G., and Rivest, R.L., Orthogonal packings in two dimensions, SIAM Journal on Computing, Vol.9, No.4, pp. 846-855, 1980

상세보기
Bean, J. C., A multiple-choice genetic algorithm for a nonlinear cutting stock problem, Computing in Science and Engineering, Vol.2, No.2, pp. 80-83, 2000

상세보기
Dagli, C.H., Poshyanonda, P., New approaches to nesting rectangular patterns, Journal of Intelligent Manufacturing, Vol.8, pp. 177-190, 1997
Petridis V., Kazarlis,S., and Bakirtzis, A., Varying fitness functions in genetic algorithm constrained optimization The cutting stock and unit commitment problems, IEEE Trans. on Systems, Man, and Cybernetics-Part B: Cybernetics, Vol.28, No.5, pp. 629-640, 1998

상세보기
Jakobs, S., On genetic algorithms for the apcking polygons, European Journal of Operational Research 88, pp. 165-181, 1996

상세보기
Lutfiyya,II. B. McMillin, P. Poshyanonda, and C. Dagli, Composite stock cutting through simulated anncaling, Mathl. Comput. Modeling, Vol.16, No.1, pp. 57-74, 1992

상세보기
홍철의, 김영준, 시뮬레이티드 어닐링에서의 비용오류 측정 및 분석, 한국정보처리학회 논문지, 제7권 제4호, pp. 1141-1149, 2000

원문보기 상세보기

저자의 다른 논문 :

표제어: 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

연합인증