tsp_results.md

Traveling Salesman Problem

For hybrid:

• max number of iterations: 50

• max no improvement iterations : 10

• improvement threshold : 0.005s

• calculated points: 79 from 79

• points from cache: 0 from 79

• number of nodes: 4

• execution time: 0.018s

• parameters:

┌─────────────┬────────┬────────┬─────────┬─────────────┬──────────┬─────────┬────────┐
│             │ start  │ min    │ max     │ sum of diff │ expected │ changes │ final  │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ temperature │ 0.8572 │ 0.00   │ 1.00    │ 0.14        │ 0.00     │ 50      │ 0.9999 │
│ decrease    │        │        │         │             │          │         │        │
│ coefficient │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 150    │ 10.00  │ 200.00  │ 2920.64     │ 35.19    │ 50      │ 54     │
│ mutations   │        │        │         │             │          │         │        │
│ per         │        │        │         │             │          │         │        │
│ dynasty     │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ mutation    │ 0.57   │ 0.00   │ 1.00    │ 21.60       │ 0.26     │ 50      │ 0.02   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ crossover   │ 0.56   │ 0.00   │ 1.00    │ 17.49       │ 0.21     │ 50      │ 0.31   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ elitism     │ -0.13  │ -      │ -       │ -           │ -        │ -       │ 0.66   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 35     │ 1.00   │ 100.00  │ 152.19      │ 1.83     │ 50      │ 30     │
│ stale       │        │        │         │             │          │         │        │
│ iterations  │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ population  │ 148    │ 1.00   │ 1000.00 │ 20174.02    │ 243.06   │ 50      │ 10     │
│ size        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ dynasties   │ 1982   │ 100.00 │ 2000.00 │ 63109.09    │ 760.35   │ 50      │ 130    │
│ limit       │        │        │         │             │          │         │        │
└─────────────┴────────┴────────┴─────────┴─────────────┴──────────┴─────────┴────────┘

List:

• max number of iterations : limit of total iterations of optimization process, termination condition
• max no improvement iterations : max amount of steps performed without detected improvement, termination condition
• improvement threshold : minimal value detected as improvement in objective function result
• termination reason : the reason why optimization process was stopped
• iterations number : actual number of iterations performed during optimization
• resumed after stale : how many times optimization progress was resumed after some iterations without improvement
• points from cache : points calculated during previous optimizations and read from cache
• number of nodes : number of nodes in graph representing cities from traveling salesman problem
• execution time : duration of shortest found hybrid optimization process using final parameters, measured in seconds

Table:

• start : initial value of parameter in starting point
• min : lower bound of parameter
• max : upper bound of parameter
• sum of diff : sum of absolute differences between starting value and next value
• expected : mathematical expectation of difference between starting value and next value
• changes : number of successful changes of parameter value to more optimal
• final : calculated value of parameter for which execution time was the lowest

For SA:

• max number of iterations: 50

• max no improvement iterations : 10

• improvement threshold : 0.005s

• calculated points: 33 from 33

• points from cache: 0 from 33

• number of nodes: 4

• execution time: 0.007s

• parameters:

┌─────────────┬────────┬────────┬─────────┬─────────────┬──────────┬─────────┬────────┐
│             │ start  │ min    │ max     │ sum of diff │ expected │ changes │ final  │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ temperature │ 0.1471 │ 0.00   │ 1.00    │ 8.73        │ 0.35     │ 17      │ 1.0000 │
│ decrease    │        │        │         │             │          │         │        │
│ coefficient │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 112    │ 10.00  │ 200.00  │ 188.84      │ 7.55     │ 17      │ 110    │
│ mutations   │        │        │         │             │          │         │        │
│ per         │        │        │         │             │          │         │        │
│ dynasty     │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ mutation    │ 1.00   │ 1.00   │ 1.00    │ 0.00        │ 0.00     │ 0       │ 1.00   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ crossover   │ 0.00   │ 0.00   │ 0.00    │ 0.00        │ 0.00     │ 1       │ 0.00   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ elitism     │ -0.00  │ -      │ -       │ -           │ -        │ -       │ 0.00   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 99     │ 1.00   │ 100.00  │ 1208.63     │ 48.35    │ 17      │ 100    │
│ stale       │        │        │         │             │          │         │        │
│ iterations  │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ population  │ 1      │ 1.00   │ 1.00    │ 0.00        │ 0.00     │ 0       │ 1      │
│ size        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ dynasties   │ 808    │ 100.00 │ 5000.00 │ 38996.81    │ 1559.87  │ 17      │ 123    │
│ limit       │        │        │         │             │          │         │        │
└─────────────┴────────┴────────┴─────────┴─────────────┴──────────┴─────────┴────────┘

List:

• max number of iterations : limit of total iterations of optimization process, termination condition
• max no improvement iterations : max amount of steps performed without detected improvement, termination condition
• improvement threshold : minimal value detected as improvement in objective function result
• termination reason : the reason why optimization process was stopped
• iterations number : actual number of iterations performed during optimization
• resumed after stale : how many times optimization progress was resumed after some iterations without improvement
• points from cache : points calculated during previous optimizations and read from cache
• number of nodes : number of nodes in graph representing cities from traveling salesman problem
• execution time : duration of shortest found hybrid optimization process using final parameters, measured in seconds

Table:

• start : initial value of parameter in starting point
• min : lower bound of parameter
• max : upper bound of parameter
• sum of diff : sum of absolute differences between starting value and next value
• expected : mathematical expectation of difference between starting value and next value
• changes : number of successful changes of parameter value to more optimal
• final : calculated value of parameter for which execution time was the lowest

For GA:

• max number of iterations: 50

• max no improvement iterations : 10

• improvement threshold : 0.005s

• calculated points: 51 from 58

• points from cache: 7 from 58

• number of nodes: 4

• execution time: 0.036s

• parameters:

┌─────────────┬────────┬────────┬─────────┬─────────────┬──────────┬─────────┬────────┐
│             │ start  │ min    │ max     │ sum of diff │ expected │ changes │ final  │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ temperature │ 0.9963 │ 0.00   │ 1.00    │ 0.05        │ 0.00     │ 32      │ 1.0000 │
│ decrease    │        │        │         │             │          │         │        │
│ coefficient │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 170    │ 10.00  │ 200.00  │ 2888.32     │ 53.49    │ 32      │ 24     │
│ mutations   │        │        │         │             │          │         │        │
│ per         │        │        │         │             │          │         │        │
│ dynasty     │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ mutation    │ 0.39   │ 0.10   │ 1.00    │ 7.22        │ 0.13     │ 32      │ 0.10   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ crossover   │ 0.81   │ 0.10   │ 1.00    │ 8.82        │ 0.16     │ 32      │ 0.28   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ elitism     │ -0.20  │ -      │ -       │ -           │ -        │ -       │ 0.61   │
│ rate        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ max         │ 58     │ 1.00   │ 100.00  │ 1589.45     │ 29.43    │ 32      │ 100    │
│ stale       │        │        │         │             │          │         │        │
│ iterations  │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ population  │ 572    │ 10.00  │ 2000.00 │ 38470.00    │ 712.41   │ 32      │ 46     │
│ size        │        │        │         │             │          │         │        │
├─────────────┼────────┼────────┼─────────┼─────────────┼──────────┼─────────┼────────┤
│ dynasties   │ 1824   │ 100.00 │ 2000.00 │ 34862.61    │ 645.60   │ 32      │ 115    │
│ limit       │        │        │         │             │          │         │        │
└─────────────┴────────┴────────┴─────────┴─────────────┴──────────┴─────────┴────────┘

List:

• max number of iterations : limit of total iterations of optimization process, termination condition
• max no improvement iterations : max amount of steps performed without detected improvement, termination condition
• improvement threshold : minimal value detected as improvement in objective function result
• termination reason : the reason why optimization process was stopped
• iterations number : actual number of iterations performed during optimization
• resumed after stale : how many times optimization progress was resumed after some iterations without improvement
• points from cache : points calculated during previous optimizations and read from cache
• number of nodes : number of nodes in graph representing cities from traveling salesman problem
• execution time : duration of shortest found hybrid optimization process using final parameters, measured in seconds

Table:

• start : initial value of parameter in starting point
• min : lower bound of parameter
• max : upper bound of parameter
• sum of diff : sum of absolute differences between starting value and next value
• expected : mathematical expectation of difference between starting value and next value
• changes : number of successful changes of parameter value to more optimal
• final : calculated value of parameter for which execution time was the lowest

Summary:

┌────────┬─────────────┬───────────┬──────────┬───────────┬─────────┬────────────┬────────────┬───────────┬───────────┐
│ mode   │ temperature │ max       │ mutation │ crossover │ elitism │ max        │ population │ dynasties │ execution │
│        │ decrease    │ mutations │ rate     │ rate      │ rate    │ stale      │ size       │ limit     │ time      │
│        │ coefficient │ per       │          │           │         │ iterations │            │           │           │
│        │             │ dynasty   │          │           │         │            │            │           │           │
├────────┼─────────────┼───────────┼──────────┼───────────┼─────────┼────────────┼────────────┼───────────┼───────────┤
│ hybrid │ 0.9999      │ 54        │ 0.02     │ 0.31      │ 0.66    │ 30         │ 10         │ 130       │ 0.018s    │
├────────┼─────────────┼───────────┼──────────┼───────────┼─────────┼────────────┼────────────┼───────────┼───────────┤
│ SA     │ 1.0000      │ 110       │ 1.00     │ 0.00      │ 0.00    │ 100        │ 1          │ 123       │ 0.007s    │
├────────┼─────────────┼───────────┼──────────┼───────────┼─────────┼────────────┼────────────┼───────────┼───────────┤
│ GA     │ 1.0000      │ 24        │ 0.10     │ 0.28      │ 0.61    │ 100        │ 46         │ 115       │ 0.036s    │
└────────┴─────────────┴───────────┴──────────┴───────────┴─────────┴────────────┴────────────┴───────────┴───────────┘

• temperature decrease coefficient : coefficient by which temperature is lowered at each iteration of optimization process
• max mutations per dynasty : max number of mutations used to produce vital individual in dynasty
• mutation rate : percent of individuals in population that are created using mutation
• crossover rate : percent of individuals in population that are created using crossover of selected parents
• elitism rate : percent of most fit individuals in population that are cloned without changes
• sum of mutation rate, crossover rate and elitism rate always equals 1
• max stale iterations : max allowed number of iterations that do not produce individuals with better fittness
• population size : number of individuals in population
• dynasties limit : max number of dynasties of new solutions produced during optimization process, terminates if exceeded
• execution time : time spent searching for optimal solution, measured in seconds

To run:

• Sudoku problem: cargo test -- --ignored find_opt_params_sudoku
• Traveling salesman problem: cargo test -- --ignored find_opt_params_tsp