Генетический алгоритм (GA) — это поисковая оптимизация, основанная на принципах генетики и естественного отбора . Он часто используется для поиска оптимальных или почти оптимальных решений сложных проблем, которые в противном случае потребовались бы для решения целой жизни. Он часто используется для решения задач оптимизации, в исследованиях и в машинном обучении.
Введение в оптимизацию
Оптимизация — это процесс создания чего-то лучшего . В любом процессе у нас есть набор входов и набор выходов, как показано на следующем рисунке.
Оптимизация относится к нахождению значений входных данных таким образом, что мы получаем «наилучшие» выходные значения. Определение «наилучшего» варьируется от проблемы к проблеме, но в математических терминах оно относится к максимизации или минимизации одной или нескольких целевых функций путем изменения входных параметров.
Множество всех возможных решений или значений, которые могут принимать входные данные, составляют пространство поиска. В этом пространстве поиска лежит точка или набор точек, которые дают оптимальное решение. Цель оптимизации — найти эту точку или набор точек в пространстве поиска.
Что такое генетические алгоритмы?
Природа всегда была источником вдохновения для всего человечества. Генетические алгоритмы (GA) — это алгоритмы поиска, основанные на понятиях естественного отбора и генетики. GA — это подмножество гораздо большей ветви вычислений, известной как эволюционные вычисления .
GA были разработаны Джоном Холландом и его студентами и коллегами из Мичиганского университета, прежде всего Дэвидом Э. Голдбергом, и с тех пор пробовали решать различные задачи оптимизации с высокой степенью успеха.
В ГА у нас есть пул или совокупность возможных решений данной проблемы. Эти решения затем подвергаются рекомбинации и мутации (как в естественной генетике), порождая новых детей, и процесс повторяется на протяжении разных поколений. Каждому индивидууму (или подходящему решению) присваивается значение пригодности (в зависимости от значения его целевой функции), и более подходящие индивидуумы получают более высокий шанс на спаривание и получают больше «более подходящих» индивидуумов. Это соответствует дарвиновской теории выживания наиболее приспособленных.
Таким образом, мы продолжаем «развивать» лучших людей или решения из поколения в поколение, пока не достигнем критерия остановки.
Генетические алгоритмы по своей природе достаточно рандомизированы, но они выполняют намного лучше, чем случайный локальный поиск (в котором мы просто пробуем различные случайные решения, отслеживая лучшие на данный момент), поскольку они также используют историческую информацию.
Преимущества ГА
У GA есть различные преимущества, которые сделали их чрезвычайно популярными. К ним относятся —
-
Не требует никакой производной информации (которая может быть недоступна для многих реальных проблем).
-
Это быстрее и эффективнее по сравнению с традиционными методами.
-
Имеет очень хорошие параллельные возможности.
-
Оптимизирует как непрерывные, так и дискретные функции, а также многоцелевые задачи.
-
Предоставляет список «хороших» решений, а не просто одно решение.
-
Всегда получает ответ на проблему, которая со временем становится лучше.
-
Полезно, когда пространство поиска очень велико и задействовано большое количество параметров.
Не требует никакой производной информации (которая может быть недоступна для многих реальных проблем).
Это быстрее и эффективнее по сравнению с традиционными методами.
Имеет очень хорошие параллельные возможности.
Оптимизирует как непрерывные, так и дискретные функции, а также многоцелевые задачи.
Предоставляет список «хороших» решений, а не просто одно решение.
Всегда получает ответ на проблему, которая со временем становится лучше.
Полезно, когда пространство поиска очень велико и задействовано большое количество параметров.
Ограничения ГА
Как и любая техника, ГА также страдают от нескольких ограничений. К ним относятся —
-
GA не подходят для всех проблем, особенно для задач, которые просты и для которых доступна производная информация.
-
Значение пригодности рассчитывается многократно, что может быть вычислительно дорогостоящим для некоторых задач.
-
Будучи стохастическим, нет никаких гарантий относительно оптимальности или качества решения.
-
Если не реализовано должным образом, GA может не сходиться к оптимальному решению.
GA не подходят для всех проблем, особенно для задач, которые просты и для которых доступна производная информация.
Значение пригодности рассчитывается многократно, что может быть вычислительно дорогостоящим для некоторых задач.
Будучи стохастическим, нет никаких гарантий относительно оптимальности или качества решения.
Если не реализовано должным образом, GA может не сходиться к оптимальному решению.
GA — Мотивация
Генетические алгоритмы обладают способностью предоставлять «достаточно хорошее» решение «достаточно быстро». Это делает генетические алгоритмы привлекательными для использования при решении задач оптимизации. Причины, по которым нужны ГА, следующие:
Решение сложных проблем
В информатике существует большой набор проблем, которые NP-Hard . По сути это означает, что даже самым мощным вычислительным системам требуется очень много времени (даже лет!) Для решения этой проблемы. В таком сценарии ГА оказываются эффективным инструментом для предоставления практически оптимальных решений за короткое время.
Отказ градиентных методов
Традиционные методы, основанные на исчислении, работают, начиная со случайной точки и двигаясь в направлении градиента, пока мы не достигнем вершины холма. Этот метод эффективен и очень хорошо работает для однопиковых целевых функций, таких как функция стоимости в линейной регрессии. Но в большинстве реальных ситуаций у нас есть очень сложная проблема, называемая ландшафтами, которые состоят из множества вершин и долин, что приводит к сбою таких методов, поскольку они страдают от присущей им тенденции застревания в локальных оптимальных условиях. как показано на следующем рисунке.
Быстрое получение хорошего решения
У некоторых сложных проблем, таких как Задача коммивояжера (TSP), есть реальные приложения, такие как поиск пути и VLSI Design. Теперь представьте, что вы используете свою систему GPS-навигации, и для расчета «оптимального» пути от источника до пункта назначения требуется несколько минут (или даже нескольких часов). Задержка в таких реальных приложениях неприемлема, и поэтому требуется «достаточно хорошее» решение, которое доставляется «быстро».