PASOS PARA APLICAR EL AG

1. Generar una población de vectores (individuos).
2. Mientras no se encuentre un criterio de parada: 

• Seleccionar un conjunto de vectores padre, que serán reemplazados de la población.
• Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores                           hijo.
• Aplicar una mutación a cada descendiente.
• Evaluar a los hijos.
• Introducir a los hijos en la población.
• Eliminar a aquellos individuos menos eficaces.

Normalmente este proceso finaliza después de un numero determinado de generaciones o cuando la población ya no puede mejorar. La selección de los padres se elige probabilísticamente hacia los individuos más aptos. Al igual que ocurre con en la Naturaleza, los sujetos con mayor aptitud diseminan sus características en toda la población.

Esta descripción de los AG se adapta a cada situación concreta, siendo habitual la codificación de números enteros en vez de binarios. Del mismo modo se han sofisticado los distintos operadores de cruzamiento y mutación.

APLICACIONES DEL ALGORITMO GENETICO

1.-Optimización, donde son utilizados en numerosas tareas de optimización, donde se incluyen la optimización numérica y los problemas de optimización combinatoria.

2.-Programacion automática, se emplean para el desarrollo de programas para tareas especificas y para el diseño de otras estructuras computacionales tales como el autómata celular y las redes de comunicación.

3.-Aprendizaje máquina, los algorítmos genéticos se han utilizado en la predicción del tiempo, o en la estructura de una proteína. además estos sirven para desarrollar aspectos determinados de sistemas particulares de aprendizaje, como el de los pesos de una red neuronal, las reglas para sistemas de clasificación de aprendizaje y los sensores para robots.

4.-En la economía se han hecho uso de los algoritmos genéticos para modelizar procesos de innovación, el desarrollo de estrategias, y la aparición de mercados económicos.

5.-En los sistemas inmunes, cuando se deben modelizar varios aspectos de los sistemas inmunes naturales, donde se incluye la mutación somática durante la vida de un individuo y el descubrimiento de familias de genes múltiples en tiempo evolutivo, han resultado útil el descubrimiento de esta técnica.

ALGORITMO GENETICO

Para comenzar, se definirá algoritmo como una serie de procesos que se desarrollan de forma estructurada u organizada, para dar soluciones a problemas presentados. 

    

Se puede plantear una definición dada por Goldberg  de la siguiente forma  "Los algoritmos genéticos son algoritmos  de busqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para construir así un algoritmo de busqueda que tenga algo de las genialidades de las búsquedas humanas ".

Para que se alcance una solución a un problema , se debe partir por un conjunto inicial de individuos, el que se le denominará población, el cual se genera de forma aleatoria. cada uno de estos individuos representará una posible solución  al problema. Estos individuos evolucionarán tomandose como base los esquemas propuestos por darwin sobre la seleccion natural, y se adaptaran con el paso de cada generación en mayor medida, a la solución requerida.

APLICACIONES DE LAS CADENAS DE MARKOV

Se aplica en el posicionamiento de marcas para describir la probabilidad de que un cliente que adquiere la marca A en un periodo, adquiere en su lugar la marca B en el siguiente y analizar la penetración en el mercado.

Se aplica para describir la probabilidad de que una maquina que funciona en un periodo determinado, continúe o falle en el siguiente.

Se aplica en la meteorología si considera el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos.

Otra aplicación son los juegos de azar, un ejemplo es de ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar termine sin dinero.

CADENAS ABSORBENTES

Una cadena de Márkov que consta solamente de estados transitorios y absorbentes, se denomina CADENA DE MÁRKOV ABSORBENTE.

Pasos que se deben seguir para la construcción de una matriz de cadena absorbente:

1.  Determinar si la cadena es absorbente. Esto ocurre:

·  Si la cadena tiene por lo menos un estado absorbente (es decir que hay 1 y 0 en la matriz).

·  Si es posible pasar de un estado no absorbente a un estado absorbente.

2.  Forma la matriz de transición T. Ponga el estado absorbente al final. asegúrese de que los renglones y las columnas se encuentran en el mismo orden.

3.  Descarte los renglones que corresponden a los estados absorbentes. Esta información no se requerirá más.

4.  Forme la matriz N a partir de las columnas no absorbentes de la matriz del paso 3 y forme la matriz A partir de las columnas absorbentes.

5.  Calcule la matriz fundamental (I – N) -1. Esta matriz proporciona la cantidad esperada de periodos que se empleara en los estados no absorbentes antes de quedar absorbidos. La matriz (I – N) -1. Se obtiene de la información de un estado no absorbente, así que se denota con estados no absorbentes.

6.  Calcule y nombre a (I – N) -1 A. Esta matriz proporciona la probabilidad de ser absorbidos en cada uno de los estados no absorbentes. Los renglones de (I – N) -1 A se encuentran rotulados con los estados no absorbentes y las columnas, con los estados absorbentes.

PROCEDIMIENTO DE CADENA DE MARKOV

Un proceso de markov esta caracterizado por una funcion de probabilidad de transicion representada por T, llamada matriz de transicion que representa las probabilidades de transito de un estado a otro y un vector de probabilidad de estado inicial que representa el estado inicial del mercado.

CADENAS DE MARKOV

Las cadenas de markov son modelos probabilísticos que se usan para predecir la evolución y el comportamiento a corto y a largo plazo de determinados sistemas.

Ejemplos: reparto del mercado entre marcas; dinámica de las averías de máquinas para decidir política de mantenimiento; evolución de una enfermedad,…

Una cadena de Markov es una sucesión de ensayos similares u observaciones en la cual cada ensayo tiene el mismo número finito de resultados posibles y  en donde la probabilidad de cada resultado para un ensayo dado depende sólo del resultado del ensayo inmediatamente precedente y no de cualquier resultado previo.

SIMULACIÓN MONTECARLO

La Simulación de Montecarlo es una técnica q combina conceptos estadísticos (muestreo aleatorio) con la capacidad que tienen los ordenadores para generar números pseudo-aleatorios y automatizar cálculos. Los orígenes de esta técnica están ligados al trabajo aplicando una infinidad de ámbitos como alternativas a los modelos matemáticos exactos o inclusos como único medio de estimar soluciones para problemas complejos.

En la actualidad es posible encontrar modelos de simulación Montecarlo en las áreas informáticas, empresarial, económica, industrial e incluso social.

En otras palabras, la simulación de Montecarlo está presente en todos los ámbitos en la que el comportamiento aleatorio o probabilístico desempeñe un papel fundamental.

El nombre de Montecarlo proviene de la famosa ciudad de Mónaco, donde abundan los casinos de juegos y donde el azar la probabilidad y el comportamiento aleatorio conforman todo un estilo de vida.

¿QUE ES LA SIMULACION MONTECARLO?

La simulación Montecarlo es una técnica matemática computarizada que permite tener en cuenta el riesgo en análisis cuantitativos y tomas de decisiones. 

Esta técnica es utilizada por profesionales de campos tan dispares como los de finanzas, gestión de proyectos,  energía, manufacturación, ingeniería, investigación y desarrollo, seguros, petróleo y gas, transporte y medio ambiente.

La simulación Montecarlo ofrece a la persona responsable de tomar las decisiones una serie de posibles resultados, así como la probabilidad de que se produzcan según las medidas tomadas. Muestra las posibilidades extremas, los resultados de tomar la medida más arriesgada y la más conservadora, así como todas las posibles consecuencias de las decisiones intermedias.

VENTAJAS

·         Es un método directo y flexible.

·         Cuando el modelo matemático es demasiado complicado la simulación permite obtener una simulación.

·         La simulación permite resolver problemas que no tiene solución analítica.

·         La simulación no interviene en el mundo real, permite experimentar.

DESVENTAJAS

·         La simulación no genera soluciones Óptimas globales.

·         Una buena simulación puede resultar muy complicada, gran número de variables.

·         No proporciona la decisión a tomar, si no que resuelve el problema mediante aproximación para unas condiciones iniciales.

·         Cada simulación es única, interviene el azar.

METODO MONTECARLO

El método de Montecarlo permite resolver problemas matemáticos mediante la simulación de variables aleatorias. John Von Neumann, en los años 40 y con los primeros ordenadores, aplica la simulación para resolver problemas complejos que no podían ser resueltos de forma analítica. Montecarlo y su casino están relacionados con la simulación. La ruleta, juego estrella de los casinos, es uno de los aparatos mecánicos más sencillos que nos permiten obtener números aleatorios para simular variables aleatorias.

NUMEROS ALEATORIOS

Los números aleatorios son la base esencial de la simulación  Usualmente toda la aleatoriedad involucrada en el modelo se obtiene a partir de un generador de números aleatorios que produce una sucesión de valores que supuesta mente son realizaciones de una secuencia de variables aleatorias independientes e idénticamente distribuidas. Posteriormente estos numero aleatorios se transforman convenientemente para simular las diferentes distribuciones de probabilidad que se requieran en el modelo.

Una pieza fundamental en una simulación que requiera el uso del azar, son los números aleatorios. En una hoja de cálculo como Microsoft® Excel®, para tener un número aleatorio es escribir en una celda =aleatorio()

Los números aleatorios tienen las siguientes características:

1. Son números reales.

2. Se representan con la letra r.

3. Su rango es [0,1) , es decir, 0 ≤ r < 1

4. Se distribuyen uniformemente entre 0 y 1 

5. En una secuencia larga de números aleatorios, el promedio debe ser de 0.5 y su varianza de  1/12  

6. Cada número aleatorio es independiente del anterior y del siguiente.

MODELO CON VARIOS SERVIDORES

(M/M/C):(DG/¥/¥)

En este modelo los clientes llegan con una tasa constante λ y un máximo de c clientes son atendidos simultáneamente. La tasa de servicio por servidor activo es también constante e igual a μ. Al usar c servidores paralelos se acelera la tasa de servicio. Si el número de clientes en el sistema n es igual o excede a c, la tasa combinada de servicio es igual a cμ. Por otra parte, si n es menor que c, la tasa combinada de salidas es de nμ. En término del modelo generalizado tenemos

λ_n=   λ    n=0,1,2,…μ_n={

nμ    n=0,1,…,c

cμ    n=c+1,c+2,…

(M/M/C):(DG/N/¥)

La única diferencia con el modelo anterior es que el número máximo de clientes permitidos en el sistema es N, es decir, la longitud máxima de la línea de espera es N-c. En términos del modelo generalizado esta situación se traduce en

(M/M/ ¥ ):(DG/ ¥ /¥)

MODELO DE AUTOSERVICIO

En este modelo, el número de servidores es ilimitado porque el cliente mismo es también un servidor. Este es normalmente el caso en los establecimientos de autoservicio. Una vez más en términos del modelo generalizado se tiene

(M/M/ R ):(DG/ K /K)

MODELO DE SERVICIO DE MAQUINAS

Para el caso del modelo de servicio de máquinas el cual se define como un taller en el cual existen una cantidad K de máquinas las cuales se averían a una tasa  λ y una cantidad R de mecánicos que las reparan a una tasa µ. 

MODELOS CON UN SERVIDOR

(M/M/1):(PLPS/¥/¥)

 Se tiene que la distribución exponencial:

Tiene una media:

(M/M/1):(DG/N/¥)

La única diferencia con el modelo anterior es que el numero máximo de clientes permitidos en el sistema es N, es decir, la longitud máxima de la cola de espera es N − 1.

En términos del modelo generalizado esta situación se traduce en:

MEDIDAS DE DESEMPEÑO DE ESTADO ESTABLE

Una vez que se ha determinado la probabilidad  p_n, de estado estable de n clientes en el sistema, podemos calcular las medidas de desempeño de estado estable de líneas de espera en forma directa. Entre las principales medidas de desempeño que se utilizarán se cuentan:

Ls = Número Esperado de Clientes en el Sistema

Lq = Número de Clientes Esperados en la Fila

Ws= Tiempo Estimado de Espera en el Sistema

Wq= Tiempo Estimado de Espera en la Fila

C= Numero de servidores ocupados promedio.

FORMULAS DE LITLLE

NOTACION KENDALL

David G. Kendall

(a/b/c):(d/e/f)

a=llegadas

b=salidas

c=servidores en paralelo

d=disciplina de la cola

e=cantidad maxima del sistema

f=tamaño de la fuente

Distribuciones para a y b

M= Markov o Poisson

D= Deterministico o tiempo constante

Ek= Erlag o Gama de tiempo

Gl= Distribucion general de tiempo entre llegadas

G= Distribucion general de tiempo de servicio

Disciplina de la cola

PLPS

ULPS

SEOA (aleatorio)

DG (Disciplina General)

MUERTES PURAS

•       El sistema inicia con N clientes en el tiempo 0.

•       No se permiten más llegadas.

•       Las salidas tiene una frecuencia de µ clientes por unidad de tiempo.

MODELO NACIMENTOS PUROS

•       Solo permite ingresos al sistema.

•       Probabilidad de que no hayan llegadas en un espacio de tiempo t.

DISTRIBUCION EXPONENCIAL

•       La mayoría de los casos la llegada es aleatoria sin influencia del tiempo transcurrido entre el evento anterior

•       Los tiempo aleatorios de llegada se describen con la distribución exponencial

Los tiempos aleatorios entre llegadas se describen en forma cuantitativa, en los modelos de colas, con la distribución exponencial, que se describe como sigue:

Para la distribución exponencial:

ELEMENTOS DE UN MODELO COLA

•       CLIENTE

•       SERVIDOR: LINEA O PARALELO

•       FUENTE

•       TIEMPO ENTRE LLEGADAS

•       TIEMPO DE SERVICIO

•       TAMAÑO DE LA COLA: FINITO O INFINITO

•       DISCIPLINA D ELA COLA: ORDEN EN QUE ESCOGEN LOS CLIENTES D ELA COLA: PLPS, ULPS, SEOA O PRIORIDAD

SISTEMAS DE COLAS

Un sistema de colas se puede describir como: “clientes” que llegan buscando un servicio, esperan si este no es inmediato, y abandonan el sistema una vez han sido atendidos. En algunos casos se puede admitir que los clientes abandonan el sistema si se cansan de esperar.

El término “cliente” se usa con un sentido general y no implica que sea un ser humano, puede significar piezas esperando su turno para ser procesadas o una lista de trabajo esperando para imprimir en una impresora en red.

FIG. 1 SISTEMA DE COLAS BASICO

Aunque la mayor parte de los sistemas se puedan representar como en la figura 1, debe quedar claro que una representación detallada exige definir un número elevado de parámetros y unciones.

La teoría de colas fue originariamente un trabajo práctico. La primera aplicación de la que se tiene noticia es del matemático danés Erlang sobre conversaciones telefónicas en 1909, para el cálculo de tamaño de centralitas. Después se convirtió en un concepto teórico que consiguió un gran desarrollo, y desde hace unos años se vuelve a hablar de un concepto aplicado aunque exige un importante trabajo de análisis para convertir las fórmulas en realidades, o viceversa.

INTRODUCCION

Todos hemos experimentado en alguna ocasión la sensación de estar perdiendo el tiempo al esperar en una cola. El fenómeno de las colas nos parece natural: esperamos en el coche al estar en un tapón, o un semáforo mal regulado, o en un peaje; esperamos en el teléfono a que nos atienda un operador y en la cola de un supermercado para pagar....

Generalmente como clientes no queremos esperar, los gestores de los citados servicios no quieren que esperemos.... ¿Por qué hay que esperar?

La respuesta es casi siempre simple, en algún momento la capacidad de servicio ha sido (o es) menor que la capacidad demandada. Esta limitación se puede eliminar invirtiendo en elementos que aumenten la capacidad. En estos casos la pregunta es: ¿Compensa invertir?

La teoría de colas intenta responder a estas preguntas utilizando métodos matemáticos analíticos.

INTRODUCCION A LA SIMULACION

Simulación es un área de estudio que forma parte de la Investigación de Operaciones (IDO), La cual es usada prácticamente en todas las áreas de estudio conocidas. Simulación permite estudiar un sistema sin tener que realizar experimentación sobre el sistema real. Esto presenta muchas ventajas que discutiremos más adelante aquí. Sin embargo, esta no es la única forma de estudiar un sistema; otra posibilidad es construir un modelo análitico conformado por un conjunto de ecuaciones (generalmente diferenciales) que representan al sistema para luego resolverlo para diferentes situaciones, o bien plantear un modelo de optimización que pretende proporcionar la mejor estrategia que el sistema debe adoptar para funcionar mejor de acuerdo con alguna medida de rendimiento establecida en la "función objetivo" y satisfaciendo las diversas condiciones del problema, establecidas en "las restricciones". Los modelos que se obtienen como un conjunto de ecuaciones se denominan con frecuencia modelos analíticos, es decir modelos de ecuaciones diferenciales o de optimización. Por cierto que, los estudiosos de las ecuaciones diferenciales afirman con orgullo que todos los modelos analíticos son de ecuaciones diferenciales, ya que incluso una simple ecuación algebráica es una ecuacion diferencial de o den cero (sic). Cualquiera que sea el caso, analizaremos aquí a manera de introducción los modelos analíticos y los de simulación, que por cierto aún no decimos como son, pues primero veremos algunas inconveniencias de los modelos analíticos. Posteriormente, despues de discutir brevemente que son los modelos de simulación, indicaremos ventajas y desventajas de los modelos de simulación.