유전 알고리즘: 자연 선택에 의한 검색 및 최적화

게시 됨: 2022-03-11

유전 알고리즘이란 무엇입니까?

지난 몇 년 동안 인공 지능(AI)에 대한 열광적인 반응이 있었습니다. 구글, 애플, 마이크로소프트와 같은 주요 기업들이 이 주제에 대해 적극적으로 노력하고 있습니다. 실제로 AI는 많은 목표, 접근 방식, 도구 및 응용 프로그램을 포괄하는 우산입니다. 유전 알고리즘(GA)은 가능한 많은 솔루션을 통해 지능적으로 검색하기 위한 도구 중 하나일 뿐입니다.

GA는 자연 진화에 존재하는 원리를 기반으로 하는 메타휴리스틱 검색 및 최적화 기술입니다. 더 큰 종류의 진화 알고리즘에 속합니다.

GA는 문제에 대한 일련의 잠재적인 해결책인 염색체 집단을 유지합니다. 아이디어는 "진화"가 자연 선택과 유사하게 연속적인 여러 세대 후에 문제에 대한 최적의 솔루션을 찾을 것이라는 것입니다.

GA는 선택, 유전자 교차 및 돌연변이의 세 가지 진화 과정을 모방합니다.

자연 선택과 유사하게 GA 선택의 중심 개념은 적합성입니다. 더 적합한 염색체가 더 나은 생존 기회를 갖습니다. 피트니스는 염색체가 나타내는 솔루션의 품질을 측정하는 함수입니다. 본질적으로 모집단 내의 각 염색체는 입력 매개변수를 나타냅니다. 예를 들어 문제에 거래 가격 및 거래량과 같은 두 가지 입력 매개변수가 포함되어 있는 경우 각 염색체는 논리적으로 두 가지 요소로 구성됩니다. 요소가 염색체 내에서 인코딩되는 방식은 다른 주제입니다.

선택하는 동안 염색체는 번식 을 위한 부모 쌍을 형성합니다. 각 어린이 는 부모에게서 특성을 취합니다. 기본적으로 자식은 부모의 특성을 조합한 것입니다. 특성 중 일부는 한 부모에게서 가져오고 일부는 다른 부모에게서 가져옵니다. 재조합 외에도 일부 특성은 .

더 건강한 염색체는 더 많은 자녀를 낳기 때문에 각 후속 세대는 더 나은 적합성을 갖게 될 것입니다. 어느 시점에서 세대는 우리 문제에 대한 충분한 해결책을 나타내는 염색체를 포함할 것입니다.

GA는 강력하고 복잡한 문제에 광범위하게 적용할 수 있습니다. 기존의 최적화 기술로는 해결하기 어려운 많은 종류의 최적화 문제가 있습니다. 유전 알고리즘은 솔루션이 거의 최적인 효율적인 알고리즘입니다. 잘 알려진 응용 프로그램에는 일정, 운송, 라우팅, 그룹 기술, 레이아웃 설계, 신경망 교육 등이 포함됩니다.

실천하기

우리가 살펴볼 예는 GA의 "Hello World"로 간주될 수 있습니다. 이 예제는 처음에 J. Freeman이 Simulating Neural Networks with Mathematica 에서 제공했습니다. Mitsuo Gen과 Runwei Cheng의 Genetic Algorithms and Engineering Design 에서 가져왔습니다.

단어 짝짓기 문제는 유전 알고리즘으로 표현을 발전시키려고 합니다. 처음에 알고리즘은 무작위로 생성된 문자 목록에서 "~일지 여부" 구를 "추측"해야 합니다.

목록의 13개 위치[공백 제외] 각각에 대해 26개의 가능한 문자가 있으므로 순수한 임의 방식으로 올바른 구문을 얻을 확률은 (1/26)^13=4.03038×10-19이며, 이는 약 100억 중 두 번의 기회(Gen & Chong, 1997).

여기서 문제를 좀 더 광범위하게 정의하여 솔루션을 훨씬 더 어렵게 만듭니다. 우리가 영어나 특정 문구에 국한되지 않는다고 가정해 봅시다. 우리는 결국 모든 알파벳이나 기호 집합을 다룰 수 있습니다. 우리는 언어에 대한 지식이 없습니다. 우리는 언어가 있는지조차 모릅니다.

상대방이 공백을 포함한 임의의 구문을 생각했다고 가정해 보겠습니다. 우리는 구의 길이와 알파벳의 기호 수를 알고 있습니다. 그것이 우리가 가진 유일한 지식입니다. 각 추측 후, 상대는 우리에게 얼마나 많은 글자가 있는지 알려줍니다.

각 염색체는 알파벳 기호의 인덱스 시퀀스입니다. 영어 알파벳에 대해 이야기하는 경우 'a'는 0, 'b'는 1, 'c'는 2 등으로 표시됩니다. 따라서 예를 들어 단어 "be"는 [4, 1] 로 표시됩니다.

Java 코드 조각을 통해 모든 단계를 보여주지만 각 단계를 이해하는 데 Java 지식이 필요한 것은 아닙니다.

유전 알고리즘 코어

유전자 알고리즘의 일반적인 구현으로 시작할 수 있습니다.

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

이것은 모든 GA가 어느 정도 구성되는 간단한 단계 세트입니다. 초기화 단계에서 초기 구 모집단을 생성합니다. 모집단의 크기는 populationSize 에 의해 결정됩니다. 구문이 생성되는 방법은 supplier 의 구현에 따라 다릅니다.

반복 단계 내에서 while 루프의 테스트 내에서 종료 조건이 충족될 때까지 모집단을 발전시킵니다. 종료 조건에는 세대 수와 모집단의 문구 중 하나의 정확한 일치가 모두 포함될 수 있습니다. termination 는 정확한 구현을 캡슐화합니다.

각 반복 내에서 일반적인 GA 단계를 수행합니다.

  1. 염색체 적합도를 기반으로 모집단에 대해 선택을 수행합니다.
  2. 크로스오버 작업을 통해 새로운 "세대"를 생성합니다.
  3. 일부 구에서 일부 문자의 재조합을 수행하십시오.

알고리즘의 핵심은 매우 간단하고 도메인에 구애받지 않습니다. 모든 문제가 마찬가지일 것입니다. 조정해야 할 것은 유전 연산자의 구현입니다. 다음으로 앞에서 언급한 각 GA 연산자를 자세히 살펴보겠습니다.

선택

우리가 이미 알고 있듯이 선택은 현재 염색체의 후계자, 즉 우리 문제에 더 적합한 염색체를 찾는 과정입니다. 선택하는 동안 더 나은 적합성을 가진 염색체가 더 나은 생존 기회를 갖도록 해야 합니다.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

이 구현의 이면에 있는 아이디어는 다음과 같습니다. 인구는 숫자 축에서 결과 범위로 표시됩니다. 전체 인구는 0과 1 사이입니다.

유전자 알고리즘의 선택 단계가 어떻게 작동하는지 시각적으로 보여줍니다.

염색체가 차지하는 범위의 덩어리는 적합도에 비례합니다. 결과적으로 더 적합한 염색체가 더 큰 덩어리를 얻습니다. 그런 다음 무작위로 0과 1 사이의 숫자를 엿보고 숫자를 포함하는 범위를 찾습니다. 분명히, 더 큰 범위는 선택될 가능성이 더 높으므로 더 적합한 염색체가 더 나은 생존 기회를 갖습니다.

피트니스 함수에 대한 세부 정보를 모르기 때문에 피트니스 값을 정규화해야 합니다. 적합성 함수는 fitness 으로 표현되며, 이는 염색체를 염색체 적합성을 나타내는 임의의 이중으로 변환합니다.

코드에서 모집단의 모든 염색체에 대한 적합도를 찾고 전체 적합도도 찾습니다. for 루프 내에서 전체 적합도에 의해 축소된 확률에 대해 누적 합계를 수행합니다. 수학적으로 이것은 최종 변수의 값이 1이 되어야 합니다. 부동 소수점의 부정확성으로 인해 이를 보장할 수 없으므로 확실히 하기 위해 1로 설정합니다.

마지막으로 입력된 염색체의 수와 동일한 횟수만큼 난수를 생성하고 그 숫자를 포함하는 범위를 찾은 다음 해당 염색체를 선택합니다. 알다시피 동일한 염색체가 여러 번 선택될 수 있습니다.

크로스오버

이제 우리는 "교배"하기 위해 염색체가 필요합니다.

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

사전 정의된 확률 crossoverProbability 를 사용하여 육종을 위한 부모를 선택합니다. 선택한 상위 항목이 섞여서 모든 조합이 발생할 수 있습니다. 우리는 부모 쌍을 취하고 crossover 연산자를 적용합니다. 모집단의 크기를 동일하게 유지해야 하기 때문에 각 쌍에 대해 연산자를 두 번 적용합니다. 아이들은 인구에서 부모를 대체합니다.

돌연변이

마지막으로 특성의 재조합을 수행합니다.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

사전 정의된 확률 mutationProbability 를 사용하여 염색체에 "돌연변이"를 수행합니다. 돌연변이 자체는 mutation 로 정의됩니다.

문제별 알고리즘 구성

이제 일반 구현에 제공해야 하는 문제별 매개변수 유형을 살펴보겠습니다.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

매개변수는 각각 다음과 같습니다.

  1. 크로스오버 연산자
  2. 교차 확률
  3. 피트니스 기능
  4. 돌연변이 연산자
  5. 돌연변이 확률
  6. 인구 규모
  7. 초기 모집단에 대한 염색체 공급자
  8. 종료 기능

문제의 구성은 다음과 같습니다.

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

교차 연산자 및 확률

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

교차 가능성은 0.25이므로 평균적으로 염색체의 25%가 교차를 위해 선택될 것으로 예상합니다. 한 쌍의 염색체 교차를 위한 간단한 절차를 수행합니다. [0..length] 범위에서 난수 n 을 생성합니다. 여기서 length 는 염색체의 길이입니다. 이제 우리는 한 염색체에서 처음 n 문자를 취하고 두 번째 염색체에서 나머지 문자를 취하여 선택된 쌍을 짝짓기합니다.

피트니스 기능

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

적합성 기능은 단순히 대상 구와 주어진 염색체 사이의 일치 수를 계산합니다.

돌연변이 연산자 및 확률

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

돌연변이 작업은 각 염색체에서 독립적으로 수행됩니다. 돌연변이 확률은 0.05이므로 평균적으로 인구의 5%가 돌연변이될 것으로 예상합니다. 임의의 문자 위치를 선택하고 그 값을 알파벳의 임의 문자로 교체하여 돌연변이를 일으킵니다. 각 돌연변이 염색체에 대해 두 번 수행합니다.

공급업체

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

공급자는 알파벳에서 임의의 문자를 가져와 임의의 구문을 생성합니다. 각 구에는 미리 정의된 일정한 길이가 있습니다.

종료 기능

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

종료 함수는 호출 횟수를 계산하고 정확히 일치하는 항목이 있거나 생성 횟수가 3,000에 도달하면 true 를 반환합니다.

실행

이제 알고리즘을 테스트할 준비가 되었습니다. 여러 번 실행하면 모든 실행이 성공하는 것은 아님을 알 수 있습니다. 매번 반복 횟수가 다릅니다. 이는 알고리즘의 확률적 특성 때문입니다. 알고리즘에는 개선할 수 있는 몇 가지 지점이 있습니다. 교차 및 돌연변이 확률로 플레이할 수 있습니다.

숫자를 낮추면 안정적이지만 느린 솔루션이 됩니다. 적은 수의 염색체가 유전 연산자의 영향을 받으므로 솔루션에 더 많은 반복이 필요합니다.

숫자를 늘리면 알고리즘 속도가 빨라지지만 솔루션이 불안정해집니다. 맞춤 염색체는 보존될 뿐만 아니라 유전 조작자의 영향을 받습니다. 따라서 그들은 "좋은" 유전자를 잃게 됩니다.

좋은 균형을 찾는 것이 중요합니다. 반복 횟수를 늘리면 알고리즘에 솔루션을 찾을 수 있는 더 많은 기회가 제공되지만 다른 한편으로는 더 많은 시간이 걸립니다. 또한 다양한 교차 및 돌연변이 방법을 적용할 수 있습니다. 이러한 연산자를 잘 선택하면 솔루션의 품질이 크게 향상됩니다.

다음은?

우리는 여기에서 빙산의 일각을 다루었습니다. 우리는 입력이 하나만 있는 예를 들었고 입력은 쉽게 염색체로 표시될 수 있습니다. 유전 연산자는 단순하고 단순합니다.

실제 문제를 가지고 유전 알고리즘을 적용하는 것은 매우 흥미롭습니다. 실제 입력 데이터를 인코딩하는 다양한 접근 방식과 다양한 교차 및 돌연변이 구현을 발견하게 될 것입니다.

메트릭을 최적화하기 위해 추측해야 하는 매개변수 집합을 통해 문제를 표현할 수 있다면 문제를 해결하는 데 사용할 수 있는 GA를 빠르게 설정할 수 있습니다.

가장 흥미로운 문제 중 하나는 인공 신경망을 가르치는 것입니다. 최적화 가능한 매개변수를 시냅스 강도로 설정하고 적합성 메트릭을 신경망이 정답을 제공한 입력의 백분율로 설정할 수 있습니다. 그 후에 우리는 편안하게 앉아서 신경망이 우리가 원하는 이상적인 솔루션으로 발전하도록 할 수 있습니다. 또는 적어도 우리가 충분히 좋은 것을 얻을 때까지 진화에는 시간이 걸리기 때문입니다.