유전 알고리즘에서의 문제 독립적 유전자 재배열

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

위치기반 인코딩을 사용하는 유전 알고리즘에서 정적 유전자 재배열이란 상관성이 높은 유전자들이 서로 인접하도록 배치하는 것을 말한다. 그것은 유전 알고리즘이 효과적으로 고품질의 스키마들을 생성하고 보존하는 데 도움을 준다. 본 논문에서는 선형의 위치기반 인코딩을 위한 정적 재배치 방법을 제안한다. 본 논문에서 제안하는 방법은 특정 문제에 한정된 정보를 사용하지 않는다는 점에서 기존의 방법들과 차이가 있다. 그것은 모든 유전자들 사이의 상관성을 계산하여 가중치가 있는 완전 그래프를 만든다. 그리고 그 그래프에서 상대적으로 가중치가 높은 간선들만 골라 냄으로써 가중치가 없는 희소 그래프로 변환한다. 끝으로 그래프 탐색을 통해 유전자 재배열을 찾는다. 여러 문제에 관한 광범위한 실험을 통해 본 논문에서 제안한 방법은 재배열을 하지 않은 유전 알고리즘에 비해 현저한 성능 향상을 보여 주었다. In genetic algorithms with locus-based encoding, static gene reordering is to locate the highly related genes closely together. It helps the genetic algorithms to create and preserve the schema of high-quality effectively. In this paper, we propose a static reordering framework for linear locus-based encoding. It differs from existing reorderings in that it is independent of problem-specific knowledge. It makes a complete graph where weights represent the interelationship between each pair of genes. And, it transforms the graph into a unweighted sparse graph by choosing the edges having relatively high weight. It finds a gene reordering by graph search method. Through the wide experiments about several problems, the method proposed in this paper shows significant performance improvement as compared with the genetic algorithm that does not rearrange genes.

랜덤 불리언 네트워크 모델을 이용한 되먹임 루프가 네트워크 강건성에 미치는 영향

권영근(Yung-Keun Kwon) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.3

생체네트워크는 여러 종류의 환경 변화에 매우 강건하다고 알려져 있지만 그 메커니즘은 아직 밝혀지지 않고 있다. 본 논문에서는 랜덤 네트워크에 비해 생체네트워크에 되먹임 루프가 매우 많이 존재한다는 구조적 특징을 발견하고 그것이 네트워크의 강건성에 어떤 영향을 미치는지를 살펴보았다. 이를 위해 불리언 네트워크 모델을 이용하여 네트워크 강건성을 적절하게 측정하는 방법을 정의하고 많은 불리언 네트워크에 대해서 시뮬레이션하였다. 그 결과, 불리언 네트워크에서 되먹임 루프의 개수가 증가하면 고정점 끌개의 개수는 거의 변화가 없지만 유한순환 끌개의 개수는 크게 줄어든다는 사실을 밝혔다. 또한, 되먹임 루프의 개수가 증가함에 따라 고정점 끌개로 수렴하는 거대한 끌개 영역이 생성됨을 보였다. 이러한 사실들은 매우 많은 수의 되먹임 루프가 네트워크의 강건성을 높이는 데 중요한 요인임을 설명한다. It is well known that many biological networks are very robust against various types of perturbations, but we still do not know the mechanism of robustness. In this paper, we find that there exist a number of feedback loops in a real biological network compared to randomly generated networks. Moreover, we investigate how the topological property affects network robustness. To this end, we properly define the notion of robustness based on a Boolean network model. Through extensive simulations, we show that the Boolean networks create a nearly constant number of fixed-point attractors, while they create a smaller number of limit-cycle attractors as they contain a larger number of feedback loops. In addition, we elucidate that a considerably large basin of a fixed-point attractor is generated in the networks with a large number of feedback loops. All these results imply that the existence of a large number of feedback loops in biological networks can be a critical factor for their robust behaviors.

불리언 네트워크 계산 모델을 이용한 무척도 네트워크와 생체 네트워크 강건성의 관계 분석

권영근(Yung-Keun Kwon) 한국정보과학회 2011 정보과학회논문지 : 소프트웨어 및 응용 Vol.38 No.6

생체 네트워크의 동역학은 네트워크의 구조적 특성과 관련이 있으며 그 관계의 규명은 생체 네트워크의 설계 원리를 이해하는 데 중요하다. 본 논문에서는 생체 네트워크에서 정점의 차수가 멱급수 분포를 따르는 무척도 특성이 있음을 주목하고 이것이 네트워크 강건성에 어떤 영향을 미치는지를 살펴보았다. 비록 무척도 특성과 네트워크 강건성의 관계를 보인 기존의 연구들이 있었지만, 시뮬레이션을 하는데 있어 단순히 상태 궤적의 차이를 비교한 점, 네트워크의 연결성을 고려하지 않은 점, 모든 가능한 네트워크 상태를 고려하지 않은 점 등에서 아직 그 관계에 대한 이해가 부족하다. 이러한 점에서 본 논문에서는 연결된 네트워크 구조만을 생성하는 불리언 네트워크 모델을 제안하여 모든 가능한 네트워크 상태에 대해 수렴하는 끌개가 얼마나 잘 유지되는지에 관한 강건성을 조사하였다. 대량의 시뮬레이션을 통해 무척도 네트워크가 랜덤 네트워크에 비해 환경 변화와 같은 상태 변이에 더 강건하다는 사실을 밝혔다. 또한, 무척도 네트워크에서는 차수가 매우 큰 허브 정점이 생성되지만 이들의 강건성은 상대적으로 매우 약함을 보였다. 실제로 신경세포의 신호전달네트워크를 분석해 본 결과 차수가 큰 정점에 해당하는 유전자들 집합에서 치사유전자의 비율이 높다는 것을 관찰할 수 있었는데 이는 허브 정점이 강건하지 못하다는 사실을 잘 뒷받침해 준다. 이러한 결과들은 생체 네트워크가 보이는 무척도 특성이 랜덤 네트워크와는 매우 다른 동역학적 특성을 유도하는 중요한 설계 원리중의 하나임을 설명한다. Dynamical behaviors of biological networks are related to their structural characteristics and thus investigations on such relationships are important in understanding a design principle of biological networks. In this paper, we note that biological networks have a scale-free property where degree distribution of nodes follows a power law and try to elucidate the effects of the scale-free property on the network robustness. Although there have been previous studies on the relationship between the scale-free property and robustness, our understanding is still unclear since they simply focused on the difference of state trajectories, did not consider the network connectivity, and did not examine dynamics over all possible network states. In this regard, we propose a Boolean network model which generates only connected networks and investigate the robustness in terms of the converging attractors over all possible states. Through extensive simulations, we show that scale-free networks are more robust against perturbations than random networks. In addition, it is shown that the scale-free networks generate hub nodes with a considerably large degree but their robustness is very small. This is supported by the observation that the proportion of lethal genes in the set of hub genes is relatively large in a signal transduction network. All these results imply that the scale-free property is an important design principle of biological networks to induce different dynamics from that of random networks.

데이터 공학 : 컴퓨터공학 분야 키워드네트워크의 구조적 변화 이해

권영근 ( Yung Keun Kwon ) 한국정보처리학회 2013 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.2 No.3

컴퓨터공학 분야 학술 논문 데이터베이스를 이용한 키워드 연관 네트워크 기반 지식지도

정보석,권영근,곽승진,Jung, Bo-Seok,Kwon, Yung-Keun,Kwak, Seung-Jin 한국정보처리학회 2011 정보처리학회논문지D Vol.18 No.6

최근 여러 분야에서 활용되고 있는 지식지도는 대량의 정보 속에 숨겨진 특징을 찾아서 그 의미를 파악할 수 있도록 가시적인 형태의 결과를 보여주는 것을 말한다. 본 논문에서는 2000년부터 2010년까지 컴퓨터 공학 분야의 국내 학술지에 게재된 논문들의 데이터베이스를 활용하여 연구동향 분석을 위한 키워드 연관 네트워크 기반의 지식지도를 제안하였다. 그 지식지도를 통해 키워드 연관 네트워크에서 개별 키워드가 속한 연결 요소의 크기 변화를 살펴봄으로써 관련 연구 주제의 영향력 변화를 추론할 수 있었다. 또한, 랜덤 네트워크와의 비교를 통해 키워드 연관 네트워크에서 최대 연결 요소의 크기가 상대적으로 매우 작으며, 상호 관련성이 높은 키워드 쌍들의 그룹이 밀집되어 있음을 보였다. 이는 최대 연결 요소에 대응하는 연구 분야가 크지 않으며 여러 소규모의 연구 주제들이 느슨한 형태로 연결되어 있음을 암시한다. 이러한 분석 결과들은 단순히 개별 키워드의 사용 빈도수 등을 분석하는 전통적인 방식으로는 얻기 어렵다는 점에서 본 논문에서 제안한 지식지도가 연구동향 분석의 방법이 될 수 있다. A knowledge map, which has been recently applied in various fields, is discovering characteristics hidden in a large amount of information and showing a tangible output to understand the meaning of the discovery. In this paper, we suggested a knowledge map for research trend analysis based on keyword-relation networks which are constructed by using a database of the domestic journal articles in the computer engineering field from 2000 through 2010. From that knowledge map, we could infer influential changes of a research topic related a specific keyword through examining the change of sizes of the connected components to which the keyword belongs in the keyword-relation networks. In addition, we observed that the size of the largest connected component in the keyword-relation networks is relatively small and groups of high-similarity keyword pairs are clustered in them by comparison with the random networks. This implies that the research field corresponding to the largest connected component is not so huge and many small-scale topics included in it are highly clustered and loosely-connected to each other. our proposed knowledge map can be considered as a approach for the research trend analysis while it is impossible to obtain those results by conventional approaches such as analyzing the frequency of an individual keyword.

전화전략기반 엔진출력 최적화를 통한 선박경제운항시스템

장호섭,권영근,Jang, Ho-Seop,Kwon, Yung-Keun 한국통신학회 2011 韓國通信學會論文誌 Vol.36 No.4B

선박경제운항이란 기상예측정보를 활용하여 연료소모량을 최소화하도록 선박을 운항하는 것으로서 최근 많은 시스템이 이를 위해 연구되고 있다. 기존의 시스템에서는 문제의 복잡성을 줄이기 위해 엔진의 출력을 고정하거나 속력을 일정하게 운항한다는 가정을 기반으로 접근하고 있다. 그러나 엔진출력을 잘 조절한다면 더 좋은 기상환경에서 선박이 운항할 수 있게 되어 연료소모량을 더욱 줄일 수 있다. 본 논문에서는 진화전략 알고리즘을 사용하여 항로의 세부구간별로 최적출력을 탐색할 수 있는 새로운 경제운항시스템을 제안하였다. 또한, 지리적 최단 경로를 찾을 수 있는 $A^*$ 알고리즘과 곡선 표현의 자유도를 높일 수 있는 방법을 사용함으로써 임의의 출발지와 목적지에 대해서 제안된 경제운항시스템을 적용할 수 있도록 하였다. 총 36가지의 운항 시나리오에 대해서 이 논문에서 제안된 시스템의 성능을 기존의 출력고정 운항방법과 비교한 결과, 운항소요시간은 거의 차이가 없으면서도 연료소모량을 평균적으로 1.3%, 최대로는 5.6% 개선시킬 수 있음을 관찰하였다. An economic ship routing means to sail a ship with a goal of minimizing the fuel consumption by utilizing weather forecast information, and many such systems have been recently developed. Most of them assume that sailing is carried out with a constraint like a fixed output of engine-power or a fixed sailing speed. However, if the output of engine-power is controlled, it is possible to reduce the fuel consumption by sailing a ship under a relatively good weather condition. In this paper, we propose a novel economic ship routing system which can search optimal outputs of the engine-power for each part of a path by employing an evolutionary strategy. In addition, we develope an $A^*$ algorithm to find the shortest path and a method to enhance the degree of curve representation. These make the proposed system applicable to an arbitrary pair of departure and destination points. We compared our proposed system with another existing system not controlling output of the engine-power over 36 scenarios in total, and observed that the former reduced the estimated fuel consumption than the latter by 1.3% on average and the maximum 5.6% with little difference of estimated time of arrival.

조선소 트랜스포터 최적 운영을 위한 혼합형 유전알고리즘

박준호(Jun-Ho Park),권영근(Yung-Keun Kwon) 한국컴퓨터정보학회 2023 韓國컴퓨터情報學會論文誌 Vol.28 No.12

본 연구에서는 트랜스포터의 할당 및 운행 순서를 최적화하기 위한 유전 알고리즘을 제안한다. 유전 알고리즘의 해는 리스트의 집합으로 표현되는데 각 리스트는 해당 트랜스포터가 작업할 순서를 나타낸다. 또한 성능 향상을 위해 효과적인 지역 탐색 연산을 결합한 혼합형 유전 알고리즘의 형태로 구현하였다. 지역 탐색 연산은 작업량이 적은 트랜스포터에서 작업의 블록을 꺼내어 다른 트랜스포터의 작업 목록에 삽입함으로써 트랜스포터 운용 대수의 감소를 유도한다. 제안하는 알고리즘의 효용성을 평가하기 위해 실제 조선소와 유사한 규모의 시뮬레이션 환경을 통해 Multi-Start 및 순수 유전알고리즘과 비교하였다. 가장 큰 규모의 문제에 대해 그들에 비해 트랜스포터 수는 각각 40% 및 34%, 총작업 소요 시간은 27% 및 17% 감소시켰다. In this study, we propose a genetic algorithm (GA) to optimize the allocation and operation order of transporters. The solution in the GA is represented by a set of lists each of which the operation order of the corresponding transporter. In addition, it was implemented in the form of a hybrid genetic algorithm combining effective local search operations for performance improvement. The local search reduces the number of operating transporters by moving blocks from a transporter with a low workload into that with a high workload. To evaluate the effectiveness of the proposed algorithm, it was compared with Multi-Start and a pure genetic algorithm through a simulation environment similar in scale to an actual shipyard. For the largest problem, compared to them, the number of transporters was reduced by 40% and 34%, and the total task time was reduced by 27% and 17%, respectively.

혼합형 유전알고리즘을 이용한 조선소 스키드 순서 최적화

최민재(Min-Jae Choi),권영근(Yung-Keun Kwon) 한국컴퓨터정보학회 2023 韓國컴퓨터情報學會論文誌 Vol.28 No.12

본 연구는 조선소 소조립 공정에서 스키드 투입 순서 최적화를 통해 전체 작업시간을 단축시키는 새로운 유전 알고리즘 방법을 제안한다. 하나의 해는 스키드 번호들의 순열로 표현되며 그러한 표현에 적합한 유전 연산자들을 적용하였다. 또한 탐색 성능의 개선을 위해 UniDev라 불리우는 기존의 휴리스틱 알고리즘을 적절하게 변형하여 유전 알고리즘과 결합하였다. 특히 UniDev에서 느린 스키드 탐색 부분을 그리디 알고리즘의 형태로 변경하였다. 매우 큰 규모의 문제에 대해 시뮬레이션을 수행한 결과 Multi-Start 탐색과 UniDev기반 혼합형 유전알고리즘에 비해 본 연구에서 제안하는 방법이 안정적으로 작업시간을 최소화함을 관찰하였다. In this paper, we propose a novel genetic algorithm to reduce the overall span time by optimizing the skid insertion sequence in the shipyard subassembly process. We represented a solution by a permutation of a set of skid ids and applied genetic operators suitable for such a representation. In addition, we combined the genetic algorithm and the existing heuristic algorithm called UniDev which is properly modified to improve the search performance. In particular, the slow skid search part in UniDev was changed to a greedy algorithm. Through extensive large-scaled simulations, it was observed that the span time of our method was stably minimized compared to Multi-Start search and a genetic algorithm combined with UniDev.

진화전략 기반 경로탐색 알고리즘을 활용한 선박경제운항시스템

방세환 ( Se-hwan Bang ),권영근 ( Yung-keun Kwon ) 한국정보처리학회 2014 한국정보처리학회 학술대회논문집 Vol.21 No.2

서 최근 다양한 방법론이 연구되고 있다. 성공적인 경제운항시스템을 구현하기 위해서는 기상을 고려 하여 지리적 운항경로를 바꾸거나 적절하게 엔진 출력을 조절하는 방법이 필요하다. 그러나 항해 시각에 따라 연료소모량이 변하는 동적 비용 문제임을 고려할 때 지리적 운항 경로의 결정은 최적의 해를 찾기가 어렵다. 이에 이 논문에서는 매우 많은 지리적 후보 경로들 중에서 우수한 품질의 해를 효과적으로 탐색하기 위한 진화전략 기반 경로탐색 알고리즘을 제안하였다. 제안된 방법을 5개 노선에 대해 실험한 결과 최단거리 운항 방법에 비해 운항소요시간은 거의 차이가 없으면서도 연료소모량을 평균 1.41%, 최대 1.45% 개선시킬 수 있었다.

기상예보와 운항비용예측 기반의 선박경제운항시스템

장호섭 ( Ho-seop Jang ),권영근 ( Yung-keun Kwon ) 한국정보처리학회 2011 한국정보처리학회 학술대회논문집 Vol.18 No.1

선박경제운항이란 파도와 바람과 같은 해양 기상정보 예측을 바탕으로 선박의 운항방법에 따른 연료 소모량과 운항시간을 예상해보고, 가장 경제적인 운항을 하는 것을 말한다. 본 논문에서는 실용화할 수 있는 범용의 경제운항시스템 개발에 중점을 두었다. 기존의 시스템들을 살펴보면 임의의 정해진 경로를 대상으로 실험하는 경우가 많은데, 이를 개선하여 임의의 출발점과 도착점이 주어지면 A*알고리즘을 통해서 지리상 최단경로를 찾아내도록 하여 시스템을 자동화하였으며 적용범위를 세계 전역으로 확대 하였다. 그리고 기존의 엔진출력을 고정하거나 속력을 일정하게 운항한다는 가정에서 벗어나서 엔진출력을 탐색하여 보다 효율적인 운항 솔루션을 찾아내도록 하였다. 그리고 사용측면에서는 운항사 들에게 보다 효용성 높은 시스템이 되기 위해서, 일방적인 권고보다는 연료소모량과 운항시간 별로 다양한 솔루션들을 제공하여 운항사의 판단을 존중함과 동시에 운항보조시스템으로서의 역할에 충실할 수 있도록 하였다.