EAX Crossover operator about euro-neurips-2022 HOT 17 CLOSED

If you have time you can also look into this crossover operator!

from euro-neurips-2022.

Reference code: here (not sure if this is good, but it is fairly short, and if it works it might be easy to adapt to our setting), and here (much longer, might work, but is possibly quite hard to translate).

The first has no license, the second Apache 2.0. The first we can probably implement from scratch anyway, because it's so short. The second, not sure. Maybe reimplement, maybe vendor. I'd start with the first because it seems easier.

from euro-neurips-2022.

@blablaslack if you have worked on this, can you give a brief update here?

from euro-neurips-2022.

From Arnold et al. (2021):

According to Holland [20], the success of crossover-based genetic algorithms is largely because they promote the survival and propagation of high-quality building blocks

The more I read about crossovers, the more I think that EAX (and SREX) are really good crossover operators. EAX/SREX maintain the good building blocks/substructures from routes in a relatively efficient way. The advantage of EAX/SREX is that the route-based representation is used, rather than the giant-tour representation. Because OX and AEX don't take into account the routes they seem to be much less effective for the problem at hand. So I think it might be worthwhile to implement EAX (or other route-based representation crossovers).

from euro-neurips-2022.

Are we doing this? I am not sure. There's some code examples linked to above that could possibly be edited for our case. If it's not too much work, would you (@leonlan) be interested in trying this?

from euro-neurips-2022.

Are we doing this? I am not sure. There's some code examples linked to above that could possibly be edited for our case. If it's not too much work, would you (@leonlan) be interested in trying this?

I have read into this, but it's a lot of work due to possibly induced subtours that need to be repaired. I think that it depends a bit on our (leaderboard) performance on the static problem. If we are OK then I think we should skip this one. Otherwise I'll have an attempt at this.

from euro-neurips-2022.

@LuukPentinga Is this something you are willing to work on? This has been on my to-do list for very long, but I haven't gotten to it yet because it's a difficult coding thing. From what I saw you're pretty comfortable with cpp 😄 You can also help with dynamic stuff if you prefer!

from euro-neurips-2022.

I feel like this is probably a good idea, and could add value to the crossover operators. We know these matter from the OX/SREX discussion back in July, so having another one that's quite performant might well be worth it!

from euro-neurips-2022.

Sure, I can have a look. The reference paper talks about both single and block version of AEX, do you think we should consider both?

from euro-neurips-2022.

From Nagata et al. (2010):

By their nature (see Step 4), single strategy is more suited for relatively local improvement and block strategy tends to better support global improvement as more (geographically close) edges are considered.

I think both will be useful. Perhaps start with the single strategy? That one seems to be easier to implement.

Also, EAX may cause subtours which need to repaired at some point. The authors suggest a 2-OPT approach, but I think this is too much work (but feel free to do that as well!). An easier approach that I thought of is as follows.

• Consider a subtour $T$. Assume that $(a, b, c)$, is a cycle, i.e. $c$ goes to $a$.
• Try out all tours where we simply connect two adjacent nodes to the depot. In this case, $(a, b, c)$, $(b, c, a)$, $(c, a, b)$ are all the possibilities.
• Select the tour that minimizes the cost (incl. penalties).

This should be relatively simple and we don't have to mess with 2-OPT. The only potential issue I see is that this takes $O(|r|^2)$ where $|r|$ is the length of the route, since we need to evaluate all $|r|$ tours and evaluate the cost in $O(|r|)$ time.

from euro-neurips-2022.

If there's anything I can help with let me know!

from euro-neurips-2022.

@LuukPentinga Any update on this?

from euro-neurips-2022.

I am currently trying to sort this out, but running into trouble. First of, the described procedure in nagata et al. does not seem to be entirely correct. In particular, in step 2. Here they describe a way to construct what they call AB-cycles, but actually these do not exist most of the time.

For example:
Parent A has routes r1 = (d,u,d), r2 = (d,v,d) with d the depot.
Parent B has route r1 = (d,u,v,d).

Then, in step 1 we take all the edges that are in exactly one parent (XOR). Here, from parent A we inherit (u,d) and (d,v), and from parent B we inherit (u,v).

In step 2 we mean to build an AB cycle from the edges from 1, which is a cycle that:

1. Has alternating edges from A,B,
2. Has edges from A in the opposite direction from B.

But in this case we can not construct such a graph as both edges to/from the depot are from parent A. Due to our initial solution (1 vehicle, 1 node) we can actually never make such a cycle. I feel like a workaround should be to just allow this, but now I'm running into all kinds of other trouble.

from euro-neurips-2022.

If I understand this correctly, does this procedure fail whenever one of the two parents is a 1-client-per-vehicle solution? Or are there more cases where it fails? If it's the former, then I suggest to just shortcut the EAX procedure and return one of the parents (since this an edge case).

from euro-neurips-2022.

No, it should be far more often than this. I think it typically occurs when one parent uses 1 vehicle for a set of nodes, while another uses 2 for the same set. For example (0,1,2,3,4,0) for A and (0,1,2,0) and (0,3,4,0) for B results in a case where the only cycle is (0,2,3,0), again with one edge from the one parent, and 2 from the other.

from euro-neurips-2022.

What if we ignore edges involving the depot?

from euro-neurips-2022.

The competition's about to end, and I think we can be pretty happy with the results of yesterday's submission. I do not think it is worth the risk to change anything. Since #121 is, as far as I can tell, unfinished, there's no point in trying anything EAX-related anymore.

I'm closing this issue, and the related pull request.

from euro-neurips-2022.