4. Findings
4.3. Validation of Measures
Além do que foi estudado neste trabalho, considera-se que há muito a ser pesquisado com relação a este tema. Apresentam-se, portanto, algumas sugestões para estudos futuros:
o A estratégia de renovação da população adotada neste trabalho pode ser utilizada em outros algoritmos evolucionários a fim de se avaliar a performance desses algoritmos baseados nessa estratégia. Esse estudo pode levar em conta o ajuste dos parâmetros envolvidos no uso dessa estratégia sob alguns aspectos, como, por exemplo: permitir a redução do CVMF durante o processamento do algoritmo; estudar o nível ideal para esse CVMF, com base em algum valor fixo, como o tamanho da população, o tamanho da instância ou uma relação entre esses dois valores; ajustar o número de iterações para o teste do CVMF e o percentual de indivíduos que devem ser renovados; etc.;
o Explorar as boas características apontadas para os construtores de cadeias de PGM estudadas, no sentido de oferecer mais tempo de processamento ou de implementar algoritmos paralelos, permitindo que o aumento do tamanho da população – que apresentou evidências de efeito sobre a probabilidade de obtenção da solução ótima para instâncias pequenas – possa ser aplicado às instâncias grandes. Esse estudo é viável visto que, para muitas instâncias, se observou que ocorria melhora na solução pouco tempo antes do final do processamento do ProtoG limitado pelo tempo máximo de execução fornecido; o Estudar as evidências dessas boas características apontadas de forma individual,
ou seja, para cada construtor de cadeia proposto neste trabalho;
o Realizar a avaliação da performance de algoritmos, adotando vários modelos e testes de hipóteses disponíveis na metodologia estatística, explorando, além dos que foram apresentados (com variações no planejamento do experimento), muitos outros possíveis, na busca de modelos bem ajustados, considerando a diversidade de comportamento das instâncias frente à aplicação dos algoritmos;
o A Análise de Sobrevivência estudada levou em conta a observação do tempo de processamento até que a solução ótima fosse alcançada. Essa iniciativa não permite que a performance de algoritmos, para instâncias grandes, seja avaliada dessa forma, devido à escassez ou mesmo falta de execuções que produzam esse resultado. Uma simples alteração no planejamento do experimento pode incentivar novos estudos: a observação do tempo de processamento até que um EPS mínimo especificado seja atingido. Dessa forma, é possível a avaliação da performance entre algoritmos aplicados às instâncias grandes a partir do teste de hipótese baseado na função de sobrevivência definida sob esse tempo.
REFERÊNCIAS
AARTS, E. H. L.; KORST, J. H. M.; LAARHOVEN, P. J. M. A quantitative analysis of the
simulated annealing algorithm: a case study for the traveling salesman problem. J. Stats. Phys, 50, p. 189-206, 1988.
AGRESTI, A. An introduction to categorical data analysis. New York: John Wiley & Sons, 1996. AHUJA, R. K.; ORLIN, J. B.; TIVARI, A. A greedy genetic algorithm for the quadratic
assignment problem. Computers and Operations Research, v. 27, n. 10, p. 917-934, 2000. ANDERBERG, M. R. Cluster analysis for applications. New York: Academic Press, 1973. ANDERSON, T. W. An introduction to multivariate statistical analysis. New York: John Wiley & Sons, 1958.
ANGELINE, P. J. Adaptive and self-adaptive evolutionary computation. In: PALANISWAMI, Y. et al. (Ed.) Computation intelligence: a dynamic system perspective. Piscataway: IEEE Press, 1995. p. 152-163.
APPLEGATE, D. et al. On the solution of traveling salesman problems. Documenta
Mathematica, p. 645-658, 1998. Extra Volume, ICM III.
APPLEGATE, D. et al. TSP Cuts which do not conform to the template paradigm. In: JÜNGER, M.; NADDEF, D. (Ed.) Computational combinatorial optimization. Springer, 2001. p. 261-304. BECKER, T. J. No accidental tourist. 2004. Disponível em: <http://gtresearchnews.gatech.edu/ reshor/rh-f04/tsp.html>.
BERKSON, J. Application of the logistic function to bioassay. Journal of the American Statistical
Association, 39, p. 357-365, 1944.
BERSINI, H.; RENDERS, B. Hybridizing genetic algorithms with hill-climb methods for global optimization: two possible ways. In: INTERNATIONAL SYMPOSIUM EVOLUTIONARY COMPUTATION, 1994. Proceedings… Orlando: IEEE,1994. p. 312-317.
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. São Paulo: Edgard Blücher, 1996.
BOLDRINI, J. L. et al. Álgebra linear. 3. ed. São Paulo: HARBRA,1986.
BORÜVKA, O. O jistém problému minimálním. (Czech). Acta Societ. Scient. Natur. Moravicae, 3, p. 37-58, 1926a.
BORÜVKA, O. Príspevek k reseníotázky economické stavby elektrovodnich sítí (Czech).
Elecktrotechniky obzor, 15, p. 153-154, 1926b.
BUCCI, M. Optimization with simulated annealing. C/C++ Users Journal, 19, p. 10-27, 2001. BULLNHEIMER, B.; HARTL, R. F.; STRAUSS, C. A new rank based version of the ant system: a computational study. Central European Journal for Operations Research and Economics, v. 7, n. 1, p. 25-38, 1999.
BURIOL, L. S., FRANÇA, P. M., MOSCATO, P. A new memetic algorithm for the asymmetric traveling salesman problem. Journal of Heuristics, v. 10, n. 5, p. 483-506, 2004.
BUSSAB, W. O.; MIAZAKI, E. S.; ANDRADE, D. F. Introdução à análise de agrupamentos. In: SIMPÓSIO BRASILEIRO DE PROBABILIDADE E ESTATÍSTICA, 9. 1990, São Paulo. Anais… São Paulo: ABE, IME – USP, 1990.
CAMPELLO, R. E.; MACULAN, N. Algoritmos e heurísticas: desenvolvimento e avaliação de performance. Niterói: Editora da Universidade Federal Fluminense,1994.
CAMPOS, V.; LAGUNA, M.; MARTÍ, R. Context-independent scatter and tabu search for
permutation problems. Technical Report, TR03-2001, University of Valencia, 2001.
CERNY, V. Thermodynamical approach to the traveling salesman problem: an efficient
simulation algorithm. Journal of Optimization Theory an Application, v. 45, n. 1, p. 41-51, 1985. CHARTRAND, G.; OELLERMANN, O. R. Applied and algorithmic graph theory. New York: McGraw-Hill, 1993.
CHATFIELD, C.; COLLINS, A. J. Introduction to multivariate analysis. London: Chapman and Hall, 1980.
CLERGUE, M.; COLLARD, P. Genetic heuristic for search space exploration. In:
INTERNATIONAL ARTIFICIAL INTELLIGENCE, 1999. Proceedings… San Mateo: Morgan Kaufmann, 1999. p. 1218-1224.
COCHRANE, E. M.; BEASLEY, J. E. The co-adaptive neural network approach to the euclidean travelling salesman problem. Neural Networks, Oxford: Elsevier Science, 16, p. 1499-1525, 2003.
COELLO, C. A. C.; BECERRA, R. L. Evolutionary multiobjective optimization using a cultural algorithm. In: IEEE SWARM INTELLIGENCE SYMPOSIUM, 2003. Proceedings… Indianapolis:
IEEE Service Center, 2003. p. 6-13.
COLLETT, D. Modelling binary data. London: Chapman & Hall, 1991.
COLLETT, D. Modelling survival data in medical research. London: Chapman & Hall, 1991. CONOVER, W. J. Practical nonparametric statistics. 2. ed. New York: Wiley, 1980.
COOK, S. A. The complexity of theorem, proving procedures. In: ACM SYMPOSIUM ON THEORY OF COMPUTING, 3., 1971. Proceedings… New York, 1971, p. 151-158.
CROWDER, H.; PADBERG, M. W. Solving large scale symmetric traveling salesman problems to optimality. Management Science, 26, p. 495-509, 1980.
DAWKINS, R. The Selfish Gene. Oxford: Oxford University Press, 1976.
DEMÉTRIO, C. G. B. Modelos lineares generalizados em experimentação agronômica. 2002. Disponível em: <http://www.lce.esalq.usp.br/clarice/Apostila.pdf>.
DOBSON, A. J. An introduction to statistical modelling. 2. ed. London: Chapman & Hall,1990. DYKE, G. V.; PATTERSON, H. D. Analysis of factorial arrangements when the data are proportions. Biometrics, 8, p. 1-12,1952.
FEO, T. A.; RESENDE M. G. C. Greedy randomized adaptive search procedures. Journal of
Global Otimization, 6, p. 109-133, 1995.
FIECHTER, C. N. A parallel tabu search algorithm for large scale traveling salesman problems. Working Paper 90/1, Department of Mathematics, Ecole Polytechnique Federale de Lausanne,
Switzerland, 1990.
FLEURENT, C; FERLAND, J. A. Genetic hybrids for the quadratic assignment problem. In: PARDALOS, P. M.; WOLKOWICZ, H. (Ed.) Quadratic assignment and related problems. American Mathematical Society, 1994.
FREISLEBEN, B.; MERZ, P. New genetic local search operators for the traveling salesman problem. In: CONFERENCE ON PARALLEL PROBLEM SOLVING FROM NATURE, 4.,1996.
Proceedings… Springer-Verlag Lecture Notes in Comput. Sci, 1996, p. 890-899.
GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to the theory of NP- completeness. San Francisco: Freeman, 1979.
GOLDBARG, M. C.; GOLDBARG, E. F. G. Transgenética computacional: uma aplicação ao problema quadrático de alocação. Pesquisa Operacional, v. 22, n. 3, p. 359-386, 2002. GOLDBARG, M. C.; GOUVÊA, E. F. Computational transgenetic. In: CONGRESSO
LATINOIBERO-AMERICANO DE INVESTIGACIÓN OPERACIONES Y SISTEMAS, 10., 2000.
Anais… 2000.
GOLDBARG, M. C.; LUNA, H. P. L. Programação linear e otimização combinatória: modelos e algoritmos. Rio de Janeiro: Campus, 2000.
GOLDBARG, M. C.; GOUVÊA, E. F.; MEDEIROS NETO, F. D. Piston pump mobile unity tour problem: an evolutionary view. In: GENETIC AND EVOLUTIONARY COMPUTATION
CONFERENCE, 2002, New York. Proceedings… San Francisco: Morgan Kaufmann Publishers, 2002. p. 1264-1264.
GOLDBARG, M. C.; GOUVÊA, E. F.; SILVA, L. M. A transgenetic approach for the graph coloring problem. In: EUROPEAN OPERATIONAL RESEARCH CONFERENCE, 2001,
Proceedings… Rotterdan, 2001.
GOLDBERG, D. E. Genetic algorithms in search, optimization, and machine learning. New York: Addison Wesley, 1989.
GOLDBERG, D. E.; KORB, B.; DEB, K. Messy genetic algorithms: motivation, analysis, and first results. Complex Systems, 3, p. 493–530, 1990.
GOUVÊA, E. F. Transgenética computacional: um estudo algorítmico. 2001. Tese (Doutorado) – Universidade Federal do Rio d Janeiro, Rio de Janeiro, 2001.
GOUVÊA, E. F., e GOLDBARG M. C. A transgenetic algorithm applied to the quadratic assignment problem. Journal of Heuristics . Submetido em 2003.
GOWER, J. C.; ROSS, G. J. S. Minimum spanning trees and single linkage cluster analysis.
Applied Statistic, v. 18, n. 1, p. 54-64, 1969.
GUTIN, G.; PUNNEN, A. P. (Ed.) Traveling salesman problem and its variations. Kluwer Academic Publishers, 2002.
HAMERSLEY, J. M.; HANDSCOMB, D. C. Monte carlo method. Londres: Merthuen, 1964. HANDA, H. et al. Genetic algorithm involving coevolution mechanism to search for effective genetic information. In: INTERNATIONAL CONFERENCE ON EVOLUTIONARY
HANSEN P.; MLADENOVIĆ, N. Variable neighborhood search in state-of-the-art. GLOVER, F.; KOCHENAGEN, G. (Ed.) Handbook of Metaheuristics. Dordrecht: Kluwer Academic Publishers, 2003 Disponível em: <http://www.crpc.rice.edu/CRPC/newsAchive/techweb_6_29_ 98.htm>. HANSEN, N.; OSTERMEIER, A. Completely derandomized self adaptation in evolution strategies. Evolutionary Computation, v. 9, n. 2, p. 159-195, 2001.
HAREL, D. Algorithmics: the spirit of computing. MA: Addison-Wesley, 1987.
HAYKIN, S. Redes Neurais: princípios e prática. Tradução de P. M. Engel. 2 ed. Porto Alegre: Bookman, 2001.
HINTERDING, R. Self-adaptation using multi-chromosomes. IEEE, 73, p. 87-91, 1997.
HOLLAND, J. H. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
HORN J.; GOLDBERG, D. E. Genetic algorithm difficulty and modality of fitness landscapes. In: WHITLEY, L. D.; VOSE, M. D. (Ed.) Foundations of genetic algorithms, San Mateo: Morgan Kaufmann, 1995, 3, p. 243-269.
HOTELLING, H. Analysis of a complex of statistical variables into principal components.
Journal of Educational Psychology, 24, p. 417-441, 498-520, 1933.
JOLLIFFE, I. T. Principal component analysis. New York: Springer-Verlag, 1986.
JONHSON, R. A.; WICHERN, D. W. Applied multivariate statistical analysis. 3. ed. New Jersey: Pretince-Hall, Englewood Cliffs, 1982.
JOYCE, G. F. RNA evolution and the origins of life. Nature, 338, p. 217-223, 1989.
JÜNGER, M.; REINELT, G.; RINALDI, G. The traveling salesman problem. In: BALL, et al. (Ed.) Handbook on operations research and the management sciences. North Holland Press, 1994. p. 225-330.
KAPLAN, E. L.; MEIER P. Nonparametric estimation from incomplete observations. Journal of
American Statistical Association, 53, p. 457-481, 1958.
KARHUNEN, K. Uber lineare methodem in der wahrscheinlichkeitsrechnung. Annales
Academiae Scientiarum Fennicae, Series AI: Mathematica-Physica, 37, 1947. p. 3-9. Tradução
de RAND Corp., Santa Monica, CA, Rep. T-131, 1960.
KARLSSON, P. Simulated annealing applied to the traveling salesman problem: report of Uppsala University, 2002. Disponível em: <http://peg.it.uu.se/~saps02/ PatrickKarlsson/> KARP, R. M. Reducibility among combinatorial problems. In: MILLER, R. E.; THATETCHER, J. W. (Ed.), Complexity of Computer Computation. New York: Plenun Press, 1972.
KATAYAMA, K.; SAKAMOTO, H. The efficiency of hybrid mutation genetic algorithm for the traveling salesman problem. Mathematical and Computer Modelling, 31, p. 197-203, 2000. KIRKPATRICK, S.; GELATT JÚNIOR., C. D.; VECCHI, M. P. Optimization by simulated annealing. Science, 4598, 1983.
KNOX, J. Tabu search performance on the symmetric traveling salesman problem. Computers
KRASNOGOR, N.; SMITH, J. A memetic algorithm with self-adaptive local search: TSP as a case study. In: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2000.
Proceedings… San Francisco: Morgan Kaufmann Publishers, 2000. p. 987-994.
KRUSKAL JÚNIOR., J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7, p. 48-50, 1956. KRUSKAL, W. H.; WALLIS, W. A. Use of ranks in one criterion variance analysis. Journal of
the American Statistical Association, 47, p. 583-621, 1952.
LAWLER, E. L. et al. (Ed.) The traveling salesman problem. Chichester: John Wiley, 1985. LAY, D. C. Álgebra linear e suas aplicações. Tradução de R. Camelier e V. M. Lório. 2. ed. Rio de Janeiro: Livros Técnicos e Científicos, 1999.
LOÈVE, M. Probability theory. 3. ed. New York: Van Nostrand, 1963.
MANTEL, N.; HAENSZEL, W. Statistical spects of the analysis of data from retrospective studies of disease. Journal of the National Cancer Institute, 22, p. 719-748, 1959.
MARJAN, M.; MATEJ, C.; VILJEM, Z. A metaevolutionary approach in searching of the best combination of crossover operators for the TSP. In: INTERNATIONAL CONFERENCE
NEURAL NETWORKS, 2000. Proceedings… Anaheim; Calgary; Zürich: IASTED/ACTA Press, 2000. p. 32-36.
MATHIAS, K.; WHITLEY, D. Genetic operators, the fitness landscape and the traveling salesman problem. In: MÄNNER, R.; MANDERICK, B. (Ed.) Parallel problem solving from
nature II. Berlin: Springer-Verlag, 1992. p. 221-230.
MAYLEY, G. Guiding or hiding: explorations into the effects of learning on the rate of evolution. School of Cognitive and Computing Science, University of Sussex, Brighton, England, 1997. McCULLOCH, C. E.; SEARLE, S. R. Generalized, linear and mixed models. New York: John Wiley & Sons, 2000.
MERZ, P.; FREISLEBEN, B. Memetic algorithms for the traveling salesman problem. Complex
system, 11, p. 1-49, 1997.
MERZ, P.; FREISLEBEN, B. Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation, v. 4, n. 4, p. 337-352, 2000.
METROPOLIS, N. et al. Equation of state calculation by fast computing machines. Journal
Chemical Physics, 21, p. 1087-1091, 1953.
MICHALEWICZ, Z. e FOGEL, D. B. How to solve it: modern heuristics, New York: Springer- Verlag, 2000.
MONTGOMERY, D. C. Design and analysis of experiments. 4. ed. New York: John Wiley & Sons, 1997.
MOSCATO, P. On evolution, search, optimization, genetic algorithms and martial arts. Caltech
Concurrent Computation Program. California Institute of Technology. p. 158-179, 1989.
MÜHLENBEIN, H.; MAHNIG, T. Evolutionary computation and beyond. In: UESAKA, Y.; KANERVA, P.; ASOH, H. (Ed.) Foundations of real-world intelligence. Stanford: CLSI Publications, 2001. p. 123-186.
MÜHLENBEIN, H.; VOOSEN, D. S. Analysis of selection, mutation and recombination in genetic algorithms: evolution as a computational process. In: BANZHAF, W.; EECKMAN, F. H. (Ed.) Lecture Notes in Computer Science, 899. Berlin: Springer, 1995. p. 142-168.
NELDER, J. A.; WEDDERBURN, R. W. N. Generalized linear models. Journal of the Royal
Statistical Society, A, v. 135, n. 3, p. 370-384, 1972.
NOLFI, S.; FLOREANO, D. Learning and evolution. Autonomous Robots, v. 7, n. 1, p. 89-113, 1999.
PAPOULIS, A. Probability, random variables, and stochastic process. Singapore: McGraw-Hill, 1984.
PARDALOS, L. Y.; RESENDE, M. G. C. A greedy randomized adaptive search procedure for the quadratic assignment problem, DIMACS Series, Discrete Mathematics and Theoretical
Computer Science, 16, p. 237-261, 1994.
PEARSON, K. On a criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can reasonably supposed to have arisen from random sampling. Philos. Mag., Ser. 5, 50, p. 157-175, 1900.
PEARSON, K. On lines and planes of closest fit to system of points in space. Philosophical
Magazine, 2, p. 559-572, 1901.
POTVIN, J. V. The traveling salesman problem: a neural network perspective. INFORMS
Journal on Computing, 5, p. 328-348, 1993.
POTVIN, J. V. Genetic algorithms for the traveling salesman problem. Annals of Operations
Research, 63, p. 339-370, 1996.
PREISENDORFER, R. W. Principal component analysis in meteorology and oceanography. New York: Elsevier, 1988.
PRIM, R. C. Shortest connection networks and some generalizations. Bell Systems Technical
Journal, 36, p. 1389-1401, 1957.
RADCLIFFE, N. J.; SURRY, P. D. Formal memetic algorithms. In: FOGARTY, T. C. (Ed.)
Evolutionary computing: AISB Workshop. Berlin: Springer-Verlag, 1994.
RAMOS, I. C. O., et al. A ProtoG algorithm applied to the traveling salesman problem. In: INTERNATIONAL CONFERENCE OF THE CHILLEAN COMPUTER SCIENCE SOCIETY, 23., 2003, Chillán. Proceedings … Washington: IEEE, 2003. p. 23-30.
REINELT, G. The traveling salesman: computational solutions for TSP applications. Berlin: Springer-Verlag, 1994.
REINELT, G. TSPLIB, 1995. Disponível em: <http://www.iwr.uni-heidelberg.de/iwr/comopt/ software/TSPLIB95/>
REYNOLDS, R. An introduction to cultural algorithms. In: ANNUAL CONFERENCE ON EVOLUTIONARY PROGRAMMING, 3., 1994. Proceedings… River Edge: World Scientific, 1994. p. 131-139.
Statistical Analysis System INSTITUTE INC. SAS user’s guide. Cary: SAS Institute Inc, 1988. SCHMITT, L. J.; AMINI, M. M. Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: an empirical study.
SIEGEL, S. Estatística não paramétrica. Tradução de A. A. Farias. São Paulo: McGraw-Hill do Brasil, 1975.
SOKAL, R. R.; SNEATH, P. H. A. Principles of numerical taxonomy. London: Freeman, 1963. SPECTOR L.; LUKE, S. Culture enhances the evolvability of cognition. In: COGNITIVE SCIENCE CONFERENCE, 1996. Proceedings… Disponível em: <http://www.cs.umd.edu/ users/seanl/papers/culture-cogsci.pdf>.
STOKES, M. E.; DAVIS, C. S.; KOCH, G. G. Categorical data analysis using the SAS System. Cary: SAS Institute, 1999.
VAVAK, F.; JUKES, K. A.; FORGARTY, T. C. Performance of a genetic algorithm with variable local search range relative to frequency of the environmental changes. In: ANNUAL
CONFERENCE OF GENETIC PROGRAMMING, 3., 1998. Proceedings… 1998.
VENABLES, W. N.; RIPLEY, B. D. Modern applied statistics with S-PLUS. 2. ed. New York: Springer-Verlag, 1997.
VIANA, G. V. R. Meta-heurísticas e programação paralela em otimização combinatória. Fortaleza: Edições UFC, 1998.
WAH, B. W.; IEUMWANANONTHACHAI Teacher: a genetics-based system for learning and for generalizing heuristics. In: YAO, X. (Ed.) Evolutionary computation: theory and applications. Singapore: World Scientific, 1999.
WALD, A. Tests of statistical hypotheses concerning several parameters when the number of observations is large. Trans. Amer. Math. Soc., 54, p. 426-482, 1943.
WHITLEY, D. Modeling hybrid genetic algorithms. In: WINTER, G. et al. (Ed.) Genetic
algorithms in engineering and computer science. New York: Wiley, 1995. p. 191-201.
WOLPERT, D. H.; MACREADY, W. G. No free lunch theorems for optimization. IEEE
Transactions on Evolutionary Computation, 1, p. 67-82, 1997.
YAO, X. Evolutionary computation: theory and applications. Singapore: World Scientific, 1999. YAO, X. An overview of evolutionary computation, Chinese Journal of Advanced Software
Research, v. 3, n. 1, p. 12-29, 1996.
ZAHN, C. T. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE
APÊNDICES
APÊNDICE A. A
PLICAÇÃO DAA
NÁLISE DEA
GRUPAMENTOSExemplo A.1: A Tabela A.1 apresenta as junções obtidas com a execução, passo a passo, do algoritmo MLS (Quadro 3.2 – passos 6 a 12), para a instância eil76. A primeira coluna identifica o cluster Cj obtido em cada passo de repetição j. As duas colunas seguintes
mostram os números que identificam os clusters (de 1 a 76 – cidades e de 77 a 150 - conjunto de cidades) agrupados no passo de repetição j. A terceira coluna apresenta o nível de junção obtido no passo de repetição j. E, finalmente, na quarta coluna, se encontram as diferenças entre os níveis de junção verificados em dois passos consecutivos (não calculadas durante a execução do algoritmo MLS) – destacam-se (em cor cinza) as células em que se encontram as maiores diferenças observadas dentro de cada quarto de parte dessa coluna (pontilhado).
Tabela A.1. Algoritmo MLS executado passo a passo – eil76
j k l wj wj - wj-1 77 34 46 2,2361 - 78 3 44 3,0000 0,7639 79 75 76 3,0000 0,0000 80 9 39 4,1231 1,1231 81 27 52 4,1231 0,0000 82 15 57 4,2426 0,1195 83 41 42 4,2426 0,0000 84 81 77 4,4721 0,2295 85 29 45 4,4721 0,0000 86 83 43 4,4721 0,0000 87 60 70 4,4721 0,0000 88 68 79 4,4721 0,0000 89 7 35 5,0000 0,5279 90 89 8 5,0000 0,0000 91 90 84 5,0000 0,0000 92 80 72 5,0000 0,0000 93 92 58 5,0000 0,0000 94 38 65 5,0000 0,0000 95 62 73 5,0000 0,0000 96 78 32 5,0990 0,0990 97 6 88 5,0990 0,0000 98 12 40 5,0990 0,0000 99 33 95 5,0990 0,0000 100 87 71 5,0990 0,0000 101 1 99 5,3852 0,2861 102 4 97 5,3852 0,0000 103 102 67 5,3852 0,0000
(continuação) j k l wj wj - wj-1 104 103 91 5,3852 0,0000 105 104 26 5,6569 0,2717 106 23 56 5,8310 0,1741 107 93 10 6,0000 0,1690 108 18 50 6,0000 0,0000 109 20 100 6,0000 0,0000 110 101 63 6,0828 0,0828 111 110 16 6,0828 0,0000 112 109 37 6,0828 0,0000 113 21 47 6,3246 0,2418 114 113 48 6,3246 0,0000 115 111 28 6,4031 0,0786 116 115 74 6,4031 0,0000 117 105 85 6,4031 0,0000 118 117 114 6,4031 0,0000 119 118 36 6,4031 0,0000 120 119 51 6,4031 0,0000 121 120 17 6,4031 0,0000 122 116 30 6,7082 0,3051 123 122 86 6,7082 0,0000 124 121 5 6,7082 0,0000 125 124 98 6,7082 0,0000 126 123 2 7,0000 0,2918 127 125 53 7,0000 0,0000 128 127 14 7,0000 0,0000 129 107 94 7,0000 0,0000 130 126 128 7,0711 0,0711 131 130 13 7,0711 0,0000 132 131 112 7,0711 0,0000 133 129 11 7,0711 0,0000 134 24 49 7,0711 0,0000 135 132 69 7,2111 0,1400 136 96 133 7,2111 0,0000 137 135 19 7,2801 0,0690 138 136 66 7,2801 0,0000 139 138 108 7,6158 0,3357 140 137 54 7,8102 0,1945 141 140 139 8,0000 0,1898 142 141 82 8,0623 0,0623 143 142 22 8,0623 0,0000 144 143 25 8,2462 0,1840 145 144 64 9,0000 0,7538 146 145 106 9,2195 0,2195 147 146 134 9,2195 0,0000 148 147 55 9,2195 0,0000 149 148 61 10,0499 0,8303 150 149 59 10,6301 0,5803 151 150 31 13,4536 2,8235