위치기반 인코딩을 사용하는 유전 알고리즘에서 정적 유전자 재배열이란 상관성이 높은 유전자들이 서로 인접하도록 배치하는 것을 말한다. 그것은 유전 알고리즘이 효과적으로 고품질의 스키마들을 생성하고 보존하는 데 도움을 준다. 본 논문에서는 선형의 위치기반 인코딩을 위한 정적 재배치 방법을 제안한다. 본 논문에서 제안하는 방법은 특정 문제에 한정된 정보를 사용하지 않는다는 점에서 기존의 방법들과 차이가 있다. 그것은 모든 유전자들 사이의 상관성을 계산하여 가중치가 있는 완전 그래프를 만든다. 그리고 그 그래프에서 상대적으로 가중치가 높은 간선들만 골라 냄으로써 가중치가 없는 희소 그래프로 변환한다. 끝으로 그래프 탐색을 통해 유전자 재배열을 찾는다. 여러 문제에 관한 광범위한 실험을 통해 본 논문에서 제안한 방법은 재배열을 하지 않은 유전 알고리즘에 비해 현저한 성능 향상을 보여 주었다.
In genetic algorithms with lotus-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.
