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

류광렬(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.

승무일정계획의 최적화를 위한 이웃해 탐색 기법과 정수계획법의 결합

황준하(Junha Hwang),류광렬(Kwang Ryel Ryu) 한국정보과학회 2004 정보과학회논문지 : 소프트웨어 및 응용 Vol.31 No.6

정수계획법에 기반한 기법들은 다양한 승무일정계획 최적화 문제를 해결하는 데 매우 효과적인 것으로 알려져 있다. 그러나 정수계획법은 대상 문제의 제약조건 및 목적함수가 모두 선형적으로 표현되어야만 적용이 가능하다는 단점이 있으며 문제의 규모가 클 경우 과도한 수행 시간과 메모리 자원을 요구하게 된다. 반면 이웃해 탐색 기법과 같은 휴리스틱 탐색 기법은 대상 문제의 제약조건이나 목적함수의 형태에 관계없이 쉽게 적용이 가능하다. 그러나 이웃해 탐색 기법은 복잡한 탐색 공간을 탐색할 경우 국소 최적해에 도달한 후 국소 최적해로부터 쉽게 빠져나오지 못하는 경우가 많다. 본 논문에서는 이웃해 탐색 기법과 정수계획법의 장점을 효과적으로 결합하기 위한 방안을 제시하고 있으며 실제 운행중인 지하철 승무일정계획 문제에 적용해 봄으로써 대규모 승무일정계획 최적화 문제에 성공적으로 적용될 수 있음을 확인하였다. Methods based on integer programming have been shown to be very effective in solving various crew pairing optimization problems. However, their applicability is limited to problems with linear constraints and objective functions. Also, those methods often require an unacceptable amount of time and/or memory resources given problems of larger scale. Heuristic methods such as neighborhood search, on the other hand, can handle large-scaled problems without too much difficulty and can be applied to problems having any form of objective functions and constraints. However, neighborhood search often gets stuck at local optima when faced with complex search spaces. This paper presents a hybrid algorithm of neighborhood search and integer programming, which nicely combines the advantages of both methods. The hybrid algorithm has been successfully tested on a large-scaled crew pairing optimization problem for a real subway line.

녹색 에너지 자립섬을 위한 스마트 그리드 운영 프레임워크

박지헌(Jiheon Park),류광렬(Kwang Ryel Ryu) 한국컴퓨터정보학회 2014 한국컴퓨터정보학회 학술발표논문집 Vol.22 No.1

에너지 자립섬은 외부 전력의 유입이 어려운 상황에서 풍력/태양광 발전과 같은 재생 에너지를 주요 발전원으로 운영하는 섬이다. 에너지 자립섬의 운영을 위해서는 전력 수요와 공급량을 예측하여 발전기, 송배전 시스템, ESS 등의 운영 계획 수립이 필요한데 수요 및 공급의 예측은 기상 상황 및 시간 등의 다양한 요소에 영향을 받으므로 예측이 어렵다. 이러한 특성을 감안하여 효율적인 전력망 운영을 위해 기계 학습을 기반으로 한 스마트 그리드 운영 프레임워크의 활용을 통해 이 문제를 해결하고자 한다. 본 논문에서는 자립섬 운영 계획 수립에 필요한 구성 요소를 파악하고 요소들 간의 연계 관계를 분석하여 운영 시스템의 프레임워크 설계안을 제시한다.

내부 디스정션 표현이 가능한 서브그룹 규칙 학습 방법

김세영(Seyoung Kim),류광렬(Kwang Ryel Ryu) 한국컴퓨터정보학회 2017 韓國컴퓨터情報學會論文誌 Vol.22 No.1

We can obtain useful knowledge from data by using a subgroup discovery algorithm. Subgroup discovery is a rule model learning method that finds data subgroups containing specific information from data and expresses them in a rule form. Subgroups are meaningful as they account for a high percentage of total data and tend to differ significantly from the overall data. Subgroup is expressed with conjunction of only literals previously. So, the scope of the rules that can be derived from the learning process is limited. In this paper, we propose a method to increase expressiveness of rules through internal disjunctive representation of attribute values. Also, we analyze the characteristics of existing subgroup discovery algorithms and propose an improved algorithm that complements their defects and takes advantage of them. Experiments are conducted with the traffic accident data given from Busan metropolitan city. The results shows that performance of the proposed method is better than that of existing methods. Rule set learned by proposed method has interesting and general rules more.

문서 클러스터링에 의한 효율적인 병렬 정보검색 시스템

강유경(Yu Gyung Kang),류광렬(Kwang Ryel Ryu),정상화(Sang-Hwa Chung) 한국정보과학회 2001 정보과학회논문지 : 소프트웨어 및 응용 Vol.28 No.2

본 논문은 고품질의 정보를 신속하게 제공할 수 있으면서 가격대 성능비가 우수한 병렬 정보검색 시스템을 제시하고 있다. 본 검색 시스템은 문서 라이브러리를 여러 개의 클러스터로 세분화하고 검색 시 클러스터 단위로 프로세서에 할당함으로써 작업 단위를 적절한 규모로 하였을 뿐만 아니라, 문서의 점수 계산 시 프로세서 간 통신이 전혀 필요치 않게 하였다. 검색은 1차로 클러스터 레벨에서 관련 클러스터들을 찾는 것으로 시작하여 2차로 관련 클러스터 내에서 실제 문서를 찾는 방식으로 이루어진다. 이러한 계층적인 검색 구조로 인하여 1차 검색 후 여과가 가능하므로 전체적인 검색의 부하를 줄일 수 있다. 또한 문서의 클러스터가 가능한 한 유사한 문서군이 되도록 함으로써 불필요한 클러스터가 검색될 가능성을 최소화하여 성능을 높였다. 본 검색 시스템은 분산메모리 MIMD 구조의 다중 트랜스퓨터 시스템에서 구현되었으며, 실험 결과 무작위적으로 클러스터링한 경우에 비해 유사 문서군으로 클러스터링한 접근 방법이 우수함을 확인하였다. This paper presents a fast and cost-effective parallel information retrieval system. In this system, the document library is divided into many clusters so that retrieval tasks are assigned to each processor on cluster-by-cluster basis. To minimize the number of clusters relevant to a user's query, each cluster is made to consist of similar documents. The size of the clusters are determined in such a way that the balancing of loads among the working processors is easily achievable. The retrieval is done in two stages. In the first stage, all the clusters relevant to the user's query are retrieved and those with low scores are screened out to lessen the load of the second stage. The qualified clusters are then distributed to the processors. In the second stage, relevant documents are retrieved from the assigned clusters and those documents are scored. There is no need for inter-processor communication during document scoring because all the necessary information is self-contained in the respective cluster. The system has been implemented on a multi-transputer system which is a distributed memory MIMD machine. Experimental results show that our similarity-based document clustering scheme gives better performance than a random clustering scheme.