Генетический алгоритм — это процедура, которая ищет наилучшее решение проблемы, используя операции, имитирующие естественные процессы, участвующие в эволюции, такие как «выживание наиболее приспособленных», хромосомный кроссинговер и мутация. В этой статье дается краткое введение в написание генетических алгоритмов, обсуждаются некоторые важные аспекты написания собственного алгоритма и представлено несколько примеров генетических алгоритмов в действии.
Угадывание неизвестного
На дворе 2369 год, и человечество рассеялось по звездам. Вы молодой, умный врач, работающий на звездной базе в глубоком космосе, который кишит межзвездными путешественниками, торговцами и случайными бездельниками. Практически сразу после вашего приезда вами заинтересовался один из продавцов станции. Он утверждает, что он не более чем простой портной, но ходят слухи, что он тайный агент, работающий на особенно неприятный режим.
Вы двое начинаете вместе наслаждаться еженедельными обедами и обсуждать все, от политики до поэзии. Даже по прошествии нескольких месяцев вы все еще не уверены, делает ли он романтические жесты или выискивает секреты (не то чтобы вы их знали). Возможно, это и то, и другое.
Однажды за обедом он бросает вам вызов: «У меня есть для вас сообщение, дорогой доктор! Я, конечно, не могу сказать, что это такое. Но я скажу вам, что это 12 символов. Эти символы могут быть любой буквой алфавита, пробелом или знаком препинания. И я скажу вам, насколько далеки ваши догадки. Вы умны; как ты думаешь, ты сможешь это понять?»
Вы возвращаетесь в свой кабинет в медицинском отсеке, все еще думая о том, что он сказал. Внезапно симуляция секвенирования генов, которую вы оставили работающей на соседнем компьютере в рамках эксперимента, натолкнула вас на идею. Вы не взломщик кодов, но, возможно, вы сможете использовать свои знания в области генетики, чтобы понять его послание!
Немного теории
Как я упоминал в начале, генетический алгоритм — это процедура, которая ищет решение, используя операции, имитирующие процессы, управляющие эволюцией. В течение многих итераций алгоритм выбирает лучших кандидатов (предположений) из набора возможных решений, повторно комбинирует их и проверяет, какие комбинации приблизили его к решению. Менее выгодные кандидаты отбрасываются.
В приведенном выше сценарии любой символ в секретном сообщении может быть A–Z, пробелом или обычным знаком препинания. Допустим, это дает нам следующий
Предположим, мы делаем три предположения: HOMLK? WSRZDJ, BGK KA! QTPXC, и XELPOCV.XLF!. Первый кандидат получает 248,2 балла, второй — 632,5, а третий — 219,5. Как рассчитывается оценка, зависит от ситуации, которую мы обсудим позже, но сейчас давайте предположим, что она основана на отклонении между кандидатом и целевым сообщением: идеальная оценка равна 0 (то есть отклонений нет; кандидат и цели одинаковы), а больший балл означает большее отклонение. Предположения, набравшие 248,2 и 219,5 баллов, ближе к тому, чем может быть секретное сообщение, чем предположение, набравшее 635,5 баллов.
Будущие догадки делаются путем объединения лучших попыток. Есть много способов комбинировать кандидатов, но сейчас мы рассмотрим простой метод пересечения: каждый символ в новом предположении имеет шанс 50–50 быть скопированным с первого или второго родительского кандидата. Если мы возьмем два предположения HOMLK? WSRZDJи XELPOCV.XLF!, первый символ нашего
Генерация новых кандидатов через кроссовер
Генерация новых кандидатов через кроссовер
Однако при нескольких итерациях может возникнуть проблема, если мы используем значения только от родительских кандидатов: отсутствие разнообразия. Если у нас есть один кандидат, состоящий из всех A’, а другой из всех B’, то любое потомство, порожденное ими исключительно путем скрещивания, будет состоять только из A’ и B’. Нам не повезло, если решение содержит файл C.
Чтобы снизить этот риск и сохранить разнообразие, не теряя при этом решения, мы можем внести небольшие изменения. Вместо прямого разделения 50 на 50 мы даем небольшой шанс, что вместо этого будет выбрано произвольное значение из алфавита. С этой мутацией потомство может стать HELLO WORLD!.
Мутация сохраняет свежесть вещей!
Мутация сохраняет свежесть вещей!
Неудивительно, что генетические алгоритмы заимствуют много слов из генетической науки. Итак, прежде чем мы пойдем дальше, давайте уточним нашу терминологию:
Аллель: член генетического алфавита. То, как определяются аллели, зависит от алгоритма. Например, 0и 1могут быть аллелями для генетического алгоритма, работающего с двоичными данными, алгоритм, работающий с кодом, может использовать указатели на функции и т. д. В нашем сценарии секретного сообщения аллелями были буквы алфавита, пробелы и различные знаки препинания.
Хромосома: заданная последовательность аллелей; вариант решения; догадка». В нашем сценарии, HOMLK? WSRZDJ, XELPOCV.XLF! и HELLO WORLD! все хромосомы.
Ген: аллель в определенном месте хромосомы. Для хромосомы HOMLK? WSRZDJпервый ген равен H, второй ген равен O, третий равен M, и так далее.
Популяция: совокупность одной или нескольких
Генерация: популяция во время конкретной итерации алгоритма. Кандидаты в одном поколении предоставляют гены для производства популяции следующего поколения.
Пригодность: мера, которая оценивает близость кандидата к желаемому решению. Более подходящие хромосомы с большей вероятностью передадут свои гены будущим кандидатам, в то время как менее подходящие хромосомы с большей вероятностью будут отброшены.
Отбор: процесс выбора одних кандидатов для воспроизведения (используется для создания новых
Размножение: процесс объединения генов одного или нескольких кандидатов для получения новых кандидатов. Донорские хромосомы называются родителями, а полученные хромосомы называются потомками.
Мутация: случайное введение аберрантных генов в потомство для предотвращения потери генетического разнообразия в течение многих поколений.
Покажи мне код!
Я подозреваю, что, учитывая общий обзор и список терминологии, вам, вероятно, не терпится увидеть код. Итак, давайте посмотрим на JavaScript, который решает нашу проблему с секретным сообщением. Пока вы читаете, я предлагаю вам подумать о том, какие методы можно считать «шаблонным кодом» и реализации каких методов более тесно связаны с проблемой, которую мы пытаемся решить:
class Candidate {
constructor (chromosome, fitness) {
this.chromosome = chromosome;
this.fitness = fitness;
}
/**
* Convenience method to sort an array of Candidate
* objects.
*/
static sort (candidates, asc) {
candidates.sort ((a, b) => (asc)
? (a.fitness — b.fitness)
: (b.fitness — a.fitness)
) ;
}
}
class GeneticAlgorithm {
constructor (params) {
this.alphabet = params.alphabet;
this.target = params.target;
this.chromosomeLength = params.target.length;
this.populationSize = params.populationSize;
this.selectionSize = params.selectionSize;
this.mutationRate = params.mutationRate;
this.mutateGeneCount = params.mutateGeneCount;
this.maxGenerations = params.maxGenerations;
}
/**
* Convenience method to return a random integer [
*/
randomInt (max) {
return Math.floor (Math.random () * max) ;
}
/**
* Create a new chromosome from random alleles.
*/
createChromosome () {
const chrom = [];
for (let i = 0; i < this.chromosomeLength; i++) {
chrom.push (this.alphabet[
this.randomInt (this.alphabet.length)
]) ;
}
return chrom;
}
/**
* Create the initial population with random chromosomes
* and assign each a fitness score for later evaluation.
*/
init () {
this.generation = 0;
this.population = [];
for (let i = 0; i < this.populationSize; i++) {
const chrom = this.createChromosome () ;
const score = this.calcFitness (chrom) ;
this.population.push (new Candidate (chrom, score));
}
}
/**
* Measure a chromosome’s fitness based on how close its
* genes match those of the target; uses mean squared
* error.
*/
calcFitness (chrom) {
let error = 0;
for (let i = 0; i < chrom.length; i++) {
error += Math.pow (
this.target[i].charCodeAt () — chrom[i].charCodeAt (),
2
) ;
}
return error / chrom.length;
}
/**
* Reduce the population to only the fittest candidates;
* elitist selection strategy.
*/
select () {
// lower MSE is better
Candidate.sort (this.population, true) ;
this.population.splice (this.selectionSize) ;
}
/**
* Apply crossover and mutation to create new offspring
* chromosomes and increase the population.
*/
reproduce () {
const offspring = [];
const numOffspring = this.populationSize /
this.population.length * 2;
for (let i = 0; i < this.population.length; i += 2) {
for (let j = 0; j < numOffspring; j++) {
let chrom = this.crossover (
this.population[i].chromosome,
this.population[i + 1].chromosome,
) ;
chrom = this.mutate (chrom) ;
const score = this.calcFitness (chrom) ;
offspring.push (new Candidate (chrom, score));
}
}
this.population = offspring;
}
/**
* Create a new chromosome through uniform crossover.
*/
crossover (chromA, chromB) {
const chromosome = [];
for (let i = 0; i < this.chromosomeLength; i++) {
chromosome.push (
this.randomInt (2)? chromA[i]: chromB[i]
) ;
}
return chromosome;
}
/**
* (Possibly) introduce mutations to a chromosome.
*/
mutate (chrom) {
if (this.mutationRate < this.randomInt (1000) / 1000) {
return chrom;
}
for (let i = 0; i < this.mutateGeneCount; i++) {
chrom[this.randomInt (this.chromosomeLength) ] =
this.alphabet[
this.randomInt (this.alphabet.length)
];
}
return chrom;
}
/**
* Return whether execution should continue processing
* the next generation or should stop.
*/
stop () {
if (this.generation > this.maxGenerations) {
return true;
}
for (let i = 0; i < this.population.length; i++) {
if (this.population[i].fitness == 0) {
return true;
}
}
return false;
}
/**
* Repeatedly perform genetic operations on the
* population of candidate chromosomes in an attempt to
* converge on the fittest solution.
*/
evolve () {
this.init () ;
do {
this.generation++;
this.select () ;
this.reproduce () ;
} while (! this.stop ());
return {
generation: this.generation,
population: this.population
};
}
}
const result = new GeneticAlgorithm ({
alphabet: Array.from ('ABCDEFGHIJKLMNOPQRSTUVWXYZ!'),
target: Array.from ('HELLO WORLD!'),
populationSize: 100,
selectionSize: 40,
mutationRate: 0.03,
mutateGeneCount: 2,
maxGenerations: 1000000
}).evolve () ;
console.log ('Generation’, result.generation) ;
Candidate.sort (result.population, true) ;
console.log ('Fittest candidate’, result.population[0]) ;
Мы начнем с определения Candidateобъекта данных, чтобы просто соединить хромосомы с их оценкой пригодности. Для удобства к нему также прикреплен метод статической сортировки; это удобно, когда нам нужно найти или вывести наиболее подходящие хромосомы.
Далее у нас есть GeneticAlgorithmкласс, реализующий сам генетический алгоритм.
Конструктор берет объект с различными параметрами, необходимыми для моделирования. Он предоставляет способ указать генетический алфавит, целевое сообщение и другие параметры, которые служат для определения ограничений, при которых будет выполняться симуляция. В приведенном выше примере мы ожидаем, что в каждом поколении будет 100 кандидатов. Из них для размножения будут отобраны только 40 хромосом. Мы допускаем 3% шанс введения мутации, и мы мутируем до двух генов, когда это произойдет. Значение maxGenerationsслужит защитой; если мы не придем к решению после миллиона поколений, мы все равно прервем сценарий.
Стоит отметить, что популяция, размер выборки и максимальное количество поколений, предоставляемых при запуске алгоритма, довольно малы. Для более сложных задач может потребоваться большее пространство для поиска, что, в свою очередь, увеличивает использование памяти алгоритмом и время, необходимое для его выполнения. Однако настоятельно рекомендуется использовать небольшие параметры мутации. Если они становятся слишком большими, мы теряем все преимущества воспроизведения кандидатов на основе пригодности, и симуляция начинает превращаться в случайный поиск.
Такие методы, как randomInt (), init () и, run () вероятно, можно считать шаблонными. Но то, что есть шаблон, не означает, что он не может иметь реального значения для симуляции. Например, генетические алгоритмы активно используют случайность. Хотя встроенная Math.random () функция подходит для наших целей, вам потребуется более точный генератор случайных чисел для решения других задач. Crypto.getRandomValues () предоставляет более криптографически стойкие случайные значения.
Производительность также является соображением. Я стремлюсь к удобочитаемости этой статьи, но имейте в виду, что операции будут повторяться снова и снова. Вам может понадобиться микрооптимизировать код внутри циклов, использовать структуры данных с более эффективным использованием памяти и встроенный код, а не разделять его на функции/методы, независимо от языка реализации.
Реализация таких методов, как calcFitness (), select (), reproduce (), и даже stop () зависит от проблемы, которую мы пытаемся решить.
calcFitness () возвращает значение, измеряющее соответствие хромосомы некоторым желаемым критериям — в нашем случае, насколько близко она соответствует секретному сообщению. Расчет пригодности почти всегда зависит от ситуации; наша реализация вычисляет среднеквадратичную ошибку, используя значения ASCII для каждого гена, но другие показатели могут подойти лучше. Например, я мог бы рассчитать расстояние Хэмминга или Левенштейна между двумя значениями или даже включить несколько измерений. В конечном счете, для
Этот select () метод демонстрирует элитарную стратегию отбора — отбор только самых подходящих кандидатов из всего населения для воспроизводства. Как я упоминал ранее, существуют и другие стратегии, такие как турнирный отбор, который отбирает наиболее подходящих кандидатов из множества отдельных кандидатов в популяции, и отбор Больцмана, который оказывает все большее давление при выборе кандидатов. Цель этих различных подходов состоит в том, чтобы гарантировать, что хромосомы имеют возможность передавать гены, которые могут оказаться полезными позже, даже если это может быть неочевидно сразу. Подробные описания этих и других стратегий выбора, а также примеры реализации можно легко найти в Интернете.
Проиллюстрированы различные стратегии отбора
Проиллюстрированы различные стратегии отбора
Существует также много подходов к комбинированию генов. Наш код создает потомство с помощью равномерного кроссовера, в котором каждый ген имеет равные шансы быть выбранным от одного из родителей. Другие стратегии могут отдавать предпочтение генам одного родителя по сравнению с генами другого. Другой популярной стратегией является кроссовер по k точкам, при котором хромосомы расщепляются в k точках, в результате чего получается k + 1 срезов, которые объединяются для получения потомства. Точки пересечения могут быть фиксированными или выбраны случайным образом.
проиллюстрированы стратегии пересечения
проиллюстрированы стратегии пересечения
Мы также не ограничены двумя родительскими хромосомами; мы объединяем гены трех или более кандидатов или даже строим одного кандидата. Рассмотрим алгоритм, написанный для эволюции изображения путем рисования случайных многоугольников. В этом случае наши хромосомы реализованы в виде данных изображения. Во время каждого поколения наиболее подходящее изображение выбирается из популяции и служит родительским, а все дочерние кандидаты генерируются путем рисования своих собственных полигонов на копии родительского. Родительская хромосома/изображение служит основой, а дочерние хромосомы/изображения являются уникальными мутациями/рисунками на родительской.
Генетические алгоритмы в действии
Генетические алгоритмы можно использовать как для развлечения, так и для прибыли. Возможно, двумя наиболее популярными примерами генетических алгоритмов в действии являются BoxCar 2D и разработанные НАСА антенны
BoxCar 2D — это симуляция, в которой используются генетические алгоритмы для создания наилучшего «автомобиля», способного перемещаться по смоделированной местности. Автомобиль строится из восьми случайных векторов, образующих многоугольник и прикрепляющих колеса к случайным точкам.
Автомобиль, эволюционировавший в BoxCar 2D, изображение из таблицы лидеров BoxCar 2D.
Автомобиль, эволюционировавший в BoxCar 2D, изображение из таблицы лидеров BoxCar 2D.
В 2006 году в рамках миссии НАСА «Космические технологии 5» были протестированы различные новые технологии в космосе. Одной из таких технологий были новые антенны, разработанные с использованием генетических алгоритмов. Разработка новой антенны может быть очень дорогим и трудоемким процессом. Это требует особого опыта, и частые неудачи случаются, когда требования меняются или прототипы не работают должным образом. Для создания усовершенствованных антенн требовалось меньше времени, они имели более высокий коэффициент усиления и потребляли меньше энергии. Полный текст статьи, в которой обсуждается процесс проектирования, находится в свободном доступе в Интернете (Automated Antenna Design with Evolutionary Algorithms). Генетические алгоритмы также использовались для оптимизации существующих конструкций антенн для повышения производительности.
Лучшие современные антенны для своего класса требований, изображение взято из документа Automated Antenna Design.
Лучшие современные антенны для своего класса требований, изображение взято из документа Automated Antenna Design.
Генетические алгоритмы использовались даже в
Лучшие макеты поколений 1 и 9, изображения взяты из статьи Optimizing Website Design.
Лучшие макеты поколений 1 и 9, изображения взяты из статьи Optimizing Website Design.
Вывод
К настоящему времени вы должны иметь базовое представление о том, что такое генетические алгоритмы, и быть достаточно знакомым с их словарем, чтобы расшифровать любые ресурсы, с которыми вы можете столкнуться в своих собственных исследованиях. Но понимание теории и терминологии — это только полдела. Если вы планируете написать свой собственный генетический алгоритм, вы также должны понимать свою конкретную проблему. Вот несколько важных вопросов, которые следует задать себе перед началом работы:
Как я могу представить свою проблему в виде хромосом? Каковы мои действительные аллели?
Я знаю, что такое цель? То есть что я ищу? Это конкретное значение или любое решение, пригодность которого превышает определенный порог?
Как я могу количественно оценить пригодность моих кандидатов?
Как я могу комбинировать и видоизменять варианты для создания новых
Надеюсь, я также помог вам понять, как программы могут черпать вдохновение из природы — не только в форме, но также в процессе и функциях.
