Non-Dominated Rank based Sorting Genetic Algorithm Elitism Issue

Question

I am trying to implement a genetic algorithm for my Master's Thesis relating to satellite constellation design. I want to obtain pareto-fronts for multiple objective functions. I am writing my own algorithm based on a Non-Dominated Rank based Sorting Genetic Algorithm by Ashish Ghosh and Mrinal Kanti Das ( http://www.isical.ac.in/~ash/Mrinal-fi-08.pdf ) which is based on the NSGA-II. This algorithm uses elitism by combining the parent and child populations into a single set of individuals, size 2N, and then selecting the N best individuals to become the new child population, where N is the size of the initial population. The fitness is based on non-dominated fronts, the ranking within each front, and the spacing between individuals in that front.

The algorithm I wrote works fine until nearly every individual in the combined parent/child population is in the first non-dominated front (they are all non-dominated). When this occurs, the only thing that distinguishes fitness between every individual is the spacing between individuals. Therefore, I could have an individual that performs very well and should be passed on to the next generation, but it does not get selected for because it may be close to another individual. If I take a plot of every solution over the entire GA run, there are some solutions in the first non-dominated front at the end of the GA that are dominated by previous individuals that did not get passed on to the next generation. This could be a problem with my code, but after thinking about the way the algorithm works, I am wondering if it is a problem with the algorithm.

Thanks for your help!

Here is my Pseudo Code:

1. Initialize random population of size N.

2. Compute the fitness, f, of each individual for each objective function.

3. Classify each individual into non-dominated fronts (non-dominated solutions go into first front, then discard solutions in first front and the next set of non-dominated solutions go into second front, until entire population is sorted into sets of non-dominated fronts).

4. Assign ranks to each solution, where the rank of solution i is the number of solutions that dominate solution i.

5. Calculate the minimum distance between solution i and the next closest solution in the same front as solution i, for all i.

6. Compute the new fitness value, F, based on front, rank, and minimum distance:

   The average fitness value Favg is assigned to the first front where Favg(i) = N for all solutions i in front 1 and N = number of individuals in population

   The average fitness for each individual in current front is then adjusted based on rank where, Fadj(i) = Favg(i) – g(i) for all solutions i in current front, and where g(i) is the number of solutions in the same front as solution I having rank less than or equal to that of solution i

   The density factor is then considered where F(i) = Fadj(i) – 1/Min, where Min is the minimum distance between solution I and the next closest solution in the same front as solution i, and F(i) is the final fitness value of solution i

   If Fj is the minimum fitness of solution j and Fj < 0 then add (0 – Fj) to the fitness of all solutions to make them positive

   The Favg value is assigned for the next front, Favg(ii) = Favg(i) – e, where e is some small value thereby ensuring the fitness values of front f is less than that of any solution of front f-1

7. Next perform the genetic operations (tournament based selection, crossover, and mutation) to obtain a child population of size N.

8. Compute the fitness, f, of each individual in the child population for each objective function.

9. Combine the parent population and child population into a single set of size 2N.

10. Next repeat steps 3-6 to classify and compute the fitness F of the combined parent/child population.

11. Perform elitism by sorting the fitness values, F, of the combined population. Select the best N individuals which will become the new child population.

12. Repeat from step 3 until the maximum number of generations is reached.

Answer 1

"If I take a plot of every solution over the entire GA run, there are some solutions in the first non-dominated front at the end of the GA that are dominated by previous individuals that did not get passed on to the next generation."

To prevent this, you must have an archive of never-dominated solutions. Otherwise, a solution's descendants over several generations can make a tradeoff that favors one objective function F1 over another F2, and then they can make the reverse tradeoff in a way that gives results that are strictly inferior to their ancestor.

It's not just that comparing two generations is insufficient. There is no bounded number of ancestor generations that you can keep around for comparisons that will with certainty prevent subsequent generations from squirming around in the space of objective function values until they end up in a region dominated by an ancestor.