[논문]인타샤(Intarsia) 스웨터 직조를 위한 실 연결 방법의 유전자 알고리즘 해법 연구

허상무; 김우제

doi:10.7737/kmsr.2015.32.1.035

인타샤(Intarsia) 스웨터 직조를 위한 실 연결 방법의 유전자 알고리즘 해법 연구
A Study on the Genetic Algorithm of Thread's Connection Method for Intarsia Sweater Weaving 원문보기

經營科學 = Korean management science review, v.32 no.1, 2015년, pp.35 - 47

허상무 (서울과학기술대학교 IT정책전문대학원) , 김우제 (서울과학기술대학교 글로벌융합산업공학과)

Abstract ▼ AI-Helper

The purpose of this paper is to find an optimal weaving connection method of sweater threads while weaving intarsia sweater by the genetic algorithm. The objective function was devised to minimize labor cost and lessen the amount of thread usage. In order to create the parental population group in the genetic algorithm, we developed five thread connection methods. Besides, elite chromosome screening methods for the offspring group was selected both to the whole chromosome thread elite and to a color-coded elite thread chromosome. Commonly used diamond pattern in Intarsia sweater manufacturing was applied to the experiments. The experimental results showed that thread system saved the labor and material costs than woven method under the existing software. When weaving Intarsia sweater in the field, we can apply the developed genetic algorithm to improve productivity of weaving connection method.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문의 연구문제는 스웨터를 직조할 때, (1)과 같이 스웨터에 사용되는 실 사용량을 최소화하고, (2)의 스웨터 뒤판에 부유하는 실에 대해 수작업 매듭 공수를 최소화할 수 있는 휴리스틱한 실 연결 방법을 찾는 것이다.
본 연구는 스웨터 직조시 실 연결 경로에 대하여 휴리스틱한 연결 방식을 찾는 문제로서 최적의 경로를 찾는 TSP 모델과 유사성이 있다. 선행 TSP 연구로 Goldberg and Lingle[10]은 유전자 알고리즘을 이용하여 TSP 문제를 최초로 접목시킨 연구자이다.
하지만 다양한 스웨터 무늬가 존재하고, 실의 연결 경로가 다수 존재하고, 실 연결시 물리적인 제약조건으로 인해 인건비와 재료비가 최소화된 스웨터를 생산하는데는 한계가 있었다. 이에, 본 연구에서는 물리적인 실 연결 제약조건을 고려하여 스웨터를 직조하며, 스웨터 직조 인건비를 최소할 수 있도록 스웨터 뒤판의 실 매듭 공수를 최소화시키고 더 이상 실 매듭 공수가 최소화되지 않으면 실 사용량 재료비를 최소화하는 휴리스틱한 실 연결 방법을 찾고자 한다.

가설 설정

근래에는 컴퓨터로 디자인하고 자동 인타샤로 직조하고 있다. 프로그램으로 직조된 스웨터가 사람이 직조한 스웨터보다 인건비나 실 재료비가 적으면 좋을 것이다. 하지만 다양한 스웨터 무늬가 존재하고, 실의 연결 경로가 다수 존재하고, 실 연결시 물리적인 제약조건으로 인해 인건비와 재료비가 최소화된 스웨터를 생산하는데는 한계가 있었다.

제안 방법

1) 초기 모집단은 의 휴리스틱한 다섯가지 실 y축 연결 방법을 이용하여 모집단을 생성한다.
3가지 방법을 추가했지만 추가된 연결방법이 최적해에 수렴하는 지 알 수 없으므로 총 4가지 연결방식을 혼합한 방식을 추가하여 와 같이 총 5가지 연결방법을 고안하였다.
각 방식의 수렴속도를 고려하여 과 같이 혼합방식에 대한 혼합비율을 설정하였다.
무작위법의 특성은 y축 아래로 연결할 때 거리에 상관없이 무작위로 연결되고, 실끼리 서로 교차시켜도 되는 연결 방식이다. 그래서 무작위법의 두 가지 특성을 조작하여 몇가지 연결 방법을 추가적으로 고안하였다. 첫 번째는 실이 y축으로 연결될 때 거리가 가까운 직조영역을 우선적으로 연결시키는 방법이고, 두 번째는 다른 실의 연결 경로를 파악하여 실끼리 서로 교차되지 않도록 연결하는 방법이다.
연구방법으로는 유전자 알고리즘의 적합도 목적함수를 이용하여 휴리스틱한 실 연결 방법을 찾고자 한다. 또한 유전자 알고리즘의 효과를 검증하기 위해 다이어몬드 무늬 스웨터를 대상으로 최적의 스웨터에 수렴한 결과와 기존 방식으로 직조된 스웨터의 결과를 비교하여 인건비와 재료비가 얼마나 개선되었는지를 점검하도록 한다.
본 연구는 최적의 스웨터 탐색을 위한 목적함수로서 TSP 모델을 적용하였고, 최적의 스웨터를 탐색하기 위하여 총 다섯 가지 실 y축 연결방법을 고안하였다. 또한, 유전자 알고리즘의 엘리트 보전전략 중 추가적으로 색상별 엘리트 염색체를 보존하는 전략을 적용하여 최적해에 고속으로 수렴하는 것을 규명하였다.
엘리트보존 전략은 생성된 염색체 적합도를 평가하여 우수한 부모 염색체를 자식에게 복제하는 전략으로서 최적 근사 해에 신속하게 수렴시키기 위한 중요한 전략이라고 할 수 있다. 본 연구에서는 두 가지 엘리트 보존 전략을 적용하였다. 첫 번째는 모든 색상에 대한 염색체를 대상으로 가장 우수한 염색체 10%를 보존시켰고 두 번째는 색상 별로 가장 우수한 1등과 2등 염색체를 추출하여 <표 7>과 같이 조합하여 5%를 보존시켰다.
교배에는 일점 교배, 다점교배 및 일양교배[5] 등이 있다. 본 연구에서는 일점교배와 일점교배를 여러 번하는 사이클 교배를 예비 실험한 결과 사이클 교배의 수렴속도가 월등하였으므로 사이클 교배를 적용하였다.
분리된 직조 영역에 대하여 x축 직조 순서를 살펴보았으므로 본 연구의 탐색 대상인 실을 y축으로 연결하는 방법을 살펴보도록 한다. <그림 3>(2)와 같이 분리된 직조 영역 중 동일 색상끼리 y축으로 연결할 수 있는 논리적인 연결 경로는 <그림 4>와 같다.
본 실험을 하기 전에 <표 5>의 실 혼합연결비율을 결정해야 한다. 실 혼합방식은 무작위 법과 휴리스틱 3번 까지를 혼합하는 방식이므로 예비실험을 통해 혼합 비율을 설계하였다.
연구방법으로는 유전자 알고리즘의 적합도 목적함수를 이용하여 휴리스틱한 실 연결 방법을 찾고자 한다. 또한 유전자 알고리즘의 효과를 검증하기 위해 다이어몬드 무늬 스웨터를 대상으로 최적의 스웨터에 수렴한 결과와 기존 방식으로 직조된 스웨터의 결과를 비교하여 인건비와 재료비가 얼마나 개선되었는지를 점검하도록 한다.
이와 같이 설계한 휴리스틱한 4가지 연결방식이 최적해에 수렴한다는 보장이 없으므로 각 방식을 혼합한 방식을 고안하였다. 각 방식들은 최적 근사해에 수렴하는 속도가 다를 것이므로 4가지 방식을 25%씩 균등하게 혼합하는 것은 부적합한 비율이라 판단하였고, 각 방식별로 최적해에 수렴하는 속도를 이용하여 혼합 비율을 정하는 것이 타당한 방법이라고 판단하였다.
인타샤의 직조원리를 살펴본 결과 의 다수의 y축 연결 경로 중 최적의 경로를 찾는 문제가 TSP(Traveling Salesman Problem) 모델과 유사성이 있으므로 의 목적함수를 이용하여 TSP 모델로 모형화할 수 있을 것으로 판단하였다.
첫 번째는 모든 색상에 대한 염색체를 대상으로 가장 우수한 염색체 10%를 보존시켰고 두 번째는 색상 별로 가장 우수한 1등과 2등 염색체를 추출하여 과 같이 조합하여 5%를 보존시켰다.

대상 데이터

본 연구에서 구현한 프로그래밍언어는 c언어이며, 실험에 사용된 컴퓨터 사양은 Intel ® 1.86GHz,1GB 노트북에서 실험하였다.
실험을 위한 모집단은 100개로 설정하였고 모집단 재편성 비율은 과 같이 설계하였다.
예비실험은 1,000세대까지 실험하였고 실험결과와 같이 무작위법과 휴리스틱 3번까지 모두 최적해에 수렴하지 못했다.

이론/모형

첫 번째, 실 매듭 최소화는 수리식으로 모델링하기 어렵고 선형계획법과 같은 수리모델로 풀 수 없다. 두 번째, 실이 연결될 수 있는 모든 경우를 시도하여 최적해를 찾을 수는 있지만 속도가 너무 느리기 때문에 고속으로 최적 근사해를 찾기 위해 유전자 알고리즘을 적용하였다.
실이 연결될 때 서로 교차하는 지를 점검하는 방법은 이재규[5] 선분교차 방법을 이용하였다. <그림14>와 같이 (1)과 (2)가 만족되면 선분이 교차하는 것으로 판단한다.
86GHz,1GB 노트북에서 실험하였다. 실험 그림은 인타샤스웨터에 많이 사용하는 다이어몬드 무늬를 적용하여 실험하였다.

성능/효과

최적 근사해에 수렴하지 않았으면 정렬된 모집단을 이용하여 후손 모집단을 생성한다.3) 후손 모집단을 생성하는 방법은 첫 번째는 부모 모집단에서 전체 엘리트와 색상별 엘리트 염색체를 유전시키고 두 번째는 부모 염색체를 교배하여 유전시키고 세 번째는 부모염색체를 돌연변이화 하여 유전시키고 마지막으로 염색체를 재생성하여 후손 모집단을 생성한다.
이와 같이 설계한 휴리스틱한 4가지 연결방식이 최적해에 수렴한다는 보장이 없으므로 각 방식을 혼합한 방식을 고안하였다. 각 방식들은 최적 근사해에 수렴하는 속도가 다를 것이므로 4가지 방식을 25%씩 균등하게 혼합하는 것은 부적합한 비율이라 판단하였고, 각 방식별로 최적해에 수렴하는 속도를 이용하여 혼합 비율을 정하는 것이 타당한 방법이라고 판단하였다. 혼합 비율은 예비 실험을 통하여 설정하였다.
본 연구는 최적의 스웨터 탐색을 위한 목적함수로서 TSP 모델을 적용하였고, 최적의 스웨터를 탐색하기 위하여 총 다섯 가지 실 y축 연결방법을 고안하였다. 또한, 유전자 알고리즘의 엘리트 보전전략 중 추가적으로 색상별 엘리트 염색체를 보존하는 전략을 적용하여 최적해에 고속으로 수렴하는 것을 규명하였다. 본 연구에서 고안한 방식을 현장에서 적용한다면 최적해에 고속으로 수렴시켜 인건비와 재료비를 절감할 수 있을 것이다.
본 연구로 최적화된 과 기존 소프트웨어로 직조한 를 비교한 결과, 절감 효과는과 같이 수작업 공수는 노랑과 빨강이 절감되었고, 총 인건비는 11%가 절감되었다.
설계된 방식으로 실험한 결과 과 같이 수작업 최소화는 3세대 만에 수렴하였고 실거리 최소화는 74세대 만에 수렴하였다.
본 연구로 최적화된 <그림 21>과 기존 소프트웨어로 직조한 <그림 22>를 비교한 결과, 절감 효과는<표 11>과 같이 수작업 공수는 노랑과 빨강이 절감되었고, 총 인건비는 11%가 절감되었다. 실 사용량은 모든 색상에서 절감되었고, 총 실 재료비는 7%가 절감된 것으로 나타났다.

후속연구

또한, 유전자 알고리즘의 엘리트 보전전략 중 추가적으로 색상별 엘리트 염색체를 보존하는 전략을 적용하여 최적해에 고속으로 수렴하는 것을 규명하였다. 본 연구에서 고안한 방식을 현장에서 적용한다면 최적해에 고속으로 수렴시켜 인건비와 재료비를 절감할 수 있을 것이다.
본 연구는 비용 최소화 측면의 연구로 볼 수 있다. 향후 연구로는 스웨터 품질 측면으로, 실 연결 시 실의 장력을 이용하여 스웨터의 품질을 평가하는 실 연결방법을 탐색하는 연구와 생산성 향상 측면인실판의 움직임을 최소화하여 스웨터 직조 속도를 개선하는 연구 과제가 남겨졌다.

질의응답

핵심어	질문	논문에서 추출한 답변
	돌연변이 연산은 어떻게 부분 최적해로 수렴하는 위험을 완화하는가?	하지만 전체 최적해에 수렴하지 못하고 부분 최적해(local optimal solution)로 수렴할 위험이 존재한다. 돌연변이 연산은 부모 염색체 값을 임의의 다른 값으로 교체하여 부분 최적해로 수렴하는 위험을 완화시킨다.
	유전자 알고리즘이란 무엇인가?	유전자 알고리즘은 환경에 적응한 개체가 더 많은 후손을 남기는 자연 선택과 진화를 모방하여 컴퓨터로 모의 실행하는 최적 근사해 알고리즘이다. 유전자 알고리즘 흐름[9]은 <그림 7>와 같이 초기해 집단을 생성한 이후 엘리트 염색체를 자식에게 유전시켜 최적 근사해를 탐색하는 알고리즘이다.
	인타샤 스웨터 직조 최적화를 위해 유전 알고리즘을 적용한 이유 두 가지는 무엇인가?	본 연구에서 유전자 알고리즘을 적용해야 하는 이유는 크게 두 가지로 정리할 수 있다. 첫 번째, 실 매듭 최소화는 수리식으로 모델링하기 어렵고 선형계획법과 같은 수리모델로 풀 수 없다. 두 번째, 실이 연결될 수 있는 모든 경우를 시도하여 최적해를 찾을 수는 있지만 속도가 너무 느리기 때문에 고속으로 최적 근사해를 찾기 위해 유전자 알고리즘을 적용하였다.

참고문헌 (11)

김광백, 송두헌, "유전자 알고리즘을 이용한 경로탐색", 한국해양정보통신학회논문지, 제15권, 제6호(2011), pp.1251-1255.

원문보기 상세보기
문치웅, 김재균, "공정순서에 기초한 생산셀 설계를 위한 유전 알고리즘 접근", 한국경영과학회지, 제23권, 제3호(1998), pp.123-133.

원문보기 상세보기
양미나, 이건호, "유전자 알고리즘을 이용한 매트릭스 조직의 소프트웨어 개발 스케줄링", 한국경영과학회지, 제23권, 제2호(2006), pp.187-198.
이경미, 이건명, "방문순서 제약이 있는 순회 세일즈맨 문제를 위한 유전자 알고리즘", 정보과학회논문지, 제25권(1998), pp.362-368.
이재규, C로 배우는 알고리즘 2, 세화, 2013.
장인성, 박승헌, "대중교통망에서의 최단경로 탐색을 위한 유전자 알고리즘", 한국경영과학회지, 제18권, 제1호(2001), pp.101-118.
전건욱, 김기태, "교통상황과 확률적 수요를 고려한 차량경로문제의 Hybrid 유전자 알고리즘", 대한교통학회지, 제28권, 제5호(2010), pp.107-116.

원문보기 상세보기
정성훈, "유전자 알고리즘의 성능향상을 위한 선택적 돌연변이", 정보처리학회논문지 제17-B권, 제2호(2010), pp.149-156.
정환묵, 지능정보시스템 원론, 21세기사, 1999.
Goldberg, D. and R.A. Lingle, "loci and the traveling salesman problem," Proc. of the 1st int conf. on Genetic Algorithm, (1985), pp.154-159.
Sallabi, O.M., "An Improved Genetic Algorithms to Solve the Traveling Salesman Problem," World Academy of Science, Enginering and Technology, Vol.52, No.3(2012), pp. 471-474.

저자의 다른 논문 :

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

연합인증