eCite Digital Repository
A random walk analysis of search in metaheuristics
Citation
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
Abstract
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 |
Downloads: | 0 |
Repository Staff Only: item control page