확률적 확산 탐색

Stochastic diffusion search

확률적 확산 검색(SDS)은 1989년에 처음으로 인구 기반 패턴 매칭 알고리즘으로 설명되었다.[1]그것은 개미 군집 최적화, 입자 군집 최적화 및 유전 알고리즘을 포함하는 군집 지능과 자연적으로 영감을 받은 검색 및 최적화 알고리즘에 속한다. 그러한 SDS가 최초의 군집 지능 메타휴리스틱이었기 때문이다.시뮬레이션 환경의 물리적 특성 수정에 기반한 개미 군집 최적화에 채택된 오명 통신과 달리, SDS는 한 종의 개미인 렙토토락스 아큐르보룸이 채택한 탠덤 호출 메커니즘과 유사한 에이전트 간 직접적(일대일) 통신의 형태를 사용한다.

SDS에서 에이전트는 가설(검색 문제에 대한 후보 솔루션)에 대해 값싸고 부분적인 평가를 수행한다.그런 다음 직접적인 일대일 커뮤니케이션을 통해 가설(정보의 확산)에 대한 정보를 공유한다.확산 메커니즘의 결과, 동일한 가설을 가진 에이전트 군집으로부터 고품질 솔루션을 식별할 수 있다.SDS의 운영은 간단한 비유로 가장 쉽게 이해할 수 있다 – The Laste Game.

레스토랑 게임

한 무리의 대표단이 낯선 마을에서 열린 긴 회의에 참석한다.매일 밤 각 대의원은 식사할 곳을 찾아야 한다.다양한 식당을 선택할 수 있으며, 각 식당은 매우 다양한 식사를 제공한다.이 단체가 직면한 문제는 최고의 식당, 즉 최대 수의 대표들이 식사를 즐길 수 있는 레스토랑을 찾는 것이다.식당과 식사 조합을 병행해서 검색해도 너무 오래 걸릴 것이다.문제를 해결하기 위해 대표단은 확률적 확산 검색을 채택하기로 결정한다.

각 대표들은 마을에서 가장 좋은 레스토랑을 식별하는 가설을 유지하는 대리인 역할을 한다.매일 밤 각 대표들은 그곳에서 식사를 하고 제공되는 식사 중 하나를 무작위로 선택하여 그의 가설을 시험한다.다음날 아침 아침, 전날 밤 식사를 즐기지 못한 모든 대표들은 무작위로 선발된 동료 한 명에게 저녁식사 소감을 공유해 달라고 요청한다.경험이 좋으면 이 식당도 자신의 선택으로 삼는다.그렇지 않으면 그는 'Yellow Pages'에 열거된 레스토랑 중에서 무작위로 다른 레스토랑을 고를 뿐이다.이 전략을 사용하여 매우 빠른 속도로 상당한 수의 딜러가 시내에서 가장 '최고의' 레스토랑에 모인다는 것을 알 수 있다.

적용들

SDS는 텍스트 검색 [비숍, 1989년], 객체 인식[비숍, 1992년], 특징 추적[Grech-Cini, 1993년], 모바일 로봇 자기 지역화[Beattie, 1998년], 무선 네트워크 사이트 선택 등 다양한 문제에 적용되어 왔다[Whitaker, 2002년].

분석

많은 Nature Inspected Search 기법과는 달리 SDS의 행동을 기술하는 종합적인 수학 프레임워크가 있다. SDS의 분석은 SDS의 글로벌 최적성과 수렴성[Nasuto, 1998년], 선형 시간 복잡성[Nasuto 등, 1999년], 견고성[Myatt, 2004년], 그리고 다양한 검색 하에서 자원 할당 [Nasuto, 1999년]을 조사했다.조건들

참조

  1. ^ 1989년 주교 329-331페이지
  • Bishop, J.M. (1989). "Stochastic Searching Networks" (PDF). Proc. 1st IEE Conf. on Artificial Neural Networks. London: 329–331.
  • 비숍, J.M. & Torr, P., (1992)확률적 검색 네트워크.R. 링가드, D.J. 마이어스, C.에서.나이팅게일(eds), 이미지, 음성 및 자연 언어를 위한 신경 네트워크, pp370–387, 뉴욕, 채프먼 & 홀.
  • Beattie, P.D. & Bishop, J.M., (1998년)'세나리오' 자율 휠체어의 자기 지역화.Kluwer Academic Publishes of Intelligent and Robotic Systems 22, 페이지 255–267.
  • Grech-Cini, H.J. & McKee, G.T.(1993) 사람 얼굴 이미지에서 입 부위 찾기P.S.에서.Schenker (Ed.) – The International Society for Optical Engineering, Sensor Fusion VI 2059, Massachusetts.
  • 마얏트, D.R., 비숍 J.M.과 나스토, S.J., (2004)확률적 확산 검색을 위한 최소 안정적 수렴 기준은 전자 공문에 게재된다.
  • 나스토, S.J. (1999년)확률적 확산 검색의 자원배분 분석박사 논문.영국의 독서 대학교
  • 나스토, S.J. & 비숍, J.M. (1999년)확률적 확산 탐색의 수렴해석병렬 알고리즘 및 응용 프로그램 저널 14:2, 페이지 89–107.
  • 나스토, S.J. 비숍, J.M.&로리아, L., (1998년)확률적 확산 검색의 시간 복잡성98년 오스트리아 빈, 뉴럴 연산
  • 휘태커, R.M. 헐리, S. (2002)무선 네트워크를 위한 사이트 선택에 대한 에이전트 기반 접근 방식.ACM 응용컴퓨팅 심포지엄(Madrid)을 진행하십시오.574–577.
  • 존스 씨(2002년).제한된 확률적 확산 검색.2002년, 영국 독서대학교.