Genetic Algorithm 유전알고리즘 - Introduction

Genetic Algorithm 유전알고리즘 - Introduction

유전자 알고리즘 (Genetic Algorithm, GA)은 유전학 및 자연 선택의 원칙을 기반으로하는 검색 기반 최적화 기법입니다. 문제를 해결하기 위해 평생 동안 걸리는 어려운 문제에 대해 최적 또는 거의 최적의 솔루션을 찾는 데 자주 사용됩니다. 이것은 주로 최적화 문제, 연구 및 기계 학습을 해결하는 데 사용됩니다.

Optimization

최적화는 더 나은 것을 만드는 과정입니다. 어떤 프로세스에서 다음 그림과 같이 일련의 입력과 일련의 출력이 있습니다.

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

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

What are Genetic Algorithms?

자연은 언제나 모든 인류에게 영감의 위대한 원천이었습니다. 유전자 알고리즘 (GA)은 자연 선택과 유전학의 개념에 기반한 검색 기반 알고리즘입니다. GA는 진화론 적 계산 (Evolutionary Computation)으로 알려진 계산의 훨씬 큰 부분의 하위 집합입니다.

GA는 존 홀랜드 (John Holland)와 미시간 대 (University of Michigan)의 학생과 동료들에 의해 개발되었으며, 특히 데이비드 이스트 골드버그 (David E. Goldberg)와 같은 대학의 학생들과 동료들에 의해 개발되었습니다.

GA에는 주어진 문제에 대한 풀이 또는 가능한 솔루션 군이 있습니다. 그런 다음이 해답은 재조합과 돌연변이 (자연 유전학 에서처럼)를 거쳐 새로운 아이를 생산하며,이 과정은 여러 세대에 걸쳐 반복됩니다. 각 개인 (또는 후보 솔루션)에는 적합성 값 (목적 함수 값에 따라)이 할당되고, 개개인에게는 더 많은 "fitter" 개인을 배우고 양성 할 기회가 더 많이 부여됩니다. 이것은 "가장 작은 자들의 생존"이라는 다윈 이론과 일치합니다.

이러한 방식으로 우리는 멈춤 기준에 도 할 때까지 세대에 따라 더 나은 개인이나 솔루션을 "진화"시킵니다.

유전 알고리즘은 본질적으로 충분히 랜덤 화되어 있지만, 과거의 정보도 활용하면서 무작위 지역 검색 (지금까지 최선을 추적하면서 다양한 무작위 솔루션을 시도하는 것)보다 훨씬 뛰어납니다.

Advantages of Genetic Algorithms

GAs는 다양한 장점을 가지고있어서 대단히 인기가 있습니다. 여기에는 -

- 파생 정보가 필요하지 않습니다 (많은 실제 문제에서 사용 가능하지 않을 수 있음).

- 기존 방법에 비해 빠르고 효율적입니다.

- 매우 우수한 병렬 기능을 갖추고 있습니다.

- 연속 및 이산 기능과 다중 목표 문제를 모두 최적화합니다.

- 단일 솔루션뿐만 아니라 "우수한"솔루션 목록을 제공합니다.

- 항상 문제에 대한 답변을 얻습니다.

- 검색 공간이 매우 크고 관련 매개 변수가 많은 경우에 유용합니다.

Limitations of Genteic Algorithms

어떤 기술과 마찬가지로, GAs는 또한 몇 가지 한계가 있습니다. 여기에는 -

- GA는 모든 문제, 특히 간단하고 파생 정보가 있는 문제에 적합하지 않습니다.

- Fitness 값은 반복적으로 계산되므로 일부 문제의 경우 컴퓨팅 비용이 많이 듭니다.

- 확률적이므로 솔루션의 최적 또는 품질에 대한 보장이 없습니다.

- 제대로 구현되지 않으면 GA가 최적의 솔루션으로 수렴되지 않을 수 있습니다.

Genetic Algorithms - Motivation

유전 알고리즘은 "충분히 좋은"솔루션을 "신속하게"제공 할 수 있습니다. 이것은 유전 알고리즘을 최적화 문제를 푸는데 사용하기에 매력적인 것으로 만듭니다. GAs가 필요한 이유는 다음과 같습니다.

Solving Difficult Problems

컴퓨터 과학에서는 NP-Hard라는 큰 문제가 있습니다. 이것이 본질적으로 의미하는 바는 심지어 가장 강력한 컴퓨팅 시스템조차도이 문제를 해결하는 데 아주 오랜 시간이 걸린다는 것입니다. 이러한 시나리오에서 GAs는 단기간 내에 사용할 수있는 거의 최적의 솔루션을 제공하는 효율적인 도구로 입증됩니다.

Failure of Gradient Based Methods

전통적인 미적분 기반 방법은 무작위 지점에서 시작하여 그라디언트 방향으로 이동하여 언덕 꼭대기에 도달 할 때까지 작동합니다. 이 기법은 효율적이며 선형 회귀 분석에서 비용 함수와 같은 단일 피크 목표 함수에서 매우 잘 작동합니다. 그러나 대부분의 실제 상황에서 우리는 많은 피크와 많은 골짜기로 만들어진 풍경으로 불리는 매우 복잡한 문제를 가지고 있습니다.이 문제는 그러한 방법을 실패하게 만듭니다. 왜냐하면 그들은 지역의 최적 상태에 고착되는 고유의 경향을 겪기 때문입니다 다음 그림과 같습니다.

Getting a Good Solution Fast

TSP (Traveling Salesperson Problem)와 같은 어려운 문제에는 경로 찾기 및 VLSI 디자인과 같은 실제 응용 프로그램이 있습니다. 이제 GPS 네비게이션 시스템을 사용 중이며 소스에서 목적지까지의 "최적의"경로를 계산하는 데 몇 분 (또는 심지어 몇 시간)이 걸린다 고 상상해보십시오. 이러한 실제 응용 프로그램에서의 지연은 용인 할 수 없으므로 "빠르다"는 "좋은"해결책이 필요합니다.

Basic Terminology

유전 알고리즘에 대한 논의를 시작하기 전에 사용되는 몇 가지 기본 용어에 대해 잘 알고 있어야합니다.

- 모집단(Population) - 주어진 문제에 대한 가능한 (인코딩 된) 모든 해답의 부분 집합입니다.

- 염색체 (chromosome) - 염색체는 주어진 문제에 대한 그러한 해답 중 하나입니다.

- 유전자 - 유전자는 염색체의 한 요소 위치입니다.

- 대립 유전자 (Allele) - 특정 염색체에 대해 유전자가 취하는 값입니다.

- Genotype - Genotype은 계산 공간의 모집단입니다. 계산 공간에서 솔루션은 컴퓨팅 시스템을 사용하여 쉽게 이해하고 조작 할 수있는 방식으로 표현됩니다.

- Phenotype - 표현형은 솔루션이 실제 상황에서 표현되는 방식으로 표현되는 실제 실제 솔루션 공간의 인구입니다.

- Decoding and Encoding - 간단한 문제의 경우 표현형과 유전자형 공간이 동일합니다. 그러나 대부분의 경우 표현형과 유전자형 공간이 다릅니다. 디코딩은 솔루션을 유전자형에서 표현형 공간으로 변환하는 과정이며, 인코딩은 표현형에서 유전자형 공간으로 변환하는 과정입니다. 디코딩은 피트니스 값 계산 중에 GA에서 반복적으로 수행되므로 빠르다.

- 적합도함수 (Fitness Function) - 단순히 정의 된 적합성 기능은 솔루션을 입력으로 가져 와서 솔루션의 출력을 출력으로 생성하는 기능입니다. 경우에 따라 적합도함수 과 목표 함수가 같을 수도 있지만 문제에 따라 다를 수도 있습니다.

- 유전 연산자 - 이것들은 자손의 유전 적 구성을 바꾼다. 여기에는 크로스 오버, 돌연변이, 선택 등이 포함됩니다.

Basic Structure

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