Algoritmos de Optimización y Clasificación: Una Visión General

Este documento presenta una descripción detallada de varios algoritmos clave utilizados en optimización y aprendizaje automático. Se exploran algoritmos de búsqueda de vecindad variable, enfriamiento estadístico, algoritmos de estimación de costes, GRASP, CGA, árboles de clasificación y otros métodos avanzados.

Búsqueda de Vecindad Variable (VNS)

La Búsqueda de Vecindad Variable (VNS) es un método de optimización que explora sistemáticamente diferentes vecindades de una solución para encontrar la mejor. El algoritmo se describe a continuación:

  1. Seleccionar el conjunto de sistemas de vecinos Vk, k = 1, . . . , kmax
  2. Elegir una solución inicial e0
  3. Repetir hasta que no se mejore
  4. Hacer k = 1
  5. Repetir hasta que k = kmax
  6. Encontrar la mejor solución e en Vk(e0)
  7. Si e es mejor que e0 entonces e0 = e y k = 1 //solución mejor la aceptamos y comenzamos por el primer sistema de vecinos.
  8. else k = k + 1 //cambiamos al siguiente sistema de vecinos.

Simulated Annealing (Enfriamiento Estadístico)

Simulated Annealing (SA) es un algoritmo de optimización que acepta soluciones peores con cierta probabilidad, lo que permite escapar de óptimos locales. El algoritmo es el siguiente:

  1. Seleccionar una solución inicial e0 de E
  2. Inicializar iteraciones num_iter=0
  3. Repetir
  4. tam_cadena=0
  5. Repetir
  6. Elegir de forma aleatoria una solución enew en V(e0)
  7. d = f(enew) - f(e0)
  8. si d < 0 entonces //Si es mejor se acepta e0 = enew
  9. sino elegir un número aleatorio aleat en [0, 1]
  10. si e-d/ck > aleat e0 = enew //Si hay suerte se acepta a pesar de ser peor
  11. tam_cadena=tam_cadena+1
  12. hasta tam_cadena > tam_max
  13. ck +1 = w(ck) //Se reduce el margen de aceptados
  14. num_iter=num_iter+1
  15. hasta num_iter > iter_max //Termina cuando no se aceptan soluciones peores.

Algoritmos de Estimación de Costes (EDAs)

Los Algoritmos de Estimación de Distribuciones (EDAs) son una clase de algoritmos evolutivos que aprenden y utilizan una distribución de probabilidad para generar nuevas soluciones. El algoritmo general es:

  1. Obtener una población inicial de individuos D0
  2. Repetir hasta que se cumpla un criterio de parada
  3. Seleccionar de Di un conjunto de individuos DiS
  4. Aprender una distribución de prob. pi(x) a partir de DiS
  5. Muestrear pi(x) para obtener Di+1/2
  6. Crear la nueva población Di+1 a partir de Di y Di+1/2

UMDA

El algoritmo UMDA (Univariate Marginal Distribution Algorithm) es un tipo específico de EDA.

  1. D0 Generar M individuos (la población inicial) al azar
  2. Repeat for l = 1, 2, . . . hasta que se verifique el criterio de parada
  3. DSe l-1 Seleccionar N M individuos de Dl-1 de acorde al método de selección
  4. pl(x) = p(x|DSe l-1) = Qn i=1 pl(xi) = Qn i=1 PN j=1 j (Xi=xi|DSe l-1)
  5. N Estimar la distribución de probabilidad conjunta
  6. Dl Muestrear M individuos (la nueva población) de pl(x)

GRASP

GRASP (Greedy Randomized Adaptive Search Procedure) es un metaheurístico iterativo para problemas de optimización combinatoria. El algoritmo es:

  1. Elegir muestreando una distribución uniforme una ciudad i
  2. Repetir n .. 1
  3. Calcular las k ciudades más cercanas a la última añadida (dentro de las no añadidas)
  4. Seleccionar dentro de las k, una ciudad j con probabilidad inversamente proporcional a la distancia a la última ciudad elegida

CGA

El Algoritmo Genético Correlacionado (CGA) es un algoritmo evolutivo que utiliza una representación basada en probabilidades para guiar la búsqueda. El algoritmo es:

  1. Inicializar el vector de probabilidades p0(x) p0(x) = p0(x1, . . . , xi, . . . , xn) = (p0(x1), . . . , p0(xi), . . . , p0(xn)) = (0,5, . . . , 0,5, . . . , 0,5)
  2. l = l + 1. Muestrear pl(x) con l = 0, 1, . . . obtener dos individuos: xl1, xl2
  3. Evaluar y ordenar xl1 y xl2 obteniendo: xl1:2 (el mejor de los dos) y xl2:2 (el peor de los dos)
  4. Actualizar el vector de probabilidades pl(x) hacia xl1:2
  5. for i = 1 to n do
  6. if xli,1:2 ≠ xli,2:2 then
  7. if xli,1:2 = 1 then pl(xi) = pl-1(xi) + 1 K
  8. if xli,1:2 = 0 then pl(xi) = pl-1(xi) - 1 K
  9. Comprobar si el vector de probabilidades pl(x) ha convergido
  10. for i = 1 to n do
  11. if pl(xi) > 0 y pl(xi) < 1 then volver al Paso 2
  12. pl(x) representa la solución final

Árboles de Clasificación

Los árboles de clasificación son modelos predictivos que utilizan una estructura de árbol para clasificar datos. Se presentan dos variantes:

TDIDT

TDIDT (Top-Down Induction of Decision Trees) es un algoritmo para construir árboles de decisión. El algoritmo es:

  1. Begin
  2. if todos los patrones de D pertenecen a la misma clase C then resultado de la inducción es un nodo simple (nodo hoja) etiquetado como c
  3. else begin
  4. 1. Seleccionar la variable mas informativa Xr con valores xr1 , . . . , xrnr
  5. 2. Particionar D de acorde con los nr valores de Xr en D1 , . . . , Dnr
  6. 3. Construir nr subarboles T1 , . . . , Tnr para D1 , . . . , Dnr
  7. 4. Unir Xr y los nr subarboles T1 , . . . , Tnr con los valores xr1 , . . . , xrnr
  8. endif
  9. End

Variantes:

  • ID3 – Basa su selección de variable mas informativa en I(Xi, C) (cantidad de información mutua).
  • C4.5 – Basa su selección de variable mas informativa en I(Xi, C)/ H(Xi). – Realiza un poda (post pruning), para simplificar el árbol obtenido basándose en el número de bien clasificados.

BSEJ

BSEJ (Bayesian Search for Ensemble of Junctions) es un algoritmo que construye un clasificador combinando variables predictoras. El algoritmo es:

  1. Paso 1. Inicializar con el modelo naïves Bayes con todas las variables predictoras
  2. Paso 2. Repetir en cada paso la mejor opción entre:
  3. (a) Considerar reemplazar dos de las variables usadas por el clasificador por una nueva variable producto cartesiano de ambas
  4. (b) Considerar eliminar una variable usada por el clasificador.
  5. Evaluar cada posible opción por medio de la estimación del porcentaje de bien clasificados
  6. Hasta que ninguna opción produzca mejoras

TAN

Naïves Bayes aumentado a Árbol (TAN) utiliza una adaptación del algoritmo de Chow-Liu para generar un árbol de información mutua. El algoritmo es:

  1. Paso 1. Calcular I(Xi , Xj | C) con i < j, i, j = 1, . . . , n
  2. Paso 2. Construir un grafo no dirigido completo cuyos nodos corresponden a las variables predictoras: X1 , . . . , Xn . Asignar a cada arista conectando las variables Xi y Xj un peso dado por I(Xi , Xj | C)
  3. Paso 3. A partir del grafo completo anterior y siguiendo el algoritmo de Kruskall construir un árbol expandido de máximo peso
  4. Paso 4. Transformar el árbol no dirigido resultante en uno dirigido, escogiendo una variable como raíz, para a continuación direccionar el resto de aristas .
  5. Paso 5. Construir un modelo TAN añadiendo un nodo etiquetado como C y posteriormente un arco desde C a cada variable predictora Xi

PBIL

PBIL (Population-Based Incremental Learning) es un algoritmo de aprendizaje basado en poblaciones que utiliza un vector de probabilidades para representar las soluciones. El algoritmo es:

  1. Obtener un vector inicial de probabilidades p0(x)
  2. while no convergencia do
  3. begin
  4. Usando pl(x) obtener M individuos: xl1, . . . , xlk, . . . , xlM
  5. Evaluar y ordenar xl1, . . . , xlk, . . . , xlM
  6. Seleccionar los N (N M) mejores individuos: xl1:M, . . . , xlk:M, . . . , xlN:M
  7. Actualizar el vector de probabilidades pl+1(x) = (pl+1(x1), . . . , pl+1(xn))
  8. for i = 1, . . . n do
  9. pl+1(xi) = (1 - α)pl(xi) + α/N ΣNk=1 xli,k:M
  10. end