유전자 알고리즘은 '다윈의 자연 진화론'에서 영감을 받은 적응형 휴리스틱 검색 알고리즘입니다. .' 기계 학습의 최적화 문제를 해결하는 데 사용됩니다. 해결하는 데 오랜 시간이 걸리는 복잡한 문제를 해결하는 데 도움이 되므로 중요한 알고리즘 중 하나입니다.
유전 알고리즘은 다양한 실제 응용 분야에서 널리 사용되고 있습니다. 예를 들어, 전자 회로 설계, 코드 해독, 이미지 처리 및 인공 창의성.
본 주제에서는 Genetic 알고리즘에 사용되는 기본 용어, 작동 방식, Genetic 알고리즘의 장점과 한계 등 Genetic 알고리즘에 대해 자세히 설명합니다.
연결 자바 문자열
유전 알고리즘이란 무엇입니까?
Genetic 알고리즘을 이해하기 전에 먼저 이 알고리즘을 더 잘 이해하기 위해 기본 용어를 이해하겠습니다.
인구에 존재하는 모든 존재의 적합성을 계산한 후 인구의 어떤 개체가 다음 세대를 형성할 씨앗을 번식하고 생산할 것인지 결정하기 위해 선택 과정이 사용됩니다.
사용 가능한 선택 스타일 유형
이제 최적화 문제를 해결하기 위한 휴리스틱 검색 알고리즘으로 유전자 알고리즘을 정의할 수 있습니다. 이는 컴퓨팅에 사용되는 진화 알고리즘의 하위 집합입니다. 유전 알고리즘은 유전 및 자연 선택 개념을 사용하여 최적화 문제를 해결합니다.
유전 알고리즘은 어떻게 작동하나요?
유전자 알고리즘은 진화적인 세대 주기에 따라 작동하여 고품질 솔루션을 생성합니다. 이러한 알고리즘은 향상된 적합 솔루션을 제공하기 위해 모집단을 강화하거나 대체하는 다양한 작업을 사용합니다.
기본적으로 복잡한 최적화 문제를 해결하기 위해 다음과 같은 5단계가 포함됩니다.
1. 초기화
유전자 알고리즘의 과정은 인구라고 불리는 개체 집합을 생성하는 것부터 시작됩니다. 여기서 각 개인은 주어진 문제에 대한 해결책입니다. 개인은 유전자라고 불리는 일련의 매개변수를 포함하거나 이를 특징으로 합니다. 유전자는 끈으로 결합되어 염색체를 생성하는데, 이것이 문제의 해결책이다. 초기화에 가장 널리 사용되는 기술 중 하나는 임의의 이진 문자열을 사용하는 것입니다.
2. 체력 할당
피트니스 함수는 개인이 얼마나 적합한지 결정하는 데 사용됩니까? 이는 개인이 다른 개인과 경쟁할 수 있는 능력을 의미합니다. 모든 반복에서 개인은 적합성 기능을 기반으로 평가됩니다. 피트니스 기능은 각 개인에게 피트니스 점수를 제공합니다. 이 점수는 재생산 대상으로 선정될 확률을 추가로 결정합니다. 체력 점수가 높을수록 재생산 대상으로 선정될 확률이 높아집니다.
3. 선정
선택 단계에는 자손의 번식을 위한 개체의 선택이 포함됩니다. 선택된 모든 개체는 번식을 증가시키기 위해 두 쌍으로 배열됩니다. 그런 다음 이 개체들은 자신의 유전자를 다음 세대에 전달합니다.
다음과 같은 세 가지 유형의 선택 방법을 사용할 수 있습니다.
- 룰렛 휠 선택
- 토너먼트 선택
- 순위 기반 선택
4. 재생산
선택 과정이 끝나면 재생산 단계에서 자식이 생성됩니다. 이 단계에서 유전 알고리즘은 상위 모집단에 적용되는 두 가지 변형 연산자를 사용합니다. 재생산 단계에 관련된 두 연산자는 다음과 같습니다.
- 원포인트 크로스오버
- 2점 크로스오버
- 리버리 크로스오버
- 상속 가능한 알고리즘 크로스오버
부모의 유전자는 교차점이 충족될 때까지 서로 교환됩니다. 새로 생성된 자손이 개체군에 추가됩니다. 이 프로세스를 크로스오버라고도 합니다. 사용 가능한 크로스오버 스타일 유형:
돌연변이 연산자는 개체군의 다양성을 유지하기 위해 자손(새 자식)에 무작위 유전자를 삽입합니다. 염색체의 일부 비트를 뒤집어서 수행할 수 있습니다.
돌연변이는 조기 수렴 문제를 해결하는 데 도움이 되고 다양성을 향상시킵니다. 아래 이미지는 돌연변이 과정을 보여줍니다.
사용 가능한 돌연변이 스타일 유형,
5. 해지
재생 단계 이후에는 종료 기준으로 중지 기준이 적용됩니다. 알고리즘은 임계 적합성 솔루션에 도달한 후 종료됩니다. 최종 솔루션이 모집단에서 가장 좋은 솔루션으로 식별됩니다.
단순 유전 알고리즘의 일반적인 작업 흐름
유전 알고리즘의 장점
- 유전자 알고리즘의 병렬 기능이 가장 좋습니다.
- 이산함수, 다목적 문제, 연속함수 등 다양한 문제를 최적화하는 데 도움이 됩니다.
- 시간이 지남에 따라 개선되는 문제에 대한 솔루션을 제공합니다.
- 유전자 알고리즘에는 파생 정보가 필요하지 않습니다.
유전 알고리즘의 한계
- 유전 알고리즘은 단순한 문제를 해결하는 데 효율적인 알고리즘이 아닙니다.
- 문제에 대한 최종 솔루션의 품질을 보장하지는 않습니다.
- 적합도 값을 반복적으로 계산하면 일부 계산 문제가 발생할 수 있습니다.
유전 알고리즘과 기존 알고리즘의 차이점
- 검색 공간은 문제에 대한 가능한 모든 솔루션의 집합입니다. 기존 알고리즘에서는 한 세트의 솔루션만 유지되는 반면, 유전자 알고리즘에서는 검색 공간의 여러 솔루션 세트를 사용할 수 있습니다.
- 전통적인 알고리즘은 검색을 수행하기 위해 더 많은 정보가 필요한 반면, 유전자 알고리즘은 개인의 적합성을 계산하기 위해 단 하나의 목적 함수만 필요합니다.
- 전통적인 알고리즘은 병렬로 작동할 수 없는 반면, 유전적 알고리즘은 병렬로 작동할 수 있습니다(개인의 적합성을 계산하는 것은 독립적입니다).
- 유전 알고리즘의 한 가지 큰 차이점은 탐색자 결과에 직접적으로 작동하는 대신 상속 가능한 알고리즘이 흔히 염색체로 분류되는 표현(또는 렌더링)에 작동한다는 것입니다.
- 기존 알고리즘과 유전자 알고리즘의 가장 큰 차이점 중 하나는 후보 솔루션에 직접 작동하지 않는다는 것입니다.
- 전통적인 알고리즘은 결국 하나의 결과만 생성할 수 있는 반면, 유전 알고리즘은 다양한 세대에서 여러 개의 최적 결과를 생성할 수 있습니다.
- 전통적인 알고리즘은 최적의 결과를 생성할 가능성이 높지 않은 반면, 유전자 알고리즘은 전역적으로 최적의 결과를 생성한다고 보장하지는 않지만 Crossover, Mutation과 같은 유전 연산자를 사용하므로 문제에 대한 최적의 결과를 얻을 가능성이 큽니다.
- 기존 알고리즘은 본질적으로 결정론적인 반면, 유전 알고리즘은 본질적으로 확률론적입니다.