Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Dynamik und Statistische Physik
DY 19: Poster II
DY 19.43: Poster
Donnerstag, 20. März 1997, 09:30–12:30, Z
Suchraumglättung für kombinatorische Optimierungsprobleme — •J. Schneider1, M. Dankesreiter1, W. Fettes1, I. Morgenstern1, M. Schmid1, and J. M. Singer2 — 1Institut für Theoretische Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — 2Physikinstitut, Universität Zürich, CH-8057 Zürich
Commonly there are two types of local search [1] 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 barriers separating different minima. The second is introducing a control-parameter 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 [2], i.e. to eliminate barriers between low-energy configurations and therefore to allow a fast and easy approach to the global optimum. We present results for this procedure [3].
[1] G. Dueck, J. Comp. Phys. , Vol. 104, 86 (1993)
[2] Jun Gu, IEEE Transactions on Systems,
Man and Cybernetics,
Vol. 24, No. 5, May 1994
[3] J. Schneider, M. Dankesreiter, W. Fettes, I. Morgenstern,
M. Schmid, J. M. Singer, submitted to Physica A