선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서 위치기반 인코딩에서 유전자들을 정적으로 재배치하는 프레임워크를 제안하였다. 그것은 재배치 없는 유전 알고리즘에 비해 일관된 성능 향상을 보여 주었다.
- 그 방법은 염색체 표현으로서 위치기반 인코딩을 하는 경우에 적용될 수 있다. 본 논문에서는 세 가지 대표적인 NP-hard 조합 최적화 문제들(그래프 분할, 선형 배열, 순회 판매원 문제)에 대해 실험을 수행하였다. 그 결과, 재배치를 하지 않는 경우에 비해 현저한 성능 향상을 보여 주었다.
- 그러므로, 새로운 문제들 각각에 대해 새로운 휴리스틱을 통해 재배치해야 한다. 본 논문에서는 특정 문제에 한정적인 정보를 사용하지 않는 정적 재배치 방법을 제안한다. 그 방법은 염색체 표현으로서 위치기반 인코딩을 하는 경우에 적용될 수 있다.
- 전처리를 거친 유전 알고리즘은 임의로 배열된 유전자로 수행된 유전 알고리즘에 비해 눈에 띄게 좋은 성능을 보여 주었다. 특히 전처리는 랜덤 기하 그래프와 캐터필러 그래프에 대해서 큰 성능 향상을 보여 주었다 또한 2-Opt보다 더 강력한 지역 최적화 휴리스틱을 사용한다면 더욱 향상된 해를 구할 수도 있음을 지적하고자 한다. 하지만, 여기에서는 주관심이 제안된 유전자 재배열 방법의 효과를 알아보는 것이므로 지역 최적화 방법을 2-Opt로 고 정하였다.
가설 설정
- 하지만 이 수치는 일반적인 수치가 야니라 어느 정도 노이즈를 포함하는 정보가 되며, 본. 논문에서는 각각의 거리는 정규분포에 해당하는 노이즈를 갖는 것으로 가정하였다. 0를 간선의 가중치라 할 때, 尸(1μ圣叫) =。、。5를 만족하는 叫보다 큰 가중치를 갖는 간선들을 골라낸다.
- [단계 2]에서 구 한 가중치가 있는 완전 그래프를 유전자 상관 그래프(gene-interaction graph)라 불리는 가중치 없는 희소그래프로 변환한다. 본 논문에서는 [단계 2]에서 구한 그래프의 가중치들이 정규분포를 갖는다고 가정한다. [단계 1]에서 상대적으로 품질이 좋은 해들을 골라냈고 어들해를 사용하여 [단계 2]에서 계산되는 거리로부터 유전자 간의 거리를 계산해 내었다.
- 이 연구에서는 오직 선형 인코딩만을 고려하였다. 비록 그것이 전통적이며 가장 많이 이용되는 인코딩이기 는 하지만, 다차원 인코딩 역시 유전 알고리즘 분야에서 각광받고 있다 [31, 32].
※ AI-Helper는 부적절한 답변을 할 수 있습니다.