Selección basada en recompensas

La selección basada en recompensas es una técnica utilizada en algoritmos evolutivos para seleccionar soluciones potencialmente útiles para la recombinación. La probabilidad de ser seleccionado para un individuo es proporcional a la recompensa acumulada obtenida por el individuo. La recompensa acumulada se puede calcular como una suma de la recompensa individual y la recompensa heredada de los padres.

Descripción

La selección basada en recompensas se puede utilizar dentro del marco de Multi-armed Bandit para la optimización de múltiples objetivos para obtener una mejor aproximación del frente de Pareto . ^[1]

El recién nacido y sus padres reciben una recompensa si fue seleccionado para la nueva población ; de lo contrario, la recompensa es cero. Existen varias definiciones de recompensa posibles: ${\displaystyle a'^{(g+1)}}$ ${\displaystyle r^{(g)}}$ ${\displaystyle a'^{(g+1)}}$ ${\displaystyle Q^{(g+1)}}$

• 1. , si el individuo recién nacido fue seleccionado para la nueva población . ${\displaystyle r^{(g)}=1}$ ${\displaystyle a'^{(g+1)}}$ ${\displaystyle Q^{(g+1)}}$
• 2. , donde es el rango del individuo recién insertado en la población de individuos. El rango se puede calcular utilizando un procedimiento de clasificación no dominado bien conocido. ^[2] ${\displaystyle r^{(g)}=1-{\frac {rank(a'^{(g+1)})}{\mu }}{\mbox{ if }}a'^{(g+1)}\in Q^{(g+1)}}$ ${\displaystyle rank(a'^{(g+1)})}$ ${\displaystyle \mu }$
• 3. , donde es la contribución del indicador de hipervolumen del individuo a la población . La recompensa si el individuo recién insertado mejora la calidad de la población, que se mide como su contribución de hipervolumen en el espacio objetivo. ${\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)})}$ ${\displaystyle \Delta {H}(a,Q^{(g)})}$ ${\displaystyle a}$ ${\displaystyle Q^{(g)}}$ ${\displaystyle r^{(g)}>0}$
• 4. Una relajación de la recompensa anterior, que implica una penalización basada en el rango de puntos para el frente de Pareto dominado -ésimo: ${\displaystyle k}$ ${\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)}$

La selección basada en recompensas puede identificar rápidamente las direcciones de búsqueda más fructíferas al maximizar la recompensa acumulada de los individuos.

Véase también

• Selección proporcional de fitness
• Selección (algoritmo genético)
• Muestreo universal estocástico
• Selección de torneos

Referencias

1. Loshchilov, I.; M. Schoenauer; M. Sebag (2011). "No todos los padres son iguales para MO-CMA-ES" (PDF) . Optimización multicriterio evolutiva 2011 (EMO 2011) . Springer Verlag, LNCS 6576. pp. 31–45. Archivado desde el original (PDF) el 4 de junio de 2012.
2. Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). "Un algoritmo genético multiobjetivo rápido y elitista: NSGA-II". IEEE Transactions on Evolutionary Computation . 6 (2): 182–197. CiteSeerX 10.1.1.17.7771 . doi :10.1109/4235.996017.