Optimization Algorithms Based on Search-space Transformation and Efficient Representation

Abstract

This thesis presents novel approaches of improving the performance of optimization algorithms, primarily focusing on representation and possible transformation of the search space. We study the relationship between search spaces, which vary depending on how we map the structure of real-world concepts onto that of symbols used in computer algorithms. Through the study, we try to devise novel effective algorithms using representations that are fitted to the structures of search spaces and transformations from conventional search spaces into new ones. We studied the structures of search spaces and proposed various techniques to improve the performance of optimization algorithms by transforming the spaces. Firstly, the thesis introduces the mathematical concept of quotient space and studies its properties related to optimization algorithms and representations. Especially for redundant representations, the concept is consistent with the genotypephenotype mapping derived from an equivalence relation defined by an isometry group. We show that this mapping can be naturally interpreted using the concept of quotient space, in which the original space and its quotient space correspond to the genotype space and the phenotype space, respectively. Using this characterization, it is possible to define quotient geometric crossovers on the phenotype space. These crossovers have very appealing properties for non-synonymously redundant encodings, such as reducing the size of the search space actually searched, removing the low locality from the encodings, and allowing a more informed search by utilizing distances better tailored to the specific solution interpretation. We give four example applications of quotient geometric crossovers for non-synonymously redundant encodings and demonstrate their superiority experimentally. We also present a new crossover operator for real-coded genetic algorithms in relation with the concept of quotient space. In this case, quotient space has an effect of transforming the topology of the hyper-rectangular real space by gluing opposite boundaries. We propose a novel methodology to remove the inherent bias of pre-existing crossover operators using the property of quotient of bounded real space. This is done by gluing opposite boundaries and designing a boundary extension method for making the fitness function smooth at the glued boundary. We show the advantages of the proposed crossover by comparing its performance with those of existing ones on test functions that are commonly used in the literature, and a nonlinear regression on a real-world dataset. Secondly, the thesis presents a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem.We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale problem instances. We also propose a Lagrangian method for the multicampaign assignment problem, which is a campaign model to overcome the multiple recommendation problem which occurs when conducting several personalized campaigns simultaneously. We combine the Lagrangian method with a genetic algorithm to find good near-feasible solutions. We verify the effectiveness of our evolutionary Lagrangian approach in both theoretical and experimental views of points. The suggested Lagrangian approach is practically attractive for large-scale real-world problems. Finally, the thesis presents some novel ideas inspired by linear algebraic approaches. Linear algebraic structure lie in search spaces of many problems. We analyze two essential problems arising from edge-based graph partitioning. We show that one of them is an NP-hard problem but the other is in P, presenting a novel methodology that links linear algebra theory to the graph problems as a part of proving the facts. As a result of the linear algebraic manipulation, we could devise a linear-time algorithm for the problem in P. We also study linear algebraic structures in genetic algorithms using binary encoding. We especially focus on examining the variation of performance when changing basis. A transformed basis can change the linkage structure inherent in the fitness function. From empirical analysis, we could show that a better basis makes the fitness landscape smoother and hence genetic algorithms based on the new encoding obtain better performance. As advanced work, we investigate nonsingular binary matrix space, GL_n(Z_2), which is used for representing the change of basis in binary encoding. We analyze the properties of GL_n(Z_2) and discuss possible representations and recombination operators when used in evolutionary algorithms. Not only typical approaches but also ones using elementary matrices of linear algebra are presented.

본 논문은 탐색 공간의 표현과 가능한 변환에 초점을 맞추어 최적화 알고리즘의 성능을 향상시키는 독창적인 접근법을 제시한다. 실세계의 개념들을 컴퓨터 알고리즘에서 사용하는 기호들로 어떻게 연결시키느냐에 따라 달라질 수 있는 탐색 공간 사이의 관계를 연구한다. 이 연구를 바탕으로 해서, 탐색 공간의 구조에 잘 맞는 표현과 관습적인 탐색 공간에서 새로운 공간으로의 변환을 이용한 새롭고 효과적인 알고리즘들을 고안해 내고자 노력한다. 탐색 공간의 구조를 연구하고 이 공간들 간의 변환을 통해 최적화 알고리즘의 성능을 개선할 수 있는 다양한 기법들을 제안한다. 첫번째로, 몫 공간의 수학적 개념을 소개하고 최적화 알고리즘, 표현과 관련된 그 성질들을 연구한다. 특히 중복 표현의 경우에, 몫 공간의 개념은 등장변환 군에 의해 정의된 동치 관계로부터 나온 유전자형-표현형 매핑과 같다. 몫 공간의 개념을 사용함으로써 이 매핑을 자연스럽게 해석할 수 있으며, 여기서 원래의 공간과 그 몫 공간은 각각 유전자형 공간과 표현형 공간에 해당한다는 것을 보인다. 이런 특성을 이용하여 표현형 공간에 몫 기하 교차 연산자를 정의하는 것이 가능하다. 이 교차 연산자는 비동의 중복 인코딩에 대해 실제 탐색 대상이 되는 탐색 공간의 크기를 줄여 주고 인코딩의 낮은 집약성을 없애주며 주어진 해에 대한 해석에 더 잘 맞는 거리를 활용하여 좀 더 정보력 있는 탐색을 가능하게 해 주는 등의 무척 매력적인 속성들을 지닌다. 비동의 중복 인코딩에 대한 네 개의 몫 기하 교차 연산자의 응용 예를 제시하고 그 우월성을 실험적으로 보인다. 본 논문에서는 또한 몫 공간의 개념과 관련해서 실수 코딩 유전 알고리즘을 위한 새로운 교차 연산자를 제안한다. 이 경우 몫 공간은 다차원의 직사각형 모양인 실수 공간을 그 맞은편 경계들끼리 붙임으로서 위상을 변환하는 효과가 있다. 몫 공간의 이러한 성질을 이용해서 기존 교차 연산자들이 지닌 본질적인 편향성을 없앨 수 있는 독창적인 방법론을 제안한다. 이는 맞은편 경계들을 서로 붙이고 그 붙여진 경계에서 적합도 함수가 매끈한 모양을 갖도록 경계를 확장하는 방식을 고안함으로써 가능하다. 학계에서 일반적으로 사용되는 테스트 함수들과 실세계 데이터를 이용한 비선형 회귀 문제에 대해 성능을 비교함으로써 제안한 교차 연산자의 이점을 보인다. 두 번째로, 이론적이고 실험적인 측면에서 좋은 가능해를 찾기 위한 새로운 라그랑지 방법을 기술한다. 라그랑지 이완법이 최적해를 찾을 수 있는 용량 제약 조건의 값인 라그랑지 용량이라는 개념을 설명한 후, 0-1 다차원 배낭 문제에 맞는 라그랑지 용량을 형식적으로 재소개하고 새로운 관련 성질을 포함하여 그의 새로운 기하적인 동치 조건을 기술한다. 그 성질을 바탕으로 해서, 0-1 다차원 배낭 문제에 대해 좋은 가능해를 찾는 새로운 라그랑지 휴리스틱을 제안한다. 벤치마크 데이터에 대해 기존의 라그랑지 접근법과 비교하고 제안한 방법이 규모가 큰 인스턴스에 대해 잘 동작한다는 것을 보인다. 다중 캠페인 할당 문제에 대한 라그랑지 방법 또한 제안하는데, 이 문제는 여러 개의 개인화된 캠페인들을 동시에 수행할 때 일어나는 중복 추천 문제를 해결하기 위한 캠페인 모델이다. 좋은 가능해를 찾기 위해 라그랑지 방법을 유전 알고리즘과 결합한다. 이 진화 라그랑지 접근법이 이론적이고 실험적인 관점에서 효과적임을 입증한다. 제안한 라그랑지 접근법은 규모가 큰 실세계 문제들을 다룰 때 현실적으로 좋은 방법이 될 수 있다. 마지막으로, 선형 대수적인 접근법에서 영감을 얻은 독창적인 아이디어들을 제시한다. 많은 문제 공간들에 선형 대수적 구조가 깔려있다. 간선 기반 그래프 분할에서 발생하는 두 개의 필수적인 문제를 분석한다. 그 중 한 문제는 NP-난해 문제지만 다른 하나는 P에 속함을 보이는데, 증명의 일부분으로 선형 대수 이론을 그래프 문제와 연결시킨 새로운 접근법을 제시한다. 선형 대수적 조작을 이용해 P에 속하는 문제의 선형 시간 알고리즘을 고안할 수 있었다. 또한 본 논문에서는 이진 인코딩을 사용하는 유전 알고리즘에서의 선형 대수적 구조를 연구한다. 특히 기저를 바꿀 때 유전 알고리즘의 성능이 어떻게 변화하는가에 초점을 맞춘다. 변환된 기저는 적합도 함수에 내재하는 연결 구조를 바꿀 수 있다. 실험적인 분석을 통해 더 좋은 기저가 적합도 지형을 좀 더 매끄럽게 만들고 따라서 그 새로운 인코딩을 바탕으로 한 유전 알고리즘은 더 좋은 성능을 낼 수 있음을 보일 수 있었다. 그 후속 연구로 정칙 이진 행렬 공간 GL_n(Z_2)을 조사하는데, 이 공간은 이진 인코딩에서의 기저 변환을 표현하는 데에 사용될 수 있다. GL_n(Z_2)의 성질들을 분석하고 진화 알고리즘에 쓰일 경우 가능한 표현과 재조합 연산자들에 관해 논의한다. 전형적인 접근법 뿐만 아니라 선형 대수의 기본 행렬을 이용한 접근법 또한 제시한다.