... tiene varios inconvenientes:
- Son lentas.
- Hay que establecer un sistema para recorrer todas las posibilidades.
- En ocasiones es imposible o simplemente no es practico recorrer todas las posibilidades. Vease la nota (*) al final.
Ante el primer problema, solo queda la paciencia o buscarse un ordenador más potente/rápido; pero ne el segundo y tercero no tengo tan claro que siempre se pueda solventar. Para poder tener constancia de que soluciones se han recorrido y cuales quedan por visitar, puede ser necesario usar complejas extructuras de datos. Por ejemplo, para recorrer un plano completo puede ser necesario trazar una curva de Peano cuyos puntos de paso son ¡¡infinitos!!. La cantidad de memoria que requiere almacenarlos puede ser terrible.
El enfoque empleado en esta ocasión será la busqueda de una solución satisfactoria por medio de un algoritmo de los llamados inteligentes: Algoritmos genéticos.
Todas las explicaciones que voy a dar son solo válidas en el ámbito de la divulgación y no es mi intención hacerme pasar por un experto. En caso de dudas, ya buscaremos a quien preguntarselas B-)
¿Qué es un algoritmo genético?
Un algoritmo genético es un sistema de busqueda de soluciones usando el azar como nuestro aliado (estocástico lo llaman los expertos). E intenta imitar los mecanismos de selección/evolución de la naturaleza de los más aptos.
Pongamos un ejemplo: Sea una montaña en la que queremos localizar una mina de carbón. Podemos intentar localizarla por fuerza bruta, es decir, hacemos un plano de la montaña y levantamos un recorrido que pase por todos los rincones de la montaña. A partir de ese recorrido, vamos haciendo prospecciones hasta encontrar una veta de carbon. El otro método consiste en hacer una serie de prospecciones al azar. Y mirar el porcentaje de carbono de cada una (podemos suponer que la densidad de carbono va subiendo conforme nos acercamos a una veta). Aquellas prospecciones con bajo contenido en carbono son desechadas y se efectúan nuevas prospecciones en las zonas cercanas a donde medimos la mayor densidad (las nuevas ubicaciones son escogidas al azar pero en función de las densidades y distancias a las antiguas).
¿Qué tiene que ver la minería con la genética? mucho. El mecanismo es similar a la de los seres vivos: Las prospecciones representan a una población. Las prospecciones menos aptas son despreciadas y olvidadas y a partir de los elementos más aptos se calculan cuales serán los siguientes intentos de encontrar el filón. Vemos reflejados los mecanismos de la selección (supervivencia de los más útiles) y de la evolución (como escoger nuevos elementos a partir de los anteriores).
Y ahora hablemos de algorítmos genéticos: Para poder aplicarlos hacen falta tres elementos: una forma de representar cada posible solucion, una forma de determinar si nos acercamos o no a lo ideal (la llamaremos función de evaluación) y una forma de obtener nuevos intentos de solución a partir de la población anterior. Y esto último es lo que nos queda por hablar para ser todos unos expertos en algoritmos genéticos. B-)
Cada posible solución (que llamaremos individuo) está representado por una variable de estado que lo discrimina del resto. Esa variable de estado es como la cadena de ADN de un ser vivo. Dentro están los genes que en nuestro caso serían distintas variables que lo definen. Por ejemplo si nuestro individuo fuese una posición del espacio representado por tres coordenadas enteras de 16 bit, el individuo quedaría representado por una variable de 3*16= 48 bits donde los 16 primero serían la coordenada X, los segundos la coordenada Y y los terceros la coordenada Z. (*) Un conjunto de individuos representa una población.
¿Cómo evolucionan estos sistemas? pues igual que el material genético de los seres vivos. Podemos coger «material genético» de un padre y de una madre y combinarlos formando una nueva cadena ADN mezcla de la de los padres, puede suceder una mutación espontánea de un individuo alterando algún bit de su ADN, procesos de recombinación entre diversos elementos, ... La función de evaluación determina si el resultado es viable (si está dentro del campo de las soluciones) y cual es su nivel de aptitud. Y por tanto de supervivencia.
Ventajas de este sistema:
- Se puede determinar a priori las necesidades de cálculo que van a existir, en función de la población (determinada en fase de diseño), la función de evaluación (conocida), la población (se selecciona en fase de diseño) y los mecanismos de reproducción (se selecciona igualmente en fase de diseño).
- La efectividad de este método es en su límite inferior equivalente a una busqueda totalmente al azar; pero si se hace un buen diseño, tenderá a soluciones aceptables en muy poco tiempo.
- El tiempo máximo de busqueda de soluciones se puede establecer.
- Conservando una copia de la población, se puede interrumpir y continuar búsquedas; incluso aunque se varíen los parámetros de la búsqueda
¿Sirve para todo este método?
No. Este sistema nos permite acercarnos a los óptimos aunque no asegura que lo hemos hallado. Así que cuando se exige la mejor solución, hará falta combinarlo con otros sistemas para poder confirmarla. Además hay que asegurarse de que no caemos en un máximo/mínimo local que dé una falsa mejor solución.
Bueno, me he quedado ya sin espacio, Si interesa el tema haré otra entrada con el caso práctico del empaquetamiento y explicando mi programa, dando los fuentes para que lo podais usar los que querais y como querais.
--
* Un «ADN» de 48 bits da un campo de soluciones de 2^48 posibles
individuos, si miramos a millon de soluciones por segundo, tardaríamos
8.9 años en ver todas las posibles soluciones, ¿entendeis porque la
fuerza bruta no es siempre lo mejor?
