Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature/partially matched uniform cx #11

Merged

Conversation

aneksteind
Copy link

@aneksteind aneksteind commented Apr 27, 2020

An implementation of "uniform partially matched crossover". An example is given in this paper in section 4.4.4. Useful for problems such as traveling salesman and genotypes that require uniquely-labeled genes 0 through N to remain present in the chromosome following crossover. An example of the problem having such a crossover alleviates:

Parent 1: [1,2,3,4,5]
Parent 2: [5,4,3,2,1]

Single point crossover after the 2nd index

Child 1: [5,4,3,4,5]
Child 2: [1,2,3,2,1]

If you imagine the genes as stops along a route, the resulting genotypes are no longer valid because 2 locations are skipped in each child representation. This is the problem that partially-matched crossover is meant to alleviate; it's an element-preserving operation.

@aneksteind aneksteind force-pushed the feature/partially_matched_uniform_cx branch 2 times, most recently from 4015496 to 79714f3 Compare April 27, 2020 01:41
@aneksteind aneksteind marked this pull request as draft April 27, 2020 01:47
@aneksteind aneksteind force-pushed the feature/partially_matched_uniform_cx branch from 79714f3 to 6e092e0 Compare April 27, 2020 03:27
@Martin1887
Copy link
Owner

This method seems interesting :).

But why do you add the StableVec dependency? Is it necessary?

@aneksteind
Copy link
Author

@Martin1887 It was needed because on crossover.rs line 178 for example, if an element is removed from the vector, the locations of the other elements need to remain in place. Otherwise the list of indices will become out of date and have the potential to cause an out-of-bounds panic. I wrestled with this for a while so if you have another idea I'm happy to discuss it.

@aneksteind aneksteind marked this pull request as ready for review April 30, 2020 00:34
@aneksteind
Copy link
Author

aneksteind commented Apr 30, 2020

@Martin1887 I think this is ready for review/feedback.

@Martin1887
Copy link
Owner

I have reviewed it a bit more. Could not be used a Vec<Option> putting as None the popped values instead of removing in a StableVec?

If the response is negative it could be merged too as it, but it is convenient to reduce the dependencies.

I will probably revisit it when I have more free time to try to optimize it anyway (probably I will not be able to, your implementation seems good :-)).

@aneksteind aneksteind force-pushed the feature/partially_matched_uniform_cx branch from 803ad4b to c716381 Compare May 3, 2020 01:07
@aneksteind
Copy link
Author

@Martin1887 I like your suggestion and hadn't thought of it, just changed it to match.

@aneksteind aneksteind force-pushed the feature/partially_matched_uniform_cx branch from c716381 to ca3dae4 Compare May 3, 2020 02:20
@Martin1887 Martin1887 merged commit bd51140 into Martin1887:3.0 May 3, 2020
@Martin1887
Copy link
Owner

OK, merged. If i do changes in the future in this crossover I will tell you.

@Martin1887
Copy link
Owner

Hello.

I have revised your implementation and I think that the i1 and i2 vectors are not correctly initialized causing that the crossover does nothing, retrieving children equal to parents. If I have understood correctly the paper, these vectors must be the index in which the individual has that value meanwhile your implementation generates vectors with value equal to the index.

In addition, I don't like the use of std::mem::replace, so I will think another manner of implement that.

Kind Regards.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants