검색 상세

선행 제약이 있는 빈 패킹 문제를 위한 제약 인식 개인 최선 위치 기반 입자 군집 최적화

  • 이원석 (아주대학교 일반대학원)

초록/요약

본 연구는 선행 제약이 있는 빈 패킹 문제(BPP-P; bin packing problem with precedence constraints)를 위한 새로운 입자 군집 최적화(PSO; particle swarm optimization) 방법인 “제약 인식 개인 최선 위치 기반 입자 군집 최적화”(PSO-CCP; PSO with constraint conscious personal best position)을 제안한다. 제약 조건 문제에서 입자 군집 최적화(PSO)의 한계점은 제약 조건을 위반하는 해 공간(infeasible region)을 불필요하게 탐색하는 과정에서 군집 최선 위치(Gbest; global best position)로의 조숙한 수렴(premature convergence)할 가능성이 높다는 점이다. 이로 인해 국소 최적해(local optima)에서 빠져나올 가능성이 낮아 전역최적해(optimal solution)을 쉽게 지나칠 가능성이 높다. 이러한 문제를 해결하고자, 기존의 입자 군집 최적화(PSO)의 한계점을 완화할 수 있게 PSO-CCP를 설계하였다. PSO-CCP에서 제약 인식 개인 최선 위치(CCP; constraint conscious personal best position)는 각 입자의 위치에서의 목적함수 값과는 관계없이 오직 제약조건 위반 정도를 고려한 개인 최선 위치(Pbest; personal best position)이다. PSO-CCP에서 CCP의 도입으로 나타나는 입자들의 특성은 두 가지가 있다. 첫 번째 특성은 각 입자들이 각 CCP 주변 영역을 탐색하여 제약 조건을 만족하는 해(feasible solution)을 효율적으로 발견할 가능성이 높다. 두 번째 특성은 PSO-CCP에서 입자들은 입자 군집 최적화 알고리즘(PSO)의 입자들과 비교하여 이동거리가 짧아 CCP 영역 주변을 자세히 탐색한다. PSO-CCP는 입자 군집 최적화 알고리즘(PSO)와 비교하여 제약 조건을 만족하는 해(feasible solution)을 효율적으로 발견하고 군집 최선 위치(Gbest)로의 조숙한 수렴할 가능성이 낮다. PSO-CCP의 입자들이 군집 최선 위치 (Gbest)로의 조숙한 수렴하지 않는 과정에서 입자들의 속도 크기가 비교적 작으며 제약 인식 개인 최선 위치(CCP)는 반복적으로 변화한다. 이로 인해 PSO-CCP는 PSO에 비해 전역최적해를 찾는 효과성은 증가한다. PSO-CCP는 BPP-P의 한 유형인 단일 조립 라인 균형 문제 유형 1(SALBP-1; simple assembly line balancing problem-1)에 적용하여 PSOCCP가 PSO보다 더 최적해에 가까운 해를 찾는다는 것을 검증한다. 제약 인식 개인 최선 위치(CCP)가 문제 특성에 따라 적절하게 정의된다면 PSO-CCP는 BPP-P뿐만 아니라 다양한 제약 기반 문제에 대해서도 PSO에 비해 더 최적해에 가까운 해를 찾을 것으로 기대된다. 주제어: 입자 군집 최적화 알고리즘, 군집 지능, 실현 가능성, 선행제약이 있는 빈 패킹 문제, 제약 기반 최적화 문제, 단일 조립 라인 균형 문제 유형 1

more

목차

제1장 서론 1
제2장 관련 연구 5
제3장 BPP-P 및 PSO 18
제1절 BPP-P의 정의 및 수리모형 18
제2절 PSO의 정의 및 수리모형 20
제4장 BPP-P에서의 PSO-CCP 21
제1절 BPP-P 제약 조건 변환 및 CCP 정의 22
제2절 BPP-P에서의 PSO-CCP 알고리즘 절차 24
제3절 BPP-P에서의 PSO-CCP 입자의 반복적 탐색 과정에 대한 실험적 검증 34
제4절 BPP-P에서 PSO-CCP가 전역최적해를 찾는 효과성 39
제5장 실험 설정 및 결과 47
제1절 실험 데이터 및 파라미터 설정 47
제2절 실험 결과 52
제6장 논의 56
제7장 요약 및 결론 60
References 62
부록 67
Abstract 71

more
반출 Meta View 목록