|
|
| (не показано 6 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| '''Поиск восхождением к вершине''' (далее в статье просто восхождение) — это техника [[Оптимизация (математика)|математической оптимизации]], принадлежащая семейству алгоритмов [[Локальный поиск (оптимизация)|локального поиска]]. Алгоритм является [[Метод итерации|методом итерации]], который начинается с произвольного решения задачи, а затем пытается найти лучшее решение путём {{не переведено 5|Пошаговый эвристический поиск|пошагового||incremental heuristic search}} изменения одного из элементов решения. Если решение даёт лучшее решение, делается приращение для получения нового решения и оно делается, пока не достигнем момента, в котором улучшение найти не удаётся.
| | {{HowTo |
| | | |Description_of_problem=Поиск восхождением к вершине - алгоритм поиска в компьютерных науках, когда агент просматривает значения переменных на ближайших полях и на поле с максимальным значением переменной. Использование алгоритма поиск восхождением к вершине можно наблюдать в таких играх как Sims или Pac-Man, когда призраки преследуют Pacman, следуя наивысшему значению запаха Pac-man, который распространяется по всему полю см. http://ccl.northwestern.edu/netlogo/models/Pac-Man |
| Например, восхождение можно использовать для решения [[Задача коммивояжёра|задачи коммивояжёра]]. Легко найти начальное решение, в котором коммивояжёр посещает все пункты, но которое, скорее всего, будет очень плохим по сравнению с оптимальным решением. Алгоритм начинается с этого решения и делает маленькие изменения в решении, при которых меняется порядок посещения двух пунктов. В конечном счёте, скорее всего, будет найден существенно более короткий маршрут.
| | |Environment=Pac-Man, NetLogo |
| | | |Solution=Использовать встроенные команды NetLogo |
| Восхождение находит оптимальные решения в задачах [[Выпуклое программирование|выпуклого программирования]], для других задач алгоритм найдёт только {{не переведено 5|локальный оптимум|||local optimum}} (решение, которое не может быть улучшено переходом в соседние узлы), которое не обязательно будет лучшим решением ([[Экстремум|глобальный оптимум]]) из всех возможных решений в ([[Область допустимых решений|области допустимых решений]]). Примеры алгоритмов, которые решают выпуклые задачи методом поиска восхождения к вершине, включают [[симплекс-метод]] для [[Линейное программирование|линейного программирования]] и [[двоичный поиск]]{{sfn|Skiena|2010|с=253}}. В качестве попытки преодолеть застревание в локальном оптимуме можно попробовать начать поиск заново (т.е. повторить локальный поиск) или использовать более сложные схемы, основанные на итерациях (как в {{не переведено 5|Итеративный локальный поиск|итеративном локальном поиске||iterated local search}}), запоминании в памяти (как в {{не переведено 5|Пассивный поиск|пассивном поиске||like reactive search optimization}} и [[Поиск с запретами|поиске с запретами]]), или требующие меньшего запоминания стохастические модификации алгоритма (такие как [[Алгоритм имитации отжига|имитация отжига]]).
| | * uphill patch-variable |
| | | * uphill4 patch-variable |
| Относительная простота алгоритма делает алгоритм популярным среди оптимизационных алгоритмов. Он широко используется в теории [[Искусственный интеллект|искусственного интеллекта]] для достижения целевого состояния из начальной точки. Метод выбора следующей точки и начальной точки может меняться, давая ряд связанных алгоритмов. Хотя более продвинутые алгоритмы, такие как [[алгоритм имитации отжига]] или [[поиск с запретами]] могут давать результаты лучше, в некоторых ситуациях восхождение работает с тем же успехом. Восхождение часто даёт лучший результат по сравнению с другими алгоритмами, когда ограничено время на осуществление поиска, что важно в системах реального времени, при условии, что малое число шагов сходится к хорошему решению (к оптимальному, либо близкому к нему). Другой экстремальный случай, [[сортировка пузырьком]], может рассматриваться как алгоритм восхождения (каждая перестановка соседних элементов уменьшает число неупорядоченных пар), и такой подход далёк от оптимального даже при малых N, поскольку число перестановок растёт квадратично.
| | |Code=to move |
| | | uphill elevation |
| Восхождение является {{не переведено 5|Алгоритм с отсечением по времени|алгоритмом с отсечением по времени ||anytime algorithm}} — он возвращает допустимое решение, даже если прерывается в любой момент времени.
| | end |
| | | |url_example=http://ccl.northwestern.edu/netlogo/models/Ants |
| == Математическое описание ==
| | |KeyConcepts=Паттерн вычислительного мышления |
| | | |FieldActivity=Computational Thinker |
| Восхождение пытается максимизировать (или минимизировать) целевую [[Функция (математика)|функцию]] <math>f(\mathbf{x})</math>, где <math>\mathbf{x}</math> — вектор непрерывных и/или дискретных значений. На каждой итерации восхождение подправляет один элемент в <math>\mathbf{x}</math> и определяет, внесённые исправления улучшают значение <math>f(\mathbf{x})</math> или нет. (Заметим, что это отличается от методов [[Градиентный спуск|градиентного спуска]], которые исправляют все элементы вектора <math>\mathbf{x}</math> на каждой итерации согласно градиенту подъёма.) При восхождении принимается любое изменение, улучшающее <math>f(\mathbf{x})</math>, и процесс продолжается, пока не достигнем точки, в которой нельзя найти улучшение значения <math>f(\mathbf{x})</math>. Тогда говорят, что <math>\mathbf{x}</math> является «локальным оптимумом».
| | }} |
| | | === [[NetLogo]] === |
| В дискретных векторных пространствах каждое возможное значение <math>\mathbf{x}</math> можно представить как [[Вершина (теория графов)|вершину]] в [[Граф (математика)|графе]]. Восхождение проходит по графу от вершины к вершине, всегда локально увеличивая (или уменьшая) значение функции <math>f(\mathbf{x})</math>, пока не будет достигнут [[Экстремум|локальный максимум]] (или [[Экстремум|локальный минимум]]) <math>x_m</math>.
| |
| | |
| [[Файл:hill climb.png|thumb|260px|''Поверхность с одним максимумом. Восхождение к вершине хорошо подходит для оптимизации путём поиска по таким поверхностям и сходится к глобальному максимуму.'']]
| |
| | |
| == Варианты ==
| |
| | |
| При '''простом восхождении''' выбирается первый узел в направлении вершины, в то время как при '''наискорейшем восхождении''' сравниваются все наследники и выбирается узел, наиболее близкий к вершине. Обе формы завершаются неуспехом, если нет узла для подъёма, что может случиться, если имеется локальный максимум, не являющийся решением. Наискорейшее восхождение подобно [[Поиск по первому наилучшему совпадению|поиску по первому наилучшему совпадению]], который перебирает все возможные расширения текущего пути, а не только один вариант.
| |
| | |
| '''{{не переведено 5|Случайный поиск восхождением к вершине|||Stochastic hill climbing}}''' не проверяет все соседние узлы перед выбором движения. Вместо этого соседний узел выбирается случайным образом и принимается решение (основываясь на улучшении, даваемом этим соседом), двигаться ли к этому узлу или проверить другой узел.
| |
| | |
| [[Покоординатный спуск]] осуществляет [[линейный поиск]] вдоль одной координаты из текущей точки на каждой итерации. Некоторые варианты покоординатного спуска выбирают координатное направление случайно на каждой итерации.
| |
| | |
| '''Случайное возобновление восхождения''' — это [[метаалгоритм]], построенный на основе алгоритма восхождения. Он известен также как '''Shotgun Hill climbing''' (Пулемётное восхождение). Алгоритм итеративно осуществляет восхождение, каждый раз выбирая случайное начальное <math>x_0</math>. Лучшее значение <math>x_m</math> сохраняется и, если новая попытка восхождения даёт лучший <math>x_m</math> по сравнению с запомненным, он заменяет запомненное состояние.
| |
| | |
| Случайное возобновление восхождения во многих случаях является на удивление эффективным алгоритмом. Оказывается, что часто эффективнее тратить ресурсы ЦПУ на исследование пространства, вместо того чтобы тщательно оптимизировать из исходного состояния.
| |
| | |
| == Задачи == | |
| | |
| === Локальные максимумы ===
| |
| [[Файл:local maximum.png|thumb|260px|''Поверхность с двумя локальными максимумами. (Только один из них является глобальным максимумом.) Если восхождение начинается в неудачной точке, оно может привести в меньшему максимуму.'']]
| |
| | |
| Восхождение не обязательно отыщет глобальный максимум, оно может привести к [[Экстремум|локальному максимуму]]. Эта проблема не возникает, если функция выпукла. Однако, поскольку не все функции выпуклы, восхождение может не найти глобальный максимум. Другие алгоритмы локального поиска пытаются преодолеть эту проблему, такие как {{не переведено 5|случайный поиск восхождением к вершине|||stochastic hill climbing}}, [[Случайное блуждание|случайные блуждания]] и [[алгоритм имитации отжига]].
| |
| | |
| [[Файл:Hill Climbing with Simulated Annealing.gif|thumb|left|500px|Несмотря на то, что имеется много локальных максимумов на этом графе, глобальный максимум может быть найден с помощью '''имитации отжига'''. К сожалению, применимость алгоритмов имитации отжига сильно зависит от задачи, поскольку опирается на нахождение ''удачных прыжков'', которые улучшают позицию.]]
| |
| {{clear}}
| |
| | |
| === Хребты и ущелья === | |
| | |
| [[Файл:ridge.png|thumb|190px|''Хребет'']] | |
| | |
| Хребты являются сложной проблемой для восхождения при оптимизации в непрерывном пространстве. Поскольку восхождение изменяет только один элемент вектора в один момент времени, каждый шаг переходит только в направлении числовых осей. Если целевая функция образует узкий хребет, который возрастает в направлении, отличном от координатных осей (в случае минимизации функция образует узкое ущелье, убывающее в направлении, отличном от осей координат), тогда восхождение может подниматься по хребту (или спускаться по ущелью) зигзагом. Если стороны хребта (или ущелья) очень крутые, восхождение может быть вынуждено идти очень мелкими зигзагообразными шагами, что может вызвать неоправданно долгое время восхождения вдоль хребта (или спуска по ущелью).
| |
| | |
| Методы же градиентного спуска могут двигаться в направлении, в котором поднимается хребет или спускается ущелье. Следовательно, градиентный спуск или [[Метод сопряжённых градиентов (для решения СЛАУ)|метод сопряжённых градиентов]] будет более предпочтительным, если целевая функция дифференцируема. Восхождение, однако, имеет преимущество отсутствия требования к дифференцируемости, так что восхождение может оказаться более предпочтительным, когда целевая функция сложная.
| |
| | |
| === Плато ===
| |
| Другая проблема, иногда возникающая при восхождении — плато. Плато встречается, когда поверхность достаточно плоская, так что значения целевой функции неотличимы от значений близлежащих узлов ввиду ограниченности точности вычислений машиной. В таких случаях алгоритм восхождения не может выбрать направление движения и может пойти в направлении, которое не ведёт к улучшению целевой функции.
| |
|
| |
|
| == Псевдокод ==
| |
|
| |
|
| <pre> | | <syntaxhighlight lang="Logos" line> |
| Алгоритм восхождения в дискретном пространстве
| | to go |
| currentNode = startNode;
| | ;; Остановиться, если все черепахи в наивысшей точке |
| loop do
| | if all? turtles [peak?] |
| L = NEIGHBORS(currentNode);
| | [ stop ] |
| nextEval = -INF;
| | ask turtles [ |
| nextNode = NULL;
| | ;; remember where we started |
| for all x in L
| | let old-patch patch-here |
| if (EVAL(x) > nextEval)
| | ;; to use UPHILL, the turtles specify a patch variable |
| nextNode = x;
| | uphill pcolor |
| nextEval = EVAL(x);
| | ;; are we still where we started? if so, we didn't |
| if nextEval <= EVAL(currentNode)
| | ;; move, so we must be on a peak |
| //Возвращаем текущий узел, поскольку лучшего узла нет
| | if old-patch = patch-here [ set peak? true ] |
| return currentNode;
| | ] |
| currentNode = nextNode;
| | tick |
| </pre>
| | end |
|
| |
|
| <pre> | | </syntaxhighlight> |
| Алгоритм восхождения в непрерывном пространстве
| |
| currentPoint = initialPoint; // обычно используется вектор нулевой длины
| |
| stepSize = initialStepSizes; // обычно используется вектор из единиц
| |
| acceleration = someAcceleration; // обычно используется значение 1.2
| |
| candidate[0] = -acceleration;
| |
| candidate[1] = -1 / acceleration;
| |
| candidate[2] = 0;
| |
| candidate[3] = 1 / acceleration;
| |
| candidate[4] = acceleration;
| |
| loop do
| |
| before = EVAL(currentPoint);
| |
| for each element i in currentPoint do
| |
| best = -1;
| |
| bestScore = -INF;
| |
| for j from 0 to 4 // пытаемся перебрать каждый из 5 кандидатов
| |
| currentPoint[i] = currentPoint[i] + stepSize[i] * candidate[j];
| |
| temp = EVAL(currentPoint);
| |
| currentPoint[i] = currentPoint[i] - stepSize[i] * candidate[j];
| |
| if(temp > bestScore)
| |
| bestScore = temp;
| |
| best = j;
| |
| if candidate[best] is 0
| |
| stepSize[i] = stepSize[i] / acceleration;
| |
| else
| |
| currentPoint[i] = currentPoint[i] + stepSize[i] * candidate[best];
| |
| stepSize[i] = stepSize[i] * candidate[best]; // accelerate
| |
| if (EVAL(currentPoint) - before) < epsilon
| |
| return currentPoint;
| |
| </pre>
| |
|
| |
|
| == См. также ==
| |
| * [[Градиентный спуск]]
| |
| * [[Жадный алгоритм]]
| |
| * {{не переведено 5|Вальрасовский аукцион|Невидимая рука||Walrasian auction}}
| |
| * {{не переведено 5|Сдвиг среднего|||Mean-shift}}
| |
|
| |
|
| == Примечания ==
| | {{#widget:iframe |
| {{примечания|2}} | | |url=https://netlogoweb.org/launch#https://netlogoweb.org/assets/modelslib/Code%20Examples/Hill%20Climbing%20Example.nlogo |
| | | |width=1000 |
| == Литература ==
| | |height=1000 |
| {{refbegin|colwidth=30em}}
| |
| * {{книга
| |
| |ref=Russell, Norvig
| |
| |автор=Stuart J. Russell, Peter Norvig
| |
| |год=2003
| |
| |заглавие=Artifical Intelligence: A Modern Approach
| |
| |место=Upper Saddle River, New Jercey
| |
| |издательство=Prentice Hall | |
| |страницы=111–114 | |
| }} | | }} |
| * {{книга
| |
| |ref=Skiena
| |
| |автор=Steven Skiena
| |
| |заглавие=The Algorithm Design Manual
| |
| |издательство=[[Springer Science+Business Media]]
| |
| |издание=2nd
| |
| |год = 2010
| |
| |isbn=1-849-96720-2
| |
| }}
| |
| {{refend}}
| |
|
| |
| Статья базируется на материале, взятом из статьи [[Free On-line Dictionary of Computing|Free On-line Dictionary of Computing (FOLDOC)]], имеющей лицензию [[GNU FDL|GFDL (версия 1.3)]].
| |
|
| |
| == Ссылки ==
| |
| {{Алгоритмы поиска на графах}}
| |
|
| |
|
| {{Методы оптимизации}}
| |
|
| |
|
| [[Категория:Алгоритмы поиска]]
| | В моделях NetLogo примеры поиска восхождением к вершине |
| [[Категория:Метаэвристика]]
| | * https://ccl.northwestern.edu/netlogo/models/HillClimbingExample |
| {{rq|checktranslate|style}}
| | * https://ccl.northwestern.edu/netlogo/models/HillClimbingExample3D |
| | * описание алгоритма - http://www.cs.us.es/~fsancho/?e=132 |
