jSO Algorithm Fix Validation

This project validates the fix for a bug in the Boost C++ library's implementation of the jSO algorithm. The experiment compares the original implementation against the corrected version to demonstrate the impact of properly maintaining population diversity.

Background

While reviewing the jSO algorithm implementation in Boost's math/optimization library, I discovered that the external archive was erroneously storing successful trials, whereas according to the original paper, it should store eliminated individuals. This led to a Pull Request (#1263) with the following description:

Fix: Corrected the external archive error in the jSO algorithm #1263

Problem Description: In the jSO algorithm, the external archive was storing successful trials, but according to the original paper, it should store eliminated individuals. The external archive is meant to maintain diversity, and storing successful trials fails to achieve this effect.

Solution: Modified the jSO algorithm's external archive update to store eliminated individuals.

This project was created to validate the fix by comparing the optimization performance of both implementations, and the experimental results can be found here.

Experimental Setup

Optimization Problem

• Objective Function: Rosenbrock function (a classic non-convex optimization test problem)

  double rosenbrock(std::vector<double> const & x) {
     double result = 0;
     for (size_t i = 0; i < x.size() - 1; ++i) {
         double tmp = x[i+1] - x[i]*x[i];
         result += 100*tmp*tmp + (1-x[i])*(1-x[i]); 
     }
     return result;
  }

• Search Space: [0, 100]^dimension
• Dimensions Tested: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
• Number of Runs: 10 runs per dimension to account for the stochastic nature of the algorithms

Algorithms Compared

1. jSO: Original implementation with incorrect external archive management
2. jSO_FIX: Corrected implementation that properly stores eliminated individuals

Environment

• Operating System: Ubuntu 22.04.5 LTS (Jammy Jellyfish)
• C++ Compiler: GCC 13.1.0
• C++ Standard: C++17

Implementation Details

For each algorithm and dimension size, the experiment:

• Runs multiple optimizations with different random seeds
• Records convergence data (best fitness value) at each generation
• Computes statistical measures (mean, min, max) across all runs
• Saves results to TXT files in the format: generation, jso_mean, jso_min, jso_max, jso_fix_mean, jso_fix_min, jso_fix_max
• Generates visual comparisons using matplotlib

Key Hypothesis

The key question this experiment addresses is: "Does storing eliminated individuals (rather than successful trials) in the external archive increase population diversity and help avoid premature convergence?"

By correctly maintaining population diversity through proper external archive management, the jSO_FIX algorithm should demonstrate improved optimization performance, particularly in high-dimensional problems.

Project Structure

• comparison.cpp: Main C++ implementation with both algorithms
• optimization: Contains the jSO and jSO_FIX algorithm implementations
• convergence_plot.py: Python script to generate visualization of results
• data: Directory where result TXT files are stored
• plots: Directory where generated plots are saved
• CMakeLists.txt: CMake build configuration

How to Run

1. Ensure data directory exists:

   mkdir -p data plots

2. Build the C++ optimization code:

   mkdir -p build && cd build
   cmake .. && make
   cd ..
   ./build/optimization_comparison

3. Generate plots:

   python3 convergence_plot.py

Dependencies

• C++17 compliant compiler
• CMake (3.10+)
• Python 3 with pandas, matplotlib, and numpy packages

License

This project is available under the Boost Software License, Version 1.0.