[논문]유전 알고리즘의 기초와 응용

김영석; 샤오샤오

유전 알고리즘의 기초와 응용
Basic of Genetic Algorithm and Its Applications 원문보기

소성가공 = Transactions of materials processing : Journal of the Korean society for technology of plastics, v.30 no.5, 2021년, pp.255 - 266

김영석 (경북대학교 기계공학부) , 샤오샤오 (경북대학교 기계공학과)

초록이 없습니다.

표/그림 (19)

그림 Fig. 1 The framework of the GA (population, chromosomes and genes)
그림 Fig. 2 Selection, crossover, mutation in GA
그림 Fig. 3 Flowchart of GA
그림 Fig. 4 Simple TSP model
그림 Fig. 5 Total distance of each route
표 Table 1 Distance between each city [km]
그림 Fig. 6 ISF of VWACF model
그림 Fig. 7 Calculation of each parent
표 Table 2 Best combination of parameters and max angle
그림 Fig. 8 Bitstring of the manufacturing process
그림 Fig. 9 Case of [001122221100]
표 Table 3 Flow time required based on job
표 Table 4 Flow time required based on machine
표 Table 5 Gantt chart of the work schedule for the bitstring [000011112222]
표 Table 6 Gantt chart of the machine schedule for the bitstring [000011112222]
표 Table 7 Gantt chart of the work schedule for the bitstring [001122221100]
표 Table 8 Gantt chart of the machine schedule for the bitstring [001122221100]
그림 Fig. 10 (a) Machine schedule and (b) job schedule of bitstring [000011112222] by using GA
그림 Fig. 11 (a) Machine schedule and (b) job schedule of bitstring [001122221100] by using GA

AI 본문요약
AI-Helper

문제 정의

본 해설에서는 유전 알고리즘에 대한 설명과 STP, 소성가공문제 및 작업스케줄 설계에의 적용을 통해 유전 알고리즘 프로그램의 응용에 대한 이해를 높이도록 하였다. 본 해설을 통해 독자들은 유전 알고리즘에 대한 최소한의 지식을 갖추어 소성가공분야의 산업현장과 연구에 도움이 되길 바란다.

가설 설정

대상으로 한 소규모 공장에서 4 개의 기계를 (Machine) 이용하여 3 개의 작업(Job)을 수행하여 3 종류의 제품을 생산하고 있는 것을 가정하자. 이 3 작업 x 4기계 (3-Jobs x 4-Machines) 문제에서 각 작업에 소요되는 기계 순번과 작업에 요구되는 소요 시간을 (𝐽 , 𝑀 )의 쌍으로 다음 Table 3 과 Table 4 에나타내었다.
4와 같이 5개의 도시를 방문하는 방문판매원 문제에 대해서 설명한다. 문제를 간단히 하기 위하여 방문 판매원은 A 도시에서 출발하고 A 도시로 돌아온다고 가정한다. 각각의 도시간의 거리를 Table 1에 나타내었다.
첫 번째, 환경에 적합한 개체가 살아남는다.

제안 방법

본문 중에 기술한 방문판매원 문제, 점진판재 성형 문제, 작업 스케쥴 문제에 대한 유전 알고리즘프로그램을 한국소성가공학회의 자료실에 GA-1, GA-2, GA-3으로 게재하였다. 참고 바랍니다.

성능/효과

[001111002222] 유전자 비트열은 [000011112222] 유전자 비트열에 대한 돌연변이 유전자 조작을 통해 생성할 수 있다. 따라서 작업 스케줄 문제 유전 알고리즘을 적용하여 유전자 조작을 통해서 다양한 유전자 비트열을 생성하고 각각의 경우에 대한 총 소요시간을 평가하여 최적해를 구하는 것이 가능하다. 단, 유전자 조작을 수행할 때에 같은 시간대에 동일한 작업이 수행되어서는 안되고 또한 생성한 유전자 비트열은 반드시 각 작업이 4회씩 행해져야 한다는 것에 주의하여야 한다.

후속연구

본 해설에서는 유전 알고리즘에 대한 설명과 STP, 소성가공문제 및 작업스케줄 설계에의 적용을 통해 유전 알고리즘 프로그램의 응용에 대한 이해를 높이도록 하였다. 본 해설을 통해 독자들은 유전 알고리즘에 대한 최소한의 지식을 갖추어 소성가공분야의 산업현장과 연구에 도움이 되길 바란다. 본 해설에 사용한 python 프로그램을 한국소성가공학회 홈페이지의 일반자료실에 올려놓았다.
본 해설에 사용한 python 프로그램을 한국소성가공학회 홈페이지의 일반자료실에 올려놓았다. 유전 알고리즘을 소성가공 연구에 활용하고자 하는 독자들은 프로그램을 각자의 문제에 맞게 수정하여 사용하길 추천한다.

참고문헌 (25)

M. Mitchell, 1996, An Introduction to Genetic Algorithms, MIT Press.
E. H. L. Aarts, A. H. Eiben, K. M. V. Hee, 1989. A general theory of genetic algorithms, In Computing Science Notes., Eindhoven University of Technology.
D. G. Goldberg, 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.
E. Wirsansky, 2020, Hands-On Genetic Algorithms with Python: Applying genetic algorithms to solve real-world deep learning and artificial intelligence problems, CreateSpace.
J. H. Holland, 1992, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, A Bradford Book
J. S. Chung, S. M. Hwang, 1996, Application of Genetic Algorithm to Die Shape Otimization in Extrusion, Trans. Mater. Process., Vol. 5, No. 4, PP. 269~280.
W. S. So, J. H. Jung, 2006, Development of Production Scheduling Management Program using Genetic Algorithm for Polymer Production, Korean Chem. Eng. Res., Vol. 44, No. 2, April, 2006, pp. 149-159.
D. H. Kim, B. W. Yoon, J. H. Lee, 2011,Size and Shape Optimization of Truss Structures using Micro Genetic Algorithm, J. Kor. Society. Steel. Constr., Vol. 23, No.4, pp.465~474.
Y. H. Lee, E. T. Park, J. Kim, B. S. Kang, W. J. Song, 2019, Optimization on Weight of High Pressure Hydrogen Storage Vessel Using Genetic Algorithm, Trans. Mater. Process., Vol. 28, No. 4, PP. 203~211.

원문보기 상세보기
D. Hermawanto, 2013, Genetic Algorithm for Solving Simple Mathematical Equality Problem, Comput. Sci.
島田拓？, 2016, M.S., 遺？的アルゴリズムを用いた勤務スケジュ？ル作成, Chuo university.
B. T. Zhang, 1995, Genetic Algorithm Theory and Applications, Inst. Electr. Information. Eng., Vol. 22, No. 11, pp. 1290~1300.
S. Chatterjee, C. Carrera, L. A. Lynch, 1996. Genetic algorithms and traveling salesman problems, Eur. J. Oper. Res., Vol. 93, No. 3, pp. 490~510.

상세보기
C. Sheppard, 2018, Genetic Algorithms with Python, CreateSpace.
W. J. Lee, H. Y. Kim, 2005, Genetic Algorithm Implementation in Python, Proc. Kor. Information. Process. Society Conf., Vol. 12, No. 1, PP. 473~476.
https://pythonhealthcare.org/2018/10/01/94-geneticalgorithms-a-simple-genetic-algorithm/
H. Iseki, K. Kato, S. Sakamoto, 1992, Flexible and Incremental Sheet Metal Bulging Using a Path-Controlled Spherical Roller. Trans. Jpn. Soc. Mech. Eng. Vol. 58, pp. 3147~3155.
T. McAnulty, J. Jeswiet, M. Doolan, 2017 Formability in single point incremental forming: A comparative analysis of the state of the art. CIRP. J. Manuf. Sci. Technol, Vol.16, pp. 43~54.

상세보기
S. Gatea, H. Ou, G. McCartney, 2016, Review on the influence of process parameters in incremental sheet forming, Int. J. Adv. Manuf. Technol., Vol. 87, pp. 479~499.

상세보기
S. Yang, Y. S. Kim, 2020, Optimization of Process Parameters of Incremental Sheet Forming of Al3004 Sheet Using Genetic Algorithm-BP Neural Network, J. Kor. Acad.-ind. Coop. Society., Vol. 21, No. 1 pp. 560~567.

원문보기 상세보기
A. Lawrynowicz, 2011, Genetic algorithms for solving scheduling problems in manufacturing systems, Found. Manag., Vol. 3, No. 2, pp. 7~25.

상세보기
B. J. Park, H. R. Chol, H. S. Kim, 2003, A hybrid genetic algorithm for the job shop scheduling problems, Comput. Ind. Eng., Vol. 45, No. 4, pp. 597~613.

상세보기
T. C. E.Cheng, B. M. T. Lin, 2009, Johnson's rule, composite jobs and the relocation problem, Eur. J. Oper. Res., Vol. 192, No. 3, pp. 1008~1013.

상세보기
J. M. Wilson, 2003, Gantt charts: A centenary appreciation, Eur. J. Oper. Res., Vol. 149, No. 2, pp. 430~437.

상세보기
https://colab.research.google.com/github/jckantor/ND-Pyomo-Cookbook/blob/master/docs/04.03-JobShop-Scheduling.ipynb#scrollTo20k5vVxKIshoF

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

연합인증