| dbo:abstract
|
- Selecció per escalada: en incrementar-se l'aptitud mitjana de la població, la força de la pressió selectiva també augmenta i la funció d'aptitud es fa més discriminatòria. Aquest mètode pot ser útil per a seleccionar més tard, quan tots els individus tinguin una aptitud relativament alta i només els distingeixin petites diferències en l'aptitud. Els mecanismes d'escalada es fan servir per a guardar nivells apropiats de competició al llarg de la simulació. Sense ells, aviat sorgeix la tendència en alguns super-individus a dominar el procés de selecció; en aquest cas, els valors de la funció objectiu s'han de reduir. Posteriorment, quan la població ha assolit nivells alts de convergència, la competència entre els membres és molt menor. Llavors, els valors de la funció objectiu cal que s'incrementin per a accentuar les diferències entre els membres de la població. Els mètodes d'escalada procedeixen dels estudis empírics de Bagley i Rosenberg, encara que més recentment, Forres (1985) va presentar una actualització d'aquests mecanismes:
* Escalada lineal.
* σ – truncament.
* Escalada potencial. L'escalada lineal treballava bé menys quan s'obtenien valors de la funció objectiu inferiors a zero. Aquest problema acostuma a sorgir quan quasi tots els membres de la població són molt aptes, però uns quants, molt letals, tenen valors excessivament baixos. Forrest va suggerir el mecanisme σ – truncament, que fa servir la desviació estàndard de la població, σ, per a calcular una certa constant a partir del valor de la funció: En aquesta equació, la constant ‘c’ s'elegeix com un múltiple de la desviació estàndard de la població i els valors negatius (f ‘ < 0) són portats a zero. Gillies va suggerir una escalada potencia on el nou valor es pren com una potència específica, tal com segueix: (ca)
- Gradientní algoritmus (Hill-climbing, horolezecký algoritmus) je nejjednodušší informovaná metoda prohledávání stavového prostoru. Vstupem algoritmu je uzel, ze kterého se má prohledávání zahájit. Nejprve je uzel expandován - jsou vygenerovány jeho sousední uzly a tyto uzly jsou ohodnoceny. Algoritmus vybere z nich nejlépe ohodnocený uzel a ten je nadále expandován. Pokračuje se jako na začátku. Algoritmus tak expanduje uzly se stále vyšším ohodnocením, dokud nenarazí na uzel, po jehož expanzi mají všechny jeho sousední uzly horší ohodnocení. V tu chvíli se algoritmus ukončí s výsledkem posledního expandovaného uzlu. Algoritmus si během svého běhu nepotřebuje udržovat informaci o navštívených uzlech. Gradientní algoritmy jsou jednoduché a rychlé, ale nemusí nalézt globálním maximum, pokud není prostor možných řešení konvexní. Při průchodu mohou zůstat v lokálním extrému, ze kterého se již nedostanou. Gradientní algoritmus je obvykle spouštěn z náhodného místa stavového prostoru. Nevýhoda uvíznutí v lokálním extrému jde částečně omezit opakovaným spouštěním tohoto algoritmu z různých míst stavového prostoru. Při každém spuštění může algoritmus uvíznout v jiném lokálním extrému a pak lze jednoduše vybrat nejvýhodnější z nich. Tímto způsobem se také zvyšuje šance na nalezení globálního maxima. Gradientní algoritmus je diskrétní analogií algoritmu gradientní sestup, který vyžaduje diferencovatelnost ztrátové funkce. (cs)
- Bergsteigeralgorithmus (engl. hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Es besteht dabei eine Analogie zu einem Bergsteiger, der im dichten Nebel den Gipfel sucht und dazu seine Schritte möglichst steil bergauf lenkt. Geht es nach allen Richtungen nur noch nach unten, ist er auf einem Gipfel angekommen. Ebenso wird im Bergsteigeralgorithmus eine potenzielle Lösung für ein gegebenes Problem Schritt für Schritt verbessert. Dabei wird jeweils eine lokale Veränderung durchgeführt und nur übernommen, wenn der entstandene Lösungskandidat besser geeignet ist. Das Verfahren endet, wenn vom aktuellen Punkt aus keine Verbesserung mehr möglich ist – analog ist der Bergsteiger auf einem Hügel angekommen. Der gefundene Punkt ist im besten Fall das globale Maximum (Bergspitze) oder nur ein lokales (Nebengipfel). Der Bergsteigeralgorithmus kann als simpler evolutionärer Algorithmus aufgefasst werden, wobei es nur ein Individuum, keine Rekombination und eine Mutations-Operation gibt. Für das Problem der lokalen Maxima gibt es folgende Ansätze:
* Eine ganze Population von Bergsteigern beginnt an verschiedenen Startpunkten, sodass verschiedene Maxima erklommen werden.
* Ein lokales Maximum wird durch eine einmalige starke Mutation verlassen, durch abermaliges Bergsteigen kann dann ein anderes Maximum gefunden werden. Eine ausführliche Implementierung eines Bergsteigeralgorithmus ist im Artikel Downhill-Simplex-Verfahren beschrieben. (de)
- In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found. For example, hill climbing can be applied to the travelling salesman problem. It is easy to find an initial solution that visits all the cities but will likely be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained. Hill climbing finds optimal solutions for convex problems – for other problems it will find only local optima (solutions that cannot be improved upon by any neighboring configurations), which are not necessarily the best possible solution (the global optimum) out of all possible solutions (the search space). Examples of algorithms that solve convex problems by hill-climbing include the simplex algorithm for linear programming and binary search. To attempt to avoid getting stuck in local optima, one could use restarts (i.e. repeated local search), or more complex schemes based on iterations (like iterated local search), or on memory (like reactive search optimization and tabu search), or on memory-less stochastic modifications (like simulated annealing). The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. It is used widely in artificial intelligence, for reaching a goal state from a starting node. Different choices for next nodes and starting nodes are used in related algorithms. Although more advanced algorithms such as simulated annealing or tabu search may give better results, in some situations hill climbing works just as well. Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems, so long as a small number of increments typically converges on a good solution (the optimal solution or a close approximation). At the other extreme, bubble sort can be viewed as a hill climbing algorithm (every adjacent element exchange decreases the number of disordered element pairs), yet this approach is far from efficient for even modest N, as the number of exchanges required grows quadratically. Hill climbing is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends. (en)
- En ciencia de la computación, el algoritmo hill climbing, también llamado algoritmo de Escalada Simple o ascenso de colinas es una técnica de optimización matemática que pertenece a la familia de los algoritmos de búsqueda local. Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, luego intenta encontrar una mejor solución variando un único elemento de la solución. Si el cambio produce una mejor solución, otro cambio incremental se le realiza a la nueva solución, repitiendo este proceso hasta que no se puedan encontrar mejoras. Suele llamarse a esta búsqueda algoritmo voraz local, porque toma un estado vecino "bueno" sin pensar en la próxima acción. El Algoritmo Hill climbing es interesante para encontrar un (una solución que no puede ser mejorada considerando una configuración de la vecindad) pero no garantiza encontrar la mejor solución posible (el ) de todas las posibles soluciones (el ).La característica de que sólo el óptimo local puede ser garantizado puede ser remediada utilizando reinicios (búsqueda local repetida), o esquemas más complejos basados en iteraciones, como , en memoria, como optimización de búsqueda reactiva y búsqueda tabú, o modificaciones estocásticas, como simulated annealing. La relativa simplicidad de este algoritmo lo hace una primera elección popular entre los algoritmos de optimización. Es usado ampliamente en inteligencia artificial, para alcanzar un estado final desde un nodo de inicio. La elección del próximo nodo y del nodo de inicio puede ser variada para obtener una lista de algoritmos de la misma familia. Aunque algoritmos más avanzados tales como simulated annealing o búsqueda tabú pueden devolver mejores resultados, en algunas situaciones hill climbing opera sin diferencias. El hill climbing con frecuencia puede producir un mejor resultado que otros algoritmos cuando la cantidad de tiempo disponible para realizar la búsqueda es limitada, por ejemplo en sistemas en tiempo real.El algoritmo puede devolver una solución válida aún si es interrumpido en cualquier momento antes de que finalice. Por ejemplo, el hill climbing puede ser aplicado al problema del viajante. Es fácil encontrar una solución inicial que visite todas las ciudades pero sería muy pobre comparada con la solución óptima. El algoritmo comienza con dicha solución y realiza pequeñas mejoras a esta, tales como intercambiar el orden en el cual dos ciudades son visitadas. Eventualmente, es probable que se obtenga una ruta más corta. (es)
- La méthode hill-climbing ou méthode d'escalade est une méthode d'optimisation permettant de trouver un optimum local parmi un ensemble de configurations. (fr)
- 山登り法（やまのぼりほう、英: hill climbing, HC）は、評価関数の極値を探索する探索アルゴリズム。最も代表的な局所探索法として知られている。最良優先探索は過去の解を管理するが、探索対象を現在の解だけに制限したものである。評価関数を使用する探索アルゴリズムとしては最も単純。 (ja)
- Алгоритм пошуку зі сходженням до вершини (англ. Hill climbing) являє собою звичайний цикл, в якому постійно відбувається переміщення в напрямку зростання деякого значення, тобто підйом. Робота цього алгоритму закінчується після досягнення «піку», в якому жоден з сусідніх станів не має більш високого значення. У цьому алгоритмі не передбачено супровід дерева пошуку, тому в структурі даних поточного вузла необхідно реєструвати тільки стан і відповідне йому значення цільової функції. В алгоритмі зі сходженням до вершини не здійснюється прогнозування за межами станів, які є безпосередньо сусідніми по відношенню до поточного стану. Це нагадує спробу альпініста, який страждає від амнезії, знайти вершину гори Еверест в густому тумані. В інформатиці алгоритм сходження на вершину — це математичний метод оптимізації, який належить до сім'ї локального пошуку. Це ітераційний алгоритм, який починається з довільного розв'язку проблеми, а потім намагається знайти краще рішення, поступово змінючи один елемент розв'язку. Наприклад, алгоритм сходження на вершину може бути застосований до задачі комівояжера. Легко знайти початкове значення, яке відвідує всі міста, але це буде дуже «бідним» в порівнянні з оптимальним рішенням. Алгоритм починається з таким рішенням і робить невеликі зміни до нього, такі, як зміна порядку відвідування двох міст. Зрештою, набагато коротший маршрут, ймовірно, буде отримано. Алгоритм сходження на вершину хороший для знаходження локального оптимуму (рішення, яке не може бути поліпшене шляхом розгляду сусідніх конфігурацій), але знаходження оптимального розв'язку (глобальний оптимум) з усіх можливих рішень (простір пошуку) не гарантується. Відносна простота алгоритму робить його популярним вибором серед алгоритмів оптимізації. Він широко використовується в галузі штучного інтелекту, для досягнення цільового стану від початкового вузла. Пов'язані алгоритми вибирають наступні та початкові вузли по-різному. Незважаючи на більш просунуті алгоритми, такі як імітація відпалу або табу-пошук, які можуть дати кращі результати, в деяких ситуаціях алгоритм сходження на вершину працює так само добре. Алгоритм сходження на вершину часто дає кращий результат, ніж інші алгоритми, коли кількість часу для виконання пошуку обмежена, наприклад, у системах реального часу. (uk)
- Поиск восхождением к вершине (далее в статье просто восхождение) — это техника математической оптимизации, принадлежащая семейству алгоритмов локального поиска. Алгоритм является методом итерации, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение путём изменения одного из элементов решения. Если решение даёт лучшее решение, делается приращение для получения нового решения и оно делается, пока не достигнем момента, в котором улучшение найти не удаётся. Например, восхождение можно использовать для решения задачи коммивояжёра. Легко найти начальное решение, в котором коммивояжёр посещает все пункты, но которое, скорее всего, будет очень плохим по сравнению с оптимальным решением. Алгоритм начинается с этого решения и делает маленькие изменения в решении, при которых меняется порядок посещения двух пунктов. В конечном счёте, скорее всего, будет найден существенно более короткий маршрут. Восхождение находит оптимальные решения в задачах выпуклого программирования, для других задач алгоритм найдёт только (решение, которое не может быть улучшено переходом в соседние узлы), которое не обязательно будет лучшим решением (глобальный оптимум) из всех возможных решений в (области допустимых решений). Примеры алгоритмов, которые решают выпуклые задачи методом поиска восхождения к вершине, включают симплекс-метод для линейного программирования и двоичный поиск. В качестве попытки преодолеть застревание в локальном оптимуме можно попробовать начать поиск заново (т.е. повторить локальный поиск) или использовать более сложные схемы, основанные на итерациях (как в ), запоминании в памяти (как в и поиске с запретами), или требующие меньшего запоминания стохастические модификации алгоритма (такие как имитация отжига). Относительная простота алгоритма делает алгоритм популярным среди оптимизационных алгоритмов. Он широко используется в теории искусственного интеллекта для достижения целевого состояния из начальной точки. Метод выбора следующей точки и начальной точки может меняться, давая ряд связанных алгоритмов. Хотя более продвинутые алгоритмы, такие как алгоритм имитации отжига или поиск с запретами могут давать результаты лучше, в некоторых ситуациях восхождение работает с тем же успехом. Восхождение часто даёт лучший результат по сравнению с другими алгоритмами, когда ограничено время на осуществление поиска, что важно в системах реального времени, при условии, что малое число шагов сходится к хорошему решению (к оптимальному, либо близкому к нему). Другой экстремальный случай, сортировка пузырьком, может рассматриваться как алгоритм восхождения (каждая перестановка соседних элементов уменьшает число неупорядоченных пар), и такой подход далёк от оптимального даже при малых N, поскольку число перестановок растёт квадратично. Восхождение является — он возвращает допустимое решение, даже если прерывается в любой момент времени. (ru)
- 爬山算法是一种的方法，采用启發式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 1.
* 局部最大 2.
* 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3.
* 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。 解决方法：随机重启爬山算法 (zh)
|
| rdfs:comment
|
- La méthode hill-climbing ou méthode d'escalade est une méthode d'optimisation permettant de trouver un optimum local parmi un ensemble de configurations. (fr)
- 山登り法（やまのぼりほう、英: hill climbing, HC）は、評価関数の極値を探索する探索アルゴリズム。最も代表的な局所探索法として知られている。最良優先探索は過去の解を管理するが、探索対象を現在の解だけに制限したものである。評価関数を使用する探索アルゴリズムとしては最も単純。 (ja)
- 爬山算法是一种的方法，采用启發式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 1.
* 局部最大 2.
* 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3.
* 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。 解决方法：随机重启爬山算法 (zh)
- Selecció per escalada: en incrementar-se l'aptitud mitjana de la població, la força de la pressió selectiva també augmenta i la funció d'aptitud es fa més discriminatòria. Aquest mètode pot ser útil per a seleccionar més tard, quan tots els individus tinguin una aptitud relativament alta i només els distingeixin petites diferències en l'aptitud. Els mètodes d'escalada procedeixen dels estudis empírics de Bagley i Rosenberg, encara que més recentment, Forres (1985) va presentar una actualització d'aquests mecanismes:
* Escalada lineal.
* σ – truncament.
* Escalada potencial. (ca)
- Gradientní algoritmus (Hill-climbing, horolezecký algoritmus) je nejjednodušší informovaná metoda prohledávání stavového prostoru. Vstupem algoritmu je uzel, ze kterého se má prohledávání zahájit. Nejprve je uzel expandován - jsou vygenerovány jeho sousední uzly a tyto uzly jsou ohodnoceny. Algoritmus vybere z nich nejlépe ohodnocený uzel a ten je nadále expandován. Pokračuje se jako na začátku. Algoritmus tak expanduje uzly se stále vyšším ohodnocením, dokud nenarazí na uzel, po jehož expanzi mají všechny jeho sousední uzly horší ohodnocení. V tu chvíli se algoritmus ukončí s výsledkem posledního expandovaného uzlu. Algoritmus si během svého běhu nepotřebuje udržovat informaci o navštívených uzlech. (cs)
- Bergsteigeralgorithmus (engl. hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Es besteht dabei eine Analogie zu einem Bergsteiger, der im dichten Nebel den Gipfel sucht und dazu seine Schritte möglichst steil bergauf lenkt. Geht es nach allen Richtungen nur noch nach unten, ist er auf einem Gipfel angekommen. Für das Problem der lokalen Maxima gibt es folgende Ansätze: Eine ausführliche Implementierung eines Bergsteigeralgorithmus ist im Artikel Downhill-Simplex-Verfahren beschrieben. (de)
- In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found. Hill climbing is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends. (en)
- En ciencia de la computación, el algoritmo hill climbing, también llamado algoritmo de Escalada Simple o ascenso de colinas es una técnica de optimización matemática que pertenece a la familia de los algoritmos de búsqueda local. Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, luego intenta encontrar una mejor solución variando un único elemento de la solución. Si el cambio produce una mejor solución, otro cambio incremental se le realiza a la nueva solución, repitiendo este proceso hasta que no se puedan encontrar mejoras. Suele llamarse a esta búsqueda algoritmo voraz local, porque toma un estado vecino "bueno" sin pensar en la próxima acción. (es)
- Поиск восхождением к вершине (далее в статье просто восхождение) — это техника математической оптимизации, принадлежащая семейству алгоритмов локального поиска. Алгоритм является методом итерации, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение путём изменения одного из элементов решения. Если решение даёт лучшее решение, делается приращение для получения нового решения и оно делается, пока не достигнем момента, в котором улучшение найти не удаётся. Восхождение является — он возвращает допустимое решение, даже если прерывается в любой момент времени. (ru)
- Алгоритм пошуку зі сходженням до вершини (англ. Hill climbing) являє собою звичайний цикл, в якому постійно відбувається переміщення в напрямку зростання деякого значення, тобто підйом. Робота цього алгоритму закінчується після досягнення «піку», в якому жоден з сусідніх станів не має більш високого значення. У цьому алгоритмі не передбачено супровід дерева пошуку, тому в структурі даних поточного вузла необхідно реєструвати тільки стан і відповідне йому значення цільової функції. (uk)
|
