{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T20:35:06Z","timestamp":1723322106464},"reference-count":30,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T00:00:00Z","timestamp":1048204800000},"content-version":"vor","delay-in-days":140,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2002,11]]},"abstract":"Abstract<\/jats:title>A local\u2010search heuristic for finding high\u2010quality solutions for many hard optimization problems is explored. The method is inspired by recent progress in understanding far\u2010from\u2010equilibrium phenomena in terms of self\u2010organized criticality, a concept introduced to describe emergent complexity in physical systems. This method, called extremal optimization, successively replaces the value of extremely undesirable variables in a sub\u2010optimal solution with new, random ones. Large, avalanche\u2010like fluctuations in the cost function emerge dynamically. These enable the search to effectively scaling barriers to explore local optima in distant neighborhoods of the configuration space while eliminating the need to tune parameters. Drawing upon models used to simulate the dynamics of granular media, evolution, or geology, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as simulated annealing. This method is very general and so far has proved competitive with\u2014and even superior to\u2014more elaborate general\u2010purpose heuristics on testbeds of constrained optimization problems with up to 105<\/jats:sup> variables, such as bipartitioning, coloring, and spin glasses. Analysis of a model problem predicts the only free parameter of the method in accordance with all experimental results. \u00a9 2003 Wiley Periodicals, Inc.<\/jats:p>","DOI":"10.1002\/cplx.10072","type":"journal-article","created":{"date-parts":[[2003,3,24]],"date-time":"2003-03-24T11:59:12Z","timestamp":1048507152000},"page":"57-62","source":"Crossref","is-referenced-by-count":47,"title":["Optimization with extremal dynamics"],"prefix":"10.1002","volume":"8","author":[{"given":"Stefan","family":"Boettcher","sequence":"first","affiliation":[]},{"given":"Allon G.","family":"Percus","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2003,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5426-1"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/27\/20\/001"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023069201470"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.53.414"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.71.4083"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.348"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.59.381"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00007-2"},{"key":"e_1_2_1_10_2","volume-title":"Spin Glass Theory and Beyond","author":"Mezard M.","year":"1987"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/32\/28\/302"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.5211"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026114"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/35\/5\/301"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056918"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"Hendrickson B.A.;Leland R.A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing '95; San Diego CA 1995.","DOI":"10.1145\/224170.224228"},{"key":"e_1_2_1_18_2","unstructured":"Karypis G.;Kumar V.METIS a Software Package for Partitioning Unstructured Graphs seehttp:\/\/www\u2010users.cs.umn.edu\/karypis\/metis\/main.shtml(METIS is copyrighted by the Regents of the University of Minnesota)."},{"key":"e_1_2_1_19_2","unstructured":"Dall J.Searching Complex State Spaces with Extremal Optimization and other Stochastic Techniques. Thesis Fysisk Institut Syddansk Universitet Odense 2000(in Danish)."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.6.865"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00044-5"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4371(95)00348-7"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1209\/epl\/i1997-00483-y"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.5135"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.67.060403"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022221005097"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.59.3617"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/27\/4\/001"},{"key":"e_1_2_1_30_2","unstructured":"7th DIMACS Implementation Challenge on Semidefinite and related Optimization Problems;Johnson D.S.;Pataki G.;Alizadeh F. Eds.; (to appear seehttp:\/\/dimacs.rutgers.edu\/Challenges\/Seventh\/#PC)."},{"key":"e_1_2_1_31_2","unstructured":"J\u00fcnger M.;Liers F. private communication."}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcplx.10072","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cplx.10072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T05:08:50Z","timestamp":1694495330000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cplx.10072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["10.1002\/cplx.10072"],"URL":"https:\/\/doi.org\/10.1002\/cplx.10072","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}