최소 충돌 알고리즘

Min-conflicts algorithm

컴퓨터 과학에서 min-conflicts 알고리즘은 제약조건 만족 문제를 해결하기 위한 검색 알고리즘 또는 경험적 접근법이다.

제약조건 만족도 문제의 모든 변수에 값을 처음 할당하면 알고리즘은 하나 이상의 제약조건을 위반하는 충돌이 있는 변수 집합에서 변수를 무작위로 선택한다.[1]그런 다음 이 변수에 충돌 횟수를 최소화하는 값을 할당한다.최소 충돌 횟수가 있는 값이 둘 이상일 경우 임의로 하나를 선택한다.무작위 변수 선택 및 최소 충돌 값 할당 프로세스는 해결책이 발견되거나 사전 선택된 최대 반복 횟수에 도달할 때까지 반복된다.

제약조건 만족도 문제는 모든 변수에 할당된 값(완전 상태라고 함)이 있을 때 국지적 검색 문제로 해석될 수 있기 때문에 최소 충돌 알고리즘은 최소 충돌 횟수로 상태를 선택하는 수리 휴리스틱으로[2] 볼 수 있다.

알고리즘.

알고리즘 MIN-CONFLICTS 입력: console.csp, A 제약조건 만족도 문제. max_step, 포기 전 허용되는 단계 수 current_state, csp 내 변수에 대한 값의 초기 할당.출력:변수 또는 실패에 대한 값 집합 솔루션.i ← 1 ~ max_step은 csp의 솔루션인 경우 current_state set var ← 상충 변수 집합에서 무작위로 선택한 변수 CONVERNTED[csp] 설정 값 ← Current_state return failure에서 VAR 설정 값 v ← current_state val을 최소화한다.

알고리즘에는 명시되어 있지 않지만, 솔루션 접근에 있어 좋은 초기 임무는 매우 중요할 수 있다.어느 정도 랜덤성이 있는 탐욕스러운 알고리즘을 사용하고 다른 할당이 충분하지 않을 경우 변수 할당이 제약 조건을 깨도록 허용하십시오.무작위성은 Min-conflict가 탐욕스러운 알고리즘의 초기 할당에 의해 생성된 국소 미니마를 피하도록 돕는다.사실, 최소 충돌 솔루션에 가장 잘 반응하는 제약조건 만족도 문제는 탐욕스러운 알고리즘이 문제를 거의 해결해주는 곳에서 잘 된다.지도 색칠 문제는 민-충돌뿐만 아니라 탐욕 알고리즘에서도 좋지 않다.지도의 하위 영역은 색깔을 안정적으로 유지하는 경향이 있고 최소 충돌은 지역 최소값에서 벗어나기 위해 언덕을 오를 수 없다.그CONFLES 함수는 할당 나머지 상태가 알려진 경우 특정 개체에 의해 위반된 제약 조건의 수를 계산한다.

역사

인공지능과 이산형 최적화는 수년간 제약만족 문제를 알고 추론해 왔지만, 1990년대 초가 되어서야 대규모 CSP를 해결하기 위한 이 과정이 알고리즘 형태로 체계화되었다.초기에 우주 망원경 과학 연구소의 마크 존스턴은 허블 우주 망원경에서 천문 관측을 스케줄링하는 방법을 찾았다.그는 우주 망원경 유럽 코디네이션 시설의 한스-마틴 아도르프와 협력하여 장난감 n-queens 문제(1024명의 여왕용)를 해결할 수 있는 신경망을 만들었다.[3][4]스티븐 민튼과 앤디 필립스는 신경망 알고리즘을 분석해 (1) 탐욕스러운 알고리즘을 이용한 초기 과제와 (2) 갈등 최소화 단계(더 늦게 "민간 갈등"이라고 한다)의 두 단계로 구분했다.AAAI-90에서 논문이 작성되고 발표되었다. 필립 레어드는 알고리즘의 수학적인 분석을 제공했다.

그 후, 마크 존스턴과 STScI 직원들은 허블 우주 망원경에서 천문학자들의 관측 시간을 계획하기 위해 최소 충돌 시간을 사용했다.

예

8-퀴엔의 최소 충돌 해결 애니메이션.1단계는 칼럼을 탐욕스럽게 배치하여 갈등을 최소화한 후 해결한다.

Min-Conflicts는 왕비 재할당을 위해 체스 보드에서 임의로 열을 선택하여 N-Queens 문제를 해결한다.알고리즘은 각 사각형에 표시된 충돌 횟수(공격 여왕의 수)에 대해 각 잠재적 움직임을 검색한다.알고리즘은 최소 충돌 횟수로 퀸을 광장으로 이동시켜 무작위로 넥타이를 끊는다.충돌 횟수는 여왕이 공격할 수 있는 각각의 새로운 방향에 의해 발생한다는 점에 유의한다.만약 두 여왕이 같은 방향(행 또는 대각선)에서 공격한다면, 그 충돌은 한 번만 계산된다.또한 여왕이 현재 위치보다 더 큰 갈등을 일으킬 수 있는 위치에 있다면, 여왕은 움직이지 않는다는 점에 유의한다.여왕이 최소한의 갈등 상태라면 움직일 필요가 없다는 것이다.

N-Queens를 해결하기 위한 이 알고리즘의 실행 시간은 문제 크기와 무관하다.이 알고리즘은 평균 50단계에서 백만-퀴즈 문제를 해결하기도 한다.이러한 발견과 관찰은 1990년에 엄청난 양의 연구로 이어졌고, 지역 검색 문제와 쉬운 문제와 어려운 문제 사이의 구분에 대한 연구를 시작했다.N-Queens는 주 공간 전체에 솔루션이 촘촘히 분포되어 있어 현지 검색이 용이하다.어려운 문제에도 효과가 있다.예를 들어 허블우주망원경의 관측 일정을 잡는 데 사용돼 일주일간의 관측 일정을 잡는 데 걸리는 시간을 3주에서 10분 정도로 단축했다.[5]

참고 항목

참조

  1. ^ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1990). "Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method" (PDF). Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, Massachusetts: 17–24. Retrieved 27 March 2013.
  2. ^ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1992). "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems" (PDF). Artificial Intelligence. 58 (1): 161–205. CiteSeerX 10.1.1.308.6637. doi:10.1016/0004-3702(92)90007-k. Retrieved 27 March 2013.
  3. ^ Johnston, M. D.; Adorf, H.-M. (1989). "Learning in Stochastic Neural Networks for Constraint Satisfaction Problems". NASA Conf. On Space Telerobotics 1989, Pasadena, CA; G. Rodriguez, H. Seraji (Eds.): 367–376 vol.II.
  4. ^ Adorf, H.-M.; Johnston, M. D. (1990). "A discrete stochastic neural network algorithm for constraint satisfaction problems". 1990 IJCNN International Joint Conference on Neural Networks: 917–924 vol.3. doi:10.1109/IJCNN.1990.137951.
  5. ^ 스튜어트 러셀, 피터 노빅 "인공지능:현대적 접근법(3판)", 페이지 220-222, 2009년 12월 11일.

외부 링크

  • [1] 민충돌 휴리스틱 마이크로폼 : 실험과 이론적 결과 / 스티븐 민튼...[et al.]NASA, Ames Research Center, 인공지능 연구부.마이크로피쉬로 된 예탁도서관에 배포된다.