인공지능 - 오토마톤 및 탐색

오토마톤

• 시간 경과와 상태 변화를 표현
• 스스로 움직이는 기계
• 예시 : 운동을 한다 -> 단백질 섭취 -> 근육 증가 , 다침 -> 운동 휴식 -> 근육 감소 무한 반복

마르코프 모델

• 오토마톤 개념 + 상태 변화가 일어날 확률
• 예시 : 오늘 날씨에 따른 내일의 날씨의 확률

상태 기반 에이전트

• 게임을 예로들면, 게임의 등장 인물이나 필드의 구성요소 각각을 유한 오토마타로 설정해 인공지능을 구현하는 것

휴리스틱 탐색

• 상태공간에 대한 정보를 이용해서 탐색 효율을 높이는 탐색
• 언덕 오르기 방법
• 최상 우선 탐색
• 빔 탐색
• A* 알고리즘
• 다익스트라 알고리즘

Minimax 알고리즘과  알파베타 가지치기

• 자신의 순서에서는 최댓값을 선정하고, 상대방의 순서에서는 최솟값을 선정
• 알파베타 가지치기 : 고려할 필요가 없는 가지 제거
• 알파 : Max가 어떤 선택을 할지 예측한 값 - 자식노드 중 현재 노드의 최댓값
• 베타 : Min이 어떤 선택을 할지 예측한 값 - 자슥노드 중 현재 노드의 최솟값
• mini-max 몬테카를로 트리 탐색 : 무작위적인 시뮬레이션에 의해 형세의 유리한 정도를 결정하여 게임트리 구성

백트레킹 탐색

• 가능한 모든 방법을 탐색한다는 기본 아이디어 기반
• DFS을 이용하면서 불필요한 곳은 가지치기를 통해 제거하는 방법
• 예시 : N-Queen

유전 알고리즘

• 특정 조건을 만족하는 조합을 구하는 알고리즘
• 예시 : 20Kg 가방에 가장 많은 짐을 넣을 수 있는 조합을 구하는 문제
• 초기화 -> 평가 -> 도태(선택), 교차, 돌연변이 -> 평가
• 유전 알고리즘의 장단점
  • 결정론적 알고리즘이 존재하는 문제에 대해서는 유전 알고리즘 접근법이 의미가 없음
  • 유전 알고리즘은 본질적으로 확률적 특성으로 인해 수행 시간을 예측 할 수 없음
  • 기존의 방법으로는 해결할 수 없는 제약 조건 만족 문제와 같이 완벽하게 최적의 솔류션이 필요 없는 어려운 문제에 종종 사용됨

선택 연산자

• 유전 알고리즘은 재생산을 위하여 우수한 성능을 보이는 부모 염색체 2개를 선택
• 부모 염색체를 선택할 때 많이 사용되는 알고리즘(룰렛 휠 알고리즘)

교차 연산자

• 교차점을 기준으로 유전자들을 교환