title: Obvious speedup to NSGA-II?
body: <p><a href="http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf" rel="nofollow">Nondominated sorting genetic algorithm (NSGA) II</a> has become very well known for multiobjective optimization.  I'm starting to implement this, starting with the "fast-non-dominated-sort" function, i.e., not touching the anticrowding schemes just yet.  The pseudocode is show at the bottom of the 3rd page of the above NSGA II link.</p>
  
  <p>Upon studying it, it seems to me (most likely naively!) that a simple speedup can be tweaked into the pseudocode.  Specifically, the testing of whether solution $q$ is nondominated can be brought outside of a nested loop.  More specifically, there are two nested loops, one to iterate $p$ over the solutions of the current nondominance front and another to iterate over each solution $q$ dominated by $p$.  The test of whether $q$ is nondominated for the <em>next</em> front is $n_q = 0$, where $n_q$ is the number of solutions that dominate solution $q$.  If we bring this outside the two nested loops, the test doesn't have to happen as often.  Yet it seems that $n_q$ should still have the correct value when both loops are done.  You would still have to iterate over all $q$'s to test them, but you wouldn't be visiting each one more than once.</p>
  
  <p>Am I missing some obvious reason why the domination count is inside the nested loops?</p>