introduction genetic algorithms machine learning
자바에서 객체 배열 선언
이 유전 알고리즘 자습서는 유전 알고리즘이 무엇이며 기계 학습에서 그 역할을 자세히 설명합니다. :
에서 이전 튜토리얼 , 우리는 인공 신경망 모델 – Multilayer Perceptron, Backpropagation, Radial Bias & Kohonen Self Organizing Maps (아키텍처 포함)에 대해 배웠습니다.
우리는 신경망보다 이전에 나온 유전 알고리즘에 초점을 맞출 것이지만 이제는 NN이 GA를 인수했습니다. GA는 여전히 일정, 게임, 로봇 공학, 하드웨어 설계, 출장 세일즈맨 문제 등과 같은 최적화 문제와 같은 실제 생활에서 응용 프로그램을 가지고 있습니다.
유전 알고리즘은 자연 선택과 유전학에 대한 진화론 적 아이디어에 기반한 알고리즘입니다. GA는 적응 형 휴리스틱 검색 알고리즘입니다. 즉 알고리즘은 시간에 따라 변경되는 반복 패턴을 따릅니다. 따라야 할 올바른 경로를 말하지 않고 피드백이 필요한 강화 학습 유형입니다. 피드백은 긍정적이거나 부정적 일 수 있습니다.
=> 완전한 기계 학습 교육 시리즈 읽기
학습 내용 :
유전 알고리즘을 사용하는 이유
GA는 다양한 최적화 문제에 사용할 수있는보다 강력한 알고리즘입니다. 이러한 알고리즘은 다른 AI 알고리즘과 달리 노이즈가있는 경우 쉽게 벗어나지 않습니다. GA는 큰 공간 또는 다중 모드 공간 검색에 사용할 수 있습니다.
유전 알고리즘의 생물학적 배경
유전학은 성장을 의미하는 그리스어 'genesis'에서 파생되었습니다. 유전학은 진화 과정에서 자손 간의 유전 요인, 유사성 및 차이점을 결정합니다. 유전 알고리즘은 또한 자연 진화에서 파생됩니다.
생물학적 염색체의 일부 용어
- 염색체 : 한 종의 모든 유전 정보는 염색체에 저장됩니다.
- 유전자 : 염색체는 유전자라고하는 여러 부분으로 나뉩니다.
- 대립 유전자 : 유전자는 개인의 특성을 식별합니다. 유전자 조합이 속성을 형성 할 가능성을 대립 유전자라고합니다. 유전자는 다른 대립 유전자를 가질 수 있습니다.
- 유전자 풀 : 모집단 풀에서 모든 대립 유전자 인 유전자의 가능한 모든 조합을 유전자 풀이라고합니다.
- 게놈 : 한 종의 유전자 세트를 게놈이라고합니다.
- 현장: 각 유전자는 유전자좌 (locus)라고하는 게놈에 위치합니다.
- 유전자형: 개인의 완전한 유전자 조합을 유전자형이라고합니다.
- 표현형 : 해독 된 형태의 일련의 유전자형을 표현형이라고합니다.
유전 알고리즘이란?
유전 알고리즘은 진화를위한 자연계에서와 같이 과정을 자극합니다. Charles Darwin은 자연 진화에서 생물학적 존재가“적자 생존”원칙에 따라 진화한다는 진화론을 언급했습니다. GA 검색은 '적자 생존'이론을 장려하도록 설계되었습니다.
GA는 최적화 문제를 해결하기 위해 무작위 검색을 수행합니다. GA는 이전 기록 정보를 사용하는 기술을 사용하여 새 검색 공간에서 검색을 최적화합니다.
GA와 염색체의 상관 관계
인체에는 유전자로 구성된 염색체가 있습니다. 특정 종의 모든 유전자 세트를 게놈이라고합니다. 살아있는 존재에서 게놈은 다양한 염색체에 저장되는 반면 GA에서는 모든 유전자가 동일한 염색체에 저장됩니다.
자연 진화와 유전 알고리즘 용어의 비교
| 자연 진화 | 유전 알고리즘 |
|---|---|
| 염색체 | 끈 |
| 유전자 | 특색 |
| 대립 유전자 | 기능 가치 |
| 유전자형 | 코딩 된 문자열 |
| 표현형 | 디코딩 된 구조 |
GA의 중요한 용어
- 인구: 개인의 그룹입니다. 모집단에는 테스트중인 개인 수, 검색 공간 정보 및 표현형 매개 변수가 포함됩니다. 일반적으로 모집단은 무작위로 초기화됩니다.
- 개인 : 개인은 인구의 단일 솔루션입니다. 개인은 유전자라고하는 매개 변수 세트를 가지고 있습니다. 유전자가 결합되어 염색체를 형성합니다.
- 유전자 : 유전자는 유전 알고리즘의 구성 요소입니다. 염색체는 유전자로 구성됩니다. 유전자는 문제에 대한 해결책을 결정할 수 있습니다. 임의 길이의 비트 (0 또는 1) 문자열로 표시됩니다.
- 적합: 적합성은 문제의 표현형의 가치를 알려줍니다. 피트니스 함수는 솔루션이 최적 솔루션에 얼마나 가까운지를 알려줍니다. 피트니스 함수는 문제와 관련된 모든 매개 변수의 합 (유클리드 거리 등)과 같은 여러 방법으로 결정됩니다. 피트니스 함수를 평가하는 규칙은 없습니다.
간단한 유전 알고리즘
단순 GA에는 개별 염색체 집단이 있습니다. 이 염색체는 가능한 해결책을 나타냅니다. 복제 연산자는 돌연변이 및 재조합을 수행하기 위해 이러한 염색체 세트에 적용됩니다. 따라서 GA의 행동이 그것에 의존하기 때문에 적절한 재생산 연산자를 찾는 것이 중요합니다.
간단한 유전 알고리즘은 다음과 같습니다.
#1) 무작위로 생성 된 인구부터 시작합니다.
#두) 각 염색체의 피트니스 기능을 계산합니다.
#삼) n 개의 자손이 생성 될 때까지 단계를 반복합니다. 자손은 아래와 같이 생성됩니다.
- 모집단에서 한 쌍의 염색체를 선택하십시오.
- 확률 p로 쌍을 교차씨자손을 형성합니다.
- 확률 p로 교차 변형미디엄.
# 4) 원래 모집단을 새 모집단으로 바꾸고 2 단계로 이동합니다.
이 반복 프로세스에서 따르는 단계를 살펴 보겠습니다. 염색체의 초기 집단이 생성됩니다. 초기 모집단에는 모든 솔루션이 생성 될 수 있도록 충분한 유전자가 있어야합니다. 첫 번째 모집단 풀은 무작위로 생성됩니다.
- 선택: 최적의 유전자 세트는 피트니스 기능에 따라 선택됩니다. 최고의 피트니스 기능을 가진 스트링이 선택됩니다.
- 생식: 새로운 자손은 재조합과 돌연변이에 의해 생성됩니다.
- 평가: 생성 된 새로운 염색체는 적합성에 대해 평가됩니다.
- 바꿔 놓음: 이 단계에서 이전 인구는 새로 생성 된 인구로 대체됩니다.
룰렛 휠 선택 방법
룰렛 휠 선택은 널리 사용되는 선택 방법입니다.
선택 과정은 아래와 같이 짧습니다.
이 방법에서는 룰렛 휠을 통해 선형 검색이 수행됩니다. 휠의 슬롯은 개별 피트니스 값에 따라 무게가 측정됩니다. 대상 값은 모집단의 적합성 합계 비율에 따라 무작위로 설정됩니다.
그런 다음 목표 값에 도달 할 때까지 모집단을 검색합니다. 이 방법은 개인의 적자를 보장하지는 않지만 적자 일 가능성이 있습니다.
룰렛 휠 선택과 관련된 단계를 살펴 보겠습니다.
개인의 기대 가치 = 개인의 적합성 / 인구의 적합성. 휠 슬롯은 체력에 따라 개인에게 할당됩니다. 바퀴는 N 번 회전합니다. 여기서 N은 인구의 총 개인 수입니다. 한 번의 회전이 끝나면 선택한 개인은 부모 풀에 배치됩니다.
- 모집단에있는 여러 개인의 총 기대 값을 S라고합니다.
- 3-5n 번 단계를 반복합니다.
- 0과 S 사이의 정수 s를 선택하십시오.
- 모집단의 개인을 반복하고 합계가 s보다 클 때까지 예상 값을 합산합니다.
- 기대 값이 한도를 초과하는 개인이 선택됩니다.
룰렛 휠 선택의 단점 :
- 체력이 매우 다르면 룰렛 휠의 둘레가 가장 높은 체력 기능 염색체에 의해 최대가되므로 나머지는 선택 될 기회가 거의 없습니다.
- 시끄 럽습니다.
- 진화는 인구 적합성의 차이에 따라 달라집니다.
기타 선택 방법
에서 사용되는 다른 많은 선택 방법이 있습니다. '선택' 유전 알고리즘의 단계.
널리 사용되는 다른 두 가지 방법에 대해 설명합니다.
# 1) 순위 선택 : 이 방법에서는 모든 염색체에 순위의 적합성 값이 부여됩니다. 최악의 체력은 1이고 최적의 체력은 N입니다. 느린 수렴 방법입니다. 이 방법에서는 다양성이 보존되어 성공적인 검색으로 이어집니다.
잠재적 인 부모를 선택하고 토너먼트를 개최하여 부모가 될 개인을 결정합니다.
# 2) 토너먼트 선택 : 이 방법에서는 선택적인 압력 전략이 모집단에 적용됩니다. 최고의 개인은 체력이 가장 높은 사람입니다. 이 개인은 인구의 Nu 개인 간의 토너먼트 대회 우승자입니다.
우승자와 함께 토너먼트 인구가 다시 풀에 추가되어 새로운 자손을 생성합니다. 짝짓기 풀에서 승자와 개인의 체력 값의 차이는 최적의 결과를위한 선택적 압력을 제공합니다.
크로스 오버
2 명의 개인을 데리고 그들로부터 아이를 생산하는 과정입니다. 선택 후 번식 과정은 좋은 찌르기의 클론을 만듭니다. 크로스 오버 연산자는 더 나은 자손을 생산하기 위해 현에 적용됩니다.
크로스 오버 연산자의 구현은 다음과 같습니다.
- 개체군에서 무작위로 두 개체를 선택하여 자손을 낳습니다.
- 교차 사이트는 문자열 길이를 따라 무작위로 선택됩니다.
- 사이트의 값이 바뀝니다.
수행되는 크로스 오버는 단일 포인트 크로스 오버, 2 포인트 크로스 오버, 멀티 포인트 크로스 오버 등이 될 수 있습니다. 단일 포인트 크로스 오버에는 1 개의 크로스 오버 사이트가있는 반면 2 포인트 크로스 오버 사이트에는 값이 스왑되는 2 개의 사이트가 있습니다.
아래 예에서이를 확인할 수 있습니다.
단일 포인트 크로스 오버
2 점 크로스 오버
교차 확률
피씨, 교차 확률은 교차가 수행되는 빈도를 설명하는 용어입니다. 0 % 확률은 새로운 염색체가 이전 염색체의 정확한 사본이됨을 의미하고 100 % 확률은 모든 새로운 염색체가 교차로 만들어 짐을 의미합니다.
돌연 변이
Crossover 후에 돌연변이가 이루어집니다. 크로스 오버는 현재 솔루션에만 초점을 맞추지 만 변형 작업은 전체 검색 공간을 검색합니다. 이 방법은 잃어버린 유전 정보를 복구하고 유전 정보를 배포하는 것입니다.
이 연산자는 인구의 유전 적 다양성을 유지하는 데 도움이됩니다. 지역 최소값을 방지하고 모든 인구로부터 쓸모없는 솔루션을 생성하는 것을 방지합니다.
돌연변이는 작은 확률로 각 유전자의 가치를 반전 시키거나 용액의 질이 향상 될 때만 돌연변이를 수행하는 등 다양한 방법으로 수행됩니다.
일부 돌연변이 방법은 다음과 같습니다.
- 뒤집기 : 0에서 1 또는 1에서 0으로 변경합니다.
- 교환 : 두 개의 임의 위치가 선택되고 값이 서로 바뀝니다.
- 반전 : 임의 위치가 선택되고 그 옆의 비트가 반전됩니다.
각각의 몇 가지 예를 살펴 보겠습니다.
뒤집기
교환
반전
돌연변이 확률
피미디엄, 돌연변이 확률은 염색체의 돌연변이 빈도를 결정하는 용어입니다. 돌연변이 확률이 100 %이면 전체 염색체가 변경되었음을 의미합니다. 돌연변이가 수행되지 않으면 교차 후 바로 새로운 자손이 생성됩니다.
일반적인 유전 알고리즘의 예 돌연변이 확률 : 피미디엄, 돌연변이 확률은 염색체의 돌연변이 빈도를 결정하는 용어입니다. 돌연변이 확률이 100 %이면 전체 염색체가 변경되었음을 의미합니다.
돌연변이가 수행되지 않으면 교차 직후 새로운 자손이 생성됩니다. 염색체의 초기 모집단은 A, B, C, D로 제공됩니다. 모집단 크기는 4입니다.
피트니스 함수는 문자열에서 1의 숫자로 간주됩니다.
| 염색체 | 적합 |
|---|---|
| 받는 사람 : 00000110 | 두 |
| B : 11101110 | 6 |
| C : 00100000 | 1 |
| D : 00110100 | 삼 |
체력의 합은 12이며 평균 체력 함수는 ~ 12/4 = 3이됩니다.
교차 확률 = 0.7
돌연변이 확률 = 0.001
#1) B와 C를 선택하면 C의 체력 값이 평균 체력보다 낮기 때문에 크로스 오버가 수행되지 않습니다.
#두) B가 돌연변이 됨 => B : 11101110-> B': 인구 다양성 보존을위한 01101110
#삼) B와 D를 선택하면 크로스 오버가 수행됩니다.
B : 11101110 E : 10110100 –> D : 00110100 F : 01101110
# 4) E가 변이되면
E : 10110100-> E': 10110000
해당 염색체는 아래 표에 나와 있습니다. 순서는 무작위로 지정됩니다.
| 염색체 | 적합 |
|---|---|
| A : 01101110 | 5 |
| B : 00100000 | 1 |
| C : 10110000 | 삼 |
| D : 01101110 | 5 |
체력 값이 6 인 가장 적합한 개인이 손실 되더라도 인구의 전체 평균 체력이 증가하고 다음과 같이됩니다. 14/4 = 3.5
유전 알고리즘을 중지해야하는 경우
아래 나열된 일부 조건이 충족되면 유전 알고리즘이 중지됩니다.
# 1) 최고의 개인 수렴 : 최소 체력 수준이 수렴 값 아래로 떨어지면 알고리즘이 중지됩니다. 더 빠른 수렴으로 이어집니다.
# 2) 최악의 개인 수렴 : 모집단에서 최소 적합 개인이 수렴 미만의 최소 적합 값에 도달하면 알고리즘이 중지됩니다. 이 방법에서는 최소 체력 표준이 모집단에서 유지됩니다. 이는 최고의 개인이 보장되지는 않지만 개인의 최소 체력 가치가 있음을 의미합니다.
# 3) 적합성 합계 : 이 방법에서는 적합성의 합이 수렴 값보다 작거나 같으면 검색이 중지됩니다. 모든 인구가 체력 범위 내에 있음을 보장합니다.
# 4) 중간 피트니스 : 이 방법에서는 모집단의 개인 중 최소 절반이 수렴 값보다 크거나 같을 것입니다.
일부 수렴 기준 또는 중지 조건은 다음과 같습니다.
- 지정된 수의 세대가 진화했을 때.
- 알고리즘을 실행하기 위해 지정된 시간이 충족되었을 때.
- 모집단의 적합성 값이 반복으로 더 이상 변경되지 않는 경우.
유전 알고리즘의 장점 및 단점
유전 알고리즘의 장점은 다음과 같습니다.
- 솔루션 공간이 더 넓습니다.
- 글로벌 최적을 찾는 것이 더 쉽습니다.
- 병행: 여러 GA는 서로 간섭하지 않고 동일한 CPU를 사용하여 함께 실행할 수 있습니다. 그들은 격리되어 병렬로 실행됩니다.
Limitations of GA :
- 피트니스 기능 식별은 제한 사항입니다.
- 알고리즘의 수렴이 너무 빠르거나 너무 느릴 수 있습니다.
- 교차, 돌연변이 확률, 모집단 크기 등과 같은 매개 변수를 선택하는 데 제한이 있습니다.
유전 알고리즘의 응용
GA는 고차원 문제를 해결하는 데 효과적입니다. GA는 검색 공간이 매우 크고 사용 가능한 수학적 문제 해결 기술이없고 다른 기존 검색 알고리즘이 작동하지 않을 때 효과적으로 사용됩니다.
GA가 사용되는 일부 애플리케이션 :
- 최적화 문제 : 최적화 문제의 가장 좋은 예 중 하나는 GA를 사용하는 여행 세일즈맨 문제입니다. 작업 스케줄링, 음질 최적화 GA와 같은 다른 최적화 문제가 널리 사용됩니다.
- 면역 시스템 모델 : GA는 진화 기간 동안 개별 유전자 및 다중 유전자 패밀리에 대한 면역 체계의 다양한 측면을 모델링하는 데 사용됩니다.
- 기계 학습 : GA는 분류, 예측, 학습 및 분류 규칙 생성과 관련된 문제를 해결하는 데 사용되었습니다. .
결론
유전 알고리즘은 자연 진화 방법을 기반으로합니다. 이러한 알고리즘은 인코딩 된 매개 변수 (0 또는 1)를 사용하기 때문에 다른 분류 알고리즘과 다릅니다. 모집단에 여러 개인이 있으며 수렴을 위해 확률 적 방법을 사용합니다.
교차 및 돌연변이 과정에서 GA는 연속적인 세대에 수렴합니다. GA 알고리즘을 실행한다고해서 항상 성공적인 솔루션이 보장되는 것은 아닙니다. 유전 알고리즘은 작업 스케줄링 문제인 최적화에서 매우 효율적입니다.
이 튜토리얼이 유전 알고리즘의 개념에 대한 지식을 풍부하게 해주기를 바랍니다 !!
=> 독점적 인 기계 학습 시리즈를 보려면 여기를 방문하십시오
추천 도서
- 유전 알고리즘을 사용한 모델 기반 테스트
- 데이터 마이닝 대 기계 학습 대 인공 지능 대 딥 러닝
- 기계 학습 자습서 : ML 및 응용 프로그램 소개
- 기계 학습의 유형 : 감독 대 비지도 학습
- 기계 학습의 인공 신경망에 대한 완벽한 가이드
- 2021 년 가장 인기있는 11 가지 머신 러닝 소프트웨어 도구
- 톱 13 최고의 머신 러닝 회사 (업데이트 된 2021 목록)
- 기계 학습에서 SVM (Support Vector Machine)이란?