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 $B$ si $A$ supera a $B$ independientemente de la compensación entre el valor y el coste, es decir, si $A$ es ambos mejor y más barato que $B$ .
Evidentemente, tanto la mejor alternativa como la más barata pertenecen siempre a la frontera de Pareto y, de hecho, son sus puntos finales. Un algoritmo sencillo para encontrar las demás alternativas (si las hay) en la frontera de Pareto consiste en ordenar primero las alternativas según uno de los objetivos, por ejemplo, el coste. A continuación, se comienza con la alternativa más barata (que, como se ha señalado, siempre pertenece a la frontera de Pareto) y se saltan las alternativas sucesivas en orden de coste creciente hasta encontrar una con un valor más alto. Esta alternativa se añade entonces a la frontera y se reinicia la búsqueda a partir de ella.
Una descripción paso a paso del algoritmo, suponiendo que $A_1, \dotsc, A_n$ son las alternativas en orden creciente de coste, es así:
Algoritmo A :
- Dejemos que $i := 1$ .
- Añadir $A_i$ a la frontera de Pareto.
- Encontrar el más pequeño $j>i$ tal que $\operatorname{value}(A_j) > \operatorname{value}(A_i)$ .
- Si no hay tal $j$ existe, se detiene. De lo contrario, deje que $i := j$ y repetir desde el paso 2.
Anexo
En los comentarios de abajo, 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 multisets (que puede incluir la misma alternativa más de una vez). A continuación, trataré ambos casos, pero permítanme primero dar un algoritmo alternativo para calcular la frontera de Pareto para solo alternativas:
Algoritmo B :
- Dejemos que $A_1, \dotsc, A_n$ sean las alternativas ordenadas según su relación coste/valor. Sea $i := 1$ .
- Añadir $A_i$ a la frontera de Pareto $P$ .
- Encontrar el más pequeño $j>i$ tal que $A_j$ no está dominada por ninguna alternativa ya en $P$ .
- Si no hay tal $j$ existe, se detiene. De lo contrario, deje que $i := j$ y repetir desde el paso 2.
En el paso 3, para comprobar si $A_j$ está dominada por cualquier alternativa en $P$ bastará con encontrar la alternativa más cara $B \in P$ que sigue siendo más barato que $A_j$ . (Por supuesto, por simetría, también podríamos elegir $B$ como la alternativa menos valiosa en $P$ que tiene mayor valor que $A_j$ .) Si $B$ no domina $A_j$ tampoco puede hacerlo ninguna otra alternativa en $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 se generaliza mejor.
Ahora, consideremos conjuntos de cero o más alternativas. Obviamente, podríamos enumerar todos estos conjuntos y 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 según su relación coste/valor. Sea $i := 1$ . Dejemos que $P := \lbrace\emptyset\rbrace$ , donde $\emptyset$ denota la combinación que no contiene alternativas.
- Para cada combinación $C \in P$ , dejemos que $C^* := C \cup \lbrace A_i \rbrace$ . Si $C^*$ no está dominada por ninguna combinación ya existente en $P$ , añada $C^*$ a $P$ .
- Si $i = n$ , stop. En caso contrario, incremente $i$ de uno en uno y repetir desde el paso 2.
De nuevo, como en el algoritmo B, no necesitamos comparar $C^*$ a cada combinación en $P$ ; es suficiente con comprobar si $C^*$ está dominada por la combinación más cara en $P$ que es más barato que $C^*$ .
¿Qué ocurre con las combinaciones de conjuntos múltiples? En este caso, obviamente, la frontera de Pareto $P$ contiene infinitas combinaciones: en particular, para cualquier combinación $C \in P$ la combinación $C + A_1$ , donde $A_1$ es la alternativa con la menor relación coste/valor, también pertenece en $P$ .
Sin embargo, el número de veces que cualquier otros alternativa puede aparecer en una combinación no dominada debe ser acotada. (La prueba es un poco tediosa, pero se deduce de simples consideraciones geométricas). Por lo tanto, sólo tenemos que considerar el conjunto finito $P_0$ de aquellas combinaciones en la frontera de Pareto que sí no incluir la alternativa $A_1$ las combinaciones restantes en la frontera se obtienen sumando un cierto número de $A_1$ s a esas combinaciones.
Para las combinaciones de conjuntos múltiples, también tenemos el siguiente lema útil:
Lema: Cualquier combinación que contenga una subcombinación dominada debe ser a su vez dominada.
En particular, esto significa que las combinaciones en $P$ sólo puede incluir alternativas que pertenezcan a su vez a $P$ . Así, como primer paso, podemos utilizar el algoritmo A (o B) para calcular la frontera de Pareto para las alternativas individuales y descartar cualquier alternativa que no forme parte de ella.
Para un algoritmo completo para calcular $P_0$ La siguiente definición resulta útil:
Dfn: Una combinación $B$ se dice que $A$ -dominar $C$ si la combinación $B + nA$ domina $C$ para algún número entero no negativo $n \in \mathbb N$ . Equivalentemente, $B$ $A$ -dominan $C$ si $\operatorname{cost}(C) > \operatorname{cost}(B) + n\,\operatorname{cost}(A)$ , donde $n = \max \left(0, \left\lfloor \frac{\operatorname{value}(C)-\operatorname{value}(B)}{\operatorname{value}(A)} \right\rfloor \right)$ .
Utilizando esta definición, podemos aplicar el siguiente algoritmo:
Algoritmo D :
- Dejemos que $A_1, \dotsc, A_n$ son las alternativas (no dominantes) ordenadas según su relación coste/valor. Sea $i := 2$ . Dejemos que $P_0 := \lbrace\emptyset\rbrace$ .
- Para cada combinación $C \in P_0$ , dejemos que $C^* := C + A_i$ . Si $C^*$ no es $A_1$ -dominado por cualquier combinación ya en $P_0$ , añada $C^*$ a $P_0$ .
- Repita desde el paso 2 hasta que no se añadan más combinaciones a $P_0$ .
- Si $i = n$ , stop. En caso contrario, incremente $i$ de uno en uno y repetir desde el paso 2.
I piense en este algoritmo debería ser correcto, pero para ser honesto, no estoy 100% seguro de que no haya errores o lagunas en mi esquema de prueba. Así que, por favor, pruébalo a fondo antes de usarlo para cualquier cosa importante. :-)
También creo que debería ser posible implementar el paso 2 de manera eficiente de forma similar a los algoritmos B y C, pero la situación se complica por el hecho de que la condición de rechazo es $A_1$ -dominio en lugar de la simple dominación. Por supuesto, si $B$ domina $C$ , entonces es trivial $A$ -dominan $C$ para cualquier $A$ Así que al menos se puede hacer una comprobación rápida de la dominancia simple.
Otra forma de optimizar el paso 2 es observar que si $C + A_i$ es $A_1$ -dominado por cualquier combinación en $P_0$ entonces también lo será $D + A_i$ para cualquier combinación $D$ que incluye $C$ como una subcombinación. En particular, podemos saltar al paso 4 en cuanto encontremos que $\emptyset + A_i = A_i$ mismo es $A_1$ -dominado por alguna combinación ya en $P_0$ .
