"유전 알고리즘"의 두 판 사이의 차이

2,912 바이트 추가됨 ,  9년 전
전체적으로 다듬음, 설명 조금 추가
잔글 ('유전자 알고리즘'에 대한 용어부분 삭제. -통용표기)
(전체적으로 다듬음, 설명 조금 추가)
'''유전 알고리즘'''(geneticGenetic algorithmAlgorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 [[최적화 문제1975년]] 해결하는개발된 기법의[[전역 최적화]] 하나로기법으로, [[전역 최적화 문제]] 기법이다해결하는 기법의 하나이다. [[진화생물학|생물의 진화]]를 모방한 기법인 [[진화 연산]]의 대표로서대표적인 기법으로, 생명체에실제 진화의 적용되는과정에서 많은 방식을부분을 차용하여차용하였으며, 변이([[돌연변이]]), 교차(교배) 연산 등이 존재하며,존재한다. 또한 [[세대]], [[인구]] 같은등의 용어도 사용한다문제 풀이 과정에서 사용된다.
== 개요 ==
인공 유전 시스템인 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 John Holland에 의해서 1975년에 개발된 전역적(Global)인 최적화 알고리즘이다.
 
== 개요 ==
유전 알고리즘은 자연 선택의 원리와 자연계의 생물 유전학에 기본 이론을 두며 병렬적이고 전역적(Global)인 탐색 알고리즘으로서, 모든 생물은 주어진 다양한 환경 속에 적응함으로써 살아남는다는 Darwin의 적자생존(Survival of the fittest)의 이론을 기본 개념으로 한다.
유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 병렬적이고 전역적인 탐색 알고리즘으로서, [[찰스 다윈|다윈]]의 적자생존 이론을 기본 개념으로 한다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 [[유전자]], 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 [[진화]]로 표현할 수 있다.
 
달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다.
유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다.
 
유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이 아니며, 문제를 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분의 받아들일 수 있는 수준의 해를 보여줄 수 있다.
다시 말하면 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾는 모의 진화(Simulated evolution)형의 탐색 알고리즘이다. 최근에 생물의 진화과정, 즉 자연선별과 유전법칙 등을 모방한 진화 알고리즘으로 진화전략(Evolution strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 현재 활발히 연구되고 있다.
 
이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있다. 유전 알고리즘은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로, 자연과학, /공학 및 인문사회과학인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는데해결하는 데 널리 응용되고 있다.
 
=== 용어 ===
* 세대 : 세대는 특정한 순간의 해의 집합을 의미한다. 각 세대의 해는 교배나 변이를 통해 다음 세대의 해를 만들어낸다.
* 인구 : 인구는 특정한 세대의 해의 개수를 의미한다.
 
=== 용어구성 ===
=== 요구 조건 ===
유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 [[유전자 표기]]의 형식으로 표현할 수 있어야 하며, 이 해가 얼마나 적합한지를 [[적합도 함수]]를 정의해야한다통해 계산할 수 있어야 한다.d 일반 생명체의 특성이 [[유전체]]의 집합인 [[유전자]]로 나타나는 것과 같이, 유전자유전 표기는알고리즘에서는 문제의해의 특성을 숫자나숫자의 배열이나 문자열과 같은 값의자료 구조를 집합으로통해서 표시하게 된다. 적합도 함수는 특정이렇게 나타내어진 해가 얼마나 적합한지문제의 답으로 적합한지를 평가하기 나타내는위한 함수이다. 일반이는 실세계의 생명체가 유전자에유전적 특성에 따라 특정환경에 환경이나 [[질병]]에서얼마나 살아 남을적응할있는있는지가 확률이 존재하는결정되는 것과 같이, 적합도 함수는 주어진 해가 다음 세대를 생산할비교할있을지,있다. 혹은 세대를 남기지 못하고 없어질지를 정하게 된다.
 
=== 흐름 ===
어떤 문제에 대해 유전자 표기와 적합도 함수가형식이 정의되었다면, 문제에어떤 대한해들의 초기유전자들을 해의서로 집합을조합함으로써 구한다.기존의 초기해로부터 해는 좋을 필요가 없으며, 단순히 이후의새로운 해를 구하는만들어낼 있어있다. 필요한이런 [[아담과조합 하와]]와연산은 같은교배(Crossover)에 초기비유할 개체로서의 역할을 한다있다. 생명체가우수한 교배를해들을 통해선택하여 이들을 다음교배하면, 세대를만들어진 생성하는해는 것과우수한 마찬가지로,해들이 초기가지는 해의특성을 집합물려받을 내부의가능성이 해의높을 교배를 통해 다음것이다. 세대의우수한 해의 집합을선택에는 생성하게앞에서 된다. 교배시에는정의한 적합도 함수를 이용해이용할 적합한 유전자를있으며, 가진적합도가 개체를높은 찾는해가 과정이선택될 확률을 높게 있게되며만들면, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 된다. 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨줄넘겨주도록 할 수 있으며, 변이는이는 [[지역 최적점]]에 빠지지 않도록 하는 주요한 기법이다.
 
해들을 교배하기 위해서는 [[아담과 하와]]처럼 초기 해의 집단이 필요하다. 초기해 집단은 단지 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것이므로, 우수한 해들로 이루어질 필요는 없다. 일반적으로는 유전자를 랜덤하게 생성하여 초기 해 집단을 구성한다. 초기해 집단이 구성되면, 이들 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 되며, 이를 세대를 거듭하면서 반복해 가면, 해들은 점점 정답에 가까워지게 된다.
 
유전 알고리즘이 전역 최적해를 구하려면, 많은 인구를 유지하면서 많은 세대를 내려갈 필요가 있다. 따라서, 대부분의 경우는 세대가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다.
 
=== 선택 ===
한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 균등 비례 룰렛휠룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.
 
선택의해의 문제는선택은 중요한유전 문제일알고리즘의 성능에 있다큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역최적화에지역 쉽게최적해에 빠질빠지는 경우가 생길 수도 있기 때문이다. 또한또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼질퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다. 따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할 수 있다.
 
반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있기때문이다. 때문에 선택의 문제는 고민이 필요한 부분이라 할 수 있다. 일반적으로는 가장 좋은 해의 순으로 선택될 확률이 높게 부여하는 방법론이 많이 쓰인다고 한다.
일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법론이 많이 사용된다. 이는 반대로 말하면, 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 준다고 볼 수 있다. 현 세대에서 가장 좋은 해라 할지라도 실제로는 지역 최적해에 가까운 해일 수도 있고, 반대로 좋지 않은 해라 할지라도 전역 최적해에는 더 가까울 수도 있기 때문이다. 실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로, 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적해에 빠지는 것을 가능한 한 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다.
즉 나쁜 해라 할지라도 그 해속에 포함된 좋은 인자를 퍼뜨릴 기회를 주자는 것이다. 머리도 좋고 잘생겼지만 매사 법대로 논리대로만 진행하는 사람과 머리도 그리좋지 못하고 평균적으로 떨어지지만 유대관계도 좋고 평판이 좋은 사람
누가 좋은가는 아무도 모르는 것이므로 시스템을 구현하는 사람의 의지가 짙게 깔리는 부분이라고도 할 수 있다.
 
=== 교차 ===
일반 생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 일반적으로이와 마찬가지로 개의유전 알고리즘에서 해가자연 선택된 해들은 교배를 해서통하여 다음 세대의 해를해들을 생성하게 되며,된다. 새로운일반적으로 해는 각각의개의 부모해를 해로부터선택한 서로 겹치지 않는간에 위치의교배 유전체를연산을 받아수행하게 새로운되며, 유전자를이를 구성하게통해 된다.생성된 이때해는 염색체가 재조합되는 과정에서각각의 부모 염색체의해의 일부분이교차 특정연산을 위치를 기준으로통해서 서로 바뀌어겹치지 결합되는않는 경우가위치의 있는데유전인자를 받아 현상을새로운 [[교차]]라고유전자를 한다.구성하게 유전 알고리즘에서는 이 교차 현상을 의도적으로 이용, 부모해를 교차시켜서 자식해를 만들어낸다된다.
 
실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다. 유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다. 교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다.
 
또한 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있다. 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다.
 
=== 변이 ===
일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다. 변이 연산은 주어진 해의 유전자 내의 유전체가유전 순서를인자의 바꿔서순서 혹은 값이 임의로 변경되어 다른 유전자해로 표기로변형되는 되는연산이다. 것이다해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다. 따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해집단의 다양성을 높여준다.
 
=== 대치 ===

편집

1,040