Notice
Recent Posts
Recent Comments
Today
Total
03-29 01:50
Archives
관리 메뉴

Jeongchul Kim

Genetic Algorithm 유전알고리즘 - 염색체 유전자 적합도함수 본문

카테고리 없음

Genetic Algorithm 유전알고리즘 - 염색체 유전자 적합도함수

김 정출 2018. 3. 23. 00:26


Genetic Algorithm 유전알고리즘 - 염색체 유전자 적합도 함수


Genetic Algorithm 유전알고리즘 - Introduction

유전 알고리즘을 구현하는 동안 가장 중요한 결정 중 하나는 우리가 솔루션을 표현하는 데 사용할 표현을 결정하는 것입니다. 부적절한 표현은 GA의 성능 저하를 초래할 수 있음이 관찰되었습니다.


그러므로 적절한 표현을 선택하는 것은 표현형과 유전자형 공간 사이의 매핑을 적절하게 정의하는 것이 GA의 성공에 필수적입니다.


이 절에서는 유전 알고리즘에 대해 가장 일반적으로 사용되는 표현을 제시합니다. 그러나 표현은 매우 문제가 많으므로 여기에 언급 된 표현이나 표현의 혼합이 자신의 문제에 더 잘 맞을 수 있다는 것을 독자가 알 수 있습니다.


Binary Representation

이것은 GAs에서 가장 간단하고 널리 사용되는 표현 중 하나입니다. 이 유형의 표현에서 유전자형은 비트 문자열로 구성됩니다.


솔루션 공간이 부울 결정 변수 (예 또는 아니오)로 구성되어있는 일부 문제의 경우 이진 표현은 자연 스럽습니다. 예를 들어 0/1 배낭 문제를 생각해보십시오. n 개의 항목이있는 경우 n 개의 요소로 구성된 이진 문자열로 솔루션을 나타낼 수 있습니다. 여기서 x 번째 요소는 항목 x가 선택되었는지 (1) 또는 선택되지 않는지 (0) 여부를 나타냅니다.



다른 문제, 특히 숫자를 다루는 문제의 경우 이진 표현으로 숫자를 나타낼 수 있습니다. 이러한 종류의 인코딩 문제는 서로 다른 비트가 다른 의미를 가지므로 돌연변이와 교차 연산자가 원하지 않는 결과를 초래할 수 있다는 것입니다. 회색 코드를 사용하면 어느 정도 해결할 수 있습니다. 한 비트의 변경으로 인해 솔루션에 큰 영향을 미치지는 않습니다.


Real Valued Representation

이산 변수가 아닌 연속 변수를 사용하여 유전자를 정의하려는 문제의 경우, 실수 값 표현은 가장 자연스러운 표현입니다. 그러나 이 실수 또는 부동 소수점 수의 정밀도는 컴퓨터에만 국한됩니다.



Integer Representation

이산 가치있는 유전자의 경우, 우리는 항상 해답 공간을 이진 '예'또는 '아니오'로 제한 할 수 없습니다. 예를 들어, 북쪽, 남쪽, 동쪽 및 서쪽의 네 가지 거리를 인코딩하려는 경우 {0,1,2,3}으로 인코딩 할 수 있습니다. 이 경우 정수 표현이 바람직합니다.



Permutation Representation

많은 문제에서 솔루션은 요소의 순서로 표현됩니다. 이러한 경우에 순열 표현이 가장 적합합니다.


이 대표적인 예는 여행 판매원 문제 (TSP)입니다. 이 점원은 모든 도시를 한 번 둘러보고 처음 도시로 돌아와야합니다. 투어의 총 거리를 최소화해야합니다. 이 TSP에 대한 해답은 자연적으로 모든 도시의 순서 또는 순열이므로 순열 표현을 사용하면이 문제를 이해할 수 있습니다.



Population

인구는 현재 세대의 솔루션의 하위 집합입니다. 그것은 또한 일련의 염색체로 정의 될 수 있습니다. GA 인구를 다룰 때 염두에 두어야 할 몇 가지 사항이 있습니다


- 인구의 다양성이 유지되어야한다.

- GA가 느려지는 원인이 될 수 있기 때문에 인구 규모를 크게 유지해서는 안되며, 적은 수의 인구가 좋은 짝짓기 풀에 충분하지 않을 수도 있습니다. 따라서 시행 착오를 통해 최적의 개체군 크기를 결정해야합니다.

- Population은 일반적으로 크기 인구, 크기 x, 염색체 크기의 2 차원 배열로 정의됩니다.


Population Initialization

GA에서 모집단을 초기화하는 데는 두 가지 기본 방법이 있습니다.

- 무작위 초기화 - 완전히 무작위로 초기 모집단을 채 웁니다.

- 휴리스틱 초기화 - 알려진 휴리스틱을 사용하여 초기 모집단을 채웁니다.


그것은 전체 인구가 비슷한 해결책과 매우 작은 다양성을 갖는 인구를 초래할 수 있기 때문에 휴리스틱을 사용하여 초기화되지 않아야한다는 것이 관찰되었습니다. 실험적으로 임의의 해가 인구를 최적 상태로 유도하는 것으로 나타났습니다. 따라서 휴리스틱 초기화로 전체 인구를 휴리스틱 기반 솔루션으로 채우기보다는 무작위 솔루션으로 나머지를 채우는 것만으로 몇 가지 좋은 솔루션을 제공합니다.


또한 어떤 경우 휴리스틱 초기화는 인구의 초기 적합성에만 영향을 미치지 만 최후에는 최적성을 유도하는 솔루션의 다양성이 관찰되었습니다.


Fitness Function

간단히 정의 된 적합도 함수는 문제의 후보 솔루션을 입력으로 사용하고 솔루션이 문제와 관련하여 "좋은"결과를 "적합"시키는 방법을 출력으로 생성하는 기능입니다.


적합도 값의 계산은 GA에서 반복적으로 수행되므로 충분히 빠릅니다. 적합도 값을 느리게 계산하면 GA에 부정적인 영향을 미쳐 예외적으로 느려질 수 있습니다.


대부분의 경우 적합성 함수와 목적 함수는 주어진 목적 함수를 최대화하거나 최소화하는 목적과 같습니다. 그러나 여러 목표와 제약 조건을 가진보다 복잡한 문제의 경우 알고리즘 설계자는 다른 적합성 기능을 선택할 수 있습니다.


Fitness function은 다음의 특징을 가져야 합니다.

- 적합도 함수는 계산하기에 충분히 빠릅니다.


- 주어진 솔루션이 얼마나 적합한 지, 또는 주어진 솔루션으로부터 어떻게 개인이 생산 될 수 있는지를 정량적으로 측정해야합니다.


경우에 따라 적합성 함수를 직접 계산하는 것은 문제가 본질적으로 복잡하기 때문에 가능하지 않을 수 있습니다. 이러한 경우 우리는 우리의 요구에 맞게 근사치를 계산합니다.




Comments