Оптимизация

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

Целевая функция

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

y = 1/х X sin(x) Ее график изображен на рис. 12.18.

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

Эта функция интересна тем, что у нее несколько локальных минимумов. Это точки, в которых значение функции меньше, чем в ближайшей окрестности, но необязательно является абсолютно наименьшим.

Рис. 12.18. График функции 1/x X sin(x)

Следовательно, задачу не всегда можно решить, просто взяв произвольное решение и спускаясь по склону, потому что при таком подходе мы можем «застрять» в локальном минимуме и никогда не найти глобального.

Имитация отжига

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

Когда температура становится равна 0, алгоритм возвращает найденное к этому моменту решение.

Генетические алгоритмы

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

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

Использование ранее написанного кода

Для обоих алгоритмов необходимо знать целевую функцию и область определения решения. Областью определения называется возможный диапазон изменения каждой переменной. В нашем простом примере можно взять область определения [(0,20)], то есть единственная переменная будет изменяться от 0 до 20. Теперь можно вызвать любой метод оптимизации, передав ему в качестве параметров целевую функцию cost и область определения domain: >>> import math

>>> def costf(x): return (1.0/(x[0]+0.1))*math.sin(x[0]) >>> domain=[(0,20)]

>>> optimization.annealingoptimize(domain,costf)

[5]

Для любой задачи оптимизацию, возможно, придется провести несколько раз, чтобы подобрать параметры и добиться приемлемого компромисса между временем работы и качеством решения. При построении оптимизатора для решения схожих задач – например, планирования путешествий, когда цель остается неизменной, а меняются лишь детали (время в полете и цены), – можно один раз подобрать хорошие параметры, а затем пользоваться ими для всех похожих задач. Существует масса возможностей сочетать машинное обучение, открытые API и открытое сотрудничество. А в будущем по мере совершенствования алгоритмов, появления новых API и увеличения числа активных участников сообщества возможности будут только расширяться. Надеюсь, что, прочитав эту книгу, вы получили в свое распоряжение необходимые инструменты и загорелись желанием искать новые пути их применения!

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100