TSP代写、代做algorithms留学生、代做Java，c/c++，Python程序语言

日期：2020-06-22 11:14

Traveling Salesman Problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities

and the distances between each pair of cities, what is the shortest possible route that

visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial

optimization, important in operations research and theoretical computer science.

Approaches taken to solve the TSP:

? Heuristic approaches;

? Memetic algorithms;

? Ant colony optimizations;

? Simulated annealing;

? Genetic algorithms;

? Neural networks;

? And various other methods for more specific variations

of the TSP.

4

Elastic Neural Network

Ridge (L2) and Lasso (L1) regression are some of the simple techniques to reduce

model complexity and prevent over-fitting which may result from simple linear

regression.

Elastic net regularization method includes both Lasso (L1) and Ridge (L2)

regularization methods. Lasso Regression (Least Absolute Shrinkage and Selection

Operator) adds “absolute value of magnitude” of coefficient as penalty term to

the loss function. Ridge regression adds “squared magnitude” of coefficient as

penalty term to the loss function.

https://en.wikipedia.org/wiki/Regularization_(mathematics)

ENN for TSP

TSP with elastic net:

? An array of cities (y);

? An array of network points (x);

? Network points are located in form of a circle;

? The elastic network evolves iteratively;

? Two forces act on each point of the network at every evolution step:

1. The first force attracts points to cities - stretches out the network;

2. The second force pulls the closest points to each other - tightens the network.

ENN for TSP

TSP with elastic net:

? An array of cities (y);

? An array of network points (x);

? Network points are located in form of a circle;

? The elastic network evolves iteratively;

? Two forces act on each point of the network at every evolution step:

1. The first force attracts points to cities - stretches out the network;

2. The second force pulls the closest points to each other - tightens the network.

ya ? Point(xa, ya)

xi ? Cit y(xi, yi)

- coordinates of the net point

- coordinates of the city

K - coefficient determining the temperature of the system (decreases as the network evolves)

Δya - change point position in 1 step

8

Recommended settings

α = 1. β = 1. initialK = 0.1 Kupdate period = 25 iterations

Knew

= max( 0.01, 0.99 *K );

Field size : X : [0,1]; Y : [0,1] - City coordinates are normalised

Points circle radius : 0.1

NofPoints = NofCities * numPointFactor; numPoimtFactor = 2.5

Stop conditions:

? By worst distance City<->closestPoint: 0.005 - 0.009;

? By maximal number of iterations: 10K - 50K

9

Scalar solution with graphical interface

IDE for your choice

Qt Creator is

recommended but

not required

You can use your existing code

code if you passed PRG-PR 2018

10

Qt Creator

Free download for open source users: https://www.qt.io/download

Wikipedia page: https://de.wikipedia.org/wiki/Qt_(Bibliothek)

Manual (German): https://de.wikibooks.org/wiki/Qt_für_C%2B%2B-Anf?nger

11

Data for tests

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/

Lists of cities with optimal solutions for some of them:

City list Optimal way

12

Implementation

1. With graphical interface

2. Console application for calculation speed tests

TSP EN -> implementation as a separate file / header is recommended

g++ consoleENTSP.cpp -O3 -fno-tree-vectorize -fopenmp -o run.out

Compilation flags are needed for console application

13

SIMDization

Optional:

? with given headers;

? with Vc;

? with basic SSE(or AVX) intrinsics;

? with your own headers.

Investigations:

? good/bad vectorizable code;

? data structures: SoA, AoSoA;

? the impact of the number of cities on the quality of vectorization

? …

14

Parallelization

Parallelization of the code with OpenMP

Investigations:

? effect of parallelization of different parts of the code;

? combination of SIMD and OpenMP;

? the impact of the number of cities on the quality of parallelization;

? speed up with different numbers of threads/cores used (if possible);

? …