Строго говоря, эти две вещи - имитация отжига (SA) и генетические алгоритмы не являются ни алгоритмами, ни их предназначением для "извлечения данных".
Оба являются метаэвристиками - на пару уровней выше «алгоритма» в масштабе абстракции. Другими словами, оба термина относятся к метафорам высокого уровня - один заимствован из металлургии, а другой - из эволюционной биологии. В метаэвристической таксономии SA - это метод с одним состоянием , а GA - популяционный метод (в подклассе наряду с PSO, ACO и др., Обычно называемыми как биологически вдохновленная метаэвристика ).
Эти две метаэвристики используются для решения задач оптимизации, особенно (хотя и не исключительно) в комбинаторной оптимизации (она же программирование удовлетворения ограничений ). Комбинаторная оптимизация относится к оптимизации путем выбора из набора отдельных элементов - иными словами, нет непрерывной функции для минимизации. Проблема ранца, задача коммивояжера, проблема распиловки - все это проблемы комбинаторной оптимизации.
Связь с интеллектуальным анализом данных заключается в том, что ядром многих (более?) Контролируемых алгоритмов машинного обучения (ML) является решение задачи оптимизации - (например, многоуровневой персептрон и машины опорных векторов).
Любой метод решения для решения задач ограничения, независимо от алгоритма, будет состоять в основном из этих шагов (которые обычно кодируются как один блок в рекурсивном цикле):
кодировать специфичные для домена детали
в функции стоимости (это
поэтапная минимизация стоимости
вернулся из этой функции, которая
представляет собой «решение» с / о
проблема);
оценка прохождения функции стоимости
в первоначальном «предположение» (для начала
итерация);
на основе значения, возвращенного из
функция стоимости, генерировать последующее
вариант решения (или более
один, в зависимости от
метаэвристический) к стоимости
функция;
оцените каждое возможное решение по
передавая его в наборе аргументов, чтобы
функция стоимости;
повторять шаги (iii) и (iv) до
либо некоторый критерий сходимости
удовлетворен или максимальное количество
итерации достигнуты.
Метаэвристика направлена на шаг (iii) выше; следовательно, SA и GA отличаются тем, как они генерируют подходящие решения для оценки по функции стоимости. Другими словами, это место, где нужно посмотреть, чтобы понять, как эти две метаэвристики отличаются.
Неформально, сущность алгоритма, направленного на решение комбинаторной оптимизации, заключается в том, как он обрабатывает решение-кандидат, значение которого возвращается из функции стоимости на хуже , чем текущее лучшее решение-кандидат (тот, который возвращает наименьшее значение из функции стоимости). Самый простой способ для алгоритма оптимизации обрабатывать такое подходящее решение - это полностью отклонить его - это то, что делает алгоритм подъема по холмам. Но при этом простое восхождение на холм всегда будет пропускать лучшее решение, отделенное от текущего решения холмом. Иными словами, сложный алгоритм оптимизации должен включать в себя метод (временно) принятия возможного решения хуже (то есть, в гору) текущего лучшего решения, потому что даже лучшее решение, чем текущее, может лежать на пути через это худшее решение.
Так как же SA и GA генерируют подходящие решения?
Суть SA обычно выражается в терминах вероятности того, что более подходящее решение-кандидат будет принято (все выражение в двойных скобках является показателем степени:
p = e((-highCost - lowCost)/temperature)
Или в питоне:
p = pow(math.e, (-hiCost - loCost) / T)
Термин «температура» - это переменная, значение которой уменьшается в процессе оптимизации, и, следовательно, вероятность того, что SA примет худшее решение, уменьшается с увеличением числа итераций.
Иными словами, когдаалгоритм начинает итерацию, T очень велико, что, как вы можете видеть, заставляет алгоритм переходить к каждому вновь созданному решению-кандидату, лучше или хуже, чем текущее наилучшее решение - т. е. выполняется случайное блуждание в пространстве решений.По мере увеличения числа итераций (т. Е. По мере того, как температура охлаждается), поиск алгоритмом пространства решений становится менее разрешительным, пока при T = 0 поведение не будет идентично простому алгоритму восхождения на холм (т. Е. Только решения лучше, чем текущий лучшийрешение принято).
Генетические алгоритмы очень разные.С одной стороны - и это большая вещь - он генерирует не единственное решение для кандидата, а целую «совокупность из них».Это работает так: GA вызывает функцию стоимости для каждого члена (вариант решения) населения.Затем он ранжирует их от лучшего к худшему, упорядочив их по значению, возвращенному функцией стоимости («лучшее» имеет наименьшее значение).Из этих ранжированных значений (и соответствующих им вариантов решения) создается следующая совокупность.Новые члены населения создаются по существу одним из трех способов.Первый обычно называется «элитарностью» и на практике обычно подразумевает просто принятие наиболее подходящих решений-кандидатов и передачу их напрямую - без изменений - следующему поколению.Два других способа, которыми новые члены населения обычно называют «мутация» и «кроссовер».Мутация обычно включает в себя изменение одного элемента в векторе решения-кандидата из текущей совокупности для создания вектора решения в новой совокупности, например, [4, 5, 1, 0, 2] => [4, 5, 2, 0, 2].Результат операции кроссовера аналогичен тому, что произошло бы, если бы векторы могли иметь половые контакты, т. Е. Новый дочерний вектор, элементы которого состоят из некоторых от каждого из двух родителей.
Таковы алгоритмические различия между GAи SA.Как насчет различий в производительности?
На практике: (мои наблюдения ограничиваются проблемами комбинаторной оптимизации) GA почти всегда превосходит SA (возвращает более низкое «лучшее» возвращаемое значение из функции стоимости - то есть значениеблизко к глобальному минимуму пространства решений), но с более высокой стоимостью вычислений.Насколько мне известно, в учебниках и технических публикациях приводится одно и то же заключение о разрешении.
, но вот в чем дело: GA по своей природе распараллеливаем;Более того, это тривиально, потому что отдельным «поисковым агентам», входящим в каждую группу, не нужно обмениваться сообщениями, т. е. они работают независимо друг от друга.Очевидно, что это означает, что GA вычисление может быть распределено , что означает на практике, вы можете получить гораздо лучшие результаты (ближе к глобальному минимуму) и лучшую производительность (скорость выполнения).
При каких обстоятельствах SA может превзойти GA?Я думаю, что общий сценарий - это те проблемы оптимизации, которые имеют малое пространство для решения, так что результат от SA и GA практически одинаков, но контекст выполнения (например, сотни похожих задач, запущенных в пакетном режиме) предпочитает более быстрый алгоритм (которыйвсегда должно быть SA).