Mochila problema con la incertidumbre de los beneficios

Question

Estoy tratando de encontrar la estrategia óptima para un juego donde el objetivo es recoger una serie de elementos donde el beneficio es incierto, pero los pesos establecidos. Cada ronda de recolección de un punto específico en el tiempo, y cada ronda es parcialmente independiente del pasado (creo que los juegos de deportes). Esto es, básicamente, una versión de la mochila problema. (véase el Problema de la Mochila)

Aquí está el problema :
Maximizar: $$\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij} +\sum _{j=1}^{\left | G_{s} \right |}p_{sj}x_{sj}$$ Sujeto a: $$ \begin{align} (\sum _{i=1}^{n}\sum _{j=1}^{\left | G_{i} \right |}w_{ij}x_{ij} +\sum _{j=1}^{\left | G_{s} \right |}w_{sj}x_{sj})&\leq c \\ \sum _{j=1}^{\left | G_{i} \right |}x_{ij} &= 1 \\ \sum _{j=1}^{\left | G_{s} \right |}x_{sj} &= k \\ x_{ij} \in \{0,1\}\\ x_{sj} \in \{0,1\} \end{align} $$ Notación:
N el número de elementos
n el número de grupos
c la capacidad de una sola mochila
G = {$G_{1},...,G_{n}$} el conjunto de los grupos de
${\left | G_{i} \right |}$ el número de elementos en el grupo $G_{i}$
${\left | G_{s} \right |}$ el número de elementos en el grupo $G_{s}$ (grupo especial)
$p_{ij}$ la ganancia de punto j de grupo $G_{i}$
$w_{ij}$ el peso del elemento j de grupo $G_{i}$
$p_{sj}$ la ganancia de punto j de grupo $G_{s}$
$w_{sj}$ el peso del elemento j de grupo $G_{s}$
k restricción de grupo $G_{s}$

Así, por ejemplo, digamos que usted tiene 100 elementos por grupo, donde cada elemento tiene un beneficio y un peso. En este caso particular, el beneficio es incierto y por lo tanto debe utilizar la regresión para venir para arriba con una estimación razonable.

Hasta el momento, estoy usando regresión lineal emparejado con un k-NN algoritmo para predecir la ganancia de cada elemento basado en observaciones pasadas. Yo también uso un árbol de decisión alumno para una clasificación entre los artículos que tienen un positivo de ganancias o beneficios negativos (de nuevo, con observaciones anteriores).

Voy a usar GLPK para resolver el problema de la mochila. De hecho, ya he codificado el módulo y su listo para ir. El problema es con la incertidumbre de los beneficios.

Estoy teniendo un momento difícil conceptualizar la incertidumbre y el riesgo. Es allí una manera de separar el elemento opciones de acuerdo al riesgo? Tal vez puedo mirar el histórico de la variación en la ganancia de valor de cada elemento? ¿Hay algún método en particular que sería útil aquí? (Algo parecido a Monte Carlo, etc?)

Answer 1

En el caso de un estocásticos de optimización como esta, usted realmente debe tener una función objetivo que los pesos de riesgo. Idealmente, esto sería una función de utilidad, que puede ser convertido a una utilidad esperada cuando hay una distribución de probabilidad sobre la recompensa y la utiliza en su lugar. (Nota: esto supone que las utilidades de los elementos son independientes el uno del otro, y de si los otros elementos que se incluyen en su selección final o no).

Si usted simplemente reemplazar:

Maximizar: $\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}$

con la maximización de la rentabilidad esperada:

Maximizar: $\text{E}\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij} = \sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}\text{E}(p_{ij})x_{ij}$

obtendrás una función objetivo donde es maximizar el retorno esperado, dadas las limitaciones. Esto no requiere nada más que la sustitución de $\text{E}p_{ij}$ $p_{ij}$ en su función objetivo y, a partir de una estimación de la perspectiva, todo lo que tendría que hacer es sustituir los valores de predicción de la $p_{ij}$ en la función objetivo. Agrupación por riesgo (sin embargo medido) es irrelevante con este objetivo, a menos que por alguna razón se mejora la estimación de la $p_{ij}$.

Si, por otro lado, puede crear una función de utilidad $U(p)$, el máximo esperado de la utilidad de la función se convierte en:

Maximizar: $\text{E}U(\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}) = \sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}\text{E}U(p_{ij})x_{ij}$

(suponiendo que, una vez más, una función de utilidad separable) y el objetivo de su análisis estadístico es encontrar una distribución de probabilidad (por ejemplo, una posterior distribución de probabilidad) de la $p_{ij}$ que puede utilizar para formar $\text{E}U(p_ij)$. (Véase, por ejemplo, Salvaje, DeGroot, o Raiffa y Schlaifer en los vínculos muy fuertes entre la estadística Bayesiana y teoría de la utilidad.) Entonces sustituto $\text{E}U(p_{ij})$ en su función objetivo y resolver como si se tratara de un problema determinista - que es, puesto que la maximización de un valor esperado y todo el azar se encuentra oculto en el interior del "valor esperado".