유전자 알고리즘의 수렴 속도 향상을 통한 효과적인 로봇 길 찾기 알고리즘

서민관(Min-Gwan Seo),이재성(Jae-Sung Lee),김대원(Dae-Won Kim) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.4

유전자 알고리즘은 초기 해 집합을 대상으로 해 집합의 평가와 유전자 연산자의 적용, 자연 선택 등의 과정을 반복하여 최적 해를 찾는 탐색 알고리즘이다. 유전자 알고리즘을 설계할 때 사용한 선택 전략, 세대교체 방법, 유전자 연산자 등은 유전자 알고리즘의 탐색 효율성에 영향을 준다. 본 논문에서는 시간 제약이 있는 상황에서의 로봇 경로탐색을 위해 기존의 유전자 알고리즘보다 빠르게 수렴하는 유전자 알고리즘을 제안한다. 로봇 경로 탐색 시 긴급한 상황에서 유전자 알고리즘은 연산을 위한 충분한 시간을 확보하지 못 하게 되고, 이는 최종적으로 찾아낸 경로의 질을 떨어뜨린다. 제안하는 알고리즘은 빠른 수렴을 위한 선택 전략, 세대교체 방법을 사용하였으며, 유전자 연산자로는 전통적인 교차, 돌연변이 외에 경로의 길이를 줄이기 위한 단축 연산자를 추가로 사용하였다. 이를 통해 제안하는 알고리즘은 적은 세대 수에도 빠르게 짧은 경로를 찾아낸다. The Genetic algorithm is a search algorithm using evaluation, genetic operator, natural selection to populational solution iteratively. The convergence and divergence characteristic of genetic algorithm are affected by selection strategy, generation replacement method, genetic operator when genetic algorithm is designed. This paper proposes fast convergence genetic algorithm for time-limited robot path planning. In urgent situation, genetic algorithm for robot path planning does not have enough time for computation, resulting in quality degradation of found path. Proposed genetic algorithm uses fast converging selection strategy and generation replacement method. Proposed genetic algorithm also uses not only traditional crossover and mutation operator but additional genetic operator for shortening the distance of found path. In this way, proposed genetic algorithm find reasonable path in time-limited situation.

다목적 유전자 알고리즘을 이용한문서 클러스터링

이정송(Jung Song Lee),박순철(Soon Cheol Park) 한국산업정보학회 2012 한국산업정보학회논문지 Vol.17 No.2

본 논문에서는 텍스트 마이닝 분야에서 중요한 부분을 차지하고 있는 문서 클러스터링을 위하여 다목적 유전자 알고리즘을 제안한다. 문서 클러스터링에 있어 중요한 요소 중 하나는 유사한 문서를 그룹화 하는 클러스터링 알고리즘이다. 지금까지 문서 클러스터링에는 k-means 클러스터링, 유전자 알고리즘 등을 사용한 연구가 많이 진행되고 있다. 하지만 k-means 클러스터링은 초기 클러스터 중심에 따라 성능 차이가 크며 유전자 알고리즘은 목적 함수에 따라 지역 최적해에 쉽게 빠지는 단점을 갖고 있다. 본 논문에서는 이러한 단점을 보완하기 위하여 다목적 유전자 알고리즘을 문서 클러스터링에 적용해 보고, 기존의 알고리즘과 정확성을 비교 및 분석한다. 성능 시험을 통해 k-means 클러스터링(약 20%)과 기존의 유전자 알고리즘(약 17%)을 비교할 때 본 논문에서 제안한 다목적 유전자 알고리즘의 성능이 월등하게 향상됨을 보인다. In this paper, the multi-objective genetic algorithm is proposed for the document clustering which is important in the text mining field. The most important function in the document clustering algorithm is to group the similar documents in a corpus. So far, the k-means clustering and genetic algorithms are much in progress in this field. However, the k-means clustering depends too much on the initial centroid, the genetic algorithm has the disadvantage of coming off in the local optimal value easily according to the fitness function. In this paper, the multi-objective genetic algorithm is applied to the document clustering in order to complement these disadvantages while its accuracy is analyzed and compared to the existing algorithms. In our experimental results, the multi-objective genetic algorithm introduced in this paper shows the accuracy improvement which is superior to the k-means clustering(about 20 %) and the general genetic algorithm (about 17 %) for the document clustering.

회로 분할을 위한 어댑티드 유전자 알고리즘 연구

송호정(Ho-Jeong Song),김현기(Hyun-Gi Kim) 한국콘텐츠학회 2021 한국콘텐츠학회논문지 Vol.21 No.7

VLSI 설계에서의 분할(partitioning)은 기능의 최적화를 위하여 설계하고자 하는 회로의 그룹화(grouping)하는 단계로서 레이아웃(layout)에서 면적과 전파지연의 최소화를 위해 함께 배치할 소자를 결정하는 문제이다. 이러한 분할 문제에서 해를 얻기 위해 사용되는 알고리즘은 Kernighan-Lin 알고리즘, Fiduccia Mattheyses heuristic, 시뮬레이티드 어닐링, 유전자 알고리즘 등의 방식이 이용된다. 본 논문에서는 회로 분할 문제에 대하여 유전자 알고리즘과 확률 진화 알고리즘을 결합한 어댑티드 유전자 알고리즘을 이용한 해 공간 탐색(solution space search) 방식을 제안하였으며, 제안한 방식을 유전자 알고리즘 및 시뮬레이티드 어닐링 방식과 비교, 분석하였고, 어댑티드 유전자 알고리즘이 시뮬레이티드 어닐링 및 유전자 알고리즘보다 더 효과적으로 최적해에 근접하는 것을 알 수 있었다. In VLSI design, partitioning is a task of clustering objects into groups so that a given objective circuit is optimized. It is used at the layout level to find strongly connected components that can be placed together in order to minimize the layout area and propagation delay. The most popular algorithms for partitioning include the Kernighan-Lin algorithm, Fiduccia-Mattheyses heuristic and simulated annealing. In this paper, we propose a adapted genetic algorithm searching solution space for the circuit partitioning problem, and then compare it with simulated annealing and genetic algorithm by analyzing the results of implementation. As a result, it was found that an adaptive genetic algorithm approaches the optimal solution more effectively than the simulated annealing and genetic algorithm.

유전자 알고리즘을 이용한 확장성 있고 빠른 경로 재탐색 알고리즘

이정규,김선호,양지훈,Lee, Jung-Kyu,Kim, Seon-Ho,Yang, Ji-Hoon 한국정보처리학회 2011 정보처리학회논문지B Vol.18 No.3

본 논문은 유전자 알고리즘을 이용해서 동적으로 변하는 네트워크상에서 빠르게 최단 경로를 재탐색할 수 있는 알고리즘을 제안한다. 제안 알고리즘은 다익스트라 알고리즘과 유전자 알고리즘을 통합한 형식의 알고리즘이다. 이 제안 알고리즘은 최초 탐색 시 다익스트라(Dijkstra) 알고리즘을 이용해서 유전자 알고리즘의 초기화 과정을 용이하게 하는 선행자 배열을 정의한다. 그 후 유전자 알고리즘은 적절한 유전 연산자를 통해 동적으로 변하는 트래픽 상황에서 최적의 경로를 재탐색한다. 실험 결과를 통해 제안 알고리즘이 거대한 네트워크 데이터에 대해서 다른 유전자 알고리즘 기반의 최단경로 찾기 알고리즘이나 다익스트라 알고리즘보다 적은 계산시간으로 더 짧은 주행시간의 경로를 제시한다는 것을 보였다. This paper presents a fast and scalable re-routing algorithm that adapts to dynamically changing networks. The proposed algorithm integrates Dijkstra's shortest path algorithm with the genetic algorithm. Dijkstra's algorithm is used to define the predecessor array that facilitates the initialization process of the genetic algorithm. After that, the genetic algorithm re-searches the optimal path through appropriate genetic operators under dynamic traffic situations. Experimental results demonstrate that the proposed algorithm produces routes with less traveling time and computational overhead than pure genetic algorithm-based approaches as well as the standard Dijkstra's algorithm for large-scale networks.

유전자 알고리즘을 이용한 포장층 탄성계수 역해석 기법 개발 : Part Ⅰ : GA 연산자 선정

박성완(Park Seong Wan),박희문(Park Hee Mun),황정준(Hwang Jung Joon) 대한토목학회 2007 대한토목학회논문집 D Vol.27 No.4D

효율적인 포장관리를 위해서는 공용중인 아스팔트 포장의 구조적 적정성 평가를 위한 포장층 탄성계수의 정확한 추정이 필요하며, 이를 위하여 현재 FWD(Falling Weight Deflectometers)를 가장 널리 많이 사용하고 있다. 본 연구에서는 FWD로부터 얻은 표면 처짐 값을 이용하여 포장구조체의 각층 탄성계수 추정을 위한 GAPAVE 프로그램의 효율적인 운용 방법에 대해 연구하였다. 본 연구에서 개발된 GAPAVE 프로그램은 유한요소 구조해석과 유전자 알고리즘을 기반으로 한 역해석 프로그램이다. 기존에 제시된 유전자 알고리즘 연산자를 기준으로 역해석 결과에 미치는 연산자의 민감도를 분석한 결과로 부터 포장구조체의 구조 및 강성 조건에 따라 최적의 연산자 값이 변함을 알 수 있으며 이를 위해 포장구조체의 조건에 따른 최적의 유전자 알고리즘 연산자 선정 절차와 세부적인 연산자 선정 범위를 본 연구에서 제시하였다. It is important to predict the structural adequacies of asphalt pavements in service for the efficient pavement management using the falling weight deflectometer (FWD). The purpose of this study is to present the procedure for backcalculating the layer moduli using the FWD deflections and GAPAVE program. The GAPAVE, backcalculation program for layer moduli, developed in this study is based on finite element structural analysis and genetic algorithm. From the sensitivity analysis results, the genetic algorithm parameters are affected by structural and stiffness conditions of pavements. For more accurate backcalculation, the optimized genetic algorithm parameters need to be selected at each pavement condition. This study proposes the procedure for the selection of GA parameters and the reasonable ranges of GA parameters.

지식기반 유전자알고리즘을 이용한 한국인 빈발 HLA 대립유전자에 대한 결합 펩타이드 예측

조연진 ( Yeon-jin Cho ),오흥범 ( Heung-bum Oh ),김현철 ( Hyeoncheol Kim ) 한국인터넷정보학회 2012 인터넷정보학회논문지 Vol.13 No.4

감염된 미생물에서 유래한 단백질 펩타이드가 HLA에 결합하여 숙주의 세포표면에 제시되면, T 세포가 이를 인식하여 면역반응을 유발함으로써 감염원을 제거하게 된다. HLA와 펩타이드간의 결합이 안정적일수록 T 세포반응이 강하게 일어나 효율적으로 감염원을 제거할 수 있다고 알려져 있다. 따라서 특정 HLA에 안정적으로 결합할 수 있는 펩타이드(HLA binder)를 찾아낼 수 있다면 감염질환이나 암의 예방을 위한 펩타이드 백신의 개발에 활용될 수 있다. 그런데 HLA는 매우 다형하기 때문에 하나의 집단 내에서도 어느 정도의 빈도를 가지는 대립유전자의 수가 매우 많다. 따라서 이들 모든 대립유전자들에 대해 가능한 펩타이드조합을 제작한 후 직접 실험을 통해 안정적으로 결합하는 펩타이드를 찾아내는 것은 매우 비효율적이다. 이를 극복하기 위하여 특정 HLA에 안정적으로 결합하는 펩타이드를 예측하는 정보전산적인 방법이 최근 개발되어 왔다. 이들 방법을 통해 제시된 펩타이드에 대해서만 직접 생물학적 실험을 시행함으로써 연구자는 검증해야 할 후보 펩타이드의 수를 현격히 감소시킬 수 있게 된다. 본 논문에서는 HLA 결합 펩타이드 예측을 위해 기계학습을 이용한 방법을 소개할 뿐만 아니라, 지금까지 HLA 결합 펩타이드 예측에 시도된 적이 없는 `지식기반 유전자알고리즘(knowledge-based genetic algorithm)`이라는 새로운 모델을 제시하고자 한다. 이것은 유전자알고리즘(GA)에 기반한 것이었지만 전문가 지식을 접목함으로써 GA보다 더 향상된 성능으로 한국인에 흔한 HLA에 결합하는 펩타이드를 예측하였다. 뿐만 아니라 이것은 결합하는 펩타이드의 규칙을 한국인에 흔한 HLA 대립유전자에 대하여 추출해 줄 수 있는 새로운 방법이었다. T cells induce immune responses and thereby eliminate infected micro-organisms when peptides from the microbial proteins are bound to HLAs in the host cell surfaces, It is known that the more stable the binding of peptide to HLA is, the stronger the T cell response gets to remove more effectively the source of infection. Accordingly, if peptides (HLA binder) which can be bound stably to a certain HLA are found, those peptieds are utilized to the development of peptide vaccine to prevent infectious diseases or even to cancer. However, HLA is highly polymorphic so that HLA has a large number of alleles with some frequencies even in one population. Therefore, it is very inefficient to find the peptides stably bound to a number of HLAs by testing random possible peptides for all the various alleles frequent in the population. In order to solve this problem, computational methods have recently been developed to predict peptides which are stably bound to a certain HLA. These methods could markedly decrease the number of candidate peptides to be examined by biological experiments. Accordingly, this paper not only introduces a method of machine learning to predict peptides binding to an HLA, but also suggests a new prediction model so called `knowledge-based genetic algorithm` that has never been tried for HLA binding peptide prediction. Although based on genetic algorithm (GA). it showed more enhanced performance than GA by incorporating expert knowledge in the process of the algorithm. Furthermore, it could extract rules predicting the binding peptide of the HLA alleles common in Koreans.

무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 population 초기화 방법에 관한 연구

홍성삼(Sung-Sam Hong),한명묵(Myung-Mook Han),최혁진(Hyuk-Jin Choi),문창민(Chang-Min Mun) 한국지능시스템학회 2012 한국지능시스템학회논문지 Vol.22 No.5

무기할당 문제(Weapon Target Allocation : WTA)는 전형적인 NP-Complete 문제로 공중에서 위협하는 표적에 대해 아군의 무기를 적절히 할당하는 문제이다. 이러한 NP-Complete 문제들은 주로 휴리스틱 알고리즘을 이용하여 최적해를 찾는다. 유전자 알고리즘은 대표적인 휴리스틱 알고리즘으로 다양한 도메인에서 우수한 성능을 보여주는 휴리스틱 알고리즘이다. 유전자 알고리즘의 단계 중에 population 초기화는 최초 염색체를 결정하는 문제로 유전자 알고리즘의 해의 질을 높일 수 있고, 탐색 성능을 높일 수 있으나 많은 연구가 이루어지고 있지 않는 분야이다. 따라서 본 논문에서는 WTA 문제를 해결하기 위해 유전자 알고리즘의 성능을 향상시키기 위한 population 초기화 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 초기화할 때 WTA 문제 도메인의 특성을 반영하고, 우성유전자를 상속받는다. 또한, 문제 공간에서의 탐색 공간을 넓게 선정하여 질이 좋은 해를 효율적으로 찾을 수 있도록 하였다. 본 논문에서는 제안하는 알고리즘과 다른 알고리즘과의 다양한 속성의 비교분석 및 실험을 통해 성능을 분석하여 제안하는 알고리즘의 우수성을 검증하였다. 실험 결과 제안하는 알고리즘이 WTA 문제 해결에서 다른 방법들에 비해 좋은 성능을 보였다. 특히, 제안하는 알고리즘은 문제 상황에 따라 RMI 수치를 조정하여 적응성 있게 적용할 수 있기 때문에, 문제의 상황이 다양한 WTA 문제 도메인에 적용하기 적합한 알고리즘이다. The Weapon Target Allocation(WTA) problem is the NP-Complete problem. The WTA problem is that the threatful air targets are assigned by weapon of allies for killing the targets. A good solution of NP-complete problem is heuristic algorithms. Genetic algorithms are commonly used heuristic for global optimization, and it is good solution on the diverse problem domain. But there has been very little research done on the generation of their initial population. The initialization of population is one of the GA step, and it decide to initial value of individuals. In this paper, we propose to the population initialization method to improve a Genetic Algorithm. When it initializes population, the proposed algorithm reflects the characteristics of the WTA problem domain, and inherits the dominant gene. In addition, the search space widely spread in the problem space to find efficiently the good quality solution. In this paper, the proposed algorithm to verify performance examine that an analysis of various properties and the experimental results by analyzing the performance compare to other algorithms. The proposed algorithm compared to the other initialization methods and a general genetic algorithm. As a result, the proposed algorithm showed better performance in WTA problem than the other algorithms. In particular, the proposed algorithm is a good way to apply to the variety of situation WTA problem domain, because the proposed algorithm can be applied flexibly to WTA problem by the adjustment of RMI.

임베디드 하드웨어 유전자 알고리즘을 위한 실시간 처리 시스템

박세현,서기성,Park Se-hyun,Seo Ki-sung 한국정보통신학회 2004 한국정보통신학회논문지 Vol.8 No.7

A real-time processing system for embedded hardware genetic algorithm is suggested. In order to operate basic module of genetic algorithm in parallel, such as selection, crossover, mutation and evaluation, dual processors based architecture is implemented. The system consists of two Xscale processors and two FPGA with evolvable hardware, which enables to process genetic algorithm efficiently by distributing the computational load of hardware genetic algorithm to each processors equally. The hardware genetic algorithm runs on Linux OS and the resulted chromosome is executed on evolvable hardware in FPGA. Furthermore, the suggested architecture can be extended easily for a couple of connected processors in serial, making it accelerate to compute a real-time hardware genetic algorithm. To investigate the effect of proposed approach, performance comparisons is experimented for an typical computation of genetic algorithm. 임베디드 하드웨어 유전자 알고리즘을 위한 실시간 처리 시스템을 설계하였다. 제안된 시스템은 유전자 알고리즘의 기본 모듈인 selection, crossover, 및 mutation과 evaluation을 병행적으로 동작시키기 위해서 이중 프로세서로 구현하였다. 구현된 시스템은 두개의 Xscale 프로세서와 진화 하드웨어가 내장된 FPGA 로 구성되었다. 또한 본 시스템은 유전자 알고리즘의 기본 모듈 수행이 두 개의 프로세서에 자동으로 균등 배분되는 구조를 지니고 있어, 유전자 알고리즘 처리의 효율성을 극대화 할 수 있다. 제안된 임베디드 하드웨어 유전자 알고리즘 처리 시스템은 임베디드 리눅스 운영체제에서 수행되며 진화 하드웨어에서 실시간으로 처리된다. 또한 제안된 이중 프로세서의 각 프로세서 모듈은 동일한 구조로 가지고 있으므로 여러 개의 모듈을 직렬 연결하여 빠른 하드웨어 유전자 알고리즘 실시간 처리에 그대로 사용될 수 있다.

중심합성계획법 기반 이중유전자알고리즘을 활용한 차량추종모형 정산방법론 개발

배범준,임현섭,소재현 한국ITS학회 2019 한국ITS학회논문지 Vol.18 No.2

미시적 교통류 모형의 정산은 시뮬레이션 분석에 있어 매우 중요한 요소이다. 유전자 알고리즘은 교통류 모형의 정산에 널리 활용되어 왔으며, 일반적으로 이러한 최적화 문제에 있어높은 효율성을 보이는 것으로 알려져 있다. 하지만 제한된 시간내에 신속한 의사결정을 위한시뮬레이션 분석에 있어 유전자알고리즘의 모형 정산속도는 여전히 느리다. 이에 본 연구에서는 정산 효율 향상을 위해 중심합성계획법 기반의 이중유전자알고리즘을 활용한 차량추종모형 정산방법론을 개발하였다. 개발된 정산 방법론에서는 실험계획법 중 하나인 중심합성계획법과 유전자알고리즘을 결합하여 준최적해를 찾고, 이를 다시 유전자알고리즘의 초기 값으로하여 모형 파라미터의 최적해를 찾는다. 개발된 방법을 활용하여 Gipps의 차량추종모형을 정산하였다. 선행연구에서 사용된 단일 유전자알고리즘을 활용한 방법과 비교한 결과, 본 연구에서 개발한 방법이 더 짧은 시간내에 최적해를 찾는 것으로 확인되었다. 개발된 방법론은 유전자알고리즘을 사용하는 다양한 교통분석에 활용될 수 있을 것으로 기대된다. The calibration of microscopic traffic simulation models has received much attention in the simulation field. Although no standard has been established for it, a genetic algorithm (GA) has been widely employed in recent literature because of its high efficiency to find solutions in such optimization problems. However, the performance still falls short in simulation analyses to support fast decision making. This paper proposes a new calibration procedure using a dual GA and central composite design (CCD) in order to improve the efficiency. The calibration exercise goes through three major sequential steps: (1) experimental design using CCD for a quadratic response surface model (RSM) estimation, (2) 1st GA procedure using the RSM with CCD to find a near-optimal initial population for a next step, and (3) 2nd GA procedure to find a final solution. The proposed method was applied in calibrating the Gipps car-following model with respect to maximizing the likelihood of a spacing distribution between a lead and following vehicle. In order to evaluate the performance of the proposed method, a conventional calibration approach using a single GA was compared under both simulated and real vehicle trajectory data. It was found that the proposed approach enhances the optimization speed by starting to search from an initial population that is closer to the optimum than that of the other approach. This result implies the proposed approach has benefits for a large-scale traffic network simulation analysis. This method can be extended to other optimization tasks using GA in transportation studies.

국부적 향상을 이용한 복합 유전자 알고리즘 : GA + 셀룰러 학습 GA + Cellular Learning

고명숙,김주연 부천대학 2001 論文集 Vol.22 No.-

진화 이론에 의하면 진화 과정 중 모집단에 속하는 가장 적합한 개체들만이 그 다음 세대에도 생존할 수 있으며 각 개체는 생명 주기 동안에 적응 능력을 학습하며 그 유전적 형질들이 다음 세대에도 보존됨을 알 수 있다. 또한 생명 주기동안에 학습된 특질들은 그 다음 세대에서 다시 학습할 필요가 없다. 이러한 경험 획득 과정을 학습(learning)이라 부르며 일반적으로 유전자 알고리즘에서는 국부 탐색(local search)을 통하여 학습이 이루어진다. 유전자 알고리즘은 복잡한 상태 공간상에서 최적의 해를 찾기 위해 유향성 임의 탐색을 행하는 전통적인 최적화 알고리즘이다. 이 논문에서는 함수 최적화를 위해 학습 속도를 개선한 셀롤러 학습을 기반으로 하는 유전자 알고리즘을 제안한다. 복합 유전자 알고리즘은 기존의 유전자 알고리즘과 국부 탐색 기법을 혼합시킴으로써 최적해로의 수렴률을 향상시킨 방법이다. 제안하는 셀롤러 학습 전략은 셀롤러 오토마타의 주기성과 수렴성을 기반으로 한다. 유기체가 그 개체의 생명 주기의 한 세대에서 얻게되는 지식과 경험들을 자손에게 전달한다는 이론을 바탕으로 한다. 분석적인 실험을 통하여 제한한 학습 전략이 기존의 방법보다 더 빨리 전역 최적 해를 찾을 수 있음을 증명하였다. 셀롤러 학습을 이용한 복합 유전자 알고리즘은 전역 최적해로의 수렴 속도를 향상시킨 최적화 알고리즘이다. According to evolutionary theories, only the most suited individuals in a population are likely to survive and individuals learn to adapt significantly during their lifetime, and thus transmitting their biologocal heredity to new generations. Genetic Algorithms are traditional optimization techniques using directed random searches to locate optimal solutions in complex landscapes. This paper proposes a genetic algorithm based Cellular Learning with accelerated learning capability for function optimization. A Hybrid genetic algorithm combines local search with a more traditional genetic algorithm and it can be improved in convergent to optimum. Proposed Cellular Learning strategy is based on periodic and convergent behaviors in cellular automata, and on the theory of transmitting to offspring the knowledge and experience that organisms acquire in their lifetime. We demonstrated through analytical experiments that the proposed cellular learning strategy could find the global opyimum faster than conventional learning strategies. The hybrid genetic algorithm based on cellular learning is an optimization algorithm that is capable of accelerating convergence speed to global optimum.