유전자 알고리즘을 이용한 CORBA 기반의 재사용 클래스 라이브러리 구현

이병정(Byung-Jeong Lee),문병로(Byung-Ro Moon),우치수(Chi-Su Wu) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.2

Software reuse is very important to improve development productivity and code reliability. An object-oriented reuse library with an elaborate classification scheme and a precise retrieval system is essential for efficient reuse. In this study, we apply a genetic algorithm to multi-way clustering and cluster-based linear retrieval in a reuse library. The multi-way clustering tries to find an optimal component grouping and classify components elaborately by considering the number of clusters, similarity in a cluster, and similarity between clusters; the cluster-based linear retrieval tries to find an optimal query that retrieves clusters containing many components similar to a given query. In this paper, our experimental results have shown that genetic algorithm produces better solutions than simulated annealing algorithm. We also describe a Reusable Class Library(RCL) based on CORBA using the algorithm. 개발 과정의 생산성과 프로그램의 신뢰성을 향상시키기 위하여 소프트웨어 재사용이 매우 중요하며, 효과적인 재사용을 위해서 세밀한 분류 방법과 정확한 검색 방법에 기반한 객체 지향 재사용 라이브러리가 필수적이다. 본 연구에서는 재사용 라이브러리의 다중 클러스터링(multi-way clustering) 분류 방법과 클러스터 기반 성형 검색(cluster-based linear retrieval) 방법에 유전자 알고리즘(genetic algorithm)을 적용한다. 다중 클러스터링은 부품들이 할당된 클러스터 개수, 클러스터 내부 유사도 그리고 클러스터들 사이의 유사도를 최적화하는 클러스터링을 찾아 부품을 세밀히 분류하는 것이고, 클러스터 기반 선형 검색은 주어진 질의와 유사한 부품을 많이 포함하는 클러스터를 검색하는 것이다. 본 논문에서는 유전자 알고리즘이 시뮬레이티드 어닐링 알고리즘(simulated annealing algorithm)보다 우수한 해를 찾는 것을 실험을 통하여 보이고, 또한 본 알고리즘을 이용한 CORBA 기반의 재사용 클래스 라이브러리(RCL)를 기술한다.

서열순서화문제를 위한 상위정보를 이용하는 혼합형 유전알고리즘

서동일(Dong-Il Seo),문병로(Byung-Ro Moon) 한국지능시스템학회 2005 한국지능시스템학회논문지 Vol.15 No.6

본 논문에서는 서열순서화문제를 위한 새로운 혼합형 유전알고리즘을 제안한다. 제안된 유전알고리즘에서는 보로노이양자 화교차를 교차연산자로 사용하고 경로보전 3-최적화를 지역탐색 휴리스틱으로 사용한다. 보로노이양자화교차는 주어진 문제 인스턴스의 상위 정보를 이용하는 교차연산자이다. 이것은 원래 순회판매원문제를 위해서 제안된 교차연산자이기 때문에 서열순서화문제에 적용하기 위해서는 상당한 변형을 필요로 한다. 본 연구에서는 서열순서화문제에 맞도록 보로노이양자화교차를 적절히 변형하고, 변형된 보로노이양자화교차에서 필요로 하는 가능해생성알고리즘, 선행관계사이클분해알고리즘, 유전자거리지정방법 등을 개발하였다. TSPLIB와 ZIB-MP-Testdata로부터 얻어진 서열순서화문제 인스턴스들에 대한 실험결과, 제안된 유전알고리즘이 비교된 다른 유전알고리즘들에 비해서 더 안정적이고 성능이 우수한 것으로 나타났다. In this paper, we propose a new hybrid genetic algorithm for sequential ordering problem (SOP). In the proposed genetic algorithm, the Voronoi quantized crossover (VQX) is used as a crossover operator and the path-preserving 3-Opt is used as a local search heuristic. VQX is a crossover operator that uses the epistasis information of given problem instance. Since it is a crossover proposed originally for the traveling salesman problem (TSP), its application to SOP requires considerable modification. In this study, we appropriately modify VQX for SOP, and develop three algorithms, required in the modified VQX, named Feasible Solution Generation Algorithm, Precedence Cycle Decomposition Algorithm, and Genic Distance Assignment Method. The results of the tests on SOP instances obtained from TSPLIB and ZIB-MP-Testdata show that the proposed genetic algorithm outperforms other genetic algorithms in stability and solution quality.

유전 알고리즘과 디지털 카메라를 이용한 엘리베이터군 제어

김정환(Jung-Hwan Kim),문병로(Byung-Ro Moon) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1B

이 논문에서는 유전 알고리즘과 디지털 카메라를 이용한 새로운 엘리베이터군 제어 정책을 제안한다. 유전 알고리즘을 이용하여 각 층에서 일어나는 hall call에 대한 타당한 엘리베이터를 할당하는 엘리베이터 제어 시스템을 구성한다. 유전 알고리즘의 문제 공간 탐색 능력을 이용하여 각 교통량 패턴에 잘 적응하는 hall call과 car call을 다루는 타당한 제어 정책과 프로시져를 찾아낸다. 또한 디지털 카메라를 사용하여 각 층에서 엘리베이터를 기다리는 승객들의 수를 예측함으로 각 승객들의 탑승 대기 시간을 줄이는 새로운 방법을 제안한다.

비유사 중복 인코딩을 사용하는 유전 알고리즘을 위한 정규화 연산

최성순(Sung-Soon Choi),문병로(Byung-Ro Moon) 한국정보과학회 2007 정보과학회논문지 : 소프트웨어 및 응용 Vol.34 No.6

정규화는 교차 연산 전에 두 부모해 사이의 일관성을 유지하기 위하여 한 부모해를 다른 부모해에 맞추어 변환하는 연산이다. 본 논문은 비유사 중복 인코딩이 유전 알고리즘의 성능을 떨어뜨리는 이유와 정규화 연산이 비유사 중복 인코딩에 의해 유발되는 문제점들을 어떻게 완화하는지 설명한다. 이를 위해 완전 비유사 중복 인코딩을 정의하고, 완전 비유사 중복 인코딩에 의해 적합도와 거리의 상관성이 없는 탐색 공간이 만들어짐을 증명한다. 또한, 완전 비유사 중복 인코딩을 사용하는 다수의 문제들에 대한 실험을 바탕으로, 정규화를 통해 상관성이 없는 탐색 공간이 상관성이 있는 탐색 공간으로 변화되어 유전알고리즘의 성능이 향상됨을 보인다. Normalization transforms one parent genotype to be consistent with the other before crossover. In this paper, we explain how normalization alleviates the difficulties caused by non-synonymously redundant encodings in genetic algorithms. We define the encodings with maximally non-synonymous property and prove that the encodings induce uncorrelated search spaces. Extensive experiments for a number of problems show that normalization transforms the uncorrelated search spaces to correlated ones and leads to significant improvement in performance.

표현상의 제약을 최소화한 유전 알고리즘의 인코딩과 교차 방법

정순철(Soonchul Jung),문병로(Byung-Ro Moon) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1B

유전 알고리즘에서 전통적인 일차원 염색체 표현으로는 보통 문제에 내재되어 있는 상당한 양의 정보가 손실된다. 예를 들어 그래프 구조를 선형 무자열로 인코딩할 때 한 노드의 인접 정보의 상당부분이 사라진다. 그래프 문제를 이차원 염색체 표현으로 인코딩하는 것이 일차원 염색체 표현으로 인코딩하는 것에 비하여 보다 좋은 결과를 보인다고 알려져 있다. 그러나 격자나 행렬같은 제한된 이차원 염색체 표현은 여전히 정보 손실을 야기시킨다. 본 논문은 문제의 정보를 최대한 보존하고, 교차함에 있어서 최대한의 자유를 주는 인코딩/교차 연산자 쌍을 제안한다. 순회 판매원 문제에 대한 실험 결과는 제안된 방법이 전통적인 선형 인코딩/교차 연산자 쌍보다 눈에 띄게 우수함을 보여준다.

중복 추천 문제를 반영한 다중 캠페인의 최적화

김용혁(Yong-Hyuk Kim),문병로(Byung-Ro Moon) 한국정보과학회 2005 정보과학회논문지 : 소프트웨어 및 응용 Vol.32 No.5

개인화된 마케팅에서 고객 만족과 마케팅 효율을 최대화하는 것은 중요하다. 개인화된 캠페인이 수행됨에 따라 여러 캠페인이 동시에 수행되곤 한다. 이 논문에서 우리는 동시에 여러 개인화된 캠페인을 수행할 때 발생하는 중복 추천 문제를 제기한다. 이는 특정 고객에게 상당히 많은 양의 캠페인이 쏟아지게 되는 문제를 말한다. 이 이슈를 해결하기 위한 다중캠페인 할당 문제를 모델링 한다. 그리고 이 문제의 해결 방법으로 동적계획법을 비롯한 여러 휴리스틱 알고리즘들을 제안한다. 필드 데이타의 실험을 통해 제기된 문제 모델의 중요성과 제안된 알고리즘의 효율성을 입증한다. In personalized marketing, it is important to maximize customer satisfaction and marketing efficiency. As personalized campaigns are frequently performed, several campaigns are frequently run simultaneously. The multiple recommendation problem occurs when we perform several personalized campaigns simultaneously. This implies that some customers may be bombarded with a considerable number of campaigns. We raise this issue and formulate the multi-campaign assignment problem to solve the issue. We propose dynamic programming method and various heuristic algorithms for solving the problem. With field data, we also present experimental results to verify the importance of the problem formulation and the effectiveness of the proposed algorithms.

유전 알고리즘에서의 자기 조직화 신경망의 활용

김정환(Jung-Hwan Kim),문병로(Byung-Ro Moon) 한국정보과학회 2006 정보과학회논문지 : 소프트웨어 및 응용 Vol.33 No.4

자기 조직화 신경망 (SOM: Self-Organizing Map)은 자율 학습 신경망으로 사전 지식이 존재하지 않는 자료에 존재하는 구조적 관계성을 보전하는데 이용된다. 자기 조직화 신경망은 벡터 양자화, 조합 최적화, 패턴 인식과 같은 복잡한 문제 해결을 위한 연구에 많이 이용되어 왔다. 이 논문에서는 좀더 효율적인 유전 알고리즘을 얻기 위한 스키마 변환 도구로서 자기 조직화 신경망을 이용하는 새로운 사용법에 대해서 제안한다. 즉, 각 자식해는 탐색 공간에서 좀더 바람직한 모양을 가지는 동질의 인공 신경망으로 변환된다. 이 변환으로 인해 강한 상위(epistasis)를 가지는 유전자들은 염색체 상에서 서로 인접하게 되는 것이다. 실험 결과는 기존 결과에 비해서 주목할만한 성능 개선이 있음을 보여준다. Self-Organizing Map (SOM) is an unsupervised learning neural network and it is used for preserving the structural relationships in the data without prior knowledge. SOM has been applied in the study of complex problems such as vector quantization, combinatorial optimization, and pattern recognition. This paper proposes a new usage of SOM as a tool for schema transformation hoping to achieve more efficient genetic process. Every offspring is transformed into an isomorphic neural network with more desirable shape for genetic search. This helps genes with strong epistasis to stay close together in the chromosome. Experimental results showed considerable improvement over previous results.

n차원 구면상에서의 실수 코딩 유전 알고리즘

김진현(Jin-Hyun Kim),문병로(Byung-Ro Moon) 한국정보과학회 2010 한국정보과학회 학술발표논문집 Vol.37 No.1A

본 연구에서는 실수 코딩을 사용하는 유전 알고리즘의 문제공간이 n차원 구면으로 제한된 경우에 사용 할 교배 연산자와 변이 연산자를 제안하고, 이를 실제로 사용한 실험 결과를 제시한다. n차원 실수 공간에서 일반적으로 사용되는 연산자를 n차원 구면에 사영하는 방법을 사용하였으며, 해의 범위가 제한된 경우에 사용할 해의 수선 방법도 제안하였다. 제안된 연산자를 사용하며 몇 가지 최적화 문제를 푸는 실험을 한 결과 평균 오차율 2.0%내에서 최적해를 구함을 확인하였다.

새로 출시되는 품목들을 위한 단어 기반의 사용자 선호도 예측 기법

최윤석(Yoon-Seok Choi),문병로(Byung-Ro Moon) 한국지능시스템학회 2006 한국지능시스템학회논문지 Vol.16 No.2

협동적 여과(CF) 시스템은 구현의 용이성과 뛰어난 성능으로 널리 활용되고 있다. 그러나 이 시스템은 데이터 희소성, 신상품 추천 불가, 추천 근거에 대한 설명 부족 등의 문제점을 포함하고 있어 이를 해결하기 위한 많은 연구가 진행되었다. 데이터 희소성 문제는 데이터의 누적에 따라 해결될 수 있지만, 협동적 여과 기법의 특성상 새로이 출시되는 품목에 대한 추천이 불가능하다. 이를 해결하기 위해 내용 기반(CB) 기법을 같이 사용하는 연구들이 제안되었다. 또한 협동적 여과 시스템은 추천 과정에 있어 추천 근거에 대한 설명을 제공하지 않는다. 본 연구에서는 추천에 대한 설명 기능을 포함하고 있는 선호 단어를 활용한 내용기반 예측 시스템을 제안한다. 이 시스템은 새로이 출시되는 영화에 대해 사용자의 영화에 대한 평가 정보를 예측하며, 추천의 근거가 되는 선호 단어를 제시한다. 또한 기존의 내용기반 예측 시스템에서 일어나는 속성 비매칭 문제로 인한 성능 저하를 막기 위해 기호 네트워크를 활용한 성능 개선 방법을 제안한다. 성능 비교를 위해 EachMovie 데이터베이스와 IMDb 사의 영화 홍보 데이터를 사용하였다. CF systems are widely used in recommendation due to the easy implementation and the outstanding performance. They have several problems such as the sparsity problem, the first-rater problem, and recommending explanation. Many studies are suggested to resolve these problems. While the influence of the sparsity problem lessens as the users' data are accumulated, but the first-rater problem is originated from the CF systems and there are a number of researches to overcome the disadvantages of CF systems based on the content-based methods. Also CF systems are black boxes, providing no explanation of working of the recommendation. In this paper we present a content-based prediction system based on the preference words, which exposes the reasoning behind a recommendation. Our system predicts user's rating of a new movie and we suggest a semiotic network-based method to solve the mismatching problem between the items. For experimental comparison, we used EachMovie and IMDb dataset.

전략 테이블과 유전 알고리즘을 이용한 LZ77 알고리즘의 성능 개선

정순철(Soonchul Jung),서동일(Dong-Il Seo),문병로(Byung-Ro Moon) 한국정보과학회 2004 정보과학회논문지 : 소프트웨어 및 응용 Vol.31 No.12

저장 공간이나 전송 시간을 줄여서 비용을 아끼는 데이타 압축 기술은 그 유용성 때문에 오래전부터 연구되어 왔다. Lempel-Ziv 77(LZ77) 알고리즘은 실용적인 사전-기반 비손실 압축 알고리즘이다. 기존의 LZ77 알고리즘에서 알고리즘의 성능에 큰 영향을 미치는, 사전의 크기는 고정되어 있다. 본 논문에서는 사전의 크기를 동적으로 바꾸면서 압축을 하는 동적 LZ77 알고리즘과 동적 LZ77 알고리즘에서 사용하는 전략을 진화시키는 유전 알고리즘을 소개한다. 유전 알고리즘으로 진화시킨 전략을 가지고 동적 LZ77 알고리즘은 기존의 LZ77 알고리즘보다 최대 약 16%까지 더 좋은 압축 효율을 보여 주었다. Data compression techniques have been studied for decades because they saved space and time to reduce costs. The Lempel-Ziv 77 (LZ77) is a dictionary-based, lossless compression algorithm. The dictionary size of the LZ77 algorithm is fixed, and the performance of the algorithm is highly dependent on its dictionary size. In this paper, we suggest a dynamic LZ77 algorithm that changes its dictionary size during compression, and also we suggest a genetic algorithm to evolve the dictionary-resizing strategies. The suggested algorithm outperformed the original version up to about 16%.