Conversation
…n't need initialization, which can be a costly operation depending on the chromosome)
…heuristics based ordered sub chromosomes crossovers
…ation and keep parameters + extended chromosome and fitness stubs for variable ranges and length
|
I can see the continuous control build failed because of c# language features. In the mean time, I think it would be a good idea to upgrade a few versions in the project, which would probably yield that build to pass. Most notably, I played a bit with your Benchmark.Net project, and the latest Benchmark.Net version has breaking changes with your code, but I'd be willing to do the updates. |
|
No problem to use the newer C# version, we are using 7.0 and you are probably using 8.0. |
|
OK it seems I was a bit overenthusiastic with the initial results. Apparently the OnePointChromosome was having difficulties with the extended-size StubChromosome, making it look like the WhaleOptimizer was performing particularly well, but actually the UniformCrossover is killing it with this task, overperforming the WhaleOptimizer with much better performances. This is not too unexpected though, since that chromosome's fitness landscape is pretty smooth without any local maxima, so it makes sense with enough genetic mixing, a standard crossover would suffice spreading the population and finding the maxima at the edges, whereas the ellicoidal search pattern of the WhaleOptimizer doesn't bring much to the table. This brings 2 suggestions:
Anyway, I'm gone for good now, and for a couple days. I hope the last commits to your comments were satisfactory, and that your code review is going smoothly. |
|
I was able to squeeze another couple hours since I was a bit frustrated with the latest results. I fixed a important bug with match randomization, and started reworking the Fluent API/parameter passing mechanism with Lambda Expression visitors. It's not functional yet, but I believe the hardest is behind. |
|
I very much like this library and I appreciate that there is effort to expand its capabilities and improve it. Thank you @jsboige for putting a lot of work in. Please do not take the following personally. I would like to add a perspective from what I perceive to be the general consesus of the operations research community. There are classical, well-established, tried and tested metaheuristics: Tabu-Search, Iterated Local Search, Greedy Algorithms, Simulated-Annealing, Evolutionary Algorithms, Genetic Algorithms, Ant-Colony-Optimization, and a few others. In recent years there has been an explosion of "new" metaheuristics, including: Whale-Optimization, Eukaryote Metaheuristic, Grey Wolf Optimization, and much much more. Those "new" metaheuristics are The argument is that the "new" metaheuristics are not, in fact, new. They just reheat and repackage concepts, ideas, operators, subroutines from classical metaheuristics under a new name. While among all those repackaged ideas there is some "truly innovative research of high quality" (Sörensen, 2015), it is hard to filter them out from all the noise, and hard to ascribe credibility to those new ideas. In rare exceptions, some of the few good, innovative ideas can also fit nicely into existing, classical frameworks, and improve them. But should not be sold as new under a different name. Why did/does this happen? In short: easy publications - an author can claim that it is "new". More options, and fancier algorithms, do not necessarily mean that they also perform better, e.g. demonstrated in Ruiz, Stützle 2007. Also, a plethora of options (and possibly multiple options with different names that ultimately lead to the same outcome) does not make it easier to use a certain algorithm/framework. I am not a maintainer of this library, so I have no say in what gets merged and what does not. It comes down to what @giacomelli thinks. I just wanted to put this perspective out there, as I fear that starting to accept additions like this could ultimate deteriorate the quality of this library (and create a lot of reviewing and maintenance work). I do have some questions and suggestions:
|
… GeometricMetaheuristicBase improvements
|
I'm closing this PR because I believe it's out of the scope of GeneticSharp: to provide the basics of algorithm genetics. Maybe this PR could be a "child" project of GeneticSharp, like "GeneticSharip-Contributions" or something like that. Feel free to re-open it to let us further discuss this possibility. |
This is a very large pull request that introduces a new powerful feature to GeneticSharp: Metaheuristics.
It comes with numerous fixes, tweaks and improvements, which are not necessarily related, so in order to make it easier to understand, I will also make 2 other smaller pull-requests that this one contains, related to issue #82. Hopefully we can validate those preparatory intermediate pull-requests before this one is entirely validated. Those pull-requests are #89 and #88.
Note that there isn't much code coverage yet, comments are lacking too, and there is probably some more work to do before it can be fully integrated in master branch, thus my proposal to merge it in develop first.
However, I believe it is clean enough for an initial review, and there are important heavy unit tests passing that should clear the way. This is also that I will have to postpone working on it for about a week, and I figured now that the upgrade has started yielding very promising results, you might be willing to give it a try a give me your feedback.
Now about it: Metaheuristics are a new kind meta-operators that will allow controling the evolution process through other native operators dynamically. In the last 20 years, a lot of succesful ones were introduced, often based on natural metaphors. They manage to better guide evolution through finely tuned exploration/exploitation tradeoff, and prevent early collapse to a local optimum, which standard GAs and GeneticSharp exhibits (see issue #47 for a discussion about it).
In order to integrate known Metaheuristics and corresponding capabilities, I believe the mealpy repository is going to be a reference, since it implements pretty much all of them.
For now, I have set to myself the objective to have one well known good Metaheuristic working, namely Whale Optimisation Algorithm (WOA), for which I strictly followed the easier original Matlab version.
The initial result can be seen in a factory class where I intend to implement add other famous Metaheuristics when initial integration is cleared. In order to make using Metaheuristcs easier, I have started providing the corresponding fluent API that is demonstrated through that initial example, and will be used throughout the other factory examples.
Another distinct Metaheuristic, which I also implemented and tested is the Eukaryote MetaHeuristic. It is of a different kind, because it leverages the available dynamical operator mechanism at the chromosome level rather than the evolution operators themselves as with other Metaheuristics. My work on that was largely inspired by the following publication introducing geometric crossover for Sudokus. The corresponding metaheuristics allows spliting a regular 81 cells chromosome into a 9 rows subchromosome karyotypes, and then using on each of them ordered crossovers and mutations preserving permutations. This is illustrated both in the Unit tests and in the updated gtk# application controller, though on this one you have to select the crossovers and mutation manually using the Gui.
The new Eurkaryote-based chromosome outperforms the existing Cells chromosome and prevents collapse to suboptimal solutions in certain cases, which was the intended behaviour. Note that it is still inferior to the recently improved existing PermutationChromosome, which has a reduced search space and doesn't need the chromosome splitting overhead.
Those two initial test-cases guided me designing all the capabilities needed for their implementation, and should provide robust examples on how to leverage the new capabilities: there is now a vast range of options available through the combination of Metaheuristics building blocks.
There is a lot of code-coverage to add now, together probably with a couple bugs to fix, and I will be willing to do most of the clean-up, though of course if you appreciate the contribution, I don't mind doing that work collaboratively.
About modifications to the existing code-base, I tried to keep the footprint relatively light. I encourage you to compare benchmarks with other branches. There shouldn't be too much impact. That is, of course, when using the default Pass-through Metaheuristic. When using a relatively heavy Metaheuristc with sub-components like the WOA, the overhead is more severe (more than 2X), but it is largely compensated by the fact that the search reaches much better fitness that the original GA wasn't capable of reaching with the suboptimal modal collapse aforementioned, and it does so with populations an order of magnitude smaller (I encourage you to analyse the initial compund unit test: the Metaheuristic based vastly outperforms the regular GA). Now it doesn't mean there isn't room for improvements . I believe the parameter passing mechanism, though functional, might be interesting to refactor both for speed and fluent usage.
Some of the other technical discussion will probably concern the other 2 pull-requests, which are preliminaries to this one, so I'll leave it at here now, with that already long description.
I hope this doesn't look too frightening, that you'll enjoy the contribution, and I'm definitely up for discussing what needs discussed.
Cheers