Population migration: A meta-heuristics for stochastic approaches to constraint satisfaction problems

Mizuno K, Nishihara S, Kanoh H, & Kishi I (2001). Population migration: A meta-heuristics for stochastic approaches to constraint satisfaction problems. Informatica 25 (3): 421-429.

[img]
Preview
Text
Population migration A meta-heuristics for stochastic approaches to constraint satisfaction problems.pdf - Published Version
Available under License Creative Commons Attribution.

Download (779kB) | Preview

Abstract

A meta-heuristics for escaping from local optima to solve constraint satisfaction problems is proposed, which enables self-adaptive dynamic control of the temperature to adjust the locality of stochastic search. In our method, several groups with different temperatures are prepared. To each group the same number of candidate solutions are initially allotted. Then, the main process is repeated until the procedure comes to a certain convergence. The main process is composed of two phases: stochastic searching and population tuning. As for the latter phase, after evaluating the adaptation value of every group, migration of some number of candidate solutions in groups with lower values to groups with higher values are induced. Population migration is a kind ofparallel version of simulated annealing, where several temperatures are spatially distributed. Some experiments are performed to verify the efficiency of the method applied to constraint satisfaction problems. It is also demonstrated that population migration is exceptionally effective in the critical region where phase transitions occur.

Item Type: Article
Uncontrolled Keywords: constraint satisfaction, search algorithms, stochastic search, meta-heuristics
Research Programs: Risk, Modeling and Society (RMS)
Bibliographic Reference: Informatica; 25:421-429 [2001]
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 02:13
Last Modified: 30 Aug 2016 09:31
URI: http://pure.iiasa.ac.at/6316

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313