다수 목표간의 상호간섭에 대한 학습을 통한 계획효율의 개선

류광렬(Kwang Ryel Ryu) 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.3

계획 시스템이 복수개의 목표를 가진 문제를 풀기 위해 탐색을 수행하는 경우, 그 목표들이 수행되어야 할 올바른 순서지정에 관한 규칙을 찾아 학습하도록 함으로써 시스템 스스로가 성능을 향상시킬 수 있게 하려는 연구가 최근 상당한 성과를 얻고 있다. 그런데, 목표 순서지정 규칙에 관한 종래의 연구 결과는 주로 두개의 목표 사이의 순서지정에 대한 학습으로 국한되어 왔다. 본 연구에서는 이를 확장하여 세 개의 목표를 사이의 복잡한 간섭현상을 분석하고, 여러 목표들이 달성되어야 할 최적의 순서를 찾기까지 거치게 되는 몇 단계의 순서 재배치 과정을 종합 분석함으로써 복수 목표간의 순서지정 규칙을 유도해 낼 수 있는 새로운 학습방법을 개발하였다. 이 새 방법을 계획시스템 상에 구현한 PAL-Ⅱ 시스템을 일련의 실험을 통해 평가해 본 결과, 특히 문제에 주어진 목표의 수가 많을 경우 계획에 소요되는 처리 시간을 학습 결과를 이용하여 단축시킴으로써 시스템의 성능을 상당히 향상시킬 수 있음을 확인하였다. Significant research results are available in the area of improving the efficiency of a planning or problem solving system by learning goal ordering rules to avoid goal interactions that can arise during the solution of problems with conjunctive goals. Previous results for learning goal ordering rules, however, were limited to learning from only pairwise goal interactions. This research presents a new learning method that can analyze complex goal interactions involving three goals to derive ordering rules. The new method is developed based on the analysis of the procedure that searches for an optimal ordering of goals through multiple steps of re-ordering. In a series of empirical tests, the newly implemented planning and learning system PAL-Ⅱ showed significantly improved performance by the use of non-pairwise goal ordering rules especially when the number of goals given in a problem is large.

계층적 유전 알고리즘에 의한 부하 평준화 시스템

류광렬(Kwang Ryel Ryu),황준하(Junha Hwang),최형림(Hyung Rim Choi),조규갑(Kyu Kap Cho) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2A

본 논문은 작업일정계획에서의 부하 평준화 문제를 효율적으로 해결하기 위하여 계층적 유전 알고리즘의 적용 방법을 제시하고 있다. 전체적인 부하 평준화를 위해 우선 상위 단계에서는 작업장들 사이의 부하가 평준화되도록 하며 하위 단계에서는 각 작업장 내에서 일자별 부하가 평준화되도록 하였다. 이 두 단계 각각의 문제 해결을 위해 유전 알고리즘을 사용하였으며, 하위 단계에서 문제가 발생했을 경우 이를 상위 단계에 반영하여 다시 계획을 수립하는 등 반복적인 탐색 과정을 통하여 해를 개선시킬 수 있는 방법을 제시하였다. 실험 결과, 계층적 유전 알고리즘이 기존의 다른 방법들보다 좋은 해를 탐색할 수 있음을 확인되었다.

유전 알고리즘을 이용한 자동차 부품공장의 작업 일정계획 수립

류광렬(Kwang Ryel Ryu),박성훈(Sung Hoon Park),김갑환(Kap Hwan Kim),홍봉희(Bong Hee Hong) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

일정계획은 일종의 최적화 문제로서 현실적 대규모 문제의 경우 그 복잡도가 매우 높으므로 최근 들어 전통적인 수리적 기법 외에 여러 가지 AI기법을 응용하려는 노력이 계속되고 있다. 본 논문은 실제의 자동차 부품 공장을 대상으로 유전 알고리즘을 적용하여 복잡한 일정계획 문제를 성공적으로 풀 수 있음을 보인 것이다. 문제 해결의 가장 중요한 관건이 되는 유전자 표현법으로는 직접적인 방식과 간접적 방식의 절충행을 택하였고, 실험 결과 거의 최적에 가까운 일정계획이 약8분의 계산 시간으로 구해져 충분히 실용화가 가능함을 확인했다.

사출금형부품의 특지형상의 분류 및 표현방법의 개발

경영민,류광렬,정영득,조규갑,Kyoung, Young-Min,Ryu, Kwang-Ryel,Jeong, Yeong-Deug,Cho, Kyu-Kab 한국정밀공학회 1995 한국정밀공학회지 Vol.12 No.11

This paper describes a hierarchical structure for feature definition and classification, and feature representation method based on frame structure for process planning of prismatic machined components of injection mold. The concept of Volume Removal Directions and Vertical Faces is proposed to develop a method to define and to classify features for components of injection mold systematically. A method for classifying features by the combination of volume removal directions and vertical faces is developed, and also a feature representation method by using frame structure to represent design and manufacturing information is presented.

가감속을 고려한 교착없는 AGV 주행경로설정

최이,박태진,류광렬,Choe, Ri,Park, Tae-Jin,Ryu, Kwang-Ryel 한국항해항만학회 2006 한국항해항만학회지 Vol.30 No.10

컨테이너 터미널과 같이 다수의 AGV(Automated Guided Vehicle)를 한정된 공간에서 동시에 운용하는 환경에서는 AGV의 작업생산성에 악영향을 주는 충돌, 데드락(deadlock), 라이브락(liveiock)이 발생할 확률이 높다. 또한, AGV의 가/감속 운동은 AGV의 주행시간을 예측하기 어렵게 만들기 때문에 AGV 라우팅을 더욱 어렵게 만드는 요인이다. 본 논문에서는 AGV 사이의 충돌, 데드락, 라이브락을 방지하기 위해 점유영역 예약테이블(Occupancy Area Reservation table; OAR table)을 이용하는 방법과 최적주행경로를 선택하기 위해 가감속 운동을 고려하여 AGV의 주행시간을 추정하는 방법을 제안한다. 시간중심 시뮬레이 션(time-driven simulation)을 통해 제안방안을 실험 한 결과 제안방안의 효과를 확인하였다. In the environment where multiple AGVs(Automated Guided Vehicles) operate concurrently in limited space, collisions, deadlocks, and livelocks which have negative effect on the productivity of AGVs occure more frequently. The accelerated motion of an AGV is also one of the factors that make the AGV routing more difficult because the accelerated motion makes it difficult to estimate the vehicle's exact travel time. In this study, we propose methods of avoiding collisions, deadlocks, and livelocks using OAR(Occupancy Area Reservation) table, and selecting best route by estimating the travel time of an AGV in accelerated motion. A set of time-driven simulation works validated the effectiveness of the proposed methods.

병렬 타부 탐색을 이용한 발전기 기동정지계획의 최적화

이용환,황준하,류광렬,박준호,Lee, yong-Hwan,Hwang, Jun-ha,Ryu, Kwang-Ryel,Park, Jun-Ho 한국정보과학회 2002 정보과학회논문지 : 소프트웨어 및 응용 Vol.29 No.9

발전기 기동정지 계획은 하나의 전력시스템을 형성하는 다수의 발전기에 대해서 주어진 여러 제약을 따르는 일간 또는 주간의 기동 및 정지시간을 결정하는 작업으로 다양한 제약과 방대한 탐색공간으로 인해 최적의 경제적 계획 수립이 매우 어려운 대규모 최적화 문제이다. 타부 탐색은 보통의 지역적 탐색법에 비해 국지적 최적해에 빠질 위험이 적고 다른 전역적 탐색기법에 비해 대상문제에 관한 지식을 충분히 활용하기에 유리하여 많은 최적화 문제에 사용되고 있다. 그러나 규모가 방대하면서 많은 제약조건이 존재하는 대규모 최적화 문제들은 타부 탐색으로도 빠른 시간내에 최적의 해를 찾아내기 힘들다. 본 논문은 대규모 최적화 문제의 하나인 발전기 기동정지 계획 문제를 타부 탐색의 병렬화를 통해 해결함으로써 탐색 소요시간의 단축과 함께 해의 질 또한 향상시킬 수 있음을 보여준다. The unit commitment problem in a power system involves determining the start-up and shut-down schedules of many dynamos for a day or a week while satisfying the power demands and diverse constraints of the individual units in the system. It is very difficult to derive an economically optimal schedule due to its huge search space when the number of dynamos involved is large. Tabu search is a popular solution method used for various optimization problems because it is equipped with effective means of searching beyond local optima and also it can naturally incorporate and exploit domain knowledge specific to the target problem. When given a large-scaled problem with a number of complicated constraints, however, tabu search cannot easily find a good solution within a reasonable time. This paper shows that a large- scaled optimization problem such as the unit commitment problem can be solved efficiently by using a parallel tabu search. The parallel tabu search not only reduces the search time significantly but also finds a solution of better quality.

Scheduling RMGs in a container terminal with determination of the intermediate location of containers

Yuan Hui(원휘),Kwang Ryel Ryu(류광렬),Ri Choe(최이) 한국지능정보시스템학회 2010 한국지능정보시스템학회 학술대회논문집 Vol.2010 No.11월

This paper addresses the problem of scheduling the twin rail-mounted gantry (RMG) cranes used at automated container terminals. We consider this problem in a real-time situation and employ local search-based methods to optimize crane scheduling. The proposed method creates a schedule for the jobs requested within a given fixed-length horizon. To reflect changes in the situation, the method updates the crane schedule by rescheduling at fixed intervals. In the process of searching for the optimal schedule, the proposed method optimizes not just job assignment for each RMG and the sequence of job execution, but also the intermediate locations of containers. A simulation shows that the proposed method outperforms the previous methods it is compared with in terms of the waiting time of both the internal transportation vehicles (i.e. automated guided vehicles) and the external trucks.

능동적 학습을 위한 복수 문의예제 선정

강재호(Jaeho Kang),류광렬(Kwang Ryel Ryu) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1B

능동적 학습(active learning)은 제한된 시간과 인력으로 가능한 정확도가 높은 분류기(classifier)를 생성하기 위하여, 훈련집합에 추가할 예제 즉 문의예제(query example)의 선정과 확장된 훈련집합으로 다시 학습하는 과정을 반복하여 수행한다. 능동적 학습의 핵심은 사용자에게 카테고리(category) 부여를 요청할 문의예제를 선정하는 과정에 있다. 효과적인 문의예제를 선정하기 위하여 다양한 방안들이 제안되었으나, 이들은 매 문의단계마다 하나의 문의예제를 선정하는 경우에 가장 적합하도록 고안되었다. 능동적 학습이 복수의 예제를 사용자에게 문의할 수 있다면, 사용자는 문의예제들을 서로 비교해가면서 작업할 수 있으므로 카테고리 부여작업을 보다 빠르고 정확할 수 있어 전반적인 학습기산의 단축에 큰 도움이 될 것이다. 하지만, 각 예제의 문의예제로써의 적합 정도를 추정하면 유사한 예제들은 서로 비슷한 수준으로 평가되므로, 기존의 방안들을 복수의 문의예제 선정작업에 그대로 적용할 경우, 유사한 예제들이 문의예제로 동시에 선정되어 능동적 학습의 효율이 저하되는 현상이 나타날 수 있다. 본 논문에서는 특정 예제를 문의예제로 선정하면 이와 일정 수준이상 유사항 예제들은 해당 예제와 함께 문의예제로 선정하지 않음으로써, 이러한 문제점을 극복할 수 있는 방안을 제안한다. 제안한 방안을 문서분류 문제에 적용해 본 결과 기존 문의예제 선정방안으로 복수 문의예제를 선정할 때 발생할 수 있는 문제점을 상당히 완화시킬 있을 뿐 아니라, 복수의 문의예제를 선정하더라도 각 문의단계마다 하나의 예제를 선정하는 경우에 비해 큰 성능의 저하가 없음을 실험적으로 확인하였다.

기억기반학습을 이용한 사례기반설계시 참조사례의 인덱싱

강재호(Jaeho Kang),류광렬(Kwang Ryel Ryu),이동곤(Dongkon Lee) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.1

사례기반추론(Case-Based Reasoning, CBR)은 새로운 문제가 주어질 때 과거의 유사한 문제 해결 사례를 기반으로 그 해법을 적절히 변용함으로써 새로운 문제에 적합한 해결책을 효율적으로 도출하고자 하는 문제 해결 접근 방법이다. 사례기반설계는 사례기반추론을 설계에 응용한 방법으로 유사한 요구조건 하에서 설계된 과거사례를 설계에 참고 및 활용하는 방법으로 선박개념설계 등 여러 분야에서 활용하고 있다. 이러한 사례기반설계기법을 이용하여 효율적으로 고품질의 설계를 도출하기 위해서는 설계하고자 하는 대상의 설계상의 요구조건과 부합되는 사례를 적절히 선정해야 하고, 선정된 사례와 현 설계조건과의 차이점을 명확하게 인지하여 현 상황에 맞게 변용할 수 있어야 한다. 본 논문에서는 과거 사례 선정 기록을 활용하여 그 선정 경향을 기억기반학습기법을 이용하여 학습함으로써 새로운 설계 시 적절한 사례를 선정하는 인덱싱 기법을 제시한다. 사례기반설계의 전형적인 예인 선박개념설계에서 설계 시 참조용도로 사용할 실적선을 선정하는 문제에 적용하여 실험해 본 결과 decision tree나 간단한 휴리스틱을 적용하여 참조 사례를 제시한 방법에 비해 본 논문에서 제시하는 기억기반학습을 적용한 방법이 우수함을 확인하였다. The case-based reasoning (CBR) is an approach for solving a new problem by retrieving past similar cases and adapting their solutions. The case-based design is an application of case-based reasoning to design domains such as a conceptual ship design. There are two important aspects to consider for producing an efficient and high quality design by using case-based design methodology. One is the selection of appropriate cases from the pool of past cases, and the other is the adaptation of the selected cases to make them suitable for new design requirements by recognizing differences of previous and current design environment. This paper presents a method of applying a memory-based learning (MBL) technique to automatic building of an indexing scheme for selecting reference cases by using the history of previous references. Empirical results show that the indexing scheme generated by MBL outperforms those by other learning methods such as the decision tree learning or a simple heuristic in our conceptual ship design domain.

군집화 기법을 이용한 능동적 학습의 최초학습예제 선정

강재호(Jaeho Kang),류광렬(Kwang Ryel Ryu) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅰ

기계학습의 분류(classification) 기술을 실제 문제에 적용하기 위해서는 카테고리(category)를 부여한 학습예제를 상당수 준비하여야 한다. 예제에 카테고리를 부여(labeling)하는 작업에는 무시할 수 없는 시간과 인력을 필요로 한다. 능동적 학습(active learning)은 동일한 수의 학습예제로 최대한의 성능을 달성하기 위하여 카테고리를 부여할 학습예제를 선별하는 전략이다. 능동적 학습은 현재까지 파악된 정보에 기반하여 분류기(classifier)를 생성하고, 생성된 분류기를 활용하여 카테고리를 부여 받았을 때 가장 이득이 큰 예제들을 선정하여 사용자에게 문의하는 과정을 반복하여 수행한다. 만일 능동적 학습의 첫 학습단계에서 학습에 보다 유용한 예제들을 최초학습예제집합으로 선정한다면 같은 수의 학습예제로 더 나은 성능을 달성할 수 있을 것이다. 본 논문에서는 유사한 예제들은 동일한 카테고리에 속할 가능성이 높다는 일반적인 가정에 기반하여 예제들을 군집화(clustering)한 후, 생성된 각 군집을 대표할 수 있는 예제로 최초학습예제집합으로 구성하는 방안을 제안한다. 제안한 방안을 문서분류 문제를 대상으로 실험해 본 결과 최초학습예제들을 임의로 선정하는 방식보다 정확도가 높은 분류기를 생성할 수 있음을 확인하였다.