La optimización simplemente significa obtener el mejor valor del conjunto de valores dado (con algunos criterios). El ejemplo más común es la programación dinámica. Tomemos, por ejemplo, uno de los problemas más comunes: 0–1 Problema de mochila.
Planteamiento del problema: dados los pesos y valores de n elementos, coloque estos elementos en una mochila de capacidad W para obtener el valor total máximo en la mochila.
En otras palabras, dados dos conjuntos enteros val [0..n-1] y wt [0..n-1] que representan valores y pesos asociados con n elementos respectivamente. También dado un número entero W que representa la capacidad de la mochila, descubra el subconjunto de valor máximo de val [] de tal manera que la suma de los pesos de este subconjunto sea menor o igual a W. No puede dividir un elemento, ni elegir el elemento completo o no lo elijas (propiedad 0-1).
- ¿Cuál es la mejor tarea para las redes neuronales en 2017 y tal vez para los próximos 5 años?
- ¿R es tan popular solo por las bibliotecas que pueden manejar varias funciones estadísticas?
- ¿Cuáles son algunos pequeños proyectos iniciales en aprendizaje automático de regresión lineal que un principiante puede hacer en 2-3 días?
- ¿Debo usar bibliotecas de python como Scikit-learn para ML que tienen algoritmos estándar implementados (considerando que soy un novato en el aprendizaje automático)?
- ¿Qué biblioteca / framework AI es el mejor, OpenAI, OpenNN o TensorFlow?
En la programación dinámica, dividimos el problema en subproblemas superpuestos y usamos sus salidas para obtener la salida del problema actual.
Algoritmo para la mochila 0–1:
El algoritmo toma como entrada el peso máximo W , el número de elementos n, y las dos secuencias v = < v1 , v2,. . . , vn > yw = < w1 , w2,. . . , wn >. Almacena los valores de c [ i , j ] en la tabla, es decir, una matriz bidimensional, c [0. . n , 0. . w ] cuyas entradas se calculan en un orden de fila mayor. Es decir, la primera fila de c se completa de izquierda a derecha, luego la segunda fila, y así sucesivamente. Al final del cálculo, c [ n , w ] contiene el valor máximo que puede recogerse en la mochila.
Dynamic-0-1-mochila (v, w, n, W)
PARA w = 0 A W
DO c [0, w ] = 0
PARA i = 1 a n
DO c [ i , 0] = 0
PARA w = 1 A W
DO IFf wi ≤ w
ENTONCES SI vi + c [ i -1, w – wi ]
ENTONCES c [ i , w ] = vi + c [ i -1, w – wi ]
ELSE c [ i , w ] = c [ i -1, w ]
MÁS
c [i, w ] = c [ i -1, w ]
El conjunto de elementos a tomar se puede deducir de la tabla, comenzando en c [ n. w ] y el rastreo hacia atrás de donde provienen los valores óptimos. Si c [ i, w ] = c [ i -1, w ] el ítem i no es parte de la solución, y seguimos rastreando con c [ i -1, w ]. De lo contrario, el ítem i es parte de la solución, y continuamos rastreando con c [ i -1, w – W ].
Entonces, tome este código de Python para Knapsack usando el algoritmo anterior:
def knapSack (W, wt, val, n):
K = [[0 para x en el rango (W + 1)] para x en el rango (n + 1)]
# Construye la tabla K [] [] de abajo hacia arriba
para i en rango (n + 1):
para w en rango (W + 1):
si i == 0 o w == 0:
K [i] [w] = 0
elif wt [i-1] <= w:
K [i] [w] = max (val [i-1] + K [i-1] [w-wt [i-1]], K [i-1] [w])
más:
K [i] [w] = K [i-1] [w]
volver K [n] [W]
La programación dinámica es solo uno de los ejemplos de optimización matemática. Hay muchas más técnicas de optimización como la optimización convexa, que actualmente es un tema candente para la investigación en programación matemática, pero requiere un mayor nivel de comprensión en matemáticas.
