옛날에는 탐색으로 모든 문제를 해결하고자 노력했다(general problem solver(GPS)). → 하지만 매우 제한된 영역에서만 동작했다. 실제적인 문제 해결을 위해 나타난 시스템 → 전문가 시스템(expert knowledge) 전문가 시스템은 규칙으로 표현되는 지식을 통해 추론함으로써 복잡한 문제를 해결하도록 설계되었다. 인공지능 소프트웨어 최초의 성공적인 형태 지식의 중요성이 강조된다. 전문가 시스템 구성요소 지식베이스(Knowledge Base: KB) 어떤 특수한 문제 영역에 대한 사실이나 규칙으로 구성된다. 예시) 횡단보도에서 초록불이 켜지면 사람들이 건너간다. 추론엔진 KB에 있는 정보와 사실을 바탕으로, 사실로부터 규칙을 적용하는 과정을 진행하는 엔진 KB와 추론엔진은 독립적인 관..
Example1. A simple function optimization, f(x) = x2 on the integer interval [0,31] encoding scheme → binary unsigned integer of length 5 fitness function → 목표함수 이용 selection scheme → roulette wehel selection 사용 crossover, mutation scheme → one point parameter setting M(population size) = 4 → coin을 20번 던져서 initialization한다. Pc = 1 Pm = 0.001 Evolving process 01101 → 13 ( fitness는 13*13 = 169) % o..
조합 최적화 (Combinatorial Optimization, CO) VLSI 디자인에서의 배치 및 라우팅 문제: VLSI 셀들의 집합이 주어지며, 이들은 경계에 포트를 가지고 있다. 또한 포트를 연결해야 하는 네트워크의 모음도 주어진다. 전체 배치 및 배선 거리를 최소화하고 각 선이 특정한 상수 이하인 방법을 찾아야 한다. 외판원 문제 (The Traveling Salesman Problem): 외판원은 최소 비용으로 각 도시를 한 번만 방문하는 경로를 찾고자 합니다. 실행 가능한 해는 1부터 n까지의 숫자의 순열로 나타낼 수 있습니다. 따라서 해 공간의 크기는 (n-1)!이다 Local Search 부분 탐색 알고리즘 이전 값에 가까운 값으로 할당 공간 내에서 값을 수정 모든 제약 조건이 만족될 때..
플레이어의 이익이나 손실은 정확히 상대방들의 이익이나 손실과 균형을 이룬다. 전통적인 전략 - MinMax 각 상태에서 상대방의 최대 보상을 최소화하려고 시도 (나시 균형) 철저한 탐색 밴딧 기반 메소드 K개의 행동/움직임 중 선택 최상의 움직임을 계속해서 선택하여 누적 보상을 극대화해야 함 • 밴딧 기반 메소드는 가장 불확실한 가지를 **탐색(Exploration)**하고 가장 유망한 가지를 **개발(Exploitation)**하는 효율적인 트레이드오프로 알려져 있어서 트리 탐색에 사용된다. • 상한 신뢰 구간 (UCB) 밴딧 알고리즘은 트리 탐색에 적용되며 UCT (트리에 적용된 상한 신뢰 구간)라고 한다. MCTS overview 부분 탐색 트리를 반복적으로 구축 반복 가장 긴급한 노드 트리 정책 ..
Min-Max 알고리즘은 두 명의 플레이어가 참여하는 게임에서 적용된다. 예시: 체스, 바둑, 틱택토 등과 같은 게임 두 명의 플레이어 게임의 특징 논리 게임: 게임은 규칙과 약속의 집합으로 설명이 가능하다. 완전 정보 게임: 게임의 특정 시점에서 가능한 다음 움직임을 알 수 있다. Min-max Algorithm은 깊이 우선: 현재 게임 위치에서 시작하여 종료 게임 위치까지 이어진다. 최종 게임 위치는 Max 플레이어의 관점에서 평가된다. 트리의 내부 노드 값은 하향식으로 평가된 값으로 채워진다. Max 플레이어에 속하는 노드는 자식 노드 중 최대 값을 받는다. Min 플레이어에 속하는 노드는 자식 노드 중 최소 값을 받는다. Max 플레이어는 마지막에 가장 높은 가치를 갖는 움직임을 선택하려고 노력한..
맹목적 탐색: 정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 탐색 하는 방법 깊이 우선 탐색 (DFS) 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진, 즉 깊이 방향으로 탐색 • 최근에 생성된 노드를 가장 먼저 확장 • 노드의 깊이 Root node의 깊이는 1 자손인 노드의 깊이 = 부모노드의 길이 + 1 • 백트래킹(backtracking)을 위해 깊이 제한을 둔다. DFS의 알고리즘 출발노드를 OPEN에 넣는다. OPEN에 노드가 남아있는 동안 다음을 반복한다. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다.(이 노드를 n이라고 부름) n의 길이가 깊이 제한에 도달하지 않았다면 다음을 실행한다. 노드 n을 확장하여 모든 후계노드를 생성 생성된 후계노드들에게 부..
상태공간이란? 초기 상태와 목표상태를 포함하여 임의의 상태로부터 연산자를 통해 생성 가능한 모든 상태들의 집합 상태공간 구성요소 상태 묘사 형태 : 연산자 적용이 용이한 상태 묘사방식을 선택 초기상태와 목표상태에 대한 묘사 연산자의 종류 상태 묘사란? 다양한 형태의 자료 구조를 사용하여 문제의 상태를 표현하는 것 목표 상태 : 탐색과정이 끝났는가 하는 결정 새로 생성된 상태묘사들이 목표상태를 묘사하고 있는지 검토하는 정합과정 최적화 문제의 경우 최적해를 탐색하는 과정까지 수행 상태 공간 표현(방향성 그래프) 상태공간에서 목표를 탐색하는데 유용 노드 (node): 상태 묘사를 나타낸다. 아크 (arc): 연산자를 표현 C(Ni, Nj ): 두 노드 사이의 경로에 드는 비용 문장 분석 초기 상태: abaab..
에이전트란? 특정 환경 내에 위치하여, 설계된 목적을 만족시키기 위하여, 자율적으로 유연하게 행동할 능력이 있는 컴퓨터 시스템 인공지능에서의 문제에 주체 지능형 에이전트란? 센서로부터 인지된 주변 환경을 인지하고 효과기를 통해 외부환경에 적절한 행동을 취할 수 있는 로봇/기계/소프트웨어 에이전트의 종류 Rational Agents Do right thing Simple Reflex Agents 당장의 정해진 규칙에 의해서 행동, 경험 활용 X Model based Reflex Agents 특정 상황에서 수행되는 행동의 영향력을 이해하고 환경을 모델링한다. Goal based Agents 행동을 실행하기 이전에 목적에 부합하는지 고려 Utility based Agents 과정을 중시할 수 있는, 효율성을 ..
인공지능이란? - 사람처럼 생각하고 사람처럼 행동하는 기계를 만드는 연구 인공지능의 역사 제 1기: 태동기(1943 - 1956) Turing Test : 사고하는 기계 제안 → 기계가 인간과 얼마나 비슷하게 대화할 수 있는지를 기준으로 기계에 지능이 있는지를 판별하고자 하는 테스트 인간의 사고(학습) 과정을 최초로 연결망을 통한 모델화 성공 Hebbian Learning Theory - 인간의 두뇌가 학습하는 과정을 신경세포가 어떻게 받아들이는지 설명하는 이론 SNARC: 최초의 신경회로망 컴퓨터 제 2기: 초기 관심기(1952 - 1969) Perceptron (F.Rosenblatt, 1957): a single layer artificial neural network, a FeedForward n..
