저는 “게임 프로그래머를 위한 AI 기술”이라는 책의 기술을 기반으로 유전자 알고리즘을 작성하려고 합니다. 이 기술은 다음 집단의 유전자에 대해 이진 인코딩 및 적합성의 비례 선택(룰렛 휠 선택이라고도 함)을 사용합니다. 프로그램 내에서 2차원 배열로 무작위로 생성됩니다. 최근 의사 코드를 발견하고 이를 구현하려고 시도했지만, 내가 하려고 했던 작업의 세부 사항에 몇 가지 문제가 발생했습니다. 많은 책과 일부 오픈 소스 코드를 확인했지만 여전히 진행하는 데 어려움을 겪고 있습니다. 모집단의 전체 체력 합계를 구하고 합계와 0 사이에서 임의의 숫자를 선택해야 한다는 것을 이해합니다. 그런 다음 숫자가 상위 숫자보다 크면 덮어쓸 수 있지만 어려움을 겪고 있습니다. 이러한 아이디어를 구현하는 시간입니다. .Java는 녹슬었으므로 이러한 아이디어를 구현하는 데 도움을 주시면 대단히 감사하겠습니다. 당신이 찾고 있는 개념은 “룰렛 휠 따기”라고 합니다. 아직 확립된 적합도 기능은 없습니다(이는 각 개인의 적합도가 염색체의 필수 값임을 의미할 수 있음). 하지만 그렇게 할 때 일반적인 계획은 다음과 같습니다. 전체 모집단의 체력을 합산합니다. 0과 전체 적합도 사이에서 임의의 숫자(x라고 부르자)를 선택합니다. 인구에 대해 반복합니다. 각 구성원에 대해: x에서 구성원의 건강을 뺍니다. 이제 x가 0보다 작거나 같으면 현재 멤버를 선택합니다. 다른 동등한 구현이 있지만 일반적인 아이디어는 적합도에 비례하는 확률로 멤버를 선택하는 것입니다. 해야 할 일: 피트니스 기능에 대한 몇 가지 참고 사항. 염색체 표현(귀하의 경우 32비트 정수)은 이를 평가하는 데 사용되는 적합도 함수와 무관합니다. 예를 들어, 이진 인코딩은 일반적으로 염색체를 적절한 크기의 정수 값으로 압축된 비트 필드 세트로 취급합니다. 그런 다음 적절한 비트마스킹 작업을 통해 교차 및 돌연변이를 수행할 수 있습니다. 관심이 있으시면 비트 연산을 사용하여 이러한 기능을 구현하는 간단한 GA 코드(C 및 Python)를 게시해 드릴 수 있습니다. 귀하가 이러한 언어에 얼마나 익숙해졌는지 잘 모르겠습니다.
나는 선택 중에 배열의 각 요소를 반복할 필요성을 줄이기 위해 “누적 피트니스 배열”과 이진 검색을 생성하여 이 알고리즘을 구현했습니다. 모집단 크기 N에 대한 누적 피트니스 배열을 생성합니다. arr(N).arr(0) := ComputeFitness(individual(0))을 설정합니다. 그런 다음 각 후속 요소에 대해 X, arr(X) = arr(X-1) + ComputeFitness(individual(X) ). 0과 arr(N) 사이의 난수를 생성합니다(즉, 전체 적합도). 누적 피트니스 배열에서 적절한 인덱스를 찾으려면 이진 검색(예: Collections.binarySearch)을 사용하고 이 인덱스를 사용하여 개인을 선택합니다. 재생 단계 시작 시 피트니스 배열을 생성하기만 하면 여러 번 재사용할 수 있습니다. O(log N) 시간 안에 선택을 수행합니다. 여담이지만 토너먼트 선택은 구현하기가 훨씬 쉽습니다!
룰렛 휠 선택에 관한 다른 질문도 도움이 될 수 있습니다. 룰렛 휠 선택 알고리즘 유전 알고리즘에서 룰렛 선택 처음 한 시간 동안 나는 룰렛이 어떻게 작동하는지 설명하려고 했습니다. 두 번째에서는 Jarod Elliott가 일부 의사코드를 제공했습니다. 효율적인 구현에 대한 Adamski의 의견과 함께 이것들은 무언가를 작동시키는 데 충분할 것입니다.
다음은 GA의 전체 개요입니다. C/Java/Python/.으로 쉽게 코딩할 수 있도록 아주 자세하게 작성되어 있습니다.
/* 1. 모집단 초기화 */POP_SIZE = 모집단의 개인 수pop = newPop = ()for i=1 to POP_SIZE { pop.add( getRandomIndividual() )}/* 2. 현재 모집단 평가 */totalFitness = 0for i =1 ~ POP_SIZE { 피트니스 = pop(i).evaluate() totalFitness += 피트니스}끝나지 않은 상태_조건(최고의 피트니스, #반복, 개선 없음…){// 새로운 모집단 구축// 선택 사항: 엘리트주의: 다음에서 최고의 K 복사 현재 팝을 newPop으로 보내는 동안 newPop.size()
현재 피트니스 기능이 없습니다(도메인에 따라 다름). 크로스오버는 단순한 1점 크로스오버가 됩니다(이진 표현을 사용하기 때문입니다). 돌연변이는 무작위로 간단히 뒤집을 수 있습니다. 편집: 현재 코드 구조와 표기법을 고려하여 위의 의사 코드를 Java로 구현했습니다. 이는 결코 가장 효율적이거나 완전한 구현이 아닙니다. 나는 그것을 꽤 빨리 썼다는 것을 인정한다.individual.java
import java.util.Random;public class Individual{public static final int SIZE = 500;private int() gene = new int(SIZE);private int FitnessValue;public Individual() {}public int getFitnessValue() {return FitnessValue; }public void setFitnessValue(int FitnessValue) {this.fitnessValue = FitnessValue;}public int getGene(int index) {return gene(index);}public void setGene(int index, int gene) {this.genes(index) = gene ;}public void randGenes() { Random rand = new Random();for(int i=0; i