Schneider, Johannes and Dankesreiter, Markus and Fettes, Werner and Morgenstern, Ingo and Schmid, Martin and Singer, Johannes Maria
Search-space smoothing for combinatorial optimization problems.
Physica A Statistical Mechanics and its Applications 243 (1-2), pp. 77-112.
Commonly there are two types of local search approaches known to treat combinatorial optimization problems with very complex search-space structure: One is to introduce very complicated types of local move classes, allowing a bypass of high energetic barriers separating different minima. The second is introducing a control-parameter (i.e. temperature in physics terminology) dependent state space walker, which is — depending on this control parameter — more or less easily able to climb over barriers. A third, less well-known, but very obvious approach is to smooth the search space, i.e. to eliminate barriers between low-energy configurations and therefore to allow a fast and easy approach to the global optimum. This procedure will be discussed in depth in the following work.
|Institutions:|| Physics > Institute of Theroretical Physics > Professor Morgenstern|
|02.50.-r; 02.50.Ga; 02.70.Lg; 89.20.+a; 89.80.+h; 89.90.+n||PACS|
|Keywords:||Optimization; Monte Carlo; Traveling salesman; Great deluge; Smoothing; Local searc|
|Subjects:||500 Science > 530 Physics|
|Created at the University of Regensburg:||Unknown|
|Deposited On:||09 Aug 2010 12:25|
|Last Modified:||20 Jul 2011 22:34|