View source for Reward-based selection

'''Reward-based selection''' is a technique used in [[Evolutionary algorithm|evolutionary algorithm]]s for selecting potentially useful solutions for recombination. 
The probability of being selected for an individual is proportional to the cumulative reward obtained by the individual. The cumulative reward can be computed as a sum of the individual reward and the reward inherited from parents.

==Description==
Reward-based selection can be used within [[Multi-armed bandit]] framework for [[Multi-objective optimization]] to obtain a better approximation of the [[Pareto efficiency|Pareto front]].
<ref>{{cite conference
 |first       = I.
 |last        = Loshchilov
 |author2     = M. Schoenauer
 |author3     = M. Sebag
 |title       = Not all parents are equal for MO-CMA-ES
 |book-title   = Evolutionary Multi-Criterion Optimization 2011 (EMO 2011)
 |pages       = 31–45
 |publisher   = Springer Verlag, LNCS 6576
 |date        = 2011
 |url         = http://www.lri.fr/~ilya/publications/EMO2011_MOCMAselection.pdf
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20120604215318/http://www.lri.fr/~ilya/publications/EMO2011_MOCMAselection.pdf
 |archive-date = 2012-06-04
}}</ref>
 
The newborn <math>a'^{(g+1)}</math> and its parents receive a reward <math>r^{(g)}</math>, if <math>a'^{(g+1)}</math> was selected for new population <math>Q^{(g+1)}</math>, otherwise the reward is zero. 
Several reward definitions are possible:

*1. <math> r^{(g)}=1</math>, if the newborn individual <math>a'^{(g+1)}</math> was selected for new population <math>Q^{(g+1)}</math>.
*2. <math> r^{(g)} = 1 - \frac{rank(a'^{(g+1)})}{\mu} \mbox{ if } a'^{(g+1)} \in Q^{(g+1)} </math>, where <math>rank(a'^{(g+1)})</math> is the rank of newly inserted individual in the population of <math>\mu</math> individuals. Rank can be computed using a well-known non-dominated sorting procedure.<ref>{{cite journal|last1=Deb|first1=K.|last2=Pratap|first2=A.|last3=Agarwal|first3=S.|last4=Meyarivan|first4=T.|title=A fast and elitist multi-objective genetic algorithm: NSGA-II|journal=IEEE Transactions on Evolutionary Computation|volume=6|issue=2|pages=182–197|year=2002|doi=10.1109/4235.996017|citeseerx=10.1.1.17.7771}}</ref>
*3. <math> r^{(g)} = \sum_{a\in Q^{(g+1)}} \Delta{H}(a,Q^{(g+1)}) - \sum_{a\in Q^{(g)}} \Delta{H}(a,Q^{(g)})</math>, where <math>\Delta{H}(a,Q^{(g)})</math> is the hypervolume indicator contribution of the individual <math>a</math> to the population <math>Q^{(g)}</math>. The reward <math>r^{(g)}>0</math> if the newly inserted individual improves the quality of the population, which is measured as its hypervolume contribution in the objective space.
*4. A relaxation of the above reward, involving a rank-based penalization for points for <math>k</math>-th dominated Pareto front: <math> r^{(g)} =  \frac{1}{2^{k-1}} \left( \sum_{ndom_k(Q^{(g+1)})} \Delta{H}(a,ndom_k(Q^{(g+1)})) - \sum_{ndom_k(Q^{(g)})}  \Delta{H}(a,ndom_k(Q^{(g)})) \right)</math>

Reward-based selection can quickly identify the most fruitful directions of search by maximizing the cumulative reward of individuals.

==See also==
*[[Fitness proportionate selection]]
*[[Selection (genetic algorithm)]]
*[[Stochastic universal sampling]]
*[[Tournament selection]]

== References ==
<!--- See Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->
{{Reflist}}

{{DEFAULTSORT:Rewardbased Selection}}
<!--- Categories --->
[[Category:Evolutionary algorithms]]
[[Category:Genetic algorithms]]

{{Sourceattribution|Reward-based selection}}