뻐꾸기 수색

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Cuckoo Search" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2015년 6월) (이 템플릿 메시지 제거 방법과 시기 알아보기)

운영연구에서 뻐꾸기 검색은 양신쉐와 수아쉬 뎁이 2009년 개발한 최적화 알고리즘이다.^[1][2] 그것은 일부 뻐꾸기 종들이 다른 종의 숙주새 둥지에 알을 낳음으로써 기생하는 의무적인 품종에서 영감을 얻었다. 어떤 숙주새는 침입한 뻐꾸기와 직접적인 충돌을 일으킬 수 있다. 예를 들어, 만약 주인 새가 알이 자신의 것이 아니라는 것을 발견한다면, 그것은 이 외계인 알들을 버리거나 단순히 둥지를 버리고 다른 곳에 새로운 둥지를 지을 것이다. 신세계 브로드-파라시틱 타페라 같은 일부 뻐꾸기 종은 암컷 기생 뻐꾸기들이 종종 선택된 소수의 숙주 종의 알의 색깔과 무늬에서 흉내 내는 것에 매우 전문적이 될 정도로 진화했다.^[3] 뻐꾸기 검색은 이러한 사육 행동을 이상화하여 다양한 최적화 문제에 적용할 수 있다. 뻐꾸기 수색은 잘 알려진(μ+λ) 진화 전략의 특수한 경우인 것으로 나타났다.^[4]

은유

뻐꾸기 검색(CS)은 다음과 같은 표현을 사용한다.

둥지에 있는 각각의 알은 해결책을 나타내고, 뻐꾸기 알은 새로운 해결책을 나타낸다. 목표는 새롭고 잠재적으로 더 나은 해결책(쿠쿠)을 사용하여 둥지에서 썩 좋지 않은 해결책을 대체하는 것이다. 가장 간단한 형태로, 각각의 둥지는 하나의 알을 가지고 있다. 알고리즘은 각 둥지가 솔루션 집합을 나타내는 여러 개의 알을 갖는 더 복잡한 경우로 확장될 수 있다.

CS는 세 가지 이상화된 규칙을 기반으로 한다.

1. 각 뻐꾸기는 한 번에 한 개의 알을 낳고, 그 알을 임의로 선택한 둥지에 버린다.
2. 고품질의 달걀을 가진 최고의 둥지는 다음 세대로 넘어간다.
3. 이용 가능한 숙주 둥지의 수는 고정되어 있고, 뻐꾸기가 낳은 알은 개연성 p ${\displaystyle a_{})}$( $0{\displaystyle {}_{},}$ ${\displaystyle 1}$ $){\displaystyle p_{a}\in (0,1$)을 가진 숙주새에 의해 발견된다$.$이 경우 숙주새는 알을 던져/둥지에 버리고 완전히 새로운 둥지를 지을 수 있다.

게다가, 양과 뎁은 무작위 보행 방식의 검색이 단순한 무작위 보행보다는 레비 비행에 의해 더 잘 수행된다는 것을 발견했다.

알고리즘.

의사 코드는 다음과 같이 요약할 수 있다.

객관적인 기능:f()),))(x1x2,…,)d);{\displaystyle f(\mathbf{x}),\quad \mathbf{)}=(x_{1},x_{2},\dots ,x_{d}), \,}n{n\displaystyle}호스트 둥지의 초기 인구를 발생시키다.;는 동안(t<,에서는 MaxGeneration)또는(기준을 멈추)는 뻐꾸기 무작위로(, 말하)에 의해 그것의 해법을 대체하다.페rforming Lévy flights;    Evaluate its quality/fitness ${\displaystyle F_{i}}$          [For maximization, ${\displaystyle F_{i}\propto f(\mathbf {x} _{i})}$ ];    Choose a nest among n (say, j) randomly;    if (${\displaystyle F_{i}>$$F_{j}}}),$ j를 새 솔루션으로 교체; 더 나쁜 둥지의 A 부분(${\displaystyle p_{}}$ ${\$이 버려지고 새 둥지가 구축되면 종료; 최상의 솔루션/둥지를 유지; 솔루션/둥지 순위를 매기고 현재 최상의 솔루션을 다음 세대에 전달; 종료하는 동안 

이 알고리즘의 중요한 장점은 단순성이다. 실제로 입자 군집 최적화, 조화 검색과 같은 다른 모집단 또는 에이전트 기반 메타휴리스틱 알고리즘과 비교했을 때 CS(인구 크기 $n{\displaystyle }$ ${\displaystyle n}$과는 별개로)에는$$ 기본적으로 단일 파라미터 $p{\displaystyle {}_{}}$ ${\displaystyle a_{}}$ ${\$밖에 없다.$$ 그러므로, 그것은 실행하기가 매우 쉽다.

랜덤 워크 및 스텝 크기

중요한 문제는 새로운 해결책을 도출하기 위한 일반 방정식에서 레비 비행과 무작위 보도의 적용이다.

${\displaystyle \mathbf {x} _{t+1}=\mathbf {x} _{t}sE_{t}}}$

여기서 $E{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$는 무작위 보행에 대한 평균과 일률 표준 편차가 0인 표준 정규 분포에서 추출하거나$$, 레비 항공편의 경우 레비 분포에서 추출한다. 분명, 무작위 산책은 또한 뻐꾸기의 알과 숙주의 알 사이의 유사성과 연관될 수 있는데, 이것은 실행하는데 까다로울 수 있다. 여기서 단계 크기 $s{\displaystyle }$ ${\displaystyle s}$는 임의의 보행자가 일정한 반복 횟수를 위해 얼마나 멀리 갈 수 있는지를 결정한다$$. 레비 스텝 크기의 세대는 종종 까다로우며, 필요한 무작위 숫자의 수가 적기 때문에 챔버스 등의 접근방식의^[7] 구현이 가장 계산적으로 효율적이라는 것을 발견한 레카르디에^[6] 의해 세 가지 알고리즘(만테그나^[5] 포함)의 비교가 수행되었다.

s가 너무 크면 생성된 새 솔루션은 이전 솔루션에서 너무 멀리 떨어져 있거나(또는 범위를 벗어나기도 한다) 있을 것이다. 그렇다면 이런 움직임은 받아들여질 것 같지 않다. s가 너무 작으면 변화가 너무 작아 유의미하지 않으며, 따라서 그러한 검색은 효율적이지 않다. 따라서 검색을 최대한 효율적으로 유지하기 위해서는 적절한 단계 크기가 중요하다.

예를 들어, 단순 등방성 무작위 보행의 경우 d-dimension 공간에서 $이동$된 평균 r$${\$displaystyle$ r$}$ 거리는

${\displaystyle r^{2}=2Dt,}$

여기서 $D{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \tau }$ ${\displaystyle D=s^{2}/2\tau }$은(는) 유효 확산 계수다. 여기서 $s{\displaystyle }$ ${\displaystyle s}$은(는) 각 점프에서 스텝 크기 또는 이동 거리이고$$, $\tau {\displaystyle }$ ${\displaystyle \tau$ }은$($는) 각 점프에 걸리는 시간이다. 위의 방정식은 다음을^[8] 함축하고 있다.

${\displaystyle s^{2}={\frac {\\tau \;r^{2}}:{t\;d}}.}$

For a typical length scale L of a dimension of interest, the local search is typically limited in a region of ${\displaystyle r=L/10}$. For ${\displaystyle \tau =1}$ and t=100 to 1000, we have ${\displaystyle s\approx 0.01L}$ for d=1, and ${\displaystyle s\approx 0.001L}$ for d=10. 따라서 대부분의 문제에 대해 s/L=0.001 ~ 0.01을 사용할 수 있다. 정확한 파생은 레비 비행의 행동에 대한 상세한 분석이 필요할 수 있다.^[9]

메타휴리스틱스 관련 개방형^[10] 문제가 많기 때문에 알고리즘과 융합분석이 효과적일 것이다.

이론적 분석

CS 기반 알고리즘의 성능 향상을 위한 이론적 분석은 상당한 노력이 필요하다.^[11]

1. CS 기반 알고리즘의 융합에 관한 이론적 분석
2. 제어 매개변수 설정에 충분하고 필요한 조건 제공
3. 기존 CS 알고리즘을 향상시키기 위해 비균형 검색 규칙 채택

향상된 뻐꾸기 검색 알고리즘

뻐꾸기 검색 알고리즘의 융합은 (원래 방식에서 무작위 교체를 사용하는 대신) 버려진 둥지를 유전적으로 대체함으로써 실질적으로 개선될 수 있다.^[12] 알고리즘에 대한 수정은 또한 최상의 (고품질) 둥지의 추가 교배에 의해 이루어졌으며 이 접근법은 다양한 산업 최적화 문제에 성공적으로 적용되었다.^[14][15]

참조