HeDoS

This source code deals with solving 3D Travelling Salesman Problem using Genetic Algorithms.

Originally developed for an MSc thesis in 2006, it has been modernized to use Java 25 (LTS), Maven, and structured YAML configuration.

Key Features

• Java 25 Modernization: Utilizes Virtual Threads, finalized Structured Concurrency (Joiners), and Scoped Values for clean, immutable, and scalable context propagation across parallel execution scopes.
• High-Performance Math & Memory: Leverages the Vector API (SIMD) for lightning-fast calculations and the Foreign Function & Memory (FFM) API for optimized off-heap management of distance matrices and population genomes.
• Robust Architecture: Built with Google Guice (DI), Jackson (YAML), and a reactive EventBus for clean separation of concerns and thread-safe, event-driven UI localization.
• Interactive Visualization: Real-time performance charting with persistent tooltips, 3D path rendering, and a compact, localized configuration side panel.
• Scientific Benchmarking: Integrated JMH (Java Microbenchmark Harness) suite to quantify SIMD speedups and memory throughput directly from the UI.

Why the FFM API?

Traditional Java arrays are indexed by int, limiting them to approximately 2.1 billion elements. For large-scale 3D TSP problems, the $N^2$ distance matrix can easily exceed this limit. By using the FFM API (MemorySegment):

• Beyond the 2GB Limit: We utilize long addressing to support massive coordinate datasets.
• GC Efficiency: Memory for distance matrices and population genomes is allocated via Arena.ofAuto(), reducing heap pressure and providing a foundation for zero-copy variation.
• Native Hardware Alignment: MemorySegment allows for precise 64-byte alignment (AVX-512 compatible), enabling the Vector API to perform peak-performance "aligned loads."

Optimization Algorithms

HeDoS implements several state-of-the-art algorithms for solving the 3D Travelling Salesman Problem:

Crossover Operators

• Cycle Crossover (CX): Ensures that all genes in the offspring come from the same position in one of the parents. Oliver et al. (1987)
• Edge Recombination (ERX): Focuses on preserving edge adjacencies, which is critical for TSP. Whitley et al. (1989)
• Partially Mapped Crossover (PMX): An approach that respects absolute positions and maintains valid permutations. Goldberg & Lingle (1985)
• Single Point Crossover: Splits parent chromosomes at a single point and exchanges segments to produce offspring, maintaining gene order and diversity.
• Two Point Crossover: Swaps two segments between parents to produce offspring, preserving relative order and diversity.
• Uniform Crossover: Randomly selects genes from each parent with equal probability, promoting genetic diversity in offspring.
• Vectorized Uniform Crossover: A custom high-performance uniform crossover utilizing Java Vector API (SIMD) for rapid offspring generation.

Mutation Operators

• Displacement Mutation: Extracts a sub-tour and re-inserts it at a random position, effectively shifting segments of the tour. Michalewicz (1992)
• Inversion Mutation: Reverses the order of a randomly selected subset of genes, helping to eliminate path crossings and improve solution quality.
• Only Improving Random Mutation: Applies random mutations only if they result in an improved solution, ensuring non-decreasing fitness.
• Only Improving Systematic Mutation: Systematically explores possible mutations and applies only those that improve the solution, ensuring non-decreasing fitness.
• Random Mutation: Randomly alters genes in the chromosome to introduce genetic diversity and prevent premature convergence.
• Vectorized Scramble Mutation: Randomly reorders a subset of genes to maintain genetic diversity. Syswerda (1991). Our implementation is SIMD-accelerated for bulk gene processing.

Selection Operators

• Roulette Wheel Selection: Selects individuals probabilistically based on fitness proportion, giving higher chances to fitter individuals. Goldberg (1989)
• Stochastic Universal Sampling: Selects multiple individuals in a single pass using evenly spaced pointers, ensuring a more representative sampling of the population. Baker (1987)
• Tournament Selection: Randomly selects a group of individuals and chooses the best among them, balancing selection pressure and diversity. Goldberg & Deb (1991)

Local Search Optimizers (LSO)

• 2-Opt: A basic local search that iteratively removes edge crossings by swapping pairs of edges. Croes (1958)
• 3-Opt: A more powerful heuristic that explores triplet edge removals. Our implementation utilizes java.util.stream for Parallel Best-Improvement scanning across the tour. Lin (1965)
• Lin-Kernighan (LKH): Often considered the gold standard for TSP, this is a variable-k-opt heuristic. Lin & Kernighan (1973)
• Partitioned Parallel 2-Opt: A specialized implementation that divides the tour into segments and optimizes them concurrently using modern Java concurrency primitives.
• Multi Start Local Search

Getting Started

Prerequisites

• Java 25 (LTS): Required for the latest performance improvements, Vector API (SIMD), and Virtual Threads.
  • JVM Flags: Because the project utilizes incubator and preview features, the following flags are required:
    • --add-modules jdk.incubator.vector
    • --enable-preview
• Maven 3.8+: Used for dependency management and build orchestration.
• Xj3D Libraries: See the manual installation section below.

Quick Start

The project includes helper scripts for a streamlined setup:

1. Install Dependencies: Copy required Xj3D JARs to lib/ and run:

   ./install_deps.sh

2. Build and Run:

   ./run.sh

Alternatively, use Maven directly:

mvn clean compile exec:exec

Usage

1. Targets: Manage 3D points via the "Manage Targets" dialog or generate random datasets through "File > Generate Random Targets".
2. Configuration: Adjust GA parameters (Population, Mutation, Crossover, Elitism, Stagnation) in the localized side panel. Hover over ComboBox items to see strategy descriptions.
3. Hybrid GA: Select a Local Optimization strategy (e.g., Lin-Kernighan or Parallel 3-Opt) to significantly improve solution quality.
4. Benchmarking: Scientific validation of optimizations is available via the Benchmark menu. Results are displayed in a detailed dialog after the JMH suite completes.
5. Analysis: Use the real-time Duration Chart to monitor total time, local search time, and fitness. Click on the chart to view exact generation metrics in a persistent tooltip.
6. Persistence: Save your best tour, settings, or performance statistics using the "File" menu.

License: Apache License 2.0

---

Xj3D installation and copying required libraries

• Download Xj3D installer from Xj3D Download Page
• Install it and copy the following JARs from jar inside the Xj3D installation folder to the lib folder under the project folder:

File	Suggested ArtifactId
aviatrix3d-all_3.1.1-nps.jar	aviatrix3d-all
xj3d.browser_2.3.0-nps.jar	xj3d-browser
xj3d.cadfilter_2.3.0-nps.jar	xj3d-cadfilter
xj3d.replica_2.3.0-nps.jar	xj3d-replica
xj3d-2.3-3rdparty-nps.jar	xj3d-3rdparty
xj3d-2.3-nps.jar	xj3d-core

• You can run the program now, it gives the following native library error:

  SEVERE: Native code library (32 and 64 bit library) failed to load: java.lang.UnsatisfiedLinkError: no odejava in java.library.path ``

You can overcome this issue by using the following VM argument: -Djava.library.path=${Xj3D_Installation_Path}/natives/Linux/x84_64/

But this change creates a window closing problem. It is possible to use without this library path.

My MSc Thesis

It is in Turkish, here is the information for interested readers:

• T. E. Kalayci, Yapay Zeka Teknikleri Kullanan Üç Boyutlu Grafik Yazılımları için "Extensible 3D" (X3D) ile Bir Altyapı Oluşturulması ve Gerçekleştirimi, Ege üniversitesi Bilgisayar Mühendisliği Yüksek Lisans Tezi, İzmir, Türkiye, 2006.