为何并行化TSP遗传算法优化函数后运行更慢？求优化建议

Hey there! Let's dig into why your parallel TSP GA implementation is slower than expected—there are a few key issues in your code that are killing the parallel speedup, and I'll walk you through fixing them step by step.

1. You're Running Threads Sequentially (Not Actually Parallel!) #

The biggest problem here is that you're calling join() immediately after starting each thread:

for (int j = 0; j < N_THREADS; j++) {
    myThreads[j]= new addInP();
    myThreads[j].start();
    myThreads[j].join(); // Waits for this thread to finish before starting the next!
}

This means you're starting one thread, waiting for it to complete all its work, then starting the next. You're not running anything in parallel—you just added the overhead of thread creation/destruction on top of your original serial code.

Fix: Start all threads first, then call join() on all of them after they're all running. Like this:

// Start all threads first
for (int j = 0; j < N_THREADS; j++) {
    myThreads[j] = new addInP();
    myThreads[j].start();
}
// Now wait for all to finish
for (int j = 0; j < N_THREADS; j++) {
    myThreads[j].join();
}

2. Heavy Contention on Shared Variables #

Your addInP class uses static shared variables (currentGenerationSize, generation) with synchronized methods, which creates a lot of lock contention. Every time a thread checks or updates currentGenerationSize, or adds to generation, it has to wait for the lock—this bottleneck negates any parallel gains.

Specific Problems: #

• currentGenerationSize uses synchronized methods, but an AtomicInteger would be more efficient for atomic increments/checks without explicit locks.
• generation is a shared ArrayList, which isn't thread-safe. Calling addAll() from multiple threads will cause race conditions (missing elements or ConcurrentModificationException), and adding synchronization around it would just create another bottleneck.

Fix: Avoid shared mutable state per generation. Instead, have each thread generate its own subset of the population, then combine all subsets at the end. This eliminates contention entirely.

Rewrite your task class to handle independent work:

// Use Callable instead of Thread to return results directly
class AddInTask implements Callable<List<SalesmanGenome>> {
    private final List<SalesmanGenome> population;
    private final int targetCount;
    // Pass all constants via constructor (no static shared state!)
    private final float mutationRate;
    private final int numberOfCities;
    private final int startingCity;
    private final int[][] travelPrices;
    private final Random random = new Random(Thread.currentThread().getId() + System.nanoTime());

    public AddInTask(List<SalesmanGenome> population, int targetCount, float mutationRate, int numberOfCities, int startingCity, int[][] travelPrices) {
        this.population = population;
        this.targetCount = targetCount;
        this.mutationRate = mutationRate;
        this.numberOfCities = numberOfCities;
        this.startingCity = startingCity;
        this.travelPrices = travelPrices;
    }

    @Override
    public List<SalesmanGenome> call() {
        List<SalesmanGenome> threadLocalGeneration = new ArrayList<>();
        while (threadLocalGeneration.size() < targetCount) {
            List<SalesmanGenome> parents = pickNRandomElements(population, 2, random);
            List<SalesmanGenome> children = crossover(parents);
            children.set(0, mutate(children.get(0), mutationRate, numberOfCities, startingCity, travelPrices, random));
            children.set(1, mutate(children.get(1), mutationRate, numberOfCities, startingCity, travelPrices, random));
            threadLocalGeneration.addAll(children);
        }
        // Trim if we overshoot (for odd target counts)
        return threadLocalGeneration.subList(0, targetCount);
    }
}

Then update your optimizeP method to use a thread pool for efficient thread reuse:

public SalesmanGenome optimizeP() throws InterruptedException, ExecutionException {
    // Reuse threads with a pool instead of creating new ones each iteration
    ExecutorService executor = Executors.newFixedThreadPool(N_THREADS);
    List<SalesmanGenome> population = initialPopulation();
    SalesmanGenome globalBestGenome = population.get(0);

    for (int i = 0; i < maxIterations; i++) {
        List<SalesmanGenome> selectedPopulation = selection(population);
        int individualsPerThread = generationSize / N_THREADS;
        int remainingIndividuals = generationSize % N_THREADS;

        List<Callable<List<SalesmanGenome>>> tasks = new ArrayList<>();
        // Assign fixed workloads to each thread
        for (int j = 0; j < N_THREADS; j++) {
            int targetCount = individualsPerThread;
            if (j == N_THREADS - 1) {
                targetCount += remainingIndividuals; // Handle leftover individuals
            }
            tasks.add(new AddInTask(selectedPopulation, targetCount, mutationRate, numberOfCities, startingCity, travelPrices));
        }

        // Run all tasks and collect results
        List<Future<List<SalesmanGenome>>> futures = executor.invokeAll(tasks);
        population = new ArrayList<>();
        for (Future<List<SalesmanGenome>> future : futures) {
            population.addAll(future.get());
        }

        // Update global best genome
        globalBestGenome = Collections.min(population);
        if (globalBestGenome.getFitness() < targetFitness) {
            break;
        }
    }

    executor.shutdown(); // Clean up the thread pool
    return globalBestGenome;
}

3. Thread-Safe Random Number Generation #

If your pickNRandomElements or mutate methods use a shared Random instance, you'll get contention because Random's methods are synchronized.

Fix: Use a thread-local Random instance (like in the AddInTask example above) to avoid this bottleneck.

4. Avoid Over-Threading #

Make sure N_THREADS matches your CPU core count (or a small multiple of it). Using too many threads will cause excessive context-switching, which slows down execution.

By fixing these issues—actually running threads in parallel, eliminating shared state contention, reusing threads with a pool, and ensuring thread-safe randomness—you should see a significant speedup in your parallel GA implementation.

内容的提问来源于stack exchange，提问作者annalisa peperon