[ML] Operator selection about euro-neurips-2022 HOT 11 CLOSED

@leonlan I doubt we'll do this due to time pressure. But, should we apply the operators randomly instead (e.g., by fixing it to some arbitrary ordering at the start of the LS search)? A large part of the literature does this, and it might shake the search up a bit.

from euro-neurips-2022.

Data explanation

The raw/ folder contains files of the form *instance*.txt.
These files store results of local search operators applied over ten seconds of runtime (for each instance).
The data is rather raw: only a few statistics are collected, in addition to the solution before and after the operator.
This format is detailed below.

Each file contains many records of a local search application.
These are separated by a single empty line.
A record looks like this:

58 1
164 36
Route #1: 72 16 2 210 25 52 77 70 114 115 33 28 50 207 73 20 45 29 118 98 92 49 21 194 104
Route #2: 38 106 31 108 87 7 46 41 100 111 101 88 198 76 187 160 67 97 60
Route #3: 134 154 62 143 144 39 12 37 47 40 3 109 83 14 30 4 161 178 168 149 94 117
Route #4: 119 75 32 201 182 157 165 190 189 197 44 122 43 129 61 11 23 17
Route #5: 90 95 124 10 84 123 132 99 156 141 130 212 199 186 121 26 64 89 63 24 19 203 169 153 55
Route #6: 22 206 18 172 175 170 86 105 209 152 162 147 54 171 102 48 112
Route #7: 183 56 74 158 180 69 78 142 82 184 85 138 146 205 53 91 5 81 151 200 79
Route #8: 145 8 42 35 125 163 185 191 15 80 150 213 164 167
Route #9: 179 135 9 196 57 65 148 66 204 110 128 58 59 96 127 202 208 133 93
Route #10: 173 27 71 116 155 107 131 120 13 36 113 177 1
Route #11: 6 68 211 34 103 195 174 188 176 51 137 136 159 192 193 139 126 181 140 166
Cost 116603
1
NOP
2
Route #1: 72 16 2 210 25 52 77 70 114 115 33 28 50 207 73 20 45 29 118 98 92 49 21 194 104
Route #2: 38 106 31 108 87 7 46 41 100 111 101 88 198 76 187 160 67 97 60
Route #3: 134 154 62 143 144 39 12 37 47 40 3 109 83 14 30 4 161 178 168 149 94 117
Route #4: 119 75 32 201 182 157 165 190 189 197 44 122 43 129 61 11 23 17
Route #5: 90 95 124 10 84 123 132 99 156 141 130 212 199 186 121 26 64 89 63 24 19 203 169 153 55
Route #6: 22 206 18 172 175 170 86 105 209 152 162 147 54 171 102 48 112
Route #7: 145 8 42 35 125 163 185 191 15 80 150 213
Route #8: 183 56 74 158 180 69 78 142 82 184 85 138 146 205 53 91 5 81 151 200 79
Route #9: 179 135 9 196 57 65 148 66 204 110 128 58 59 96 127 202 208 133 93
Route #10: 173 27 71 116 155 107 131 120 13 36 164 167 113 177 1
Route #11: 6 68 211 34 103 195 174 188 176 51 137 136 159 192 193 139 126 181 140 166
Cost 116556

The record begins with the penalty terms: 58 for the load factor, 1 for the time warp.
Since these are dynamically altered during the search, they are stored here so the objective values can be meaningfully evaluated/compared.
For node operators, the next line presents the evaluated client pair (164 and 36).
For route operators, the route indices (starting at one) are printed instead.
Then, we get the solution state before applying an operator.
This is stored in CVRPLib format, as a list of routes (tools.py has methods for reading this solution, as well as the original instance data).
The final row of this state contains the cost, evaluated using the problem data for the instance indicated by the file name, and the penalty terms given earlier.
The next line, 1, indicates the applied operator (1, see below).
After this, one of two things happen: if a better solution was found, we get the new solution after applying the operator to the given pair.
If the solution was not improved, we print NOP instead.
In this case, operator 1 did not result in a better solution, so we got NOP.
We then move to the second operator: 2.
This operator did make an improvement, which is given by the solution state after applying the operator.
Here, the record ends: after an improving move, later operators are not evaluated.

Note: route and node operators are applied in different records.

The operators are as follows:

1. move_single_client
2. move_two_clients
3. move_two_clients_reversed
4. swap_two_client_pairs
5. swap_two_clients_for_one
6. swap_two_single_clients
7. two_opt_between_routes
8. two_opt_within_route
9. relocate_star
10. swap_star

relocate_star and swap_star are route operators, the rest operate on nodes.

from euro-neurips-2022.

@Y-Jansen one limitation of this is that each operator is applied one after another. So the sample is a little biased, on that moves are always performed in a fixed order, rather than just all at once and then seeing what happens.

If that's a problem you should let me know.

from euro-neurips-2022.

This looks relevant for operator selection. I'm not sure about the quality of the paper, but it's recent and the setting at least is roughly similar. QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows

from euro-neurips-2022.

The current implementation determines with probability intensificationProbability whether or not the route operators (9-10 from the list above) are applied to the solution. On the other hand, the node operators (1-8) are always applied by default. Route operators are more exhaustive than node operators, hence the ordering (I believe).

I think an interesting question would be: given the progress from the node operators, can we predict the success of applying route operators?

from euro-neurips-2022.

@Y-Jansen can you give an update on when you will be able to work on this?

from euro-neurips-2022.

@jaspervd96 @Y-Jansen Karimi-Mamaghan et al. (2022) is a really nice lit review. It goes into detail about learning operator selection in Chapter 7.1 - very relevant for this issue!

from euro-neurips-2022.

Plus it's easy to do by shuffling the route and node operators. Could you perhaps benchmark that on your cluster?

from euro-neurips-2022.

Plus it's easy to do by shuffling the route and node operators. Could you perhaps benchmark that on your cluster?

Sure I'll try it out.

from euro-neurips-2022.

@N-Wouda now that we merged #94, should we close this issue?

from euro-neurips-2022.

Yeah I think so, because I'm pretty sure we're not going to work on this anymore.

from euro-neurips-2022.