Reward-based selection

Reward-based selection can be used within Multi-armed bandit framework for Multi-objective optimization to obtain a better approximation of the Pareto front. [1]

The newborn ${\displaystyle a'^{(g+1)}}$ and its parents receive a reward ${\displaystyle r^{(g)}}$, if ${\displaystyle a'^{(g+1)}}$ was selected for new population ${\displaystyle Q^{(g+1)}}$, otherwise the reward is zero. Several reward definitions are possible:

• 1. ${\displaystyle r^{(g)}=1}$, if the newborn individual ${\displaystyle a'^{(g+1)}}$ was selected for new population ${\displaystyle Q^{(g+1)}}$.
• 2. ${\displaystyle r^{(g)}=1-{\frac {rank(a'^{(g+1)})}{\mu }}{\mbox{ if }}a'^{(g+1)}\in Q^{(g+1)}}$, where ${\displaystyle rank(a'^{(g+1)})}$ is the rank of newly inserted individual in the population of ${\displaystyle \mu }$ individuals. Rank can be computed using a well-known non-dominated sorting procedure.[2]
• 3. ${\displaystyle r^{(g)}=\sum _{a\in Q^{(g+1)}}\Delta {H}(a,Q^{(g+1)})-\sum _{a\in Q^{(g)}}\Delta {H}(a,Q^{(g)})}$, where ${\displaystyle \Delta {H}(a,Q^{(g)})}$ is the hypervolume indicator contribution of the individual ${\displaystyle a}$ to the population ${\displaystyle Q^{(g)}}$. The reward ${\displaystyle r^{(g)}>0}$ 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 ${\displaystyle k}$-th dominated Pareto front: ${\displaystyle 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)}$

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

• Fitness proportionate selection
• Selection (genetic algorithm)
• Stochastic universal sampling
• Tournament selection