Skip to content

Proposal: OpenCLGA

Jump to bottom
John Hu edited this page Apr 10, 2017 · 1 revision

Proposal 1 - Generic

The Thought of Generic

Since the Genetic Algorithm is an abstract algorithm, we don't need to bind any predefined type with this algorithm. So, the thought of this proposal is Generic.

The Design of Gene

We had already had a general Gene data structure in Python. It has a list of DNA, a list of DNA Candidates, and a mutate function, like:

class Gene:
    def __init__(self, dna, elements=HUMAN_DNA_ELEMENTS, name=""):
        self.elements = elements
        self.dna = dna
    def mutate(self, prob=0.5):
        # ... implementation ...

The variant variable of this Gene is the type of DNA. The type of DNA is the type of elements which is the candidates of the DNA. So, it is possible to probe the type of elements. If it is primitive types, like int, float, bool, char, we can just copy the data into CL. If it is object type, we can 1. index the elements, 2. convert DNA as int type, and copy the int value into CL.

So, we can generate a similar structure in CL, like this one:

typedef struct _Gene1 {
  T dna[n];
} Gene1;

T Gene1_Candidates[] = new T {candidate1, candidate2, candidate3, ..., candidateN};
int num_of_dna_in_gene1 = n;
int num_of_candidate_of_gene1 = N;
int size_of_dna_of_gene1 = sizeof(T);

void gene1_mutate(__global Gene1* gene, T[] candidates, int num_of_dna, int num_of_candidate) {
  // implementation of gene1 mutate
}

The definitions are:

  • T is the type of candidates which is primitive.
  • Gene1 is the Gene whose data type is T.
  • Gene1_Candidates is an array of all candidates of Gene1.
  • n is the number of DNA of Gene1.
  • N is the number of candidates of DNA of Gene1.

With this type, we can operate the Gene1 similar to python version.

The Design of Chromosome

The Chromosome is a list of Gene, and a crossover function. This structure looks simpler than Gene. But it supports a list of different types of Gene. Strictly speaking, it supports a list of different types of candidates of a Gene. According to the design of Gene, we should design the Chromosome as the following:

typedef struct _ChromosomeInternal {
  char* data;
} ChromosomeInternal;

typedef struct _Chromosome {
  Gene1 gene1;
  Gene2 gene2;
  ...
  GeneN geneN;
} Chromosome;

int num_of_gene = n;

chromosome_mutate(__global ChromosomeInternal* c, int index_of_gene) {
  switch (index_of_gene) {
    case 1:
      gene1_mutate((__global Gene1*)((__global char*) c + 0), Gene1_Candidates, num_of_dna_in_gene1, num_of_candidate_of_gene1);
      break;
  }
}

chromosome_crossover(__global ChromosomeInternal* c) {
  // implementations of crossover
}

The Design of Fitness Function

The fitness function cannot be a generic version. So, we still need user to implement the fitness function like this:

float calc_fitness(__global Chromosome* c) {
  // implementation of fitness function
}

The Design of Main Function

The design of main function is pretty similar to current version. We only need to generate the procedure of GA, like:

__kernel void main(... a lot of parameters ...) {

  calc_fitness(thread_chromosome);

  barrier(CLK_GLOBAL_MEM_FENCE);

  sorting_fitness();
  calc_survivors();

  barrier(CLK_GLOBAL_MEM_FENCE);

  crossover_based_on_survivors(thread_chromosome);

  barrier(CLK_GLOBAL_MEM_FENCE);

  mutate(thread_chromosome);

}

In sequential GA, the crossover can be done with any two chromosomes. In parallel GA, we cannot do it because we may crossover a chromosome which is also crossovered by other chromosome.

So, we have three choices: 1. use elite list (the survivors), 2. group different chromosomes for crossover, 3. make it as a sequential. We should implement the elite list as our first version...

Proposal 2 - Enumerations

According to the proposal 1, we know that all DNA in a Gene can be converted to a enumeration type, even it is primitive types.

The proposal 2 is very similar to proposal 1. But we don't need to generate different types of Gene. We only need to know the size of each enumeration for each Gene, like:

#define NUM_OF_GENE 7
#define SIZE_OF_CHROMOSOME 17 // the sum of size of gene.
int size_of_gene_enum[] = {7, 5, 3, 3, 9, 6, 7};
int size_of_gene[] = {2, 3, 4, 3, 2, 1, 2};

void gene_mutate(int* gene, int size_of_gene, int enum_size) {
  // implementation of gene_mutate based on gene enum
}

void chromosome_mutate(int* chromosome) {
  for (int i = 0; i < NUM_OF_GENE; i++) {
    gene_mutate(chromosome, size_of_gene[i], size_of_gene_enum[i]);
    chromosome += size_of_gene[i];
  }
}

void chromosome_crossover(int* chromosome) {
  // implementation of chromosome
}

In this case, the fitness function cannot be similar to python version. It would be harder for a programmer who is not good at C to write it. But, this kind of design may be suitable for code generation from python, like py2opencl.

Unknown Things

  • Can we cast the __global variable to different types of __global type?? Issue 9
    • Yes, we can cast to any __global type.... This is a good news
  • Can we cast a pointer into a type which is stored at a variable??
    • No
  • How does C++ implement Generic?? May we do it in CL??
    • Maybe...

Final Decision

The current implementation is Proposal 2 which is an extension of Proposal 1. You may find the source code at our master branch of this repo.

Clone this wiki locally