*병* 스토어

*병*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

2개
전체 판매량

15개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 2개

유전알고리즘과 활용 평가A좋아요

◆ 개요 ( What are Genetic Algorithms? )유전자 알고리즘(Genetic Algorithm, GA)은 적자 생존과 유전의 메카니즘을 바탕으로 하는 탐색 알고리즘이다. 다시 말해 주어진 환경에 잘 적응하는 유전자만을 선택(selection)하고 교배(crossover)하고 때에 따라서는 돌연변이(mutation)도 하며 다음 세대에 우수한 유전 형질이 전달(reproduction)되게 된다. 따라서 진화(evolution)가 거듭될수록 주어진 환경에 더 적합한 유전자들만이 남아있게 될 것이다.유전자 알고리즘은 미시간대학의 홀랜드(John Holland)에 의해 탄생하였으며.당시 연구원들의 연구 목표는[1] 자연시스템의 적응적 과정을 추상화시키며 철저하게 분석하여,[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.유전자 알고리즘(GA)은 그러한 배경에서 만들어졌으며, 근본적으로 다른 탐색이나 최적화 알고리즘과는 세 가지 정도가 다르다.[1] GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로 탐색한다.[2] GA는 적합성 함수(fitness function)를 사용한다.[3] GA는 확률적인 변이 규칙을 사용한다.간단한 예를 들어보자. f(x) = x2[0 ≤ x ≤ 31] 이라는 환경이 있으며, 환경에 살아가는 개체(유전자)가 x인 셈이다. 그리고 환경에 잘 적응하는 정도를 함수값으로 정의하자. 그러므로 x = 0이라는 개체보다 x = 4라는 개체가 f(x) = x2[0 ≤ x ≤ 4]라는 환경에서 더 잘 적응하는 것이다.환경: f(x) = x2[0 ≤ x ≤ 31]개체: 0 ≤ x ≤ 31적합성(fitness): f(x)*************0010011위의 네 개체가 살고 있는 군(집단)에서 과연 f(x) = x2이라는 환경에서 누가 더 잘 적응할 것으로 생각되는가? 위의 이진수를 십진수로 바꾸어 생각하면 쉽게 알 수 있다. 위의 예에서 01000은 살기 어렵고, 11000은 그나마 가장 잘 적응할 것이다. 서할당된 영역이 넓으면 그만큼 걸릴 확률이 많은 것이다. 우수 형질은 그만큼 원판에서의 면적 할당이 넓게 함으로써 다음 세대의 개체 생산의 가능성을 크게 하는 것이다. 아래 그림을 보면 이해가 될 것이다. 군(pool)에 개체들이 있고, 그 개체들은 우수 정도에 따라 영역을 할당받는다. 우수 개체는 아래 그림에서 (2) 영역을 할당받을 것이고, 열등 형질은 (1) 영역을 할당받을 것이다. 이제 재생산의 남은 과정은 원판을 돌리고 화살만 쏘면 되는 것이다. 걸리면 살아남는 개체가 되는 것이다. 냉혹함이 숨겨져 있는 알고리즘이다.유전자 알고리즘에서의 재생산(Reproduction)예제(example)f(x) = x2이라는 환경에서 살아가는 개체가 시간 t일 때*************0010011와 같이 네 개체만이 있다면 개체들의 적합도(fitness)와 전체에 대한 우수성의 비율을 아래 표에 나타내었다.No.개체Fitness% of Total10110116914.421100057649.2301000645.541001136130.9Total1170100.0표. f(x) = x2에서의 개체와 적합함수(fitness function)원판위에 적합함수(fitness function)에 따라 다음 세대에서의 생존 가능성을 그리면 앞의 원판 그림이다. No. 2라는 개체가 f(x) = x2이라는 환경에서는 가장 잘 적응되고 원판에서도 가장 넓은 영역을 차지하고 있다. 따라서 다음 세대를 재생산(reproduction) 하기 위해 화살을 네 번 쏜다면, No. 2라는 개체는 살아남아서 다음 단계인 교배(crossover)를 할 가능성이 가장 높다.이상으로 roulette wheel이라는 확률 기반의 재생산(reporduction) 방법에 대해 알아보았다. 교배는 실제 재생산된 개체들끼리의 연산으로 좀 더 나은 개체를 발생시키고자 하는 데 목적이 있다. 유전자 알고리즘은 재생산(reproduction), 교배(crossover), 돌연변이(mutation)에 대해서 확실히 알 돌연변이가 발생하는 확률을 너무 높게 설정하면 무작위 탐색이 될 수 있기에, 적절한 돌연변이의 발생이 요구된다.그림. 돌연변이(mutation)( 일반적으로, 돌연변이 발생 확률 = 0.01 )이상으로 유전자 알고리즘의 기본적인 연산자에 대하여 알아보았다. 재생산(reproduction), 교배(crossover), 돌연변이(mutation)이라는 기본적인 연산자를 이용하여 개체군 내에서의 개체를 변화시켜며, 또 적응해가도록 하며, 그러한 연산자는 다윈의 자연 선택(natural selection)의 원칙을 그 모델로 삼고 있다.‘죄수의 딜레마‘ 유전알고리즘을 이용한 접근죄수의 딜레마와 전략들진화에는 깊은 파라독스가 있다.냉혹한 생존경쟁이 다른 한편으로 공생과 다른 형태의 협동을 출현시킨다는 사실이다. 정치학자 로버트 악세로드(Robert Axelord)는 "죄수의 딜레마"(prisoner's dilemma)라는 게임이 이 문제에 대한 단서를 제공해줄지 모른다고 생각했다.이것은 원래 1950년대 랜드사의 두 연구자에 의해서 개발된 게임이었다.각각 상대방의 범행을 알고 있는 두 범인 있다고 하자.이들은 구속되기 전에 서로의 범행에 대해 입을 다물기로 합의했다. 범인들은 다른 증거가 없기 때문에 상대의 범행에 대해 입을 꾹 다물고 있으면 둘다 무죄석방될 수 있다는 것을 알고 있다.경찰은 이들이 입을 다물고 있자 상황타개용으로 하나의 미끼를 던진다. 경찰은 상대의 범죄를 증언하는 자에게 포상금을 약속한다. 범인은 침묵(협동),자백(배반) 중 어떤 행동을 취하게 될까? 약간 복잡하기 때문에 여기에 점수를 부여해서 상황을 단순화 시키자. 둘이 같이 침묵을 지켰을 때는 무죄방면되는데 여기에는 각자 3점을 부여한다.둘이 같이 상대의 범행을 증언했을 때는 둘다 구속된다.그러나 증언으로 죄가 약간 가벼워진다고 보고 여기에 1점을 준다. 한 사람이 침묵하고 다른 사람이 증언했을 때는 증언한 사람은 (상대가 증언하지 않았으므로) 무죄방면되고 포상금도 받게 되어 5점의 최고점수를배반한데 대해 다음번에 통쾌하게 복수할 수도 있고(협동→배반→배반),너그럽게 용서할 수도 있다(협동→배반→협동).물론 상대도 마찬가지로 여러 전략을 선택할 수 있다.1979년 악셀로드는 게임이론을 전공하는 학자들에게 부탁하여 라운드로빈 방식으로 죄수의 딜레마게임에 참가할 각종 정책을 제출하여 여러 정책이 상호작용하는 동안 최고의 점수를 딸 수 있도록 해보라고 청하였다.이 정책들은 컴퓨터프로그램을 만들어 다른 정책들이 C(협동)나 D(배반)를 택할 때 동일한 정책을 쓰는 상대를 다시 만날 때 상대의 과거행위를 기억하도록 하여 그에 대응하는 행동으로 쓸 수 있게 하였다.이 프로그램은 항상 C나 D로 밖에 반응할 수 없으나 어떤 제약도 주지 않았는데 예를 들어 주사위를 던져 C나 D를 골라 반응에 이용할 수 있게 하는 것도 허용하였다.처음 악셀로드의 토너먼트에 14종의 정책이 참가하였는데 악셀로드는 여기에 RANDOM(무작위)이라는 프로그램을 하나 더 첨가하였다.이 게임에 출전한 프로그램들은 다양해서 베이직 컴퓨터 언어로 4줄에 불과한 것에서부터 77줄에 이르는 프로그램 까지 있었다.악셀로드는 이 프로그램들 끼리 200회씩 각각 대전하도록 하였는데 이 토너먼트를 5번 반복하여 통계적 오류를 제거하였다.우승을 따낸 프로그램은 토론토대학의 심리학자이자 철학자인 아나톨 라포로트(Anatol Rappoport)가 내어 놓은 것인데 이것은 프로그램중 가장 짧은 것으로 TIT FOR TAT라고 불렀다.이것은 아주 단순한 기법으로 탁포르틱(눈에는 눈)이라고 불러도 좋을 것이다.이 정책은 "첫번째 만남에서 우선 협동하고,그 다음 부터는 상대가 바로 직전에 한 수대로 따라 한다."는 것이다."이게뭐야"할 정도로 단순한 것인데 세상에 이런 것이 내노라하는 쟁쟁한 전문가들이 만들어낸 복잡한 전략의 프로그램들을 이기게 될 줄은 아무도 몰라었다.첫 토너먼트의 교훈은 "먼저 배반하지 않는다."는 선한 성질과 "화를 한번 내고 나면 원한을 남기지 않는다."는 관용적 성질이 중요하다는 것이었다ect;상대의 수에 관계없이 항상 D(배반) 카드를 낸다.→배반파3. tit-for-tat;일단 C카드를 내고 다음 부터는 상대의 수를 따라한다.즉 상대가 C를 내면 C를 내고 D를 내면 D를 낸다.→정의파4. mistrust;일단 D카드를 내고 다음 부터는 상대의 수를 따라한다.→불신파이것은 바로 상대의 직전의 카드만을 보고 결정하는 전략이다.그러나 상대가 한 앞의 몇수를 참고로 자신의 카드를 결정할 수도 있다.이 메모리의 단계를 높임으로써 가능한 전략의 수는 엄청나게 늘어나게 되는데 예컨대 앞의 두수를 보고 결정한다면 2의 2의 2제곱 즉 16가지 전략이 가능하다.일반적으로 2의 2의 n제곱의 전략이 가능하다.(여기서 n은 메모리의 단계이다) 이 가운데 토너먼트에 제시된 몇가지 전략을 소개하면 다음과 같다.5. random;0.5의 확률로 C와 D 카드를 낸다.상대에게 다음 전략이 노출되지 않는 장점이 있다.→오리무중파6. spite;일단 C카드를 내지만 상대가 D카드를 내면 그 후로는 상대의 수에 관계없이 계속 D카드를 낸다.상대의 배반을 억제하는 효과가 있다.→원한파7. per-kind;상대의 수에 관계없이 C,C,D를 주기적으로 반복한다.8. per-nasty;상대의 수에 관계없이 D,D,C를 주기적으로 반복한다.9. per-CD;C에서 시작해서 C,D,C,D..를 반복한다.10. soft-major;상대가 많이 사용하는 수를 사용하고 똑같으면 C를 낸다.(선수일 경우는 C를 낸다)→균등파이것은 약간 이해하기 어려울지 모르겠다. 예를 들어 soft-major와 random의 대결을 생각해 보자.카드는 동시에 제출됨으로 판단은 당회 직전 까지의 결과를 토대로 이루어진다.3회전에서 soft-major는 C를 낸다.왜냐하면 2회전까지 random의 수는 C,C 였기 때문이다.14회전에서 soft-major는 D가 되는데 그 직전 13회전 까지의 random의 수를 보면 C가 6번,D가 7번 나왔다.그러므로 14회전에서 soft-major의 수는 D이다.11

공학/기술| 2003.06.03| 12페이지| 1,000원| 조회(1,403)

유전, 알고리즘, 진화, GA

미리보기

닫기
[알고리즘] 유전알고리즘과 ‘ 죄수의 딜레마’

..PAGE:1Genetic Algorithm유전알고리즘과‘ 죄수의 딜레마’..PAGE:2개요 ( What are Genetic Algorithms? )유전알고리즘의 세가지 연산자재생산 (reproduction )교배 (crossover)돌연변이 (mutation)‘죄수의 딜레마‘ 유전알고리즘을 이용한 접근죄수의 딜레마와 전략들..PAGE:3◆ 개요 ( What are Genetic Algorithms? )[1] 자연시스템의 적응적 과정을 추상화시키며 철저하게분석하여,[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.◆ 다른탐색이나 최적화알고리즘과의 차이점[1] GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로탐색한다.[2] GA는 적합성 함수(fitness function)를 사용한다.[3] GA는 확률적인 변이 규칙을 사용한다...PAGE:4◆ 교배(crossover)[1] 교배대상의 개체(들)를 선택한다.( 하나 혹은 2개 이상의 개체 )[2] 유전자 배열 중의 임의의 위치 k를 선택하고,개체들간의 유전자 배열을 바꾼다.(swap)0110111001..PAGE:5◆ 돌연변이(mutation)교배는 개체군 내에서의 개체 진화에 한계가 존재한다.다시 말해, 주어진 환경에 어느 한계까지는 진화하여적응할 수 있지만, 개체군내의 개체의 유전자 schema를 극복할 수 없다.돌연변이(mutation)은 유전자 배열 중의 유전자(gene)를 바꾸는 연산자이다.1111011100..PAGE:6‘죄수의 딜레마‘ 유전알고리즘을 이용한 접근죄수의 딜레마?상대에 대한 정보 부재와 신뢰 부족으로,최악을 피하기 위해 차악을 선택한다범인은 침묵(협동),자백(배반) 을 통하여 각각에 해당하는점수를 부여 받을수 있다.이 게임을 1회에 그치지 않고 반복한다.그래서 상대가 나를배반한데 대해 다음번에 통쾌하게 복수할 수도 있고(협동→배반→배반),너그럽게 용서할 수도 있다(협동→배반→협동).물론 상대도 마찬가지로 여러 전략을 선택할 수 있다...PAGE:7◆ 몇가지 전략소개1. cooperate;상대의 수에 관계없이 항상 C(협동) 카드를 낸다.→박애파2. defect;상대의 수에 관계없이 항상 D(배반) 카드를 낸다.→배반파3. tit-for-tat;일단 C카드를 내고 다음 부터는 상대의 수를 따라한다.즉상대가 C를 내면 C를 내고 D를 내면 D를 낸다.→정의파..PAGE:84. mistrust;일단 D카드를 내고 다음 부터는 상대의 수를 따라한다.→불신파5. random;0.5의 확률로 C와 D 카드를 낸다.상대에게 다음 전략이노출되지 않는 장점이 있다.→오리무중파6. spite;일단 C카드를 내지만 상대가 D카드를 내면 그 후로는상대의 수에 관계없이 계속 D카드를 낸다.상대의 배반을 억제하는 효과가 있다.→원한파..PAGE:97. per-kind;상대의 수에 관계없이 C,C,D를 주기적으로반복한다.8. per-nasty;상대의 수에 관계없이 D,D,C를 주기적으로반복한다.9. per-CD;C에서 시작해서 C,D,C,D..를 반복한다...PAGE:1010. soft-major;상대가 많이 사용하는 수를 사용하고 똑같으면C를 낸다.(선수일 경우는 C를 낸다)→균등파11.prober;일단 시작되면 C,D,D를 순서대로 낸다.상대가 둘째,셋째 수에서 C를 낸다면 계속 D를 내고 그렇지않으면 그 때부터 tit-for-tat의 전략을 택한다.→시험파..PAGE:1112.gradual;다음의 경우를 제외하고는 tit-for-tat의 전략을 택한다.상대의 첫 번째 D에 대해서는 1번 D를 내고 이어서 2번 C를낸다. (D,C,C)두번째 상대의 D에 대해서는 2번 D를 내고 이어서 2번 C를낸다.(D,D,C,C)세 번째 D에 대해서는 3번 D를 내고 2번 C를 낸다.(D,D,D,C,C)→온건 응징파13.pavlov;첫수는 C를 내고 직전 회전에서 상대와 자기가 같은 수를

공학/기술| 2003.06.03| 13페이지| 1,000원| 조회(874)

진화, GA, 유전알고리즘

미리보기

닫기