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.

• ThreeFx: Could you show us your (pseudo)code?

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.

• Chris Hinds: That makes sense. If the never-dominated solution archive is kept external however, it seems like the algorithm will not converge on the pareto-front. It seems like you would want the archive to somehow influence the optimization process. Say the normal population is size N, the combined parent/child population is size 2N, and the archive population is size A(non-bounded). Could you combined the parent/child population with the archived population to make a set of size 2N+A and then select the best N individuals based on fitness to be passed to the next generation?
• Jerry Federspiel: It seems like it would simpler to take your current algorithm and replace the usage of the "parent" generation completely with a sample of the archive. It's worth a shot.
• Chris Hinds: That would make it more simpler, and I guess the parents would have already been compared to the archive. Thank you so much for your help!
• Jerry Federspiel: I hope I'm not leading you astray. I haven't implemented any of this stuff; I'm just thinking about it. There's one more thing that I think is worth considering.
• Jerry Federspiel: The never-dominated set's objective function values will form a possibly-bumpy surface in space. Each member of the set dominates a prism of volume under that surface. It seems as though it would be desirable for the sample to dominate as much of the volume under the surface as possible. If the surface is smooth, a random sample should work well for this. But if the surface is bumpy, you will cover volume most effectively by selecting points near the cusps/ high curvature areas of those bumps. A fast/simple way of identifying those points is an exercise left to the reader :)