LDEE - Low-Dimensional Euclidean Embedding for Visualization of Search Spaces in Combinatorial Optimization
This web page contains additional information for the paper entitled "Low-Dimensional Euclidean Embedding for Visualization of Search Spaces in Combinatorial Optimization".
If you have any suggestions or questions concerning this website feel free to contact me at krzysztof.michalak@ue.wroc.pl
Tools overview
This example uses several command-line tools to process data and prepare visualizations.
| Name | Description |
| ExtractUniqueSolutions | A tool that preprocesses a dataset consisting of the solution file and attributes file in such a way that only one copy of each solution is kept. If the dataset contains duplicate solutions, this preprocessing is required before the NeighbourProb tool is used. |
| NeighbourProb |
A tool that calculates neighbour probabilities subsequently used by the t‑SNE embedding tool.
The neighbour probabilities calculation step is performed separately, because it takes lots of time, and can be parallelized using a computational cluster.
Warning: The NeighbourProb tool requires solutions (e.g. permutations) to be unique. If you get the error message: The dataset contains duplicate solutions. Either prepare a dataset so that it contains unique solutions only or use the ExtractUniqueSolutions tool to fix the dataset.
you have to prepare the dataset with only one copy of each solution or use the ExtractUniqueSolutions to preprocess the dataset. |
| CombineFiles | A tool that combines files produced by the NeighbourProb tool when run in parallel runs. |
| TSNEEmbedding | A tool that performs the t‑SNE embedding. |
| TransformData | A tool that applies simple transformations (e.g. rotations) to data produced by the TSNEEmbedding tool. Such transformations can be useful as a preprocessing for the VacuumEmbedding tool if the points produced by t-SNE can better fit a square grid if rotated or scaled. |
| VacuumEmbedding | A tool that performs the Vacuum Embedding. |
| HeightMap | A tool that plots height maps using solution attributes and coordinates produced by TSNEEmbedding or VacuumEmbedding. |
| PopulationDynamics | A tool that plots solutions from consecutive generations of a population based metaheuristic (e.g. an evolutionary algorithm) on height maps using solution attributes, coordinates produced by TSNEEmbedding or VacuumEmbedding, and a file listing solution IDs for consecutive generations. |
Using the tools listed in Table 1., data can be processed by following the workflow presented in Figure 1.
Figure 1. An overview of the LDEE workflow (click to enlarge).
Color palettes
TSNEEmbedding, VacuumEmbedding, HeightMap, and PopulationDynamics tools can use various color palettes for plotting visualizations. The available palettes are:
- gray
- gray_reverse
- rainbow (default)
In order to select the palette, use the --height-map-palette command line parameter, for example --height-map-palette=gray.
The --palette-start and --palette-end parameters can be used to select the color assigned to the minimum and the maximum value, respectively.
For example, you can set --palette-start=0.3 and --palette-end=0.7 when using the rainbow palette to use colors ranging from light blue to orange (instead of the default range from dark blue to dark red).
By default, the minimum value of the attribute is mapped to the palette starting color (e.g. dark blue for the rainbow palette) and the maximum value of the attribute is mapped to the palette ending color (e.g. dark red for the rainbow palette) and the intermediate values of the attribute are mapped linearly to the colors of the palette.
The --scale-log parameter causes the logarithm of the attribute value to be mapped to the color, and the --scale-power causes a power of the attribute value to be used (e.g. setting --scale-power=2 causes the square of the attribute value to be mapped to the color).
When visualizing multiple datasets, it may be useful to keep the color scale range fixed (e.g. dark blue should always correspond to 0 and dark red should always correspond to 100), even if the minimum and maximum values of the attribute vary between datasets.
In such case you can set the range of attribute values mapped to the palette using the --scale-min and --scale-max parameters.
For example, you can set --scale-min=0 and --scale-max=100.
Multiobjective Firefighter Problem example
This example shows how to use LDEE tools to produce visualizations of solutions obtained for a multiobjective Firefighter Problem (FFP) using an Evolutionary Algorithm.
This example uses the data files and the set of LDEE tools.
If you want to skip some steps you can get precalculated results here. Note, that your own results as well as the precalculated ones may be slightly different from the presented below, because of the intrinsic randomness of the used methods.
Note: To prevent automatic opening of the contents the files have their extensions changed. Rename these files to *.zip
Problem description
In the Firefighter Problem (FFP) fire spreads in discrete time steps on a graph with Nv vertices.
The vertices can be in one of three states: 'B' - burning, 'D' - defended, 'U' - untouched (neither burning nor defended).
Initially Ns vertices are burning.
In each time step Nf vertices can become defended by firefighters (and be immune to fire until
the end of the simulation). The spreading of fire continues until it can no longer spread either because it is surrounded by defended vertices or because all the undefended vertices are burning.
Solutions of the Firefighter Problem are permutations which determine in what order to protect the vertices in the graph.
In the single-objective FFP the evaluation of a solution is the number of non-burning vertices when the fire stops spreading.
In the multiobjective FFP with m objectives there are m different values v1(v), ..., vm(v) assigned to each graph vertex v.
The m objectives attained by a solution are calculated by simulating the spreading of fire and when the simulation stops the values vj(v)
for non-burning vertices are added together to obtain the objective fj for j = 1, ..., m.
Evolutionary algorithm
In this example an Erdős-Rényi graph with Nv = 500 vertices and edge probability Pedge = 0.0055 was used and the number of objectives was m = 2. Each value vj(v) was randomly drawn from the uniform distribution over [0, 100]. The number of initially burning vertices was Ns = 1 and the number of vertices defended by firefighters in each time step was Nf = 2.
The parameters of the evolutionary algorithm were set to:
| Symbol | Description | Value |
| Ngen | Number of generations | 250 |
| Npop | Population size | 500 |
| Pcross | Crossover probability | 1.0 |
| Pmut | Mutation probability | 0.05 |
Input data
During the algorithm run there were Ngen·Npop = 125 000 specimens in total in all the populations, among which there were 25 600 different specimens. The moffp_solutions.txt file contains solutions (specimens) in the format:
| Solution ID | Permutation |
55 |
474, 333, 265, 467, 199, 111, 233, ... |
56 |
108, 148, 38, 64, 197, 292, 491, ... |
57 |
289, 226, 342, 361, 211, 81, 62, ... |
58 |
227, 105, 255, 390, 64, 81, 153, ... |
... |
... |
in which the first number is the solution ID and then there is the permutation representing the solution. The elements of the permutation are integers starting from 0. Attributes of the solutions are stored in the attributes.txt in the format:
| Solution ID | Gen. num. | Objective f1 | Objective f2 | fU |
55 |
1 |
780.331675140342 |
495.134563834935 |
0 |
56 |
1 |
606.734873636968 |
605.217153348596 |
0 |
57 |
1 |
621.03719246622 |
542.595817680748 |
0 |
58 |
1 |
560.18866731794 |
390.447313008107 |
1 |
... |
... |
... |
... |
... |
which stores the solution ID, the generation number in which a given solution first appeared, the values of the objectives f1 and f2 and the fU value which represents the number of graph vertices in the 'U' state at the end of the simulation, that is, vertices which were not defended, but fire has not reached them. These are vertices which were cut off from fire by other, defended vertices. In general, it is beneficial to increase the fU value, because vertices in the 'U' state contribute positively to the f1 and f2 objectives and do not use firefighters in any of the time steps (thus not using up the Nf limit). On the other hand, maximizing fU does not automatically mean maximizing f1 or f2, because some solutions may have lower fU, but may involve protecting vertices with higher v1(v) and v2(v) values. Thus, in this example fU is used as the third objective, separately from f1 and f2.
Nearest neighbour probabilities
To calculate nearest neighbour probabilities run:
NeighbourProb.exe --problem-type=perm moffp_solutions.txt
As these calculations take long to complete for permutations of size 500, it is best to use parallel infrastructure and run:
NeighbourProb.exe --problem-type=perm --batch-size=100 --batch-number=0 moffp_solutions.txt
...
NeighbourProb.exe --problem-type=perm --batch-size=100 --batch-number=255 moffp_solutions.txt
The above-shown commands should be executed one per cluster node.
If calculations are run in 256 parallel jobs, they complete on average in about 6-7 minutes on an Intel Xeon E5-2670 CPU, however some of them take longer and complete in about 13 minutes.
If parallelized to 26 batches of 1000 elements the calculations should complete in about 45-60 minutes.
The estimated running time using a single thread (no parallelism) is 17-18 hours on the same equipment.
The resulting moffp_nearest_neighbour_probabilities.txt file contains nearest neighbours and their probabilities in the format:
| Solution ID | Neighbour idx (odd rows) / probabilities (even rows) |
55 |
699 654 171 677 1335 874 3313 1213 1114 ... |
55 |
0.298110741688634 0.164553840285086 ... |
56 |
165 974 5684 6361 1005 6060 15193 14341 ... |
56 |
0.326887752675726 0.0682274299260752 ... |
... |
... |
If the calculations are ran in parallel, multiple files are generated, named as follows:
moffp_nearest_neighbour_probabilities.txt.000000
...
moffp_nearest_neighbour_probabilities.txt.000255
These files can be combined into one using the "CombineFiles" tool:
CombineFiles.exe moffp_nearest_neighbour_probabilities.txt 255
Warning: The NeighbourProb tool requires solutions (e.g. permutations) to be unique. If you get the error message:
The dataset contains duplicate solutions. Either prepare a dataset so that it contains unique solutions only or use the ExtractUniqueSolutions tool to fix the dataset.
you have to prepare the dataset with only one copy of each solution or use the ExtractUniqueSolutions to preprocess the dataset.
The t-SNE Embedding
The t-SNE embedding is obtained by running the following command.
The optional parameter --plots turns on plotting of each iteration of the algorithm.
Run either:
TSNEEmbedding.exe moffp_nearest_neighbour_probabilities.txt
or:
TSNEEmbedding.exe --plots --plot-size=10 moffp_nearest_neighbour_probabilities.txt moffp_attributes.txt 2
Both of which produces the moffp_embedded_tsne.txt file with the following format:
| Solution ID | X Coordinate | Y Coordinate |
55 |
3.80609591550068 |
0.10518352167755 |
56 |
3.6567498896134 |
0.0492027717014185 |
57 |
3.87000299122556 |
0.113489316750194 |
58 |
3.85896356239319 |
-0.014547308927447 |
... |
... |
... |
The Vacuum Embedding
The Vacuum Embedding is obtained by running the following command.
The optional parameter --plots turns on plotting of each iteration of the algorithm.
Run either:
VacuumEmbedding.exe moffp_embedded_tsne.txt
or:
VacuumEmbedding.exe --plots moffp_embedded_tsne.txt moffp_attributes.txt 2
Both of which produce the moffp_embedded_ve.txt file with the following format:
| Solution ID | X Coordinate | Y Coordinate |
55 |
116 |
41 |
56 |
105 |
40 |
57 |
122 |
49 |
58 |
118 |
38 |
... |
... |
... |
Note: The Vacuum Embedding requires the number of points to be an exact square.
If your dataset does not represent an exact square, the preferred action is to remove some solutions before calculating nearest neighbour probabilities.
Alternatively, you can use the --skip-rows parameter of the VacuumEmbedding.exe program specifying the number of rows suggested by the VacuumEmbedding.exe program in the error message which says 'The number of solutions (<num_solutions>) is not a square.'.
For example, it the program says:
The number of solutions (50074) is not a square. Either:
a) Decrease the number of solutions to 223 x 223 = 49729 for example using the '--skip-rows=345' parameter
b) Increase the number of solutions to 224 x 224 = 50176
--skip-rows=345 parameter:
VacuumEmbedding.exe --skip-rows=345 moffp_embedded_tsne.txt moffp_attributes.txt 2
Visualizations
Based on the Vacuum Embedding results stored in the moffp_embedded_ve.txt file and the attributes in the moffp_attributes.txt file it is possible to visualize the generation number, the objectives and the fU value. To generate colur images run:
HeightMap.exe --height-map-palette=rainbow moffp_embedded_ve.txt moffp_attributes.txt 1 4
 (click to enlarge) |
 (click to enlarge) |
 (click to enlarge) |
 (click to enlarge) |
| Generation number |
Objective f1 | Objective f2 | Number of untouched vertices fU |
In these images blue corresponds to the smallest value and red corresponds to the largest value. To generate grayscale images run:
HeightMap.exe --height-map-palette=gray moffp_embedded_ve.txt moffp_attributes.txt 1 4
 (click to enlarge) |
 (click to enlarge) |
 (click to enlarge) |
 (click to enlarge) |
| Generation number |
Objective f1 | Objective f2 | Number of untouched vertices fU |
In these images dark shade corresponds to the smallest value and light shade corresponds to the largest value.
Differential plots can be obtained using the --pairwise-diff switch which produces these plots for all pairs of attributes in the
given range.
HeightMap.exe --pairwise-diff --height-map-palette=rainbow moffp_embedded_ve.txt moffp_attributes.txt 2 3
 (click to enlarge) |
 (click to enlarge) |
| Difference f1 - f2 | Difference f2 - f1 |
As previously, in these images blue corresponds to the smallest value and red corresponds to the largest value. It can be observed that in earlier generations (top-right corner) only such solutions could be found that optimize one of the objectives at the expense of the other, an effect which is visible as large differences shown as blue (left image) and red (right image) color. In later generations solutions that represent more balanced trade-offs are visible (green). Other observations can be made by comparing, as shown below, the graphs showing the generation number (left image, color), the objectives fj for j = 1, 2 (two middle images, grayscale) and the the number fU of graph vertices in the 'U' state (right image, grayscale). First of all, the solutions which optimize one of the objectives (either f1 or f2) are found relatively early in the search (arrows in the two middle images show the areas with the best found values of each objective represented by the lightest shade). As mentioned above in later generations the algorithm seems to have focused more on finding balanced trade-offs between the two objectives which can be seen as an area with a little darker shade for both objectives (bottom-left corner). Note, that, because solutions are shown only once in the graph and multiple copies of the same solution are not visualized, this does not mean that solutions optimizing each objective individually were not present in the population in later generations, but rather that no new solutions have been found improving these objectives individually in later generations. This may indicate that not enough selective pressure has been put on extending the Pareto front towards its edges. On the other hand, in later generations the algorithm found solutions that maximize the number of vertices in the 'U' state. This shows that it is possible to use the structure of the graph in such a way that defended vertices cut off some other vertices from fire. While this allowed finding balanced trade-offs between objectives (green areas in differential plots) it did not help in maximizing individual objectives (the area corresponding to the last generations in not the lightest in the plots for individual objectives).
 (click to enlarge) |
Population dynamics
Population dynamics can be visualized by plotting markers representing solutions in each population on a height map representing a selected attribute. Solutions are plotted at coordinates in a square grid assigned to them by the LDEE method. The Dots visualization type plots solutions from each generation in a separate image marking them using dots.
PopulationDynamics.exe --visualization-type=Dots moffp_populations.txt moffp_embedded_ve.txt
moffp_attributes.txt 2
 Generation 1 of 250 (click to enlarge) |
 Generation 100 of 250 (click to enlarge) |
 Generation 200 of 250 (click to enlarge) |
The Paint visualization type plots solutions from all generations in the same image marking them using dots with progressively changing colors.
PopulationDynamics.exe --visualization-type=Paint --height-map-palette=gray --palette-end=0.8
moffp_populations.txt moffp_embedded_ve.txt moffp_attributes.txt 2
 Generation 1 of 250 (click to enlarge) |
 Generation 100 of 250 (click to enlarge) |
 Generation 200 of 250 (click to enlarge) |
Running times
Calculation of nearest neighbour probabilities was carried out on a computer cluster with Intel Xeon E5-2670 CPUs. The t-SNE embedding, the Vacuum Embedding and visualizations were done on a single notebook with the Intel i7-6700HQ CPU running at 2.6 GHz and an nVidia GeForce 960M GTX graphics card (GPU). Table 8. presents running times of the calculations performed in this example. The total time is calculated using the maximum time from the first row, because this is how long the user needs to wait for all the jobs to complete.
| Step | Equipment | Time |
| Nearest neighbour probabilities | Computer cluster with Intel Xeon E5-2670 CPUs 256 parallel jobs |
(average) 6m 20s (maximum) 13m 24s |
| t-SNE Embedding | Notebook with the Intel i7-6700HQ CPU @ 2.6 GHz and an nVidia GeForce 960M GTX graphics card (GPU) |
7m 53s |
| Vacuum Embedding | 2m 59s | |
| Visualizations (all) | 0m 03s | |
| Total: | 24m 19s | |
«Back to research topics list