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

서민관(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.

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

송호정(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.

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

이정송(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.

무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 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.

유전자 알고리즘을 이용한 레이저 시스템 최적화

이진호 국제문화기술진흥원 2020 The Journal of the Convergence on Culture Technolo Vol.6 No.4

Genetic algorithm was first introduced to study adaption phenomena occurring in nature based on Darwin’s theory of survival of the fittest. It has been used when analytical approach is not possible because of a large number of variables. In this paper, we demonstrated that genetic algorithm could be used to obtain physically optimized experimental values. We programmed a genetic algorithm that uses a few Gaussian functions to find a given function value and the same algorithm was connected to the laser system to obtain laser pulses of 40fs of maximum pulse width and 1mJ of maximum output power. This study shows that genetic algorithm can be applied to laser systems to obtain the optimized laser pulses. 다윈의 적자생존 이론을 토대로 자연에서 일어나는 적응현상을 연구하기 위해 처음 소개된 유전자 알고리즘은 일반적으로 변수가 많아 기존의 수치 해석적인 방법으로 해를 찾기 힘든 수학적인 최적화된 해를 찾는데 사용되어왔다. 본 논문에서는 물리적인 최적화된 실험값을 얻기 위해 유전자 알고리즘이 적용 될 수 있음을 보였다. 먼저몇 개의 가우시안 함수를 이용하여 주어진 함수 값을 찾는 유전자 알고리즘을 구현 하였고 동일한 알고리즘을 레이저 시스템에 연결하여 최대 40fs펄스 폭과 1mJ의 최대 출력을 갖는 레이저 펄스를 얻을 수 있었다. 본 연구는 유전자 알고리즘을 레이저 시스템에 적용하여 우리가 원하는 레이저 펄스를 얻는데 사용 될 수 있음을 보였다.

유전자 알고리즘 및 패턴 서치 방법을 이용한 풍력 터빈 블레이드의 형상 최적화

이진학(Yi, Jin-Hak),대니 새일(Sale, Danny) 대한토목학회 2012 대한토목학회논문집 A Vol.32 No.6A

이 연구에서는 풍력 터빈 블레이드의 형상 최적화를 위한 직접탐색 기반의 최적화 기법을 적용하고, 최적화 기법간의 성능을 비교하여 효과적인 방법을 제안하고자 하였다. 이를 위하여 수평축 풍력 터빈의 최적설계 코드인 HARP_Opt (Horizontal Axis Rotor Performance Optimizer)을 기반으로 연간 발전량 평가 방법을 수정하고, HARP_Opt에서 적용하고 있는 기존의 유전자 알고리즘과 함께 패턴 서치 방법을 추가 적용하였다. 이를 1㎿급 풍력 발전 터빈 블레이드의 단면 형상 최적 설계 문제에 적용하였으며, 기존의 유전자 알고리즘 및 마이크로 유전자 알고리즘, 그리고 패턴 서치 방법의 성능을 비교한 결과, 연간 발전량과 해의 일관성 면에 있어서는 패턴 서치 방법이 상대적으로 우수하였으며, 계산시간 측면에서는 마이크로 유전자 알고리즘이 상대적으로 우수한 것으로 분석되었다. In this study, direct-search based optimization methods are applied for blade shape optimization of wind turbines and the optimization performances of several methods including conventional genetic algorithm, micro genetic algorithm and pattern search method are compared to propose a more efficient method. For this purpose, the currently available version of HARP_Opt (Horizontal Axis Rotor Performance Optimizer) code is enhanced to rationally evaluate the annual energy production value according to control strategies and to optimize the blade shape using pattern search method as well as genetic algorithm. The enhanced HARP_Opt code is applied to obtain the optimal turbine blade shape for 1MW class wind turbines. The results from pattern search method are compared with the results from conventional genetic algorithm and also micro genetic algorithm and it is found that the pattern search method has a better performance in achieving higher annual energy production and consistent optimal shapes and the micro genetic algorithm is better for reducing the calculation time.

유전자 알고리즘을 이용한 포장층 탄성계수 역해석 기법 개발 : 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.

개선된 유전자 역전파 신경망에 기반한 예측 알고리즘

윤여창,조나래,이성덕 한국데이터정보과학회 2017 한국데이터정보과학회지 Vol.28 No.6

In this study, the problems in the short term stock market forecasting are analyzed and the feasibility of the ARIMA method and the backpropagation neural network is discussed. Neural network and genetic algorithm in short term stock forecasting is also examined. Since the backpropagation algorithm often falls into the local minima trap, we optimized the backpropagation neural network and established a genetic algorithm based on backpropagation neural network for forecasting model in order to achieve high forecasting accuracy. The experiments adopted the korea composite stock price index series to make prediction and provided corresponding error analysis. The results show that the genetic algorithm based on backpropagation neural network model proposed in this study has a significant improvement in stock price index series forecasting accuracy. 본 연구에서는 단기 예측을 위한 자기회귀누적이동평균모형, 역전파 신경망 및 유전자 알고리즘의 결합 적용에 대하여 논의하고 이를 통한 유전자-신경망 알고리즘의 효용성을 살펴본다. 일반적으로 역전파 알고리즘은 지역 최소값에 수렴될 수 있는 단점이 있기 때문에, 여기서는 예측 정확도를 높이기 위해 역전파 신경망 구조를 최적화자고 유전자 알고리즘을 결합한 유전자-신경망 알고리즘 기반 예측모형을 구축한다. 실험을 통한 오차 비교는 KOSPI 지수를 이용한다. 결과는 이 연구에서 제안된 유전자-신경망 모형이 역전파 신경망 모형과 비교할 때 예측 정확도에서 어느 정도 유의한 효율성을 보여주고자 한다.

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

배범준,임현섭,소재현 한국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.