Siéntete en la libertad de divulgar nuestro sitio y códigos con tus amigos, apóyanos para ampliar nuestra comunidad.
Solución:
La definición básica de la frontera de Pareto es que consiste exactamente en aquellas alternativas que son no dominado por cualquier otra alternativa. Decimos que una alternativa $ A $ domina a $ B $ si $ A $ supera a $ B $ a pesar de todo de la compensación entre valor y costo, es decir, si $ A $ es ambos mejor y más barato que $ B $.
Evidentemente, tanto la alternativa mejor como la más barata pertenecen siempre a la frontera de Pareto y, de hecho, son sus puntos finales. Un algoritmo simple para encontrar las otras alternativas (si las hay) en la frontera de Pareto es clasificar primero las alternativas de acuerdo con uno de los objetivos, por ejemplo, el costo. Luego se comienza con la alternativa más barata (que, como se señaló, siempre pertenece a la frontera de Pareto) y se saltan alternativas sucesivas en orden de costo creciente hasta encontrar una con un valor más alto. Esta alternativa luego se agrega a la frontera y se reinicia la búsqueda desde ella.
Una descripción paso a paso del algoritmo, asumiendo que $ A_1, dotsc, A_n $ son las alternativas en orden creciente de costo, es la siguiente:
Algoritmo A:
- Sea $ i: = 1 $.
- Agregue $ A_i $ a la frontera de Pareto.
- Encuentre el $ j> i $ más pequeño tal que $ operatorname value (A_j)> operatorname value (A_i) $.
- Si no existe tal $ j $, deténgase. De lo contrario, deje $ i: = j $ y repita desde el paso 2.
Apéndice
En los comentarios a continuación, Nupul preguntó sobre el cálculo de la frontera de Pareto para combinaciones de alternativas.
Hay dos casos naturales e interesantes: uno en el que las combinaciones son conjuntos de alternativas (es decir, cada alternativa puede aparecer como máximo una vez en una combinación) y otro en el que son conjuntos múltiples (que pueden incluir la misma alternativa más de una vez). Abordaré ambos casos a continuación, pero permítanme primero dar un algoritmo alternativo para calcular la frontera de Pareto para soltero alternativas:
Algoritmo B:
- Dejemos que $ A_1, dotsc, A_n $ sean las alternativas ordenadas en orden de aumento de la relación costo / valor. Sea $ i: = 1 $.
- Agregue $ A_i $ a la frontera de Pareto $ P $.
- Encuentre el $ j> i $ más pequeño de modo que $ A_j $ no esté dominado por ninguna alternativa que ya esté en $ P $.
- Si no existe tal $ j $, deténgase. De lo contrario, deje $ i: = j $ y repita desde el paso 2.
En el paso 3, para comprobar si $ A_j $ está dominado por alguna alternativa en $ P $, será suficiente encontrar la alternativa más cara $ B en P $, que sigue siendo más barata que $ A_j $. (Por supuesto, por simetría, también podríamos elegir $ B $ como la alternativa menos valiosa en $ P $ que tiene un valor más alto que $ A_j $.) Si $ B $ no domina $ A_j $, tampoco puede hacerlo ninguna otra alternativa en $ A_j $. $ P $.
El algoritmo B es algo más complicado que el algoritmo A anterior (en particular, el algoritmo A se ejecuta en $ O (n) $ tiempo si las alternativas ya están ordenadas, mientras que el algoritmo B necesita $ O (n log n) $ tiempo en cualquier caso), pero resulta que generaliza mejor.
Ahora, consideremos conjuntos de cero o más alternativas. Obviamente, podríamos simplemente enumerar todos esos conjuntos y luego aplicar el algoritmo A o B, pero esto sería muy ineficiente: para $ n $ alternativas, el número de conjuntos es $ 2 ^ n $. En cambio, podemos adaptar el algoritmo $ B $ para construir las combinaciones sobre la marcha:
Algoritmo C:
- Dejemos que $ A_1, dotsc, A_n $ sean las alternativas ordenadas en orden de aumento de la relación costo / valor. Sea $ i: = 1 $. Sea $ P: = lbrace emptyset rbrace $, donde $ emptyset $ denota la combinación que no contiene alternativas.
- Para cada combinación $ C en P $, sea $ C ^ *: = C cup lbrace A_i rbrace $. Si $ C ^ * $ no está dominado por ninguna combinación que ya esté en $ P $, agregue $ C ^ * $ a $ P $.
- Si $ i = n $, deténgase. De lo contrario, incremente $ i $ en uno y repita desde el paso 2.
Nuevamente, como en el algoritmo B, no necesitamos comparar $ C ^ * $ con cada combinación en $ P $; basta con comprobar si $ C ^ * $ está dominado por la combinación más cara en $ P $ que es más barata que $ C ^ * $.
¿Qué pasa con las combinaciones de varios conjuntos? En este caso, obviamente, la frontera de Pareto $ P $ contiene infinitas combinaciones: en particular, para cualquier combinación $ C en P $, la combinación $ C + A_1 $, donde $ A_1 $ es la alternativa con el menor costo / relación de valor, también pertenece a $ P $.
Sin embargo, el nmero de veces otro La alternativa puede aparecer en una combinación no dominada debe estar acotada. (La demostración es un poco tediosa, pero se deriva de simples consideraciones geométricas). Por lo tanto, solo necesitamos considerar el conjunto finito $ P_0 $ de aquellas combinaciones en la frontera de Pareto que no no incluir la alternativa $ A_1 $; las combinaciones restantes en la frontera se obtienen agregando algún número de $ A_1 $ s a esas combinaciones.
Para combinaciones de varios conjuntos, también tenemos el siguiente lema útil:
Lema:Cualquier combinación que contenga una subcombinación dominada debe ser ella misma dominada.
En particular, esto significa que las combinaciones en $ P $ solo pueden incluir alternativas que pertenecen a $ P $. Por lo tanto, como primer paso, podemos usar el algoritmo A (o B) para calcular la frontera de Pareto para alternativas simples y descartar cualquier alternativa que no forme parte de ella.
Para que un algoritmo completo calcule $ P_0 $, la siguiente definición resulta útil:
Dfn: Se dice que una combinación $ B $ $ A $ -domina $ C $ si la combinación $ B + nA $ domina $ C $ para algún entero no negativo $ n in mathbb N $. De manera equivalente, $ B $ $ A $ -domina $ C $ iff $ operatorname costo (C)> operatorname costo (B) + n , operatorname costo (A) $, donde $ n = max left (0, left lfloor frac operatorname value (C) – operatorname value (B) operatorname value (A) right rfloor right) $ .
Usando esta definición, podemos aplicar el siguiente algoritmo:
Algoritmo D:
- Sea $ A_1, dotsc, A_n $ las alternativas (no dominadas) ordenadas en orden de aumento de la relación costo / valor. Sea $ i: = 2 $. Sea $ P_0: = lbrace emptyset rbrace $.
- Para cada combinación $ C en P_0 $, sea $ C ^ *: = C + A_i $. Si $ C ^ * $ no es $ A_1 $ -dominado por ninguna combinación que ya esté en $ P_0 $, agregue $ C ^ * $ a $ P_0 $.
- Repita desde el paso 2 hasta que no se agreguen más combinaciones a $ P_0 $.
- Si $ i = n $, deténgase. De lo contrario, incremente $ i $ en uno y repita desde el paso 2.
I pensar este algoritmo debería ser correcto, pero para ser honesto, no estoy 100% seguro de que no haya errores o lagunas en mi boceto de prueba. Así que pruébelo a fondo antes de usarlo para cualquier cosa que importe. 🙂
También creo que debería ser posible implementar el paso 2 de manera eficiente de una manera similar a los algoritmos B y C, pero la situación se complica por el hecho de que la condición de rechazo es dominación $ A_1 $ en lugar de dominación simple. Por supuesto, si $ B $ domina a $ C $, entonces trivialmente $ A $ domina a $ C $ por cualquier $ A $, por lo que al menos primero se puede hacer una comprobación rápida de un dominio simple.
Otra forma de optimizar el paso 2 es tener en cuenta que si $ C + A_i $ es $ A_1 $ -dominado por cualquier combinación en $ P_0 $, entonces también lo estará $ D + A_i $ para cualquier combinación $ D $ que incluya $ C $ como una sub-combinación. En particular, podemos saltar al paso 4 tan pronto como encontremos que $ emptyset + A_i = A_i $ en sí mismo es $ A_1 $ -dominado por alguna combinación que ya está en $ P_0 $.