비동기식 셀룰러 오토매틱

다른 멀티에이전트 시스템 모델과 마찬가지로 셀룰러 오토마타는 일반적으로 시간을 이산형 및 상태 업데이트로 처리하며 동시에 발생하는 것으로 간주한다.모델에 있는 모든 세포의 상태는 새로운 상태가 다른 세포에 영향을 미치기 전에 함께 업데이트된다.대조적으로, 비동기 세포 자동화는 셀의 새로운 상태가 인접한 셀의 상태 계산에 영향을 미치는 방식으로 개별 셀을 독립적으로 업데이트할 수 있다.

동기식 업데이트 구현은 두 단계로 분석할 수 있다.첫 번째 상호작용은 인접성과 업데이트 규칙을 기반으로 각 셀의 새 상태를 계산한다.상태 값은 임시 저장소에 보관된다.두 번째 단계는 새 상태를 셀에 복사하여 상태 값을 업데이트한다.

이와는 대조적으로, 비동기 업데이트는 반드시 이 두 단계를 구분하지 않는다: 가장 단순한 경우(완전히 비동기 업데이트)에서는 상태 변경이 즉시 구현된다.

동기식 접근방식은 모든 셀이 함께 업데이트되도록 하기 위한 글로벌 시계의 존재를 가정한다.컴퓨터 시스템을 준비하는데 편리하지만, 예를 들어, 모델이 그러한 장치가 존재한다는 증거가 없는 살아있는 시스템을 나타내도록 의도된 경우 이는 비현실적인 가정일 수 있다.

(K에 의해) 독자적으로 발견되는 일반적인 방법.1970년대 나카무라, T.1980년대 토폴리와 1998년 C. L. Nehaniv에 의해)는 동기식 세포 자동화의 단순한 수정으로 구성된 비동기식 세포 자동화를 통해 동기식 세포 자동화의 동작을 정확히 모방할 수 있게 한다(Nehaniv 2002).그러나 이 방법의 정확성은 최근에 더 엄격하게 증명되었다.결과적으로, 비동기 세포 자동화가 보편적 계산의 콘웨이 게임, 그리고 자기복제(예: Von Neumann Universal constructor에서와 같이)와 같은 에뮬레이션이 가능한 동기식 세포 자동화에 대한 결과로부터 바로 따라온다.더욱이 일반구축과 증빙은 보다 일반적인 동기식 오토마타 네트워크(특수 사례로 셀룰러 오토마타를 포함하는 외부 입력을 허용하는 지시된 그래프에 걸친 오토마타의 이종 네트워크)에도 적용되며, 이에 대응하여 그들의 행동이 비동기적으로 실현되는 방법을 건설적으로 보여준다.비동기식 오토마타 네트워크.

구성표 업데이트

몇몇 연구에서는 비동기 모델을 구현했고 그들의 행동이 동기 모델과 다르다는 것을 발견했다.베르시니와 데쿠르(1994)는 콘웨이의 게임 오브 라이프(Game of Life)가 업데이트 계획에 얼마나 민감한지를 보여줬다.어떤 흥미로운 행동도 비동기적인 경우에서 사라진다.Harvey와 Bosomaier(1997)는 무작위 부울 네트워크에서의 확률적 업데이트는 점 유치기의 표현만을 초래한다고 지적했다. 느슨한 순환유도기의 개념을 도입했지만 반복 가능한 순환행동은 없다.카나다(1994)는 업데이트 시 비차오틱 패턴을 생성하는 일부 1차원 CA 모델에서 무작위화 시 혼돈 패턴의 가장자리가 동시에 생성된다는 것을 보여주었다.오르포넨(1997)은 업데이트 순서에 제약이 없는 네트워크에 의해 동기적으로 업데이트된 임계값 논리 단위 네트워크(인공 뉴런 참조)를 시뮬레이션할 수 있음을 입증했다.Siper 외 연구진(1997)은 특정 컴퓨팅 작업을 수행하는 불균형 CA의 진화를 조사했다.이러한 모델은 동일한 업데이트 규칙을 가진 모든 노드의 일반적인 요구 사항을 완화한다.그들의 모델에서, 노드는 블록으로 조직되었다.블록 내의 노드는 동기적으로 업데이트되었지만 블록은 비동기적으로 업데이트되었다.그들은 세 가지 방법으로 실험을 했다: (1) 각 단계마다, 블록을 교체와 함께 무작위로 선택한다. (2) 각 단계마다, 교체 없이 무작위로 선택된다. (3) 각 단계마다, 블록은 고정된 업데이트 순서에 따라 선택된다.

비동기 업데이트의 종류는 다양하며, 저자들마다 이것을 다른 방식으로 설명하였다.아래 이미지에 표시된 구성은 다음과 같다(Cornforth et al. 2005).

• 동기식 계획 - 모든 셀은 각 시간 단계에서 병렬로 업데이트된다.이것은 비교를 위해 여기에 언급된 전통적인 모델이다.
• 무작위 독립 계획 - 각 시간 단계에서 셀을 교체와 함께 무작위로 선택하고 업데이트한다.
• 임의 순서 체계 - 각 단계에서 모든 노드가 임의 순서로 업데이트된다.
• 주기적 체계 - 각 단계에서 고정된 업데이트 순서에 따라 노드가 선택되며, 이 순서는 모델 초기화 중에 무작위로 결정된다.
• 자체 클럭 방식 - 각 셀에는 임의의 기간과 위상에 초기화되는 독립 타이머가 있다.기간이 만료되면 셀이 업데이트되고 타이머가 재설정된다.업데이트는 자율적이며 세포마다 다른 속도로 진행된다.
• 자체 동기화 방식 - 시계 방식과 동일하지만 타이머의 위상은 인접 네트워크와의 국소 결합에 의해 영향을 받으므로 국소 동기화를 달성할 수 있다.

아래의 시간 상태 다이어그램은 다른 파라미터를 변경하지 않고 셀룰러 오토마타 모델의 업데이트 체계를 변경함으로써 발생하는 차이를 보여준다.사용된 규칙인 규칙 30은 각 다이어그램에 대해 동일하다.

원래 규칙 30	규칙 30이 임의로 업데이트됨
규칙 30이 임의의 순서로 업데이트됨	규칙 30이 주기적 순서로 업데이트됨
자동 시계 규칙 30	자가 동기화 규칙 30

시사점

셀룰러 오토마타와 같은 모델은 실생활에서 작용하는 과정을 이해하는 데 도움을 주기 위해 종종 사용된다.단순화된 모델을 구축함으로써 새로운 통찰력을 배울 수 있다.모델링되고 있는 것을 적절히 설명하기 위해 이러한 모델들이 얼마나 단순해야 하는가에 대한 의문이 항상 있다.비동기 모델의 사용은 모델에서 추가적인 리얼리즘 수준을 허용할 수 있다.위에서 설명한 모든 계획은 실생활에서 그 역할을 한다.무작위 독립 체계는 소셜 네트워크나 컴퓨터 네트워크의 통신을 모델링하는 데 적합할 수 있다.시계로 표시된 계획은 곤충 군집을 모델링하는 데 적합할 수 있는 반면, 자기 동기화 계획은 신경 조직에 적용될 수 있다.

참조

• H. Bersini와 V.1994년 우회전비동기식은 셀룰러 오토마타 기반 모델인 인공생명체에 관한 IVth Conference의 Procedures , 382-387페이지, 캠브리지, MA, 1994년 7월, vol 204, no. 1-2, pp. 70-82페이지에서 안정성을 유도한다.
• Cornforth, D, Green, D & Newth, D 2005, Multi-Agent Systems의 비동기 프로세스 주문, Physica D, vol 204, no. 1-2, 페이지 70-82.
• 콘포스, D, 그린, DG, 뉴트 D&Kirley M 2002, 인조개미가 스텝을 밟으며 행진하는가? 생물학적 시스템의 비동기 프로세스 및 모듈화 순서.스탠디시, 베다우, 압바스, 시드니 인공생명체에 관한 제8차 국제회의의 진행, 28-32페이지
• Fatés N, (2014), 비동기 셀룰러 오토마타 안내 여행, 셀룰러 오토마타 저널: Vol. 9(5-6), 페이지 387-416, 사전 인쇄
• Fatés N, and Morvan M, (2005) 기초 세포 자동자, 복합 시스템의 비동기화에 대한 강인성에 대한 실험적 연구: 제16권 / 제1호, 페이지 1-27.
• 파테스 N, 모반 M, N. 샤바넬, E.티에리, (2006), 2쿼터 초급 셀룰러 오토마타의 완전 비동기 동작, 이론 컴퓨터 과학:362, 페이지 1 - 16.
• 하비 1세, 그리고 보소마이어 T.R.J. (1997년)접합 시간 초과:비동기 부울 네트워크의 유인기.남편들과 하비 (eds.)에서, 인공 생명에 관한 제4차 유럽 회의의 진행, 67-75, MIT 프레스.
• 카나다 Y. (1994년).비동기식 1D 셀룰러 오토마타에서의 무작위성의 영향인공 생명체 4호
• Nehaniv, C. L. (2002)비동기식 셀룰러 오토마타에서의 진화, 인공생명 VIII, 65-73, MIT 프레스.
• Nehaniv, C. L. (2004).비동기식 오토마타 네트워크는 모든 동기식 오토마타 네트워크를 에뮬레이트할 수 있다, 국제 대수학 및 연산 저널, 14(5-6):719-739.
• 오포넨, P. (1997)진정한 비동기 임계값 로직 네트워크를 사용한 컴퓨팅.이론 컴퓨터 과학 174(1-2):123-136.
• Siper M, Tomassini M., Capcarree M.S. (1997년)진화하는 비동기식 확장형 비동기식 셀룰러 오토마타.프롤 오브 인터. 인공신경망과 유전자 알고리즘에 관한 콘퍼런스, 스프링거-베를랙.
• 모나시 대학의 가상 연구소 세포 자동화의 비동기 업데이트 시뮬레이션.