Step 1 : Representation (Encoding) & Initialization

최적화에서 Problem Specific한 부분이 인코딩 부분과 뒤에서 볼 fitness function 정의하는 부분

앞서 각 컴포넌트들이 유기적으로 전체적인 큰 흐름에서 어떻게 동작하는지 살펴보았다.

이제부터 좀 더 디테일하게 각 컴포넌트의 내부적으로 어떤 방식으로 동작하는지, 어떻게 개념들이 구성되어 있는지 보겠다.

 

ㅁ당연한 얘기지만 Potential Solution를 컴퓨터상에 표현(인코딩)할 수 있어야 한다. (Q. 어떤 자료구조를 사용해야 할까?)

 

ㅁ Representation (Encoding) 관련 용어 정리 (컴포넌트를 이루는 서브 컴포넌트)

Population = Chromosomes

Choromosme =Genes

Gene= potential solution (local & global solution) 값을 갖는(저장하는) 변수

Allele = Gene 변수의 value (값)

 

 

ㅁ 서칭(솔루션) 스페이스 관점에서 개념 다시 생각하기 

서칭(솔루션) 스페이스는 가능한 '상태(Potential Solution)들'의 collection으로 이루어짐.

Chromosome = Individual = candidate possible solution = state

gene = 1개의 possobile solution을 구성하고 있는 cell (자료구조의 한 element)

Representation Engineering은 결국 solution space를 컴퓨터 상에 어떻게 잘 인코딩할지 분석하고 이해하는 것이다. 

 

https://slidetodoc.com/genetic-algorithms-ga-the-most-widely-known-type/

coding space = phenotype space

solution space = genotype space

 

솔루션스페이스가 컴퓨터상(coding space)에 잘표현되도록, 잘 1대1 매핑 되도록 Representation engineering을 잘 해야 한다. 

 

어떻게 대응되는지 이해할 것

 

 

인코딩할 때 신경써야할 점

 

 

ㅁ Initilization 은 알고리즘 초기작업으로 Chromosome을 랜덤값으로 채워주는 걸 의미한다. (더 정교하게 랜덤값이 아닌, 다른 값으로 채워줄 수도 있다.)

 

 

이 인코딩을 어떻게 할지는 문제 도메인에 따라 다르다.  따라서 여러 예제를 풀어봄으로써 트레이닝 좀 해야 한다. 

아래의 'Kanpsack 예제'에서 어떻게 인코딩 하는지 보자.

가방에 아이템을 담았는지 여부를 binary 변수로 나타냈다. 즉, gene을 binary 변수로 표현했다.

저체 가방에 담긴 상태 = gene의 배열(또는, list) = chromosome = individual candidate possible solution = state

 

그 外 여러 인코딩 방법들

 

 

ㅁ Initilization 은 알고리즘 초기작업으로 Chromosome을 랜덤값으로 채워주는 걸 의미한다. (더 정교하게 랜덤값이 아닌, 다른 값으로 채워줄 수도 있다.)

초기화 한 이후에 각 chormosome의 fitness value를 매겨 본다.

 

 

참고:

https://slidesplayer.org/slide/14134418/

Reprensentation의 종류 (참고: https://jeongchul.tistory.com/572)

 

Binary Representation

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

 

 

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

 

 

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

 

 

Real Valued Representation

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

 

 

 

Integer Representation

 

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

 

 

Permutation Representation

 

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

 

 

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

 

출처: https://jeongchul.tistory.com/572 [Jeongchul]