Loading…
Best possible strategy for finding ground states
Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance...
Saved in:
| Published in: | Physical review letters 2001-06, Vol.86 (23), p.5219-5222 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3 |
| container_end_page | 5222 |
| container_issue | 23 |
| container_start_page | 5219 |
| container_title | Physical review letters |
| container_volume | 86 |
| creator | Franz, A Hoffmann, K H Salamon, P |
| description | Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that, within the large class of algorithms that simulate a random walk on the landscape, threshold accepting is the best possible strategy. In particular, it can perform better than simulated annealing and Tsallis statistics. Our proof is the first example of a provably optimal strategy in this area. |
| doi_str_mv | 10.1103/PhysRevLett.86.5219 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_osti_</sourceid><recordid>TN_cdi_osti_scitechconnect_40203643</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>70901136</sourcerecordid><originalsourceid>FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3</originalsourceid><addsrcrecordid>eNpNkF9LwzAUxYMobk4_gSAFwbfOe5MsaR91-A8Giuw9tOntVunamaTCvr0ZG-jTvXB_51zOYewaYYoI4v5jvfOf9LOgEKaZms445idsjKDzVCPKUzYGEJjmAHrELrz_AgDkKjtnI0SRSan4mMEj-ZBse--bsqXEB1cEWu2SundJ3XRV062SleuHroq3ePKX7KwuWk9Xxzlhy-en5fw1Xby_vM0fFqkVPA-pRLQ8q4CTBqXiVpc5LzTXmUQNudCi1LNS5rxGJAmVjTjHCmeysgJJTNjtwbb3oTHeNoHs2vZdRzYYCRyEkiJSdwdq6_rvISYxm8Zbatuio37wJn6CmFVFUBxA62JUR7XZumZTuJ1BMPs2zb82TabMvs2oujnaD-WGqj_NsT7xCx5rcRA</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>70901136</pqid></control><display><type>article</type><title>Best possible strategy for finding ground states</title><source>American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)</source><creator>Franz, A ; Hoffmann, K H ; Salamon, P</creator><creatorcontrib>Franz, A ; Hoffmann, K H ; Salamon, P</creatorcontrib><description>Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that, within the large class of algorithms that simulate a random walk on the landscape, threshold accepting is the best possible strategy. In particular, it can perform better than simulated annealing and Tsallis statistics. Our proof is the first example of a provably optimal strategy in this area.</description><identifier>ISSN: 0031-9007</identifier><identifier>EISSN: 1079-7114</identifier><identifier>DOI: 10.1103/PhysRevLett.86.5219</identifier><identifier>PMID: 11384462</identifier><language>eng</language><publisher>United States: The American Physical Society</publisher><subject>ALGORITHMS ; ANNEALING ; BASIC BIOLOGICAL SCIENCES ; GROUND STATES ; Models, Theoretical ; NEURAL NETWORKS ; PROTEINS ; SPIN ; STATISTICS</subject><ispartof>Physical review letters, 2001-06, Vol.86 (23), p.5219-5222</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3</citedby><cites>FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,776,780,881,27901,27902</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/11384462$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink><backlink>$$Uhttps://www.osti.gov/biblio/40203643$$D View this record in Osti.gov$$Hfree_for_read</backlink></links><search><creatorcontrib>Franz, A</creatorcontrib><creatorcontrib>Hoffmann, K H</creatorcontrib><creatorcontrib>Salamon, P</creatorcontrib><title>Best possible strategy for finding ground states</title><title>Physical review letters</title><addtitle>Phys Rev Lett</addtitle><description>Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that, within the large class of algorithms that simulate a random walk on the landscape, threshold accepting is the best possible strategy. In particular, it can perform better than simulated annealing and Tsallis statistics. Our proof is the first example of a provably optimal strategy in this area.</description><subject>ALGORITHMS</subject><subject>ANNEALING</subject><subject>BASIC BIOLOGICAL SCIENCES</subject><subject>GROUND STATES</subject><subject>Models, Theoretical</subject><subject>NEURAL NETWORKS</subject><subject>PROTEINS</subject><subject>SPIN</subject><subject>STATISTICS</subject><issn>0031-9007</issn><issn>1079-7114</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2001</creationdate><recordtype>article</recordtype><recordid>eNpNkF9LwzAUxYMobk4_gSAFwbfOe5MsaR91-A8Giuw9tOntVunamaTCvr0ZG-jTvXB_51zOYewaYYoI4v5jvfOf9LOgEKaZms445idsjKDzVCPKUzYGEJjmAHrELrz_AgDkKjtnI0SRSan4mMEj-ZBse--bsqXEB1cEWu2SundJ3XRV062SleuHroq3ePKX7KwuWk9Xxzlhy-en5fw1Xby_vM0fFqkVPA-pRLQ8q4CTBqXiVpc5LzTXmUQNudCi1LNS5rxGJAmVjTjHCmeysgJJTNjtwbb3oTHeNoHs2vZdRzYYCRyEkiJSdwdq6_rvISYxm8Zbatuio37wJn6CmFVFUBxA62JUR7XZumZTuJ1BMPs2zb82TabMvs2oujnaD-WGqj_NsT7xCx5rcRA</recordid><startdate>20010604</startdate><enddate>20010604</enddate><creator>Franz, A</creator><creator>Hoffmann, K H</creator><creator>Salamon, P</creator><general>The American Physical Society</general><scope>CGR</scope><scope>CUY</scope><scope>CVF</scope><scope>ECM</scope><scope>EIF</scope><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope><scope>OTOTI</scope></search><sort><creationdate>20010604</creationdate><title>Best possible strategy for finding ground states</title><author>Franz, A ; Hoffmann, K H ; Salamon, P</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2001</creationdate><topic>ALGORITHMS</topic><topic>ANNEALING</topic><topic>BASIC BIOLOGICAL SCIENCES</topic><topic>GROUND STATES</topic><topic>Models, Theoretical</topic><topic>NEURAL NETWORKS</topic><topic>PROTEINS</topic><topic>SPIN</topic><topic>STATISTICS</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Franz, A</creatorcontrib><creatorcontrib>Hoffmann, K H</creatorcontrib><creatorcontrib>Salamon, P</creatorcontrib><collection>Medline</collection><collection>MEDLINE</collection><collection>MEDLINE (Ovid)</collection><collection>MEDLINE</collection><collection>MEDLINE</collection><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><collection>OSTI.GOV</collection><jtitle>Physical review letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Franz, A</au><au>Hoffmann, K H</au><au>Salamon, P</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Best possible strategy for finding ground states</atitle><jtitle>Physical review letters</jtitle><addtitle>Phys Rev Lett</addtitle><date>2001-06-04</date><risdate>2001</risdate><volume>86</volume><issue>23</issue><spage>5219</spage><epage>5222</epage><pages>5219-5222</pages><issn>0031-9007</issn><eissn>1079-7114</eissn><abstract>Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that, within the large class of algorithms that simulate a random walk on the landscape, threshold accepting is the best possible strategy. In particular, it can perform better than simulated annealing and Tsallis statistics. Our proof is the first example of a provably optimal strategy in this area.</abstract><cop>United States</cop><pub>The American Physical Society</pub><pmid>11384462</pmid><doi>10.1103/PhysRevLett.86.5219</doi><tpages>4</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0031-9007 |
| ispartof | Physical review letters, 2001-06, Vol.86 (23), p.5219-5222 |
| issn | 0031-9007 1079-7114 |
| language | eng |
| recordid | cdi_osti_scitechconnect_40203643 |
| source | American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list) |
| subjects | ALGORITHMS ANNEALING BASIC BIOLOGICAL SCIENCES GROUND STATES Models, Theoretical NEURAL NETWORKS PROTEINS SPIN STATISTICS |
| title | Best possible strategy for finding ground states |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-02T00%3A39%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_osti_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Best%20possible%20strategy%20for%20finding%20ground%20states&rft.jtitle=Physical%20review%20letters&rft.au=Franz,%20A&rft.date=2001-06-04&rft.volume=86&rft.issue=23&rft.spage=5219&rft.epage=5222&rft.pages=5219-5222&rft.issn=0031-9007&rft.eissn=1079-7114&rft_id=info:doi/10.1103/PhysRevLett.86.5219&rft_dat=%3Cproquest_osti_%3E70901136%3C/proquest_osti_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c329t-411c28d02e706628dfb92a727841709373b75b492f11e40dc1c221d154dc31e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=70901136&rft_id=info:pmid/11384462&rfr_iscdi=true |