Made available in DSpace on 2014-12-17T14:55:03Z (GMT). No. of bitstreams: 1
IloneideCOR.pdf: 1010601 bytes, checksum: 76bbc04aa0a456f079121fb0d750ea74 (MD5)
Previous issue date: 2005-03-03 / The problems of combinatory optimization have involved a large number of researchers in search of approximative solutions for them, since it is generally accepted that they are unsolvable in polynomial time. Initially, these solutions were focused on heuristics. Currently, metaheuristics are used more for this task, especially those based on evolutionary algorithms. The two main contributions of this work are: the creation of what is called an -Operon- heuristic, for the construction of the information chains necessary for the implementation of transgenetic (evolutionary) algorithms, mainly using statistical methodology - the Cluster Analysis and the Principal Component Analysis; and the utilization of statistical analyses that are adequate for the evaluation of the performance of the algorithms that are developed to solve these problems. The aim of the Operon is to construct good quality dynamic information chains to promote an -intelligent- search in the space of solutions. The Traveling Salesman Problem (TSP) is intended for applications based on a transgenetic algorithmic known as ProtoG. A strategy is also proposed for the renovation of part of the chromosome population indicated by adopting a minimum limit in the coefficient of variation of the adequation function of the individuals, with calculations based on the population. Statistical methodology is used for the evaluation of the performance of four algorithms, as follows: the proposed ProtoG, two memetic algorithms and a Simulated Annealing algorithm. Three performance analyses of these algorithms are proposed. The first is accomplished through the Logistic Regression, based on the probability of finding an optimal solution for a TSP instance by the algorithm being tested. The second is accomplished through Survival Analysis, based on a probability of the time observed for its execution until an optimal solution is achieved. The third is accomplished by means of a non-parametric Analysis of Variance, considering the Percent Error of the Solution (PES) obtained by the percentage in which the solution found exceeds the best solution available in the literature. Six experiments have been conducted applied to sixty-one instances of Euclidean TSP with sizes of up to 1,655 cities. The first two experiments deal with the adjustments of four parameters used in the ProtoG algorithm in an attempt to improve its performance. The last four have been undertaken to evaluate the performance of the ProtoG in comparison to the three algorithms adopted. For these sixty-one instances, it has been concluded on the grounds of statistical tests that there is evidence that the ProtoG performs better than these three algorithms in fifty instances. In addition, for the thirty-six instances considered in the last three trials in which the performance of the algorithms was evaluated through PES, it was observed that the PES average obtained with the ProtoG was less than 1% in almost half of these instances, having reached the greatest average for one instance of 1,173 cities, with an PES average equal to 3.52%. Therefore, the ProtoG can be considered a competitive algorithm for solving the TSP, since it is not rare in the literature find PESs averages greater than 10% to be reported for instances of this size. / Os problemas de otimiza??o combinat?ria t?m envolvido um grande n?mero de pesquisadores na busca por solu??es aproximativas para aqueles, desde a aceita??o de que eles s?o considerados insol?veis em tempo polinomial. Inicialmente, essas solu??es eram focalizadas por meio de heur?sticas. Atualmente, as metaheur?sticas s?o mais utilizadas para essa tarefa, especialmente aquelas baseadas em algoritmos evolucion?rios. As duas principais contribui??es deste trabalho s?o: a cria??o de uma heur?stica, denominada Operon, para a constru??o de cadeias de informa??es necess?rias ? implementa??o de algoritmos transgen?ticos (evolucion?rios) utilizando, principalmente, a metodologia estat?stica - An?lise de Agrupamentos e An?lise de Componentes Principais -; e a utiliza??o de an?lises estat?sticas adequadas ? avalia??o da performance de algoritmos destinados ? solu??o desses problemas. O Operon visa construir, de forma din?mica e de boa qualidade, cadeias de informa??es a fim de promover uma busca -inteligente- no espa?o de solu??es. O Problema do Caixeiro Viajante (PCV) ? focalizado para as aplica??es que s?o realizadas com base num algoritmo transgen?tico, denominado ProtoG. Prop?e-se, tamb?m, uma estrat?gia de renova??o de parte da popula??o de cromossomos indicada pela ado??o de um limite m?nimo no coeficiente de varia??o da fun??o de adequa??o dos indiv?duos, calculado com base na popula??o. S?o propostas tr?s an?lises estat?sticas para avaliar a performance de algoritmos. A primeira ? realizada atrav?s da An?lise de Regress?o Log?stica, com base na probabilidade de obten??o da solu??o ?tima de uma inst?ncia do PCV pelo algoritmo em teste. A segunda ? realizada atrav?s da An?lise de Sobreviv?ncia, com base numa probabilidade envolvendo o tempo de execu??o observado at? que a solu??o ?tima seja obtida. A terceira ? realizada por meio da An?lise de Vari?ncia n?o param?trica, considerando o Erro Percentual da Solu??o (EPS) obtido pela percentagem em que a solu??o encontrada excede a melhor solu??o dispon?vel na literatura. Utiliza-se essa metodologia para a avalia??o da performance de quatro algoritmos, a saber: o ProtoG proposto, dois algoritmos mem?ticos e um algoritmo Simulated Annealing. Foram realizados seis experimentos, aplicados a sessenta e uma inst?ncias do PCV euclidiano, com tamanhos de at? 1.655 cidades. Os dois primeiros experimentos tratam do ajuste de quatro par?metros utilizados no algoritmo ProtoG, visando melhorar a performance do mesmo. Os quatro ?ltimos s?o utilizados para avaliar a performance do ProtoG em compara??o aos tr?s algoritmos adotados. Para essas sessenta e uma inst?ncias, conclui-se, sob testes estat?sticos, que h? evid?ncias de que o ProtoG ? superior a esses tr?s algoritmos em cinq?enta inst?ncias. Al?m disso, para as trinta e seis inst?ncias consideradas nos tr?s ?ltimos experimentos, nos quais a avalia??o da performance dos algoritmos foi realizada com base no EPS, observou-se que o ProtoG obteve EPSs m?dios menores que 1% em quase metade das inst?ncias, tendo atingido a maior m?dia para uma inst?ncia composta por 1.173 cidades, com EPS m?dio igual a 3,52%. Logo, o ProtoG pode ser considerado um algoritmo competitivo para solucionar o PCV, pois n?o ? raro serem reportados, na literatura, EPSs m?dios maiores que 10% para inst?ncias desse porte.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/15175 |
| Date | 03 March 2005 |
| Creators | Ramos, Iloneide Carlos de Oliveira |
| Contributors | CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Luna, Henrique Pacca Loureiro, CPF:21545073872, http://lattes.cnpq.br/4967240163248619, Gouv?a, Elizabeth Ferreira, CPF:81652011749, http://lattes.cnpq.br/2888641121265608, Melo, Jorge Dantas de, CPF:09463097449, http://lattes.cnpq.br/7325007451912598, D?ria Neto, Adri?o Duarte, Goldbarg, Marco C?sar |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Engenharia El?trica, UFRN, BR, Automa??o e Sistemas; Engenharia de Computa??o; Telecomunica??es |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds