View Code? Open in Web Editor
NEW
GA for solving HTP
License: Apache License 2.0
htpga's Introduction
GA for solving HTP
![concept](img/concept.png)
- NxN개 육각형의 마름모꼴 모양
- 1차원 배열 세 개 형태의 표현형
- 꼭짓점에 맞닿은 육각형의 개수에 따라 Level(Contact Level)로 분할
- 육각형과 맵핑되어 Fitness 계산/지역성을 반영한 변이 연산 등에 활용
- 지수귀문도 꼭짓점의 실제 값들을 세 개의 일차원 배열로 담고 있는 클래스
- 값 get/set, swap 등의 연산 및 부가정보를 위한 속성들
- Verification(값들이 순열의 성질을 유지하는지)
-
VerticeSpace의 각각 값들의 위치와 맵핑되는 6개의 튜플을 담고 있는 육각형 자료구조
- 각 튜플은 (level, position)으로 VerticeSpace의 element에 접근하는 포인터 역할을 함
-
Tortoise 클래스에 의해 이차원 배열 형태로 사용됨
-
위치 정보 튜플의 get/set(set은 초기 tortoise 구성에만 사용) 및 이차원배열에서의 좌표 정보
- length를 파라미터로 받아 length*length 크기의 VerticesSpace와 대응되는 Hexagon 클래스들을 구성하는 클래스
- 지역적으로 인접한 값들, 육각형 값의 합/평균/분산 등 유전 연산을 돕는 operation 제공
![class](img/class.png)
htpga's People
Contributors
Watchers
htpga's Issues
Definition at README
- NxN개 육각형의 마름모꼴 모양
- 1차원 배열 세 개 형태의 표현형
- 꼭짓점에 맞닿은 육각형의 개수에 따라 Level(Contact Level)로 분할
- 육각형과 맵핑되어 Fitness 계산/지역성을 반영한 변이 연산 등에 활용
Conterexample
'
- Image above is not in diamond shape.
- Due to wrong premises, whole VerticeSpace class should be reimplement.
- Current implementation of gene is little complicated, it might be implemented simpler way.
- 유전자 인코딩
- Contact Level이 해의 품질에 영향을 주기 때문에, Contact Level 별로 유전자를 인코딩한다.
- 선택
- 품질 비례 룰렛휠 선택을 사용
- 선택압 상수 k는 가장 일반적인 3으로 선택
- 교차
- 2차원 내추럴 교차를 선택
- 각 contact level의 중간지점을 잘라서 교차
- (1차원 유전자의 경우) PMX 사용
- 변이
- 전형적 변이를 사용
- 30%의 확률로 1을 가감
- 가감폭은 유동적으로 하는 가변폭 변이와 비교에 볼만 함.
- 수선
- Greedy repair 사용
- 겹치는 값들이 발생할 경우, 하나씩 값을 넣어보며 가장 좋은 값을 수선된 값으로 선택
- 지역 최적화