Monografías
Publicar | Monografías por Categorías | Directorio de Sitios | Software Educativo | Juegos Educativos | Cursos On-Line Gratis

 

Algoritmos genéticos parte 1 - Monografía



 
DESCARGA ESTA MONOGRAFÍA EN TU PC
Esta monografía en formato html para que puedas guardarla en tu pc e imprimirla.



Vínculo Patrocinado




Aquí te dejamos la descarga gratuita
Nota: para poder abrir archivos html solo necesitas tener instalado internet explorer u otro navegador web.




ALGORITMOS GENÉTICOS



1 BÚSQUEDA, OPTIMIZACIÓN Y APRENDIZAJE



En realidad, los algoritmos de búsqueda abarcan prácticamente todo algoritmo para resolver problemas automáticamente. Habitualmente, en Informática se habla de búsqueda cuando hay que hallar información, siguiendo un determinado criterio, dentro de un conjunto de datos almacenados; sin embargo, aquí nos referiremos a otro tipo de algoritmos de búsqueda, a saber, aquellos que, dado el espacio de todas las posibles soluciones a un problema, y partiendo de una solución inicial, son capaces de encontrar la solución mejor o la única. El ejemplo clásico de este tipo de problemas se encuentra en los rompecabezas y juegos que se suelen abordar en inteligencia artificial. Un ejemplo es el problema de las 8 reinas, en el cual se deben de colocar 8 reinas en un tablero de ajedrez de forma que ninguna amenace a otra; o las torres de Hanoi, en el que, dada una serie de discos de radio decreciente apilados, hay que apilarlos en otro sitio teniendo en cuenta que no se puede colocar ningún disco encima de otro de radio inferior.
Este tipo de problemas es fácil de abordar usando algoritmos “clásicos”, como por ejemplo algoritmos recursivos o de tipo voraz (greedy), sin embargo, hay otro tipo de problemas mucho más complicados, sobre todo los NP-completos (aquellos cuya complejidad crece con el tamaño del problema de forma exponencial) que no pueden ser abordados de esta forma. Algunos ejemplos de estos problemas serían los siguientes:
- 8-puzzle, en el cual, como se muestra en la ilustración 1, a partir de una configuración inicial donde hay 8 cuadros desordenados, hay que llegar a otra configuración donde estén ordenados, usando para el intercambio cualquier posición que se halle vacía. El problema de búsqueda en este caso consiste en encontrar un camino que vaya desde la configuración inicial hasta la final.

2676.gif

- Problema del viajante, en el cual, dadas una serie de ciudades separadas por distancias diferentes, hay que calcular un camino tal que la distancia total recorrida sea mínima, y no que no repita ninguna ciudad. Este problema es NP-completo, y es paradigmático de este tipo de problemas.
- Mastermind: En este juego, que se muestra en la figura 2, un jugador debe de averiguar una combinación de chinchetas de colores oculta por el otro jugador, y lo hace haciendo suposiciones sobre la combinación, y siendo contestado con una chincheta pequeña y blanca por cada acierto de color, y una negra por cada acierto de color o posición. Sólo una solución (entre 64) es la correcta, pero el jugador que ha puesto la combinación oculta va orientando la búsqueda mediante las chinchetas blancas o negras. El problema se hace exponencialmente más difícil cuando se aumenta el número de colores, y la longitud de la combinación.

2677.gif

En muchos casos, la búsqueda está guiada por una función que indica lo buena que es esa solución, o el coste de la misma, o lo cerca que se está de la solución final, si es que se conoce; el problema se convierte entonces en un problema de optimización, es decir, encontrar la solución que maximiza la función objetivo, de evaluación o fitness o minimiza el coste. En términos formales, dada una función F de n variables x1,x2,…, xn, optimizar la función consiste en encontrar la combinación de valores de xi tales que F(x1, x2,…, xn) = Máximo. Se puede hablar de maximizar en vez de minimizar sin perder generalidad, ya que maximizar F equivale a minimizar -F.
Generalmente, los problemas de optimización son tratados por la rama de las matemáticas denominada Investigación Operacional, aunque prácticamente todas las ramas de la ciencia y la ingeniería necesitan tratar con problemas de optimización en algún momento. Por ejemplo, en teoría de juegos se trata de maximizar la probabilidad de ganar, y en reconocimiento de patrones de minimizar el error de clasificación de un patrón desconocido (como una imagen de satélite digitalizada, o un canal procesado de una señal de un electroencefalograma).
El problema de optimización no siempre está formulado de una forma tan clara. En muchos casos, la forma de la función F no se conoce, y debe de aproximarse mediante polinomios o combinaciones de funciones conocidas; habría entonces que hallar los coeficientes de los polinomios o funciones que hacen que la función calculada se acerque lo más posible a la función objetivo. Cuando el problema se reduce a calcular una serie de coeficientes, se habla de optimización paramétrica.
En control industrial se plantean también problemas de optimización: cómo mantener el funcionamiento de una máquina dentro de su régimen óptimo, por ejemplo. Cada máquina suele tener una serie de parámetros variables, y lo que se desea optimizar es habitualmente la calidad del producto final o la rapidez a la hora de producirlo.
En algunos casos, la función de evaluación ni siquiera existe, o no es estática, sino que viene dada por el entorno de la solución. Por ejemplo, en un programa para jugar al Othello o reversi, el fitness vendrá dada por su puntuación a la hora de jugar con los demás jugadores. Un autor, Pollack hizo enfrentarse a unas estrategias de juego con otras, de forma que según van evolucionando, el fitness va variando. Este tipo de optimización se suele encontrar en problemas de vida artificial y el Dilema del Prisionero, usado para modelizar interacciones sociales.
El dilema del prisionero iterado es un juego en el cual se enfrentan dos jugadores, que representan dos presos en una cárcel, que se han puesto de acuerdo para fugarse; en cada iteración, cada jugador decide si se chiva al director de la cárcel, o coopera con el otro y se escapa. Si los dos cooperan, reciben una recompensa de 3; si uno de los dos se chiva, recibe todos los privilegios de un preso bueno en la forma de una recompensa de 5, y si los dos se chivan, reciben una recompensa, pero mucho menor, como aparece en la tabla. Si este juego se repite por un número finito y conocido de iteraciones, la estrategia óptima es siempre chivarse, porque consigues una recompensa asegurada de 1*número de jugadas, sin embargo, a largo plazo la estrategia óptima es cooperar, porque la recompensa es de 3. Con este juego se han hecho muchas variantes; un algoritmo debería de crear una estrategia de forma que maximice la recompensa de un jugador.
En los problemas de Biología que la Vida Artificial trata de resolver mediente simulaciones, el fitness viene siempre dado por el entorno, acercándose a la definición biológica de fitness, que no es otra cosa que el número posible de descendientes de un individuo (que no siempre es el mismo que el número real de descendientes).
En algunos se trata de optimizar F(C), donde C es una combinación de diferentes elementos que pueden tomar un número finito de valores; pueden ser combinaciones con o sin repetición, o incluso permutaciones, como en el caso del problema del viajante; en este caso se denominan problemas de optimización combinatoria.
No siempre, el espacio de búsqueda completo contiene soluciones válidas; en algunos casos, los valores de las variables se sitúan dentro de un rango, más allá del cual la solución es inválida. Se trata entonces de un problema de optimización con restricciones. En este caso, el problema consiste en maximizar F(xi) dentro del subespacio. Un ejemplo de este problema es el de optimización de los horarios de clase de una institución de enseñanza; hay que disponerla de forma que un profesor no deba estar en dos sitios a la vez (un alumno, puede), que el número de horas libres entre clases sea mínimo, y que se cumplan las preferencias de todos los implicados. En este caso, la optimización se reduce a cumplir todas las restricciones.
Otro ejemplo clásico es el denominado job-shop scheduling, o disposición de una línea de montaje, en donde cada componente de la línea debe de estar ocupado el mayor tiempo posible y cumplir restricciones de tiempos de entrega,
Hay muchas formar de abordar problemas de optimización. Algunas de ellas se verán en las siguientes secciones

1.1 MÉTODO ANALÍTICO



Si existe la función F, es de una sola variable, y se puede derivar dos veces en todo su rango, se pueden hallar todos sus máximos, sean locales o globales. Sin embargo, la mayoría de las veces no se conoce la forma de la función F, y si se conoce, no tiene porqué ser diferenciable ni siquiera una vez. Incluso el tratamiento analítico para funciones de más de 1 variable es complicado.


1.2 MÉTODOS EXHAUSTIVOS, ALEATORIOS Y HEURÍSTICOS



Los métodos exhaustivos recorren todo el espacio de búsqueda, quedándose con la mejor solución, y los heurísticos utilizan reglas para eliminar zonas del espacio de búsqueda consideradas “poco interesantes”. Algunos algoritmos de búsqueda, como el MiniMax, son de este tipo; se suelen utilizar en juegos para examinar y podar el árbol de posibilidades a partir de la jugada actual; Deep Blue, por ejemplo, juega de esta forma.
En los métodos aleatorios, se va muestreando el espacio de búsqueda acotando las zonas que no han sido exploradas; se escoge la mejor solución, y, además, se da el intervalo de confianza de la solución encontrada.


1.3 HILLCLIMBING,


En estos métodos se va evaluando la función en uno o varios puntos, pasando de un punto a otro en el cual el valor de la evaluación es superior. La búsqueda termina cuando se ha encontrado el punto con un valor máximo. En general, un algoritmo escalador funciona de la forma siguiente
Estos algoritmos toman muchas formas diferentes, según el número de dimensiones del problema solución, el valor del incremento y en la dirección en la cual se tiene que dar. En algunos casos se utiliza el llamado Método Montecarlo (por el casino), en el cual se escoge la nueva solución de forma aleatoria.
El principal problema de este tipo de algoritmos es que se quedan en el pico más cercano a la solución inicial; además, no son válidos para problemas multimodales, en los cuales la función de coste tiene varios óptimos posibles.


1.4 RECOCIMIENTO SIMULADO



Conocido como Simulated Annealing, en inglés, el nombre viene de la forma como se consiguen ciertas aleaciones en forja; una vez fundido el metal, se va enfriando poco a poco, para conseguir finalmente la estructura cristalina correcta, que haga que la aleación sea dura y resistente.
Este algoritmo se podría calificar como escalador estocástico, y su principal objetivo es evitar los mínimos locales en los que suelen caer los escaladores. Para ello, no siempre acepta la solución óptima, sino que a veces puede escoger una solución menos óptima, siempre que la diferencia entre ambos tenga un nivel determinado, que depende de un parámetro denominado temperatura (seguimos con la metáfora). El algoritmo de recocimiento simulado es el siguiente:


1.5 TÉCNICAS BASADAS EN POBLACIÓN



Este tipo de técnicas pueden ser versiones de cualquiera de las anteriores, pero en vez de tener una sola solución, que se va alterando hasta obtener el óptimo, se persigue el óptimo cambiando varias soluciones; de esta forma es más fácil escapar de los mínimos locales tan temidos. Entre estas técnicas se hallan la mayoría de los algoritmos evolutivos, que es donde vamos a centrar nuestro trabajo.


1.6 TÉCNICAS EXPERIMENTALES



En algunos casos, solo el ojo humano es capaz de evaluar lo apropiada que es una solución a un tema determinado, por ejemplo, en problemas de diseño o de calidad. En este caso, se pueden utilizar cualquiera de las técnicas expuestas anteriormente, pero a la hora de evaluar una solución, un experto o experta tendrá que darle una puntuación. Por ejemplo, es lo que se usa cuando uno se prueba ropa para dar con la combinación correcta de colores y estilos.

2 LA EVOLUCIÓN



Después de ver el tipo de problemas a los que se pueden aplicar los algoritmos evolutivos, se va a estudiar qué es lo que inspira dichos algoritmos, la Naturaleza, ese fenómeno natural denominado evolución, y si optimiza o no.
La teoría de la evolución (que no es tal teoría, sino una serie de hechos probados), fue descrita por Charles Darwin. La hipótesis de Darwin, presentada junto con Wallace, que llegó a las mismas conclusiones independientemente, es que pequeños cambios heredables en los seres vivos y la selección son los dos hechos que provocan el cambio en la Naturaleza y la generación de nuevas especies. Pero Darwin desconocía cual es la base de la herencia, pensaba que los rasgos de un ser vivo eran como un fluido, y que los “fluidos” de los dos padres se mezclaban en la descendencia; esta hipótesis tenía el problema de que al cabo de cierto tiempo, una población tendría los mismos rasgos intermedios.
2678.jpg

Fue Mendel quien descubrió que los caracteres se heredaban de forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo. A estos caracteres que podían tomar diferentes valores se les llamaron genes, y a los valores que podían tomar, alelos. En realidad, las teorías de Mendel, que trabajó en total aislamiento, se olvidaron y no se volvieron a redescubrir hasta principios del siglo XX. Además, hasta 1930 el geneticista inglés Robert Aylmer no relacionó ambas teorías, demostrando que los genes mendelianos eran los que proporcionaban el mecanismo necesario para la evolución.

2679.jpg

Más o menos por la misma época, el biólogo alemán Walther Flemming describió los cromosomas, como ciertos filamentos en los que se agregaba la cromatina del núcleo celular durante la división; poco más adelante se descubrió que las células de cada especie viviente tenían un número fíjo y característico de cromosomas.

2680.jpg

Y no fue hasta los años 50, cuando Watson y Crick descubrieron que la base molecular de los genes está en el ADN, ácido desoxirribonucleico. Los cromosomas están compuestos de ADN, y por tanto los genes están en los cromosomas.La macromolécula de ADN está compuesta por bases púricas y pirimidínicas, la adenina, citosina, guanina y timina. La combinación y la secuencia de estas bases forma el código genético, único para cada ser vivo. Grupos de 3 bases forman un codon, y cada codon codifica un aminoácido (el que exprese ese aminoácido o no depende de otros factores); el código genético codifica todas las proteinas que forman parte de un ser vivo. Mientras que al código genético se le llama genotipo, al cuerpo que construyen esas proteínas, modificado por la presión ambiental, la historia vital, y otros mecanismos dentro del cromosoma, se llama fenotipo.
Proyectos como el del Genoma Humano tratan de identificar cuáles son estos genes, sus posiciones, y sus posibles alteraciones, que habitualmente conducen a enfermedades.
Todos estos hechos forman hoy en día la teoría del neo-darwinismo, que afirma que la historia de la mayoría de la vida está causada por una serie de procesos que actúan en y dentro de las poblaciones: reproducción, mutación, competición y selección.
La evolución se puede definir entonces como cambios en el pool o conjunto genético de una población.
Un tema polémico, con opiniones variadas dependiendo de si se trata de informáticos evolutivos o de biólogos o geneticistas, es si la evolución optimiza o no.
Según los informáticos evolutivos, la evolución optimiza, puesto que va creando seres cada vez más perfectos, cuya cumbre es el hombre; además, indicios de esta optimización se encuentran en el organismo de los animales, desde el tamaño y tasa de ramificación de las arterias, diseñada para maximizar flujo, hasta el metabolismo, que optimiza la cantidad de energía extraída de los alimentos.
Sin embargo, los geneticistas y biólogos evolutivos afirman que la evolución no optimiza, sino que adapta y optimiza localmente en el espacio y el tiempo; evolución no significa progreso. Un organismo más evolucionado puede estar en desventaja competitiva con uno de sus antepasados, si se colocan en el ambiente del último.

2.1 MECANISMOS DE CAMBIO EN LA EVOLUCIÓN



Estos mecanismos de cambio serán necesarios para entender los algoritmos evolutivos, pues se trata de imitarlos para resolver problemas de ingeniería; por eso merece la pena conocerlos en más profundidad. Los mecanismos de cambio alteran la proporción de alelos de un tipo determinado en una población, y se dividen en dos tipos: los que disminuyen la variabilidad, y los que la aumentan.
Los principales mecanismos que disminuyen la variabilidad son los siguientes:


- SELECCIÓN NATURAL:


Los individuos que tengan algún rasgo que los haga menos válidos para realizar su tarea de seres vivos, no llegarán a reproducirse, y, por tanto, su patrimonio genético desaparecerá del pool; algunos no llegarán ni siquiera a nacer. Esta selección sucede a muchos niveles: competición entre miembros de la especie (intraespecífica), competición entre diferentes especies, y competición predador-presa, por ejemplo. También es importante la selección sexual, en la cual las hembras eligen el mejor individuo de su especie disponible para reproducirse.

- DERIVA GÉNICA:


El simple hecho de que un alelo sea más común en la población que otro, causará que la proporción de alelos de esa población vaya aumentando en una población aislada, lo cual a veces da lugar a fenómenos de especiación, por ejemplo, por el denominado efecto fundador.
Otros mecanismos aumentan la diversidad, y suceden generalmente en el ámbito molecular. Los más importantes son:

- MUTACIÓN:


La mutación es una alteración del código genético, que puede suceder por múltiples razones. En muchos casos, las mutaciones las elimina la ADN-polimerasa, la navaja del ejército suizo del ADN, que igual duplica, que corrige, que desinvierte un cacho genético mal colocado. En muchos otros casos, las mutaciones, que cambian un nucleótido por otro, son letales, y los individuos ni siquiera llegan a desarrollarse, pero a veces se da lugar a la producción de una proteína que aumenta la supervivencia del individuo, y que, por tanto, es pasada a la descendencia. Las mutaciones son totalmente aleatorias, y son el mecanismo básico de generación de variedad genética. A pesar de lo que se piensa habitualmente, la mayoría de las mutaciones ocurren de forma natural, aunque existen sustancias mutagénicas que aumentan su frecuencia.

- POLIPLOIDÍA:


Mientras que las células normales poseen dos copias de cada cromosoma, y las células reproductivas una (haploides), puede suceder por accidente que alguna célula reproductiva tenga dos copias; si se logra combinar con otra célula diploide o haploide dará lugar a un ser vivo con varias copias de cada cromosoma. La mayoría de las veces, la poliploidía da lugar a individuos con algún defecto (por ejemplo, el tener 3 copias del cromosoma 21 da lugar al mongolismo), pero en algunos casos se crean individuos viables. Un caso de mutación fue el que sufrió (o disfrutó) el mosquito Culex pipiens, en el cual se duplicó un gen que generaba una enzima que rompía los organofosfatos, componentes habituales de los insecticidas;

- RECOMBINACIÓN:


Cuando las dos células sexuales, o gametos, una masculina y otra femenina se combinan, los cromosomas de cada una también lo hacen, intercambiándose genes, que a partir de ese momento pertenecerán a un cromosoma diferente. A veces también se produce traslocación dentro de un cromosoma; una secuencia de código se elimina de un sitio y aparece en otro sitio del cromosoma, o en otro cromosoma.

- FLUJO GENÉTICO:


O intercambio de material genético entre seres vivos de diferentes especies. Normalmente se produce a través de un vector, que suelen ser virus o bacterias; estas incorporan a su material genético genes procedentes de una especie a la que han infectado, y cuando infectan a un individuo de otra especie pueden transmitirle esos genes a los tejidos generativos de gametos.
En resumen, la selección natural actúa sobre el fenotipo y suele disminuir la diversidad, haciendo que sobrevivan solo los individuos más aptos (aunque esta frase, bien mirada, es una redundancia: ¿Sobreviven los mejores o son los mejores porque sobreviven?); los mecanismos que generan diversidad y que combinan características actúan habitualmente sobre el genotipo.

3 ALGORITMO GENÉTICO SIMPLE.



3.1 INTRODUCCIÓN



John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad.
Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.
En esa universidad, Holland impartía un curso titulado Teoría de sistemas adaptativos. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los algoritmos genéticos.
Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos:
- imitar los procesos adaptativos de los sistemas naturales, y
- diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.
Unos 15 años más adelante, David Goldberg, actual delfín de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Goldberg era un ingeniero industrial trabajando en diseño de pipelines, y fue uno de los primeros que trató de aplicar los algoritmos genéticos a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle algoritmos genéticos, Goldberg consiguió lo que quería, escribiendo un algoritmo genético en un ordenador personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los algoritmos genéticos en un campo con base suficiente aceptado para celebrar la primera conferencia en 1985, ICGA´85.

3.2 ANATOMÍA DE UN ALGORITMO GENÉTICO SIMPLE



Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación.
Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, el objetivo es hallar (xi,…,xn) tales que F(xi,…,xn) sea máximo.
En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,…,xn) se codifican en un cromosoma.
Todos los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son sólo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética.
Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.
Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles).
El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies.
La diversidad genética se introduce mediante mutaciones y reproducción sexual.
En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo genético, sin embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. Este tipo de optimización, denominada optimización multimodal, también se suele abordar con un algoritmo genético especializado.

Por lo tanto:

Un algoritmo genético consiste en hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y se aplican los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad. En las siguientes secciones se verán cada uno de los aspectos de un algoritmo genético.

3.3 CODIFICACIÓN DE LAS VARIABLES


Los algoritmos genéticos requieren que el conjunto se codifique en un cromosoma. Cada cromosoma tiene varios genes, que corresponden a sendos parámetros del problema. Para poder trabajar con estos genes en el ordenador, es necesario codificarlos en una cadena, es decir, una ristra de símbolos (números o letras) que generalmente va a estar compuesta de 0s y 1s.

EJEMPLO  1:
Si un atributo (tiempo) puede tomar tres valores posibles (despejado, nublado, lluvioso) una manera de representarlo es mediante tres bits de forma que:
(Tiempo = Nublado ó Lluvioso) y (Viento = Fuerte) se representaría con la siguiente cadena: 011 10.
De esta forma podemos representar fácilmente conjunciones de varios atributos para expresar restricciones (precondiciones) mediante la concatenación de dichas cadenas de bits.
Además si  tenemos otro atributo “Viento” que puede ser Fuerte o Moderado,se representaría con la siguiente cadena: 011 10.
Las postcondiciones de las reglas se pueden representar de la misma forma. Por ello una regla se puede describir como la concatenación de la precondición y la postcondición.
EJEMPLO2:
“JugaralTenis” puede ser Cierto o Falso.
Si Viento = Fuerte entonces JugaralTenis = Cierto se representaría mediante la cadena 111 10 10. Donde los tres primeros bits a uno indican que el atributo “Tiempo” no afecta a nuestra regla.
Cabe destacar que una regla del tipo 111 10 11 no tiene demasiado sentido, puesto que no impone restricciones en la postcondición. Para solucionar esto, una alternativa es codificar la postcondición con un único bit (1 = Cierto y 0 = Falso). Otra opción es condicionar los operadores genéticos para que no produzcan este tipo de cadenas o conseguir que estas hipótesis tengan una adecuación muy baja (según la función de evaluación) para que no logren pasar a la próxima generación de hipótesis.
A continuación se comienza con una población de soluciones posibles, que pueden ser generadas al azar o mediante algún método que produzca soluciones relativamente satisfactorias. A partir de este punto inicial, el algoritmo procede por etapas que ejecutan los pasos elementales siguientes:
Se evalúan todas las soluciones de la población, con el fin de otorgar más probabilidades de emparejamiento a las más satisfactorias.
Mediante un mecanismo de azar, aunque dando más oportunidades a las mejor evaluadas, se eligen las soluciones que han de cruzarse entre sí para dar lugar a descendencia.
El cruce opera sobre las cadenas de los genotipos de cada pareja de las soluciones elegidas como progenitores. El sistema mediante el cual se obtienen nuevas soluciones a partir las precedentes, es decir lo que se llama el operador de cruzamiento, puede ser distinto según las técnicas específicas empleadas. El que se describe en el punto siguiente es uno de los más generalizados.





Creative Commons License
Estos contenidos son Copyleft bajo una Licencia de Creative Commons.
Pueden ser distribuidos o reproducidos, mencionando su autor.
Siempre que no sea para un uso económico o comercial.
No se pueden alterar o transformar, para generar unos nuevos.

 
TodoMonografías.com © 2006 - Términos y Condiciones - Esta obra está bajo una licencia de Creative Commons. Creative Commons License