Uso da Otimização de Malhas Variáveis para o 'Viajante do Comércio'
| Autor: | Byron Oviedo, Cristian Zambrano-Vega, Amilkar Puris |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Revista Lasallista de Investigación, Volume: 15, Issue: 2, Pages: 210-222, Published: DEC 2018 |
| ISSN: | 2256-3938 1794-4449 |
| DOI: | 10.22507/rli.v15n2a16 |
| Popis: | espanolResumen Introduccion:. En este trabajo se presenta una propuesta para aplicar la meta-heuristica Optimizacion Basada en Mallas Variables (VMO) al problema discreto del Viajero Vendedor (TSP); este modelo explora el espacio de busqueda a Objetivo partir de una poblacion de soluciones llamada malla que se expande y contrae con la finalidad de encontrar soluciones de buena calidad. En este contexto se modifica el operador de expansion de manera tal que sea aplicable en un dominio discreto, realizando combinaciones entre las soluciones a fin de obtener nuevos nodos. Otro de los elementos que se modifica es el operador de clearing, el cual se encarga de mantener la diversidad de la malla en cada interaccion. Metodologia: Se resume en este trabajo un estudio de parametros del modelo VMO utilizando un conjunto de instancias de TSP con diferentes caracteristicas; ademas, se puede observar que la propuesta de este trabajo obtiene Resultados: competitivos al compararlos con otros algoritmos de referencia internacional mencionado en el estado del arte. El trabajo esta estructurado de la siguiente manera: En el apartado 1 se describe los aspectos fundamentales de problema de estudio TSP. Seguidamente en el segundo se explica el funcionamiento general de VMO, en el tercero se define cada uno de los operadores de expansion y contraccion para el problema de estudio. Posteriormente en el apartado cuarto se realiza un estudio de parametros de la propuesta y un analisis comparativo experimental con los resultados obtenidos con otros algoritmos mencionado en el estado del arte. Conclusiones: Se aplicaron otros operadores de generacion de nuevos nodos en el proceso de expansion, donde se realiza una combinacion de soluciones de manera que cumpla con las restricciones impuestas por el problema. EnglishAbstract Introduction: This paper presents a proposal to apply the meta-heuristic Optimization Based on Variable Meshes (VMO) to the discreet problem of the Traveler Seller (TSP); This model explores the search space to Objective from a population of solutions called mesh that expands and contracts in order to find good quality solutions. In this context, the expansion operator is modified in such a way that it is applicable in a discrete domain, making combinations among the solutions in order to obtain new nodes. Another element that is modified is the clearing operator, which is responsible for maintaining the diversity of the mesh in each interaction. Methodology: A study of VMO model parameters is summarized in this paper, using a set of TSP instances with different characteristics; In addition, it can be observed that the proposal of this work obtains competitive results when compared with other international reference algorithms mentioned in the state of the art. The work is structured as follows: Section 1 describes the fundamental aspects of the TSP study problem. Then, in the second, the general functioning of VMO is explained, in the third one, each of the expansion and contraction operators is defined for the study problem. Later in the fourth section a study of the parameters of the proposal and an experimental comparative analysis with the results obtained with other algorithms mentioned in the state of the art is made. Conclusions: Other operators of generation of new nodes were applied in the expansion process, where a combination of solutions is made in order to comply with the restrictions imposed by the problem. portuguesResumo Introducao: Este artigo apresenta uma proposta para aplicar a Otimizacao meta-heuristica Baseada em Malhas Variaveis (VMO) ao problema discreto do Vendedor Vendedor (TSP); Esse modelo explora o espaco de pesquisa para o Objective a partir de uma populacao de solucoes chamada malha que se expande e se contrai para encontrar solucoes de boa qualidade. Neste contexto, o operador de expansao e modificado de tal maneira que e aplicavel em um dominio discreto, fazendo combinacoes entre as solucoes para obter novos nos. Outro elemento que e modificado e o operador de limpeza, que e responsavel por manter a diversidade da malha em cada interacao. Metodologia: Um estudo dos parâmetros do modelo VMO e resumido neste artigo, usando um conjunto de instâncias do TSP com diferentes caracteristicas; Alem disso, pode-se observar que a proposta deste trabalho obtem resultados competitivos quando comparados com outros algoritmos de referencia internacionais mencionados no estado da arte. O trabalho esta estruturado da seguinte forma: a secao 1 descreve os aspectos fundamentais do problema do estudo TSP. Entao, no segundo, o funcionamento geral do VMO e explicado, no terceiro, cada operador de expansao e contracao e definido para o problema do estudo. Posteriormente na quarta secao e feito um estudo dos parâmetros da proposta e uma analise comparativa experimental com os resultados obtidos com outros algoritmos mencionados no estado da arte. Conclusoes: Outros operadores de geracao de novos nos foram aplicados no processo de expansao, onde uma combinacao de solucoes e feita a fim de cumprir as restricoes impostas pelo problema. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|