1. 소개

이 시리즈의 목적은 유전 알고리즘의 개념 을 설명하는 것입니다 .

유전 알고리즘은 자연에서와 동일한 프로세스를 사용하여 문제를 해결하도록 설계되었습니다. 선택, 재조합 및 돌연변이의 조합을 사용하여 문제에 대한 솔루션을 진화시킵니다.

가장 간단한 이진 유전 알고리즘 예제를 사용하여 이러한 알고리즘의 개념을 설명하는 것으로 시작하겠습니다.

2. 유전 알고리즘의 작동 방식

유전 알고리즘은 빠르게 성장하는 인공 지능 영역 인 진화 컴퓨팅의 일부입니다 .

알고리즘은 인구 라고 하는 일련의 솔루션 ( 개인으로 표시)으로 시작됩니다 . 새로운 모집단이 이전 모집단보다 나을 가능성이 있으므로 한 모집단의 솔루션을 가져 와서 새로운 모집단 을 형성하는 데 사용합니다 .

새로운 솔루션 ( 자손 ) 을 형성하기 위해 선택된 개체 는 자신의 적합성 에 따라 선택됩니다 . 더 적합할수록 더 많은 번식 기회를 갖게됩니다.

3. 이진 유전 알고리즘

간단한 유전 알고리즘의 기본 과정을 살펴 보겠습니다.

3.1. 초기화

초기화 단계에서 첫 번째 솔루션 역할을하는 랜덤의 인구 를 생성합니다 . 먼저 인구 가 얼마나 크고 우리가 기대하는 최종 해결책이 무엇인지 결정해야합니다 .

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

위의 예에서 인구 크기는 50이고 올바른 솔루션은 언제든지 변경할 수있는 이진 비트 문자열로 표시됩니다.

다음 단계에서는 원하는 솔루션을 저장하고 랜덤의 인구를 생성합니다 .

setSolution(solution);
Population myPop = new Population(populationSize, true);

이제 프로그램의 메인 루프를 실행할 준비가되었습니다.

3.2. 피트니스 체크

프로그램의 메인 루프에서 우리는 각 개인 을 피트니스 기능 으로 평가할 것입니다 (간단히 말하면 개인 이 좋을 수록 얻는 피트니스 기능의 가치가 더 높습니다).

while (myPop.getFittest().getFitness() < getMaxFitness()) {
    System.out.println(
      "Generation: " + generationCount
      + " Correct genes found: " + myPop.getFittest().getFitness());
    
    myPop = evolvePopulation(myPop);
    generationCount++;
}

의는 설명과 함께 시작하자 우리가 적자 얼마나 개인 :

public int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.getDefaultGeneLength()
      && i < solution.length; i++) {
        if (individual.getSingleGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

관찰 할 수 있듯이 두 개의 개별 개체를 조금씩 비교 합니다. 완벽한 해결책을 찾을 수 없다면 다음 단계 인 인구 의 진화로 진행해야합니다 .

3.3. 자식

이 단계에서는 새 인구 를 만들어야합니다 . 먼저, 적합성에 따라 인구 에서 두 개의 상위 개별 개체 를 선택 해야합니다 . 현 세대 의 최고의 개인 이 변경되지 않고 다음 세대로 이어질 수 있도록하는 것이 유익하다는 점에 유의하십시오 . 이 전략을 Elitism 이라고합니다 .

if (elitism) {
    newPopulation.getIndividuals().add(0, pop.getFittest());
    elitismOffset = 1;
} else {
    elitismOffset = 0;
}

두 가지 최고의 개인 개체 를 선택하기 위해 토너먼트 선택 전략 을 적용 할 것입니다 .

private Individual tournamentSelection(Population pop) {
    Population tournament = new Population(tournamentSize, false);
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.getIndividuals().size());
        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
    }
    Individual fittest = tournament.getFittest();
    return fittest;
}

각 토너먼트의 우승자 (가장 체력이 좋은 토너먼트)가 다음 단계 인 Crossover로 선정됩니다 .

private Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setSingleGene(i, indiv1.getSingleGene(i));
        } else {
            newSol.setSingleGene(i, indiv2.getSingleGene(i));
        }
    }
    return newSol;
}

크로스 오버에서 우리 는 무작위로 선택된 지점에서 선택된 각 개인의 비트를 교환 합니다. 전체 프로세스는 다음 루프 내에서 실행됩니다.

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
    Individual indiv1 = tournamentSelection(pop);
    Individual indiv2 = tournamentSelection(pop);
    Individual newIndiv = crossover(indiv1, indiv2);
    newPopulation.getIndividuals().add(i, newIndiv);
}

보시다시피, 크로스 오버 후에 우리는 새로운 개체군 에 새로운 자손을 배치 합니다. 이 단계를 수락 이라고합니다 .

마지막으로 Mutation을 수행 할 수 있습니다 . 돌연변이는 인구 의 한 세대 에서 다음 세대로 유전 적 다양성을 유지하는 데 사용됩니다 . 우리는 랜덤의 비트가 단순히 반전되는 비트 반전 유형의 변형을 사용했습니다 .

private void mutate(Individual indiv) {
    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
        if (Math.random() <= mutationRate) {
            byte gene = (byte) Math.round(Math.random());
            indiv.setSingleGene(i, gene);
        }
    }
}

모든 유형의 Mutation 및 Crossover 가이 예제에서 잘 설명 됩니다 .

그런 다음 최적의 솔루션과 같은 종료 조건에 도달 할 때까지 하위 섹션 3.2 및 3.3의 단계를 반복합니다.

4. 팁과 요령

효율적인 유전 알고리즘 을 구현하려면 매개 변수 집합을 조정해야합니다. 이 섹션에서는 가장 많이 가져 오는 매개 변수로 시작하는 방법에 대한 몇 가지 기본 권장 사항을 제공해야합니다.

  • 교차율 – 약 80 % -95 % 정도 높아야합니다.
  • 돌연변이율 – 0.5 % -1 % 정도로 매우 낮아야 합니다.
  • 인구 규모 – 좋은 인구 규모는 약 20-30 명 이지만 일부 문제의 경우 50-100 규모가 더 좋습니다.
  • 선택 – 기본 룰렛 선택 은 엘리트주의 개념과 함께 사용할 수 있습니다.
  • 크로스 오버 및 변형 유형 – 인코딩 및 문제에 따라 다릅니다.

튜닝에 대한 권장 사항은 종종 유전 알고리즘에 대한 경험적 연구의 결과이며 제안 된 문제에 따라 다를 수 있습니다.

5. 결론

이 예제 은 유전 알고리즘의 기초를 소개합니다 . 이 분야 에 대한 사전 지식 없이도 기본적인 컴퓨터 프로그래밍 기술 만 있으면서 유전 알고리즘에 대해 배울 수 있습니다 .

이 사용방법(예제)의 코드 조각에 대한 전체 소스 코드 는 GitHub 프로젝트에서 사용할 수 있습니다 .

또한 Lombok 을 사용 하여 게터와 세터를 생성합니다. 이 기사에서 IDE 에서 올바르게 구성하는 방법을 확인할 수 있습니다 .

유전 알고리즘의 추가 예를 보려면 시리즈의 모든 기사를 확인하십시오.