| dbpprop:abstract
|
- Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of applied mathematics, namely locating a good approximation to the global minimum of a given function in a large search space. It is often used when the search space is discrete (e.g. , all tours that visit a given set of cities). For certain problems, simulated annealing may be more effective than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution. The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one. By analogy with this physical process, each step of the SA algorithm replaces the current solution by a random "nearby" solution, chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T (called the temperature), that is gradually decreased during the process. The dependency is such that the current solution changes almost randomly when T is large, but increasingly "downhill" as T goes to zero. The allowance for "uphill" moves saves the method from becoming stuck at local minima—which are the bane of greedier methods. The method was independently described by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi in 1983, and by V. Černý in 1985
- Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und einfache mathematische Verfahren ausschließen. Benutzt wird dieses Verfahren zum Beispiel beim Floorplanning im Laufe eines Chipentwurfs. Grundidee ist die Nachbildung eines Abkühlungsprozesses, etwa beim Glühen in der Werkstoffkunde. Nach Erhitzen eines Metalls sorgt die langsame Abkühlung dafür, dass die Atome ausreichend Zeit haben, sich zu ordnen und stabile Kristalle zu bilden. Dadurch wird ein energiearmer Zustand, nahe am Optimum erreicht. Übertragen auf das Optimierungsverfahren entspricht die Temperatur einer Wahrscheinlichkeit, mit der sich ein Zwischenergebnis der Optimierung auch verschlechtern darf. Der Metropolisalgorithmus ist die Grundlage der simulierten Abkühlung. Im Gegensatz zu einem Lokale-Suche-Algorithmus kann das Verfahren ein lokales Optimum wieder verlassen und ein besseres finden.
- Simulované žíhání je metoda prohledávání stavového prostoru založená na simulaci žíhání oceli. Při prohledávání stavového prostoru se může snadno stát, že algoritmus uvázne v lokálním minimu. V metodě se tomu snažíme zabránit tím, že zpočátku provádíme velké změny a díky tomu se můžeme dostat z lokálního minima. Velikost změny záleží na teplotě. Čím větší je teplota, tím větší se provádí změny. Algoritmus pracuje s pouze s jedním kandidátním řešením. Obyčejný gradientní algoritmus přijímá nové řešení pouze pokud je lepší než řešení stávající. Při simulovaném žíhání jsou s určitou pravděpodobností přijímána i řešení horší. Pravděpodobnost přijetí i horšího řešení je přímo závislá na teplotě. V průběhu výpočtu algoritmu je teplota postupně snižována na základě rychlosti konvergence. Pokud algoritmus konverguje rychle, snižuje se teplota také rychle. Konverguje-li algoritmus pomalu, zpomalí se snižování teploty, aby se případně podařilo vyprostit z lokálního minima.
- Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta-heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande. El nombre e inspiración viene del proceso de recocido del acero, una técnica que consiste en calentar y luego enfriar controladamente un material para aumentar el tamaño de sus cristales y reducir sus defectos. El calor causa que los átomos se salgan de sus posiciones iniciales (un mínimo local de energía) y se muevan aleatoriamente; el enfriamiento lento les da mayores probabilidades de encontrar configuraciones con menor energía que la inicial.
- Le recuit simulé est une métaheuristique inspirée d'un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l'énergie du matériau. Elle est aujourd'hui utilisée en optimisation pour trouver les extrema d'une fonction. Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983, et indépendamment par V. Cerny en 1985.
- Il Simulated Annealing (in italiano Ricottura simulata) è una strategia che viene utilizzata per risolvere problemi di ottimizzazione. Questo processo mira a trovare un minimo globale quando si è in presenza di più minimi locali. Il concetto di Annealing deriva dalla scienza dei metalli, dov'è usato per descrivere il processo di eliminazione di difetti reticolari dai cristalli tramite una procedura di riscaldamento seguita da un lento raffreddamento. In questo caso un difetto reticolare corrisponde ad una combinazione errata di due oggetti (ad esempio una connessione errata di due neuroni all'interno di una rete neurale).
- 焼きなまし法（Simulated Annealing、SAと略記、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の確率的メタアルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案した（1985年にも V. Cerny が独自に考案）。 その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。 SAアルゴリズムは解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ T（温度を意味する）が影響する。そして前述の物理過程との相似によって、T（温度）の値は徐々に小さくなっていく。このため、最初はTが大きいので解は大胆に変化するが、Tがゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。
- Simulated annealing (SA) is een generiek, probabilistisch heuristiek optimalisatiealgoritme gebruikt om een benadering van het globale optimum van een gegeven functie (wiskunde)functie in een grote zoekruimte te vinden. Het is onafhankelijk van elkaar uitgevonden door S. Kirkpatrick, C. D. Gelatt en M. P. Vecchi in 1983 en door by V. Cerny in 1985. De naam en inspiratie komen van een Engelse term, 'annealing', binnen de metallurgiemetaalbewerking. Het betreft een techniek waarbij metaal verhit wordt en daarna gecontroleerd afgekoeld om de grootte van de kristallen binnen het materiaal te vergroten en daarmee het aantal defecten te verkleinen.
- Symulowane wyżarzanie to rodzaj algorytmu heurystycznego przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania symulowanego wyżarzania nieprzypadkowo przypomina zjawisko wyżarzania w metalurgii.
- Arrefecimento simulado ou simulated annealing é uma metaheurística para otimização que consiste numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica. Esta metaheurística é uma metáfora de um processo térmico, dito annealing ou recozimento, utilizado em metalurgia para obtenção de estados de baixa energia num sólido. O processo consiste de duas etapas: na primeira a temperatura do sólido é aumentada para um valor máximo no qual ele se funde; na segunda o resfriamento deve ser realizado lentamente até que o material se solidifique, sendo acompanhado e controlado esse arrefecimento. Nesta segunda fase, executada lentamente, os átomos que compõem o material organizam-se numa estrutura uniforme com energia mínima. Isto provoca que os átomos desse material ganhem energia para se movimentarem livremente e, ao arrefecer de forma controlada, dar-lhes uma melhor hipótese de se organizarem numa configuração com menor energia interna, para ter, como resultado prático, uma redução dos defeitos do material. De forma análoga, o algoritmo de arrefecimento simulado substitui a solução actual por uma solução próxima (i.e. , na sua vizinhança no espaço de soluções), escolhida de acordo com uma função objectivo e com uma variável <math>T</math> (dita Temperatura, por analogia). Quanto maior for <math>T</math>, maior a componente aleatória que será incluída na próxima solução escolhida. À medida que o algoritmo progride, o valor de <math>T</math> é decrementado, começando o algoritmo a converter para uma solução óptima, necessariamente local. Uma das principais vantagens deste algoritmo é permitir testar soluções mais distantes da solução actual e dar mais independência do ponto inicial da pesquisa.
- Алгоритм имитации отжига — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.
- Eniyileme teorisi, nicel olarak en iyiyi bulmayı ve bunun yöntemlerini inceler. En iyinin nasıl tanımlanacağını ve ona nasıl ulaşılacağını araştırır. Arama uzayının büyüklüğü nedeniyle kombinasyonel eniyileme problemlerinin çözümü, eniyileme yöntemlerinden faydalanmayı gerektirir. Büyük bir arama uzayı içinde gerekirci yöntemlerin kullanımı, hemen hemen imkânsızdır. Çünkü bu arama uzayı içinde en iyi çözümlerin bulunması çok zaman alır. Yerel arama yöntemleri de, arama sürecinde yerel en küçük çözümde takılıp, daha iyi bir çözüm değerine ulaşılmasına engel olabilir. Arama algoritmaları için bir dezavantaj sayılan bu durum karşısında daha detaylı arama yapan arama yöntemleri geliştirilmiştir. Benzetilmiş tavlama algoritması, bu yöntemlerden birisidir. Benzetilmiş tavlama algoritması, pek çok değişkene sahip fonksiyonların en büyük veya en küçük değerlerinin bulunması ve özellikle pek çok yerel en küçük değere sahip doğrusal olmayan fonksiyonların en küçük değerlerinin bulunması için tasarlanmıştır. Diğer olasılıksal yaklaşımlar (genetik algoritmalar, tabu arama vb. ) gibi en iyi çözümün en kısa zamanda üretimini sağlar. Bu sebeple, özellikle matematiksel modellerle gösterilemeyen kombinasyonel problemlerin eniyileme uygulamalarında tercih edilir. Benzetilmiş tavlama algoritması; elektronik devre tasarımı, görüntü işleme, yol bulma problemleri, seyahat problemleri, malzeme fizigi simulasyonu, kesme ve paketleme problemleri, akış çizelgeleme ve iş çizelgeleme problemlerinin çözümlerinde başarılı sonuçlar vermiştir.
- 模擬退火是一種通用概率演算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火是 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 在1983年所發明。而 V. Černý 在1985年也獨立發明此演算法。
|
| rdfs:comment
|
- Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of applied mathematics, namely locating a good approximation to the global minimum of a given function in a large search space. It is often used when the search space is discrete (e.g. , all tours that visit a given set of cities).
- Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und einfache mathematische Verfahren ausschließen. Benutzt wird dieses Verfahren zum Beispiel beim Floorplanning im Laufe eines Chipentwurfs.
- Simulované žíhání je metoda prohledávání stavového prostoru založená na simulaci žíhání oceli. Při prohledávání stavového prostoru se může snadno stát, že algoritmus uvázne v lokálním minimu. V metodě se tomu snažíme zabránit tím, že zpočátku provádíme velké změny a díky tomu se můžeme dostat z lokálního minima. Velikost změny záleží na teplotě. Čím větší je teplota, tím větší se provádí změny.
- Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta-heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande. El nombre e inspiración viene del proceso de recocido del acero, una técnica que consiste en calentar y luego enfriar controladamente un material para aumentar el tamaño de sus cristales y reducir sus defectos.
- Le recuit simulé est une métaheuristique inspirée d'un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l'énergie du matériau. Elle est aujourd'hui utilisée en optimisation pour trouver les extrema d'une fonction. Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983, et indépendamment par V. Cerny en 1985.
- Il Simulated Annealing (in italiano Ricottura simulata) è una strategia che viene utilizzata per risolvere problemi di ottimizzazione. Questo processo mira a trovare un minimo globale quando si è in presenza di più minimi locali. Il concetto di Annealing deriva dalla scienza dei metalli, dov'è usato per descrivere il processo di eliminazione di difetti reticolari dai cristalli tramite una procedura di riscaldamento seguita da un lento raffreddamento.
- 焼きなまし法（Simulated Annealing、SAと略記、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の確率的メタアルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案した（1985年にも V.
- Simulated annealing (SA) is een generiek, probabilistisch heuristiek optimalisatiealgoritme gebruikt om een benadering van het globale optimum van een gegeven functie (wiskunde)functie in een grote zoekruimte te vinden. Het is onafhankelijk van elkaar uitgevonden door S. Kirkpatrick, C. D. Gelatt en M. P. Vecchi in 1983 en door by V. Cerny in 1985. De naam en inspiratie komen van een Engelse term, 'annealing', binnen de metallurgiemetaalbewerking.
- Symulowane wyżarzanie to rodzaj algorytmu heurystycznego przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania symulowanego wyżarzania nieprzypadkowo przypomina zjawisko wyżarzania w metalurgii.
- Arrefecimento simulado ou simulated annealing é uma metaheurística para otimização que consiste numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica. Esta metaheurística é uma metáfora de um processo térmico, dito annealing ou recozimento, utilizado em metalurgia para obtenção de estados de baixa energia num sólido.
- Алгоритм имитации отжига — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.
- Eniyileme teorisi, nicel olarak en iyiyi bulmayı ve bunun yöntemlerini inceler. En iyinin nasıl tanımlanacağını ve ona nasıl ulaşılacağını araştırır. Arama uzayının büyüklüğü nedeniyle kombinasyonel eniyileme problemlerinin çözümü, eniyileme yöntemlerinden faydalanmayı gerektirir. Büyük bir arama uzayı içinde gerekirci yöntemlerin kullanımı, hemen hemen imkânsızdır. Çünkü bu arama uzayı içinde en iyi çözümlerin bulunması çok zaman alır.
- 模擬退火是一種通用概率演算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火是 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 在1983年所發明。而 V. Černý 在1985年也獨立發明此演算法。
|
![[RDF Data]](/statics/sw-cube.png)
