无染色体满足约束时genalg算法未返回全0染色体的问题咨询

Great question! Let's dig into why your genetic algorithm is returning chromosomes with 1s even when all valid solutions should be all 0s, and break down how the genalg package handles these scenarios.

The Root Cause: Equal Fitness Values #

The core issue lies in your fitness function design. Let's break it down:

• An all-0 chromosome (the only valid solution here) returns 0 (since x %*% survivalpoints = 0, so -0 = 0).
• Any chromosome with a 1 will exceed the weight limit, so it also returns 0.

Since every possible solution has the exact same fitness value, the rbga.bin algorithm can't distinguish between good and bad solutions. It falls back to random choices during selection, crossover, and mutation—so chromosomes with 1s stick around instead of being filtered out.

How genalg's Mechanics Amplify This #

Let's walk through the key behaviors of genalg's binary genetic algorithm that contribute to this:

• Random Initialization: By default, rbga.bin generates a random initial population. Some chromosomes will start with 1s right away.
• Roulette-Wheel Selection: The algorithm uses roulette-wheel selection to pick parents for reproduction. When all fitness values are equal, every chromosome has an equal chance of being chosen—so 1-containing chromosomes aren't eliminated.
• Mutation: With a mutationChance = 0.01, even if an all-0 chromosome exists in the population, there's a chance bits flip to 1 in later iterations. Since these mutated chromosomes still have a fitness of 0, they aren't penalized and stay in the population.
• Elitism: The default elitism value is 2, which keeps the top 2 fitness-performing individuals each generation. But when all fitness is equal, this just picks 2 random individuals—so 1-containing chromosomes can still be carried over to the next iteration.

To get the algorithm to prioritize the all-0 solution, you need to give invalid solutions a severely lower fitness value than the valid all-0 solution. Here's how to modify your evalFunc:

evalFunc <- function(x) {
  current_solution_survivalpoints <- x %*% dataset$survivalpoints;
  current_solution_weight <- x %*% dataset$weight;
  if (current_solution_weight > weightlimit){
    return(-1000000); # Assign a drastically low fitness to invalid solutions
  } else{
    return(-current_solution_survivalpoints);
  }
}

Now, the all-0 solution will have a fitness of 0, while any chromosome with 1s will have a fitness of -1e6. Since rbga.bin maximizes fitness, it will strongly favor the all-0 solution in every iteration.

• Fitness Goal: rbga.bin is designed to maximize the fitness function output. If you need to minimize a value (like survival points here), returning the negative is correct—but you must ensure invalid solutions are punished with worse (lower) fitness.
• Randomness: Genetic algorithms rely on randomness for initialization, selection, and mutation. Without clear fitness differences, this randomness leads to unpredictable results.
• Constraints Handling: For constrained problems (like your weight limit), explicitly penalize invalid solutions in the fitness function—don't just set their fitness equal to valid suboptimal solutions.

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