세포진화 알고리즘
Cellular evolutionary algorithm세포 진화 알고리즘(cEA)은 개인이 임의로 짝짓기를 할 수 없는 일종의 진화 알고리즘(EA)이지만, 모두 기본 EA가 적용되는 가까운 이웃과 상호작용한다(선택, 변동, 대체).
셀룰러 모델은 개인의 관점에서 자연 진화를 시뮬레이션하는데, 이는 잠정적인 (최적화, 학습, 검색) 문제 해결책을 인코딩한다. 이 모델의 본질적인 아이디어는 EA 모집단에 연결된 그래프로 정의된 특별한 구조를 제공하는 것인데, 각 꼭지점은 가장 가까운 이웃과 소통하는 개인이다. 특히 개인은 개념적으로 토로이드 메쉬에 설정되며, 가까운 개인과 재결합만 허용된다. 이것은 우리를 거리에 의한 고립이라고 알려진 지역성으로 이끈다. 한 개인의 잠재적인 짝을 이웃이라고 부른다. 이런 종류의 알고리즘에서는 비슷한 개인들이 틈새를 만들어 클러스터링하는 경향이 있으며, 이들 집단은 마치 별개의 하위 집단(섬)인 것처럼 작용하는 것으로 알려져 있다. 어쨌든, 인접한 그룹들 사이에는 명확한 경계선이 없으며, 가까운 틈새들은 경쟁적 틈새에 의해 쉽게 식민지가 될 수 있고, 아마도 그 과정에서 솔루션 내용을 병합할 수도 있다. 동시에, 더 먼 틈새들은 더 천천히 영향을 받을 수 있다.
소개.
세포 진화 알고리즘(cEA)은 다른 토폴로지도 가능하지만, 일반적으로 개인의 구조화된 투타차원 그리드를 진화시킨다. 이 격자에서는 진화 과정에서 유사한 개인들의 클러스터가 자연스럽게 생성되어 그 경계에서 탐사를 촉진하는 한편, 착취는 주로 직접 경쟁과 그 내부의 융합에 의해 행해진다.
그리드는 치수의 수를 쉽게 (3D까지) 연장하거나 축소할 수 있지만(예: 고리 1D까지) 일반적으로 2D 토로이드 구조로 되어 있다. 그리드의 특정 지점(개인이 배치되는 위치)의 근방은 인구에서 다른 지점까지의 맨해튼 거리로 정의된다. 격자망의 각 지점에는 인근 개인들의 동네가 겹치는 동네가 있다. 기본 알고리즘에서, 모든 이웃들은 같은 크기와 같은 모양을 가지고 있다. 가장 많이 사용되는 두 동네는 폰 노이만(Von Neumann) 또는 NEWS(North, East, West, South)라고도 불리는 L5와 무어 동네로도 알려진 C9이다. 여기서 L은 Linear를, C는 Compact를 의미한다.
cEA에서 개인은 변이 연산자가 적용되는 생식 주기 동안에만 이웃과 상호작용할 수 있다. 이 생식 주기는 각 개인의 동네 안에서 실행되며, 일반적으로 일정한 기준에 따라 이웃 중에서 부모 2명을 선택하고, 그들에 변동 연산자를 적용(예를 들어, 재조합과 돌연변이)하며, 최근 생성된 자손이 고려된 개인을 대체하는 것으로 구성된다. 예를 들어, 주어진 기준은 자손이 고려된 개인보다 더 나은 해결책을 나타내는 경우 대체한다.
동기식/비동기식
정기적인 동기식 cEA에서 알고리즘은 새로운 임시 집단을 만들기 위해 모집단의 정보를 사용하여 왼쪽 맨 위의 맨 처음 개인을 오른쪽 상단으로, 그리고 그 다음 몇 개의 행으로 진행한다. 최하위 마지막 개인으로 마무리한 후 임시 모집단은 새로 계산된 개인들로 가득 차며 교체 단계가 시작된다. 그 속에서, 어떤 기준에 따라 구 인구는 완전하고 동시에 새로 계산된 인구와 대체된다. 일반적으로 대체자는 두 모집단의 같은 위치에 가장 우수한 개인을 유지한다. 즉 엘리트주의가 사용된다.
우리는 사용된 모집단의 업데이트 정책에 따라 비동기 cEA도 정의할 수 있다는 것을 알아야만 한다. 이것은 세포자동화에서도 잘 알려진 문제다. 비동기 cEA에서 그리드의 개체가 업데이트되는 순서는 사용된 기준(라인 스위프, 고정 랜덤 스위프, 새로운 랜덤 스위프 및 균일한 선택)에 따라 변경된다. 이것들은 가장 일반적인 네 가지 인구 갱신 방법이다. 그들 모두는 즉시 이웃의 계산을 위해 새로 계산된 개인(또는 더 나은 경우 원본)을 계속 사용한다. 이것은 매우 흥미로운 새로운 연구 라인을 정의하면서, 인구가 진화의 다른 상태에 있는 개인을 언제든지 보유하도록 만든다.
이웃들의 중첩은 cEA로의 솔루션 이동의 암묵적인 메커니즘을 제공한다. 최상의 해결책은 전체 모집단을 통해 원활하게 확산되기 때문에, 모집단의 유전적 다양성은 비구조적 EA보다 더 오래 보존된다. 인구를 통한 최선의 해결책의 이러한 부드러운 분산은 cEA가 탐색 중에 수행하는 탐사와 착취 사이의 좋은 절충의 주요 쟁점 중 하나이다. 그러면 우리가 이 트레이드오프를 조절할 수 있다는 것을 쉽게 알 수 있다(따라서, 예를 들어, 이웃 간의 겹치는 정도가 이웃의 크기에 따라 증가함에 따라, 사용되는 이웃의 크기를 수정(예를 들어, 유전적 다양성 수준을 조절한다).
cEA는 확률론적 다시 쓰기가 가능한 규칙을 가진 세포자동화(CA)로 볼 수 있으며, 여기서 CA의 알파벳은 문제의 해결책의 잠재적 수와 동일하다. 따라서 cEA를 CA의 일종으로 본다면 CA의 분야에서 cEA로 지식을 수입하는 것이 가능하며, 사실 이것은 흥미로운 개방형 연구 라인이다.
병렬주의
세포 EA는 병렬에 매우 순응하기 쉬우므로, 보통 병렬 메타휴리스틱스 문헌에서 찾아볼 수 있다. 특히 미세한 곡물 병렬은 모든 개인에게 독립적인 실행 스레드를 할당하는 데 사용될 수 있으므로 전체 cEA가 동시 또는 실제 병렬 하드웨어 플랫폼에서 실행될 수 있다. 이러한 방식으로 FPGA 또는 GPU에서 cEA를 실행할 때 큰 시간 단축을 얻을 수 있다.
그러나 cEA는 전통적인 EA와는 다른 많은 의미에서 검색의 모델이라는 것을 강조하는 것이 중요하다. 또한 순차적 플랫폼과 병렬 플랫폼으로 구동할 수 있어 모델과 구현이 서로 다른 개념이라는 점을 보강한다.
cEA의 이해, 설계 및 적용에 대한 기초에 대한 자세한 설명은 여기를 참조하십시오.
참고 항목
참조
- E.알바,B. 도론소로, 세포 유전 알고리즘, 스프링거-베를랙, ISBN978-0-387-77609-5, 2008
- A.J. 이웃, J.J. 뒤릴로, F. 루나, B. Dorronsoro, E. Alba, MOCell: 다목적 최적화를 위한 새로운 세포 유전 알고리즘, International Journal of Intelligent Systems, 24:726-746, 2009
- E.알바,B. 도론소로, F. Luna, A.J. 이웃, P. Bouvry, L. Hogie, Metropolitan MANETs, Computer Communications, 30 (4) 685-697, 2007
- E.알바,B. Dorronsoro, Cellular GA, Information Processing Letters, Exvier, 98(6):225-230, 2006년 6월 30일, Capaccessored VRP를 위한 9가지 새로운 Best-So-Far Solutions
- M. 지아코비니, M. 토마시니, A. Tettamanzi, E. Alba, 일반 래티스를 위한 셀룰러 진화 알고리즘의 선택 강도, IEEE Press, 9:489-505, 2005
- E.알바,B. Dorronsoro, 동적 세포 유전 알고리즘의 탐색/폭발 트레이드오프, IEEE Press, 9(2)126-142, 2005
