Oscillating Genetic Algorithm双向量优化不收敛问题技术咨询

Hey Andy, let's dig into why your Oscillating Genetic Algorithm (OGA) works for single-vector optimization but hits a wall with the two-vector problem, and walk through actionable fixes to get it converging properly.

Your core constraints—a[i] > b[i] for all i, plus 1 ≤ a[i], b[i] ≤ 15—create a coupled search space that single-vector OGA doesn't have to deal with. Poor constraint handling is almost certainly causing your convergence issues:

• Redesign encoding to enforce constraints upfront: Instead of treating a and b as separate vectors, encode each dimension as a paired value (a[i], b[i]) where you explicitly enforce b[i] ∈ [1, 14] and a[i] ∈ [b[i]+1, 15] during initialization, crossover, and mutation. This eliminates the need for post-hoc constraint repair (which wastes computation and breaks search continuity).
• Use adaptive penalty if you stick with post-hoc checks: If you can't rewrite the encoding, replace static penalties with an adaptive scheme: increase the penalty for violating a[i] ≤ b[i] as iterations progress. Early on, allow minor violations to explore the space; later, penalize heavily to push the population toward feasible solutions. Also, prioritize feasible solutions during selection—only keep infeasible individuals if the feasible pool is too small.

Standard single-vector crossover/mutation will break your a[i] > b[i] constraint. Tailor these operations to work with paired dimensions:

• Dimension-wise crossover: Instead of splitting a and b separately, cross entire (a[i], b[i]) pairs between parents. For example, for two parents P1 = [(a1_1,b1_1), (a1_2,b1_2)] and P2 = [(a2_1,b2_1), (a2_2,b2_2)], randomly pick each pair from either parent to form the offspring. This guarantees offspring stay feasible if parents are feasible.
• Paired mutation: Never mutate a[i] or b[i] in isolation. Try these two mutation strategies:
  • Option 1: Randomly choose to adjust either b[i] or a[i]. If mutating b[i], set it to a value between 1 and a[i]-1; if mutating a[i], set it to a value between b[i]+1 and 15.
  • Option 2: Adjust the gap between a[i] and b[i] (e.g., increase/decrease the gap by 1, ensuring b[i] ≥1 and a[i] ≤15) to preserve the constraint while exploring different gap sizes.

Your goal is to minimize the physical model's standard deviation to 0 (a feasible target), so make sure your fitness function guides the algorithm effectively:

• Use a fitness metric with strong differentiation: For minimization, you can use the standard deviation directly as fitness (lower = better). Alternatively, convert it to a maximization problem with 1/(1 + std_dev)—this amplifies differences when the standard deviation is close to 0, helping the algorithm distinguish near-optimal solutions.
• Add elitism: Reserve the top 5-10% of feasible individuals (by fitness) to carry over directly to the next generation. This prevents losing the best found solutions during crossover/mutation, which is critical when converging to a precise optimal point.

OGAs rely on oscillating parameters (like mutation/crossover rates) to balance exploration and exploitation. For coupled vectors, adjust this oscillation to match the search space:

• Dynamic oscillation amplitude: Early in iterations, use large oscillations (high mutation rate, low crossover rate) to explore the feasible space widely. As the population converges, shrink the oscillation amplitude (lower mutation, higher crossover) to refine solutions within the feasible region.
• Link oscillation to constraint feasibility: If the feasible solution ratio drops below a threshold (e.g., 30%), crank up mutation rate oscillation to help the population escape infeasible regions. When feasible solutions are abundant, dial back oscillation to focus on convergence.

• Visualize population distribution: After each iteration, plot scatter points of (b[i], a[i]) for all dimensions and individuals. This will show if most of your population stays within the a[i] > b[i] region and if it's clustering toward the optimal solution.
• Test with small dimensions first: Start with 2-3 dimensional vectors instead of your full problem size. If the algorithm converges here, scale up gradually—this helps isolate whether the issue is with high dimensionality or constraint handling.
• Single-vector baseline test: Fix one vector (e.g., optimize b first to its optimal value, then hold it constant while optimizing a). If this works, the problem is definitely in how you're coupling the two vectors in the GA operations.

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