초록 ▼

본 발명에서는 엔트로피 샘플링을 이용한 유전자-엔트로피 알고리즘을 제안하였다. 엔트로피 샘플링에 기초한 이 알고리즘은 임의의 배열이 선택될 확률을 그 배열의 엔트로피에 의존하게 함으로 주어진 시스템의 전 에너지(혹은 fitness) 영역을 균일한 확률로 선택하게 한다. 이러한 엔트로피 샘플링은 주어진 시스템의 국소 최소치를 보다 쉽게 빠져 나올 수 있다는 장점이 있으며 따라서 전체 최소치(혹은 최대치)를 보다 효과적으로 찾아갈 수 있다. 특히 이 알고리즘은 국소 최소치가 많은 문제의 최적화에 적합하며 그 효과를 NK-모델에 적용하여

본 발명에서는 엔트로피 샘플링을 이용한 유전자-엔트로피 알고리즘을 제안하였다. 엔트로피 샘플링에 기초한 이 알고리즘은 임의의 배열이 선택될 확률을 그 배열의 엔트로피에 의존하게 함으로 주어진 시스템의 전 에너지(혹은 fitness) 영역을 균일한 확률로 선택하게 한다. 이러한 엔트로피 샘플링은 주어진 시스템의 국소 최소치를 보다 쉽게 빠져 나올 수 있다는 장점이 있으며 따라서 전체 최소치(혹은 최대치)를 보다 효과적으로 찾아갈 수 있다. 특히 이 알고리즘은 국소 최소치가 많은 문제의 최적화에 적합하며 그 효과를 NK-모델에 적용하여 그 우수성을 입증하였다.

대표청구항 ▼

일정 배열이 국소 최소치에 빠지지 않도록 엔트로피 샘플링 방법을 도입한 최적화 알고리즘에 있어서,초기 엔트로피 분포를 구하는 제 1 단계와;메트로폴리스 알고리즘 적용을 위한 N개의 배열을 임의로 선택하여 초기 모집단으로 두고, 그 중에서 한 개의 배열을 임의로 선택하여 그 배열의 에너지와 엔트로피를 계산하는 제 2 단계와;상기 모집단으로부터 조상을 임의로 추출하여 교차 연산자 및 돌연변이 연산 자를 적용하여 생긴 자손중 임의로 자손을 선택하는 제 3 단계와;상기 구해진 자손들을 새로운 모집단으로 형성한 후 엔트로피를 개정할 때까

일정 배열이 국소 최소치에 빠지지 않도록 엔트로피 샘플링 방법을 도입한 최적화 알고리즘에 있어서,초기 엔트로피 분포를 구하는 제 1 단계와;메트로폴리스 알고리즘 적용을 위한 N개의 배열을 임의로 선택하여 초기 모집단으로 두고, 그 중에서 한 개의 배열을 임의로 선택하여 그 배열의 에너지와 엔트로피를 계산하는 제 2 단계와;상기 모집단으로부터 조상을 임의로 추출하여 교차 연산자 및 돌연변이 연산 자를 적용하여 생긴 자손중 임의로 자손을 선택하는 제 3 단계와;상기 구해진 자손들을 새로운 모집단으로 형성한 후 엔트로피를 개정할 때까지 반복하여 되풀이 하여 히스토그램을 누적하는 제 4 단계와;상기 누적된 히스토그램에 기초한 새로운 엔트로피를 결정하는 제 5 단계와;상기 계산된 새로운 엔트로피 값으로 소정의 횟수 동안 상기 제 3 단계 내지 제 5 단계를 반복하는 제 6 단계로 이루어진 것을 특징으로 하는 엔트로피 샘플링을 사용한 유전자-엔트로피 알고리즘.제 1 항에 있어서,상기 제 1 단계는 무작위로 구한 적당한 개수의 배열로부터 에너지를 계산하고, 그 계산된 에너지에 따른 엔트로피를 구하는 것을 특징으로 하는 엔트로피 샘플링을 사용한 유전자-엔트로피 알고리즘.제 1 항에 있어서,상기 제 3 단계는 선택된 자손의 에너지 E(x')와 엔트로피 S(E(x'))를 계산하여 기준되는 엔트로피 S(E(x))와 비교하여 새로운 자손을 선택할 확률을 하기 수학식 (5)에 의해 결정하는 것을 특징으로 하는 엔트로피 샘플링을 사용한 유전자-엔트로피 알고리즘.(수학식 5)r=W(x→x′)W(x′→x)=exp(S(E(x))-S(E(x′)))(만약 r≥1이면 새로운 배열 x'을 선택하고, r<1이면 새로운 배열 x'는 확률 r로 선택함)제 3 항에 있어서,상기 새로운 자손을 채택할 확률이 채택될 경우에는 채택된 배열의 에너지에 해당하는 히스토그램 H(E(x'))을 누적하고, 채택된 배열의 엔트로피를 기준되는 엔트로피로 정하고, 채택되지 않을 경우에는 다시 자손을 구하여 그 자손의 엔트로피와 기준되는 엔트로피와 비교하는 것을 특징으로 하는 엔트로피 샘플링을 사용한 유전자-엔트로피 알고리즘.제 1 항에 있어서,상기 제 3 단계는 자손들을 직렬적으로 추가하는 것을 특징으로 하는 엔트로피 샘플링을 사용한 유전자-엔트로피 알고리즘.