Genetic Algorithm and Simulated Annealing on the Cross-in-Tray Function

Pure-Python implementations of a genetic algorithm (GA) and simulated annealing (SA) for global minimization of the Cross-in-Tray function, a classic multimodal benchmark with many local minima where gradient-based methods get trapped.

Both algorithms are written from scratch using only the Python standard library.

The Cross-in-Tray function

$$f(x, y) = -0.0001 \left( \left| \sin x \, \sin y \, \exp\!\left( \left| 100 - \frac{\sqrt{x^2 + y^2}}{\pi} \right| \right) \right| + 1 \right)^{0.1}$$

It is usually evaluated on $x, y \in [-10, 10]$ and has four global minima:

$$f(\pm 1.3491,\ \pm 1.3491) \approx -2.06261$$

The surface is covered in local minima arranged in a cross pattern, which makes it a standard test for global optimizers. See the SFU benchmark reference for details.

Algorithms

Genetic algorithm (`src/Genetic.py`)

Each individual encodes a candidate solution as two chromosomes, $x$ and $y$.

Component	Implementation
Initialization	Population sampled uniformly from $[-10, 10]^2$
Fitness	Share of the population's total objective value (lower $f$ means higher fitness, since $f < 0$)
Selection	Fitness-proportional (roulette-wheel) selection of two parents
Crossover	Child takes $x$ from one parent and $y$ from the other
Mutation	With 10% probability, $x$ or $y$ is scaled by a factor in $[0.9, 1.1]$
Output	Best individual in the final generation

Simulated annealing (`src/SimulatedAnnealing.py`)

Component	Implementation
Initialization	Random point sampled from a user-defined range
Neighbor move	Scale $x$, $y$, or both by a factor in $[0.8, 1.2]$
Acceptance	Improving moves are always accepted; worse moves are accepted with probability $e^{\Delta E / T}$
Cooling schedule	Linear: temperature decreases by 1 each iteration until it reaches 0

Usage

Requires Python 3. There are no external dependencies.

git clone https://github.com/ak811/cross-in-tray-optimization.git
cd cross-in-tray-optimization