GALGO-2.0
GALGO-2.0 copied to clipboard
olmallet81
Specific representations
hi, I saw the representation in GALGO is Bit string representation. And then, GALGO converts the bit string into the real-value. Does the GALGO support Real-valued representation? if yes, how can I set up in the GALGO? Thanks!
hi, do you have some ideas about how to implement the real-valued representation inside of the GALGO? Thanks!
Hi langongjin,
I have used Galgo many times, The example provided in the code, use double (real-value parameter), just change your lower, upper bounds.
From memory, you have already 64 bit of precision for real number (parameter), which covers all the value of a double (usually quite enough for most applications). You can even increase the number of bit 0/1 with simple code adjustment if need more precision per parameter (but simpler to use 2 (64 bits) parameters to mimic one 128 bit parameter). Do you really need to change the internal representation, for what purposes (Do you have any sample code of your app)?
AL
Extra info: You can change/specialize the internal string representation of Galgo by modifying these 2 functions to use an IEEE 754 format.
std::string GetBinary(uint64_t value) uint64_t GetValue(const std::string& s)
An example of c++ code for converting IEEE 754 is here: https://www.technical-recipes.com/2012/converting-between-binary-and-decimal-representations-of-ieee-754-floating-point-numbers-in-c/
AL
hi, Alanthie, Thank you for your ideas. You are right. The code uses the double value. But the thing is that it uses the Xover and Mutation by the binary string, and then convert the binary string into the real-valued parameters. You know this is not real-valued representation. In particular, It cannot implement the Gaussian mutation for the real-valued. Therefore, I need real real-valued representation. In addition, I do not understand what is your idea with
std::string GetBinary(uint64_t value)
uint64_t GetValue(const std::string& s)
How to implement the real-valued representation? Thank you very much!
Galgo dont use real-value internally (only bits of 0/1)
Galgo has currently only 3 mutations operators: // single point mutation: flipping a chromosome bit template <typename T> void SPM(galgo::CHR<T>& chr)
// uniform mutation: replacing a chromosome gene by a new one template <typename T> void UNM(galgo::CHR<T>& chr)
// boundary mutation: replacing a chromosome gene by its lower or upper bound template <typename T> void BDM(galgo::CHR<T>& chr)
You just need to implement the Gaussian mutation GaM = min(max(N(x,stddev),a,b). a, b are the bounds associated with a chromosome(parameter) (see BDM).
Galgo has only uniform random probability in range [0,1)
You need to use the Normal distribution to do something like:
std::default_random_engine generator;
std::normal_distribution
I may try to do it, when I find some time this week. AL
hi, Alanthie,
Thank you very much for your time. I understand your idea. But generally speaking, Gaussian mutation only work for the real-valued representation. I tried to figure out how to change the code for real-valued representation. Thus, I think we need to change the Crossover, Mutation for real-valued. In detail, we do not need the function encode() and GetBinary(), we still needgenerate() to create real value parameters. and then pass the real value parameters to objective() for calculating fitness. That is the initial stage (first generation) for first generation. After first generation, we keep the same selection() and elitism(). But I guess the crossover() might be changed, maybe just changed the length of chromosomes. Because the real-valued representations are shorter than binary string. Then, the mutation() need to be changed with Gaussian mutation. And then, pass the real values after mutated into evaluate(). This is my idea, I spent few day to figure the code. Am I right ?
I am not good at c++ coding. Unfortunitely, I have to code in C++ for my project. Last, I aim to run a multi-dimensions object function (take anyone for example) with real-valued representation and Gaussian mutation. And I am in stuck here for about few weeks. Could you help to fix the code for my goal?
Thank you very much!
Hi langongjin,
1 - Why do you say Gaussian mutation only work for the real-valued representation? For a GA algorithm, gaussian mutation only means mutate some genome part according to a gaussian probability. I guess you have a good reason (better speed convergence expectation maybe - you must be a mathematician to know this apriori!) to prefer this instead of any of the 3 others mutators. I' m an actuary and I never bothered about the mutation prob() used in Galgo.
Normally, a problem is a bunch of real-value parameters (external) to be optimized (internal algorithm) according to an utility function (external). Internally, Galgo use 01 bit representations, but anything would have work also (just more complex to code). Our DNA, AGTC is not real-valued internally, just 4 discrete values (00, 01, 10, 11). You rarely need to bother about the internal representation (Unless PROVED too inefficient).
2- "I aim to run a multi-dimensions object function (take anyone for example) with real-valued representation and Gaussian mutation." Cool, I will code the missing Gaussian mutation functions (C++), so you will be able to start testing your function. If you have a smaller (utility) function of your problem, we can start testing it with various mutators and see the convergence/improvement speed. My current job is C++, so it is not an issue for me.
3- Changing the internal representation to real-value would be a big coding/testing/debugging task as you have already explored yourself!
Thanks Alain
Extra Info (The problem with real-valued internal representation): 4 years ago James Dominic O'Shea Manchester Metropolitan University Floating point numbers are binary already - everything inside a computer is, so superficially it's just a matter of interpretation. However, there are two issues. The first is one of bit-manipulation. If you use a strongly-typed programming language used for defence / real-time / systems ptogramming etc. it won't just let you do bit-manipulation inside a floating point number - you will have to apply a type-caste operation to convince the compiler you really know what you're doing. The second is the question of "what are you changing and what are the consequences?" You could be performing crossover inside the mantissa or the exponent; you could be mutating the sign bit. Some consequences could lead to large leaps in the area being searched in the solution space, others (e.g. mutating the least significant bit in the mantissa) could have virtually no consequences at all. You could ignore this and mutate them as normal bit strings and allow it all to come out in the wash - or you could try to constrain the GA operations within the different components of the float.
Gaussian Mutator I have implemented an initial draft of the gaussian mutator. See in https://github.com/alanthie/GALGO-2.0
Run on the example.cpp // objective function example : Rosenbrock function min at (1,1)
Running Genetic Algorithm...
Generation = 0 | X1 = 1.2362554360 | X2 = 1.5742732891 | F(x) = -0.2669181560 Generation = 10 | X1 = 1.0682841230 | X2 = 1.1357900359 | F(x) = -0.0076230951 Generation = 20 | X1 = 1.0682841230 | X2 = 1.1380788891 | F(x) = -0.0056562812 Generation = 30 | X1 = 1.0252536812 | X2 = 1.0512550546 | F(x) = -0.0006389572 Generation = 40 | X1 = 1.0250095369 | X2 = 1.0505836576 | F(x) = -0.0006258477 Generation = 50 | X1 = 1.0250095369 | X2 = 1.0506752117 | F(x) = -0.0006255709 Generation = 60 | X1 = 1.0250095369 | X2 = 1.0506752117 | F(x) = -0.0006255709 Generation = 70 | X1 = 1.0250095369 | X2 = 1.0506752117 | F(x) = -0.0006255709 Generation = 80 | X1 = 1.0240329595 | X2 = 1.0486610208 | F(x) = -0.0005776138 Generation = 90 | X1 = 1.0240329595 | X2 = 1.0486305028 | F(x) = -0.0005776000 Generation = 100 | X1 = 0.9938200961 | X2 = 0.9861295491 | F(x) = -0.0002780800 Generation = 110 | X1 = 0.9938200961 | X2 = 0.9861295491 | F(x) = -0.0002780800 Generation = 120 | X1 = 0.9936064698 | X2 = 0.9866788739 | F(x) = -0.0000739332 Generation = 130 | X1 = 0.9936064698 | X2 = 0.9866788739 | F(x) = -0.0000739332 Generation = 140 | X1 = 0.9936064698 | X2 = 0.9873807889 | F(x) = -0.0000424894 Generation = 150 | X1 = 0.9936064698 | X2 = 0.9872587167 | F(x) = -0.0000408796 Generation = 160 | X1 = 0.9984283207 | X2 = 0.9972686351 | F(x) = -0.0000192411 Generation = 170 | X1 = 0.9994048981 | X2 = 0.9987945373 | F(x) = -0.0000003785 Generation = 180 | X1 = 0.9994048981 | X2 = 0.9987945373 | F(x) = -0.0000003785 Generation = 190 | X1 = 0.9994048981 | X2 = 0.9987945373 | F(x) = -0.0000003785 Generation = 200 | X1 = 0.9994048981 | X2 = 0.9987945373 | F(x) = -0.0000003785 Generation = 210 | X1 = 0.9994048981 | X2 = 0.9987945373 | F(x) = -0.0000003785 Generation = 220 | X1 = 0.9994048981 | X2 = 0.9988250553 | F(x) = -0.0000003764 Generation = 230 | X1 = 0.9994048981 | X2 = 0.9988250553 | F(x) = -0.0000003764
AL
hi, Thank you very much for your time.
-
I made a wrong description about "Gaussian mutation only work for the real-valued representation". We have different Gaussian mutations. It is a idea about mutations that could work for different representation.
-
This is very nice. I am going to test the code with Gaussian mutation you supported for my tasks (functions).
-
Yes, it is big coding/testing/debugging task, not just change the mutation. We need to change all of the related code like I said before.
- [Extra Info.] I understande what is your meaning. But for my task, I want the EA have more search ability on a small domain (like local search) and fewer global search ability. Therefore, I need the real-valued Gaussian mutation to gaurantee the more search ability on a samll domain. If we use the binary string Gaussian mutation, we can not control more individuals in a small domain. Because the Xover of binary string will switch the choromosomes so intense. But the Xover of real-valued parameters just switch the position of real-valued parameters. For example, choromosomes (0.1, 0.2, 0.3, 0.4, 0.5) and (0.2,0.3,0.4,0.5,0.6). We will have the results after Xover of real-valued (if the position of Xover is 2), (0.1, 0.2, 0.4, 0.5, 0.6) and (0.2, 0.3, 0.3, 0.4, 0.5). But for the Xover of binary string, we might have the new choromosomes (0.7123456, 0.2,0.3,0.4,0.5) and (0.4789123, 0.3, 0.4,0.5,0.6). After the Xover of real-valued, the Gaussian mutation also help to search the optimal more accurate. This why I need real-valued representation and real-valued Gaussian mutation. Hope I am right.
Last, thank you very much for you code. I am testing the code with my task. I will give you feedback if I have any questions.
Cheers!
one more thing, could give me a hint how/what you changed? This will be useful for me to handle the code. Thanks!
Hi,
In my branch, on each *.hpp file, there is an history button that shows the list of changes made. I added the gaussian mutation method void GAM(galgo::CHR<T>& chr) and some more examples of standard benchmark functions to verify the convergence of GAM (Ackley, Rastrigin, StyblinskiTang, Griewank functions). Just run the main project. I have included a VS2017 solution also.
I will do the Xover with a gaussian (after I figure it out - switching position should be easy). As said (James Dominic O'Shea) eveything is 01 representation (including double, float, string).
Do you a function I can test that would shows the advantage of gaussian Xover/Mutation over classics one?
AL
Hi, This paper explains 3 type of real-valued crossover - Is it what you need (else can you describe your Xover logic)? https://uwaterloo.ca/scholar/sites/ca.scholar/files/ahilal/files/lecture-6-1.pdf
Thanks AL
hi, Alanthie,
Thank you for your time and information.
Regarding my test function, my final function depend on a simulator, therefore, it does not work for you. But right now, I just test the classic functions from https://www.sfu.ca/~ssurjano/optimization.html. Therefore, I have the almost same test functions in your code.
Regarding the real-valued crossover, I would say I need Single arithmetic crossover and Simple arithmetic crossover from my intuition. I am not sure which one is better because I did not test. Therefore, could you implemented both of Single arithmetic crossover and Simple arithmetic crossover if you have time.
Thank you very much!
cool, Thank you very much!
I checked the code GAM
if (galgo::proba(galgo::rng) <= mutrate) // TODO - mutrate not necessary
We could keep this, but we need to set the high mutation rate for Guassian mutation, like 0.5~1. It can not be 0.05. Am I right?
Here is an example about Gaussian mutation.
http://neo.lcc.uma.es/cEA-web/GMut.htm
Yes, it is recommended to be nearer 1.0. (http://www.nashcoding.com/2010/07/07/evolutionary-algorithms-the-little-things-youd-never-guess-part-1/)
But I dont see much improvement by doing so in my tests cases! I will add more tests cases (and optimize the GAM function - not recomputing the sigma history everytime) so to know more about the tradeoff.
AL
yes, I agree with you, there is a problem in
for (int z = 1; z < chr->nogen(); z++) // number of generations
{
// sigma adapting with iteration
// TODO - One sigma per parameter
norm01 = distribution01(generator);
sigma = std::max(T(0), (T) (sigma * exp(norm01)));
}
I do not understand why z<chr->nogen(). In my understanding, there is no relationship between updating sigma and number of generations.
I printed a value as:
generator: 412013968
norm01: -0.6605581884
sigma: 11.4456127296
value: -0.0780956741
norm: 6.0425012260
gaussian_value: 5.0000000000
you could see the value of norm is far away from value so that gaussian_value is set as the maximum. And it happens often. Therefore, there is a problem here.
Thank you very much!
Yes, mutation rate should change based on efficiency of the search... (Need to measure it first - TODO!) (https://www.dynardo.de/fileadmin/Material_Dynardo/bibliothek/WOST_2.0/WOST_2_AdaptiveMutation_En.pdf)
Let me know the algos for GAM you want to try.
I' m adding some models to compare them in my branch: GAM_sigma_adapting_per_generation(galgo::CHR<T>& chr) GAM_sigma_adapting_per_mutation(galgo::CHR<T>& chr) ...
I will be able to compare them when a have the gaussian Xover and enough tests cases.
Thanks AL
hi, Alanthie, yes, we have different self-adaptive Gaussian mutations. In my understanding, the linear function between sigma and generations is also a solution for self-adaptive Gaussian mutation. But I would recommend the classic/basic method in section 4.4.2 (page 57) of the book https://link.springer.com/content/pdf/10.1007%2F978-3-662-44874-8.pdf But maybe we need to do the real-valued Xover first. If the real-valued representation works, then we can code for the self-adaptive Gaussian mutation. The Gaussian mutation works well right now if I understood right. Do you agree? Thank you very much!
hi, Alanthie,
I tested the Gaussian mutation and found a problem. The sigma = (upperBound[i] - lowerBound[i]) / 6; is not good. Because if the interval is 12, that means sigma is 2. We can imagine what the individuals will happen, which are not close to the value. In my tests, the sigma can not be more than 0.1. And normally, we normalize the interval to (0, 1) at the functions. The performance of (sigma=0.1) is better in my testing. But I have not visualized the fitness to compare. Therefore, It is my feeling from my test.
Hi langongjin,
Thanks
Yes, I`m currently fixing the various issues - work in progress in my branch. -sigma are not correctly transmit between parent/child (This is a new feature I have to implement - Galgo has currently no support for extra chromosome information transfer)
-I am implementing the real-valued gaussian mutation from 4.4.2 (page 57) GAM_UncorrelatedOneStepSizeFixed (sigma = chr->mutinfo()._sigma + gaussian) GAM_UncorrelatedOneStepSizeBoundary (sigma = (upperBound[i] - lowerBound[i]) * chr->mutinfo()._ratio_boundary + gaussian) GAM_UncorrelatedNStepSize (...in progress...)
-
MutationInfo<T> will contains all the mutation parameters for the GenticalAlgorithm _sigma (sigma to use when fixed as used by GAM_UncorrelatedOneStepSizeFixed) _ratio_boundary (as used by GAM_UncorrelatedOneStepSizeBoundary) _sigma_lowest (minimal sigma threshold for any sigma (4.4.2 (page 57) )) ... (any other as desired, you said you need a _sigma_highest)...
-
Gaussian Xover (...in progress...)
AL
cool, Thanks for your work. I have no more idea for other mutations right now. Maybe I will have after test the code when you finish.
"Gaussian Xover"? do you mean the Xover for real-valued representation? Thanks!
Hi,
Xover for real-valued representation are in my branch now: RealValuedSimpleArithmeticRecombination RealValuedSingleArithmeticRecombination RealValuedWholeArithmeticRecombination
Setup - see example.cpp: T recombination_ratio = 0.55; // Real Valued crossover void(*CrossOver)(const Population<T>&, CHR<T>&, CHR<T>&) = RealValuedWholeArithmeticRecombination; mutinfo.type = galgo::MutationType::MutationSPM; // or GAM... mutinfo.xyz = ... const _TYPE MUTRATE = 0.05; // or ...
I have fixed the other issued also - but not sure at 100% for the moment.
AL
hi, Alanthie, Thank you very much. I am going to test it and let you know how is it going.
hi, Alanthie, There are some redefinition errors in the code. I am not sure if are they same, therefore, I can not simply comment it. Could you check them? Thanks!
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:283:33: error: redefinition of 'chrmat1'
const galgo::Chromosome<T>& chrmat1 = *x[idx1];
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:260:33: note: previous definition is here
const galgo::Chromosome<T>& chrmat1 = *x[idx1];
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:284:33: error: redefinition of 'chrmat2'
const galgo::Chromosome<T>& chrmat2 = *x[idx2];
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:261:33: note: previous definition is here
const galgo::Chromosome<T>& chrmat2 = *x[idx2];
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:322:9: error: redefinition of 'i'
int i = pos;
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:313:9: note: previous definition is here
int i = pos;
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:391:35: error: use of undeclared identifier 'chrmat1'
chr1->sigma_update(i, 0.5*(chrmat1.get_sigma(i)+chrmat2.get_sigma(i) ));
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:391:56: error: use of undeclared identifier 'chrmat2'
chr1->sigma_update(i, 0.5*(chrmat1.get_sigma(i)+chrmat2.get_sigma(i) ));
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:395:35: error: use of undeclared identifier 'chrmat1'
chr2->sigma_update(i, 0.5*(chrmat1.get_sigma(i) + chrmat2.get_sigma(i) ));
^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/src/Evolution.hpp:395:58: error: use of undeclared identifier 'chrmat2'
chr2->sigma_update(i, 0.5*(chrmat1.get_sigma(i) + chrmat2.get_sigma(i) ));
Thanks! Another issue,
for (int i = 0; i < chr1->nbgene(); i++) //0～dimensions
{
chr1->initGene(i, chrmat1.get_value(i));
}
Is this still use the Binary string as the gene inside of funciton initGene and get_value?
If yes, it might be also work, but not real real-valued representation. The real real-valued representation does not need to be converted each other between real-valued and binary string.
Am I right?