class MOEAD:
def __init__(
self,
problem,
n_dim,
n_population,
n_neighbors,
bounds,
n_generations,
crossover_probability,
mutation_probability,
crossover_distribution_index,
mutation_distribution_index
):
self.problem = problem
self.n_dim = n_dim
self.n_population = n_population
self.n_neighbors = n_neighbors
self.bounds = bounds
self.n_generations = n_generations
self.crossover_probability = crossover_probability
self.mutation_probability = mutation_probability
self.crossover_distribution_index = crossover_distribution_index
self.mutation_distribution_index = mutation_distribution_index
self.population = None
self.weights = []
self.neighbors = None
self.EP = []
self.history = []
def initialize(self):
self.population = np.random.uniform(self.bounds[0], self.bounds[1], (self.n_population, self.n_dim))
self.weights = np.array([np.array([i / (self.n_population - 1), 1 - i / (self.n_population - 1)])
for i in range(self.n_population)])
distances = np.linalg.norm(self.weights[:, np.newaxis, :] - self.weights, axis=2)
self.neighbors = np.argsort(distances, axis=1)[:,1:self.n_neighbors+1]
def evolve(self):
for gen in range(self.n_generations):
for i in range(self.n_population):
parents = np.random.choice(self.neighbors[i], 2, replace=False)
child1, child2 = self.sbx_crossover(self.population[parents[0]], self.population[parents[1]])
child1 = self.polynomial_mutation(child1)
child2 = self.polynomial_mutation(child2)
self.update_population_and_EP(child1, i)
self.update_population_and_EP(child2, i)
self.history.append(self.EP.copy())
def sbx_crossover(self, parent1, parent2):
eta = self.crossover_distribution_index
rand = np.random.random(size = parent1.shape)
beta = np.empty_like(rand)
beta[rand <= 0.5] = (2 * rand[rand <= 0.5]) ** (1 / (eta + 1))
beta[rand > 0.5] = (2 * (1 - rand[rand > 0.5])) ** (-1 / (eta + 1))
child1 = 0.5 * ((1 + beta) * parent1 + (1 - beta) * parent2)
child2 = 0.5 * ((1 - beta) * parent1 + (1 + beta) * parent2)
child1 = np.clip(child1, self.bounds[0], self.bounds[1])
child2 = np.clip(child2, self.bounds[0], self.bounds[1])
do_crossover = np.random.rand() < self.crossover_probability
return (child1, child2) if do_crossover else (parent1, parent2)
def polynomial_mutation(self, individual):
eta = self.mutation_distribution_index
for i in range(self.n_dim):
if np.random.rand() < self.mutation_probability:
delta = np.random.rand()
if delta < 0.5:
multiplier = (2 * delta)**(1 / (eta + 1)) - 1
else:
multiplier = 1 - (2 * (1 - delta))**(1 / (eta + 1))
individual[i] += multiplier * (self.bounds[1] - self.bounds[0])
individual = np.clip(individual, self.bounds[0], self.bounds[1])
return individual
def update_population_and_EP(self, child, i):
child_obj = self.problem.evaluate(child)
for j in self.neighbors[i]:
weighted_sum_child = np.dot(self.weights[j], child_obj)
weighted_sum_current = np.dot(self.weights[j], self.problem.evaluate(self.population[j]))
if weighted_sum_child < weighted_sum_current:
self.population[j] = child
# Cập nhật quần thể mở rộng (EP)
is_dominated = False
for other_obj in self.EP:
if np.all(other_obj <= child_obj) and np.any(other_obj < child_obj):
is_dominated = True
break
if not is_dominated:
self.EP = [other_obj for other_obj in self.EP if not (np.all(child_obj <= other_obj) and np.any(child_obj < other_obj))]
self.EP.append(child_obj)
def run(self):
self.initialize()
self.evolve()
return self.EP, self.history
I've been working with the MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) algorithm, and I've encountered an issue. Regardless of the parameter settings I've tried, such as changing the weighting scheme, population size, or the number of neighboring subproblems, the algorithm consistently returns only a single solution instead of the expected Pareto frontier.
I've thoroughly reviewed my implementation and tried various combinations of parameters, but I can't seem to get the algorithm to produce the desired Pareto front. I suspect there might be a bug or an issue in my code, but I'm having trouble pinpointing it.
Could anyone provide some guidance on how to debug this issue or offer insights into common pitfalls when using MOEA/D? I would greatly appreciate any assistance or suggestions.
Initialization:
Create Initial Population: Generate a population of N random solutions.
Assign Weights: Assign a set of $$N$$ weight vectors corresponding to each individual $$\left{\left(\frac{i}{N-1},1-\frac{i}{N-1}\right):i=\overline{0,N-1}\right}$$.
Set Neighborhood Parameters: Determine the number of neighbors $T$ for each weight vector $i$, where the neighbors of vector $i$ are denoted by set $B(i)$ and consist of $T$ vectors with the smallest Euclidean distance to it.
Initialize the External Population: Initialize the external population of Pareto solutions, $EP = \emptyset$. Evaluate the Population:
Compute the objective function values for each solution in the population.
Main Loop:
In each generation, iterate over each individual. For each individual $i\in{1,2,\ldots,N}$, perform the following steps:
- Randomly select 2 individuals $x^k$ and $x^l$ from $B(i)$ and apply crossover (SBX) and mutation (Polynomial) operations to create an individual $x^*$.
- For each $j \in B(i)$, if the total weight (according to vector $j$) of $x^$ is less than the total weight of $x^j$, replace $x^j$ with $x^$ and compute the objective function values at $x^*$.
- Remove all solutions in $EP$ that are dominated by $x^*$.
- Add $x^$ to $EP$ if there are no solutions in $EP$ that dominate $x^$.
Continue iterating through generations until a stopping criterion is met, then return the set of solutions in $EP$.
Thank you in advance for your help.
Regardless of the parameter settings I've tried, such as changing the weighting scheme, population size, or the number of neighboring subproblems, the algorithm consistently returns only a single solution instead of the expected Pareto frontier.