Mejor suma aproximada

[[Héctor Randolph]]

¿Han escuchado algo de algoritmos genéticos?

He utilizado algoritmos genéticos para resolver problemas NP (entre ellos packing) y funcionan de maravilla.

La teoría se basa en el principio de selección natural y la evolución de las especies.

Se crea aleatoriamente una población en donde cada individuo es una posible solución al problema.

La idea es que los individuos con mayor aptitud (mejores soluciones) de una población heredan sus genes y por ende sus aptitudes a las nuevas generaciones, al cabo de muchos ciclos de selección se espera que la población final contenga a los individuos mas aptos, entonces tendremos muchas posibles soluciones.

Basicamente se utilizan los algoritmos genéticos en problemas que tienen un espacio de soluciones enorme, se trata de maximizar (optimizar) una función de aptitud.

Cada individuo es un cromosoma es decir una cadena de bits que de alguna manera representa una solución a nuestro problema, se elige una función que nos diga que tan buena es la solución y de esta manera se hacer la selección de los mejores individuos.

El problema radica en encontrar una representación de las soluciones como cadena de bits y elegir una buena función para evaluar las aptitudes.

En google hay mucha información acerca de algoritmos genéticos.

También se puede intentar con el algoritmo de recocido simulado de hecho he obtenido mejores soluciones con este último pero es un poco más complicado. En este caso se trata de simular un proceso físico de enfriamiento.

Bueno, no quiero complicarme demasiado, con respecto a lo que plantea Lepe, trataré de encontrar la representación con algoritmos genéticos a su problema y después les comento.

Saludos.