Генетические алгоритмы: поиск и оптимизация путем естественного отбора

Что такое генетические алгоритмы?

За последние несколько лет вокруг искусственного интеллекта (ИИ) возник огромный ажиотаж. Крупные компании, такие как Google, Apple и Microsoft, активно работают над этой темой. По сути, ИИ — это зонтик, который охватывает множество целей, подходов, инструментов и приложений. Генетические алгоритмы (ГА) — это лишь один из инструментов интеллектуального поиска среди множества возможных решений.

ГА — это метаэвристический метод поиска и оптимизации, основанный на принципах естественной эволюции. Он принадлежит к более широкому классу эволюционных алгоритмов.

ГА поддерживает популяцию хромосом — набор потенциальных решений проблемы. Идея состоит в том, что «эволюция» найдет оптимальное решение проблемы после ряда последовательных поколений — подобно естественному отбору.

ГА имитирует три эволюционных процесса: отбор, скрещивание генов и мутацию.

Подобно естественному отбору, центральной концепцией отбора ГА является приспособленность. Более приспособленные хромосомы имеют больше шансов на выживание. Пригодность — это функция, которая измеряет качество решения, представленного хромосомой. По сути, каждая хромосома в популяции представляет входные параметры. Например, если ваша задача содержит два входных параметра, таких как цена и объем в торговле, каждая хромосома логически будет состоять из двух элементов. То, как элементы кодируются внутри хромосомы, — это отдельная тема.

В ходе отбора хромосомы образуют родительские пары для размножения . Каждый ребенок берет характеристики от своих родителей. По сути, ребенок представляет собой рекомбинацию характеристик своих родителей: некоторые характеристики берутся у одного родителя, а некоторые — у другого. Помимо рекомбинации, некоторые характеристики могут мутировать .

Поскольку более приспособленные хромосомы производят больше детей, каждое последующее поколение будет иметь лучшую приспособленность. В какой-то момент поколение будет содержать хромосому, которая будет представлять собой достаточно хорошее решение нашей проблемы.

GA является мощным и широко применимым для сложных задач. Существует большой класс задач оптимизации, которые довольно сложно решить с помощью обычных методов оптимизации. Генетические алгоритмы — это эффективные алгоритмы, решение которых приблизительно оптимально. Известные приложения включают планирование, транспортировку, маршрутизацию, групповые технологии, проектирование макетов, обучение нейронных сетей и многие другие.

Применение на практике

Пример, который мы рассмотрим, можно считать «Hello World» GA. Этот пример изначально был приведен Дж. Фриманом в Simulation Neural Networks with Mathematica . Я взял его из книги « Генетические алгоритмы и инженерный дизайн » Мицуо Гена и Рунвей Ченга.

Задача сопоставления слов пытается развить выражение с помощью генетического алгоритма. Изначально алгоритм должен «угадывать» фразу «быть или не быть» из случайно сгенерированных списков букв.

Поскольку существует 26 возможных букв для каждого из 13 мест в списке [исключая пробелы], вероятность того, что мы получим правильную фразу чисто случайным образом, составляет (1/26)^13=4,03038×10-19, что примерно два шанса из [квинтиллиона] (Gen & Chong, 1997).

Здесь мы определим проблему несколько шире, что сделает решение еще более сложным. Предположим, что мы не ограничиваемся английским языком или конкретной фразой. В конечном итоге мы можем иметь дело с любым алфавитом или даже с любым набором символов. У нас нет знания языка. Мы даже не знаем, есть ли вообще язык.

Допустим, наш оппонент придумал произвольную фразу, включающую пробелы. Мы знаем длину фразы и количество символов в алфавите. Это единственное знание, которое у нас есть. После каждого предположения наш оппонент сообщает нам, сколько букв на месте.

Каждая хромосома представляет собой последовательность индексов символов в алфавите. Если мы говорим об английском алфавите, то «а» будет представлено 0, «б» — 1, «с» — 2 и так далее. Так, например, слово «быть» будет представлено как [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); } }

Это простой набор шагов, из которых более или менее состоит каждый ГА. На этапе инициализации мы генерируем начальную популяцию фраз. Размер популяции определяется параметром 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 мы выполняем « 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% хромосом будут отобраны для кроссинговера. Проведем простую процедуру кроссинговера пары хромосом. Мы генерируем случайное число n из диапазона [0..length] , где 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, поэтому мы ожидаем, что в среднем пять процентов популяции будут мутировать. Мы мутируем, выбирая случайную позицию буквы и заменяя ее значение случайной буквой из алфавита. Мы делаем это дважды для каждой мутировавшей хромосомы.

Поставщик

 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; }

Функция завершения подсчитывает количество вызовов и возвращает true , если имеется точное совпадение или если количество генераций достигает 3000.

Исполнение

Теперь мы готовы протестировать наш алгоритм. Если вы запустите его несколько раз, вы заметите, что не все запуски будут успешными. Каждый раз количество итераций будет разным. Это связано с вероятностным характером алгоритма. Алгоритм имеет несколько точек, где его можно улучшить. Вы можете играть с вероятностями кроссовера и мутации.

Снижение числа приведет к стабильному, но медленному решению. Меньшее количество хромосом будет затронуто генетическими операторами и, следовательно, для решения потребуется больше итераций.

Увеличение числа ускорит алгоритм, но сделает решение нестабильным. Подходящие хромосомы будут не только сохранены, но и затронуты генетическими операторами. Поэтому они потеряют свои «хорошие» гены.

Важно найти хороший баланс. Увеличение количества итераций даст алгоритму больше возможностей найти решение, но, с другой стороны, это займет больше времени. Также можно применять различные методы кроссовера и мутации. Хороший выбор этих операторов значительно улучшит качество решения.

Что дальше?

Здесь мы рассмотрели только верхушку айсберга. Мы взяли пример, который имеет только один вход, и вход может быть легко представлен как хромосома. Генетические операторы просты и понятны.

Очень интересно взять реальную задачу и применить к ней генетический алгоритм. Вы откроете для себя различные подходы к кодированию реальных входных данных, а также различные реализации кроссовера и мутации.

Если проблема может быть выражена через набор параметров, которые мы должны угадать для оптимизации метрики, мы можем быстро настроить ГА, который мы можем использовать для ее решения.

Одной из самых интересных задач является обучение искусственных нейронных сетей. Мы можем установить оптимизируемые параметры как силу синапсов, а показатель пригодности — как процент входных данных, для которых наша нейронная сеть дала правильный ответ. После этого мы можем расслабиться и позволить нашей нейронной сети развиться до идеального решения, которого мы желаем. Или, по крайней мере, пока мы не получим что-то достаточно хорошее, потому что эволюция требует времени.