WIXLIB

Memorias de la Décima Quinta Conferencia Iberoamericana en Sistemas, Cibernética e Informática (CISCI 2016)Herramienta software para resolver procesos de decisión de Markov utilizandorecocido simuladoCristhian D SANDOVALTecnología en sistematización de datos, Universidad Distrital Francisco José de CaldasBogotá, ColombiaXimena GALINDOTecnología en sistematización de datos, Universidad Distrital Francisco José de CaldasBogotá, ColombiaRoberto E SALASTecnología en sistematización de datos, Universidad Distrital Francisco José de CaldasBogotá, Colombia2.GENERALIDADESRESUMENRecocido SimuladoEl recocido simulado o Simulated annealing (SA) es unalgoritmo de búsqueda local capaz de escapar de los óptimoslocales permitiendo que bajo ciertas circunstancias se admitanmovimientos que empeoren la mejor solución encontrada hastael momento en el proceso de búsqueda [1].Este artículo expone el diseño del prototipo de software PDMRC (Procesos de decisión de Markov implementando recocidosimulado) y la implementación que se realizó utilizando variastecnologías.Se describe el problema del Remplazo del automóvil, la formacomo el prototipo lo soluciona y los resultados y conclusionesobtenidos.Entre sus características principales se debe resaltar que es unalgoritmo que implementa el procedimiento de búsqueda localpara mejorar progresivamente las soluciones. Para ello examinala vecindad y toma el primer movimiento que produce unamejora en la solución actual.Palabras Claves: Procesos de Decisión de Markov, RecocidoSimulado, Política, Matlab y Java.1.En cuanto a la cantidad de soluciones que utiliza el algoritmoSA para realizar la búsqueda se puede decir que pertenece algrupo de las metaheurísticas trayectoriales, es decir que elalgoritmo SA parte de una única solución inicial y es capaz degenerar un camino o trayectoria en el espacio de búsqueda.INTRODUCCIÓNLa importancia que tienen los procesos de decisión de Markov(PDM) en varios campos de la ciencia y la industria está ligadaa la capacidad que tienen para predecir el comportamiento de unsistema a través del tiempo y lograr tomar decisiones concriterio o probabilidad. Los PDM están conformados porcadenas de Markov, estas no son más que una serie de eventos,en la cual la probabilidad de que ocurra un evento depende delevento inmediatamente anterior. En efecto, las cadenas de estetipo tienen memoria, recuerdan el último evento y estocondiciona las posibilidades de los eventos futuros.La función objetivo es estática ya que no presenta cambiosdurante el proceso de la búsqueda y que el algoritmo nopresenta inconvenientes a la hora de decidir si se quiereminimizar o maximizar una función. La estructura de vecindades estática para limitar el campo de soluciones vecinas, estogarantiza la potencia del algoritmo y permite buscar envecindades de diferentes tamaños [1]Cadenas de MarkovSon una herramienta para analizar el comportamiento dedeterminados tipos de procesos estocásticos, esto es, procesosque evolucionan de forma no determinística a lo largo deltiempo en torno a un conjunto de estados.El prototipo de software PDM-RC nace de un intento porencontrar políticas óptimas de procesos de decisión de markovaprovechando todas las ventajas que nos ofrecen los algoritmosmetaheuriticos y en específico el algoritmo de recocidosimulado que es el algoritmo que utiliza el prototipo paradeterminar la política optima que maximice la recompensadurante una cantidad finita de estados.Una cadena de Markov, por tanto, representa un sistema quevaría su estado a lo largo del tiempo, siendo cada cambio unatransición del sistema. Dichos cambios no estánpredeterminados, aunque sí lo está la probabilidad del próximoestado en función de los estados anteriores, probabilidad que esconstante a lo largo del tiempo (sistema homogéneo en eltiempo).Eventualmente, en una transición el nuevo estadopuede ser el mismo que el anterior y es posible que exista laposibilidad de influir en las probabilidades de transiciónactuando adecuadamente sobre el sistema (decisión) [2].Con el software PDM-RC se han podido resolver variosproblemas descritos en libros de investigación de operacionespero también funciona para ejercicios propuestos o que son detipo experimental cuya finalidad siempre es encontrar la mejorpolítica para obtener una recompensa óptima.192

Memorias de la Décima Quinta Conferencia Iberoamericana en Sistemas, Cibernética e Informática (CISCI 2016)visualización y representación de gráficos, así como para eldesarrollo de algoritmos.EstadosLos estados son una caracterización de la situación en que sehalla el sistema en un instante dado, dicha caracterización puedeser tanto cuantitativa como cualitativa [3].Matlab incorpora, además, otras librerías que son coleccionesde funciones especializadas y diseñadas para resolverproblemas muy específicos y que se pueden integrar confacilidad a proyectos y/o tecnologías externas [6].Procesos de decisión de MarkovUn proceso de decisión de Markov es similar a una cadena deMarkov con la diferencia que la matriz de transición depende dela acción tomada por un agente en cada paso del tiempo. Elobjetivo es hallar una función llamada política, la cualespecifica qué acción se va tomar en cada estado, de modo queoptimice alguna función de costo o de recompensa.Integración MATLAB y JAVAEn el modelo “recompensa esperada de la política D esnecesario encontrar los ʌi o probabilidades de estado estable dela matriz de transición asociada a una política, por esta razón seutilizó librerías de Matlab que fueran capaz de resolver sistemasde ecuaciones y así poder encontrar los ʌi solicitados.Los PDM proveen un marco matemático para modelarproblemas de decisión secuencial en ambientes dinámicosinciertos. Un PDM es una tupla (S,A,P,R) donde S es unconjunto finito de estados, A es un conjunto finito de acciones,P: S * A * S ĺ[0,1] es la función de probabilidad de transición,la cual asocia un conjunto de probables estados alcanzados auna acción dada en el estado en evaluación. R(S,A) denota larecompensa obtenida si se aplica la acción A en el estado S. D(s) denota una política (o estrategia) que produce una acciónpara cada estado, es una regla que especifican cuáles accionespodrían aplicarse en cada caso[3].La integración de MATLAB y JAVA que se utilizó está basadaen crear un componente en Matlab que reciba una matriz detransición, solucione y retorne un vector columna con lasprobabilidades de estado estable. A continuación en la figura 1se muestra el diseño de cómo interactúan Matlab y java.DecisiónUna decisión es la unión de una matriz de transición y unamatriz de recompensa. La matriz de transición representa laprobabilidad de pasar de un estado i a un estado j y la matriz derecompensa representa la ganancia que se obtiene de pasar deun estado i a un estado j.PolíticaEs una regla que específica qué decisión tomar en cada estado.Un proceso de decisión de Markov tiene como mínimo (m) npolíticas, donde n son la cantidad de estados y m la cantidad dedecisiones que se pueden tomar en cada estado. Las políticaspueden depender del estado actual, de los estados pasados o deacciones externas.Figura 1. Interacción MATLAB y JAVA3. SOFTWARE PDM-RCEl software desarrollado que implementa el recocido simuladose desarrolló en java y los cálculos de la matriz de transición loshace matlab.Una política óptima es aquella que maximiza el valor esperadode recompensa total de un estado específico para cierto númerode transacciones [4].En la figura 2 se muestra el caso de uso general del softwarePDM-RC.Recompensa esperada de la política DEl siguiente modelo se conoce como Costo promedio esperado(a largo plazo) por unidad de tiempo. En la implementación deeste trabajo es utilizado para encontrar la recompensa de unapolítica “D” y por eso se han redefinido algunos conceptos quea continuación se pueden apreciar en la ecuación (1).nE ( R ( D )) Ria π i(1)i 1Donde:n es el número de estados.Ria es la recompensa de tomar la decisión a en el estado i.ʌi es la probabilidad de estado estable en i.Figura 2 Modelo de Caso de uso General PDM-RCMatlabes un potente lenguaje diseñado para la computación técnica.Matlab puede ser utilizado en computación matemática,modelado y simulación, análisis y procesamiento de datos,En el caso de uso general se puede apreciar la interacción delusuario con las funciones que dispone el prototipo y la formacomo el como el prototipo soluciona y responde internamente lasolicitud requerida.193

Memorias de la Décima Quinta Conferencia Iberoamericana en Sistemas, Cibernética e Informática (CISCI 2016)QLa Figura 3 presenta el modelo de interfaz que muestra como esla navegación a través del software.Año 16RAño 17SAño 18TAño 19Definición de decisionesPara este problema se definen 2 decisiones, cada decisión estáconformada por una matriz de transición y una matriz derecompensa.En la tabla 2 se representa la probabilidad de pasar de un estadoi a un estado j si se toma la decisión de mantener el carro en unmomento dado.Figura 3 Modelo de interfaz general PDM-RC3.Tabla 2. Matriz de transición para la decisión de mantenerel carroPROBLEMA DEL REEMPLAZO DEL AUTOMOVILUna persona desea revisar cada año el estado y los costos quetienen su carro y así tomar una decisión de mantener el actualcarro o negociarlo por uno nuevo en ese momento.El estado del sistema, i, es descrito por la edad del carro; ipuede ir desde 0 hasta 19(o desde el estado A hasta el estado T).A fin de mantener, el número de estados finitos, un carro deedad 19 permanece como un carro de edad 19 por siempre (Esconsiderado que ya está gastado). Las alternativas disponiblesen cada estado son dos, mantener el carro actual o negociarlopor uno nuevo. En el estado 0 como el carro es nuevo, no esfactible tomar la decisión de negociarlo. Así las cosas, tenemos20 estados en los cuales se pueden tomar dos decisionesposibles, de modo que hay 2 20 posibles políticas, lo que esmás de un billón de políticas.En la tabla 3 se representa la recompensa de pasar de un estado ia un estado j si se toma la decisión de mantener el carro en unmomento dado.Definición de estadosPara este problema se definen 20 estados, la tabla 1 se puedever la representación y definición de cada uno.Tabla 3. Matriz de recompensas para la decisión demantener el carroTabla 1. Conjunto de estados para el problema delreemplazo de automovilEstadoCondiciónAAño 0BAño 1CAño 2DAño 3EAño 4FAño 5GAño 6HAño 7IAño 8JAño 9KAño 10LAño 11MAño 12NAño 13OAño 14PAño 15En la tabla 4 se representa la probabilidad de pasar de un estadoi a un estado j si se toma la decisión de negociar el carro entodos los estados.194