Понимание концепции генетического алгоритма

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

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

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

Концепция ГА была заимствована из естественной генетической эволюции и тем самым еще раз доказывает то, что

«Природа всегда была великим источником вдохновения для всего человечества».

- lakhasly.com

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

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

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

• Правила отбора выбирают людей, называемых родителями, которые вносят вклад в популяцию в следующем поколении.

• Правила кроссовера объединяют двух родителей, чтобы сформировать детей для следующего поколения.

• Правила мутации применяют случайные изменения к отдельным родителям для формирования детей. [1]

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

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

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

Несколько важных терминов

Пространство поиска:

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

Оценка фитнеса:

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

Операции:

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

Кроссовер: это операция, при которой происходит фактическое (аналогичное) спаривание между людьми. Сайты кроссовера или места в хромосоме выбираются в этой операции, и две выбранные хромосомы из операции отбора берутся для кроссовера. Фактический кроссовер происходит, когда выбранные гены берутся и объединяются для получения нового потомства (имеющего ту же длину, что и у родителей). Обратите внимание, что все точки кроссовера выбираются случайным образом. Следующий пример прояснит это.

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

Преимущества и недостатки генетического алгоритма

Есть много преимуществ генетических алгоритмов перед традиционными алгоритмами оптимизации. Двумя наиболее примечательными из них являются способность решать сложные проблемы и параллелизм. Генетические алгоритмы могут иметь дело с различными типами оптимизации, независимо от того, является ли целевая функция (приспособленность) стационарной или нестационарной (изменяется со временем), линейной или нелинейной, непрерывной или прерывистой, или со случайным шумом. Потому что множественное потомство в популяции, действующей как независимые агенты, популяция (или любая подгруппа) может исследовать пространство поиска одновременно во многих направлениях. Эта функция делает идеальным распараллеливание алгоритмов для реализации. Одновременно можно управлять разными параметрами и даже разными группами закодированных строк. [2]

Однако у генетических алгоритмов есть и недостатки. Формулировка функции приспособленности, использование размера популяции, выбор важных параметров, таких как скорость мутации и кроссовера, а также критерии отбора новой популяции должны выполняться с особой тщательностью. Любой неправильный выбор затруднит сходимость алгоритма или просто даст бессмысленные результаты. Несмотря на эти недостатки, генетические алгоритмы остаются одними из наиболее широко используемых алгоритмов оптимизации в современной нелинейной оптимизации. [2]

Дополнительные преимущества:

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

К недостаткам можно отнести:

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

Псевдокод

Вот набросок типичного ГА в псевдокоде:

GA()
begin
  Create initial population;
  while (Until Stopping Criteria)
    for (Each Chromosome)
      Calculate fitness value;
      Selection (Survival of strong individuals);
      Crossover (Here, new generation produced);
      Mutation (Changing some genes for new and
                different individuals);
    end
  Generate new population;
  end
end

Можем ли мы теперь погрузиться в код?

Ниже приводится простой пример программы на Python, в которой реализован генетический алгоритм. Код был взят из GeeksforGeeks, и поэтому я никоим образом не претендую на право собственности на следующий код. Я постараюсь объяснить код шаг за шагом.

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

Здесь начинается определение класса Individual, которое определяет двухчленные переменные хромосому и пригодность и инициализирует их.

mutated_genes () - это функция, в которой происходит мутация генов. Здесь случайный ген берется из пула генов и возвращается в основную программу.

create_gnome () создает отдельные гномы или хромосомы целевой длины и возвращается к основной функции.

mate () - очень важная функция, так как именно здесь создаются новые хромосомы с лучшей приспособленностью. Здесь происходят две операции: кроссовер и мутация. На самом деле это модифицированный или специальный генетический алгоритм, в котором операции основаны на случайной вероятности. Если вероятность меньше 0,45, тогда ген из родительской хромосомы 1 передается в дочернюю хромосому, тогда как если вероятность равна больше или равно 0,45 и меньше 0,90, то соответствующий ген из родительской хромосомы 2 передается в дочернюю хромосому и если вероятность больше или равна 0,90, то мутировавший ген передается в дочернюю хромосому и, наконец, возвращается новая хромосома.

cal_fitness () вычисляет оценку пригодности конкретной хромосомы и возвращает ее, чтобы генетический алгоритм мог принимать соответствующие решения. Эта конкретная функция проверяет, достигнута ли целевая строка или нет, и, соответственно, создает оценку соответствия на основе количества символов, которые еще не соответствуют целевому требованию.

Это основная функция алгоритма, в которой все предыдущие функции вызываются для выполнения своей индивидуальной работы. Сначала создается начальная популяция. Затем популяция сортируется в соответствии с ее оценкой пригодности, помещая хромосомы с лучшими оценками в начало. Теперь он проверяет, имеет ли первый (лучший показатель пригодности) показатель пригодности меньше или равный 0, затем он должен вернуть строку, так как это целевая строка и алгоритм. останавливается. В противном случае он выполняет элитарность, добавляя 10% наиболее приспособленного населения к популяции следующего поколения и, кроме того, 50% старшего населения идет на спаривание, чтобы произвести детей. Теперь с новым поколением снова работают с самого начала, пройдя все вышеперечисленные этапы. В конечном итоге мы видим, что после значительного времени выполнения алгоритм останавливается и выдает целевую строку.

Это результат, который я получил:

PS C:\Users\RAJARSI> & python c:/Users/RAJARSI/Desktop/GA.py
Generation: 1   String: i a2yl [TXl Xn[:rZnL    Fitness: 18
Generation: 2   String: U[vW 5 mL&TgW rdLeVY    Fitness: 17
Generation: 3   String: 4g9W/5 mO&["W rGLefY    Fitness: 16
Generation: 4   String: 4gCa/5 G];[4Wo;G3e}Y    Fitness: 15
Generation: 5   String: 4gCa/5 G];[4Wo;G3e}Y    Fitness: 15
Generation: 6   String: F 1! e GeWk@/bal#tk2    Fitness: 13
Generation: 7   String: F 9! e Ge k@#OtG#e}9    Fitness: 12
Generation: 8   String: F 9! e Ge k@#OtG#e}9    Fitness: 12
Generation: 9   String: { C0Xh GeePv=orG3ePY    Fitness: 11
Generation: 10  String: 5y6/;e Gee3nWorG3ekY    Fitness: 10
Generation: 11  String: 5y6/;e Gee3nWorG3ekY    Fitness: 10
Generation: 12  String: I 1WPe GeekD=oZG_e}Y    Fitness: 9
Generation: 13  String: I 1WPe GeekD=oZG_e}Y    Fitness: 9
Generation: 14  String: I 1WPe GeekD=oZG_e}Y    Fitness: 9
Generation: 15  String: I ( W  GeeknaorG3ekY    Fitness: 8
Generation: 16  String: I ( W  GeeknaorG3ekY    Fitness: 8
Generation: 17  String: I }!pe Geek"QorGPekY    Fitness: 7
Generation: 18  String: I }!pe Geek"QorGPekY    Fitness: 7
Generation: 19  String: I }!pe Geek"QorGPekY    Fitness: 7
Generation: 20  String: F Oo&e Geekn5orGeekY    Fitness: 6
Generation: 21  String: F Oo&e Geekn5orGeekY    Fitness: 6
Generation: 22  String: F Oo&e Geekn5orGeekY    Fitness: 6
Generation: 23  String: F Oo&e Geekn5orGeekY    Fitness: 6
Generation: 24  String: I loOe Geev"5orGeekY    Fitness: 5
Generation: 25  String: I loOe Geev"5orGeekY    Fitness: 5
Generation: 26  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 27  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 28  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 29  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 30  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 31  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 32  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 33  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 34  String: I goOe GeekJYorGeeks    Fitness: 4
Generation: 35  String: I lo e GeekJQorGeeks    Fitness: 3
Generation: 36  String: I lo e GeekJQorGeeks    Fitness: 3
Generation: 37  String: I love Geek"farGeeks    Fitness: 2
Generation: 38  String: I love Geek"farGeeks    Fitness: 2
Generation: 39  String: I love Geek"farGeeks    Fitness: 2
Generation: 40  String: I love Geek"farGeeks    Fitness: 2
Generation: 41  String: I love Geek"farGeeks    Fitness: 2
Generation: 42  String: I love Geek"farGeeks    Fitness: 2
Generation: 43  String: I love Geek"farGeeks    Fitness: 2
Generation: 44  String: I love Geek"farGeeks    Fitness: 2
Generation: 45  String: I love Geek"farGeeks    Fitness: 2
Generation: 46  String: I love Geek"farGeeks    Fitness: 2
Generation: 47  String: I love GeekEforGeeks    Fitness: 1
Generation: 48  String: I love GeekEforGeeks    Fitness: 1
Generation: 49  String: I love GeekEforGeeks    Fitness: 1
Generation: 50  String: I love GeekEforGeeks    Fitness: 1
Generation: 51  String: I love GeekEforGeeks    Fitness: 1
Generation: 52  String: I love GeekEforGeeks    Fitness: 1
Generation: 53  String: I love GeekEforGeeks    Fitness: 1
Generation: 54  String: I love GeekEforGeeks    Fitness: 1
Generation: 55  String: I love GeekEforGeeks    Fitness: 1
Generation: 56  String: I love GeekEforGeeks    Fitness: 1
Generation: 57  String: I love GeekEforGeeks    Fitness: 1
Generation: 58  String: I love GeekEforGeeks    Fitness: 1
Generation: 59  String: I love GeekEforGeeks    Fitness: 1
Generation: 60  String: I love GeekEforGeeks    Fitness: 1
Generation: 61  String: I love GeekEforGeeks    Fitness: 1
Generation: 62  String: I love GeekEforGeeks    Fitness: 1
Generation: 63  String: I love GeekEforGeeks    Fitness: 1
Generation: 64  String: I love GeeksforGeeks    Fitness: 0
PS C:\Users\RAJARSI>

Если вы получили другой результат, не беспокойтесь, никакие два вывода генетического алгоритма никогда не совпадают, так как весь процесс работает на случайности. Если ваш код запускается дольше, не о чем беспокоиться. Следующий пробег может быть быстрее. Но в конечном итоге алгоритм должен заканчиваться строкой «Я люблю GeeksforGeeks»

Приложения

• Байесовский вывод связан с методами частиц в байесовской статистике и моделях скрытых цепей Маркова.

• Распределенные топологии компьютерных сетей.

• Конструкция электронных схем, известная как эволюционируемое оборудование.

• Изучение поведения роботов с помощью генетических алгоритмов.

• Обработка изображений: плотное совпадение пикселей.

• Изучение базы нечетких правил с использованием генетических алгоритмов

• Равновесное разрешение теории игр

• И многое другое… [3]

Вывод

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

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