Combinatorial problems

Other approaches such as Branch and bound algorithms can be used to optimize combinatorial problems. The branch-and-bound method produces lists of candidate solutions by a search in the state space. The set of states forms a graph. Each sub pair of states is connected if the first and the second state are produced by an operator to transform the first state in the second state.

From Poole and Mackworth [3], there are two categories of state space search algorithms:

Uninformed: The algorithm does not have any prior information about the state distribution. The Breadth-First Search is an instance of this class.

Heuristic Search: The algorithm has encoded information about the solution distribution defined by a heuristic function. The A* search algorithm is an instance of this class. The A* is a path finding algorithm and its defined in terms of weighted graphs. It has a running time of O(b^d).

Nearest Neighbor (NN) and Nearest Insertion (NI)

From Asani, Okeyinka and Adebiyi [4] the Convex-hull and Nearest Neighbor heuristics can be combined. Their results where compared with two benchmark algorithms Nearest Neighbor (NN) and Nearest Insertion (NI). Their experimental results show their approach produces better quality in terms of computation speed and shortest distance.

The Christofides and Serdyukov algorithm

Based in graph theory and combines a minimum spanning tree with a minimum-weight perfect matching where the distances between nodes in a super-graph is symmetric and follow the triangle inequality and thus form a metric space. The solution Christofides algorithm has the best worst-case scenario currently know with a quality tour of at most 1.5 the optimal string. The computational complexity is O(n³).

Given a Eulerian path we can find a Eulerian tour in O(n) time. The method finds a minimum spanning tree and duplicate all edges to create a Eulerian Graph. A graph G = (V(G), E(G)) is Eulerian if is both connected and has a closed trail and thus represents a tour with no repeated edges, containing all edges of the graph. In graph theory a Eulerian path is a string in a finite graph that visits every edge exactly once (no repeated edges) and it allows the revisiting of nodes, then returning to the starting vertex. In Fig 6 we have a comparison between Hamiltonian and Eulerian graphs.

Fig 6

Example of Hamiltonian and Eulerian graphs.

The Christofides and Serdyukov algorithm can be described as:

Find the minimum spanning tree

Create a map for the problem with the set of nodes of odd order

Find a Eulerian tour path for the map

Convert to the TSP: If a node is visited twice create a shortcut from the node before the current and next node.

k-opt method

The 2-opt and 3-opt are a special case of the k-opt method. The method can be optimized by a preprocessing using the greedy algorithm. For a random input the average running time complexity is O (n log(n)).

2opt, k-opt

Croes proposed the 2-opt algorithm [5], a 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 since there is only one way to reconnect the paths. The algorithm continues removing and reconnecting until no further improvements can be found. k-opt implementations are instances of 2-opt function but with k > 2 and can lead to small improvements in solution quality. However, as k increases so does the time to complete execution.

In his work [6] proposed the Tabu Search method and it can be used to improve the performance of several 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. In 2opt the two edges removed are inserted in the Tabu list. If the same pair of edges are created again by the 2opt move, they are considered Tabu. The pair is kept in the list until its pruned or it improves the best tour. However, using Tabu searches increases computational complexity to O(n³), as additional computation is required to insert and evaluate the elements in the list.

The Fig 7 show the 2-opt moves from [7].

Fig 7

Generating 2-opt moves.

[8] compared several heuristic strategies for the TSP problem such as Greedy, Insertion, SA, GA, etc. He investigated the performance tradeoff between solution quality and computational time. He classifies the heuristics in two class: Tour construction algorithms and Tour Improvement algorithms. All algorithms in the first group stops when a solution is found such as brute-force and Greedy Algorithm. In the second group, after a solution is found by some heuristics, it tries to improve that solution (up to a certain computation and/or time constraints) such as implemented by 2opt, Genetic Algorithm and Simulated Annealing. He concluded by showing that the computational time required is proportional to the desired solution quality.

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). These methods simulate the behavior of the cooling process of metals into a minimum energy crystalline structure.

This concept is analogous to the search of global maximum and minimum. The probability of accepting a solution is set by a dependable probability function of a temperature parameter variable t. As the temperature decreases over time the probability changes accordingly. Fig 8 demonstrates the simulated decay in the temperature function over the number of interactions in an algorithm.

Fig 8

Temperature decay relative to the iterations of the SA algorithm.

The acceptance probability is defined as p(x) = 1 if f (y) ≤ f (x) and when otherwise

[9] research combines the Simulated Annealing method with the Gene Expression Programing to improve solution diversification and state search. Their results show a better performance that other methods such as ant-colony, naive SA, naive GA, etc.

The SA algorithm specifies the neighborhood structure and the cooling function.

Fig 9 from [9] represents the SA algorithm flowchart.

Fig 9

Simulated annealing algorithm flowchart.

[10] research explores the optimization technique in Simulated Annealing and the solution impact by different temperature schedule designs. It concludes that the quality of finite time SA implementations is a result of relaxations dynamics similar to the analogy with the vitrification process of amorphous materials (non-crystalline) or disordered systems (high entropy).

Their results can be generalized in terms of entropy distributions. By the thermodynamics analogy, we know the position of particles in higher temperatures have a higher degree of uncertainty and thus there is more entropy as each particle is bouncing randomly. As the temperature decreases the particles forms bounds between them and the overall state distribution forms a glassy or crystal structure. As there is less uncertainty about the average state value for each particle there is less entropy and thus more information about the optimal state distribution is known.

[11] work provide a numerical analysis of the simulated annealing applied to the TSP. The cost distribution is compared to the control parameter of the cooling method. It concludes that the average-case performance can be defined by assuming the deviation between the final total cost and the optimal solution is distributed by a gamma distribution. This behavior is also observed in our research and this model is explained by the Kolmogorov Complexity for the Bernoulli string that represents a random solution candidate. The entropy for this distribution can be calculated and is the maximum entropy probability distribution. This is the sufficient statistics needed to represent the state set.

Metropolis algorithm and heuristic optimizations

Let f(X) be a function with output proportional to a given target distribution function r. The function r is the proposal density. At each iteration of the algorithm it attempts to move around the sample space. For each move it decides sometimes to accept a given random solution or stay in place. The probability of the solution of the new proposed candidate is with respect to the current know best solution. If the proposed solution is more probable than the know existing point, we automatically accept the new move. Else if the new proposed solution is less probable, we will sometimes reject the move and the more the decrease the probability, less likely we will accept the new move. Most of the values returned will be around the P(X) but eventually solutions with lower probability will be accepted. This characterizes can be interpreted as a generalization of the methods proposed by Simulated Annealing and Genetic Algorithms.

Other heuristics such as 2-opt, 3-opt, inverse, swap methods can be used to generate candidate solutions. Several researches such as [8] have been made to study the performance of different SA operators to solve the TSP problem [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. Their research provide an improved Simulated Annealing method that uses a dynamic list to simplify the parameter settings. This method is used to control the cooling rate for the decrease temperature used by the Metropolis Rule. The list is updated iteratively following the solution space topology. This cooling schedule can be defined as a special geometric cooling method with variable coefficients. This characteristic gives the algorithm more resistance to different input parameters values while producing good sub-optimal results.

In his work [13] proposed a biological inspired bee system to optimize the routing in Railway systems. They conclude that the average solution results are better or equivalent than the traditional SA and GA methods.

The quality of the solution can be improved by allowing more time for the algorithm to run. [14] observed that the performance of 2-opt and 3-opt algorithms can be improved by keeping an ordered list of the closest neighbors for each city-node and thus reducing the amount of solutions to search but requiring more memory to keep the list of states.

Genetic Algorithm (GA)

Genetic Algorithms was first introduced by [15] based on natural selection theory, as a stochastic optimization method in random searches for good (near-optimal) solutions. This approach is analogous to the "survival of the fittest" principle presented by Darwin. This means that individuals that are fitter 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 three 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 fittest function In the TSP This function can be defined as the length (weight) of the candidate solutions tour. In Fig 10 we have a representation of genes and chromosomes.

Fig 10

Chromosome for a sample of individual candidate solutions.

In Fig 11 is demonstrated an example of two parents under the Mutation and Crossover operators to generate a new offspring.

Fig 11

Offspring representation for the genetic algorithm mutation and crossover operators.

Next those individuals are chosen to mate (reproduction) to produce the new offspring. Individuals that produce better solutions are more fit and therefore have more chances of having offspring. However, individuals that produces 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 hoping that eventually it may lead to a better solution.

Several researches have studied the performance trade off of selection strategy and how the input parameters affect the quality of solution and the computational time [16]. in his work explores different 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.

[17] compared the quality of the solution and the convergence time on many selection methods such as proportional, tournament and ranking. They conclude that ranking and tournament have produced better results that proportional selection, under certain conditions to convergence. In his work [18] explored proportional roulette wheel and tournament method. He concluded tournament selection is more efficient than proportional roulette selection. Their work presents a simple genetic algorithm that combines roulette wheel and tournament selection. Their results suggest that this approach converges faster than roulette wheel selection.

This conclusion is related to the findings in our research and can be explained by Information Theory. The tournament selections mechanism helps to avoid the algorithm to waste execution iterations with solutions that have more noise (i.e. local minimum candidates–suboptimal solutions) and also by providing more useful information by giving a chance for all candidate to eventually produce optimal solutions, through the roulette wheel method.

The Fig 12 contains the pseudo-code for a Genetic Algorithm from [19].

Fig 12

Basic genetic algorithm.

Ant Colony (AC) optimization

Ant colony (AC) optimization is a method that models the behavior of ants to find the shortest route in the nest. The choice for a given path by each ant is defined by the distribution of pheromones left by other ants when in transit.

The method is described as:

Initialize: Create initial distribution of pheromone in the region

For i from (0, n)

For each ant

Evaluate the objective function

Update know best solution tour

Update pheromone intensity distribution

Simulate decay pheromone intensity

Stop Criterion Achieved?

Yes: Local minimum found

Continue search until maximum iteration n is reached.

In the work “Ant supervised by PSO and 2-Opt algorithm, AS-PSO-2Opt, applied to Traveling Salesman Problem” from Kefi, Rokbani, Krömer and Alimi [20] there is a optimization of the 2-opt method using a post-processing for the solution paths to help avoid local minimum. Their results perform better than other benchmark algorithms such as Genetic Algorithm and Neural Networks.

In Fig 13 we have a representation of ant nest and pheromone distribution across a 2D region.

Fig 13

Ant colony pheromone representation.

Cross-entropy (CE) method

Is a combinatorial optimization method with noise. The method approximates the optimal utility function estimator with two targets:

Create a sample from a probability density function.

Minimize the cross-entropy between the distribution and the density function to improve the candidate solution quality for the next iteration.

The CE algorithm can be described as:

Init: Set parameter μ as average and σ as the standard deviation

For i in (0, N)

Create random sample S with size n using a normal distribution N (μ, σ) with parameters μ and σ

Evaluate the Noise (entropy) distribution for the sample S

Select the best Z% candidates of the solution sample to form a new subset T ⊆ S

Update μ and σ with the probability distribution function of T, assuming a normal distribution

The algorithm works by reducing the entropy using a maximum like hood estimator P(X). In Fig 14 we have a representation for the entropy function P(X).

Fig 14

Entropy decrease process.

In “Solve Constrained Minimum Spanning Tree By cross-entropy (CE) method” [21] propose a parallel, randomized method to find a spanning tree using the lowest total cost relative to the cost weight under constrained weight boundaries.

Special cases are a class of algorithms that restricts the limits in the problem to find the optimal solution inside a give boundary. A metric TSP defines the distance between nodes under the triangle inequality and replaces the Real value Euclidian for the Manhattan distance. The Euclidian TSP is a special case for the metric TSP using integer numbers for the Euclidian distance.

The Euclidian TSP has a Euclidian minimum spanning tree associated with the minimum spanning tree of the graph and has the expected running time complexity O(n log n).

Information Theory (IT)

Quantifies the amount of information in a noisy communication channel and is measured in bits of entropy. IT is based in probability theory and statistical distributions. Entropy quantifies the amount of uncertainty in a random Bernoulli variable created by a Bernoulli process thus information can be interpreted as a reduction in the overall uncertainty about a set of finite states. Mutual information is a measure of common information between two random variables and it can be used to maximize the amount of information shared between encoded (sent) and decoded (received) signals. In Table 3 we have the relationship between Information and Entropy. As we increase our knowledge about the states following a probabilistic function distribution, we reduce entropy, as there is less uncertainty about possible state outcomes.

Table 3

Relation between the level of uncertainty and knowledge about possible string outcomes.

Information	Entropy	Word	P (X = 0)	P (X = 1)	E(X)
High	Low	0000	1	0	1*1*1*1 = 1
Medium	Medium	0001	0.75	0.25	0.75*0.75*0.75*0.25 = 0.105
Low	High	0011	0.5	0.5	0.5*0.5*0.5*0.5 = 0.0625

Information theory as an approximation method

Information Theory has applications in a range of fields and is used as a mathematical framework for encoding and decoding of information such as in adaptive systems, artificial intelligence, complex systems, network theory, coding theory, etc. IT quantifies the number of bits required to describe a given a set of states using a statistical distribution function for the input data.

Entropy of a random sequence

Entropy is a measure of uncertainty of a random variable. It is the average rate at which information is produced by a stochastic process [22]. defined the entropy H as a discrete random variable X with possible values as outcomes draw from a probability density function P(X). Fig 15 demonstrate the variation in entropy H(X) vs a Bernoulli distribution. In Eq 4 the entropy function is defined as:

Fig 15

Entropy H(X) vs Probality Pr(X = 1).

Random variables and utility function

Let X be an independent random variable with alphabet L: {001, 010, 100–}. A utility function g is used to model worth or value and is defined by g: {X ⊂ ℝ} and it represents a preference of relation between states. The utility function Y = g(X) of a random variable X express the preference of a given order of possible values of X. This order can be a logical evaluation of the value against a given threshold or constant parameter. The g(X) is defined by a normal distribution with given mean and variance under some degrees of freedom (i.e. confidence level).

As an example if g(X1 = 001 = 1) = c1 and g(X2 = 010 = 2) = c2 are the costs of two routes between a set of nodes in a super-graph G*, we can use this function to determine the arithmetical and logical relationship between them and decide if c1 is worst, better, less, greater or equal to c2. Therefore g(X1) < g(X2). The probability density function pdf(Y) can be used to calculate the entropy of the distribution of the cost values. An exponential utility is a special case used to model when uncertainty (or risks) in the outcome between binary states and in this case the expected utility function is maximized depending on the degree of risk preference.

Fig 17 demonstrate an example of a normal distribution for cost function g(X) = {50, 51, 49, 49.3, 50.5, 50.3, 49.1, 48} and the probability P(X<48). Fig 16 shows the histogram for g(X). Table 4 demonstrate the calculation for the mean, standard deviation and variance for g(X), thus we have:

Fig 16

The probability density function for cost function g(X).

Fig 17

The normal distribution with mean 49.65 and standard deviation 0.91.

Then P (X<48; X < min g(X)) = 0.0349.

Table 4

Statistical metrics for function g(X) distribution.

Parameters	Output
Standard Deviation, σ	0.91241437954473
Count, N	8
Sum, Σx	397.2
Mean, μ	49.65
Variance, σ2	0.8325

Kolmogorov complexity

The Kolmogorov complexity [23] of a string w from language L denoted by

Complexity of a string and shortest description length

Let U be a Universal computer (i.e. Universal Turing Machine). If description d(x) is the minimal string to encode x. Kolmogorov complexity K_c(x) of a string x of a computer U is

Measuring the randomness of a string

Let K_c (x|y): The conditional Kolmogorov complexity of X_n given Y. Consider for example we want to find the binary string with higher complexity between three variables X₁(010101010101010), X₂(0111011000101110) and Y (01110110001011). In Table 5 we have the representation and minimal encoding using X_n and Y. Therefore, we can see X₁ and X₂ can be encoded as combinations of Y and thus K_c(X₁|Y) > Kc (X₂| Y). This relationship is defined as

Table 5

Example of representation of strings X1 and X2 using substring Y.

Variable	Binary Sequence	Minimal String Representation Schema
Y	01110110001011	Substring
X1	010101010101010	01 (#7 pairs of bits) + 0 (#1 single bit)
X2	011101100010110	Y + 0

In Fig 18 from [24] we can see a comparison between a series of strings and the correspondent automata state machine and the regular expression patterns (i.e. regex schema).

Fig 18

Examples of representations of a given input string set using regex and an automaton.

The expected value of the Kolmogorov complexity of a random sequence is close to the Shannon entropy. From [25] this relationship between complexity and entropy can be described as a stochastic process drawn to a i.i.d on variable X following a probability mass function pdf(x). The symbol x in variable X is defined by a finite alphabet L. This expectation is

Kelly criterion and the uncertainty in random outcomes

The Kelly strategy is a function for optimal size of an allocation in a channel. It calculates the percentage of a resource that should be allocated for a given random process. It was created by John Kelly [26] to measure signal noise in a network. The bit can be interpreted as the amount of entropy in an expected event with two possible binary state outcome and even odds. This model maximizes the expectation of the logarithm of total resource value rather than the expected improvement for the utility function from each trial, in each clock unit iteration in a Turing Machine.

The Kelly criterion has applications in gambling and investments in the securities market [27]. In those special cases, the resource (communication) channel is the gambler’s financial capital wealth and the fraction is the optimal bet size. The gambler wants to reduce the risk of ruin and maximize the growth rate of his capital. This value is found by maximizing the expected value of logarithm of wealth which is equal to maximize the expected geometric growth rate.

Similarly, the log-normal Salesman’s can improve his strategy in the long run by quantifying the total of available inside information in the channel (or a tape in the Turing machine) and maximizing the expected value of the logarithm of the value function (defined by Traveled Euclidean distance) for each execution clock. Using this approach, he can reduce his uncertainty (entropy H(X)) while optimizing his rate of distance reduction (and solution quality improvement) at each execution time.

The Fig 19 demonstrate the Kelly criterion value over the Expected Growth Rate.

Fig 19

Maximization of entropy in random events.

Kelly uncertainty distribution

Let E(Y) be the expected value of random variable Y, H(Y) be the measured entropy for the pdf(Y) distribution and K*(E(Y),H(Y)) = f* be the maximization of the expected value of the logarithm of the entropy of the utility function Y = g(X). This fraction is known as the Kelly criterion and can be understood as the level of uncertainty about a given data distribution of the random variable X relative to a probability density function pdf(Y) of a measured respective cost distribution found at the sample. It’s a measurement of the amount of useful encoded information.

The value of f* is a fraction of the cost-value of g(X) on an outcome that occurs with probability p and odds b. Let the probability of finding a value which improves g(X) be p and in this case the resulting improvement is equal to 1 cost-unit plus the fraction f, (1+f). The probability of decreasing quality for Y is (1-p).

The maximization of the expected value f* is defined by the Kelly criterion formula in Eq 12

For example, consider a program with a 60% chance of improving the utility function g(X) thus p = 0.6 (success) and q = 0.4 (failure). Consider the program has a 1-to-1 odds of finding a sequence which improves g(X) and thus b = 1(1 quality-unit increase divided by 1 quality-unit decrease). For these parameters the program has a 20%(f* = 0.20) of certainty that the outcomes produce values that improve the expected value of g(X) over many trials.

Consider another sample case for a fair coin with probability of success (winning) P (1) = 0.5(50%) and failure(losing) P (0) = 0.5(50%). Table 6 demonstrate the amount improved (+) and worsen (-) for each scenario:

Table 6

Yield returns from bernoulli process P(1) and P(0).

Probability	Output	Value
Success (1)	Gain (True)	+ 2 units
Failure (0)	Lose (False)	- 1 unit

The Total Expected Outcome, Edge, is defined by:

Method Constraint 1: Entropy simulation and uncertainty measurement

Simulated Uncertainty. The first constraint is limited by the entropy. The input parameters for the Kelly function f* are the Wining probability P_W and the expected net-odds b for the Bernoulli trial B. The value of P_W is decreased by a fixed constant rate of 0.0001 at each interaction. The value b is measured as the ratio of average improvements of the positive interactions divided by the average reduction of the negative interactions. The result of this function is the percentage of the useful side information available in a noisy channel.

In Table 8 we have an example for the Kelly criterion calculation.

Table 8

Example calculation for the Kelly criterion for P (1) = 90, 50 and 10 and net-odds b = 1.

PW (Win/Cost Decrease)	PL (Lose/Cost Increase)	Expected (Averaged) Cost Gain (Quality Improvement)	Expected (Averaged) Cost Loss (Quality Worsening)	Success/Failure Ratio b	(Output) Kelly Percentage f*
90	10	+100	-100	+100/|-100| = 1	0.8
50	50	+100	-100	+100/|-100| = 1	0
10	90	+100	-100	+100/|-100| = 1	-0.8

The decision criterion 1 is implemented as an evaluation of the IF logical statement for the Simulated Kelly Criterion and the Uniform Random Number output value.

Method Constraint 2: Discrete computation distribution of a random binary variable

Bernoulli Process. The second constraint is defined by a Bernoulli process as a finite sequence of independent and random Bernoulli variables. This module will return as output the value “True” at 1% of the time for 100 interactions (N = 100) and it will accept unlikely (risky) solutions with negative gain to eventually provide improvements bets for the solution quality, under some degree of freedom. The process is defined as a trial with two binary states either “True/Success” (1) or “False/Failure” (0) with domain p ∈ [0,1]

In Fig 22 we can see a Bernoulli distribution with P (0) = 80% probability of output a Failure state

Fig 22

P(X) for the Bernoulli distribution with P(1) = 0.2 and P(0) = 1—P(1) = 0.8.

Examples of Bernoulli trials are show in Table 9.

Table 9

Examples of random events and the respective binary outcome.

Event	Outcome
Play a game	Win/Lose
Coin toss	Head/Tail
Processing a request	On time/Late
Defect in equipment’s	Good/Defect
Buy-Sell an asset	Profit/Deficit
Optimizing traveling cost	Reduction/Increase

The decision criterion 2 is implemented as a OR gate using the input Bernoulli Distribution Trial B and the output A of the IF statement from the Simulated Kelly Criterion and the Uniform Random Number output value.

Shortest distance and shortest encoding

The computational complexity problem in Graph Theory such as the TSP and NP-Hard Problems is reduced to a combinatorial problem, using an entropy function optimization method from a Bernoulli variable defined by a Log-Normal distribution.

The method is based on the amount of self-information available in a random variable and this is the minimum encoding required to represent the problem in a Turing Machine, while producing as output the near-optimal solution found before halting. By the Kolmogorov Complexity this is the optimal program with the minimum amount of encoded information.

Mathematical definition

Assuming the Euclidian distance between nodes is the utility function for the problem. The proposed algorithm instead of trying to find the best solution directedly, using an arbitrary stochastic process, and interactively improving the string path, alternatively, the QA algorithm assumes the symbols from output Y is produced by processing the input from Bernoulli variable X, that is defined by a log-normal distribution and variables X and Y share Mutual Information. This is the amount of information X has about Y and is equal to the information Y know about X.

The lemmas for the proposed model are defined in Table 10.

Table 10

Auxiliary theorems for the proposed model based in information theory.

1. The Bernoulli process B(p) is used to generate strings with length n and a pattern-code schema encoded as a Hamilton graph with probability p 2 The strings S are a Bernoulli sequence B formed with a random variable X from a finite alphabet L 3. The utility function U(S=B(X)) = Y is defined as the Euclidian Distance between nodes in a 2D plane 4. Bernoulli variables X and Y have Mutual Information 5. The Entropy Function for H(X), H(Y) and H(X|Y) can be calculated 6. E(X) is the Expected Value for X with mean $$ and standard deviation σ1 7. E(Y) is the Expected Value for Y with mean $$ and standard deviation σ2 8. f*(Y) is the optimal encoding defined by the Total Expected Value (“Edge”) divided by the Expected Solution Quality Increase if Successful (“Odds”), for Sequence Y   a. f*(Y) = Edge/Odds

Logarithm utility model

The method provides an alternative narrative for the Traveling Salesman Problem as it asks, “what is the best path between cities that simultaneously minimizes cost losses in the long run while also provide the best rate of improvement for each interaction”. The salesman wants to avoid solutions with local minima. There are several possible paths the salesman can choose, and he must guess which choice will lead to the best route over a set of candidate solutions. The uncertainty between states outcomes indicates the level of entropy (i.e. more entropy means less knowledge about the state values distribution). The reverse of entropy is the negentropy, which is defined as a temporary state condition in which a certain state distribution is more probable and more organized and thus there is less uncertainty about the state distribution for a given time frame. The utility function is demonstrated in Fig 25.

Fig 25

Utility function.

This approach is a model for risk measurement over many possible outcomes and is based in the work of John Kelly, Edward O. Thorp, von Neumann and Claude Shannon in logarithmic information utility, with applications in the financial markets and game theory such as the optimization in wealth growth in the long run and diversification in investment strategies in portfolio management.

Random path construction

In Fig 26 we have a representation of the possible path choices to produce a candidate solution tour for TSP. The example has an alphabet L with 4 elements (n = 4). At each interaction the Salesman’s needs to choose the next node in the route. In the begging at T = t0, starting in the arbitrary node L: {a}, it has several possibilities for the next move with L’: {b,c,d}. Each element (or symbol) has a 1/3 probability in t0. In the second iteration t1, the probability for the remaining possible symbol increase to 0.5, however the probability for the nodes already chosen drops to zero, and the possible choice outcome for the next state move is reduced to L’: {c,d}.

Fig 26

Tour construction for a weighted graph with a probability function p ∈ [0,1].

From initial solution in time T = t0 there are a few valid sequences that can be chosen. There is no universal function to guide the Salesman with certainty on what is the best choice. This statement is supported by the Kolmogorov complexity of the string. The Salesman must then outguess this problem using the available side-information.

The side-information can be defined by the probability density function of the Euclidian distance distribution, formed by a set of valid candidate solution strings. The condition for a candidate to be valid is to be a Hamiltonian graph. Invalid solutions have zero probability of being chosen. In Fig 27 we have a set of candidate solutions with examples of valid and invalid sequences.

Fig 27

Candidate solution production and path decision.

This feature reduces the search space to only Hamiltonian circuits. From observation, we know that there is a greater probability that edges that crosses generally produce a total path distance larger than those nodes that do not have edges that overlap. The Fig 28 demonstrate a crossing of edges in a graph.

Fig 28

Edge crossing between nodes.

Algorithms such as 2opt takes advantage of this cluster aggrupation of edges and uses a strategy to remove the crossing between a group of nodes until no further improvement is found.

Solution quality and time to convergence

The method proposed is not an exact method but is guaranteed to produce the best quality in the long run, eventually, with probability 1 and smaller time to convergence, in average. This is a method that almost surely converges to a better solution quality if compared to any other heuristics when approaching the limit, as the number of algorithm iteration goes to infinity, and without needing complex string and array manipulations. Therefore, the method has a better computational cost optimization in average.

The proposed algorithm also brings more simplicity of implementation with lower encoding overhead, when compared to other algorithms such as Genetic Algorithm, Neural Networks and Ant Colony.

Computational requirements and cost effectiveness

The time constraining in QA heuristic is not a problem because the only factor to decide the running time is the degree of freedom allowed to the program. If the algorithm is expected to be more precise and with less errors, the time parameters can be adjusted with time complexity O(n) and with each interaction the entropy about the solution states is reduced, as the knowledge about the best solution increases (i.e. Smaller Euclidian distance). Therefore, the error rate can be adjusted to any level desired.

Relation with other heuristic methods

This is similar to the approach proposed by the Cross-Entropy Method, but the Quantitative Algorithm method does not resample or update the probability density function at each interaction, but instead embraces randomness and accepts candidate solution according to a simulated decreasing entropy function, with a binary random switch attached.

This mechanism is similar to the Manhattan Rule used by the Simulated Annealing algorithm. The proposed method use the simulated Kelly function ratio value α = f* to compare against a random control value u, than the output is evaluated again using a binary operation switch B which returns True or False, following a dependable probability function, that is decremented by a constant rate c from P(X) = 100 until P(X) = 1/100, at each interaction t_N. This schema is used to provide alternatives paths and solve the hill-climbing limitation that is also present in many solvers of the TSP.

In Fig 29 we have a demonstration for the hill-climbing with examples of Global and Local points with the respective Maximum and Minimum positions.

Fig 29

Hill-Climbing problem.

Running costs

The running cost for the Quantitative Algorithm is the defined by the computational effort to generate a random candidate tour string and to evaluated with the current registered best-known solution, encoded by a Hamiltonian graph pattern, in O(N) time.

For each iteration, it has the computing cost to calculate the simulated entropy heuristic function and compare against the control values. These values can be calculated in constant time T(n). The memory required is defined by an array M of candidate solutions elements with size O(M) = 2. The array is a buffer to store the best candidate solution and the alternative solution.

Disadvantages and Limitations

Because of this design, the running time to converge is worst for the QA algorithm when compared to other methods, such as 2opt and greedy, at small instances of the problem with less than a few nodes (n<15). If compared to heuristics such as Simulated Annealing, Genetic Algorithm or Ant Colony the execution time is similar but requires less time in average. This behavior is observed in our computer simulation.

This is explained by the overhead in calculating the probabilistic temperature-function in Simulated Annealing (or the mutate-reproduce-selection operations in Genetic Algorithms) that are used as the acceptance criteria for the random candidate solutions and therefore the proposed entropy derived function in QA has a smaller running time overhead.

The running time cost for the proposed algorithm scales linearly to input with length n and the solution can be found in polynomial time in any Turing Machine. In Table 11 we have a comparison between classes of computational time complexity.

Table 11

Classes of computational complexity.

Runtime Complexity	Computational Class	Time to Convergence (1/8)	Solution (Search)Space Volume	Example Algorithm
O(1)	Constant	0000000000	0000000000
O(log n)	Logarithmic	0000000001	0000000001	Binary Search
O(n)	Linear	0000000011	0000000011	Linear Search
O(n log n)	Linearithmic time	0000000111	0000000111	k-opt method
O(n2)	Quadratic	0000001111	0000001111	Nearest neighbor (NN)
O(n3)	Cubic	0000011111	0000011111	Christofides and Serdyukov
O(nk)	Polynomial	0000111111	0000111111	A*
O(2n)	Exponential	0001111111	0001111111
O(n!)	Factorial	0011111111	0011111111	Brute-Force
O(inf)	Infinite Time	0111111111	0111111111

The proposed method has limitations. It needs a larger running time to converge for small instances if compared to heuristics such as 2opt and Greedy Algorithm, as it must run until the predefined max number of interactions parameter value is reached.

We have also observed that the local search methods such as 2opt, converge with less running time when the input is pre-sorted and thus help avoiding the algorithm to being lock down in local minima solutions. However, this implies that a predefined prefix schema must be directly encoded in the input string values, with the goal to improve running time performance. The pre-processing of the input string works as a prefix set for filtering “above average” solutions. This is explained by the Kolmogorov randomness of a string.

Alternatively, the proposed method does not need such implementation bias. This behavior can be explained by Algorithm Information Theory. The 2opt method for example is sensitive to the initial solution set sequence and if provided with an initial state with more noise than the running time also increases.

This means there are more elements to verify in the search space and thus more time is needed until converge. In the other hand, if there is less noise in the initial state, than the sub-optimal end state is found quickly. In comparison the proposed model is resistant to variations in the initial path sequence positions.

Results from SA simulation: Best tour cost found

The statistical description for the SA method distribution with n = 50 nodes and length N = 60 is described as follow

Sample size: 60

Median: 961.0134322

Minimum: 679.4900154

Maximum: 1358.45442

First quartile: 865.4905371

Third quartile: 1057.63755725

Interquartile Range: 192.14702015

Outlier: 1358.45442

The boxplot for the SA distribution is illustrated in Fig 37

Fig 37

Boxplot for the SA simulation.

Simulation review

As with any heuristics and metaheuristics, it is not an exact process defined by a general linear function, but the results from the statistical analysis demonstrate the algorithm’s quality are significant. In this paper we have demonstrated the statistical significance of the results, as the p-value for the t-Test with Unequal Variances between the Simulated Annealing (SA) heuristic (Benchmark) and the proposed Quantitative Algorithm (QA), is less than the significance level for alpha with p< 0.05. The statistical test was performed for graphs with 20, 30 and 50 nodes and all trials have returned a significant result by rejecting the null hypothesis.

This supports the evidence that the schema proposed by heuristics methods such as GA, SA, AC or CE produces results that are, in average, equal or worse than the proposed QA method based in Information Theory and Entropy simulation, running for the same number of finite iterations. The best cost and running time are in average, found in the sample from the QA method, although it was also found in the control group SA, used as our benchmark. This result is expected, as outliers can happen and are expected to be found in random process in the long term.

The results obtain in this research showed a smaller runtime overhead in QA method possibly because of the simpler numerical calculations and instructions set in the code, if compared to the above-mentioned traditional heuristics. In GA, SA, AC and Neural Networks for example there are complex matrix, string and graph manipulations.

The Christofides algorithm also has to keep track and detect short-cuts between nodes in the know state search-space and thus increasing memory requirements. The proposed method does not need a buffer of illegal moves, such as proposed by the Tabu search method used to optimize the k-opt algorithm.

It also doesn’t need to continuously look for short-cuts or swapping ties, it works by generating a random sequence that encode a Hamiltonian graph (i.e. A path that visits all nodes exactly once). After generating the random candidate solution there are only 3 conditions to decide:

Have we reached the maximum number of iterations defined in the input parameters? If yes than halt

If new path is better than the current best route than updates the current control state.

If the candidate solution is worse, than we accept the solution, according to a decaying Bernoulli process B(X) for random variable X and a probability density function estimation with entropy H(X) with dependent utility function Y = g(X).