search

luca-scr / GA

An R package for optimization using genetic algorithms
http://luca-scr.github.io/GA/
91 stars 29 forks source link

Variant Permutation Optimisation #10

Closed datawookie closed 7 years ago

datawookie commented 7 years ago

Hi Luca,

Firstly, thanks for your GA package: I have used it a number of times in the past for optimising functions of real values and got great results.

I am presently working with an optimisation problem which looks like this: maximise a fitness metric which accepts a vector of 10 integer values. Those integers can vary between 1 and 4. So, for example, these are valid inputs to the fitness function:

1 1 1 1 1 1 1 1 1 1 1 2 3 4 1 2 3 4 1 2 3 2 4 1 2 3 1 2 4 2

Now I thought that I could handle this using GA() by specifying type = "permutation" and setting

min = rep(1, 10)
max = rep(4, 10)

However this doesn't work. I have dug into your source code and seen that for permutation problems you set

min <- as.vector(min)[1]
max <- as.vector(max)[1]

This effectively removes replication from the values of min and max, with the result that my fitness function is only called with a permutation of the integers 1, 2, 3 and 4.

Obviously this doesn't work! :(

Do you have any ideas for how I could pose this problem in a suitable way to be handled by GA? I'm sure that genetic algorithms are the best approach to this problem, which can be stated in words as "find the sequence of ten integers between 1 and 4 which maximises this function...".

Any suggestions would be appreciated!

Best regards, Andrew.

datawookie commented 7 years ago

Incidentally, I found this thread on SO which makes it look like the approach I tried above would work, but the solution given by jlhoward just happens to work because of the number of parameters accepted by the function being the same as the possible range of values.

But there is the (mis)conception that this should work!

luca-scr commented 7 years ago

Hi,

your problem is not a "permutation" problem so specifying type = "permutation" would not work. A permutation problem is easily described as in the traveling salesperson problem (TSP); see for example Section 4.8 of the following paper: Scrucca L. (2013) GA: A Package for Genetic Algorithms in R. Journal of Statistical Software, Vol. 53, Issue 4, pp. 1–37. http://www.jstatsoft.org/v53/i04

Your problem is simply a discrete optimisation, where you have variables x1, ..., x10 and each can take integer values 1,2,3,4. You may solve this by encoding each variable as a binary value, or consider a real-valued with repairing. See Section 4.6 of the above paper.

Best,

Luca

datawookie commented 7 years ago

Hi Luca,

Thanks for your helpful response. I will give both of those options a try!

Best regards, Andrew.