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

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

유전알고리즘을 활용한 조망분석 최적화에 따른 볼륨 계획에 관한 연구

김범진 ( Kim Beomjim ),김용성 ( Kim Yongseong ),송석재 ( Song Seokjae ) 한국공간디자인학회 2023 한국공간디자인학회논문집 Vol.18 No.8

(연구 배경 및 목적) 디지털 건축설계 분야에서 파라메트릭 디자인의 알고리즘 기반 최적화 툴의 도입은 설계 방식에 있어 과학적 객관성을 가지는 새로운 설계 방법의 가능성을 보여준다. 이는 디지털 3차원 공간에서의 가상환경과 환경분석 시뮬레이션을 통해 이루어지고 있다. 가상공간에 구축된 환경에서 수행한 환경분석 시뮬레이션의 결과를 현실 세계의 설계에 반영하므로 과학적 객관성을 갖춘 설계안을 만들 수 있다. 이러한 방식은 지자체에서도 3D 공간정보 서비스를 구축하여 도시 계획을 수립하거나, 일조권 및 조망권을 확인하는 방식으로 이용하고 있다. 본 연구에서는 송정해수욕장 재개발 대상지를 국토정보 플랫폼의 수치지형도 데이터를 통해 Rhino Grasshopper의 알고리즘으로 디지털 3차원 공간의 가상환경에 구축하여, 유전알고리즘을 활용해 관광지인 송정해수욕장에 최대의 바다 조망을 얻을 수 있는 최적 매스 디자인 방법을 제안한다. 본 연구에서 말하는 최적의 바다 조망은 가시영역 이론에 근거해 조망도 값으로 수치화한 것을 말하며, 값이 클수록 넓은 바다 조망을 확보한다. 건축한계선 내에서 건폐율, 용적률의 조건을 충족하면서 높은 조망도를 갖는 매스 디자인을, 유전알고리즘을 활용해 찾고 정량적 분석을 통해 도출한 결과의 객관적 신뢰성을 판단하는 데 목적을 둔다. (연구 방법) 유전알고리즘의 활용은 Rhino Grasshopper의 환경분석 시뮬레이션 Add-On인 DecodingSpace로 알고리즘을 형성하고, 유전 알고리즘 기반 최적화 Add-On인 Wallacei를 통해 유전 알고리즘을 진행한다. 여기서 다목적 최적화 문제에 활용되는 유전 알고리즘의 NSGA-II 알고리즘을 이용해 최대의 바다 조망을 얻을 수 있는 매스 디자인을 찾고, 도출된 결과는 K-Means 알고리즘을 통해 도출된 데이터와 비교 분석하는 과정을 통해 정량적으로 평가하여 결과값의 신뢰성을 판단한다. (결과) 도출된 최적해는 건폐율 19.95%, 용적률 349.23%로 건폐율의 한계인 20%, 용적률의 한계인 350%에서 1% 미만의 차이를 두고 계획되었다. 도출된 조망도는 177.73으로 0순위를 포함해 총 1,500개의 데이터 모델 중 60번째로 높은 조망도 값을 가진다. 이는 생성된 데이터 모델 중 상위 4%에 해당한다. 최적해는 Fitness Rank에서 우수한 결과를 보이고 있을 뿐 아니라, 건폐율과 용적률에서도 높은 수치를 기록하고 있다. 종합적인 결과를 고려할 때, 최적해가 다른 Cluster Centroid 들보다 더 뛰어나며, 가장 최적의 선택으로 평가된다. (결론) 해당 연구에서는 유전 알고리즘을 활용하여 송정 해수욕장 재개발 대상지의 조망 분석 매스 디자인을 위해 파라메트릭 디자인과 유전 알고리즘을 결합하여 최대의 바다 조망을 얻을 수 있는 매스 디자인 방법을 제안했다. 본 연구는 이후 진행될 프로젝트에 있어 좋은 조망을 갖는 지역에서 선택된 조망을 충분히 확보할 수 있는 매스 디자인 방법론을 제안한다는 점에 가치가 있다. 하지만 국토 정보 플랫폼의 3차원 공간 정보를 통해 형성한 디지털 3차원 공간이 현실 공간을 완벽하게 반영하지 못하며, 매스 디자인에 있어 매스의 수평 투영면을 Z값으로 Extrude하여 사각기둥을 형성해 만든 단순한 형태의 매스 디자인이라는 점에 본 연구의 한계가 존재하며, 후속 연구에 있어서는 사각 기둥의 형태가 아닌 비정형의 매스 디자인 형성에 대한 연구가 필요하다. (Background and Purpose) Algorithm-based optimization tools in digital architectural design present new possibilities for scientifically objective design methods. By simulating a virtual environment and conducting an environmental analysis in a digital three-dimensional space, design plans with scientific objectivity can be developed. This approach, often used by local governments for urban planning and 3D spatial information services, was applied in this study to propose an optimal mass design method for maximizing sea views at the Songjeong Beach redevelopment site, a popular tourist destination. Using Rhino Grasshopper’s algorithm and digital topographic map data from the national land information platform, a virtual environment was created to implement a genetic algorithm. This study focused on obtaining a numerical value for the optimal sea view based on the theory of visible areas, aiming to find mass designs with high views while adhering to the building and floor area ratio constraints within the building limits. The objective reliability of the results was assessed through quantitative analysis. (Method) The genetic algorithm, formulated using Rhino Grasshopper’s environmental analysis simulation Add-On DecodingSpace, was executed using Wallacei, an optimization tool based on the genetic algorithm. Specifically, the NSGA-II genetic algorithm, designed for multipurpose optimization problems, was employed to identify a mass design that achieved maximum sea view. A quantitative evaluation of the derived results was performed using data from the K-means algorithm to ensure reliability. (Results) The optimal solution, planned with a difference of less than 1% from the dry-opening ratio limit of 19.95% and floor area ratio of 349.23%, yielded a view of 177.73. This ranks 60th among a total of 1,500 data models, including 0th place, placing it in the top 4%. The optimal solution not only excels in the Fitness Rank but also records high values for the dry-opening ratio and floor area ratio. Considering the overall results, the optimal solution surpasses the other Cluster Centroids and is deemed the optimal choice. (Conclusion) This study proposes a mass design method that maximizes sea views through a combination of parametric design and a genetic algorithm for a Songjeong Beach redevelopment site. This study introduced a valuable methodology for securing ample views in areas with promising prospects for future projects. However, the digital three-dimensional space formed through the national land information platform does not fully represent the real space. The limitation of this study is its simplistic mass design approach, which forms square columns by extruding a horizontal projection surface with a Z value. Future research should explore atypical mass designs rather than adhering to a square column structure.

유전알고리즘을 활용한 조망분석 최적화에 따른 볼륨 계획에 관한 연구

김범진,김용성,송석재 한국공간디자인학회 2023 한국공간디자인학회논문집 Vol.18 No.8

(Background and Purpose) Algorithm-based optimization tools in digital architectural design present new possibilities for scientifically objective design methods. By simulating a virtual environment and conducting an environmental analysis in a digital three-dimensional space, design plans with scientific objectivity can be developed. This approach, often used by local governments for urban planning and 3D spatial information services, was applied in this study to propose an optimal mass design method for maximizing sea views at the Songjeong Beach redevelopment site, a popular tourist destination. Using Rhino Grasshopper’s algorithm and digital topographic map data from the national land information platform, a virtual environment was created to implement a genetic algorithm. This study focused on obtaining a numerical value for the optimal sea view based on the theory of visible areas, aiming to find mass designs with high views while adhering to the building and floor area ratio constraints within the building limits. The objective reliability of the results was assessed through quantitative analysis. (Method) The genetic algorithm, formulated using Rhino Grasshopper’s environmental analysis simulation Add-On DecodingSpace, was executed using Wallacei, an optimization tool based on the genetic algorithm. Specifically, the NSGA-II genetic algorithm, designed for multipurpose optimization problems, was employed to identify a mass design that achieved maximum sea view. A quantitative evaluation of the derived results was performed using data from the K-means algorithm to ensure reliability. (Results) The optimal solution, planned with a difference of less than 1% from the dry-opening ratio limit of 19.95% and floor area ratio of 349.23%, yielded a view of 177.73. This ranks 60th among a total of 1,500 data models, including 0th place, placing it in the top 4%. The optimal solution not only excels in the Fitness Rank but also records high values for the dry-opening ratio and floor area ratio. Considering the overall results, the optimal solution surpasses the other Cluster Centroids and is deemed the optimal choice. (Conclusion) This study proposes a mass design method that maximizes sea views through a combination of parametric design and a genetic algorithm for a Songjeong Beach redevelopment site. This study introduced a valuable methodology for securing ample views in areas with promising prospects for future projects. However, the digital three-dimensional space formed through the national land information platform does not fully represent the real space. The limitation of this study is its simplistic mass design approach, which forms square columns by extruding a horizontal projection surface with a Z value. Future research should explore atypical mass designs rather than adhering to a square column structure. (연구 배경 및 목적) 디지털 건축설계 분야에서 파라메트릭 디자인의 알고리즘 기반 최적화 툴의 도입은 설계 방식에 있어 과학적 객관성을 가지는 새로운 설계 방법의 가능성을 보여준다. 이는 디지털 3차원 공간에서의 가상환경과 환경분석 시뮬레이션을 통해 이루어지고 있다. 가상공간에 구축된 환경에서 수행한 환경분석 시뮬레이션의 결과를 현실 세계의 설계에 반영하므로 과학적 객관성을 갖춘 설계안을 만들 수 있다. 이러한 방식은 지자체에서도 3D 공간정보 서비스를 구축하여 도시 계획을 수립하거나, 일조권 및 조망권을 확인하는 방식으로 이용하고 있다. 본 연구에서는 송정해수욕장 재개발 대상지를 국토정보 플랫폼의 수치지형도 데이터를 통해 Rhino Grasshopper의 알고리즘으로 디지털 3차원 공간의 가상환경에 구축하여, 유전알고리즘을 활용해 관광지인 송정해수욕장에 최대의 바다 조망을 얻을 수 있는 최적 매스 디자인 방법을 제안한다. 본 연구에서 말하는 최적의 바다 조망은 가시영역 이론에 근거해 조망도 값으로 수치화한 것을 말하며, 값이 클수록 넓은 바다 조망을 확보한다. 건축한계선 내에서 건폐율, 용적률의 조건을 충족하면서 높은 조망도를 갖는 매스 디자인을, 유전알고리즘을 활용해 찾고 정량적 분석을 통해 도출한 결과의 객관적 신뢰성을 판단하는 데 목적을 둔다. (연구 방법) 유전알고리즘의 활용은 Rhino Grasshopper의 환경분석 시뮬레이션 Add-On인 DecodingSpace로 알고리즘을 형성하고, 유전 알고리즘 기반 최적화 Add-On인 Wallacei를 통해 유전 알고리즘을 진행한다. 여기서 다목적 최적화 문제에 활용되는 유전 알고리즘의 NSGA-II 알고리즘을 이용해 최대의 바다 조망을 얻을 수 있는 매스 디자인을 찾고, 도출된 결과는 K-Means 알고리즘을 통해 도출된 데이터와 비교 분석하는 과정을 통해 정량적으로 평가하여 결과값의 신뢰성을 판단한다. (결과) 도출된 최적해는 건폐율 19.95%, 용적률 349.23%로 건폐율의 한계인 20%, 용적률의 한계인 350%에서 1% 미만의 차이를 두고 계획되었다. 도출된 조망도는 177.73으로 0순위를 포함해 총 1,500개의 데이터 모델 중 60번째로 높은 조망도 값을 가진다. 이는 생성된 데이터 모델 중 상위 4%에 해당한다. 최적해는 Fitness Rank에서 우수한 결과를 보이고 있을 뿐 아니라, 건폐율과 용적률에서도 높은 수치를 기록하고 있다. 종합적인 결과를 고려할 때, 최적해가 다른 Cluster Centroid 들보다 더 뛰어나며, 가장 최적의 선택으로 평가된다. (결론) 해당 연구에서는 유전알고리즘을 활용하여 송정 해수욕장 재개발 대상지의 조망 분석 매스 디자인을 위해 파라메트릭 디자인과 유전 알고리즘을 결합하여 최대의 바다 조망을 얻을 수 있는 매스 디자인 방법을 제안했다. 본 연구는 이후 진행될 프로젝트에 있어 좋은 조망을 갖는 지역에서 선택된 조망을 충분히 확보할 수 있는 매스 디자인 방법론을 제안한다는 점에 가치가 있다. 하지만 국토 정보 플랫폼의 3차원 공간 정보를 통해 형성한 디지털 3차원 공간이 현실 공간을 완벽하게 반영하지 못하며, 매스 디자인에 있어 매스의 수평투영면을 Z값으로 Extrude하여 사각기둥을 형성해 만든 단순한 형태의 매스 디자인이라는 점에 본 연구의 한계가 존재하며, 후속 연구에 있어서는 사각 기둥의 형태가 아닌 비정형의 매스 디자인 형성에 대한 연구가 필요하다.

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

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

유전자 알고리즘에 의한 우수 유전자형 선별

이제영,고진영,Lee, Jae-Young,Goh, Jin-Young 한국데이터정보과학회 2009 한국데이터정보과학회지 Vol.20 No.4

컴퓨터공학의 발전으로 인해, 여러 개의 변수가 존재하는 비선형 문제와 같은 최적해 탐색과 최적화에 사용되는 유전자 알고리즘은 많은 분야에서 활발하게 응용되고 있다. 그 중, 데이터마이닝분야에서 유전자 알고리즘을 이용하여 정확도를 최대로 하는 입력변수 선택방법과 여러 예측모형을 통합하는 방법 등이 제시되었다. 한편, 우리나라 축산업을 대표하는 한우의 유전자원 보존과 능력향상을 위해서는 다음세대에 유전이 되는 단일염기다형성에서 특정 유전자형을 가진 한우가 경제형질이 우수한지를 찾아낼 필요가 있다. 이에 따라, 유전자 알고리즘을 이용하여 한우의 경제형질에 가장 많은 영향을 주는 단일염기다형성 조합마커의 유전자형을 선택하는 방법을 제시하였다. 그리고 실제 한우 유전 데이터에 적용하여 주요 단일염기다형성 조합마커에서 우수 유전자형들을 선별하였다. From development of computer science, genetic algorithm has been applied to many fields for search like non-linear problem based on various variables and optimization process. Among others, in the data mining field, there are methods to select the best input variables for model accuracy and various predict models which were merged by using the genetic algorithm. In the meantime, to improve and preserve quality of the Hanwoo (Korean cattle) which is represented the agricultural industry in our country, we need to find out outstanding economical traits of Hanwoo in having specific genotype of single nucleotide polymorphism (SNP) which is inherited to next generation. According to, This research proposed the selecting method to find genotype of SNPs marker which affects economical traits of the Hanwoo by using the genetic algorithm. And we selected the best genotypes of the principal SNPs marker by applying to real data on Hanwoo genetic.

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

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

퍼지 논리를 이용한 병렬 유전 알고리즘

안영화,권기호,An Young-Hwa,Kwon Key-Ho 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.1

유전 알고리즘은 자연 선택과 유전적 성질에 기반을 둔 알고리즘으로 기존 방법으로는 쉽게 해결할 수 없는 어려운 문제에서도 성공적으로 적용되었다. 기존의 유전 알고리즘은 해 집단이 큰 경우 시간이 많이 걸리는 문제점이 있다. 병렬 유전 알고리즘은 이러한 문제를 해결하기 위하여 제안된 기존의 유전 알고리즘의 확장이라 할 수 있다. 병렬 유전 알고리즘에서 중요한 요소는 이주와 유전 연산으로 이를 적절하게 설계함으로서 좋은 결과를 얻을 수 있다. 본 논문에서는 퍼지 논리를 이용하여 기존의 병렬 유전 알고리즘을 개선하고자 한다. Genetic algorithms(GA), which are based on the idea of natural selection and natural genetics, have proven successful in solving difficult problems that are not easily solved through conventional methods. The classical GA has the problem to spend much time when population is large. Parallel genetic algorithm(PGA) is an extension of the classical GA. The important aspect in PGA is migration and GA operation. This paper presents PGAs that use fuzzy logic. Experimental results show that the proposed methods exhibit good performance compared to the classical method.

비디오 스트리밍 서버에서의 유전 알고리즘을 활용한 사용자 인기도 기반 데이터 배치 기법

이다영,송민석 한국차세대컴퓨팅학회 2018 한국차세대컴퓨팅학회 논문지 Vol.14 No.4

동적 적응 스트리밍 (Dynamic Adaptive Streaming over HTTP (DASH)) 서버는 트랜스코딩된 다양한 비트 율의 비디오 세그먼트를 저장해야 하기 때문에, 스토리지 요구량을 줄이는 것이 매우 중요하다. 본 논문에서는 비디 오 스트리밍 서버에서의 유전 알고리즘을 활용한 사용자 인기도 기반 데이터 배치 기법을 제안한다. 우리는 트랜스 코딩된 다양한 버전의 비디오 세그먼트들 중에서 어떤 버전을 저장하고, 어떻게 세그먼트를 디스크들에 분산시킬 지 에 대한 문제를 정의하고, 유전 알고리즘을 이용한 시뮬레이션 모델을 개발하였다. 이를 위해서 유전 알고리즘의 개 체군의 크기, 선택 비율, 교배 비율, 돌연변이 비율을 설정하기 위한 실험을 진행하였으며, 유전 알고리즘의 결과와 최적값을 비교하여 본 기법의 신뢰성을 확인했다. It is important to reduce the growing storage requirements of dynamic adaptive streaming over HTTP(DASH) servers that need to store transcoded video segments of various bit rates. In this paper, we propose a new genetic algorithm techniques for popularity-aware data placement in video streaming servers. We defined the popularity-aware data placement problem that chooses and places video segments on each disk. We designed and implemented a simulation model to solve this problem using a genetic algorithm. Experiments were carried out to set the population size, selection rate, crossover rate and mutation rate. We compared the results of the genetic algorithm with the optimum value to confirm the reliability of this technique.

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

이정규,김선호,양지훈,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.

의사결정 모델을 위한 염색체 비분리를 적용한 가변 염색체 유전 알고리즘

박강문,신석훈,지승도,Park, Kang-Moon,Shin, Suk-Hoon,Chi, Sung-Do 한국시뮬레이션학회 2017 한국시뮬레이션학회 논문지 Vol.26 No.4

The Genetic Algorithm(GA) is a global search algorithm based on biological genetics. It is widely used in various fields such as industrial applications, artificial neural networks, web applications and defense industry. However, conventional Genetic Algorithm has difficulty maintaining feasibility in complicated situations due to its fixed number of chromosomes. This study proposes the Genetic Algorithm using variable chromosome with chromosome attachment. And in order to verify the implication of changing number of chromosomes in the simulation, it applies the Genetic Algorithm using variable chromosome with chromosome attachment to antisubmarine High Value Unit(HVU) escort mission simulation. As a result, the Genetic Algorithm using variable chromosome has produced complex strategies faster than the conventional method, indicating the increase of the number of chromosome during the process. 유전 알고리즘은 생물 유전학에 기본 이론을 두는 전역 탐색 알고리즘으로, 산업, 뉴럴 네트워크, 웹, 그리고 국방 등의 분야에서 활발히 사용되고 있다. 하지만 기존의 유전 알고리즘은 염색체의 개수가 고정되어 있는 형태여서 시뮬레이션 도중 초기에 주어진 상황보다 더 복잡한 상황이 주어질 수 있는 경우에는 적용이 힘들다는 한계점이 존재한다. 본 연구에서는 이를 극복하기 위해서 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 제안하였다. 그리고 염색체 수의 변화가 시뮬레이션 결과에 영향을 미치는 것을 확인하기 위하여 대 잠수함 HVU 호위 임무 시뮬레이션에 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 적용하였다. 시뮬레이션 결과 기존의 유전 알고리즘과는 달리 가변 염색체 유전 알고리즘에서는 더 복잡한 전술이 더 일찍 등장하였으며, 그에 따라 염색체 수가 증가하는 방향으로 진화가 일어나는 것을 확인할 수 있었다.