← Back to EAX docs

teeline · algorithms/eax

Memetic EAX — one crossover event

EAX keeps almost all of the parents' edges and only rewires the symmetric difference. This storyboard is simplified for teaching: the default 1-AB pins one AB-cycle, while the solver picks a random one each child.

Compare Parentsframe 1/10
Both parents are crossing-free; 11 of 16 edges are shared.
Parent A Parent B shared removed bridge child
shared edges
11/16 (69%)
AB-cycles
2 · 4 / 6
E-set
1 cycle
subtours
2
bridges
1
cost A / B / child
1073.5 / 1138.9 / 994.4
child edge inheritance
shared 10 · from A 2 · from B 2 · new 2

Stage 1 of 6: Compare Parents. Parent A costs 1073.5, Parent B 1138.9. The pinned fixture shares 11 edges and has 2 AB-cycles. The E-set selects 1 cycle, producing 2 subtours and 1 bridge. The child costs 994.4.

AB-cycles and the selected E-set
CycleCitiesSelected
Cycle #14yes
Cycle #26no
Subtours21 bridge
Child cost994.4vs A 1073.5
cities: 16shared: 11/16E-set: C1