Вступление

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

В предыдущей статье « Введение в генетические алгоритмы в Java» мы рассмотрели терминологию и теорию, лежащую в основе всего, что вам нужно знать для успешной реализации генетического алгоритма.

Реализация генетического алгоритма

Чтобы продемонстрировать, что мы можем делать с генетическими алгоритмами, давайте решим проблему коммивояжера (TSP) на Java.

Формулировка TSP : коммивояжер должен проехать через n городов, чтобы продать свой товар. Между каждыми двумя городами есть дорога, но некоторые дороги длиннее и опаснее других. Учитывая города и стоимость проезда между каждыми двумя городами, какой самый дешевый способ для продавца посетить все города и вернуться в исходный город, не проезжая ни один город дважды?

Хотя это может показаться простым подвигом, стоит отметить, что это NP-сложная проблема. Не существует алгоритма, позволяющего решить эту проблему за полиномиальное время. Генетический алгоритм может только приблизить решение.

Поскольку решение довольно длинное, я буду разбивать его по функциям, чтобы объяснить его здесь. Если вы хотите предварительно просмотреть и / или попробовать всю реализацию, вы можете найти проект IntelliJ на GitHub .

Представление генома

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

Чтобы упростить расчет пригодности для людей и их сравнение, мы также добавим Comparable :

 public class SalesmanGenome implements Comparable { 
 // ... 
 } 

Несмотря на использование класса, то, чем по сути является наш человек, будет лишь одним из его атрибутов. Если мы подумаем о TSP, мы можем пронумеровать наши города от 0 to n-1 . Решением проблемы могло бы быть множество городов, чтобы минимизировать стоимость проезда через них в указанном порядке.

Например, 0-3-1-2-0 . Мы можем сохранить это в ArrayList потому что Collections Framework делает это действительно удобным, но вы можете использовать любую структуру, подобную массиву.

Атрибуты нашего класса следующие:

 // The list with the cities in order in which they should be visited 
 // This sequence represents the solution to the problem 
 List<Integer> genome; 
 
 // Travel prices are handy to be able to calculate fitness 
 int[][] travelPrices; 
 
 // While the starting city doesn't change the solution of the problem, 
 // it's handy to just pick one so you could rely on it being the same 
 // across genomes 
 int startingCity; 
 
 int numberOfCities; 
 
 int fitness; 

Что касается конструкторов, мы сделаем два - один, который создает случайный геном, и второй, который принимает в качестве аргумента уже созданный геном:

 // Generates a random salesman 
 public SalesmanGenome(int numberOfCities, int[][] travelPrices, int startingCity) { 
 this.travelPrices = travelPrices; 
 this.startingCity = startingCity; 
 this.numberOfCities = numberOfCities; 
 
 this.genome = randomSalesman(); 
 this.fitness = this.calculateFitness(); 
 } 
 
 // Generates a salesman with a user-defined genome 
 public SalesmanGenome(List<Integer> permutationOfCities, int numberOfCities, int[][] travelPrices, int startingCity) { 
 this.genome = permutationOfCities; 
 this.travelPrices = travelPrices; 
 this.startingCity = startingCity; 
 this.numberOfCities = numberOfCities; 
 
 this.fitness = this.calculateFitness(); 
 } 
 
 // Generates a random genome 
 // Genomes are permutations of the list of cities, except the starting city 
 // so we add them all to a list and shuffle 
 private List<Integer> randomSalesman() { 
 List<Integer> result = new ArrayList<Integer>(); 
 for (int i = 0; i < numberOfCities; i++) { 
 if (i != startingCity) 
 result.add(i); 
 } 
 Collections.shuffle(result); 
 return result; 
 } 

Фитнес-функция

Возможно, вы заметили, что мы вызвали метод calculateFitness() чтобы присвоить значение пригодности атрибуту объекта во время построения. Функция работает, следуя пути, проложенному в геноме через матрицу цен, и суммируя стоимость.

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

 public int calculateFitness() { 
 int fitness = 0; 
 int currentCity = startingCity; 
 
 // Calculating path cost 
 for (int gene : genome) { 
 fitness += travelPrices[currentCity][gene]; 
 currentCity = gene; 
 } 
 
 // We have to add going back to the starting city to complete the circle 
 // the genome is missing the starting city, and indexing starts at 0, which is why we subtract 2 
 fitness += travelPrices[genome.get(numberOfCities-2)][startingCity]; 
 
 return fitness; 
 } 

Класс генетического алгоритма

Сердце алгоритма будет находиться в другом классе, называемом TravelingSalesman . Этот класс будет выполнять нашу эволюцию, и все остальные функции будут содержаться в нем:

 private int generationSize; 
 private int genomeSize; 
 private int numberOfCities; 
 private int reproductionSize; 
 private int maxIterations; 
 private float mutationRate; 
 private int[][] travelPrices; 
 private int startingCity; 
 private int targetFitness; 
 private int tournamentSize; 
 private SelectionType selectionType; 

• Размер поколения - это количество геномов / особей в каждом поколении / популяции. Этот параметр также часто называют численностью населения.
• Размер генома - это длина ArrayList генома, которая будет равна numberOfCities-1 . Две переменные разделены для ясности в остальной части кода. Этот параметр также часто называют длиной хромосомы.
• Размер репродукции - это количество геномов, которые будут отобраны для воспроизведения, чтобы создать следующее поколение. Этот параметр также часто называют скоростью кроссовера.
• Максимальное количество итераций - это максимальное количество поколений, в которых программа будет развиваться до завершения, в случае, если до этого не будет сходимости.
• Скорость мутации относится к частоте мутаций при создании нового поколения.
• Цены на проезд - это матрица цен на проезд между каждыми двумя городами - эта матрица будет иметь нули по диагонали и симметричные значения в нижнем и верхнем треугольнике.
• Начальный город - это индекс начального города.
• Целевая пригодность - это приспособленность, которой должен достичь наилучший геном в соответствии с целевой функцией (которая в нашей реализации будет такой же, как функция приспособленности) для преждевременного завершения программы. Иногда установка целевого фитнеса может сократить программу, если нам нужно только определенное значение или лучше. Здесь, если мы хотим, чтобы наши затраты были ниже определенного числа, но не заботимся о том, насколько они низки, мы можем использовать его для установки этого порога.
• Размер турнира - это размер турнира для выбора турнира.
• Тип выбора будет определять тип выбора, который мы используем - мы реализуем как рулетку, так и турнир. Вот перечисление для SelectionType :

1

<!-- -->

 public enum SelectionType { 
 TOURNAMENT, 
 ROULETTE 
 } 

Выбор

Хотя в большинстве случаев преобладает метод выбора турнира, бывают ситуации, когда вы захотите использовать другие методы. Поскольку многие генетические алгоритмы используют одну и ту же кодовую базу (индивидуумы и фитнес-функции меняются), рекомендуется добавлять в алгоритм больше параметров.

Мы будем реализовывать как рулетку, так и отбор турниров:

 // We select reproductionSize genomes based on the method 
 // predefined in the attribute selectionType 
 public List<SalesmanGenome> selection(List<SalesmanGenome> population) { 
 List<SalesmanGenome> selected = new ArrayList<>(); 
 SalesmanGenome winner; 
 for (int i=0; i < reproductionSize; i++) { 
 if (selectionType == SelectionType.ROULETTE) { 
 selected.add(rouletteSelection(population)); 
 } 
 else if (selectionType == SelectionType.TOURNAMENT) { 
 selected.add(tournamentSelection(population)); 
 } 
 } 
 
 return selected; 
 } 
 
 public SalesmanGenome rouletteSelection(List<SalesmanGenome> population) { 
 int totalFitness = population.stream().map(SalesmanGenome::getFitness).mapToInt(Integer::intValue).sum(); 
 
 // We pick a random value - a point on our roulette wheel 
 Random random = new Random(); 
 int selectedValue = random.nextInt(totalFitness); 
 
 // Because we're doing minimization, we need to use reciprocal 
 // value so the probability of selecting a genome would be 
 // inversely proportional to its fitness - the smaller the fitness 
 // the higher the probability 
 float recValue = (float) 1/selectedValue; 
 
 // We add up values until we reach out recValue, and we pick the 
 // genome that crossed the threshold 
 float currentSum = 0; 
 for (SalesmanGenome genome : population) { 
 currentSum += (float) 1/genome.getFitness(); 
 if (currentSum >= recValue) { 
 return genome; 
 } 
 } 
 
 // In case the return didn't happen in the loop above, we just 
 // select at random 
 int selectRandom = random.nextInt(generationSize); 
 return population.get(selectRandom); 
 } 
 
 // A helper function to pick n random elements from the population 
 // so we could enter them into a tournament 
 public static <E> List<E> pickNRandomElements(List<E> list, int n) { 
 Random r = new Random(); 
 int length = list.size(); 
 
 if (length < n) return null; 
 
 for (int i = length - 1; i >= length - n; --i) { 
 Collections.swap(list, i , r.nextInt(i + 1)); 
 } 
 return list.subList(length - n, length); 
 } 
 
 // A simple implementation of the deterministic tournament - the best genome 
 // always wins 
 public SalesmanGenome tournamentSelection(List<SalesmanGenome> population) { 
 List<SalesmanGenome> selected = pickNRandomElements(population, tournamentSize); 
 return Collections.min(selected); 
 } 

Кроссовер

Кроссовер для TSP нетипичный. Поскольку каждый геном представляет собой перестановку списка городов, мы не можем просто скрестить двух родителей условно. Посмотрите на следующий пример (начальный город 0 неявно является первым и последним шагом):

2-4-3|1-6-5

4-6-5|3-1-2

Что бы произошло, если бы мы пересекли эти две точки в точке, обозначенной значком | ?

2-4-3-3-1-2

4-6-5-1-6-5

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

Так что, если мы не можем использовать обычный кроссовер, то , что мы используем?

Техника, которую мы будем использовать, называется частично отображенным кроссовером или сокращенно PMX. PMX случайным образом выбирает одну точку кроссовера, но в отличие от одноточечного кроссовера, он не просто меняет местами элементы двух родительских элементов, а вместо этого меняет местами элементы внутри них. Я считаю, что процесс наиболее понятен из иллюстрации, и мы можем использовать пример, с которым у нас раньше были проблемы:

{.ezlazyload .img-responsive}

Как видно здесь, мы меняем местами i й элемент одного из родителей на элемент, эквивалентный по значению i му элементу другого. Тем самым мы сохраняем свойства перестановок. Мы повторяем этот процесс для создания второго потомка (с исходными значениями родительских геномов):

 public List<SalesmanGenome> crossover(List<SalesmanGenome> parents) { 
 // Housekeeping 
 Random random = new Random(); 
 int breakpoint = random.nextInt(genomeSize); 
 List<SalesmanGenome> children = new ArrayList<>(); 
 
 // Copy parental genomes - we copy so we wouldn't modify in case they were 
 // chosen to participate in crossover multiple times 
 List<Integer> parent1Genome = new ArrayList<>(parents.get(0).getGenome()); 
 List<Integer> parent2Genome = new ArrayList<>(parents.get(1).getGenome()); 
 
 // Creating child 1 
 for (int i = 0; i < breakpoint; i++) { 
 int newVal; 
 newVal = parent2Genome.get(i); 
 Collections.swap(parent1Genome, parent1Genome.indexOf(newVal), i); 
 } 
 children.add(new SalesmanGenome(parent1Genome, numberOfCities, travelPrices, startingCity)); 
 parent1Genome = parents.get(0).getGenome(); // Reseting the edited parent 
 
 // Creating child 2 
 for (int i = breakpoint; i < genomeSize; i++) { 
 int newVal = parent1Genome.get(i); 
 Collections.swap(parent2Genome, parent2Genome.indexOf(newVal), i); 
 } 
 children.add(new SalesmanGenome(parent2Genome, numberOfCities, travelPrices, startingCity)); 
 
 return children; 
 } 

Мутация

Мутация довольно проста - если мы пройдем проверку вероятности, мы мутируем, поменяв местами два города в геноме. В противном случае мы просто возвращаем исходный геном:

 public SalesmanGenome mutate(SalesmanGenome salesman) { 
 Random random = new Random(); 
 float mutate = random.nextFloat(); 
 if (mutate < mutationRate) { 
 List<Integer> genome = salesman.getGenome(); 
 Collections.swap(genome, random.nextInt(genomeSize), random.nextInt(genomeSize)); 
 return new SalesmanGenome(genome, numberOfCities, travelPrices, startingCity); 
 } 
 return salesman; 
 } 

Политика замещения поколений

Мы используем алгоритм поколений, поэтому мы создаем совершенно новую популяцию детей:

 public List<SalesmanGenome> createGeneration(List<SalesmanGenome> population) { 
 List<SalesmanGenome> generation = new ArrayList<>(); 
 int currentGenerationSize = 0; 
 while (currentGenerationSize < generationSize) { 
 List<SalesmanGenome> parents = pickNRandomElements(population, 2); 
 List<SalesmanGenome> children = crossover(parents); 
 children.set(0, mutate(children.get(0))); 
 children.set(1, mutate(children.get(1))); 
 generation.addAll(children); 
 currentGenerationSize += 2; 
 } 
 return generation; 
 } 

Прекращение

Мы прекращаем действие при следующих условиях:

• количество поколений достигло maxIterations
• лучшая длина пути генома меньше, чем длина целевого пути

1

<!-- -->

 public SalesmanGenome optimize() { 
 List<SalesmanGenome> population = initialPopulation(); 
 SalesmanGenome globalBestGenome = population.get(0); 
 for (int i = 0; i < maxIterations; i++) { 
 List<SalesmanGenome> selected = selection(population); 
 population = createGeneration(selected); 
 globalBestGenome = Collections.min(population); 
 if (globalBestGenome.getFitness() < targetFitness) 
 break; 
 } 
 return globalBestGenome; 
 } 

Продолжительность

Лучший способ оценить, правильно ли работает этот алгоритм, - создать для него несколько случайных проблем и оценить время выполнения:

             время (мс)     Матрица затрат Решение        Длина пути

Первый забег 50644 0 Â 44 94 70\ 0 1 2 3 0 209 44 0 Â 32 56\
94 32 0 Â 63\
70 56 63 0

Второй прогон 50800 0 Â 3 Â 96 51\ 0 3 2 1 0 129 3 Â 0 Â 42 86\
96 42 0 Â 33\
51 86 33 0

Третий пробег 49928 0 Â 51 30 93\ 0 2 3 1 0 149 51 0 Â 83 10\
30 83 0 Â 58\
93 10 58 0

Четвертый 55359 0 Â 17 94 3\ 0 3 2 1 0 118 забег 17 0 Â 49 14\
94 49 0 Â 49\
3 Â 14 49 0

Пятый заезд 59262 0 Â 44 0 Â 96\ 0 1 3 2 0 176 44 0 Â 68 38\
0 Â 68 0 Â 94\
96 38 94 0

Шестой пробег 58236 0 Â 44 10 20\ 0 3 1 2 0 156 44 0 Â 57 69\
10 57 0 Â 44\
20 69 44 0

Седьмой забег 60500 0 Â 27 76 58\ 0 2 3 1 0 214 27 0 Â 93 28\
76 93 0 Â 83\
58 28 83 0

Восьмой пробег 56085 0 Â 63 59 21\ 0 2 1 3 0 178 63 0 Â 67 31\
59 67 0 Â 38\
21 31 38 0

Девятый забег 41062 0 Â 3 Â 67 89\ 0 2 3 1 0 110 3 Â 0 Â 41 14\
67 41 0 Â 26\
89 14 26 0

Десятый забег 37815 0 Â 58 83 62\ 0 1 3 2 0 228 58 0 Â 98 3\
83 98 0 Â 84\
62 3 Â 84 0

Наше среднее время работы составляет 51972 мс, что составляет около 52 секунд. Это когда длина ввода составляет четыре города, а это означает, что нам придется ждать дольше, чтобы получить большее количество городов. Может показаться, что это много, но реализация генетического алгоритма занимает значительно меньше времени, чем поиск идеального решения проблемы.

Хотя эту конкретную проблему можно решить другим методом, некоторые проблемы невозможно.

Например, НАСА использовало генетический алгоритм для создания оптимальной формы антенны космического корабля для получения наилучшей диаграммы направленности.

Генетические алгоритмы для оптимизации генетических алгоритмов?

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

Похожая техника используется в NeuroEvolution of Augmenting Topologies , или NEAT, где генетический алгоритм постоянно улучшает нейронную сеть и подсказывает, как изменить структуру, чтобы приспособиться к новым условиям.

Заключение

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

PS

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