Генетические алгоритмы - Введение
Генетический алгоритм (ГА) - это метод поисковой оптимизации, основанный на принципах Genetics and Natural Selection. Он часто используется для поиска оптимальных или почти оптимальных решений сложных проблем, решение которых в противном случае заняло бы всю жизнь. Он часто используется для решения задач оптимизации, в исследованиях и в машинном обучении.
Введение в оптимизацию
Оптимизация - это процесс making something better. В любом процессе у нас есть набор входов и набор выходов, как показано на следующем рисунке.
Оптимизация относится к поиску значений входных данных таким образом, чтобы мы получали «лучшие» выходные значения. Определение «наилучшего» варьируется от проблемы к проблеме, но с математической точки зрения оно означает максимизацию или минимизацию одной или нескольких целевых функций путем изменения входных параметров.
Набор всех возможных решений или значений, которые могут принимать входные данные, составляет пространство поиска. В этом пространстве поиска находится точка или набор точек, которые дают оптимальное решение. Цель оптимизации - найти эту точку или набор точек в пространстве поиска.
Что такое генетические алгоритмы?
Природа всегда была великим источником вдохновения для всего человечества. Генетические алгоритмы (ГА) - это поисковые алгоритмы, основанные на концепциях естественного отбора и генетики. ГА - это подмножество гораздо более крупной ветви вычислений, известной какEvolutionary Computation.
ГА были разработаны Джоном Холландом и его студентами и коллегами из Мичиганского университета, в первую очередь Дэвидом Э. Голдбергом, и с тех пор с большим успехом опробовали различные задачи оптимизации.
В ГА у нас есть pool or a population of possible solutionsк данной проблеме. Затем эти решения подвергаются рекомбинации и мутации (как в естественной генетике), производя новых детей, и этот процесс повторяется в разных поколениях. Каждому индивиду (или возможному решению) присваивается значение приспособленности (на основе его значения целевой функции), и более приспособленные особи получают более высокий шанс спариться и дать более «приспособленных» особей. Это соответствует дарвиновской теории «выживания сильнейшего».
Таким образом, мы продолжаем «развивать» лучших людей или решения из поколения в поколение, пока не достигнем критерия остановки.
Генетические алгоритмы достаточно рандомизированы по своей природе, но они работают намного лучше, чем случайный локальный поиск (в котором мы просто пробуем различные случайные решения, отслеживая лучшие на данный момент), поскольку они также используют историческую информацию.
Преимущества ГА
ГА имеют различные преимущества, которые сделали их чрезвычайно популярными. К ним относятся -
Не требует какой-либо производной информации (которая может быть недоступна для многих реальных проблем).
Работает быстрее и эффективнее по сравнению с традиционными методами.
Имеет очень хорошие параллельные возможности.
Оптимизирует как непрерывные, так и дискретные функции, а также многокритериальные задачи.
Предоставляет список «хороших» решений, а не просто одно решение.
Всегда получает ответ на проблему, который со временем становится лучше.
Полезно, когда пространство поиска очень велико и задействовано большое количество параметров.
Ограничения ГА
Как и любой метод, ГА также страдает некоторыми ограничениями. К ним относятся -
ГА не подходят для всех проблем, особенно для простых задач, по которым доступна производная информация.
Значение пригодности вычисляется многократно, что для некоторых задач может потребовать больших вычислительных ресурсов.
Поскольку решение является стохастическим, нет никаких гарантий оптимальности или качества решения.
При неправильной реализации ГА может не прийти к оптимальному решению.
GA - Мотивация
Генетические алгоритмы обладают способностью предоставлять «достаточно хорошее» решение «достаточно быстро». Это делает генетические алгоритмы привлекательными для использования при решении задач оптимизации. Причины, по которым необходимы ГА, следующие:
Решение сложных проблем
В информатике существует большой набор проблем, которые NP-Hard. По сути, это означает, что даже самым мощным вычислительным системам требуется очень много времени (даже годы!) Для решения этой проблемы. В таком сценарии ГА оказываются эффективным инструментом для обеспеченияusable near-optimal solutions в короткие сроки.
Неудача градиентных методов
Традиционные методы, основанные на исчислении, работают, начиная со случайной точки и двигаясь в направлении градиента, пока мы не достигнем вершины холма. Этот метод эффективен и очень хорошо работает для однопиковых целевых функций, таких как функция стоимости в линейной регрессии. Но в большинстве реальных ситуаций у нас есть очень сложная проблема, называемая ландшафтами, которые состоят из множества пиков и долин, что приводит к сбою таких методов, поскольку они страдают от присущей им тенденции застревать на локальных оптимумах как показано на следующем рисунке.
Быстрое получение хорошего решения
Некоторые сложные задачи, такие как задача коммивояжера (TSP), имеют реальные приложения, такие как поиск пути и проектирование СБИС. Теперь представьте, что вы используете свою систему GPS-навигации, и вам потребуется несколько минут (или даже несколько часов), чтобы вычислить «оптимальный» путь от источника до места назначения. Задержка в таких реальных приложениях неприемлема, и поэтому требуется «достаточно хорошее» решение, которое доставляется «быстро».