Geometric Nelder-Mead algorithm for the permutation representation

Alberto Moraglio, Julian Togelius

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    The Nelder-Mead Algorithm (NMA) is an almost half-century old method for numerical optimization, and it is a close relative of Particle Swarm Optimization (PSO) and Differential Evolution (DE). In recent work, PSO, DE and NMA have been generalized using a formal geometric framework that treats solution representations in a uniform way. These formal algorithms can be used as templates to derive rigorously specific PSO, DE and NMA for both continuous and combinatorial spaces retaining the same geometric interpretation of the search dynamics of the original algorithms across representations. In previous work, a geometric NMA was derived for the binary string representation. In this paper, we advance this line of research and derive formally a specific NMA for the permutation representation. The result is a Nelder-Mead Algorithm searching the space of permutations by acting directly on this representation. We present initial experimental results for the new algorithm on the Traveling Salesman Problem. The peculiar geometry of the permutation space seems to affect the performance of the geometric NMA that does not perform as well as the NMA for the binary string representation. We present a discussion about the nature of permutation spaces that seeks to explain this phenomenon. Further study is required to understand if this is a fundamental limitation of the application of the geometric NMA to permutation spaces.

    Original languageEnglish (US)
    Title of host publication2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
    DOIs
    StatePublished - 2010
    Event2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 - Barcelona, Spain
    Duration: Jul 18 2010Jul 23 2010

    Publication series

    Name2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010

    Other

    Other2010 6th IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010
    CountrySpain
    CityBarcelona
    Period7/18/107/23/10

    ASJC Scopus subject areas

    • Computational Theory and Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Geometric Nelder-Mead algorithm for the permutation representation'. Together they form a unique fingerprint.

  • Cite this

    Moraglio, A., & Togelius, J. (2010). Geometric Nelder-Mead algorithm for the permutation representation. In 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010 [5586321] (2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010). https://doi.org/10.1109/CEC.2010.5586321