Repository navigation
Releases
Releases · DmytroPalahin/aco-tsp
aco-tsp 2.0.1
The library and the tool are unchanged. This release makes every command of
the contributing guide work as it stands, on macOS included.
Added
cmake --workflow --preset coveragebuilds with instrumentation, runs the
tests, prints the coverage of each file, writes the annotated sources and
fails below 90 % of the lines (ACO_COVERAGE_MINIMUM). It works with
Clang and with GCC, and CI runs the same command.cmake --workflow --preset fuzzbuilds the harness and fuzzes the parser
for one minute, as CI does. On macOS the preset finds Homebrew's LLVM by
itself, because Apple's Clang has no libFuzzer.
Changed
- Configuring the fuzzing harness with a Clang that has no libFuzzer, such
as Apple's, stops with an explanation instead of failing at link time.
aco-tsp 2.0.0
A complete rewrite of the 2023 coursework. No source file of version 1 is
still built; the original submission is preserved under archive/.
Added
libaco, a C11 library with a documented public API (include/aco):
instances, tours, heuristics and the colony, usable independently of the
command-line tool and installable as a CMake package (aco::aco).aco-tsp, a command-line tool with two commands:solveand
generate. Every parameter is an option; nothing needs recompiling.- Three optional refinements of Ant System: elitist reinforcement
(--elitist), the pseudo-random proportional rule (--q0) and a 2-opt
local search (--local-search 2opt). - Reference solvers used as baselines: nearest neighbour, 2-opt, and an
exact Held-Karp solver for up to 20 cities (--algorithm). - A reader for a subset of TSPLIB (
EUC_2D,CEIL_2D,EXPLICITin five
layouts) next to the triangular format of the assignment, with
line-numbered error messages. - A reproducible random instance generator and three instances made with it
(data/random). - Output files: the tour in TSPLIB format (
--tour), per-iteration
statistics as CSV (--trace) and coordinates for plotting (--plot),
with gnuplot scripts for the last two. - Early stopping after a number of iterations without improvement
(--patience). - A test suite: 73 unit tests in five programs, 44 end-to-end checks of the
command-line tool, and a libFuzzer harness for the parser. - Continuous integration on Linux, macOS and Windows with GCC, Clang and
MSVC: sanitizers, Valgrind, fuzzing, clang-format, clang-tidy, CodeQL and
a coverage floor; a release workflow that publishes binaries and the
report. - A report in English (
report/report.tex) whose figures and tables are
generated byscripts/run-experiments.sh.
Changed
- The number of ants, the number of iterations,
alpha,beta,rho,Q
and the initial pheromone are run-time parameters instead of#defines. - The initial pheromone defaults to
ants * Q / L_nn, the length of a
nearest-neighbour tour setting the scale, instead of the constant 0.2. - Default parameters are now
alpha = 1,beta = 3,rho = 0.5, chosen
from the parameter study of the report. - Random numbers come from a seeded xoshiro256** generator: runs are
reproducible, and identical on every platform. - The course instances were renamed (
TSP.30is now
data/course/tsp030.txt). - Results go to standard output; files are written only on request, instead
of three fixed files in the working directory.
Fixed
- Out-of-bounds accesses: arrays of
Nelements were indexed from 1 toN. - Every matrix lived in a variable-length array on the stack, which capped
the instance size and overflowed without warning beyond it. - A roulette wheel limited to a resolution of 1 % by
rand() % 100, which
also read one element past the probability array. - The submitted program never seeded its generator: every run built the
same tours, by accident rather than by design. - A missing or malformed input file is now reported instead of being read
as garbage. - Divisions by zero when two cities coincide.
Removed
- The gnuplot pipe hard-wired to a Windows installation path. Plots are now
produced from the files written by--plotand--trace. - The 2.7 MB log of intermediate results that was committed with the code.