[논문]유전자 알고리즘을 이용한 부재 절단 경로 최적화

박주용; 서정진

Abstract ▼ AI-Helper

Nesting and cutting path optimization have a great effect on the improvement of productivity in many industries such as shipbuilding, automotive, clothing, and so on. However, few researches have been carried out for the optimization of a cutting path algorithm. This study proposed a new method for ...

Nesting and cutting path optimization have a great effect on the improvement of productivity in many industries such as shipbuilding, automotive, clothing, and so on. However, few researches have been carried out for the optimization of a cutting path algorithm. This study proposed a new method for cutting optimization using gravity center of cutting pieces and a genetic algorithm. The proposed method was tested for a sample plate including many different shapes of cutting pieces and compared to 2 other conventional methods. The test results showed that the new method had the shortest cutting path and the best effectiveness among the 3 methods.

주제어

AI 본문요약
AI-Helper

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

문제 정의

1에서 좌표계의 원점에 해당된다. 따라서 본 연구에서 제안한 최적화의 목적함수는 도심간의 이동거리의 총합인 TD가 되며 이 TD가 최소화되는 경로가 최적의 해가 된다. 이는 전형적인 TSP(The traveling salesman problem) 의 형태로 GA가 가장 효과적인 최적화 방법임이 널리 알려져 있다(Applegate et al.
본 연구에서는 절단부재도형의 도심을 이용한 GA 모델을 적용하여 절단경로거리가 최소가 되는 절단순서를 구하는 방법을 제시하였다. 본 연구에서 제시한 방법이 효율적임을 검증하기 위해 다양한 도형으로 절단되는 판재에 대해 현장에서 널리 적용되고 있는 토치 시작점에서 가까운 순서대로 배치된 부재순서로 정해지는 단순배치법과 기존의 연구에서 제안된 부재도형의 볼록꼭지점을 활용한 GA 적용법을 비교하였다.
본 연구의 목표인 절단 경로의 최적화 문제는 ”하나의 판재 상에서 폐곡선으로 이루어진 N개의 부재가 배치되어 있을 때, 토치가 하나의 출발점에서 시작하여 이들을 모두 절단하기 위한 이동거리가 최소가 되는 경로를 구하는 것”으로 정의 된다.
하지만 아직은 절단 경로의 최적화 문제에 대한 실용적 해법이 마련되지 않아 현재는 작업자의 경험에 의존하거나 토치 출발점에서부터 인접한 부재에 대해 순차적으로 절단 경로를 결정하고 있다. 이에 본 연구에서는 네스팅된 부재의 도심과 유전자 알고리즘을 이용한 절단 경로 최적화 방법을 고안하여 이를 현장에서 사용하는 순차적인 경로 설정 방법과 다른 연구자가 제안한 알고리즘과 비교하여 본 연구에서 제안한 방법의 타당성과 효용성을 제시하였다.

제안 방법

본 연구에서는 절단부재도형의 도심을 이용한 GA 모델을 적용하여 절단경로거리가 최소가 되는 절단순서를 구하는 방법을 제시하였다. 본 연구에서 제시한 방법이 효율적임을 검증하기 위해 다양한 도형으로 절단되는 판재에 대해 현장에서 널리 적용되고 있는 토치 시작점에서 가까운 순서대로 배치된 부재순서로 정해지는 단순배치법과 기존의 연구에서 제안된 부재도형의 볼록꼭지점을 활용한 GA 적용법을 비교하였다. 그 결과 단순배치법에 대해서는 12.
본 연구에서 제안된 절단경로 최적화 방법은 절단부재도형의 도심을 대상으로 각 도심사이의 이동거리를 최소화하는 도심의 순서를 GA를 이용하여 결정한다는 점에서 다른 절단경로 결정 방법과 차이가 있다. Fig.
본 연구에서는 절단경로를 정하는 방법으로 통상적으로 현장 에서 사용하는 방법과 최근 타 연구자가 제안한 방법, 그리고 본 연구에서 제안하는 방법 등 3가지로 나누어 살펴보았다. 방법 1은 일반적으로 현장에서 널리 쓰이는 방법으로 Fig.
본 연구에서는 절단경로의 최적화 방법을 각 도형의 도심을 하나의 노드(Node)로 보고 모든 노드를 거쳐 돌아오는 경로 중 최단경로를 찾는 문제로 변환하고 다음과 같은 GA 모델을 적용하여 이 경로를 찾는 방법을 취하였다. 즉, 각 노드를 하나의 알파벳으로 표현하고 Fig.
본 연구에서는 절단경로의 최적화 방법을 각 도형의 도심을 하나의 노드(Node)로 보고 모든 노드를 거쳐 돌아오는 경로 중 최단경로를 찾는 문제로 변환하고 다음과 같은 GA 모델을 적용하여 이 경로를 찾는 방법을 취하였다. 즉, 각 노드를 하나의 알파벳으로 표현하고 Fig. 5와 같이 알파벳의 순서를 절단경로로 간주하여 그 때의 경로의 길이가 최소가 되도록 GA를 적용하였다. GA는 일반적으로 Fig.

대상 데이터

본 연구의 목표인 절단 경로의 최적화 문제는 ”하나의 판재 상에서 폐곡선으로 이루어진 N개의 부재가 배치되어 있을 때, 토치가 하나의 출발점에서 시작하여 이들을 모두 절단하기 위한 이동거리가 최소가 되는 경로를 구하는 것”으로 정의 된다. 본 연구에서 최적화된 절단 경로를 구하는 대상은 Fig. 1에 나타난 바와 같이 여러 가지 도형의 형상을 가진 총 17개의 절단 부재를 포함하는 가로 9,800mm, 세로 3,100mm인 철판이다. Fig.

성능/효과

3.2절에 기술된 방법으로 유전자 모형을 만들어 선별 → 교차 → 돌연변이를 통해서 목적함수값의 최소화에 대한 적응도 평가를 수행해본 결과 TD의 값은 세대가 거듭됨에 따라 크게 줄어들어 540세대에 이르러 TD의 감소치가 거의 0에 가까운 최소값으로 수렴하였다.
본 연구에서 제시한 방법이 효율적임을 검증하기 위해 다양한 도형으로 절단되는 판재에 대해 현장에서 널리 적용되고 있는 토치 시작점에서 가까운 순서대로 배치된 부재순서로 정해지는 단순배치법과 기존의 연구에서 제안된 부재도형의 볼록꼭지점을 활용한 GA 적용법을 비교하였다. 그 결과 단순배치법에 대해서는 12.7%, 볼록꼭지점을 활용한 GA 적용법에 비해서는 9.4% 가 감소된 바 본 연구에서 제안한 부재도심을 활용한 GA 적용법이 매우 효과적임을 알 수 있었다. 절단용 CAD/CAM시스템에 본 연구에서 제시한 절단경로 최적화 루틴을 포함시킨다면 절단가공시간의 단축을 통해 생산성 향상 및 비용절감에 큰 도움이 될 것으로 사료된다.
2절에 기술된 방법으로 유전자 모형을 만들어 선별 → 교차 → 돌연변이를 통해서 목적함수값의 최소화에 대한 적응도 평가를 수행해본 결과 TD의 값은 세대가 거듭됨에 따라 크게 줄어들어 540세대에 이르러 TD의 감소치가 거의 0에 가까운 최소값으로 수렴하였다. 그리고 실제의 TD 값은 GA를 적용하기 전 42,680mm에서 적용 후 23,399mm로 56.2% 수준으로 감소되었다.
이러한 결과는 방법 1의 경우는 도형의 통과순서를 단순히 왼쪽에 위치한 순서대로 하는 것이 일반적으로 최단경로가 아니기 때문이며 방법 2의 경우는 GA를 이용하여 최적의 피어싱점의 순서 및 이에 따른 도형의 순서를 구하였지만 피어싱점이 반드시 꼭지점이 되어야 하는 조건으로 인해 최단경로를 구하는 데에 한계가 있었던 때문으로 사료된다. 따라서 본 연구를 통해 제안한 방법은 기존의 다른 2가지 방법들에 비해서 최단 절단 경로를 각각 12.7%, 9.4%를 감소시킨 효과를 보인 것으로 이 절단경로 최적화 기법이 매우 효과적임을 알 수 있었다.
방법 2와 방법 3은 최적화 도구로 GA를 이용한 점은 동일하나 방법 2의 경우는 각 도형의 피어싱점과 도형의 절단순서를 모두 GA를 통해서 결정된다는 점과 방법 3은 도형의 도심을 대상으로 GA를 이용해서 도형의 절단순서를 결정한 후 피어싱점은 다음 절단도형의 둘레상의 점 중 가장 가까운 점으로 결정된다는 점에서 차이가 있다. 본 연구 에서는 Fig. 1과 같이 절단부재도형이 배치된 판재를 대상으로 전술한 3가지 방법을 적용하여 총 절단경로의 거리를 비교하여본 연구에서 제안한 방법이 최적화된 방법임을 입증하였다.
이 수치는 모든 부재를 절단하는 절단토치경로의 총거리에서 각 절단부재도형의 둘레를 제외한 거리이다. 즉, 방법 3은 단순히 왼쪽 부재순으로 경로를 결정한 방법 1에 비해서 3,088mm가 감소하였으며 동일하게 GA를 이용한 방법 2에 비해서도 2,200mm가 감소한 결과를 보여주고 있다.

후속연구

4% 가 감소된 바 본 연구에서 제안한 부재도심을 활용한 GA 적용법이 매우 효과적임을 알 수 있었다. 절단용 CAD/CAM시스템에 본 연구에서 제시한 절단경로 최적화 루틴을 포함시킨다면 절단가공시간의 단축을 통해 생산성 향상 및 비용절감에 큰 도움이 될 것으로 사료된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	절단 경로의 최적화 문제의 정의는 무엇인가?	본 연구의 목표인 절단 경로의 최적화 문제는 ”하나의 판재 상에서 폐곡선으로 이루어진 N개의 부재가 배치되어 있을 때, 토치가 하나의 출발점에서 시작하여 이들을 모두 절단하기 위한 이동거리가 최소가 되는 경로를 구하는 것”으로 정의 된다. 본 연구에서 최적화된 절단 경로를 구하는 대상은 Fig.
	모든 절단도형의 볼록 꼭지점 중 임의의 한 점을 피어싱점으로 하고 GA를 통해서 절단경로가 최소가 되는 각 도형의 피어싱점과 그 피어싱점들의 통과순서를 결정하는 방법은 GA의 최적화 기능을 활용하고 있으나 어떤 한계를 가지는가?	2에서 보는 바와 같이 모든 절단도형의 볼록 꼭지점 중 임의의 한 점을 피어싱점으로 하고 GA를 통해서 절단경로가 최소가 되는 각 도형의 피어싱점과 그 피어싱점들의 통과순서를 결정하는 방법이다(한윤근과 장창두, 2000). 이 방법은 GA의 최적화 기능을 활용하고 있으나 피어싱점이 반드시 절단부재도형의 꼭지점 중에서 정해져야 하는 한계가 있다. 이 경우 Fig.
	본 연구에서 절단경로를 정하는 방법으로 살펴본 3가지 방법은 무엇인가?	본 연구에서는 절단경로를 정하는 방법으로 통상적으로 현장 에서 사용하는 방법과 최근 타 연구자가 제안한 방법, 그리고 본 연구에서 제안하는 방법 등 3가지로 나누 어 살펴보았다. 방법 1은 일반적으로 현장에서 널리 쓰이는 방법으로 Fig.

참고문헌 (14)

방기범 (1989). 판재 소모를 최소화하는 이차원형상의 최적 배치, 서울대학교 기계설계학과 대학원 박사학위논문, pp 3-15
이철수, 강현구, 박광렬 (1997). "CAD 데이터를 이용한 플랫바의 네스팅 및 가공데이터 생성의 자동화", 선박설계연구발표회논문집, pp 4-1~4-10
한윤근 (2000). 임의 형상 부재의 자동 네스팅 시스템에 대한 연구, 서울대학교 조선해양공학과 박사학위논문, pp 3-9
한국찬, 나석주 (1996). "레이져 절단공정에서의 토치 경로 생성에 관한 연구", 대한기계학회 논문집, Vol 20, No 6, pp 1827-1835
한윤근, 장창두 (2000). "개선된 유전자 알고리즘을 이용한 부재절단경로 최적화에 관한 연구", 대한조선학회논문집, Vol 20, No 3, pp 90-98
박주용 (2004). "선박 곡블록의 경사 필렛 이음부의 적정 용접조건 (I)", 한국해양공학회지, Vol 18, No 6, pp 79-83
강현진 (2005). 유전자 알고리즘을 이용한 조선 소조립 로봇용접 공정 최적화 및 3D 시뮬레이션을 통한 검증, 한국해양대학교 조선해양시스템공학과 대학원 석사학위논문, pp 17-29
박주용, 서정진, 강현진 (2009). "유전자 알고리즘을 이용한 조선 소조립 로봇용접공정의 최적화", 대한용접접합학회지, Vol 27, No 2, pp 57-62

원문보기 상세보기
기타노 히로아키, 조성배 (1996). 유전자 알고리즘, 대청정보시스템, pp 87-101
박성수, 박해영 (2001). C++로 구현한 유전자 알고리즘, 한올출판사, pp 201-223
Adachi, N. (1987). Framework of Mutation Model for Evolution in the Ecological Model World 'Game World', ILAS-SIS Research Report, No 74
Applegate, D.L., Bixby, R.E., Chv $\acute{a}$ tal, V. and Cook, W.J. (2006). The Traveling Salesman Problem: A Computational Study, Princeton University Press. ISBN 978-0-691-12993-8
Gutin, G., Yeo, A. and Zverovich, A. (2002). "Traveling Salesman Should Not be Greedy: Domination Analysis of Greedy-type Heuristics for the TSP", Discrete Applied Mathematics 117
Mitchell, J. (1999). "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing, 28

상세보기

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

연합인증

유전자 알고리즘을 이용한 부재 절단 경로 최적화
A Study on Cutting Path Optimization Using Genetic Algorithm 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

연합인증

유전자 알고리즘을 이용한 부재 절단 경로 최적화 A Study on Cutting Path Optimization Using Genetic Algorithm 원문보기

Abstract ▼ AI-Helper

주제어

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

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

박주용 (31) 서정진 (1)

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

유전자 알고리즘을 이용한 부재 절단 경로 최적화
A Study on Cutting Path Optimization Using Genetic Algorithm 원문보기

AI 본문요약
AI-Helper