최소 모집단 검색

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2017년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

진화론적 계산에서 최소 모집단 검색(MPS)은 주어진 품질의 척도와 관련하여 후보 솔루션 집합을 반복적으로 개선하려고 시도함으로써 문제를 최적화하는 계산 방법이다.비교적 간단한 산술 연산을 통해 소수의 후보 솔루션을 진화시킴으로써 문제를 해결한다.

MPS는 최적화되는 문제에 대해 거의 또는 전혀 가정을 하지 않으며 매우 넓은 범위의 후보 솔루션을 검색할 수 있기 때문에 메타휴리스틱이다.일정한 시간 내에 수용 가능한 국소 최적치를 찾는 것보다 정밀한 글로벌 최적화를 찾는 것이 덜 중요한 문제의 경우, MPS와 같은 메타휴리스틱을 사용하는 것이 짐승 같은 힘 검색이나 구배 강하와 같은 대안보다 더 바람직할 수 있다.

MPS는 다차원 실제 가치 함수에 사용되지만 최적화되는 문제의 구배를 사용하지 않으며, 이는 구배 강하 및 준 뉴턴 방법과 같은 고전적 최적화 방법에서 요구하는 대로 최적화 문제가 달라질 수 있도록 MPS가 필요하지 않다는 것을 의미한다.따라서 MPS는 연속적이지도 않고, 소음이 심하며, 시간에 따른 변화 등 최적화 문제에도 사용할 수 있다.

배경

MPS는 미분진화와 유사한 방법으로 새로운 해결책을 도출하기 위해 모집단 구성원들 간의 차이 벡터를 사용한다.적은 인구 규모를 유지함으로써 기능 평가의 효율적인 이용을 도모한다.모집단 크기가 검색 공간의 치수보다 작으면 $차이{\displaystyle }$ 벡터를 통해 생성된 솔루션은 n${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1}$ 치수$$ 하이퍼플레인으로 제한된다.인구 규모가 작을수록 하위 공간이 더 제한될 것이다.모집단 크기가 문제의 치수성과${\displaystyle \mathrm{동일}}$한${\displaystyle }$경우${\displaystyle (n}$ = d ) ${\디스플레이 스타일(n=$${\displaystyle \mathrm{d}}$$)\},$ $D{\displaystyle }$- 1 ${\디스플레이$ 스타일 d-1$}$ 치수$$ 하이퍼플레인 $내$에서 MPS의 "라인/하이퍼플레인 포인트"가 생성된다.이 하이퍼플레인과 직교하는 단계를 밟으면 검색 프로세스가 검색 공간의 모든 차원을 커버할 수 있다.^[1]

모집단 크기는 모집단 기반 휴리스틱스 수행의 기본 매개변수다.인구가 많을수록 탐사를 촉진하지만, 세대도 줄어들게 되고, 이로 인해 융합 가능성이 낮아질 수 있다.적은 인구를 대상으로 검색하면 융합 가능성이 높아지고 기능평가의 효율적 활용도 높아질 수 있지만 조기융합 위험도 유도할 수 있다.조기 수렴의 위험을 피할 수 있다면, 모집단 기반 휴리스틱스는 더 작은 모집단의 효율성과 더 빠른 융합률의 혜택을 받을 수 있다.조기 융합을 피하려면 인구 다변화가 중요하다.다양성과 탐구를 명시적으로 증가시키는 기법을 포함시킴으로써, 조기 수렴의 위험이 적은 더 작은 모집단을 가질 수 있다.^[1]

타작권 컨버전스

탈곡기 컨버전스(TC)는 탐구와 착취의 과정을 분리하려는 다각화 기법이다.TC는 최소 검색 단계를 설정하기 위해 "임계" 기능을 사용하며, 이 단계를 관리하면 탐색에서 착취로의 전환에 영향을 미칠 수 있으므로 검색 프로세스의 마지막 단계까지 정합화가 "보류"된다.^[2]통제된 전환의 목표는 몇몇 검색 지역 주변의 인구 집중을 조기에 피하고 조기 수렴을 유발할 수 있는 다양성의 손실을 피하는 것이다.Triachold Convergence는 입자 군집 최적화,^[3] 미분 진화, 진화 전략,^[4] 시뮬레이션 어닐링^[5] 및 분포 알고리즘 추정과 같은 몇몇 인구 기반 메타휴리스틱스에 성공적으로 적용되었다.

Trichhhold Convergence의 이상적인 경우는 각 유원지로부터 하나의 표본용액을 갖는 것이며, 각 표본용액은 국소적 최적성과 관련하여 동일한 상대적 적합성을 갖는 것이다.최소 단계를 시행하는 것은 이 이상적인 경우를 달성하는 것을 목표로 한다.MPS Trichhold Convergence는 최소 검색 단계를 설정하여 다양성을 보존하고 조기 융합을 피하기 위해 특별히 사용된다.TC는 현재 인구 구성원에 너무 가까운 새로운 해결책을 허용하지 않음으로써 (소규모) 인구의 다양성을 보존하면서 탐색 초기 단계에서 강력한 탐사를 강요한다.

알고리즘.

MPS 알고리즘의 기본 변형은 문제의 치수와 같은 크기의 모집단을 갖는 것으로 작동한다.새로운 솔루션은 (차이 벡터를 통해) 현재 솔루션에 의해 정의된 하이퍼 평면을 탐색하고 이 하이퍼 평면에 걸리지 않기 위해 추가 직교 단계를 수행함으로써 생성된다.계단 크기는 Trichhold Convergence 기법에 의해 제어되며, 이것은 검색 과정이 진행됨에 따라 단계 크기를 점차 감소시킨다.

알고리즘의 개요는 다음과 같다.

• 첫 번째 초기 모집단을 생성하십시오.Allowing these solutions to lie near the bounds of the search space generally gives good results: ${\displaystyle s_{k}=(rs_{1}*bound_{1}/2,rs_{2}*bound_{2}/2,...,rs_{n}*bound_{n}/2)}$ where ${\displays$$tyle s_{k}}$는 $k{\displaystyle }$ ${\displaystyle k}$ -th$$ 모집단 멤버, r ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 -1 또는 1일 수 있는 난수$$, $b{\displaystyle }$ ${\displaystyle o}$ ${\displaystyle \mathrm{un}}$ d ${\displaystyle i_{}}$ ${\$는 각 차원에 대한 하한 및 상한이다$$.
• 정지 조건에 도달하지 않은 경우:
• 임계값 수렴 값 업데이트(${\displaystyle }$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle \mathrm{\_}}$ ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle min\_step}$ 및$$ $m{\displaystyle }$ ${\displaystyle a}$ ${\displaystyle \_}$ s ${\displaystyle \_}$ s ${\displaystyle e}$ ${\displaystyle p}$ ${\displaystyle max\_step$
• 현재 모집단의 중심(${\displaystyle {}_{}}$ ${\displaystyle c_{}}$ ${\$ 계산
• 모집단의 각 구성원(${\displaystyle {xi}_{}}$ ${\$에 대해 다음과 같이 새 자식을 생성한다.$$
  • ${\displaystyle \mathrm{-m}}$ a ${\displaystyle \mathrm{\_}}$ ${\displaystyle e}$ ${\displaystyle p}$ ${\displaystyle -max\_step}$과($와$$){\displaystyle }$ x ${\displaystyle \mathrm{\_}}$ s ${\displaystyle e}$ p ${\$displaystyle -max\_step} 사이에 균일하게 스케일링 계수(${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$$displaystystyle max\_step})$를 생성함
  • $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$$displaystyle x_{o$와(와) $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ {\$displaystyle x_{i}$ 사이의 차이 벡터에 직교하는 벡터 생성(${\displaystyle {}_{}}$$$${\displaystyle o_{}}$ ${\$$displaystyle x_{c})$
  • 직교 벡터에 대한 스케일링 계수 계산:
    • ${\displaystyle min\_orts=sqrt(max(min\_step^{2}-F_{i}^{2},0))}$
    • ${\displaystyle max\_orts=sqrt(max\_step^{2}-F_{i}^{2},0)}$
    • ${\displaystyle orth\_step=in\_step(min\_stard,max\_stod)}$
  • 원래 솔루션에 차이와 직교 벡터를 추가하여 새 솔루션 생성
    • ${\displaystyle new\_buffer=x_{i}+F_{i}*(x_{i}-x_{c})*정기\_step*x_{o}}$
• 가장 적합하지 않은 구성원을 삭제하여 이전 모집단과 새 모집단 중 가장 적합한 구성원을 선택하십시오.
• 단일 최적 솔루션 또는 최종 결과로 발견된 최적 모집단을 반환하십시오.

참조

외부 링크

• 참조 구현