Genetic Alogorithm 의 주요 이슈

Genetic Alogorithm

 

Linkage Problem

Linkage는 유전 알고리즘에서 개체의 유전 정보를 표현하는 방식을 조작하는 기법입니다. 여기서 유전자가 같은 염색체에 위치하고 있을 때, 그 유전자 간의 링크되어 있다고 할 수 있습니다.

보통 특정한 특징이나 구조를 나타내는 개체들의 집합이 있을 때, 이들 간의 연결 정보를 유지하면서 유전 알고리즘을 수행하고자 할 때 Linkage를 활용합니다. 이를 통해 유전자들 간의 관련성을 고려하면서 탐색 공간을 줄일 수 있으며, 최적해를 더 빠르게 찾을 수 있을 수 있습니다. 

두 유전자 간 거리가 가까울수록 더 강한 링크를 지니고 있다 할 수 있고 일반적으로 거리에 의해 Linkage 강도가 결정됩니다.

 

Linkge란

 유전자가 같은 염색체에 위치하고 있을 때, 그 유전자 간의 링크되어 있다고 할 수 있습니다.

 두 유전자 간 거리가 가까울수록 더 강한 링크를 지니고 있다 할 수 있고 일반적으로 거리에 의해 Linkage 강도가 결정됩니다.

 

 

 

Linkage 발생할 수 있는 몇 가지 문제점은 다음과 같습니다:

 

강한 연결성과 약한 연결성의 혼합: Linkage Problem에서는 유전자들 간에 강한 연결성과 약한 연결성이 혼합되어 있을 수 있습니다. 강한 연결성은 유전자들이 서로 가까이 위치해 있고 함께 유지되는 경향이 있는 경우를 의미하며, 약한 연결성은 유전자들이 멀리 위치해 있고 연결이 약한 경우를 의미합니다. 이러한 혼합으로 인해 유전 알고리즘이 연결된 유전자 그룹을 정확하게 식별하거나 다루는 데 어려움을 겪을 수 있습니다.

 

교차 연산의 제한성: Linkage Problem에서 교차 연산을 수행하는 경우, 강한 연결성이 있는 유전자들이 함께 유지되어야 할 필요가 있습니다. 그러나 일반적인 유전 알고리즘에서는 교차 연산은 두 개체의 유전 정보를 교환하는 방식으로 이루어집니다. 이로 인해 강한 연결성이 있는 유전자들이 분리되어 교차되는 경우가 발생할 수 있으며, 이는 원하는 연결성을 유지하지 못하게 됩니다.

 

 

이를 해결할 수 있는 해결책으로는 아래와 같습니다.

 

 

 

1.  Gene Recording  ( 표현 방식 encoding 변경 )

 

1-1. Gene Reordering

Gene Reordering은 다음과 같은 특징을 가지고 있습니다:

 

[1] Gene Correlation (유전자 상관관계): Gene Reordering에서는 유전자들 간의 상관관계를 평가하여 유전자의 위치를 결정합니다. 유전자 간의 상관관계는 유사한 기능을 가지거나 동일한 조건에서 활동하는 유전자들 간에 발생할 수 있습니다. 이를 통해 유전자의 순서를 재배치하여 상관관계를 고려한 구조를 형성할 수 있습니다.

 

[2] GPP (Gene Positioning Problem): Gene Reordering은 주로 GPP와 관련하여 사용됩니다. GPP는 유전자들의 순서를 결정하는 문제로, 유전자들 간의 연결 정보와 상관관계를 최대한 고려하여 유전자의 배치를 수행합니다.

 

주로 Gene Reordering에서는 너비 우선 탐색(BFS)을 사용하여 유전자들의 순서를 결정합니다.  BFS를 이용하여 유전자들 간의 상관관계를 파악하고, 상관관계가 높은 유전자들을 인접한 위치로 배치하여 재배치를 진행합니다.

즉, Gene Reordering은 유전자들 간의 상관관계를 고려하여 최적의 순서를 결정하는 방식으로, GPP와 같은 문제에서 유용하게 사용될 수 있습니다. BFS를 통해 유전자들의 순서를 조정함으로써 유전자 간의 상관관계를 잘 반영하며, 효과적인 유전 알고리즘의 해 탐색을 가능하게 합니다.

 

 

1-2. Advanced Gene Reordering

 Advanced Gene Reordering은 유전 알고리즘에서 발전된 Gene Reordering 기법으로, 유전 알고리즘의 개체 집단에서 유전자 간의 상관관계를 추출하여 동적으로 유전자를 재배치하는 방식입니다. 이는 문제에 독립적으로 유전자의 순서를 재조정하는데 사용됩니다.

 

정리하면 개체 집단의 유전자 상관관계를 기반으로 하는 유전자의 순서 조정 기법입니다. 문제에 독립적으로 사용될 수 있으며, 유전 알고리즘의 성능 향상을 위해 활용될 수 있습니다.

 

 

 

 

2. 교차 연산에서의 문제 고려

 

Linkage Learning GA의 주요 특징은 다음과 같습니다:

 

[1] Gene Rearrangement (유전자 재배치): Linkage Learning GA는 유전자 간의 연결 정보를 학습하여 유전자들의 순서를 재배치합니다. 이를 통해 상호 연결된 유전자들을 인접하게 배치하고, 그룹 간의 연결성을 고려하여 유전자의 배치를 최적화합니다. 유전자의 재배치는 최종적으로 해의 품질을 향상시키는 데 기여합니다.

 

[2] Representation (표현 방식): Linkage Learning GA에서는 세 가지 요소로 유전자를 표현합니다. 첫째, "Moveable genes"는 유전자의 위치를 변경할 수 있는 부분으로, 재배치 가능한 유전자를 나타냅니다. 둘째, "non-coding segments"는 유전자 사이의 연결 정보를 나타내는 부분으로, 강한 연결성을 가진 유전자들을 식별하는 데 사용됩니다. 셋째, "probabilistic expression"은 유전자의 위치와 연결 정보에 대한 확률적인 표현입니다.

 

[3] Crossover (교차): Linkage Learning GA에서는 "Exchange crossover"라는 교차 연산을 사용합니다. 이 교차 연산은 두 개체에서 해당 위치의 유전자를 교환하여 재배치를 수행합니다. 유전자 간의 교환은 연결 정보를 보존하면서 유전자의 순서를 다양화하는 데 도움이 됩니다.

 

Linkage Learning GA는 유전자의 재배치와 연결 정보 학습을 통해 최적화 문제를 해결하는 유전 알고리즘입니다. 효과적인 유전자의 배치를 위해 다양한 표현 방식과 교차 연산을 사용하여 상호 연결성을 고려한 최적화를 수행합니다.

 

 

3. 분포 추정 알고리즘(EDA)를 사용

 

 - promising solutions에서의 정보 추출 ( ex : BOA )

Bayesian Optimization Algorithm (BOA)
베이지안 최적화 알고리즘(BOA)은 베이지안 네트워크를 사용하여 문제 공간에서 변수 간의 관계를 모델링하는 분포 추정 알고리즘의 한 유형입니다. BOA는 솔루션 공간의 확률론적 모델을 만들고 확률론적 샘플링을 통해 새로운 후보 솔루션을 생성함으로써 인코딩 기반 교차 작업의 필요성을 제거합니다.

BOA는 먼저 문제에 대한 좋은 해결책을 나타내는 일련의 훈련 데이터를 사용하여 문제 공간의 확률론적 모델을 학습합니다. 그런 다음 이 모델을 사용하여 확률론적 샘플링을 통해 새로운 후보 솔루션 세트를 생성합니다. 확률론적 모델은 이러한 후보에서 도출된 최고 성능의 솔루션을 사용하여 업데이트되며, 만족스러운 솔루션이 발견될 때까지 프로세스가 반복됩니다.

BOA의 장점은 이러한 상호 작용이 문제 공식에 명시적으로 정의되지 않은 경우에도 문제 공간에서 변수 간의 복잡한 상호 작용을 포착하는 모델을 학습할 수 있다는 것입니다. 이를 통해 BOA는 많은 수의 상호 작용 변수 또는 복잡한 종속성이 있는 문제를 해결하는 데 특히 유용합니다.

 

베이지안 최적화 알고리즘(BOA)의 주요 구성 요소는 

- 스코어링 메트릭(score metric)

- 네트워크 구조(searching for a network structure) 탐색입니다.

 

스코어링 메트릭은 BOA가 학습하려는 문제 공간의 확률 모델의 질을 측정하는 지표입니다. 일반적으로 이는 모델이 훈련 데이터에 잘 맞는 정도를 나타내는 가능도(likelihood) 또는 베이지안 점수(Bayesian score)로 구성됩니다. 높은 점수는 더 나은 모델 적합성과 좋은 솔루션 생성의 높은 가능성을 나타냅니다.

네트워크 구조 탐색은 변수들과 그들의 상호작용의 최적 배열을 찾는 과정입니다. 이를 위해 엣지 추가, 엣지 제거, 노드 분할 등의 연산으로 네트워크 구조를 수정하여 스코어링 메트릭 값을 최대화합니다. 가장 일반적인 방법은 그리디 알고리즘이며 스코어링 메트릭을 최대화하기 위해 반복적으로 엣지를 추가하거나 제거합니다.

그 밖에도 힐 클라이밍(hill-climbing), 시뮬레이티드 앤닝(simulated annealing), 랜덤 서치(random search) 등의 기법을 사용하여 탐색 공간을 보다 철저하게 탐색할 수 있습니다. 전반적으로, 스코어링 메트릭과 네트워크 구조 탐색은 BOA의 필수 구성 요소로, 문제 공간의 확률 모델을 효과적으로 학습하고 확률적 샘플링을 통해 높은 품질의 후보 솔루션을 생성하는 알고리즘을 가능하게 합니다.

 

 

 

---

 

 

Normalization

 

정규화는 유전 알고리즘(GA)에서 중요한 전처리 기법 중 하나입니다. 

정규화란, 동일한 표현형(phenotype)을 가진 경우에도 여러 가지 유전자형(genotype)이 존재하는 경우를 말합니다. 이렇게 되면 유전자 공간이 다중 모달(multimodal)이 되어 전통적인 교차(crossover) 방식들(k-point, uniform 등)에서 문제가 발생할 수 있습니다. 

정규화가 유용한 문제는, 그룹화 문제(graph partitioning, graph coloring, bin packing, workshop layout)나 구조 최적화 문제(sorting network optimization, neural network optimization, RNA structure prediction)입니다.

정규화를 적용하면, 유전자형-표현형 관계를 일대일 대응하게 만들어 문제 공간을 줄일 수 있습니다. 또한, 탐색 공간의 랜드스케이프(lanscape) 구조를 변경하므로, GA의 성능에 영향을 미칩니다.

 

• Normalization Example problems

 

. Multiway GPP(Grouping Problem using Genetic Programming): 이 문제는 그룹화 문제 중의 하나로, 유전 프로그래밍(GP)을 사용하여 해결할 수 있습니다. 각 그룹을 구성하는 개체는 다른 그룹에서는 배제되면서, 전체 그룹 개체 수의 합이 최소화되는 그룹을 찾는 것이 목적입니다

 

. Sorting Network Optimization: 해당 문제는 정렬망을 최적화하는 문제입니다. 정렬망은 병합 정렬(merge sort)에서 하위 정렬(sub-sorting) 단계를 처리하는 것으로, 이때 가장 효율적인 정렬망 구조를 찾는 것이 목적입니다.

  – 비교기 수가 가장 적은 정렬 네트워크 찾기
  – 타당성 테스트 : 제로원 원칙 (2^N 테스트 사례만 필요)
  – 상호 연결 네트워크의 스위칭 회로, 라우팅 알고리즘 및 기타 영역에서 널리 사용됨

 

Neural Network Optimization: 해당 문제는 인공 신경망의 구조나 가중치(weight) 등을 최적화하는 문제입니다. 인공 신경망은 기계학습에서 중요한 모델 중 하나로, 이때 가장 효율적인 구조나 가중치를 찾는 것이 목적입니다.

 

 

 

 

Efficient Selection 

효율적인 Selection 과정은 다양성을 유지하는데 중요합니다. 이를 위해 아래와 같은 방법을 고려할 수 있습니다

 

 

[1] 선발 (Preselection): 선발은 개체 집단에서 적합도가 높은 개체를 선별하여 다음 세대로 전파하는 과정입니다. 일반적으로 적합도가 높은 개체들은 더 많은 자손을 낳을 수 있도록 선호되는 경향이 있습니다. 선발은 개체 집단 내의 유전 다양성을 유지하면서도 우수한 솔루션들을 계속해서 발전시키는 데 도움을 줍니다.

 

[2] 공유 (Sharing): 공유는 개체 사이의 유사성을 고려하여 적합도를 조정하는 방법입니다. 개체들이 유사한 영역에서 발전할 경우 개체 간의 경쟁이 강해져 다양성이 저하될 수 있습니다. 따라서 개체들이 공유하는 자원을 제한함으로써 공동 경쟁을 강화하고, 개체 집단 내의 다양성을 유지할 수 있습니다.

 

[3] 교배 (Mating): 교배는 다양한 개체 간의 유전 정보를 교환하여 새로운 자손을 생성하는 과정입니다. 교배는 다양성을 증가시키고 새로운 유전적 조합을 탐색하는 데 중요한 역할을 합니다. 다양한 교배 연산자와 전략들이 존재하며, 이를 통해 다양한 개체들 간의 유전 정보를 교환하고 새로운 개체를 생성할 수 있습니다.

 

부모를 선택하는 3 Classes 
– Similar mating 
   • 유사 솔루션 선호
   • 공격 중심의 빠른 수렴

– Dissimilar mating

• 젠더 기반의 인코딩
• 탐색 중심의 지속적인 발산

– 하이브리드 짝짓기
• 둘 이상의 Schemes가 가중치 매개 변수와 결합

 

 

이러한 효율적인 셀렉션 과정들은 유전 알고리즘에서 다양성을 유지하고 최적해를 찾는 데 기여합니다. 다양성은 알고리즘의 탐색 공간을 탐색하고 더 많은 해 공간을 커버하는 데 도움을 주며, 최적해에 도달할 가능성을 높여줍니다.