TheTravelingSalesmanProblem(TSP)isaimportantoptimizationproblemincomputerscience, mathematics and logistics. It belongs to the class of NP-Hard problems and can be very time consumingtoﬁndsolutionstolargeinstanceswithguaranteeoptimality. Asnumberofcity-nodes inthegraphincreases,theamountofvalidroutetoursalsogrowthsrapidlyandthusrequiring considerabletimetoevaluateandclassifyeachpermutation. Theobjectiveoftheheuristicprocess is to search the solution space for the optimal solution while maximizing the attached utility-cost function (i.e. ﬁnding the shortest euclidean distance tour) and minimizing the computational time complexity of the algorithm. Manycomplexrealworldscenarioscanbereducedtoasimulationofasalesmantryingtoﬁnd the shortest (length) Hamiltonian (cycle) route in a euclidean super-graph G*. If each city-node is modeled as a input symbol in a communication channel represented by an output pair with consistent probabilities distribution thus an polynomial-time probabilistic algorithm can use this information to improve thesolution quality at the same rate of transmissionof information over the channel. InthispaperweexploreanquantitativestochasticprocessbasedinAlgorithmInformation Theory and the Shannon-Kelly criterion to ﬁnd valid near optimal solutions using a new growth- optimal strategyapplied tothe TSPproblem thathavestatisticallysigniﬁcant transmissionrate even when no encoding scheme is available, regardless of time-complexity of the problem. Previousheuristicssuchas2opt,GeneticAlgorithms(GA)andSimulatedAnnealing(SA) approach’stheTSPproblembyrelyingon aprioriknowledgeaboutthedatadistributioninorder to reduce the probability of error in ﬁnding the best candidate solution tour. In this work we propose a method that models the solution space boundaries of the TSP problem as a communication channel by means of Information Theory. We describe a search algorithmthatcheckforpatterns(i.einformationcontent)intheelementsofaconstrainedsolution space modeled as messages transmitted through communication systems. The boundaries of the searchspacearedeﬁnedbytheKolmogorovcomplexityofthecandidatesolutionssequences. We conclude with an discussion about the quality of the results and implications for general decision problem in Turing machines. Keywords: InformationTheory,AlgorithmComplexity,TuringMachine,TravelingSalesman Problem 1. Introduction 1.1. Hamiltonian Graphs, TSP Problem and Computational Complexity The computational complexity of an algorithm show how much resources are required to apply an algorithm.[ 5] In otherwordshowmuchtimeandmemoryarerequiredbyaTuringmachinetocompleteexecutionandcanbeinterpreted as a measure of diﬃculty of computing functions. [ 7] A measurement of computation complexity is big O notation. It can be deﬁned as: Let two functions f and g such as f(n) is O(g(n)) if there are positive numbers c and N such that f.n/<=cg.n/ for alln>=Nand is used to estimate the function growth tax (asymptotic complexity). [5] [6] ORCID(s): First Author et al.: Preprint submitted to Elsevier Page 1 of 34 TheTSPproblemisanimportantcombinatorialoptimization problem. Asmostof thedecisionproblems,it isin the class of NP-hard problems. Considerasalesmantravelingfromcitytocityandsomeofthemareconnected. Hisgoalistovisiteachcityexactly onceandgobacktotheﬁrstcitywhenheﬁnises. Thesalesmancanchoseanypathaslongasitsvalid(ievisiteachcity once andﬁnish at thecity ithas started thetour) he alsowants to minimizehis costbytaking theshortest route. This problem can be described as a weighted graph G where each city is a node (or vertex) and is connected by a weighted edge only if the two cities are connected by any kind of road, and this road do not cross any other city. The weigh value of the edge is deﬁned as the distance of the tour (roads) between cities. ForsymmetricTSP,asthenumberofnodes(orcities)increasesinthegraphG,thenumberofpossibletoursgrowth choice also increase and is exponential. If we consider N nodes, the function of the input size is fsize=..N*1/@_2/ This means that the number of elements an algorithm must evaluate to decide the problem is very large thus requiring considerable time and computational resources even for small instances of the problem.[3] An strategy to address this limitation is to accept near-optimal solutions by setting constrains in the problem (using heuristics methods)[ 4]. Algorithms such as 2opt, GA and SA deﬁne a*prioriknowledge about the distribution of the solutionspaceandthanrepetitivelytrytoimprovethequality. Itworksbyfollowingsomeheuristicfunctionschema whiletryingtoavoidalocalminimal. Astheheuristics(ofTSPandNPproblems)areabesteﬀortstrategytoﬁnda (good) near-optimal solution (by enforcing space and time boundaries), it does not guarantee that the solution found is thebestcandidatetothe problemandthereforeanprogramcanneverbe surethatifbyrunningmoretimetheoverall solution costcould beimproved,unless theentire solution spaceto theproblem is evaluated. This limitation isset by the deﬁnition of NP-hard class. Problems in the NP class can be solved by a non-deterministic polynomial algorithms [ 1]. Any given class of algorithmssuchasP,NP,etcmusthavealowerboundthatindexthebestperformanceanyproblemintheclasscan have. Thisboundcanbedescribedasthetotalamountofinputitems(oursymbols)amachinemustprocessandthe respective output items produced [ 1] or as we use in this paper, an Probability Distribution Function. A strategy to ﬁnd asolutiontothedecisionproblemistoﬁndafunctionthat reduceortransformanproblemfromadomaininwhich there is no know solution to a constrained domain with a know solution. This allows for an algorithm to search the solution space and decide if any solution is an valid (or yes-instances) or invalid (or no-instances) and its computable by a polynomial-time algorithm[1]. ThisstrategyallowsustomapinstancesoftheHamiltoniancircleproblemtoadecisionversionoftheTraveling Salesman Problem and can be described as a decision problem to determine if exists an Hamiltonian circuit in a given complete graph with positive integer weights hose length is not greater than a given positive integer m . [1] Each valid (yes-instance) in the TSP problem is mapped to a valid instance in the Hamiltonian problem space and this transformation can be done in polynomial time.[1] An Hamiltonian cycle (or circuit) can described as an "path" that contains all nodes and the elements in this set are not repeated, with exception to the ﬁnal vertex. This means that a Hamiltonian cycle in G with start node vhas all other nodes exactly once and them ﬁnishes at node v. An graph G is Hamiltonian if it has a Hamiltonian cycle. An Hamiltonian cycle with minimum weight is a optimal circuit and therefore is the shortest tour in the TSP Problem. Althoughheuristicssuchas2optdeﬁnespecialcasesfortheTSPproblemandproducesnear-optimalsolutionswith short length (weight) Hamiltonian cycles it does not guarantee that the results are the shortest circuit possible. [2] 1.2. Information Theory, Relative Entropy and Bernoulli sequences (i.e. binary random words) Information can be described by a quantity called entropy deﬁned by the probability distribution function of a random variable X. Its a measure of uncertainty about this variable. Let X be discrete with alphabet L and probability mass function p.x/=Pr^X=x`;xËX The entropy H is deﬁned H.X/=*É p.x/log2p.x/ The expectation value Eof a random variable f.x/is deﬁned as E.x/=É f.x/p.x/ fromaknowprobabilitymassfunction p.x/. Alternatively,entropycanalsobedeﬁnedastheexpectedvalue expofthe random variable log1_p.X/ from X in a probability mass function p.x/. This interpretation allow us to set constrains that the entropy function of a random variable must have.[ 13] In other words, entropy can be interpreted as the average code length of the shortest description of a random variable and is measuredbytakingthelogarithm. Entropydescribestheamountofinformationrequiredonaveragetoencodearandom variable.[15] Thejoint entropy of a pair of random variables X and Y can be deﬁned as H.X;Y/=*Elog2p.X;Y/ The conditional entropy of a random variable X given the conditional entropy of Y, thus H.YðX/=*Elogp.YðX/ Therelativeentropy betweendistributionspandqisameasureofdistanceDist(p||q)andcanbeinterpretedasameasure ofperformance(orineﬃciency)whenassumingdistributionqbutknowingpisthetruedistribution.[ 15]Inotherwords, by assuming a code for distribution q , this measures the additional cost D.pððq/required to describe H.p/. This means that on average we need H.p/+D.pððq/ bits to describe the random variable. [13] Themutualinformation I.X;Y/measurestheamountofinformationonerandomvariable Xhasaboutanotherran- domvariable Ywithjoinprobabilitymassfunction p.x;y/andmarginalprobabilityfunction p.x/andp.y/.I.X;Y/can bedeﬁnedastherelativeentropybetweenthejointdistributionandtheproductdistribution p.x/p.y/. Thisquantity measures the reduction in the uncertainty of Xdue to knowledge about the distribution of the random variable Y. Inotherwordsbyconditioninganrandomvariablebyanotherwecanreduceentropybyadjustingtheprobabilityof error. ThispropertymakesitpossibletoestimatetheexpectedvalueofacorrelatedrandomvariableXbyobserving therandomvariableY.Considerasanexamplethatwechooseacardfromadeckwith52cards. Theprobabilityofthis event isP.X/=1_52. Thus the entropy is H.X/=*.1_52/log2.1_52/=0:13bits andweneedthisquantityofbitstodescribetheeventofrandomlychoosingthiscards. Let evente1onthecarddeckbe to randomly pick an king of hearts(There are 4 kings in a 52 deck) and evente2be the knowledge that the card is a heart(Thereare13heartsthustheprobabilityis1/4). Theentropyof e1byknowing e2isdeﬁnedbytheconditional entropyH.Y=e2ðX=e1/. The uncertainty of the ﬁrst event was reduced by knowing e2. Thus event e2has mutual information with e1. [14] Afunctionf.x/isconvexoverainterval .a;b/ifitspositiveandhasasecondderivative[ 13]. Examplesofsuch convex functions are log, x2andex. Let X be a random variable and E the expectation on variable X. For the discrete case there is a xinXsuch as EX=É [p.x/x] and EX=Ê[xf.x/dx] in the continuous case. The Jensen inequality states that if f.x/is convex and Xis a random variable than this expectation is such that Ef.X/>=f.EX/ This implies that X=EXwith probability 1 if f is strictly convex. If we have two probability mass functions p.x/and q.x/that describes x in variable X than the distance D.pððq/is only equal if and only if p.x/=q.x/:ÅxËX . Thus ifXandYare independent variables than the entropy H.XðY/=H.X/ and H.XðY/<=H.Y/ otherwise. This means that on average observing the random variable Y can only reduce uncertainty on the variable X. This inequality properties between random variables X and Y can be used to measure the performance. [ 16] Let Z beaaconditionaldistribution functionthatdependsonlyonYandisconditionallyindependentfromX.Wecanforma Markov chain X*>Y*>Z only if the join probability function can be deﬁned as p.x;y;z/=p.x/p.yðx/p.zðy/ The mutual information for this chain is I.X;Y/>=I.X;Z/ Therefore by observing the random variable Z (i.e. "index variable") its possible to evaluate the dependence of Xand Y. Letxbeasampleofavariable X,anindexvalue fromadistribution p.X/andafunction T.X/ofthesample. By inequality we know that I.;T.X//<=I.;X/ A statistic T is suﬃcient for index if it contains all information in X about that index. Thus function T preserves mutual information. The minimal suﬃcient statistically maximally compress the information about , relative from a family of probability distribution functions that are indexed by . [18] Those inequalities between distributions enables us to divide the set of all possible sequences in two sets and thus wecanusetopredicttheprobabilityoftherandomsequenceandﬁndtheshortestdescriptionofthosesequences. A binary random sequence is a list produced by a Bernoulli process. Each element in the list isdeﬁned as a independent distributed random variable Xwith values 0 or 1. Let X be an independent identically distributed random variable X with probability mass function p.x/. [20] [19] All elements in the both sets are sorted by some index of the sequences. This encoding schema maps all sequences in xto a respective binary string. Although small there is a signiﬁcant probability and this implies that some sequences have higher probability than others binary sequences. Let random variables x in X form a stationary process (sequence). The Entropy rate of a process is the the entropy of suchsequence deﬁned as H.x1;x2;x3:::;xn/and itgrowslinearly (asymptotically), with nat a rate H.X/- . This rate is the limit of achievable compression of information. [13] 1.2.1. Kolmogorov Complexity and inference The Shannon-Bernoulli deﬁnition of a random variable X with a probability mass function p(x) has a entropy equal tothenumberofbitsrequiredtodescribexinXbyaShannoncode. AlternativeinhisworkKolmogorovdeﬁnethe algorithm complexity of an object. Kolmogorov deﬁned that the descriptive complexity of an object to be the length of the shortest binary that describes the object.[ 25] [26] Each symbol in the language have a probability of occurring (an eventinstatistics)inanystringorword,withaﬁnitelength. Thiscomplexityisindependentofthemachineinterpreting the coding. [13] Forexampleletsconsider seq1=1010101 andseq2=101000 . Inseq2wehavelistoflength6with2elements withbinarysymbol1and4elementswithsymbol0. Theﬁrstsequenceappearstobemorerandomthanthesecond sequence since we have an more uniform distribution of events in which the string has elements (or variables) with values 0 and 1. The ﬁrst sequence is more complex than seq2and must require more bits to represent.[13] InFigure 1from Maier[ 41]wecansee acomparison betweena seriesof stringsand thecorrespondentautomata state machine and the regular expression patterns (i.e. regex). Figure 1: Representation of string as state machines and the search pattern for the regex expression. The expected length of the shortest binary description of a Bernoulli variable is close to its Shannon H.X/entropy. This descriptive program can be interpreted as a universal Shannon code to the Turing Machine for all probabilities. TheconsequencefromtheKolmogorovComplexityisthatitsthereforepossibletodescribeanlowerandupper boundsforthesolutionspacefortheminimalprogram. Inotherwordssinceittaketoomuchtimeforamachineto evaluateallpossibleelementsinasolutionspacetoﬁndtheminimalprogram,wecaninsteadacceptshortnear-optimal solution/programsthatarestatisticallysigniﬁcant. Thisapproachcanbeseenasaformaldescriptionforheuristicsin general and is the foundation for inductive inference. [28][22] The Kolmogorov complexity gives a method to compare the complexity in the struct of such random sequence strings. For example, in a sequence created from a coin-ﬂip, with n bits length, there are 2npossible sequences and all are probable. The algorithm complexity of this random string (Bernoulli sequence) has the same size as the sequence itself. The intrinsiccomplexity(measured as length of the shortest program) iscomputer independent, upto limiting constrains. This constrain is deﬁned as a addictive constant to the complexity and is the length of the pre-program that allows the machine to compile another program. 1.2.2. Turing Machine for Computation Turing machines TMare the canonical model for computers. Universal computers mimic (or replicate) the actions of other computers. The Von-Neumann Architecture can be reduced to a Turing Machine. TMcan be deﬁned as a ﬁnite-state machine operating on a ﬁnite tape. At each time the machine read a symbol from the tape and may change its state, under some predeﬁned decision rule. Each operation is traced by a ﬁnite list of transactions. [ 13] The ﬁgure 2 contains a basic automata representation of a Turing machine from Hopcroft et al. [42] Figure 2: Basic Turing Machine The machine TM reads symbols sfrom tapetfrom left to right and at each symbols it decides if to update the cell with another symbol.This machines never goes back and stops after reading the entire tape once. The programs for this machine form a preﬁx-free list. However is assumed that no program that produces a halting computation for TM can bepreﬁxofanotherprogram. ThisconstraininthemachineisdeﬁnedbytheKolmogorovComplexityofthestringthat encode this program. AstheTMmachinescomputesthecellsfromthetapeitmapstheelementsfromasetofﬁnitelengthbinarystringto another set that than can have ﬁnite or inﬁnite binary string length. If the computation does not halt it is undeﬁned .[13] 1.2.3. Complexity of a string and shortest description length LetUbe a Universal computer. The Kolmogorov complexity K.x/of a string x of a computer Uis K.x/=minlength.p/ when p:U.p/=x It is the minimum length program pthat output variable x and halts. Its the small possible program. Let Cthe another computer. If this complexity is universal there is a universal computer Uthat simulates Cfor any string x by a constant concomputer C.ThusK.x/ofU <=K.x/ofC+c. [25]Thisconstantdoesnotdependonstringx.[ 13]Theupper bound on the Kolmogorov complexity is K.x/<=K.xðlength.x//+2log2length.x/+c Therefore there are few sequences with low complexity in the set. The lower bound states that are not many short programsintheset. IfXisaBernoullisequencewithprobability p.x/=1_2,thismeanstherearenomorethan 2k strings with complexity K.x/<k. [25] Considereachprogramcanproduceonlyonepossibleoutput,thenumberofsequencewithcomplexity K.x/<kis lessthan2k. Thusthecomplexitywilldependonthecomputeruptoanadditiveconstant. Letsconsiderfractalsfor example. They can produce complex 2d images with self-replicating patterns with many diﬀerent scales. However the complexity to describe its rules have a Kolmogorov Complexity close to zero. [13] The expected value of the Kolmogorov complexity of a random sequence is close to the Shannon entropy. This relationshipbetweencomplexityandentropycanbedescribedasastochasticprocessdrawntoai.i.donvariableX followingaprobabilitymassfunctionp(x). ThesymbolxinvariableXisdeﬁnedbyanﬁnitealphabet. Thisexpectation is E.1_n/K.Xnðn/=>H.X/ Therefore most of the sequences in the set do not have simple description. However there are some simple sequences. The probability that a random sequence can be compressed by more than kbits is no greater than 2.*k/. Thus most Bernoulli sequences have a complexity close to their length. The Kolmogorov complexity of a independent and identically distributed random binary variable created by a Bernoulliprocessisclosetotheentropybinaryfunction.[ 29]TheexpectedvalueofthecomplexityoftheBernoulli sequence converges to the entropy. Therefore we can bound the number of sequences with complexity that are signiﬁcantly lower than entropy and classify each element between two sets(the typical sets and a non-typical set). [ 13] LetUbe a universal computer. The universal probability of a string is deﬁned as PU.x/=É [2.*length.p//]=Pr.[U.p/=x]/ This the probability that a random program produces the string x as output. In other words its is the probability of observing the string in a set. This is based on the assumption that the outputs strings are not uniformly distributed and stringswithsimpledescriptionaremorelikelythancomplicatestrings.[ 28]Thisuniversalprobabilitycanbeinterpreted as the general representation of all computable probability distributions. [29] 1.2.4. Halting problem The halting problem states that there is no general algorithm to decide if any program halts or goes on for ever, for all inputs in a machine. Turing proved that no such algorithm can exist for all programs. This problem is similar to the self-reference property of theGodel incompleteness theorem. The halting problems can be understoodas a limitation of the class of problems than can be solved by any computer model.[13] Thereforetoﬁndtheshortestprogramweneedtodecidedbetweenallpossibleshortprograms. Sincesomeprograms may or may not halt there is no eﬃcient procedure to ﬁnd the shortest program that produces a given output string. The consequenceisthe non-computability oftheKolmogorovcomplexity. Thismeansthatthemachineexecutingthepairof input and program may found the solution but never knows that no better short programs exist. However by observing theoutputsproducedwecanestimateadistributionfunctionthatconvergetothetrueKolmogorovcomplexityinthe long run.[13] The Chaitin describes an compact representation of information and randomness. It deﬁnes the probability that a universal computer U halts when the input is a random binary sequence produced by a Bernoulli process. Formally =É [2.*length.p//] suchthatp:U.p/halts. Letsconsiderthatwecanprocessallprogramsinparallel(ateachiterationtimeunit/clock cycle in a computer) and assume (by the law of large numbers) that eventually all programs that halt will be found. Thoseprogramsthatwerefoundtohaltarethenplacedinalistofinstructionstotracktheexecutiontree. Thiselements in this list must be preﬁx-free. Therefore we can discovery if program with less than n bits exist and will halt. In other wordsthismethod reducesanyproblemto asearchofacounterexample Initsgeneralform thismethodassumesthat its possible to ﬁnd a ﬁnite-proof for any theorem if such proof exist.[13] [22] 1.3. Universal Gambling device and Universal Probability Asanexampleletsconsideranuniversalgamblingmachinethatplacesbetsonabinarysequence. Thegambler devicecanplacebetsateachinteractionandwithnetoddsof2-for-1oneachbit. Thismeansthewinningbetyeildgains of2unitsfora1unit"invested". Howmuchshouldthedevicebetateachinteractiontoavoidruin? Ifyouhavethe distributions of elements in the sequence you can use proportional betting as proposed by Kelly and achieve maximum optional-growth-ratepossible. Agambler’sbetcanbeinterpretedtobehisestimateoftheprobabilitydistributionofthe data. This distribution can be encoded. This method is similar to data compression since both are estimation of the true data distribution. If the estimation is good the wealth of the gambler will grow signiﬁcantly more (with probability 1) and thus better data compression can be achieved. If the gambling is log optimal the data compression has the Shannon limit H.[13] The relationship between the expected value of the growth rate coeﬃcient G.f/versus the Kelly fraction ffrom wealth Wis show in ﬁgure 3 from Thorp et al. [40] Figure 3: The growth rate (G(f)) of the bankroll W. IfweconsidertheKolmogorovComplexityandtheChaitin deﬁnitionofminimuminformationdescriptionon strings we can conclude that strings with simple description are more likely than complex sequences. Therefore we can improvethemethodofproportionalbettingproposedbyKellybyusingtheuniversalprobabilityofthissequenceto decide how much to bet. [ 27] If this universal distribution is know than the gambler can place bets on the expectation of the next symbol of the string and growth his wealth W(x)by a factor of 2.length.x//. This betting method bet(x)is calleduniversal gambling and W.x/=2length.x/bet.x/ . Thelogarithmofthe wealthona random sequenceandthe complexity ofthesequenceis nosmallerthanthelength of the sequence. Since 2lis the most the device can won in betting on a random string, thus this scheme performs asymptotically similarly to any other scheme that has prior knowledge about the sequence distribution, under some conﬁdent levels. [13] TheuniversalprobabilityofastringisdeﬁnedbyitsKolmogorovcomplexity. Thisstatestheprobabilityofobserving the symbol 1 or 0 in a sequence after observing the previous elements in the sequence. The conditional probability of ﬁndingthenextsymbolistheratiooftheprobabilityofallsequenceswiththissymbolasthisinitialsegmenttothe probability of all elements with this preﬁx. Suﬃcient statics describes the distribution of a random variable by estimating the probability mass function of the observabledata. [ 13]Thisestimateisverydependentoftheobservedsampleanddoesnotdescribesthestructureof theunderlying distribution. Inmost cases itsassumed that the data followsome ﬁxed set of parametricdistribution such as normal-Gauss distribution. [16] Alternatively the Kolmogorov suﬃcient statistic provides a two-stage description of the data. In the ﬁrst stage it describes the distribution function. In stage two we create a Shannon code to describe this distribution using log1_[p.Xn]bits (ie ﬁnd the model with the shortest description of the input data and the model itself.) The remainder of this paper is organized as follows: Section 2 presents an summary of the previous works and literaturereview. Section3presentsourproposedalgorithmtosolvetheinstancesoftheTSPproblemusingInformation Theory. Section 4 describes the results of the experiments and simulations performed. Section 5 summarizes the concluding remarks founded in our study. 2. Previous Work & Preliminares This section contain an overview of the most important heuristics to solve the TSP problem. Other algorithms such as Nearest Neighbor, Greedy, Insertion, Christoﬁdes, Lik-Kerninghan, Branch & Bound and Ant Colony Optimization were not discussed in this paper. Those methods and its complexity considerations is studied in details by Nilson [4]. 2.1. Heuristics for the TSP & Graph Theory An algorithm that is searching for the smallest distance (cost or weight) between nodes vanduin a graphGmust record the information about the intermediary distances to w. This information can be encoded as a label attached to the nodes where its value is deﬁned as the distance between v and w. [6] For n nodes We can use an distance matrix D=.di;j/nxn where each element represents the distance between each city-nodes. Lets be the set that contains all possible permutations from node 1 to n. Zhan et al[ 12] in his work described that the goal of the TSP is to ﬁnd a permutation  thatminimizesthedistancebetweennodes. Forsymmetricinstancesthedistancebetweentwonodesinthegraphis the same in each direction, forming an undirected graph. For asymmetric instances the weights for the edges between nodes can be dynamic or non-existent. 2.1.1. 2opt, k-opt Croes [8] proposed the 2-opt algorithm, an simple local-search heuristic, to solve the optimization problem for the TSP. It works by removing two edges from the tour and reconnects the two paths created. The new path is a valid tour sincethereisonlyonewaytoreconnectthepaths. [ 4]Thealgorithmcontinuesremovingandreconnectinguntilno furtherimprovementscanbefound. k-optimplementationsareinstancesof2-optfunctionbutwithk>2andcanleadto small improvements in solution quality. However as k increases so does the time to complete execution. InhisworkGlover[RR]proposedtheTabuSearchmethodanditcanbeusedtoimprovetheperformanceofseveral local-search heuristics such as 2opt. As neighborhood searches algorithms like 2opt can sometimes converge to a local optimum, the Tabu search keeps a list of illegal moves to prevent solutions that provide negative gain to be chosen frequently. In2optthetwoedgesremovedareinsertedinthetabulist. Ifthesamepairofedgesarecreatedagainby the 2optmove, theyare considered tabu. The pair is keep in the list until its pruned or it improves the best tour. [ 4] Howeverusingtabusearchesincreasescomputationalcomplexityto O.n3/,asadditionalcomputationisrequiredto insert and evaluate the elements in the list. The Figure 5 show the 2-opt moves from Zunic et. al [38]. Figure 4: 2-opt moves. Nilsson[4]comparedseveralheuristicstrategiesfortheTSPproblemsuchasGreedy,Insertion,SA,GA,etc. He investigatedtheperformancetradeoﬀbetweensolutionqualityandcomputationaltime. Heclassifytheheuristicsin twoclass: TourconstructionalgorithmsandTourImprovementalgorithms. Allalgorithmsintheﬁrstgroupstopswhen asolutionisfound. Inthesecondgroup,afterasolutionisfoundbysomeheuristics,ittriestoimprovethatsolution(up to certain computation and/or time constraints.)* He concluded by showing that the computational time required is proportional to the desired solution quality. 2.1.2. Genetic Algorithm (GA) GeneticAlgorithmswasﬁrstintroducedbyHollad[ 9]basedonnaturalselectiontheory,asanstochasticoptimization method in random searches for good (near-optimal) solutions. This approach is analogous to the "survival of the ﬁttest" principle presented by Darwin. This means that individuals that are ﬁtter to the environment are more likely to survive and pass their genetic information features to the next generation. In TSP the chromosome that models a solution is represented by a "path" in the graph between cities. GA has thee basic operations: Selection, Crossover and Mutation. In the Selection method the candidate individuals are chosen for the production of the next generation by following some ﬁttest function In the TSP This function can be deﬁned as the length (weight) of the candidate solutions tour. Nextthoseindividualsarechosentomate(reproduction)toproducethenewoﬀspring. Individualsthatproduce bettersolutionsaremoreﬁtandthereforehavemorechancesofhavingoﬀspring. Howeverindividualsthatproduces worst solutions should not be discarded since they have a probability to improve solution in the future. In other words, the heuristic accepts solutions with negative gain hopping that eventually it may lead to a better solution. Several researches have studied the performance trade oﬀ of selection strategy and how the input parameters aﬀects the quality of solution and the computational time. Julston studied the performance of rank-based and concluded that tournamentselectionpresentsbetterresultsthanrank-basedselections.[ 3]Razalietal. [ 3]inhisworkexploresdiﬀerent selection strategies to solve the TSP and compare the performances quality and the number of generations required. It concludes that tournament selection is more appropriate for small instance problems and rank-based roulette wheel can be used to solve large size problems. Goldenberg & Deb [ 11] compared the quality of the solution and the convergence time on many selection methods such as proportional, tournament and raking. They conclude that ranking and tournament have produced better results that proportional selection, under certain conditions to convergence. [ 3] In his work Zhong et al. [ 10] explored proportionalroulettewheelandtournament. Heconcludedtournamentselectionismoreeﬃcientthanproportional roulette selection. The ﬁgure 5 contains the pseudo-code for a Genetic Algorithm from Ferentinos et. al [39] Figure 5: Basic genetic algorithm. 2.1.3. Simulated Annealing (SA) Simulated Annealing are heuristics with explicit rules to avoid local minimal. It can be described as a local random search that temporarily accepts moves with negative gain( i.e were produced by solutions with worst quality than current). Theprobabilityofacceptingasolutionissetbyaprobabilityfunctionofatemperatureparametervariable. Asthetemperaturedecreasesovertimetheprobabilitychangeaccordingly. Theacceptanceprobabilityisdeﬁnedas p.x/=1iff.y/<=f.x/and when otherwise p.x/=e[*.f.y/*f.x//_tmp] wheretmpis the input temperature. The SA algorithm speciﬁes the neighborhood structure and the cooling function. Otherheuristicssuchas2-opt,3-opt,inverse,swapmethodscanbeusetogeneratecandidatesolutions. Several researcheshavebeenmadetostudytheperformanceofdiﬀerentSAoperatorstosolvetheTSPproblem. [ 31][33][34][35] Zhan et. al [ 12] proposed a list-based SA algorithm using a list-based cooling method to dynamically adjust the temperature decreasing rate. This adaptive approach is more robust to changes in the input parameters. Thequalityofthesolutioncanbeimprovedbyallowingmoretimeforthealgorithmtorun. SteiglitzandWeiner observed thatthe performance canbe improved by keeping a listof the closestneighbors for each city-node andthus reducing the amount of solutions to search. 2.2. Information Theory In his work Shannon was the ﬁrst to formally deﬁne entropy and mutual information[ 15]. Relative entropy or cross entropy was deﬁned by Kullback and Leibler [ 16] and is a important measure of distances (or divergence between distributions). TherelationshipbetweenmutualinformationandchannelcapacitywasintroducedbyShannon. The channelcapacityistheupperboundthatcanbeachievedreliablyontherateoftransmissionoveracommunication channel. In his work Shannon deﬁned the Continuous entropy and discrete entropy. 2.2.1. Inductive Inference, Compression & Preﬁx-free Grammar Discovery LehmannandScheﬀédeﬁnedthetheconceptofminimumsuﬃcientstatistics.[ 30]Kulbackintroducedtheconnection betweenmutualinformationandsuﬃciency[ 18]. Thisstatisticsisthemosteﬃcientrepresentationthatprovidesall possible information. Shannon[ 15] has alsodeﬁned asymptotic equipartition propertyto a sequence ofvariables draw by an random Bernoulli-process. This property states the probability of an outcome of a random sequence. This allows the partition of the elements in the set between two sets: The typical set and its complement. McMillan and Breinnan hasintroducedtheproofofthispropertyforthestationaryergodicprocessinﬁnitealphabetsources[ 19][20]. This modelforinformationimpliesthattherandomprocesswillnothaveitsproprietiessuchasmeanandstandarddeviation) changing over time and can be deduced from a sample. 2.2.2. Growth-optimal Strategy: Maximum Transmission Rate & Minimum equivocation The entropy rate of a stochastic process and the possible sequences generated by this process on a alphabet was introduced by Shannon.[ 15] Proportional gambling and log-optimal growth rate is deﬁned by Kelly and is know as the Kelly-criterion. [ 27] He proposed an model in which a gambler can place bets on signals transmitted over a communicationchannelandconcludedthatthemaximumexponentialrateofgrowthisequaltotherateoftransmission. The applications of this allocation strategy in the stock market and black-jack were introduced by Thorp [ 21]. Shannon and Thorp have worked in one of the ﬁrst wearable devices used to exploit patterns in the probabilities of outcomes in games like roulette. 2.2.3. Algorithmic Information Theory, Kolmogrov Complexity & Boundaries in Formal Systems The relationship between relative entropy and information in random sequences was introduced by Kolmogrov. [25] [26] The complexity of an object deﬁnes the length of the shortest program that can be processed by a turing machine(ie a computer) and creates this object as output. This interpretation is equivalent to the entropy rate of random variables as introduced by Shannon. Martin-Lof expanded Kolmogorov complexity and deﬁned the idea of algorithmic randomsequencesandtestsforrandomness. [ 28]InhisworkLevinandZvonkin[ 29]deﬁnedthecomplexityforrandom strings generated by a universal probability. Chaitin explored the relationship between algorithmic complexity and mathematical proofs. [22][23][24] ThevanLambalgenstudyprovidesa criticaldiscussionontheinterpretationofChaitin’salgorithmicinformation theory and the relationship between the concept of randomness (in simply deﬁned sequences) and recursive theory.[ 37] InhisworkSolomoﬀinvestigatedtheapplicationsofAlgorithmicProbabilityTheoryasamethodforinferenceand discuss the completeness, incomputability, diversity and subjectivity of the theory.[36] 2.3. Implementation Methods & Probabilistic Algorithm for the TSP 2.3.1. Algorithm Information Solution to the TSP Problem Let L be a ﬁnite language with n symbols in a set such as L: ^NODEA;NODEB;NODEC:::`n. Each item is a identiﬁcation label for the elements in the set under some probability distribution function pdf.x/. This is the likelihoodof choosingagivensymbolxin L.Thiscanbeinterpretedasan randomvariablexin Lthatcanassume any item in the set by following the know distribution pdf.x). Each symbol represents a city with a 1-1 mapping to a respective node in a super-graph G<. Therefore each node is a point with xnandyncoordinates in a 2D euclidean space. ForexampleconsiderthealphabetLthatdescribescitiesencodedbysymbolsintheset L:^SP*BR.SaoPaulo/.x1;y1/;NY* US.NewYork/.x2;y2/;LD*GB.London/.x3;y3/`. Thus each element is a node that have two variables that stores the x and y axis coordinates accordingly. A valid sequence s* can be produced by combining elements of L. Permutations with duplicated elements are invalid. S* is the set with all possible permutations of this sequence. The neighbor of each node at position i in the sequenceisthenextconnectedcity(i.eitematpositioni+1). Thissequencedescribesapathbetweennodesandisa tour starting from the ﬁrst node until the last, and returning to the ﬁrst node when ﬁnished. Examples of sequences that form valid paths are path1 = [¨SP*BR¨;¨NY*US¨;¨LD*GB¨],path2 = [¨SP*BR¨;¨LD*GB¨;¨NY*US¨],path3 = [¨LD*GB¨;¨SP*BR¨;¨NY*US¨]. In the ﬁrst sequence we start atSP*BRand go to the next node .NY*US/From there we go to the ﬁnal city LD*GBand than go back to the starting node SP*BR. This walk in the graph is a tuple [.¨SP*BR¨;¨NY*US¨/;.¨NY*US¨;¨LD* GB¨/;.¨LD*GB¨;¨SP*BR¨/]. The cost between the nodes is deﬁned as the 2D euclidean distance d.x;y/between points such that Node1:= .x1;y1/andNode2:=.x2;y2/is calculated as: dist..x1;y1/;.x2;y2//=ù .x1*x2/^2+.y1*y2/^2 The content of Figure 6 is a graph representation of the cities and the corresponding distance matrix that stores the euclidean distance between nodes. Figure 6: A sample graph for the traveling salesman problem and the corresponding cost matrix. LetL:^¨SP*BR¨;¨NY*US¨;¨LD*GB¨`and consider the coordinate vector [.1;5/;.100;80/;.30;40/]for route path3=[.¨LD*GB¨;¨SP*BR¨/;.¨SP*BR¨;¨NY*US/;.¨NY*US¨;¨LD*GB¨/] The distance between nodes¨LD*GB¨and¨SP*BR¨with points .X1;Y1/=.1;5/;.X2;Y2/=.100;80/ is d.LD*GB;SP*BR/=124:201449 The distance between nodes¨SP*BR¨and¨NY*US¨where .X1;Y1/=.100;80/;.X2;Y2/=.30;40/ is d.SP*BR;NY*US/=80:622577 . In this sequence ,the ﬁnal walk in the tour is from the last node¨NY*US¨to the ﬁrst node¨LD*GB¨and this distance isd.NY*US;LD*GB/=45:453273. Thetotaldistanceoftherouteisthesumofallintermediarypathsbetweenthenodes. Forthisexamplethetotal distance td.path3/=124:20+80:62+45:45=250:269 Thedistancecanbeinterpretedasthecost(orweight)oftheedgesbetweenvertex(nodes). Thereforethecostvectorfor path3is[124:20;80:62;45:45]. ConsiderasalesmanthatneedstovisitncitiesinL.Hewantstooptimizetheroutebetweennodesbychoosing the shortesttour through all cities. Eachcity is visited only onceand the salesmantravelback to the citywhere it has started the tour. We can use a matrix D.i;j/with sizenXnto store the relative distance for all pairs of nodes. The objective is to ﬁnd the permutation that minimizes the euclidean distances of the tour. Solutions that produce short distances maximizes the perceived value of a given utility function used by the salesman. Inotherwords,thesalesmanistryingtointeractivelyoptimizehiscurrentsolution. Thereforehemustdecideif there is a tour with a cost less than some value v, between all possible solution in the set . This the optimal tour length. As the number of cities increases the number of permutations that need to be sequentially evaluated also increase and thus requires more time to be computed. The sequences path1;path2;path3;:::pathncan be interpreted as elements that are searched when traversing a tree. Each element in this tree is a possible solution. The number of permutations grows exponentially with respect to n. In this example there are 3!=6 solutions (n!) that needs to be evaluated by the decision rule. Toaddressthespaceandtimecomplexitiesrequiredtocomputeallelementsinthesetwecanuseheuristicssuch as2-opt,GAandSAalgorithms. Thisapproachassumessomepredeﬁnedstructuretoencodethesequencesandthe decision-rules. 2-opt splits and reconnects the graph, SA generate random sequences that are accepted under some decaying temperature probability and GA mimics biologic systems to optimize the quality of the solution through naturalselection. Foreachmethodwecaninfertheprobabilitydistributionfunctionforthepairofoutputandinput strings (in a large sample of executions). In this paper we propose a algorithm information theory (AIT) approach to deal with problems that have such large searchspace. ConsiderafunctionZdeﬁnedasabinaryfunction. Thisfunctionacceptsasinputsrandomsequences created from L. # Boolean function that evaluate candidate solution cost # against parameter value . Total cost is the sum of all # intermediary distances w /uni2217etween nodes u /uni2217and v /uni2217, # returning to u /uni2217at end . fun_Z( solution , val ): if solution . total_cost < val : return 1 else : return 0 InFigure8wecanseetheautomatarepresentationoffunctionZimplementedasaTuringMachinewithtwomacro operation states: Addition and Comparison. The operators receive two unary integers and writes the sum of them (the Unary addition) or the comparison between the numbers(the Unary Comparison). The unary system repeats a symbol(like 0or 1) inorder to representan decimal number. As an examplethe number 4ca be deﬁnedas 0000 with symbol 0 or 1111 with symbol 1. Figure 7: Sample tape accepted as a valid input in the Turing Machine. For this machine the symbol 0 is used. The tape visualization is demonstrated in FIGURE 7 using the input string <0>}0+0} . The tape has the string with the values to be processed. The symbol <marks the start of the string in the tape. Avalidsequencehastheformat: <val>}cost0+cost1}. Thenumber valwillbecomparedtodetermineifits less than the sum of the sequence of intermediary costs costn.The symbol >splits the string between the cost numbers to be added (delimited by the symbol }) and the number val. This is used to determine if valis small than the sum of the sequence (total cost). The machine uses the symbol Xto mark the evaluated cells according to the state transitions at each interaction. The blank symbol is deﬁned as ¸. Figure 8: Turing Machine to compare if the sum of the cost (i.e total distance) is greater than then a given parameter value<val>}costn*1+contn} Examples of valid input strings are: <0>}0+0} <>}0+} <>}0} <00000000>}0+000+0000+0000000+0000000000} <00>}0+0+00+} Example of invalid input strings: <00000000000>}0+0+00+0} <00000>}0+0+00} <0>}0+} <0>}0} The matrix representation for the states and transitions is show bellow: from , to , read , write ,move 0 ,1 ,$,$,R 6 ,4 ,X, ,L 7 ,8 ,$,$,R 13 ,7 ,X,X,R 8 ,11 ,0 ,0 ,R 1 ,4 ,+ , ,R 7 ,9 ,0 ,X,R 2 ,5 ,# , ,L 3 ,6 ,# , ,L 10 ,12 ,0 ,X,L 1 ,2 ,# ,X,R 5 ,5 ,X, ,L 12,13,$,$,L 5 ,7 , /uni2217, ,R 12,12,X,X,L 12 ,12 , , ,L 13 ,13 ,0 ,0 ,L 5 ,5 ,0 ,0 ,L 5 ,5 , , ,L 5 ,5 ,$,$,L 6 ,6 , , ,L 6 ,6 ,0 ,0 ,L 9 ,10 ,$,$,R 0 ,0 , /uni2217,/uni2217,R 9 ,9 ,0 ,0 ,R 13 ,13 , , ,R 4 ,4 , , ,R 3 ,3 ,0 ,0 ,R 10,10,X,X,R 2 ,2 ,0 ,0 ,R 9 ,9 , , ,R 2 ,2 , , ,R 10 ,10 , , ,R 8 ,8 ,X,X,R 8 ,8 , , ,R 0 ,0 ,0 ,0 ,R 2 ,3 ,+ , ,R 3 ,3 ,+ , ,R 4 ,5 ,$,$,L Lets assume that the distribution of the output of function Z is unequal. Therefore some sequences are more likely thanothersandwecanusethisknowledgetoclassifyeachelementbetweentwosets(1-group,0-group). Iftheinput symbol in a communication channel models the likelihood of observing an symbol in a string (or sequence) with consistent probabilities, thus a algorithm can use this information to change the state of the current know solution. At eachexecutionthedependentfunctionZrevealsmorebitsofinformationabouttheunderlingstructureoftheinput string. In FIGURE 9 is show the relationship between the input and output domains from funZ. The function receives an positive number (the cost value) and returns an Boolean value draw according to the occurrence of another positive numbervalfollowing a probability distribution function pdf.val/. Figure 9: Relationship between input-output domains from the boolean mapping function Z. Letsconsideracomputerthatcanprocesssolutionsinparallelateachtimeunit. Thealgorithmmustevaluatethe solution space of candidate solutions and decide which has the best quality. In other words search for the Hamiltonian circuit trough an large set of valid permutations. Although there are lot of complex solutions with longer sequences in set S* there is a small but signiﬁcant probability of ﬁnding an near-optimal shortest solution with less complexity. TraditionalHeuristicsalgorithmsrequiresproperencodingtoproduceresultswithbetterquality(lesserrors)and assumes all outputs sequences have equal probabilities. We know from Shannon the maximum rate of transmission of symbols in a channel can be achieved trough adjusting the error rate by encoding the strings to reduce this probability. Therefore heuristics can be interpreted as a special case of a communication channel in which symbols are transmitted by a source and the decoding algorithm must decide based in a predeﬁned criterion. Fromthe algorithmperspective thesymbols inthe sequencecan berandom variables. However,once asymbol is sentitcannotbeduplicatedandthusthenumberofpossiblesequencesthatcanbegeneratedarereduced. Weknow fromKellythatbytrackingtheoccurrenceofsymbolsinachannel(withaprobabilitydistributionfunction)wecanuse this information to quantify the optimal amount of resource in the channel to allocate with each symbol. This strategy producessolutionswithimprovedqualitywithoutprior-knowledgeaboutthesystem. Wecanuse thisinformationto dynamically adjust the probability of ﬁnding any symbol in the sequence as the algorithm iterate through the solution tree. We know from Kolmogorov and Chaitin that it may exist a small program that produces any binary sequence. This program must encode all required information for the algorithm to compute and halt, with the least amount of bits possible. An algorithm to solve the TSP can be interpreted as a program that produces the shortest route with the least amounts of bits encoded. 2.4. Overview IfLis a ﬁnite-language with symbol ^c1;c2;c3;:::cn`with a1*1map to a city for each symbol. A route is a sequenceconnectingthecitiesfromlefttoright. Considertwogroups and . Let =[route1;route2;route3;:::routen] be a sample with size n of randomly created valid paths between cities. Each element in this list is a independent candidatesolutiontotheTSPproblem. Let =[route1;route2;route3;:::routem]alistofrandomrouteswithsizem. Thus and are samples with random strings created by the same random ergotic process. Consider a algorithm that process both groups and decide which one has the near-optimal solution on average with the least amount of bits possible to represent this information. Suppose this is a universal algorithm that reads symbols fromachannel,measuresthedataandwritesaindexaboutthepairofinput-outputsymbols,usingatuplet. Ateach interaction it classify the data. There are 3 classiﬁcation steps: Statistical Signiﬁcance sig<, Error Rate err<and Information Divergence div<. We deﬁne t=.sig<;err<;div</ as the label for the class. The group is our model sample in which we want to test against an alternative dynamic sample . Thisalternativegroupiscreatedrandomlyateachinteractionofthealgorithm,while iskeepstatic. The number of interactions or trials performed by this algorithm is a positive parameter max_inter. 2.4.1. Statistical Signiﬁcancy: sig* In Statistical Signiﬁcance wee need to measure how much diﬀerent are the samples. We can use a test statistic such as the chi square statistic to quantify this. Hypothesis test methods provides an signal-to-noise procedure to encode/decode the data sample, when the null hypothesis is true. Its a function of observed and expected counts constructed with a Contingency Table. This determines if there is signiﬁcant diﬀerence between observed and expected frequencies. Letvet_cost = [cost1;cost2;cost3;:::;costn]be a list where each element is the total cost for each candidate solution in the sample. The cost is deﬁned as a random variable Y, dependent on another variable X, with a probability density function pdf.y/. It is measured as sum of all intermediary distances in a given path. Let vet_cost be the equivalent to group . LetE. /betheexpectedvalue(oraverage)ofgroupThemax_ isthemaximumvalueinthecostvectorandmin_ is the minimum value for the sample. The same variables are available for group . Wecanuseacontingencytable CT :E. /tocountthefrequenciesofelementsin thataregreaterorequal(Category 0) and small(Category 1) than the E( ). LetCT :E. /be the frequencies of elements in group that are in category 0 and in category 1 also for E( ). Wecancombine CT :E. /andCT :E. /tocreateamatrix CT ; :E. /totabulatethefrequencydistributionbetween groups and categories against E( ). Table 1 Contingency Table from sets and againstE. / group\category greater or equal than E( ): 0_E( )small than E( ): 1_E( ) CT ;E. / count itens with cost >= E( ) in count itens with cost <E( ) in CT ;E. / count itens with cost >= E( ) in count itens with cost <E( ) in The chi square test for CT ; :E. /assumes the hypothesis Ho;H1: Ho(null hypothesis) : There is no signiﬁcant diﬀerence in the number of candidates solutions with cost less thanE. /between the group ; . Both groups ; are independent. H1(alternative hypothesis) : There is signiﬁcant diﬀerence in the sample observations of costs between and forE. /. Ifp-valuep*fromthechi-squaretesttothe CT ; :E. /islessthanthesigniﬁcancelevel(0.05)wecanrejectthe nullhypothesis. Thereforewecanconcludethereisstatisticalsigniﬁcantdiﬀerenceinthecostsbetweenthetwogroups. ConsideranalphabetL*withsymbols0,1. Let1betthenumberofitemswith cost<E. /in and . Similarly 0isthenumberofitemswith cost>=E. /in and Ifforexample vector_cost =[100;30;50;10;40;80;99;10] andvector_cost =[80;35;65;30;50;90;13;80]andE. /=52,E. /=55thusCT ; :E. /is Table 2 Contingency Table CT ; :E. / group\category E. /01 CT ;E. / 35 CT ;E. / 44 The chi-square statistic is 0.254. The p-value is .614295. The result is not signiﬁcant at p<:05. Therefore we fail torejectthenullhypothesis. Alternativelywecouldalsocalculatethep-valuefromchi-squaretestfor CT :E. /and CT :E. /. 2.4.2. Error Rate: err* Consider a channel in which an algorithm receives encoded signals from a source. Each symbol in this channel has a probability of occurring following a probability distribution. The error rate of a channel is the rate of equivocation or misinformation when transmitting symbols through a noisy communication channel. By adjusting the code to adapt to this rate we can transmit information regardless of the error. TheKellycriterionisastrategytomaximizetheexpectationofthelogarithmofwealth(usingfractionalbetting sizes),insteadoftheexpectedgainforeachtrial. Inthelongrunthisstrategyproducesbetterreturnsthananyother strategy. This method is used by gambling and investing to maximize the expected geometric growth rate. We will use this formula to discover the optimal channel allocation capacity for a given error rate. We use this value to measure the likelihood of ﬁnding elements in groups and that have candidate solutions that improve costs. Ifvector_cost =[100;30;50;10;40;80;99;10]andvector_cost =[80;35;65;30;50;90;13;80]andE. /=52, E. / = 55. Than_vector_cost ;E. /= [.52*100/ ;.52*30/;.52*50/;.52*10/;.52*40/;.52*80/;.52* 99/;.52*10/] = [*48 ;22;2;42;12;*28;*47;42]. Similarly_vector_cost ;E. /= [.52*80/ ;.52*35/;.52* 65/;.52*30/;.52*50/;.52*90/;.52*13/;.52*80/]=[*28 ;17;*13;22;2;*38;39;*28] Thepositivevariablesinthecostvectorcanbeinterpretedasthequantityofimprovement,orgainforeachcandidate solution. ThismeasureisthedecreaseincostfromtheexpectedvalueE(x)foreachelementinthelist. Respectively thenegative variablesarethe unitsofdecline inqualityand ismeasuredas aincreasein observedcostfrom expected value E(x). Consideringpreviousexample,thus +_vector_cost ;E. /=[22;2;42;12;42],*_vector_cost ;E. /=[*48;*28;*47], +_vector_cost ;E. /=[17;22;2;39],*_vector_cost ;E. /=[*28;*13;*38;*28]: Thealgorithmcanusethisinformationtodecidehowfavorablearetheroutesingroups and . Iffkellyisnegative than is very unlikely has elements with costs that are less than E. /. The risk of "losing" is too high for this iteration. Howeverfkelly>0there are elements in or that reduces costs signiﬁcantly and thus optimize the current solution quality. Similarlyagambleruseprobabilitiestodecidetheoptimalamountofhiswealthtobetateachtrialbasedon the symbols he receive from a channel. FromCT ; :E. /weknowthereare .5+4/=9 itemssmallerthan E.x/and.3+4/=7 itemswhosecostishigher thanE.x/. There are in total 16 candidate solutions from samples ; . Therefore class 1 has 9/16 = 0.5625 or 56% of the elements and class 0 has (7/16)=0.43 or 43%. Let the average improvement gain be deﬁned as avg_+_cost ; :E. /=[.avg_+_cost ;E. /+avg_+_cost ;E. //_2] and the average loss avg_*_cost ; :E. /=[.avg_*_cost ;E. /+avg_*_cost ;E. //_2] From previous example we have: avg_+_cost ;E. /=.22+2+42+12+42/_5=24 avg_+_cost ;E. /=.17+22+2+39/_4=20 avg_*_cost ;E. /=.*48*28*47/_3=*41 avg_*_cost ;E. /=.*28*13*38*28/_4=*26 :75 Then the modiﬁed CT ; :E. /relative to the expected costs improvement and worsening. Let the average for both groups be avg_+_cost ; :E. /(average gain) and avg_*_cost ; :E. /(average loss). avg_+_cost ; :E. /=.24+20/_2=22 avg_*_cost ; :E. /=.*41*26 :75/_2=*33 :87 Table 3 Contingency Table CT ; :E. /for the expected cost group\category E. /=52 0 1 CT ;E. / (-41) (+24) CT ;E. / (-26.75) (+20) FromCT ; :E. /wehaveProb_1 ; :E. /=0.56,Prob_0 ; :E. /=0.44andlettheratioofimprovement(ieaverage gain of positive solution by average loss of the negative solution) be 1_0_Ratio=avg_+_cost ; :E. /_ðavg_*_cost ; :E. /ð thus for this example 1_0_Ratio=.22_33:87/=0:64. The Kelly formula with these parameter is: f_kelly ; :E. /=Prob_1 ; :E. /*[.1*Prob_1 ; :E. //_1_0_Ratio ; :E. /] f_kelly ; :E. /=0:56*.0:44_0:64/=.0:56*0:68/=*0:12 TheKellyfractionis f_kelly=*0:12andsincef_kelly<0theerrorrateistoohighonthechannel. Alternatively insteadofcalculatingfromtheunionofset and wecouldalsocalculatethefractiontoeachsetseparately. Therefore from theCT ; :E. /we have: avg+_cost ;E. /=24 avg+_cost ;E. /=20 avg*_cost ;E. /=*41 avg*_cost ;E. /=*26:75 Prob_0 ;E. /=3_8=0:375 Prob_1 ;E. /=5_8=0:625 Prob_0 ;E. /=4_8=0:5 Prob_1 ;E. /=4_8=0:5 1_0_Ratio ;E. /=avg+cost ;E. /_ðavg*cost ;E. /ð=24_ð*41ð=0:58 1_0_Ratio ;E. /=avg+cost ;E. /_ðavg*cost ;E. /ð=20_ð*26:75ð=0:747 f_kelly ;E. /=Prob_1 ;E. /*[.1*Prob_1 ;E. //_1_0_Ratio ;E. /] f_kelly ;E. /=0:625*.0:375_0:58/=*0:021 f_kelly ;E. /=Prob_1 ;E. /*[.1*Prob_1 ;E. //_1_0_Ratio ;E. /] f_kelly ;E. /=0:5*.0:5_0:747/=*0:169_] 2.4.3. Information Divergence(div*) Each set have an amount of information intrinsic to itself and this can be measure in bits using the entropy formula. Wecanalsomeasuretheamountinformationthatissimilarbetweendistributions. Thisallowustoquantifytheamount ofinformationrelativeto from andto from . Itcanbeinterpretedastheamountofinformationlostbyassuming an alternative distribution to represent the true distribution. Letthelanguage L<:0;1withtwoprobabilitiesdistributionsfunctions pdf.x/forsets and . Thisfunctions describes the frequencies of symbols 0 and 1 in each sample. This probabilities are deﬁned by the occurrence of candidate solutions in either set that are higher or smaller than the expected value E. /, measured from our model sample . From the entropy formula by Shannon we can measure the amount of bits required to represent the symbols inL<for both distributions pdf. /E. /andpdf. /E. /. From the example we have CT ; :E. /and therefore: Prob_0 ;E. /=0:375 Prob_1 ;E. /=0:625 Prob_0 ;E. /=0:5 Prob_1 ;E. /=0:5 The entropy for the distribution relative E. /isH. /E. /: H. /E. /=.0:375<log2.0:375//+.0:625<log2.0:625//=*.0:375<*1:4150374992788437/+*.0 :625<*0:6780719051126377/ H. /E. /=0:954 The entropy for the distribution relative E. /isH. /E. /: H. /E. /=.0:5<log2.0:5//+.0:5<log2.0:5//=*.0:5<*1/+*.0 :5<*1/ H. /E. /=1 Thus the we need 1 full bit to represent the distribution H. /E. /and exactly 1 bit to H. /E. /. To compare the distributions we can measure the divergence between the entropy for two or more probability distribution. We can use the Jensen-Shannon divergence JS_divto quantify the similarity between distributions. This methodisbasedinthe Kullback–Leibler divergence(orrelativeentropy). If L<:0;1,pdf. /E. /=[0:375;0:625], pdf. /E. /=[0:5;0:5]thanJS_div=0:0114. Thusthediﬀerencebetweenthedistributionsrequireslessthan1bit to be described and is close to zero. This is the expectation of the logarithmic diﬀerence between the probabilities pdf. /E. /andpdf. /E. /for sequences produced by a binary function with alphabet L<:0;1. This divergence is the mutual information between a randomvariableXrelatedtotheprobabilitydistributionsfrom and andanbinaryfunctionclassiﬁerusedtomap elements between and . 2.5. Algorithm & Data Structure In FIGURE 10 is shown the ﬂowchart for the algorithm proposed in this paper. Figure 10: Flowchart of the algorithmic-information method for the salesman problem. The pseudo-code for the method described is bellow: #create a valid random permutation of the input string *no duplicates . #output : string , the sequence is a path between nodes v ad w in the graph g /uni2217. func create_random_solution_sample_list (L, const_sample_size ). sample_set = [] for i in 0 *> const_sample_size *1: sample_set . append( createValidRandomPermutation (L)) return sample_set # language L with city *node symbols . L:{c1(x1 ,y1) ,c2(x2 ,y2) ,c3(x3 ,y3) ,c4(x4 ,y4 )...} # language L /uni2217with binary symbols produced by a binary function classifier # whose input is a random senquece produced using L. L/uni2217:{0 ,1} # number of elements in each sample const_sample_size = m # number of trials const_max_inter = mi /uni2217 random_model_sequence < *createValidRandomPermutation (L) model_vector_cost < *get_total_distance_for_routes ([ random_model_sequence ]) # alpha : model set . # beta : alternative set . alpha <*create_random_solution_sample_list (random_model_sequence , const_sample_size ) vector_cost_alpha < *get_total_distance_for_routes ( alpha ) # calculate expected cost in the set expected_value_alpha < *get_average ( vector_cost_alpha ) # get the solution with the highest cost relative to expected model cost max_solution_cost_alpha = max( vector_cost_alpha ) # get the solution with the minimun cost relative to the expected model cost . min_solution_cost_alpha = min( vector_cost_alpha ) # calculate delta difference between the cost of each candidate solution # to the expected model cost . Delta_cost_vector_alpha < *get_difference_cost ( vector_cost_alpha ,\ expected_value_alpha ) # get the average improvement cost . +Delta_vector_cost_alpha < *get_positive_elem ( Delta_cost_vector_alpha ) # get the average worsening on cost relative to expected cost . *Delta_vector_cost_alpha < *get_negative_elem ( Delta_cost_vector_alpha ) avg_+Delta_cost_alpha < *calc_average(+Delta_vector_cost_alpha ) avg_*Delta_cost_alpha < *calc_average( *Delta_vector_cost_alpha ) # create the contingency table of occurrence of candidate solutions # relative to expected cost . CT_alpha < *[ count_negative_elem ( Delta_cost_vector_alpha ) , \ count_positive_elem ( Delta_cost_vector_alpha )] # get the likehood of category 1 ( candidate cost less than expected cost ) Prob_1_alpha < *get_probability_class_1 (CT_alpha) # get the likehood of category 0 ( candidate cost greater or equal than expected cost ) Prob_0_alpha < *get_probability_class_0 (CT_alpha) # create the probability distribution function to the sample . pdf_alpha < *[ Prob_1_alpha , Prob_0_alpha ] # calcuate the number of bits required to represent the sample distribution . H_alpha < *calc_entropy ( pdf_alpha ) # track solution output . label_list = [] for i from 0 *> const_max_inter : # create random sample and calculate the distances between cities ( vector cost ) beta <*create_random_solution_sample_list (random_model_sequence , \ const_sample_size ) vector_cost_beta < *get_total_distance_for_routes ( beta ) # calculate the difference between distance from candidate solutions # in the set with the expected value of the model set . Delta_cost_vector_beta < *get_difference_cost ( vector_cost_beta , \ expected_value_alpha ) max_solution_cost_beta = max( vector_cost_beta ) min_solution_cost_beta = min( vector_cost_beta ) # get the candidate solutions that improve solution quality # ( reduce expected solution cost ). +Delta_vector_cost_beta < *get_positive_elem ( Delta_cost_vector_beta ) # get solutios that are worst than expected solution cost . *Delta_vector_cost_beta < *get_negative_elem ( Delta_cost_vector_beta ) # get the average improvement relative to the expected cost value . avg_+Delta_cost_beta < *calc_average(+Delta_vector_cost_beta ) #get the average worseing relative to the expected cost value . avg_*Delta_cost_beta < *calc_average( *Delta_vector_cost_beta ) # contingency table for beta CT_beta < *[ count_negative_elem ( Delta_cost_vector_beta ) , \ count_positive_elem ( Delta_cost_vector_beta )] # calculate entropy for distribution beta Prob_1_beta < *get_probability_class_1 (CT_beta) Prob_0_beta < *get_probability_class_0 (CT_beta) # probability distribution function of finding candidate solutions with cost less # than expected cost ( category 1) or greater than expected cost ( category 0). pdf_beta < *[ Prob_1_beta , Prob_0_beta ] # the number of bits required to represent (encode) the set is define as entropy # binary function H( beta ). H_beta <*calc_entropy ( pdf_beta ) # chisquare statistic between alpha and beta CT_alpha , beta = [CT_alpha , CT_beta] # Is significant difference between the cost distributions in the samples sets ? p_value_chi2 = chi2_test (CT_alpha , beta ) # Kelly*criterion , error rate # average improvement gain from both sets *beta ( alternative ) # set and model set ( alpha ). avg_+Delta_cost_alpha , beta = (avg_+Delta_cost_alpha + avg_+Delta_cost_beta )/2 avg_*Delta_cost_alpha , beta = (avg_ *Delta_cost_alpha + avg_ *Delta_cost_beta )/2 # probability of chosing an candidate solution that improve current expected cost . Prob_1_alpha , beta = get_probability_class_1 (CT_alpha , beta ) # probability of choosing an cadidate solution at random that worse the cost # quality relative to the expected cost . Prob_0_alpha , beta = get_probability_class_0 (CT_alpha , beta ) # the ratio of improvement between category 1 and category 0. 1_0_Ratio_alpha , beta < *avg_+Delta_cost_alpha , beta / | avg_ *Delta_cost_alpha , beta | # get kelly fraction proportional to the channel capacity . f_kelly_alpha , beta < *Prob_1_alpha , beta *[(1*Prob_1_alpha , beta )/1 _0_Ratio_alpha , beta ] # information divergence between distributions . js_div_alpha , beta < *calc_jensen_shannon_divergence (L /uni2217,pdf_alpha , pdf_beta ) # create label t <*( p_value_chi2 , f_kelly_alpha , beta , js_div_alpha , beta ) costs <*( min_cost_alpha , min_cost_beta , max_cost_alpha , max_cost_beta ) label_list [ i ] < *(t , costs ) # interpreted the tuple by some criterion and decide if halt or not . # constrains are defined by program paramenters . # statistical significant : p *value < 0.005 # likehood / risk of improving current cost : f_kelly > 1 # number of bits to represent the distance between sets : js_div > 0.1 if decide_to_halt ( label_list [ i ]) == true : break return label_list The time complexity for this algorithm is deﬁned as the time required to: Create the permutations for the model group : O(n) complexity for a list with n elements. Find the average, minimum and maximum cost distance for the sample: O(n) ContingencyTable: Counttheoccurrenceofelementssmallorgreaterthantheaveragefromthemodel sample : O(n) Calculate the probability of improvement in the distance and the average gain or loss for the group: O(2) Calculate the entropy for the distribution from : O(1) Iterate the algorithm an ﬁnite number of times m* and at each trial: O(m*) Create the alternative sample : O(n) Find the minimum and maximum cost for the alternative sample : O(n) ContingencyTable: Counttheoccurrencein ofelementssmallorgreaterthantheexpectedcostfromthe model sample : O(n) Calculate the probability of improvement in the distance and the average gain or loss for the group: O(2) Calculate the Kelly fraction from and cost distributions: O(1) CalculatethechisquaretestfortheContingencyTablefor relativetoexpectedcostvaluefrom Calculate the divergence between distance distributions and : O(1) Store solution state in list: O(1) The upper bound is O..3n+c1/+m<.3n+c2//=O.n+m<n/ The space complexity is deﬁned as: List to store the sequences from the model group : O(n) Variables to store the average, minimum and max values from : O(3) Matrix to store the Contingency Table for the set: O(4) Variable to store the average gain or loss for the set: O(2) Variable to store the entropy for the distribution, represented by the Contingency Table frequencies: O(1) List to store the sequences from the alternative model : O(n) Store average, minimum and maximum values from relative to expected value for : O(3) Matrix to count frequencies for set relative to : O(4) Variable to store average gain or loss from solutions in set relative to : O(2) Variable to store the entropy for the distribution frequencies for relative to : O(1) Variable to store the similarity(or divergence) between the distributions and : O(1) Additional list to store the classiﬁcation tuple t=(sig*, err*, div*): O(m*) The upper bound is O..n+c1/+.n+c2/+m/=O.n+m/ 3. Computational Experiments & Results 3.1. Experimental Setup In this section we will focus on the computational experiment carried to observe and analyses the strategy of using algorithmic information theory to detect patterns in strings and use this schema to obtain near-optimal solutions to the TSP problem. The algorithms are implemented in Python 3 with libraries dit, matplotlib and numpy. The performance ofthemethodistestedagainst3instancesoftheproblemwithrandomlychosencitieswith10,30and50nodes. Ateach interaction the program create a new alternative hypothesis set, compares it against the model distribution and classify the sample with a label tuple t=(sig*, err*, div*) . This label is later used to sort and classify the sample distributions. The node coordinates in the euclidean space are the input symbols used to generate paths to the salesman. This tour is encoded as a sequence of nodes. A valid permutation is a tour deﬁned as a list with no duplicate elements. The solution space is the set with all valid permutation or candidate solutions. DIMENSION: 50 EDGE_WEIGHT_TYPE : EUC_2D NODE_COORD_SECTION 1 288 149 2 288 129 3 270 133 4 256 141 5 256 157 6 246 157 7 236 169 8 228 169 9 228 161 10 220 169 11 212 169 12 204 169 13 196 169 14 188 169 15 196 161 16 188 145 17 172 145 18 164 145 19 156 145 20 148 145 21 140 145 22 148 169 23 164 169 24 172 169 25 156 169 26 140 169 27 132 169 28 124 169 29 116 161 30 104 153 31 104 161 32 104 169 33 90 165 34 80 157 35 64 157 36 64 165 37 56 169 38 56 161 39 56 153 40 56 145 41 56 137 42 56 129 43 56 121 44 40 121 45 40 129 46 40 137 47 40 145 48 40 153 49 40 161 50 40 169 The maximum number of iteration is deﬁned as a input parameter m<>0. As the number of nodes in the sample increases the time and space required to evaluate and create valid permutations also increases. The number of permutations for each sample is a positive parameter sample_size=300, with a total of 600 elements in total. The algorithmterminateswhenthemaximumnumberofexecution isreached. Forthis paperwe have usedaniterationtime of 300 for all experiments. Theobjectiveofthemethodistomeasuretheamountofinformationineachsampleandthemutualinformation between groups. At each step the candidate solutions are evaluated against the expected value cost relative to the model distribution and thiscount is used to decideif the samples means aresigniﬁcantly diﬀerence using the chi-square test (p<0:05). Wealsomeasuretheamountofbitsrequiredtorepresenteachsampleusingtheentropyfunctionandthe similarity between samples is measured with the Johasen-Shannon Divergence. In this paper we are measuring the quantityofbitsrequiredtorepresentthisknowledge. Thustheentropyandthedivergencemustbepositiveintegers. The error rate for the sample distributions are measured as the likelihood of improvement in a communication channel with the Kelly criterion. In this experiment we have set the threshold for the fraction as f_kelly>0. At the end of each interaction the tuple t=(sig*, err*, div*) , the minimum and maximum values for the route costs are inserted in a buﬀer list. This list is than used to search for solutions distributions that have chi-square test with p*value<0:05andf_kelly>0. After the trials are ﬁnished (i.e. maximum number of iteration is reached) We sort the results in descending order by using the number of divergent bits between the sample distributions. 3.2. Experimental Results The algorithm results are ﬁltered by t=(sig*, err*, div*) with condition (sig* < 0.005 and err* > 0) in descending orderofdiv*forthreeinstanceoftheTSPwith10,30and50nodes. Theperformanceofthebestresultsfromthethree instances are shown in TABLE [TPP1], TABLE [TPP2] and TABLE [TPP3] respectively. Table 4 TABLE [TPP1] 10-city a): intera_min_cost b_min_cost a_max_cost b_max_cost a_avg_cost b_avg_cost 293199.8452 226.4190 464.2929 474.5521 358.1339 346.9520 Table 5 TABLE [TPP1] 10-city b): intera_b_chi2_CT b_pval a_pval a_b_chi2_pval 293[[148, 152], [123, 177]] 0.001822 0.81736 0.04028 Table 6 TABLE [TPP1] 10-city c): intera_kelly_k b_kelly_k a_b_kelly_k 2932.220446049250313e-16 0.24496 0.12800 Table 7 TABLE [TPP1] 10-city d): intera_b_info_js_div a_info_ent b_info_ent 2930.00506 0.99987 0.97650 Table 8 TABLE [TPP2] 30-city a): intera_min_cost b_min_cost a_max_cost b_max_cost a_avg_cost b_avg_cost 721409.12405 1308.8004 2414.9828 2336.10197 1905.01199 1893.9638 1961409.124054 1369.2457 2414.9828 2300.17248 1905.01199 1889.11683 1841409.12405 1465.18982 2414.9828 2494.663 1905.01199 1896.68915 For all instances of the problem we can see from the tables that the expected cost for is less than the average of . Additionallythenumberofsolutionsin withsmallercoststhanE( )islessthanthenumberofsolutionsin with expectedvaluesmallerthanE( ). ThiscanbeobservedintheContingencyTables a_b_chi2_CTfromTABLE[TPP1], TABLE[TPP2]andTABLE[TPP3]. Ifwecomparethe p*valueofthechi-squaretestwecanseethatinallcases there is a signiﬁcance diﬀerence between the sample means. The rate of improvement between distributions is measured bythe Kelly fraction. We cancompare the performance using TABLE [TPP1], TABLE [TPP2] and TABLE [TPP3]. We can see from the tables that this rate is small and close to zero. If the number of nodes increases the error rate in the channel also increases. Thus as the number of Table 9 TABLE [TPP2] 30-city b): intera_b_chi2_CT b_pval a_pval a_b_chi2_pval 72[[159, 141], [133, 167]] 0.049647 0.298697 0.033699 196[[159, 141], [133, 167]] 0.049647 0.298697 0.033699 184[[159, 141], [134, 166]] 0.064671 0.298697 0.0411716 Table 10 TABLE [TPP2] 30-city c): intera_kelly_k b_kelly_k a_b_kelly_k 722.220446049250313e-16 0.0791686 0.03744395 1962.220446049250313e-16 0.11312 0.055189232 1842.220446049250313e-16 0.05989 0.0278014806 Table 11 TABLE [TPP2] 30-city d): intera_b_info_js_div a_info_ent b_info_ent 720.0054288 0.9974015 0.990714 1960.0054288 0.9974015 0.990714 1840.00501791 0.9974015 0.991777 Table 12 TABLE [TPP3] 50-city a): intera_min_cost b_min_cost a_max_cost b_max_cost a_avg_cost b_avg_cost 2103687.880596704705 3745.695347 5749.646374 5642.41536 4666.26576 4604.589729 1943687.880596704705 3332.52242 5749.646374 5590.93659 4666.26576 4630.9972754 Table 13 TABLE [TPP3] 50-city b): intera_b_chi2_CT b_pval a_pval a_b_chi2_pval 210[[156, 144], [131, 169]] 0.02824036 0.4884223 0.04103653 194[[156, 144], [132, 168]] 0.03766692 0.48842231 0.04986020 Table 14 TABLE [TPP3] 50-city c): intera_kelly_k b_kelly_k a_b_kelly_k 2101.1102230246251565e-16 0.1936353 0.09844197 1941.1102230246251565e-16 0.1129841 0.05482081 candidate solutions increases than the risk of randomly choosing a element with a worst quality tour also increases. This value can be interpreted as a context for the chi square test. For example from TABLE [TPP2] 30-city a) we can seethatthep-valueatiterations72and196arethesameat0.033699(sincetheyhavethesameContingencyTable). Table 15 TABLE [TPP3] 50-city d): intera_b_info_js_div a_info_ent b_info_ent 2100.00502466 0.99884553 0.98839523 1940.00462900 0.99884553 0.98958752 HowevertheKellyfractionforiteration196isbetterthanat72andthusthemisinterpretationriskissmallerat196 with 0.055189232. From the TABLE [TPP1] we can see that the average gain provided by the alternative distribution is greater for the 10-city instance. From the results we see that although distribution can have in average more elements with expected cost less than , it’s still possible that the minimum tour length be in . As shown in TABLE [TPP2] 30-city b) at iteration 184 the minimum cost at is 1409.124 and at is 1465.189. However the average cost for is 1905.011 against 1896.689 from . As can be seen in the tables the similarity between the distributions is less than 0.005 bits of information. The entropy for the distributions and for each instance is approximately 1 bit per iteration. In FIGURE 11a, 11b ,11c , 11d we have the graph for the maximum and minimum cost for iteration 194 from instance with 50 cities. The graph shows the bounds in performance in each sample. The minimum costs strings have less complexity than the maximum cost sequences because they have less crossing edges between vertex in the 2d graph. The distance in the graphs reduce towards a near-optimal solution as the algorithm iterate. In FIGURE 12a,12b, 12c we can see thehistogramwith5binsfordistributions , and U ,foriteration194from50-cityinstance. Thismeasuresthe frequencies ranges of the cost samples. The data follow a normal distribution. The FIGURE 13 show the distribution of data for samples , and the union of U using a boxplot. The graph show the maximum, minimum, average and quartiles from the cost distributions. Data points above the standard deviation and the quartiles are considered outliers. Figure 13: Boxplot from , and U From box-plot in FIGURE 13 , histograms in FIGURE 12a and FIGURE 12b we can see that the distribution has more candidate solutions with cost less than average cost for , In FIGURE 14 We can see the relationship between the kelly fraction and the p-value for the chi-square test, draw fromiteration194forthe50-cityinstance. Tohelpvisualization,eachpointsizeissetbymultiplyingthenumberof (a) Minimum cost in (b) Minimum cost in (c) Maximum cost in (d) Maximum cost in Figure 11: Maximum and minimum paths in graph bits for distributions (color red), (color green) and the divergence between and (color blue) by a constant factor c=10000. As show in FIGURE 14, if distribution produces in average better solutions than than the green group is closer totheleftuppercornerandtheredgroupisshiftedtotherightbottom. Thebluegroupisthesubsetwiththedivergence between and . If isaimprovementfrom thanthissubset(representedbythebluegroup)isclosertothegreen group. Therefore we can conclude that at iteration 194 the distribution produces in average solutions with better qualitythandistribution (i.e. withsmallercostthanexpected)atasigniﬁcantlevelandthelikelihoodofﬁndinga near-optional solution is positive. (a) Histogram from (b) Histogram from (c) Histogram from , Figure 12: Histogram from sets and Figure 14: Signiﬁcancy vs Error Rate from , and U 4. Conclusion In this paper we have described a 3 stage classiﬁcation algorithm to solve the TSP and compare the performance of the solution distributions in terms of statistical signiﬁcance, error rate and information complexity. From the result of theexperimentsforthreesimulationswith 10,30and50city-nodes respectivelyitcanbe concludedthatthe expected cost between the model distribution and the alternative distribution is reduced to a near-optimal solution with smaller distance. We have found near-optimal solutions with p-value with less than 0.5% deviation for all instances of the problem. The algorithm is an approximation on the expected value of a symbol in a sequence represented by two probability distributions function p.x/andq.x/against another indexing function fzand although it may not ﬁnd the optimal solutionreliably,itcanproducenear-optimalsolutionswithpredictabletimeandspacegrowthrate. Inthispaperwe have modeled the salesman dilemma to a problem of compressing information in a communication channel that have symbolsproportionaltosometrueunknowndistributionfromarandomvariable. Themaximumexponentialrateof improvement of the algorithm is equal to the rate of transmission (and computation) of the information in this channel. Thechannelisthetotalofinsideinformationavailabletothealgorithm. Asthenumberofelements ninthesample distributions increases the time and space required to produce valid permutation also increases proportional to n. Thealgorithmexecutesaﬁnitenumberofiterationsuntilitﬁnisheswhenitreachesapredeﬁnedprogramparameter constant. Thisbehaviormakesthemethoddemandlessresourcestoﬁndtheminimumtotaldistancetotheproblemthan otherstrategies. Theamountoftimeandmemoryrequiredislinearlyproportionaltothedistributionofinput-output pairsymbolsinacommunicationchannel. Thereforethecomplexitytotransmitandcomputeasequenceofsymbols isdependontheprogramuptoaadditiveconstant. Theindexfunction fz.x/isusedtosearchthesolutionspacefor permutations with less traveling distance in the tour against a measured expectation cost-distance value. This is based ontheassumptionthatsequenceswithlesscomplexity(shortlength)aremorelikelythanoutputstringswithgreater complexity. Assuming by the law of large number that eventually all possible candidate solutions can be generated we conclude that the quality of the solution could be improved by allowing more execution time. This approach can be used to solve small and large instances of the problem. The expectation and variance between the data distributions is adaptive to the topology of the solution space under some boundaries. This has the advantage of being resistant to changes intheprogramparametervaluesundersomesigniﬁcancelevelanderrorprobability,thussamplesizesshouldbeset accordingly. TheinterpretationproposedinthispaperisdiﬀerentfromclassicalmethodstosolvetheTSPproblem. Atevery interaction it searches the solution space with the goal of maximizing the expected value of the logarithm of the current channel capacity instead of the value function deﬁned by the euclidean distance. The logarithm is used because its additiveandindependentofpastevents. Whilethealgorithmistryingtomaximizethevaluefunctionitalsohasto decideifthealternativehypothesis( )isdiﬀerentfromthenullhypothesis( )andthenumberofbitsrequiredtoencode this information. Ifthesamplesmeaninagiveniterationarediﬀerentandthelikelihoodofimprovingthecostdistanceispositive than thealgorithm set a ﬂagto Trueand record thisdata in a ﬁlteredlist. This canbe interpreted as theclassiﬁcation labelforthesampledataateachexecutionforthemachine. ThestrategycanbeimplementedusingaShannoncode usingH.X/bits with ﬁnite symbols and computed by any Turing machine Twith ﬁnite tape draw according to a Universal Computation Probability U. The Kolmogorov complexity is approximated by the length of the shortest program(i.e. groupofdatastructuresandinstructions)thatproducesthetourdistributionwiththeshortestexpected total distance as output and halts. Thereforewecanconcludethatthesalesmanproblemcanbemodeledasproblemofoptimizingthetransmission rateofinformationinanoisycommunicationchannel. Considerasaexampleasalesmanthatreceivesalistofcitiesthat it needs to visit from a channel source and he wants to ﬁnd the shortest tour between cities to minimize his cost. There is a probability density function associated with the occurrence of each symbol sent proportional to the distribution of input-output pairs. The salesman must compares his current total tour distance against the new signal received. At each interaction he wants to reduce the rate of misinformation or the risk of choosing a path that would lead to a route with a potentialcosthigherthanthecurrentknowbestsolution. ThisinterpretationrequirestwoTuringmachineswithtwo ﬁnite tapes deﬁned as: Rule 1: Turing Machines T(Source Encoder & Channel Encoder) and (Channel Decoder & Source Decoder) with two tapes. Rule 2: The tapes AandBare the communication channel Cbetween machines Tand . Rule 3: Machines Tand agree on same ﬁnite alphabet Lto encode or decode symbols. Macro state A: Twrites encoded symbols in the tape Ausing ﬁnite alphabet L Macro state B: reads the received symbols sent by TfromCand decode each sign. Macro state C: writes a symbol using another alphabet L<in its own tape B. In ﬁgure 15 we see an example representation of the ﬁnite state control unites. Figure 15: Universal Algorithmic-Information Turing Machines. Future work could be to compare the benchmark between the Algorithmic Information Theory (AIT) based method andotherheuristicssuchas2-optandSA.Additionallytoimproveperformancewecoulduseanextrabuﬀertostore illegal moves (such as in the taboo list) to avoid frequently exploring solutions with worst expected distance (negative gain) between nodes. After expiration time units is reached the element can be purged from this neighborhood list. This method could improve performance by reducing the valid solutions that are evaluated but has the downside of requiringadditionalstepstosearchandoperatetheadditionalliststructure. Alternativelythevalidpermutationscan becreatedwith2-optmovesinsteadofrandompermutation. Futureworkcouldalsoexploresettingconstrainsinthe precedence/preﬁxofrandomstringsusingthefeedbackfrompreviouscompleteexecutionsoftheAITalgorithmto dynamically update the current best know state.