English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Parameterized runtime analysis seeks to understand the influence of problemstructure on algorithmic runtime. In this paper, we contribute to thetheoretical understanding of evolutionary algorithms and carry out aparameterized analysis of evolutionary algorithms for the Euclidean travelingsalesperson problem (Euclidean TSP).  We investigate the structural properties in TSP instances that influence theoptimization process of evolutionary algorithms and use this information tobound the runtime of simple evolutionary algorithms. Our analysis studies theruntime in dependence of the number of inner points $k$ and shows that $(\mu +\lambda)$ evolutionary algorithms solve the Euclidean TSP in expected time$O((\mu/\lambda) \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + (\mu/\lambda)\cdot n^{4k}(2k-1)!)$ where $\gamma$ is a function of the minimum angle$\epsilon$ between any three points.  Finally, our analysis provides insights into designing a mutation operatorthat improves the upper bound on expected runtime. We show that a mixedmutation strategy that incorporates both 2-opt moves and permutation jumpsresults in an upper bound of $O((\mu/\lambda) \cdot n^3\gamma(\epsilon) +n\gamma(\epsilon) + (\mu/\lambda) \cdot n^{2k}(k-1)!)$ for the $(\mu+\lambda)$EA.

Parameterized Runtime Analyses of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem