ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo hill climbing wiki: info, historia y vídeos

videos internet

salud  Algoritmo hill climbing 


En ciencia de la computación, el algoritmo hill climbing, asimismo llamado Algoritmo de Escalada Simple o bien Ascenso de colinas es una técnica de optimización matemática que pertenece a la familia de los algoritmos de busca local. Es un algoritmo iterativo que empieza con una solución arbitraria a un inconveniente, entonces procura localizar una mejor solución cambiando incrementalmente un solo elemento de la solución. Si el cambio genera una mejor solución, otro cambio incremental se le efectúa a la nueva solución, repitiendo este proceso hasta el momento en que no se puedan hallar mejoras. Acostumbra a llamarse a esta busca algoritmo insaciable local, por el hecho de que toma un estado vecino "bueno" sin meditar en la próxima acción.


El Algoritmo Hill climbing es interesante para hallar un perfecto local (una solución que no puede ser mejorada considerando una configuración de la vecindad) mas no garantiza hallar la mejor solución posible (el inmejorable global) de todas y cada una de las posibles soluciones (el espacio de busca). La característica de que solo el inmejorable local puede ser garantizado puede ser remediada usando reinicios (busca local repetida), o bien esquemas más complejos basados en iteraciones, como busca local iterada, en memoria, como optimización de busca reactiva y busca tabú, o bien 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 utilizado extensamente en inteligencia artificial, para lograr un estado final desde un nodo de comienzo. La elección del próximo nodo y del nodo de comienzo puede ser variada para conseguir una lista de algoritmos de exactamente la misma familia. Si bien algoritmos más avanzados como simulated annealing o bien busca tabú pueden devolver mejores resultados, en ciertas situaciones hill climbing opera sin diferencias. El hill climbing habitualmente puede generar un mejor resultado que otros algoritmos cuando la cantidad de tiempo libre para efectuar la busca es limitada, por poner un ejemplo en sistemas en tiempo real. El algoritmo puede devolver una solución válida todavía si es interrumpido en cualquier instante antes que concluya.


Por ejemplo, el hill climbing puede ser aplicado al inconveniente del viajante. Es simple hallar una solución inicial que visite todas y cada una de las urbes mas sería muy pobre equiparada con la solución inmejorable. El algoritmo empieza con dicha solución y efectúa pequeñas mejoras a esta, como intercambiar el orden en el que 2 urbes son visitadas. Ocasionalmente, probablemente se consiga una senda más corta.


El hill climbing procura aumentar al máximo (o bien disminuir al mínimo) una función objetivo f(x), donde x es un vector de valores reservados y/o continuos. En todos y cada iteración, el hill climbing ajustará un solo elemento en x y determinará si el cambio mejora el valor de f(x). (Note que esto difiere de los métodos de descenso de gradiente, los que ajustan todos y cada uno de los valores en x en todos y cada iteración conforme al gradiente de la colina.) Con hill climbing, cualquier cambio que mejore f(x) es admitido, y el proceso sigue hasta el momento en que no pueda encontrarse un cambio que mejore el valor de f(x). x se afirma entonces que es "perfecta de forma local".


En los espacios de vectores prudentes, cada valor posible para x puede ser visualizado como un vértice en un grafo. El hill climbing proseguirá el grafo de vértice en vértice, siempre y en toda circunstancia acrecentando (o bien reduciendo) de forma local el valor de f(x), hasta lograr un máximo local (o bien un mínimo local) xm.

Una superficie convexa. Los algoritmos de hill climbing (hill-climbers) son apropiados para optimar sobre tales superficies, y van a confluir a el máximo global.

En el hill climbing simple, el primer nodo próximo es elegido, al paso que en hill climbing de ascenso pronunciado todos y cada uno de los sucesores son equiparados y la solución más próxima es escogida. Las dos formas fallan si no hay un nodo próximo, lo que sucede si hay máximos locales en el espacio de busca que no son soluciones. El hill climbing de ascenso pronunciado es afín a la busca en anchura, la que procura todas y cada una de las posibles extensiones del camino actual en lugar de solo una.


Hill climbing estocástico no examina todos y cada uno de los vecinos ya antes de decidir de qué forma moverse. En lugar de eso, escoge un vecino azaroso, y decide (basado en la cantidad de progreso en ese vecino) si moverse a él o bien examinar otro.


Descenso ordenado efectúa una busca on-line durante una dirección de coordenadas desde el punto actual en todos y cada iteración. Ciertas versiones del descenso ordenado escogen de manera aleatoria una dirección ordenada diferente en todos y cada iteración.


Hill climbing de reinicio azaroso es meta-algoritmo construido sobre la base de hill climbing. Es asimismo conocido como Shotgun hill climbing. Este efectúa, iterativamente, el hill-climbing, cada vez con una condición inicial azarosa x0. La mejor xm es guardada: si una nueva corrida del hill climbing genera una mejor xm que el estado guardado, lo sustituye.


Hill climbing de reinicio azaroso es un algoritmo sorprendentemente efectivo habitualmente. De esto se deriva que habitualmente es mejor gastar tiempo de CPU explorando el espacio, que esmeradamente optimar desde una condición inicial.

Una superficie con 2 máximos locales. (Solo uno de ellos es el máximo global.) Si un algoritmo de hill climbing empieza en una situación deficiente, confluirá al límite menor.

Un inconveniente con el hill climbing es que hallará solo el máximo local. Salvo que la heurística sea convexa, es posible que no alcance el máximo global.Otros algoritmos de busca local tratan de superar este inconveniente, entre ellos hill climbing estocástico, camino azaroso y simulated annealing.

Pese a que existen muchos máximos locales en este gráfico, el máximo global todavía puede encontrarse usando simulated annealing. Por desgracia, la aplicación de simulated annealing es concreta del inconveniente, puesto que el algoritmo consiste en hallar "saltos agraciados" que mejoran la situación. En inconvenientes que implican más dimensiones, el costo de localizar dicho salto puede aumentarse exponencialmente con la dimensionalidad. Consecuentemente, quedan todavía muchos inconvenientes para los que los algoritmos del hill climbing van a dar buenos resultados, al paso que los de simulated annealing van a correr eternamente sin conseguir ningún progreso. Esta ilustración muestra un caso extremo que implica solo una dimensión.

Cordilleras y corredores (pasadizos)


Las cordilleras son un reto para los algoritmos de hill climbing que optiman en espacios continuos. Dado a que los algoritmos de hill climbing ajustan solo un factor en el vector al unísono, a cada paso se moverá en una dirección alineada con el eje. Si la función objetivo determina una cordillera angosta que asciende en una dirección no alineada con el eje (o bien si el propósito es disminuir al mínimo, un corredor estrecho que desciende en una dirección no alineada con el eje), entonces el algoritmo de hill climbing solo puede ascender la cordillera (o bien descender por el corredor) en zigzag. Si los lados de la cordillera(o bien el corredor) son muy pronunciados, entonces el algoritmo puede verse forzado a efectuar pasos pequeñísimos mientras que serpentea cara una mejor situación. De esta forma, puede tomar una cantidad de tiempo irracional ascender la cordillera (o bien descender el corredor).


En cambio, los métodos de descenso del gradiente pueden moverse en cualquier dirección por la que la cordillera o bien el corredor pueden ascender o bien descender. De esta manera, el procedimiento de descenso en la dirección del gradiente o bien procedimiento del gradiente conjugado es en general preferido sobre hill climbing cuando la función objetivo es diferenciable. Los algoritmos de hill climbing, no obstante, tienen el beneficio de no requerir que la función objetivo sea diferenciable, con lo que pueden ser preferidos cuando la función es compleja.


Otro inconveniente que en ocasiones ocurre con hill climbing es el de la meseta. Una meseta se halla cuando el espacio de busca es plano, o bien suficientemente plano de forma tal que el valor retornado por la función objetivo es indistinguible de los valores retornados por zonas próximas debido a la precisión usada por la máquina para representar su valor. En estos casos el algoritmo es posible que no sea capaz de determinar exactamente en qué dirección debe seguir y puede tomar un camino que jamás conlleve a una mejora de la solución.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo hill climbing wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas