eCite Digital Repository

A random walk analysis of search in metaheuristics


Chen, S and Islam, S and Bolufe-Rohler, A and Montgomery, J and Hendtlass, T, A random walk analysis of search in metaheuristics, Proceedings of 2021 IEEE Congress on Evolutionary Computation (CEC), Jun 28 - Jul 1, 2021, Krakow, Poland, pp. 2323-2330. ISBN 9781728183930 (2022) [Refereed Conference Paper]

Copyright Statement

Copyright 2022 IEEE

DOI: doi:10.1109/CEC45853.2021.9504687


Random walks are a useful modeling tool for stochastic processes. The addition of model features (e.g. finite travel in one direction) can provide insight into specific practical situations (e.g. gambler's ruin). A series of random walk experiments are designed to study the effects of selection, exploration, and exploitation during the search processes of metaheuristics. We present a set of random walk conditions which leads to greater movement as the dimensionality of the sampling distributions increases. We then implement a version of Simulated Annealing in a similar search space which also achieves improving performance with increasing dimensionality. Conversely, we show that standard Particle Swarm Optimization has decreasing performance with increasing dimensionality which is consistent with the expected effects of the Curse of Dimensionality. These experiments give us insights into future methods that metaheuristics might be able to employ to defeat the Curse of Dimensionality (in globally convex, continuous domain search spaces).

Item Details

Item Type:Refereed Conference Paper
Keywords:random walk, exploration, selection, metaheuristic, curse of dimensionality
Research Division:Information and Computing Sciences
Research Group:Artificial intelligence
Research Field:Evolutionary computation
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the information and computing sciences
UTAS Author:Montgomery, J (Dr James Montgomery)
ID Code:154081
Year Published:2022 (online first 2021)
Deposited By:Information and Communication Technology
Deposited On:2022-10-27
Last Modified:2023-01-11

Repository Staff Only: item control page