유전 알고리즘-퀵 가이드

유전 알고리즘 (GA)은 다음 원칙에 기반한 검색 기반 최적화 기술입니다. Genetics and Natural Selection. 해결하는 데 평생이 걸리는 어려운 문제에 대한 최적 또는 거의 최적의 솔루션을 찾는 데 자주 사용됩니다. 최적화 문제, 연구 및 기계 학습을 해결하는 데 자주 사용됩니다.

최적화 소개

최적화는 making something better. 모든 프로세스에서 다음 그림과 같이 입력 세트와 출력 세트가 있습니다.

최적화는 "최상의"출력 값을 얻는 방식으로 입력 값을 찾는 것을 의미합니다. "최고"의 정의는 문제마다 다르지만 수학적 용어로는 입력 매개 변수를 변경하여 하나 이상의 목적 함수를 최대화하거나 최소화하는 것을 의미합니다.

입력이 검색 공간을 구성 할 수있는 모든 가능한 솔루션 또는 값의 집합입니다. 이 검색 공간에는 최적의 솔루션을 제공하는 포인트 또는 포인트 세트가 있습니다. 최적화의 목적은 검색 공간에서 해당 지점 또는 지점 집합을 찾는 것입니다.

유전 알고리즘이란 무엇입니까?

자연은 항상 모든 인류에게 큰 영감의 원천이었습니다. 유전 알고리즘 (GA)은 자연 선택 및 유전학의 개념을 기반으로하는 검색 기반 알고리즘입니다. GA는 다음과 같이 알려진 훨씬 더 큰 계산 분기의 하위 집합입니다.Evolutionary Computation.

GA는 미시간 대학의 John Holland와 그의 학생 및 동료, 특히 David E. Goldberg에 의해 개발되었으며 이후 다양한 최적화 문제에 대해 높은 수준의 성공을 거두었습니다.

GA에서 우리는 pool or a population of possible solutions주어진 문제에. 그런 다음 이러한 솔루션은 재조합과 돌연변이 (자연 유전학에서와 같이)를 거쳐 새로운 어린이를 생성하며이 과정은 여러 세대에 걸쳐 반복됩니다. 각 개인 (또는 후보 솔루션)에는 적합도 값 (목적 함수 값을 기반으로 함)이 할당되고 적합 자 개인에게는 더 많은 "적합한"개인을 짝짓기하고 산출 할 더 높은 기회가 주어집니다. 이것은“적자 생존”이라는 다윈주의 이론과 일치합니다.

이런 식으로 우리는 중단 기준에 도달 할 때까지 세대에 걸쳐 더 나은 개인이나 솔루션을 "진화"합니다.

유전 알고리즘은 본질적으로 충분히 무작위 화되지만, 역사적 정보도 활용하므로 무작위 로컬 검색 (다양한 무작위 솔루션을 시도하고 지금까지 최고를 추적)보다 훨씬 더 잘 수행됩니다.

GA의 장점

GA는 엄청난 인기를 얻은 다양한 장점이 있습니다. 여기에는-

파생 정보가 필요하지 않습니다 (많은 실제 문제에서 사용 가능하지 않을 수 있음).
기존 방법에 비해 더 빠르고 효율적입니다.
매우 우수한 병렬 기능이 있습니다.
연속 및 이산 기능과 다목적 문제를 모두 최적화합니다.
단일 솔루션이 아닌 "좋은"솔루션 목록을 제공합니다.
항상 문제에 대한 답을 얻습니다.
검색 공간이 매우 크고 관련된 매개 변수가 많을 때 유용합니다.

GA의 한계

다른 기술과 마찬가지로 GA에도 몇 가지 제한 사항이 있습니다. 여기에는-

GA는 모든 문제, 특히 단순하고 파생 정보를 사용할 수있는 문제에 적합하지 않습니다.
피트니스 값은 일부 문제에 대해 계산 비용이 많이들 수있는 반복적으로 계산됩니다.
확률론 적이기 때문에 솔루션의 최적 성이나 품질에 대한 보장은 없습니다.
제대로 구현되지 않으면 GA가 최적의 솔루션으로 수렴되지 않을 수 있습니다.

GA – 동기 부여

유전 알고리즘은 "충분한" "충분한"솔루션을 제공 할 수 있습니다. 이것은 최적화 문제를 해결하는 데 사용하기 위해 유전자 알고리즘을 매력적으로 만듭니다. GA가 필요한 이유는 다음과 같습니다.

어려운 문제 해결

컴퓨터 과학에는 많은 문제가 있습니다. NP-Hard. 이것이 본질적으로 의미하는 것은 가장 강력한 컴퓨팅 시스템조차도 그 문제를 해결하는 데 매우 오랜 시간 (심지어 몇 년!)이 걸린다는 것입니다. 이러한 시나리오에서 GA는 다음을 제공하는 효율적인 도구임이 입증되었습니다.usable near-optimal solutions 짧은 시간에.

그라디언트 기반 방법의 실패

전통적인 미적분 기반 방법은 임의의 지점에서 시작하여 언덕 꼭대기에 도달 할 때까지 기울기 방향으로 이동하는 방식으로 작동합니다. 이 기술은 효율적이며 선형 회귀의 비용 함수와 같은 단일 피크 목적 함수에 매우 적합합니다. 그러나 대부분의 실제 상황에서 우리는 풍경이라고하는 매우 복잡한 문제를 가지고 있습니다. 풍경은 많은 봉우리와 많은 계곡으로 이루어져 있으며, 이러한 방법은 지역 최적화에 갇히는 고유 한 경향으로 인해 실패합니다. 다음 그림과 같이.

좋은 솔루션을 빠르게 얻기

TSP (Traveling Salesperson Problem)와 같은 일부 어려운 문제에는 경로 찾기 및 VLSI 설계와 같은 실제 응용 프로그램이 있습니다. 이제 GPS 내비게이션 시스템을 사용하고 있으며 소스에서 목적지까지 "최적"경로를 계산하는 데 몇 분 (또는 몇 시간)이 걸린다고 가정 해보십시오. 이러한 실제 응용 프로그램의 지연은 허용되지 않으므로 "빠르게"제공되는 "충분한"솔루션이 필요합니다.

이 섹션에서는 GA를 이해하는 데 필요한 기본 용어를 소개합니다. 또한 GA의 일반적인 구조는pseudo-code and graphical forms. 독자는이 섹션에 소개 된 모든 개념을 올바르게 이해하고이 튜토리얼의 다른 섹션도 읽을 때이를 염두에 두는 것이 좋습니다.

기본 용어

유전 알고리즘에 대한 토론을 시작하기 전에이 튜토리얼 전체에서 사용할 몇 가지 기본 용어를 숙지하는 것이 중요합니다.

Population− 주어진 문제에 대해 가능한 모든 (인코딩 된) 솔루션의 하위 집합입니다. GA의 인구는 인간 대신 인간을 대표하는 Candidate Solutions가 있다는 점을 제외하면 인간의 인구와 유사합니다.
Chromosomes − 염색체는 주어진 문제에 대한 해결책 중 하나입니다.
Gene − 유전자는 염색체의 한 요소 위치입니다.
Allele − 특정 염색체에 대해 유전자가 취하는 가치입니다.

Genotype− 유전자형은 계산 공간의 모집단입니다. 계산 공간에서 솔루션은 컴퓨팅 시스템을 사용하여 쉽게 이해하고 조작 할 수있는 방식으로 표현됩니다.
Phenotype − 표현형은 실제 상황에서 솔루션이 표현되는 방식으로 표현되는 실제 실제 솔루션 공간의 모집단입니다.
Decoding and Encoding − 간단한 문제의 경우 phenotype and genotype공백은 동일합니다. 그러나 대부분의 경우 표현형과 유전자형 공간이 다릅니다. 디코딩은 솔루션을 유전자형에서 표현형 공간으로 변환하는 과정이고 인코딩은 표현형에서 유전자형 공간으로 변환하는 과정입니다. 피트니스 값을 계산하는 동안 GA에서 반복적으로 수행되므로 디코딩이 빨라야합니다.

예를 들어, 0/1 배낭 문제를 고려하십시오. 표현형 공간은 선택 될 항목의 항목 번호 만 포함하는 솔루션으로 구성됩니다.

그러나 유전자형 공간에서는 길이가 n 인 이진 문자열로 표시 될 수 있습니다 (여기서 n은 항목 수). ㅏ0 at position x 그것을 나타냅니다 x^th항목이 선택되고 1은 그 반대를 나타냅니다. 이것은 유전자형과 표현형 공간이 다른 경우입니다.

Fitness Function− 간단히 정의 된 피트니스 함수는 솔루션을 입력으로 취하고 솔루션의 적합성을 출력으로 생성하는 함수입니다. 어떤 경우에는 피트니스 함수와 목적 함수가 동일 할 수 있지만 다른 경우에는 문제에 따라 다를 수 있습니다.
Genetic Operators− 이들은 자손의 유전 적 구성을 변경합니다. 여기에는 교차, 돌연변이, 선택 등이 포함됩니다.

기본 구조

GA의 기본 구조는 다음과 같습니다.

초기 모집단 (무작위로 생성되거나 다른 휴리스틱에 의해 시드 될 수 있음)으로 시작하여이 모집단에서 짝짓기를 위해 부모를 선택합니다. 부모에 교차 및 돌연변이 연산자를 적용하여 새로운 자손을 생성합니다. 그리고 마지막으로이 자손들은 인구의 기존 개체를 대체하고 그 과정이 반복됩니다. 이런 식으로 유전 알고리즘은 실제로 인간의 진화를 어느 정도 모방하려고합니다.

다음 각 단계는이 자습서의 뒷부분에서 별도의 장으로 다룹니다.

GA에 대한 일반화 된 의사 코드는 다음 프로그램에서 설명합니다.

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

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

따라서 적절한 표현을 선택하고 표현형과 유전자형 공간 간의 매핑에 대한 적절한 정의를 갖는 것이 GA의 성공에 필수적입니다.

이 섹션에서는 유전 알고리즘에 가장 일반적으로 사용되는 표현 중 일부를 제시합니다. 그러나 표현은 매우 문제에 따라 다르며 독자는 여기에 언급 된 다른 표현이나 표현의 혼합이 자신의 문제에 더 적합 할 수 있음을 알 수 있습니다.

이진 표현

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

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

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

실제 가치 표현

이산 변수가 아닌 연속 변수를 사용하여 유전자를 정의하려는 문제의 경우 실제 가치 표현이 가장 자연 스럽습니다. 그러나 이러한 실수 또는 부동 소수점 숫자의 정밀도는 컴퓨터로 제한됩니다.

정수 표현

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

순열 표현

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

이 표현의 전형적인 예는 TSP (traveling salesman problem)입니다. 여기에서 판매원은 모든 도시를 둘러보고 정확히 한 번 각 도시를 방문하고 시작 도시로 돌아와야합니다. 투어의 총 거리를 최소화해야합니다. 이 TSP에 대한 해결책은 자연스럽게 모든 도시의 순서 또는 순열이므로 순열 표현을 사용하는 것이이 문제에 적합합니다.

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

인구의 다양성은 유지되어야하며 그렇지 않으면 조기 수렴으로 이어질 수 있습니다.
개체군 크기는 GA 속도를 늦출 수 있으므로 매우 크게 유지해서는 안되며, 작은 개체군은 좋은 짝짓기 풀에 충분하지 않을 수 있습니다. 따라서 시행 착오를 통해 최적의 모집단 크기를 결정해야합니다.

인구는 일반적으로 –의 2 차원 배열로 정의됩니다. size population, size x, chromosome size.

인구 초기화

GA에서 채우기를 초기화하는 두 가지 기본 방법이 있습니다. 그들은-

Random Initialization − 완전 무작위 솔루션으로 초기 모집단을 채 웁니다.
Heuristic initialization − 문제에 대해 알려진 휴리스틱을 사용하여 초기 모집단을 채 웁니다.

전체 모집단이 휴리스틱을 사용하여 초기화되어서는 안된다는 것이 관찰되었습니다. 모집단이 유사한 솔루션을 가지고 있고 다양성이 매우 적을 수 있기 때문입니다. 무작위 솔루션이 모집단을 최적으로 유도하는 솔루션이라는 것이 실험적으로 관찰되었습니다. 따라서 휴리스틱 초기화를 사용하면 전체 모집단을 휴리스틱 기반 솔루션으로 채우는 대신 무작위 솔루션으로 나머지를 채우는 몇 가지 좋은 솔루션으로 모집단을 시드합니다.

어떤 경우에는 휴리스틱 초기화가 모집단의 초기 적합성에만 영향을 미치지 만 결국 최적으로 이어지는 솔루션의 다양성이라는 것도 관찰되었습니다.

인구 모델

널리 사용되는 두 가지 인구 모델이 있습니다.

정상 상태

정상 상태 GA에서 우리는 각 반복에서 하나 또는 두 개의 자손을 생성하고 개체군에서 한두 명의 개체를 대체합니다. 정상 상태 GA는Incremental GA.

세대

세대 별 모델에서 우리는 'n'자손을 생성하는데, 여기서 n은 인구 크기이고 전체 인구는 반복이 끝날 때 새로운 것으로 대체됩니다.

간단히 정의 된 피트니스 함수는 candidate solution to the problem as input and produces as output 고려중인 문제와 관련하여 솔루션이 얼마나 "좋은"우리에게 얼마나 "적합"한가.

피트니스 값 계산은 GA에서 반복적으로 수행되므로 충분히 빨라야합니다. 피트니스 값을 느리게 계산하면 GA에 부정적인 영향을 미치고 예외적으로 느려질 수 있습니다.

대부분의 경우 적합 함수와 목적 함수는 주어진 목적 함수를 최대화하거나 최소화하는 목적과 동일합니다. 그러나 여러 목표와 제약이있는 더 복잡한 문제의 경우Algorithm Designer 다른 피트니스 기능을 선택할 수 있습니다.

피트니스 기능은 다음과 같은 특성을 가져야합니다.

피트니스 함수는 계산하기에 충분히 빨라야합니다.
주어진 솔루션이 얼마나 적합한 지 또는 주어진 솔루션에서 개인이 얼마나 적합한지를 정량적으로 측정해야합니다.

어떤 경우에는 당면한 문제의 고유 한 복잡성으로 인해 피트니스 함수를 직접 계산하는 것이 불가능할 수 있습니다. 그러한 경우, 우리는 우리의 필요에 맞게 피트니스 근사치를 수행합니다.

다음 이미지는 0/1 배낭 솔루션에 대한 피트니스 계산을 보여줍니다. 선택되는 항목 (1이 있음)의 수익 값을 합산하여 배낭이 가득 찰 때까지 왼쪽에서 오른쪽으로 요소를 스캔하는 간단한 피트니스 기능입니다.

부모 선택은 다음 세대를위한 자손을 만들기 위해 짝짓기하고 재결합 할 부모를 선택하는 과정입니다. 좋은 부모가 개인을 더 나은 솔루션으로 이끌 기 때문에 부모 선택은 GA의 수렴 률에 매우 중요합니다.

그러나 매우 적합한 솔루션 하나가 몇 세대 동안 전체 인구를 차지하지 않도록주의해야합니다. 이로 인해 솔루션 공간에서 솔루션이 서로 가깝게되어 다양성이 손실되기 때문입니다. Maintaining good diversityGA의 성공을 위해서는 인구가 매우 중요합니다. 하나의 매우 적합한 솔루션으로 전체 모집단을 차지하는 것은 다음과 같이 알려져 있습니다.premature convergence GA에서 바람직하지 않은 조건입니다.

피트니스 비례 선택

피트니스 비례 선택은 부모 선택의 가장 인기있는 방법 중 하나입니다. 이것에서 모든 개인은 자신의 적합성에 비례하는 확률로 부모가 될 수 있습니다. 따라서 건강한 개인은 짝짓기하고 자신의 기능을 다음 세대로 전파 할 가능성이 더 높습니다. 따라서 이러한 선택 전략은 인구에서 더 적합한 개인에게 선택 압력을 적용하여 시간이 지남에 따라 더 나은 개인으로 진화합니다.

원형 바퀴를 고려하십시오. 바퀴는n pies, 여기서 n은 모집단의 개인 수입니다. 각 개인은 체력 값에 비례하는 원의 일부를 얻습니다.

피트니스 비례 선택의 두 가지 구현이 가능합니다.

룰렛 휠 선택

룰렛 휠 선택에서 원형 휠은 앞에서 설명한대로 분할됩니다. 그림과 같이 휠 원주에서 고정 점이 선택되고 휠이 회전합니다. 고정 점 앞에 오는 바퀴의 영역이 부모로 선택됩니다. 두 번째 부모의 경우 동일한 프로세스가 반복됩니다.

피터 개인은 바퀴에 더 큰 파이를 가지고 있으므로 바퀴가 회전 할 때 고정 지점 앞에 착륙 할 가능성이 더 큽니다. 따라서 개인을 선택할 확률은 적합성에 직접적으로 달려 있습니다.

구현 현명한, 우리는 다음 단계를 사용합니다-

S = 기교의 합을 계산합니다.
0과 S 사이의 난수를 생성합니다.
인구의 맨 위에서 시작하여 P <S가 될 때까지 부분 합계 P에 벌금을 계속 추가합니다.
P가 S를 초과하는 개인이 선택된 개인입니다.

확률 적 범용 샘플링 (SUS)

Stochastic Universal Sampling은 Roulette wheel 선택과 매우 유사하지만, 다음 이미지와 같이 고정 포인트가 하나만있는 대신 여러 고정 포인트가 있습니다. 따라서 모든 부모는 바퀴를 한 번만 돌리면 선택됩니다. 또한 이러한 설정은 매우 적합한 개인이 적어도 한 번 선택되도록 장려합니다.

피트니스 비례 선택 방법은 피트니스가 음수 값을 취할 수있는 경우에는 작동하지 않습니다.

토너먼트 선택

K-Way 토너먼트 선발에서는 모집단에서 무작위로 K 명의 개인을 선택하고 이들 중 가장 좋은 것을 선택하여 부모가됩니다. 다음 부모를 선택하기 위해 동일한 프로세스가 반복됩니다. 토너먼트 선택은 부정적인 피트니스 값으로도 작동 할 수 있기 때문에 문학에서 매우 인기가 있습니다.

순위 선택

순위 선택은 음의 피트니스 값으로도 작동하며 모집단의 개인이 매우 가까운 피트니스 값을 가질 때 주로 사용됩니다 (일반적으로 실행이 끝날 때 발생 함). 이것은 다음 이미지에 표시된 것처럼 각 개인이 (피트니스 비례 선택의 경우와 같이) 파이의 거의 동일한 몫을 가지므로 서로 상대적으로 얼마나 적합하더라도 각 개인은 a로 선택 될 확률이 거의 같습니다. 부모의. 이것은 결과적으로 건강한 개인에 대한 선택 압력의 손실로 이어지고 GA가 그러한 상황에서 가난한 부모 선택을하도록 만듭니다.

여기에서 우리는 부모를 선택하면서 피트니스 가치의 개념을 제거합니다. 그러나 인구의 모든 개인은 체력에 따라 순위가 매겨집니다. 부모의 선택은 적합성이 아니라 각 개인의 순위에 따라 다릅니다. 높은 순위의 개인이 낮은 순위의 개인보다 더 선호됩니다.

염색체	피트니스 가치	계급
ㅏ	8.1	1
비	8.0	4
씨	8.05	2
디	7.95	6
이자형	8.02	삼
에프	7.99	5

무작위 선택

이 전략에서 우리는 기존 모집단에서 무작위로 부모를 선택합니다. 더 건강한 개인에 대한 선택 압력이 없으므로이 전략은 일반적으로 피합니다.

이 장에서는 다른 모듈, 용도 및 이점과 함께 크로스 오버 연산자가 무엇인지에 대해 설명합니다.

크로스 오버 소개

교차 연산자는 재생산 및 생물학적 교차와 유사합니다. 여기에서 한 명 이상의 부모가 선택되고 한 명 이상의 자손이 부모의 유전 물질을 사용하여 생산됩니다. 크로스 오버는 일반적으로 GA에서 높은 확률로 적용됩니다.p_c .

크로스 오버 연산자

이 섹션에서는 가장 널리 사용되는 크로스 오버 연산자에 대해 설명합니다. 이러한 교차 연산자는 매우 일반적이며 GA 디자이너는 문제 별 교차 연산자를 구현하도록 선택할 수도 있습니다.

원 포인트 크로스 오버

이 1 점 크로스 오버에서는 임의의 크로스 오버 지점이 선택되고 두 부모의 꼬리가 교체되어 새로운 자손을 얻습니다.

멀티 포인트 크로스 오버

멀티 포인트 크로스 오버는 새로운 자손을 얻기 위해 번갈아 가며 교체되는 1 포인트 크로스 오버의 일반화입니다.

균일 한 크로스 오버

균일 한 교차에서 우리는 염색체를 세그먼트로 나누지 않고 각 유전자를 개별적으로 처리합니다. 여기서 우리는 본질적으로 각 염색체에 대해 동전을 뒤집어 자손에 포함 될지 여부를 결정합니다. 우리는 또한 동전을 한 부모에게 편향시켜 그 부모의 자식에게 더 많은 유전 물질을 가질 수 있습니다.

전체 산술 재조합

이것은 일반적으로 정수 표현에 사용되며 다음 공식을 사용하여 두 부모의 가중 평균을 취하여 작동합니다.

Child1 = α.x + (1-α) .y
Child2 = α.x + (1-α) .y

분명히 α = 0.5이면 다음 이미지에 표시된 것처럼 두 하위 항목이 동일합니다.

데이비스 오더 크로스 오버 (OX1)

OX1은 자손에게 상대적인 순서에 대한 정보를 전송하려는 의도로 순열 기반 교차에 사용됩니다. 다음과 같이 작동합니다-

부모에 두 개의 임의 교차점을 만들고 첫 번째 부모에서 첫 번째 자손으로 이들 사이의 세그먼트를 복사합니다.
이제 두 번째 부모의 두 번째 교차 지점에서 시작하여 나머지 사용하지 않는 숫자를 두 번째 부모에서 첫 번째 자식으로 복사하여 목록을 둘러 쌉니다.
부모의 역할을 뒤집은 두 번째 자식에 대해 반복합니다.

PMX (Partially Mapped Crossover), OX2 (Order based crossover), Shuffle Crossover, Ring Crossover 등과 같은 많은 다른 크로스 오버가 있습니다.

돌연변이 소개

간단히 말해서, 돌연변이는 새로운 솔루션을 얻기 위해 염색체의 작은 무작위 조정으로 정의 될 수 있습니다. 유전 집단의 다양성을 유지하고 도입하는 데 사용되며 일반적으로 낮은 확률로 적용됩니다.p_m. 확률이 매우 높으면 GA가 무작위 검색으로 축소됩니다.

돌연변이는 검색 공간의 "탐색"과 관련된 GA의 일부입니다. 돌연변이는 GA의 수렴에 필수적이지만 교차는 그렇지 않다는 것이 관찰되었습니다.

돌연변이 연산자

이 섹션에서는 가장 일반적으로 사용되는 돌연변이 연산자를 설명합니다. 교차 연산자와 마찬가지로 이것은 완전한 목록이 아니며 GA 설계자는 이러한 접근 방식의 조합 또는 문제 별 돌연변이 연산자가 더 유용하다는 것을 알 수 있습니다.

비트 플립 돌연변이

이 비트 뒤집기 변이에서는 하나 이상의 임의 비트를 선택하고 뒤집습니다. 바이너리 인코딩 된 GA에 사용됩니다.

무작위 재설정

임의 재설정은 정수 표현에 대한 비트 플립의 확장입니다. 여기에서 허용 가능한 값 세트의 임의 값이 무작위로 선택된 유전자에 할당됩니다.

돌연변이 교체

스왑 돌연변이에서는 염색체의 두 위치를 무작위로 선택하고 값을 교환합니다. 이것은 순열 기반 인코딩에서 일반적입니다.

스크램블 돌연변이

스크램블 돌연변이는 순열 표현에서도 인기가 있습니다. 여기에서 전체 염색체에서 유전자의 하위 집합이 선택되고 그 값이 무작위로 스크램블되거나 셔플됩니다.

반전 돌연변이

반전 돌연변이에서 우리는 스크램블 돌연변이와 같은 유전자의 하위 집합을 선택하지만 하위 집합을 섞는 대신 하위 집합의 전체 문자열을 반전합니다.

생존자 선택 정책은 쫓겨날 개인과 다음 세대에 유지 될 개인을 결정합니다. 건강한 개인이 인구에서 쫓겨나 지 않도록하는 동시에 인구의 다양성을 유지하는 것이 중요합니다.

일부 GA는 Elitism. 간단히 말해, 현재 가장 적합한 인구가 항상 다음 세대로 전파된다는 것을 의미합니다. 따라서 어떤 상황에서도 현재 인구 중 적자 구성원을 교체 할 수 없습니다.

가장 쉬운 정책은 무작위 구성원을 모집단에서 쫓아내는 것이지만 이러한 접근 방식은 종종 수렴 문제가 있으므로 다음 전략이 널리 사용됩니다.

연령 기반 선택

연령 기반 선택에서는 피트니스에 대한 개념이 없습니다. 그것은 각 개인이 번식이 허용되는 유한 세대 동안 인구에 허용된다는 전제에 기초하고 있으며, 그 이후에는 체력이 아무리 좋더라도 인구에서 쫓겨납니다.

예를 들어, 다음 예에서 연령은 개인이 인구에 있었던 세대 수입니다. 인구의 가장 오래된 구성원, 즉 P4 및 P7은 인구에서 추방되고 나머지 구성원의 연령은 1 씩 증가합니다.

피트니스 기반 선택

이 피트니스 기반 선택에서 어린이는 인구 중 가장 적합하지 않은 개인을 대체하는 경향이 있습니다. 가장 적합하지 않은 개인의 선택은 토너먼트 선택, 피트니스 비례 선택 등 앞에서 설명한 선택 정책의 변형을 사용하여 수행 할 수 있습니다.

예를 들어, 다음 이미지에서 하위는 모집단에서 가장 적합하지 않은 개인 P1 및 P10을 대체합니다. P1과 P9는 동일한 적합성 값을 갖기 때문에 모집단에서 개인을 제거하는 결정은 임의적입니다.

유전자 알고리즘의 종료 조건은 GA 실행이 종료되는시기를 결정하는 데 중요합니다. 처음에는 GA가 몇 번의 반복마다 더 나은 솔루션이 제공되면서 매우 빠르게 진행되지만 개선이 매우 적은 후기 단계에서는 포화되는 경향이 있습니다. 일반적으로 실행이 끝날 때 솔루션이 최적에 가까워지는 종료 조건을 원합니다.

일반적으로 다음 종료 조건 중 하나를 유지합니다.

X 반복에 대한 모집단이 개선되지 않은 경우.
우리가 절대적인 수의 세대에 도달했을 때.
목적 함수 값이 미리 정의 된 특정 값에 도달했을 때.

예를 들어, 유전 알고리즘에서 우리는 인구가 개선되지 않은 세대를 추적하는 카운터를 유지합니다. 처음에는이 카운터를 0으로 설정했습니다. 인구의 개체보다 더 나은 자손을 만들지 않을 때마다 카운터를 증가시킵니다.

그러나 자손 중 체력이 더 좋으면 카운터를 0으로 재설정합니다. 카운터가 미리 결정된 값에 도달하면 알고리즘이 종료됩니다.

GA의 다른 매개 변수와 마찬가지로 종료 조건도 문제별로 매우 다르며 GA 설계자는 자신의 특정 문제에 가장 적합한 것이 무엇인지 확인하기 위해 다양한 옵션을 시도해야합니다.

지금까지이 튜토리얼에서 우리가 논의한 모든 것은 진화의 진화론 적 모델에 해당합니다. 자연 선택과 재조합과 돌연변이를 통한 유전 적 변이입니다. 본질적으로 개인의 유전자형에 포함 된 정보 만 다음 세대로 전달 될 수 있습니다. 이것이 지금까지 튜토리얼에서 따라온 접근 방식입니다.

그러나 평생 적응의 다른 모델은 Lamarckian Model 과 Baldwinian Model또한 존재합니다. 어떤 모델이 가장 좋은지 토론의 여지가 있으며 연구자들이 얻은 결과는 평생 적응의 선택이 매우 문제에 따라 다르다는 것을 보여줍니다.

종종 우리는 밈 알고리즘에서와 같이 GA를 지역 검색과 혼성화합니다. 이러한 경우 지역 검색 후 생성 된 개인에 대해 수행 할 작업을 결정하기 위해 Lamarckian 또는 Baldwinian Model 중 하나를 선택할 수 있습니다.

라마르 키안 모델

라마르 키안 모델은 본질적으로 개인이 일생 동안 획득 한 특성이 자손에게 전달 될 수 있다고 말합니다. 프랑스 생물 학자 Jean-Baptiste Lamarck의 이름을 따서 명명되었습니다.

하지만 자연 생물학은 유전형의 정보 만 전달 될 수 있다는 것을 우리 모두가 알고 있기 때문에 라마르크주의를 완전히 무시했습니다. 그러나 계산 관점에서 볼 때 Lamarckian 모델을 채택하면 일부 문제에 대해 좋은 결과를 제공하는 것으로 나타났습니다.

라마르 키안 모델에서 지역 검색 연산자는 이웃을 조사하고 (새로운 특성 획득) 더 나은 염색체가 발견되면 자손이됩니다.

볼드윈 모델

Baldwinian 모델은 James Mark Baldwin (1896)의 이름을 딴 중간 아이디어입니다. Baldwin 모델에서 염색체는 유익한 행동을 배우는 경향을 인코딩 할 수 있습니다. 즉, 라마르 키안 모델과 달리 획득 한 특성을 다음 세대로 전달하지 않으며 다윈 모델 에서처럼 획득 한 특성을 완전히 무시하지도 않습니다.

볼드윈 모델은이 두 극단의 중간에 있으며, 특정 특성을 획득하려는 개인의 경향이 특성 자체보다는 암호화되어 있습니다.

이 Baldwinian 모델에서 지역 검색 연산자는 이웃 (새로운 특성 획득)을 조사하고 더 나은 염색체가 발견되면 염색체에 개선 된 적합성 만 할당하고 염색체 자체를 수정하지 않습니다. 적합성의 변화는 비록 그것이 미래 세대에 직접 전달되지는 않지만 "특성을 획득"할 수있는 염색체 능력을 의미합니다.

GA는 본질적으로 매우 일반적이며 최적화 문제에 적용하는 것만으로는 좋은 결과를 얻을 수 없습니다. 이 섹션에서는 작업에서 GA 디자이너 또는 GA 구현자를 돕고 지원하는 몇 가지 사항을 설명합니다.

문제 별 도메인 지식 소개

우리가 GA에 통합하는 더 많은 문제 별 영역 지식이 관찰되었습니다. 더 나은 객관적 가치를 얻을 수 있습니다. 문제 별 교차 또는 변형 연산자, 사용자 지정 표현 등을 사용하여 문제 별 정보를 추가 할 수 있습니다.

다음 이미지는 EA에 대한 Michalewicz (1990)의 견해를 보여줍니다.

혼잡 감소

크라우 딩은 고도로 적합한 염색체가 많이 번식 할 때 발생하며 몇 세대 내에 전체 인구가 비슷한 적합성을 가진 유사한 솔루션으로 채워집니다. 이것은 GA의 성공을 보장하는 매우 중요한 요소 인 다양성을 감소시킵니다. 혼잡을 제한하는 방법에는 여러 가지가 있습니다. 그들 중 일부는-

Mutation 다양성을 소개합니다.
로 전환 rank selection 과 tournament selection 비슷한 체력을 가진 개인의 체력 비례 선택보다 선택 압력이 더 큽니다.
Fitness Sharing − 인구에 이미 유사한 개인이 포함되어있는 경우 개인의 체력이 감소합니다.

무작위 화가 도움이됩니다!

최적의 솔루션은 인구에 다양성을 부여하기 때문에 무작위 염색체에 의해 구동된다는 것이 실험적으로 관찰되었습니다. GA 구현자는 최상의 결과를 위해 모집단에서 충분한 양의 무작위 화와 다양성을 유지하도록주의해야합니다.

GA를 지역 검색과 하이브리드 화

로컬 검색은 더 나은 객관적인 값을 찾기 위해 주어진 솔루션 근처의 솔루션을 확인하는 것을 말합니다.

GA를 지역 검색과 혼성화하는 것이 때때로 유용 할 수 있습니다. 다음 이미지는 GA에서 지역 검색을 도입 할 수있는 다양한 위치를 보여줍니다.

매개 변수 및 기술의 변형

유전 알고리즘에는 모든 문제에 적용되는 "하나의 크기"나 마법의 공식이 없습니다. 초기 GA가 준비된 후에도 특정 문제에 적합한 항목을 찾기 위해 인구 크기, 돌연변이 및 교차 확률 등과 같은 매개 변수를 가지고 놀려면 많은 시간과 노력이 필요합니다.

이 섹션에서는 유전 알고리즘의 몇 가지 고급 주제를 소개합니다. GA 소개 만 찾는 독자는이 섹션을 건너 뛸 수 있습니다.

제약 된 최적화 문제

제약이있는 최적화 문제는 특정 제약이 적용되는 주어진 목적 함수 값을 최대화하거나 최소화해야하는 최적화 문제입니다. 따라서 솔루션 공간의 모든 결과가 실행 가능한 것은 아니며 다음 이미지와 같이 솔루션 공간에는 실행 가능한 영역이 포함됩니다.

이러한 시나리오에서 크로스 오버 및 돌연변이 연산자는 실행 불가능한 솔루션을 제공 할 수 있습니다. 따라서 제한된 최적화 문제를 처리 할 때 GA에서 추가 메커니즘을 사용해야합니다.

가장 일반적인 방법 중 일부는 다음과 같습니다.

사용 penalty functions 이는 실행 불가능한 솔루션의 적합성을 감소 시키며, 바람직하게는 위반 된 제약의 수 또는 실행 가능 영역으로부터의 거리에 비례하여 적합성이 감소됩니다.
사용 repair functions 실행 불가능한 솔루션을 취하고 위반 된 제약 조건이 충족되도록 수정합니다.
Not allowing infeasible solutions 인구에 전혀 들어 가지 않습니다.
사용 special representation or decoder functions 솔루션의 실현 가능성을 보장합니다.

기본 이론적 배경

이 섹션에서는 빌딩 블록 가설과 함께 스키마 및 NFL 정리에 대해 설명합니다.

스키마 정리

연구자들은 유전 알고리즘의 작동 뒤에있는 수학을 알아 내려고 노력해 왔으며 Holland의 Schema Theorem은 그 방향으로 나아가는 단계입니다. 한 해 동안 Schema Theorem을보다 일반적으로 만들기 위해 다양한 개선과 제안이 이루어졌습니다.

이 섹션에서는 스키마 정리의 수학을 탐구하지 않고 스키마 정리가 무엇인지에 대한 기본적인 이해를 개발하려고합니다. 알아야 할 기본 용어는 다음과 같습니다.

ㅏ Schema"템플릿"입니다. 공식적으로 알파벳 = {0,1, *} 위의 문자열입니다.

*는 상관 없으며 어떤 값도 취할 수 있습니다.

따라서 * 10 * 1은 01001, 01011, 11001 또는 11011을 의미 할 수 있습니다.

기하학적으로 스키마는 솔루션 검색 공간에서 하이퍼 플레인입니다.
Order 스키마의 수는 유전자에서 지정된 고정 위치의 수입니다.

Defining length 유전자에서 가장 먼 두 개의 고정 기호 사이의 거리입니다.

스키마 정리는 평균 이상의 적합성, 짧은 정의 길이 및 낮은 순서를 가진이 스키마가 교차 및 돌연변이에서 살아남을 가능성이 더 높다고 말합니다.

빌딩 블록 가설

빌딩 블록은 위에 주어진 평균 적합성을 가진 낮은 순서, 낮은 정의 길이 스키마입니다. 빌딩 블록 가설은 이러한 빌딩 블록이 이러한 "빌딩 블록"을 연속적으로 식별하고 재결합함으로써 진행됨에 따라 GA의 성공 및 적응을위한 토대 역할을한다고 말합니다.

무료 점심 없음 (NFL) 정리

1997 년 Wolpert와 Macready는 "최적화를위한 무료 점심 정리 없음"이라는 제목의 논문을 발표했습니다. 기본적으로 가능한 모든 문제의 공간에 대해 평균을 내면 재검토하지 않는 모든 블랙 박스 알고리즘이 동일한 성능을 나타냅니다.

이는 우리가 문제를 더 많이 이해할수록 GA가 더 구체적인 문제가되고 더 나은 성능을 제공하지만 다른 문제에 대해서는 성능이 저하되어이를 보완합니다.

GA 기반 머신 러닝

유전 알고리즘은 기계 학습에서도 적용됩니다. Classifier systems 의 한 형태이다 genetics-based machine learning머신 러닝 분야에서 자주 사용되는 (GBML) 시스템입니다. GBML 방법은 기계 학습에 대한 틈새 접근 방식입니다.

GBML 시스템에는 두 가지 범주가 있습니다.

The Pittsburg Approach −이 접근법에서는 하나의 염색체가 하나의 솔루션을 인코딩하므로 솔루션에 적합성이 할당됩니다.
The Michigan Approach − 일반적으로 하나의 솔루션은 많은 염색체로 표시되므로 적합성은 부분 솔루션에 할당됩니다.

크로스 오버, 뮤 테이션, 라마르 키안 또는 다 위니 안 등과 같은 표준 문제도 GBML 시스템에 존재한다는 점을 명심해야합니다.

유전 알고리즘은 주로 다양한 종류의 최적화 문제에 사용되지만 다른 응용 분야에서도 자주 사용됩니다.

이 섹션에서는 유전 알고리즘이 자주 사용되는 몇 가지 영역을 나열합니다. 이것들은-

Optimization− 유전 알고리즘은 주어진 제약 조건에서 주어진 목적 함수 값을 최대화하거나 최소화해야하는 최적화 문제에서 가장 일반적으로 사용됩니다. 최적화 문제를 해결하는 접근 방식은 튜토리얼 전체에서 강조되었습니다.
Economics − GA는 또한 거미줄 모델, 게임 이론 균형 해상도, 자산 가격 책정 등과 같은 다양한 경제 모델을 특성화하는 데 사용됩니다.
Neural Networks − GA는 신경망, 특히 순환 신경망을 훈련하는데도 사용됩니다.
Parallelization − GA는 또한 매우 우수한 병렬 기능을 가지고 있으며 특정 문제를 해결하는 데 매우 효과적인 수단이며 연구를위한 좋은 영역을 제공합니다.
Image Processing − GA는 고밀도 픽셀 매칭과 같은 다양한 디지털 이미지 처리 (DIP) 작업에 사용됩니다.
Vehicle routing problems − 여러 소프트 타임 윈도우, 여러 디포 및 이기종 차량.
Scheduling applications − GA는 다양한 스케줄링 문제, 특히 시간표 문제를 해결하는 데 사용됩니다.
Machine Learning − 이미 논의했듯이 유전학 기반 기계 학습 (GBML)은 기계 학습의 틈새 영역입니다.
Robot Trajectory Generation − GA는 로봇 팔이 한 지점에서 다른 지점으로 이동하는 경로를 계획하는 데 사용되었습니다.
Parametric Design of Aircraft − GA는 매개 변수를 변경하고 더 나은 솔루션을 발전시킴으로써 항공기를 설계하는 데 사용되었습니다.
DNA Analysis − GA는 샘플에 대한 분광 데이터를 사용하여 DNA 구조를 결정하는 데 사용되었습니다.
Multimodal Optimization − GA는 다중 최적 솔루션을 찾아야하는 다중 모드 최적화를위한 매우 좋은 접근 방식입니다.
Traveling salesman problem and its applications − GA는 새로운 교차 및 패킹 전략을 사용하는 잘 알려진 조합 문제인 TSP를 해결하는 데 사용되었습니다.

다음 책은 일반적으로 유전 알고리즘 및 진화 계산에 대한 독자의 지식을 더욱 향상시키기 위해 참조 할 수 있습니다.

검색, 최적화 및 기계 학습의 유전 알고리즘 David E. Goldberg.
유전 알고리즘 + 데이터 구조 = 진화 프로그램 Zbigniew Michalewicz.
실용적인 유전 알고리즘 Randy L. Haupt 과 Sue Ellen Haupt.
진화 알고리즘을 사용한 다중 목표 최적화 Kalyanmoy Deb.