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

김범진,김용성,송석재 한국공간디자인학회 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하여 사각기둥을 형성해 만든 단순한 형태의 매스 디자인이라는 점에 본 연구의 한계가 존재하며, 후속 연구에 있어서는 사각 기둥의 형태가 아닌 비정형의 매스 디자인 형성에 대한 연구가 필요하다.

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

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

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

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

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

유전자알고리즘에서 단성생식과 양성생식을 혼용한 번식을 통한 개체진화 속도향상

정성훈(Sung-Hoon Jung) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.3

본 논문에서는 유전자알고리즘에서 단성생식과 양성생식을 혼용하여 개체진화 속도를 향상시키는 방법에 대하여 제안한다. 단성생식은 암수의 구분이 없는 세균이나 단세포 생물이 두 개의 개체로 분열되는 방법으로 유전적으로 지역적 탐색에 유리하며 양성생식은 암수의 구분이 있는 개체가 만나 생식하는 방법으로 유전적 다양성을 확보하는데 유리하다. 이러한 특성은 유전자알고리즘에서 개체의 진화속도를 향상시키는데 적절히 이용될 수 있다. 본 논문에서는 선택된 개체가 상대적으로 좋은 개체의 경우 진화를 위하여 지역적 탐색을 강화하는 단성생식을 하게 하고 상대적으로 좋지 않은 개체의 경우 유전자의 다양성을 확보하여 전역적 탐색을 강화하는 양성생식을 하게 하였다. 단성생식의 경우 지역적 탐색을 강화하기 위하여 돌연변이 확률을 기존의 유전자알고리즘 보다 낮추었으며 양성생식의 경우 유전자의 다양성 확보를 위하여 돌연변이 확률을 기존의 유전자알고리즘 보다 크게 높였다. 4가지 함수최적화 문제에 적용해본 결과 3개의 함수에서 성능이 매우 좋았으나 전역 최적해가 분산되어 있는 4번째 함수에서는 성능이 좋지 못하였다. 이는 전역최적해가 분산되어 있는 경우 안정적 진화에 혼란을 주기 때문인 것으로 판단된다. This paper proposes a method to accelerate the evolution speed of individuals through hybrid reproduction of monogenesis and gamogenesis. Monogenesis as a reproduction method that bacteria or monad without sexual distinction divide into two individuals has an advantage for local search and gamogenesis as a reproduction method that individuals with sexual distinction mate and breed the offsprings has an advantages for keeping the diversity of individuals. These properties can be properly used for improvement of evolution speed of individuals in genetic algorithms. In this paper, we made relatively good individuals among selected parents to do monogenesis for local search and forced relatively bad individuals among selected parents to do gamogenesis for global search by increasing the diversity of chromosomes. The mutation probability for monogenesis was set to a lower value than that of original genetic algorithm for local search and the mutation probability for gamogenesis was set to a higher value than that of original genetic algorithm for global search. Experimental results with four function optimization problems showed that the performances of three functions were very good, but the performances of fourth function with distributed global optima were not good. This was because distributed global optima prevented individuals from steady evolution.

네크워크 환경의 분산평가 유전자알고리즘

이건명,류근호 한국지능시스템학회 2009 한국지능시스템학회 학술발표 논문집 Vol.19 No.2

유전자 알고리즘의 병렬처리를 위한 방법들로서 모집단을 몇 개의 소집단으로 나누어 각각의 소집단을 진화시키면서 소집단간의 정보교환을 통해 전체 모집단을 진화시키는 것과, 염색체 각각을 프로세서 별로 할당하고 프로세서간의 통신을 통해 유전자알고리즘을 수행하는 것 등이 연구되어왔다. 유전자알고리즘의 수행에 있어서 염색체의 평가에 시간이 많이 요구될 수 있고, 염색체별 평가시간이 상황에 따라 일정하지 않는 경우에 적용할 수 있는 병렬처리 유전자알고리즘으로서, 유전자알고리즘의 기본적인 처리는 하나의 프로세서 또는 시스템에서 수행되지만 각 염색체의 평가는 네트워크를 통해서 연결된 컴퓨터 시스템에 의뢰하여 결과를 얻는 방법을 제안한다. 네트워크 환경에서는 네트워크나 평가를 위임받아 처리하는 시스템이 장애가 있을 수 있고, 또한 염색체의 평가시간에 편차가 심할 수 있기 때문에 동기화된 진화를 시키는 것이 곤란하다. 본 논문에서는 일정비율의 분산된 염색체 평가 결과가 수집되면, 다음 세대로 진화하는 알고리즘을 소개하고, 제안한 방법이 효과적으로 적용될 수 있는 응용분야로서 QSAR(Quantitative Structure-Activity Relationship) 문제를 소개한다.

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

안영화,권기호,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.

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

이제영,고진영,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.

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

박강문,신석훈,지승도,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 호위 임무 시뮬레이션에 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 적용하였다. 시뮬레이션 결과 기존의 유전 알고리즘과는 달리 가변 염색체 유전 알고리즘에서는 더 복잡한 전술이 더 일찍 등장하였으며, 그에 따라 염색체 수가 증가하는 방향으로 진화가 일어나는 것을 확인할 수 있었다.