유전 연산자

Genetic operator

유전 연산자는 주어진 문제에 대한 해결책으로 알고리즘을 안내하기 위해 유전 알고리즘에 사용되는 연산자다. 알고리즘이 성공하기 위해서는 서로 연동하여 동작해야 하는 세 가지 주요 연산자 유형(교차, 교차, 선택)이 있다. 유전자 조작자는 유전적 다양성을 창조·유지하고(유전 연산자), 기존 용액(염색체라고도 함)을 새로운 용액(크로스오버)으로 결합하고, 용액(선택)을 선택하는 데 사용된다.[1] 복잡한 문제의 최적화를 위한 유전자 프로그래밍의 사용을 논하는 그의 저서에서 컴퓨터 과학자 존 코자는 또한 '반전' 또는 '주변' 연산자를 확인했지만, 이 연산자의 효율성은 결정적으로 입증된 적이 없고, 이 연산자는 거의 논의되지 않는다.[2][3]

돌연변이(또는 돌연변이 유사) 연산자는 한 번에 한 염색체에서만 작동하기 때문에 단일한 연산자라고 한다. 대조적으로 크로스오버 연산자는 기존 염색체 두 개를 하나의 새로운 염색체로 결합하여 한 번에 두 개의 염색체에서 작동하기 때문에 이항 연산자라고 한다.[4]

연산자

유전적 변형은 진화 과정의 필수품이다. 유전 알고리즘에 사용되는 유전 연산자는 적자생존이나 선택, 생식(크로스오버, 재조합이라고도 함), 돌연변이 등 자연계와 유사하다.

선택

주요 기사: 선택(유전자 알고리즘)

선택 연산자는 더 나은 해결책(크로모솜)을 선호하여 알고리즘의 다음 세대에 자신의 'gen'을 전달할 수 있게 한다. 최적의 해결책은 크로스오버 연산자에게 전달되기 전에 객관적 함수(유전자 알고리즘에서는 '피트니스 함수'라고도 한다)의 어떤 형태를 사용하여 결정된다. 예를 들어, 피트니스 비율 선택과 토너먼트 선택과 같은 최상의 솔루션을 선택하는 다른 방법들이 존재한다. 다른 방법들은 '최고'가 되는 것으로 다른 해결책을 선택할 수 있다. 또한 선정 운영자는 현 세대의 최선의 해결책을 변이되지 않고 바로 다음 세대로 전달할 수 있다. 이를 엘리트주의 또는 엘리트주의 선택이라고 한다.[1][5]

크로스오버

주요 기사: 교차(유전자 알고리즘)

크로스오버(Crossover)는 둘 이상의 부모 솔루션(크로모솜)을 가져다가 그 솔루션으로부터 자식 솔루션을 생산하는 과정이다. 좋은 용액의 일부를 재조합함으로써, 유전 알고리즘은 더 나은 용액을 만들 가능성이 더 높다.[1] 선택과 마찬가지로, 상위 솔루션을 결합하는 방법에는 여러 가지가 있는데, 여기에는 가장자리 재결합 연산자(ERO)와 '절단 및 스플라이스 크로스오버' 및 '단일 교차' 방법이 포함된다. 크로스오버 방법은 종종 염색체의 용액 표현과 밀접하게 일치시키기 위해 선택된다. 이것은 변수가 빌딩 블록으로 함께 그룹화될 때 특히 중요할 수 있으며, 이는 존중하지 않는 크로스오버 연산자에 의해 중단될 수 있다. 마찬가지로, 크로스오버 방법은 특정 문제에 특히 적합할 수 있다. ERO는 일반적으로 여행 중인 세일즈맨 문제를 해결하기 위한 좋은 옵션으로 간주된다.[6]

돌연변이

주요 기사: 돌연변이(유전자 알고리즘)

돌연변이 운영자는 해결책들 간의 유전적 다양성을 장려하고 해결책이 서로 너무 가까워지는 것을 막음으로써 유전 알고리즘이 국소적 최소치로 수렴되는 것을 막으려는 시도를 한다. 현재의 솔루션 풀을 변화시킬 때, 주어진 솔루션은 이전 솔루션과 완전히 달라질 수 있다. 용액을 변이시킴으로써 유전자 알고리즘은 변이 연산자를 통해서만 개선된 용액에 도달할 수 있다.[1] 다시 말하지만, 다른 돌연변이 방법이 사용될 수 있다; 이러한 범위는 단순한 비트 돌연변이(일부 낮은 확률을 가진 이항 끈 염색체에서 무작위 비트의 플립핑)부터 더 복잡한 돌연변이 방법까지, 용액의 유전자를 균일한 분포 또는 가우스 분포에서 선택한 무작위 값으로 대체할 수 있다. 교차 연산자와 마찬가지로, 돌연변이 방법은 염색체 내 용액의 표현과 일치하도록 선택된다.

결합 연산자

각 운영자가 개별적으로 작동하는 유전자 알고리즘에 의해 생성된 솔루션을 개선하기 위해 행동하는 동안, 운영자들은 알고리즘이 좋은 해결책을 찾는데 성공하기 위해 서로 협력해야 한다. 선택 연산자를 단독으로 사용하면 모집단으로부터 최선의 해결책의 사본을 솔루션 모집단에 채우는 경향이 있다. 돌연변이 연산자를 사용하지 않고 선택 연산자와 교차 연산자를 사용하면 알고리즘은 국소 최소값, 즉 문제에 대한 양호하지만 차선의 해결책으로 수렴하는 경향이 있을 것이다. 돌연변이 연산자를 단독으로 사용하면 무작위로 검색 공간을 거닐게 된다. 세 연산자를 모두 함께 사용해야 유전 알고리즘이 소음 방지 힐 클라이밍 알고리즘이 되어 문제에 대한 좋은 해결책이 나올 수 있다.[1]

참조

  1. ^ a b c d e "Introduction to Genetic Algorithms". Archived from the original on 11 August 2015. Retrieved 20 August 2015.
  2. ^ Koza, John R. (1996). Genetic programming : on the programming of computers by means of natural selection (6. print ed.). Cambridge, Mass.: MIT Press. ISBN 0-262-11170-5.
  3. ^ "Genetic programming operators". Retrieved 20 August 2015.
  4. ^ "Genetic operators". Retrieved 20 August 2015.
  5. ^ "Introduction to Genetic Algorithm". Retrieved 20 August 2015.
  6. ^ Schaffer, George Mason University, June, 4 - 7, 1989. Ed.: J. David (1991). Proceedings of the Third International Conference on Genetic Algorithms (2. [Dr.] ed.). San Mateo, Calif.: Kaufmann. ISBN 1558600663.