introducci´on a la computaci´on...

Introduccion a la Computacion Evolutiva Dr. Carlos A. Coello Coello

Introduccion a la Computacion Evolutiva

Dr. Carlos A. Coello Coello

Departamento de Computacion

CINVESTAV-IPN

Av. IPN No. 2508

Col. San Pedro Zacatenco

Mexico, D.F. 07300

email: [email protected]

http: //delta.cs.cinvestav.mx/~ccoello

Clase No. 1 2018


Conceptos Basicos de

Analisis de Algoritmos

Analisis a priori de algoritmos

Orden de magnitud de un algoritmo

Clase No. 1 2018


Analisis a priori de algoritmos

Se ignoran los detalles que sean dependientes de la arquitectura deuna computadora o de un lenguaje de programacion y se analiza elorden de magnitud de la frecuencia de ejecucion de las instruccio-nes de un algoritmo.

Clase No. 1 2018



Suele usarse la notacion “O” (big-O)

Si un algoritmo tiene complejidad O(g(n)) significa que alcorrerlo en una computadora con los mismos datos, perovalores incrementales de n, los tiempos resultantes de ejecucionseran siempre menores que | g(n) |

Clase No. 1 2018



Los tiempos mas comunes de los algoritmos son:

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)

Clase No. 1 2018



Clase No. 1 2018


Clase P

Un problema pertenece a la clase P si puede ser resuelto en tiempopolinomial en una computadora determinıstica.

Ejemplos: Quicksort, busqueda binaria, multiplicacion matricial.

Clase No. 1 2018


Clase NP

Un problema pertenece a la clase NP si puede ser resuelto entiempo polinomial pero usando una computadora no determinıstica.

Clase No. 1 2018


P vs NP

La clase P contiene problemas que pueden resolverserapidamente.

La clase NP contiene problemas cuya solucion puedeverificarse rapidamente.

En 1971 se planteo la pregunta: ¿Es P = NP? Desde entonces,sigue siendo una pregunta abierta para los teoricos.

Se cree que P!=NP

Clase No. 1 2018


Problemas NP Completos

Todos los algoritmos requeridos para resolverlos requierentiempo exponencial en el peor caso.

Es decir, estos problemas son sumamente difıciles de resolver.

Ejemplos: el problema del viajero, O(n22n)

Clase No. 1 2018


El problema del viajero

Encontrar una permutacion que represente el recorrido de unaserie de ciudades de tal forma que todas sean visitadasminimizando la distancia total viajada.

Clase No. 1 2018



Si consideramos n ciudades:

El tamano del espacio de busqueda es: (n− 1)!/2

Para n=10, hay unas 181,000 soluciones posibles.

Para n=20 hay unas 10,000,000,000,000,000 soluciones posibles.

Clase No. 1 2018



Para n=50 hay unas 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 solucionesposibles.

Clase No. 1 2018



Solo hay 1,000,000,000,000,000,000,000 litros de agua en elplaneta

Clase No. 1 2018


Tecnicas Clasicas de Busqueda y Optimizacion

Existen muchas tecnicas clasicas para resolver problemas conciertas caracterısticas especıficas.

Es importante saber al menos de la existencia de estas tecnicas,pues cuando el problema por resolverse se adecua a ellas, no tieneningun sentido usar heurısticas.

Clase No. 1 2018



Para optimizacion lineal, el metodo Simplex sigue siendo la opcionmas viable. Para optimizacion no lineal, hay metodos directos (p.ej. la busqueda aleatoria) y metodos no directos (p. ej. el metododel gradiente conjugado).

Clase No. 1 2018



Existen tambien tecnicas que construyen parcialmente una soluciona un problema. Por ejemplo, la programacion dinamica y el metodode ramificacion y busqueda (branch & bound).

Clase No. 1 2018



Cuando enfrentamos un cierto problema de optimizacion, si lafuncion a optimizarse se encuentra en forma algebraica, esimportante intentar resolverla primero con tecnicas clasicas, antesde utilizar cualquier heurıstica.

Clase No. 1 2018


Lo que el mundo real demanda

Existen problemas que no pueden resolverse usando unalgoritmo que requiere tiempo polinomial.

De hecho, en muchas aplicaciones practicas, no podemossiquiera decir si existe una solucion eficiente.

Hay muchos problemas para los cuales el mejor algoritmo quese conoce requiere tiempo exponencial.

Clase No. 1 2018


¿Que es una heurıstica?

La palabra “heurıstica” se deriva del griego heuriskein, que significa“encontrar” o “descubrir”. El significado del termino ha variadohistoricamente. Algunos han usado el termino como un antonimode “algorıtmico”. Por ejemplo, Newell et al. dicen: “a un procesoque puede resolver un cierto problema, pero que no ofrece ningunagarantıa de lograrlo, se le denomina una “heurıstica” para eseproblema”

Clase No. 1 2018



Las heurısticas fueron un area predominante en los orıgenes de laInteligencia Artificial. Actualmente, el termino suele usarse comoun adjetivo, refiriendose a cualquier tecnica que mejore eldesempeno en promedio de la solucion de un problema, aunque nomejore necesariamente el desempeno en el peor caso (Russell &Norvig, 1995).

Clase No. 1 2018



Una definicion mas precisa y adecuada para los fines de este cursoes la proporcionada por Reeves (1993):Una heurıstica es una tecnica que busca soluciones buenas (esdecir, casi optimas) a un costo computacional razonable, aunquesin garantizar factibilidad u optimalidad de las mismas. En algunoscasos, ni siquiera puede determinar que tan cerca del optimo seencuentra una solucion factible en particular.

Clase No. 1 2018


¿Realmente necesitamos tecnicas heurısticas?

Cuando enfrentamos espacios de busqueda tan grandes como en elcaso del problema del viajero, y que ademas los algoritmos maseficientes que existen para resolver el problema requieren tiempoexponencial, resulta obvio que las tecnicas clasicas de busqueda yoptimizacion son insuficientes.

Clase No. 1 2018


Ejemplos de tecnicas heurısticas

Busqueda tabu

Recocido simulado

Escalando la colina

Clase No. 1 2018


Busqueda Tabu

Usa una “memoria” para guiar la busqueda.

Algunas soluciones examinadas recientemente son“memorizadas” y se vuelven tabu (prohibidas) al tomardecisiones acerca del siguiente punto de busqueda.

Es determinıstica, aunque se le pueden agregar elementosprobabilısticos.

Clase No. 1 2018


Recocido Simulado

Basado en el enfriamiento de los cristales.

El horario de enfriamiento es crucial.

Requiere de una temperatura inicial, una final y una funcion devariacion de la temperatura.

Es un algoritmo probabilıstico de busqueda local.

Clase No. 1 2018


Escalando la Colina

Se aplica a un punto a la vez (tecnica local).

Se generan varios estados posibles y se selecciona el mejor.

No hay retroceso ni registro historico.

Puede quedar atrapado facilmente en optimos locales.

Es un algoritmo determinıstico.

Clase No. 1 2018


Optimizacion Global

El objetivo principal de cualquier tecnica de optimizacion esencontrar el optimo (o los optimos) globales de cualquier problema.En matematicas, existe un area que se ocupa de desarrollar losformalismos que nos permitan garantizar la convergencia de unmetodo hacia el optimo global de un problema.

Clase No. 1 2018


Optimizacion Global

Desgraciadamente, solo en algunos casos limitados, puedegarantizarse convergencia hacia el optimo global.Por ejemplo, para problemas con espacios de busqueda convexos,las condiciones de Kuhn-Tucker son necesarias y suficientes paragarantizar optimalidad global de un punto.

Clase No. 1 2018


Optimizacion Global

En problemas de optimizacion no lineal, las condiciones deKuhn-Tucker no son suficientes para garantizar optimalidad global.De hecho, todas las tecnicas usadas para optimizacion no linealpueden localizar cuando mucho optimos locales, pero no puedegarantizarse convergencia al optimo global a menos que se usentecnicas exhaustivas o que se consideren tiempos infinitos deconvergencia.

Clase No. 1 2018


Optimizacion Numerica

Existen muchos tipos de problemas de optimizacion, pero los quenos interesan mas para los fines de este curso, son de los deoptimizacion numerica, que pueden definirse de la siguiente manera:

Minimizar f(~x)

sujeta a:

gi(~x) ≤ 0 i = 1, ..., p

hj(~x) = 0 j = 1, ..., n

Clase No. 1 2018



Llamaremos a (~x) las variables de decision del problema, gi(~x) sonlas restricciones de desigualdad, y hj(~x) son las restricciones deigualdad. Asimismo, f(~x) es la funcion objetivo del problema (laque queremos optimizar).

Clase No. 1 2018



A las restricciones de igualdad y desigualdad expresadasalgebraicamente, se les denomina “restricciones explıcitas”. Enalgunos problemas, existen tambien “restricciones implıcitas”,relacionadas sobre todo con las caracterısticas del problema.

Clase No. 1 2018



Por ejemplo, si decimos:

10 ≤ x1 ≤ 20

estamos definiendo que el rango de una variable de decision debeestar contenido dentro de un cierto intervalo. De tal forma, estamos“restringiendo” el tipo de soluciones que se consideraran comovalidas.

Clase No. 1 2018


Ejemplos de espacios de busqueda convexos

Clase No. 1 2018


Ejemplos de espacios de busqueda no convexos

Clase No. 1 2018


Zona factible y no factible

Todas las soluciones a un problema que satisfagan las restriccionesexistentes (de cualquier tipo), se consideran ubicadas dentro de lazona factible. De tal forma, podemos decir que el espacio debusqueda de un problema se divide en la region (o zona) factible yla no factible.

Clase No. 1 2018


Zona factible y no factible

Esta imagen ilustra la diferencia entre la zona factible y no factiblede un problema:

Clase No. 1 2018


Optimizacion Combinatoria

Existe una clase especial de problemas que tambien seran de interespara este curso, en los cuales las variables de decision son discretasy las soluciones suelen presentarse en la forma de permutaciones. Aestos problemas se les denomina de “optimizacion combinatoria”(p. ej. el problema del viajero).

Clase No. 1 2018


Durante muchos anos, la tesis mas aceptada sobre el origen de lasespecies fue el creacionismo: Dios creo a todas las especies delplaneta de forma separada.

Clase No. 1 2018


Ademas, segun el creacionismo, las especies estaban jerarquizadaspor Dios de tal manera que el hombre ocupaba el rango superior, allado del creador.

Clase No. 1 2018


Georges Louis Leclerc (Conde de Buffon) fue tal vez el primero enespecular (100 anos antes que Darwin) que las especies seoriginaron entre sı, e incluso especulo sobre la posible existencia deun ancestro comun entre el hombre y los simios, aunque despues, elmismo refuto esta hipotesis. Varias de sus ideas fueron, sinembargo, revolucionarias para su epoca.

Clase No. 1 2018


Leclerc sugirio que las especies pudieron haberse “mejorado” y“degenerado” despues de haberse dispersado a partir de un ejecentral de la creacion. En el volumen 14 de su Histoire naturelle,generale et particuliere, argumenta que todos los cuadrupedos delmundo se desarrollaron a partir de un conjunto original de solo 38cuadrupedos. Es por ello que algunos lo consideran un“transformista” y precursor de las ideas de Darwin.

Clase No. 1 2018


Leclerc tambien indico que el cambio climatico pudo haberfacilitado la dispersion de las especies. La interpretacion correcta desus ideas es, sin embargo, muy difıcil, dado que las retoma variasveces en su extenso trabajo, cambiando en muchas ocasiones supunto de vista al respecto.

Clase No. 1 2018


El biologo frances Jean-Baptiste Lamarck enuncio la que seconsidera como la primera teorıa evolutiva coherente de la historia(en 1808).

Clase No. 1 2018


Lamarck indico correctamente que el ambiente da pie a los cambiosen los animales. Esto lo ilustro con ejemplos tales como la ceguerade los topos, la presencia de dientes en los animales y la ausencia dedientes en las aves que para el constituıan evidencia de esta teorıa.

Clase No. 1 2018


En sus trabajos, senalo que existıan dos fuerzas principales queconformaban la evolucion: una que forzaba los cambios en losanimales, pasandolos de formas simples a otras mas complejas, yuna segunda que adaptaba a los animales a sus ambientes locales yque los diferenciaba entre sı. Lamarck creıa que estas fuerzasdebıan ser explicadas como una consecuencia necesaria deprincipios fısicos basicos.

Clase No. 1 2018


Los aspectos mas importantes a tener en cuenta sobre la teorıa evolutiva

de Lamarck son los siguientes:

1. Su teorıa se centra unicamente en la evolucion de los organismos y

no en su origen ya que, en aquel entonces se aceptaba que los

organismos surgıan espontaneamente en sus formas mas simples.

2. Propuso que los cambios que sufren los organismos para adaptarse

eran heredables. Anos despues se demostro que esto era incorrecto.

Clase No. 1 2018


3. La teorıa evolutiva de Lamarck constituıa una clara oposicion a la

creencia de la epoca de que las especies permanecıan inmutables

desde su creacion.

4. Curiosamente, durante el siglo XX han existido evolucionistas que

han defendido el llamado Lamarckismo, a traves de las voces de

varios biologos y evolucionistas que han buscado reivindicar el

trabajo de Lamarck.

Clase No. 1 2018


El naturalista ingles Charles Darwin pesento en 1858 los primerosbosquejos de su (ahora famosa) teorıa sobre el origen de lasespecies. Su libro, titulado On the Origin of Species by Meansof Natural Selection, or the Preservation of FavouredRaces in the Struggle for Life, se publico el 24 de noviembre de1859 y se considera como una de las obras cientıficas masimportantes de todos los tiempos.

Clase No. 1 2018


Darwin entendio que toda poblacion consiste de individuos ligeramente

distintos entre sı y que estas pequenas variaciones hacen que cada uno

tenga distintas capacidades para adaptarse a su medio ambiente,

ası como para reproducirse y para transmitir sus rasgos a sus

descendientes.

Clase No. 1 2018


Con el paso del tiempo (o generaciones), los rasgos de los individuos que

mejor se adaptaron a las condiciones del medio ambiente, se vuelven mas

comunes, haciendo que la poblacion, en su conjunto, evoluciones. Darwin

llamo a este proceso “descendencia con modificacion”. Del mismo modo,

la naturaleza selecciona las especies mejor adaptadas para sobrevivir y

reproducirse. A este proceso, Darwin lo denomino “seleccion natural”.

Clase No. 1 2018


El cientıfico aleman August Weismann formulo la denominadateorıa del plasma germinal hacia finales del siglo XIX. Deacuerdo a esta teorıa, la herencia, en un organismo multi-celular, seefectua unicamente por medio de celulas germinales (la union delos espermatozoides con el ovulo).

Clase No. 1 2018


Segun Weismann, las otras celulas del cuerpo, son las somaticas y NO

funcionan como agentes hereditarios. Afirmo, ademas, que este efecto es

unidireccional: las celulas germinales producen celular somaticas, pero no

puede transmitirse informacion genetica de celulas somaticas a celulas

germinales. A esto se le conoce como la barrera de Weismann.

Clase No. 1 2018


Weismann realizo un experimento en el que corto las colas de un grupo

de ratas durante 22 generaciones (1,592 ratas en total). Weismann

reportarıa: “durante cinco generaciones, se produjeron 901 ratas jovenes

a partir de padres mutilados artificialmente, y no se obtuvo ni un solo

ejemplo de una cola rudimentaria, ni hubo ninguna otra anomalıa en

esta extremidad”. Esto demostraba claramente que no era posible

heredar mutilaciones ocurridas durante el tiempo de vida, y corroboraba

su teorıa del plasma germinal.

Clase No. 1 2018


El monje austriaco Johann Gregor Mendel realizo una serie de

experimentos con chıcharos durante una buena parte de su vida,

enunciando a partir de ellos las leyes basicas que gobiernan la herencia.

Los resultados de su trabajo los publico en 1866 en un artıculo titulado

“Experiments on Plant Hybridization”, pero tuvo poco impacto (solo

obtuvo 3 citas en sus primeros 35 anos), hasta que fue re-descubierto a

principios del siglo XX.

Clase No. 1 2018


Una pieza interesante de las teorıas evolutiva es el denominadoEfecto Baldwin, conocido tambien como evolucionbaldwiniana o evolucion ontogenica. Esta teorıa se propuso enun artıculo de 1896, titulado “A New Factor in Evolution”, el cualfue escrito por el psicologo norteamericano James Mark Baldwin.

Clase No. 1 2018


Este artıculo propuso la nocion de plasticidad fenotıpica, que es la

capacidad de un organismo para adaptarse a su ambiente durante su

tiempo de vida. La capacidad de aprendizaje es el ejemplo mas obvio de

plasticidad fenotıpica, aunque no es el unico. Debe aclararse, sin

embargo, que la plasticidad fenotıpica es tıpicamente costosa para un

individuo. Por ejemplo, aprender requiere energıa y tiempo.

Clase No. 1 2018


Hoy se usa el termino Neo-Darwinismo para describir a lasıntesis moderna de la teorıa de la evolucion de Darwin con lagenetica de Mendel y la teorıa del plasma germinal de Weismann.

Clase No. 1 2018


El pensamiento evolutivo actual gira en torno alNeo-Darwinismo, el cual establece que toda la vida en elplaneta puede ser explicada a traves de solo 4 procesos:

• Reproduccion

• Mutacion

• Competencia

• Seleccion

Clase No. 1 2018

introducci´on a la computaci´on...

Documents