[meta] generalize tsp_cl_algo as a GA algorithm

[john-hu]

• separate crossover, mutation, fitness as three files
• implement non-repeatable crossover
• implement non-repeatable mutation
• implement repeatable crossover
• implement repeatable mutation
• generate gene/chromosome struct according to gene.py and chromoosome.py
• generate kernel entry function according to properties of algorithm.py.
  • crossover function,
  • mutation function, etc

[kilikkuo]

As far as I can think of ... 2 thing should be taken into account.

1. To support general poinit mutation (allow duplicated element inside a gene), a list of possible elements of a gene should be passed into OCL kernel. ==> Should not be a big problem.
2. The dna length of a gene is able to greater than 1, that is, are we gonna support genes with variable length ?
   I don't think it's a easy task. IMO, it's quite tough. We may need to create a 2-D array of chromosomes in OCL Kernel to make it easy for crossover. We may need extra array to deliver the length of each chromosome (or even gene).
   If we're not gonna support. Then user need to think of a way, e.g. fill additional 0 into a gene's dna sequence to make every gene equal in length.

Thoughts ?

[john-hu]

https://github.com/PyOCL/oclGA/wiki/Proposal-of-OpenCL-GA

To support general poinit mutation (allow duplicated element inside a gene), a list of possible elements of a gene should be passed into OCL kernel. ==> Should not be a big problem.

In my design, it can be passed through the source code generation. You give me a good hint that the data will be put at stack if I put the data in source code. And if we pass data through function call, the data will be in heap. That should be better....

The dna length of a gene is able to greater than 1, that is, are we gonna support genes with variable length ?

This is a nice catch. I don't think we need to implement it now. It's called GP if we have variable length gene. It is important and we need to implement it in the future. BTW, in my design, we can implement different Gene in both python and CL to support it.

I don't think it's a easy task. IMO, it's quite tough. We may need to create a 2-D array of chromosomes in OCL Kernel to make it easy for crossover. We may need extra array to deliver the length of each chromosome (or even gene).

This one is also a good point. I cannot find any use case now. And it is worth to have further discussion.

If we're not gonna support. Then user need to think of a way, e.g. fill additional 0 into a gene's dna sequence to make every gene equal in length.

I don't think so. We can fill a lot of 0 in python for user If we really need to say oclGA supports it.

[john-hu]

An example implementation of my proposal can be found here: https://github.com/PyOCL/oclGA/tree/1e2e0be35e66ecd08a5caaa882f73be886354783/evaluation/oclGA

[john-hu]

As per offline discussion, we found the implementation of crossover or mutation doesn't give us good solution. There are few docs for this topic here:

• http://user.ceng.metu.edu.tr/~ucoluk/research/publications/tspnew.pdf (paper)
• http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php (simple explanation)
• http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 (a java implementation)
• https://github.com/parano/GeneticAlgorithm-TSP (a very impressive implementation in JS, 200 cities in JS)

[john-hu]

The first version of oclGA is implemented at evaluation folder. I close this issue and file another for moving the code to root.