... tiene varios inconvenientes:
- Son lentas.
- Hay que establecer un sistema para recorrer todas las
posibilidades por el camino más corto y en la medida de lo posible sin
repetir ( una repetición conlleva a tiempo de cálculo perdido ).
- 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 el segundo no tengo tan claro que
siempre tenga solución. Para poder tener constancia de que soluciones
se han recorrido y cuales quedan por visitar, puede ser necesario usar
complejas extructuras de datos para ir marcando cada solución
visitada. Requiriendo gran cantidad de memoria para este comentido. En otros casos es simplemente imposible dado que existen infinitos puntos posibles.
El que sea un poco sagaz deducirá por la palabra que empleé antes
que enfoque he usado en esta ocasión: «inteligente». He realizado el
sistema de búsqueda por medio de un algoritmo genético. Y como
funciona y solo he tardado una mañana en plantear y programar el
problema (obteniendo solución satisfactoria, escribo aquí para goce
mio y de ajenos. (Y por si esta información le interesa a alguien).
Todas las explicaciones que voy a dar son solo para ambitos de
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 la veta
principal). Aquellas prospecciones con bajo contenido en carbono son
desechadas y se efectúan más prospecciones en las zonas de mayor
densidad (al azar pero cerca de las mejores de las anteriores).
¿Qué tiene que ver la minería con la genética? mucho. Las
prospecciones representan a una población. Las prospecciones menos
aptos son despreciadas y olvidados y a partir de los individuos más aptos se calculan cuales serán los siguientes intentos de encontrar el filón. Vemos
reflejados los mecanismos de selección (supervivencia de los más útiles) y de evolución (como escoger nuevos elementos a partir de los más aptos).
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. (*)
¿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: A bote pronto se me ocurre los
siguientes:
- Se puede determinar a priori las necesidades de cálculo que van a
existir, en función de 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 en la mayoria de ocasiones si se hace un buen diseño, tenderá rapidamente a soluciones aceptables en muy poco tiempo.
- El tiempo máximo de busqueda de soluciones se puede establecer.
- Permite interrumpir y continuar búsquedas. Incluso aunque se varíen los parámetros de la búsqueda (solo es necesario guardar la población de un instante).
¿Sirve para todo este método?
No. Digamos que cuando la función de evaluación da valores al azar
por el espacio de las soluciones, me parece que «azar con azar se
contrarrestan» y las soluciones no tienden a ningún máximo
estable. Esto obligaría a replantear la descripción de los individuos
o buscar otro método de búsqueda de soluciones.
Además este sistema nos permite acercarnos a los óptimos aunque no
asegura que lo hemos hallado. Así que cuando se exige la mejor
solución, hara falta combinarlo con otros algorítmos.
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?
