Abstract | ||
---|---|---|
Stochastic search methods have attracted much attention of the Constraint Satisfaction Problem (CSP) research community. Traditionally, a stochastic solver escapes from localoptima or leaves plateaus by random restart or heuristic learning. In this paper, we propose the Progressive Stochastic Search (PSS) and its variants for solving binary CSPs, in which a variable always has to choose a new value when it is designated to be repaired. Intuitively, the search can be thought to be mainly driven by a "force" to "rush through" the local minima and plateaus. Timing results show that this approach signi.cantly outperforms LSDL(GENET) [2] in N-Queens, Latin squares, random permutation generation problems and randomly CSPs, while it fails to win LSDL(GENET) in quasigroup completion problems and increasing permutation generation problems. This prompts an interesting new research direction in the design of stochastic search schemes. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1109/TAI.2003.1250229 | ICTAI |
Keywords | Field | DocType |
computability,constraint theory,problem solving,search problems,stochastic processes,LSDL (GENET),Latin squares,N-Queens,binary CSP,constraint satisfaction problem,heuristic learning,progressive stochastic search,random CSP,random permutation generation problem,stochastic solver | Heuristic,Stochastic optimization,Mathematical optimization,Local optimum,Computer science,Permutation,Stochastic process,Random permutation,Constraint satisfaction problem,Artificial intelligence,Solver,Machine learning | Conference |
ISSN | ISBN | Citations |
1082-3409 | 0-7695-2038-3 | 3 |
PageRank | References | Authors |
0.45 | 8 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bryan Chi-ho Lam | 1 | 3 | 0.45 |
hofung leung | 2 | 1314 | 132.32 |