유전 알고리즘 - 위키백과, 우리 모두의 백과사전 유전 알고리즘 위키백과, 우리 모두의 백과사전. ( 유전알고리즘에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 유전 알고리즘 ( Genetic Algorithm ) 은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드 ( John Holland ) 에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이 ( 돌연변이 ), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다. 목차 1 개요 2 구성 2. 1 요구 조건 2. 2 흐름 3 연산 3. 1 선택 3. 2 교차 3. 3 변이 3. 4 대치 4 예 5 관련 기법 6 참고 문헌 개요 [
되었다면 다음 세대의 개체는 ( 8, 9, 8 ), ( 9, 0, 9 ) 가 되며, 각각의 적합도는 5, 2가 된다. 관련 기법 [ 편집 ] 개미 집단 최적화 ( ACO ) : 먹이를 찾아다니는 개미 집단의 행동에서 영감을 얻은 기법이다. 담금질 기법 ( SA ) : 해를 하나만 사용한다는 점이 가장 큰 차이점이다. 미미틱 알고리즘 : 지역 탐색 기법과 유전 알고리즘을 결합하여 빠른 시간 안에 좋은 해를 찾아내려고 하는 방법이다. 유전 프로그래밍 교차와 변이를 사용하는 등 유전 알고리즘과 많이 닮은 기법이다. 해를 프로그램으로 표현한다는 점이 특징이다. 진화 연산 생물의 진화에서 영감을 얻은 기법의 총칭이다. 현재는 진화 연산에 속하는 기법들의 차이가 점점 없어지고 있다. 진화 전략 : 교차를 사용하지 않고 변이에 의존하는 탐색
경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다. 변이 [ 편집 ] 일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다. 변이 연산은 주어진 해의 유전자 내의 유전 인자의 순서 혹은 값이 임의로 변경되어 다른 해로 변형되는 연산이다. 해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다. 따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수
이다. 해들을 교배하기 위해서는 아담과 하와처럼 초기 해의 집단이 필요하다. 초기해 집단은 단지 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것이므로, 우수한 해들로 이루어질 필요는 없다. 일반적으로는 유전자를 랜덤하게 생성하여 초기 해 집단을 구성한다. 초기해 집단이 구성되면, 이들 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 되며, 이를 세대를 거듭하면서 반복해 가면, 해들은 점점 정답에 가까워지게 된다. 유전 알고리즘이 전역 최적해를 구하려면, 많은 인구를 유지하면서 많은 세대를 내려갈 필요가 있다. 따라서, 대부분의 경우는 세대가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다. 연산 [ 편집 ] 유전 알고리즘은 선택
미지의 함수 Y = f ( x ) 를 최적화하는 해 x를 찾기 위해, 진화를 모방한 ( Simulated evolution ) 탐색 알고리즘이라고 말할 수 있다. 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수준의 해를 보여줄 수 있다. 이러한 생물의 진화 과정, 즉 자연 선택과 유전
변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해집단의 다양성을 높여준다. 대치 [ 편집 ] 교차 · 변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고, 기존 해 중 열등한 해를 가려내서 제외시키는 연산이다. 가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법 ( 해집단의 다양성을 유지하기 위함 ) 등이 있다. 예 [ 편집 ] { 1, 5, 6, 8, 3, 7, 3, 5, 9, 0 } 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 각 해의 유전자는 ( 1, 5, 3 ) 와 같이 유전체 3개의 집합
가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다. 연산 [ 편집 ] 유전 알고리즘은 선택, 교차, 변이, 대치 등 몇가지 주요 연산으로 구성된다. 선택 [ 편집 ] 한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다. 해의 선택은 유전 알고리즘의 성능에 큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역 최적해에 빠지는 경우가 생길 수도 있기 때문이다. 또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다. 따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할
연산에 속하는 기법들의 차이가 점점 없어지고 있다. 진화 전략 : 교차를 사용하지 않고 변이에 의존하는 탐색 기법이다. 진화 프로그래밍 : 변이를 주로 사용하는 기법으로 진화 전략과 유사하다. 초기에는 해를 유한 오토마타로 나타내었고 지금도 고정된 표현을 쓰지 않는 것이 특징이다. 참고 문헌 [ 편집 ] 존 홀랜드 ( 1975 ). 《 Adaptation in Natural and Artificial Systems 》. University of Michigan Press. ISBN 978 - 0 - 262 - 58111 - 0. 데이비드 골드버그 ( 1989 ). 《 Genetic algorithms in search, optimization and machine learning 》. Addison Wesley. ISBN 978 - 0 - 201 - 15767 - 3. 데이비드 골드버그 ( 2002 ). 《
염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다. 유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다. 교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다. 또한 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있다. 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는
2. 2 흐름 3 연산 3. 1 선택 3. 2 교차 3. 3 변이 3. 4 대치 4 예 5 관련 기법 6 참고 문헌 개요 [ 편집 ] 유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 병렬적이고 전역적인 탐색 알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 한다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 유전자, 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다. 달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f ( x ) 를 최적화하는 해 x를 찾기 위해, 진화를 모방한 ( Simulated evolution ) 탐색
유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용(채용)하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다.