Opened 10 years ago

Closed 10 years ago

#1496 closed feature request (done)

Implement generalized rank selection operator

Reported by: abeham Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.5
Component: Selection Version: 3.3.5
Keywords: Cc:

Description (last modified by abeham)

I just read about a generalized rank selection operator which allows a stepless variation of the selection pressure and that is based on the idea of rank selection.

The operator is described in Tate1995 as follows: "Instead, we selected parent strings by choosing a uniform random number between 1 and sqrt(m) (where m is the population size), then squaring it. The result was truncated and taken to be the rank of the selected parent (where string zero is the fittest string in the population). This approach can be generalized to give an arbitrary degree of preference or even varied dynamically during a given run by changing the power of the root of m during subsequent generations."

Unfortunately the authors did not name this operator, so my idea would be to call it GeneralizedRankSelection

The formula for calculating the index of the selected solution (assuming the solutions are sorted from best to worst) thus is as follows:

double randomNumber = 1 + rand() * (pow(m, 1.0 / pressure) - 1);
int selectedIndex = floor(pow(randomNumber, pressure) - 1);

The variable pressure lies in the open interval [1;infinity). If pressure equals 1, this is similar to random selection. The higher pressure becomes, the more likely better solutions are selected.

Change History (13)

comment:1 Changed 10 years ago by abeham

  • Description modified (diff)
  • Owner changed from swagner to abeham
  • Status changed from new to assigned

comment:2 Changed 10 years ago by abeham

  • Description modified (diff)

comment:3 Changed 10 years ago by abeham

  • Status changed from assigned to accepted

comment:4 Changed 10 years ago by abeham

  • Description modified (diff)

r6081

  • Implemented GeneralizedRankSelector

comment:5 Changed 10 years ago by abeham

r6082

  • Added the missing ISelector interface

comment:6 Changed 10 years ago by abeham

  • Version changed from 3.3.3 to branch

comment:7 Changed 10 years ago by abeham

  • Priority changed from medium to high

comment:8 Changed 10 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.4

r6342

  • merged to trunk

comment:9 Changed 10 years ago by mkommend

As far as I understand the source code, a little error is present if CopySelected is false. You are removing the selected scope from the remaining scope list, but you do not adapt the list of the ordered indexes => this means that you are always removing the scope with the worst quality (by reducing m) although another scope is removed.

comment:10 Changed 10 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to assigned

comment:11 Changed 10 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from assigned to reviewing

r6508:6511

  • Fixed bug when CopySelected = false

No, this didn't deserve 4 commits, but I'm getting a little slow. Time for bed.

comment:12 Changed 10 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to readytorelease

comment:13 Changed 10 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.4 to 3.3.5
Note: See TracTickets for help on using tickets.