CODEWITHSUNDEEP
c++genetic-algorithmopenframeworksvoronoievolutionary-algorithm
freddy
freddy

Reputation: 17

Is it necessary with binary encoding in genetic algorithms?

I'm doing a project exploring the use of genetic algorithms in architecture, where we use an evolutionary approach for creating Voronoi tessellation in 3d. This is done using ofxVoro++ for openFrameworks (c++).

Our chromosomes for the Genomes is a vector (list) of points in 3D. We have implemented single- and two-point crossover and a mutation, which randomises these points with a certain probability. In most examples I've seen, the genome is encoded binarily, which I presume would cause mutation and crossover to act differently.

So my question is this: Are there any other benefits to binary encoding (except speed) and how would you handle such an encoding/decoding in c++? Going from binary to a list of 3d-points.

Best regards, Fred

Upvotes: 0

Views: 1469

Answers (3)

Redlion
Redlion

Reputation: 81

I used different GA in logistic and finance problems. Very often I do not use binary representation. The first example that I can give you is the TSP problem:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Here I used standard representation: the chromosome is an array of integer, each value represents the city.

So, it depends on the type of problem that you are trying to solve, if you can find a way to implement the GA without a binary representation you do not need any adjustment. Furthermore I prefer the natural representation because is more simple to understand, while debugging the code, if your GA is working as you want.

Upvotes: 1

jaybers
jaybers

Reputation: 2211

Crossover and mutation are different operators. Crossover uses existing genetic. Mutation introduces new genetic material into the population. Without knowing much more info about your algorithm, randomizing points sounds like mutation. Mutation is typically performed a very low percent of the time (maybe 1%) where crossover can be rather high (50%).

So for your algorithm, I would not "modify" anything for crossover. Instead, for crossover, I would try to reposition material or simply take different portions of points from parents.

For mutation, it might make sense to add or subtract a small number to the points, thus modifying the points (mutation).

It is difficult to make suggestions without knowing more about your algorithm and chromosome representation.

Upvotes: 0

Mihai Oltean
Mihai Oltean

Reputation: 211

You can use real encoding also, but in this case is important what crossover and mutation you use. If your crossover is simply (p1+p2) / 2 or p1*a + p2*(1-a), you will not get good results.

A good crossover operator for real encoding was proposed by K. Deb in 1995. Here is the paper: http://www.complex-systems.com/pdf/09-2-2.pdf

Upvotes: 1

Related Questions