Function PGASortND_NSquare

Function Documentation

unsigned int PGASortND_NSquare(PGAContext *ctx, PGAIndividual **start, size_t n, int goal)

Perform nondominated sorting with O(n**2) algorithm.

Description

Perform dominance computation known as nondominated sorting or ranking. This is the old algorithm which is O(n**2). First compute a dominance matrix of N x N bits. The rows are the dominated-by relation. We loop over all n^2 pairs of individuals and fill the matrix. Init all ranks with -1. Then starting with rank0:

  • Get all rows of the matrix which are 0 and where the individual has no rank yet: These are the currently non-dominated individuals, assign the current rank

  • Loop over all individuals with the current rank and remove their bits from the dominance matrix

  • Increment the rank counter

  • Stop early when goal is reached

Parameters:

  • ctx – context variable

  • start – pointer to individuals

  • n – number of individuals

  • goal – number of individuals needed in next generation

Returns:

Maximum rank given or UINT_MAX if goal was reached exactly (in which case no crowding is necessary)