표제지
목차
약어표 9
Abstract 11
Ⅰ. 서론 13
1. 연구 배경 13
2. 연구 내용 및 논문의 구성 15
Ⅱ. 관련 연구 20
1. 2차할당문제 20
2. 조합 최적화 24
3. 진화 컴퓨팅 26
1) 진화 알고리즘 26
2) 유전 알고리즘 27
3) 유전 알고리즘과 진화 알고리즘의 차이 28
4) 밈틱 알고리즘 29
4. 로컬 탐색 성능 개선을 위한 기존 연구 32
5. 최적화 문제에 GPU 기반 병렬 처리를 접목한 연구 38
6. 2차할당문제에 기계을 접목한 연구 39
7. 조합 최적화를 위한 딥러닝 기술 40
8. 기존 연구의 문제점 43
9. QAPLIB 44
1) 문제 인스턴스와 그 솔루션 45
2) 2차할당문제를 위한 소프트웨어 48
10. 비교 대상 모델 48
1) R 기반 시뮬레이티드 어닐링(R) 49
2) C++ 기반의 시뮬레이티드 어닐링(SA) 49
3) Java 기반의 원탁 그룹 최적화(RTGO) 50
4) 하이브리드 유전 알고리즘(HGA) 50
5) Mallows Model(MM) 52
Ⅲ. 설계 54
1. 온도 어닐링 기반의 소프트맥스 54
2. 의사 원핫 벡터 생성 55
3. 마스크드 소프트맥스 설계 56
4. 병렬 마스크드 소프트맥스 설계 61
5. 밈틱 알고리즘 기반 구현 65
6. GPLSIMA-QAP 68
7. 텐서플로우 기반 구현 70
Ⅳ. 성능 실험 및 평가 74
1. 실험 환경 74
1) 데이터 세트 74
2) 비교 대상 모델 74
3) 하이퍼파라미터 75
4) 소프트웨어 세부 설정과 하드웨어 환경 구성 75
2. 실험 결과 77
1) 마스크드 소프트맥스와 병렬 마스크드 소프트맥스 설계 간의 비교 77
2) 매개변수의 민감도(Parameter Sensitivity) 78
3) 제안하는 GPLSIMA-QAP와 비교 대상 모델들과의 비교 81
Ⅴ. 결론 93
참고문헌 96
국문초록 101
표 1. 밈틱 알고리즘의 파라미터 66
표 2. 제안하는 GPLSIMA-QAP의 의사 코드 69
표 3. GPLSIMA-QAP 기반 마스크드 소프트맥스 기준 병렬 마스크드 소프트맥스의 실행 시간 차이 비교 77
표 4. (m=10, r=0.1) 대비 효율의 비교 78
표 5. 대규모 2차할당문제 벤치마크 인스턴스에 대한 실험 결과(1) 79
표 6. 대규모 2차할당문제 벤치마크 인스턴스에 대한 실험 결과(2) 80
표 7. 인스턴스별 최적 모델 기준 비교 결과(1) 85
표 8. 인스턴스별 최적 모델 기준 비교 결과(2) 86
표 9. 실행시간의 평균, 표준편차 및 상대 실행시간 비교 결과 90
표 10. 병렬 마스크드 소프트맥스 기반 신경망 ƒ′에 의해 생성된 할당 행렬 91
그림 1. 제안하는 GPLSIMA-QAP의 개념도 14
그림 2. 5개 공장 및 5개 주의 할당 예 16
그림 3. 최적화 문제 해결을 위한 솔루션 유형 26
그림 4. 진화 사이클 27
그림 5. Ptr-Net의 구조 42
그림 6. Bur26a에서 A 행렬 46
그림 7. Bur26a에서 B 행렬 46
그림 8. Bur 26a에서 솔루션 47
그림 9. Hybrid Genetic Algorithm의 플로우차트 52
그림 10. 행렬 할당 예시 58
그림 11. 일반적인 학습 네트워크 구조 60
그림 12. 제안하는 학습 네트워크 구조 60
그림 13. 본 논문에서 제안하는 간단한 신경망 구조 63
그림 14. 유전 알고리즘과 밈틱 알고리즘의 비교 68
그림 15. 제안하는 GPLSIMA-QAP에서 활용한 텐서플로우 코드에 대한 DAG 72
그림 16. 대규모 벤치마크 인스턴스에 대한 실험 결과(실행시간) 82
그림 17. 대규모 벤치마크 인스턴스에 대한 실험 결과(효율성) 83
그림 18. 인스턴스별 최적 모델 기준 효율성 비교 결과(히트맵) 87
그림 19. 인스턴스별 최적 모델 기준 비용 비교 결과(히트맵) 88
그림 20. 인스턴스별 최적 모델 기준 실행시간 비교 결과(히트맵) 89
그림 21. 인스턴스들에 대한 실행시간 비교(박스플롯) 90
그림 22. 병렬 마스크드 소프트맥스 기반 신경망 ƒ′에 의한 수렴 과정 92