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 void SPM(galgo::CHR& chr)

// uniform mutation: replacing a chromosome gene by a new one
template void UNM(galgo::CHR& chr)

// boundary mutation: replacing a chromosome gene by its lower or upper bound
template void BDM(galgo::CHR& 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 distribution(mean,stddev);
double norm = distribution(generator);
double gam = min(max(norm,a,b)
...change the chromosome to become the new mutate value gam... (or better simply mutate one bit per gene with GaM)
void (*Mutation)(CHR&) = GaM;

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.

1. 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.

2. This is very nice. I am going to test the code with Gaussian mutation you supported for my tasks (functions).

3. 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& 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!

Hi langongjin,

I will implement the required crossovers.

AL

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& chr)
GAM_sigma_adapting_per_mutation(galgo::CHR& 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 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&, CHR&, CHR&) = 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.

Just pushed some fixes

okay, I will let you know the results. Thanks!

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) ));

Sorry, it is now fixed.

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?

hi, Alanthie,
I tried this by add following into template class population

> std::vector<CHR>& get_newpop() { return newpop;}
> std::vector<CHR>& get_matpop() { return matpop;}

And add the following into inline void Population<T>::select(int pos)

std::vector<galgo::CHR>& np = x.get_matpop();
    for(int k=0; k < np[matidx]->nbgene(); k++)
    {
       T t = np[matidx]->get_value(k) ;
       std::cout << t;
    }

But I got some errors

/Users/lan/projects/bayesian/GALGOrealXover/GALGO/Population.hpp:264:13: error: use of alias template 'CHR' requires template arguments
std::vector<CHR>& get_newpop() { return newpop;}
            ^~~
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/Galgo.hpp:56:1: note: template is declared here
using CHR = std::shared_ptr<Chromosome<T>>;
^
In file included from /Users/lan/projects/bayesian/GALGOrealXover/GALGO/main.cpp:7:
In file included from /Users/lan/projects/bayesian/GALGOrealXover/GALGO/Galgo.hpp:81:
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/Population.hpp:264:41: error: use of undeclared identifier 'newpop'
std::vector<CHR>& get_newpop() { return newpop;}
                                        ^
/Users/lan/projects/bayesian/GALGOrealXover/GALGO/Population.hpp:267:13: error: use of alias template 'CHR' requires template arguments

template class Population
// add
std::vector& get_newpop() { return newpop;}
std::vector& get_matpop() { return matpop;}

std::vectorgalgo::CHR& np = x.get_matpop();
for(int j=0;..np[matidx]->nbgene()....)
{
T t = np[matidx]->get_value(j) ;
std::cout << t;
}

hi, Alanthie,

A small issue for the latest code. There are also have some same configurations in main.cpp and GeneticAlgorithm.hpp.

main.cpp
void set_my_config(galgo::ConfigInfo<_TYPE>& config)
{
    // override some defaults
    config.mutinfo._sigma           = 1.0;
    config.mutinfo._sigma_lowest    = 0.01;
    config.mutinfo._ratio_boundary  = 0.10;

    config.covrate = 0.50;  // 0.0 if no cros-over
    config.mutrate = 0.05;
    config.recombination_ratio = 0.50;

    config.elitpop      = 5;
    config.tntsize      = 2;
    config.Selection    = TNT;
    config.CrossOver    = RealValuedSimpleArithmeticRecombination;
    config.mutinfo._type = galgo::MutationType::MutationGAM_UncorrelatedNStepSizeBoundary;

    config.popsize  = 20;
    config.nbgen    = 20;
    config.output   = true;
}

GeneticAlgorithm.hpp
template <typename ParamTYPE>
struct ConfigInfo
{
    ConfigInfo() : mutinfo()
    {
        // DEFAULTS
        covrate = .50;  // cross-over rate
        mutrate = 1.0;  // mutation rate usually it is 1.0 for real-valued
        SP = 1.5;
        tolerance = 0.0;
        recombination_ratio = 0.60; //Real Valued crossover ratio, can't be 0.5 because 0.5 will generate two same offsprings after Xover

        elitpop = 1;
        tntsize = 2; // k-tournament size k=2/4, higher value higher pressure
        genstep = 10;
        precision = 10;

        Objective = nullptr;
        Selection = TNT; // RWS, TNT, RNK, RSP, TRS
        CrossOver = RealValuedSimpleArithmeticRecombination; //
        //Mutation = SPM; // derived from by mutinfo._type
        Adaptation = nullptr;
        Constraint = nullptr;
        FixedValue = nullptr;
        StopCondition = nullptr;

        nbgen = 10;
        popsize = 20;
        output = false;
    }

    MutationInfo<ParamTYPE> mutinfo;

    double covrate;
    double mutrate;
    double SP;
    double tolerance;
    double recombination_ratio;

    int elitpop;
    //int matsize; // set to popsize when ga is constructed, maybe change by ga.matsize = ... after constructor and before ga.run()
    int tntsize;
    int genstep;
    int precision;

    std::vector<double> (*Objective)(const std::vector<ParamTYPE>&);
    void (*Selection)(Population<ParamTYPE>&);
    void (*CrossOver)(const Population<ParamTYPE>&, CHR<ParamTYPE>&, CHR<ParamTYPE>&);
    void (*Mutation)(CHR<ParamTYPE>&);
    void (*Adaptation)(Population<ParamTYPE>&) = nullptr;                           
    std::vector<double> (*Constraint)(const std::vector<ParamTYPE>&);
    void (*FixedValue)(Population<ParamTYPE>&, int k);
    bool (*StopCondition)(galgo::GeneticAlgorithm<ParamTYPE>&);

    std::vector<bool>       force_value_flag;
    std::vector<ParamTYPE>  force_value;

    int nbgen;
    int popsize;
    bool output;
};

Are they we want?
Thanks!

Hi langongjin,

struct ConfigInfo is needed.

set_my_config() is just to setup the test exemples (in exemple.cpp) - not needed, but you can do something similar for your project.
No more need to change the default param in GeneticAlgorithm class.

Usage:
galgo::ConfigInfo<_TYPE> config; // A new instance of config witht initial defaults
set_my_config<_TYPE>(config); // Override some defaults - your specefic needs
// Add config.Objective = RosenbrockObjective<_TYPE>::Objective;
//...param...
galgo::GeneticAlgorithm<_TYPE> ga(config, par1, par2);
ga.run();

AL

hi, Alanthie,

I debug the real-valued code for days. Maybe the code real-valued representation is not good work.
Here I tested three functions for real-valued code and the original binary string representation code.

/********** 1# ACKLEY function N Dimensions **************/
template <typename T>
class AckleyObjective
{
  public:
  static std::vector<double> Objective(const std::vector<T>& x)
  {
    size_t dim_in = 5;
    auto xx = x;
    // transfer interval from [0, 1] to [-32.768, 32.768]
    for (int i = 0; i < dim_in; i++)
    {
      xx[i] = 65.536 * x[i] - 32.768;
    }
    const double a = 20.;
    const double b = 0.2;
    const double c = 2 * M_PI;
    double sum1 = 0.;
    double sum2 = 0.;
    for (size_t i = 0; i < dim_in; i++)
    {
      sum1 = sum1 + xx[i] * xx[i];
      sum2 = sum2 + std::cos(c * xx[i]);
    }
    double term1 = -a * std::exp(-b * std::sqrt(sum1 / dim_in));
    double term2 = -std::exp(sum2 / dim_in);
    double obj = term1 + term2 + a + std::exp(1);
    return {-obj}; //max = 0, at (0,...,0)
  }
};

/********** 3# Ellipsoid function N Dimensions **************/
template <typename T>
class EllipsoidObjective
{
  public:
  static std::vector<double> Objective(const std::vector<T>& x)
  {
    size_t dim_in = 5;
    double inner = 0., outer = 0.;
    for (size_t i = 0; i < dim_in; ++i)
    {
        for(size_t j = 0; j < i; j++)
        {
            inner = inner + std::pow((131.072 * x[j] - 65.536), 2); //(-65.536, 65.536)
        }
        outer = outer + inner;
    }
    return {-outer}; //maximum = 0 at (0, ..., 0)
  }
};

/********** 4# Sphere function N Dimensions **************/
template <typename T>
class SphereObjective
{
  public:
  static std::vector<double> Objective(const std::vector<T>& x)
  {
    size_t dim_in = 5;
    double inner = 0.;
    for (size_t i = 0; i < dim_in; ++i)
    {
        inner = inner + std::pow((10. * x[i] - 5.), 2);
    }
    return {-inner}; //maximum = 0 with (0, 0)
  }
};

I tested the above three functions for 10 runs, 20 generations (Actually I also tested more runs), popsize = 20. I took the average for each generations and each run. Results as:
Ackley.pdf
ackley_bi.pdf
ellipsoid.pdf
ellipsoid_bi.pdf
sphere.pdf
sphere_bi.pdf

The *.pdf are the results of real-valued representation. The *_bi.pdf are the results of binary representation. The binary representation works but not good. The real-valued representation is definitely not work/convergence. I want to say that we can not say it is convergence based on the best fitness. It is convergence only when the average should go up and the best fitness close to optimal, right?

How is your idea? could you run the above three function to see the results?

In addition, here is the R code I used to plot the figures.

rm(list = ls())
library(ggplot2)
library(dplyr)
setwd("~/projects/bayesian/GALGOrealvalue/plot/")
fitness = read.table("sphere_bi_10.txt")

fitnessmean <- aggregate(fitness,list(rep(1:(nrow(fitness)%/%20+1),each=20,len=nrow(fitness))),mean)[-1]
fitmean = data.frame(gen = rep(1:20),fit = fitnessmean$V1)
fitmanaverage = aggregate( fit ~ gen, fitmean, mean)

ggplot(fitmanaverage, aes(1:nrow(fitmanaverage))) + 
  geom_point(aes(1:nrow(fitmanaverage), fitmanaverage$fit), alpha = 1/2, colour = "black", size = 1) +
  geom_smooth(aes(1:nrow(fitmanaverage), fitmanaverage$fit), colour = "blue", method = "loess") +
  labs(x="Generations", y="fitness",title="sphere_bi") +
  ylim(-50,0) 

here is the data
sphere_bi_10.txt

Thank you very much!

hi, Alanthie,

Good news, finally, it works as:
sphere_sigma0.1.pdf

The problem is std::normal_distribution<double> distribution01(0.0, 0.1);
In book "Introduction to Evolutionary Computing" it is N(0,1). The problem is that it cannot be a fixed sigma and mu, but it is fixed in the book. The sigma should be adaptive depend on the domain. For the domain (0, 1) , the sigma should in (0.05~0.3) empirically.

I am testing more test suits, but let you know the good news firstly.

hi, Alanthie,
Could you give me some ideas about this problem? The EA convergence to the local optimal for MICHALEWICZ FUNCTION, c++ code as:

template <typename T>
class MichalewiczObjective //todo not good results
{
  public:
  static std::vector<double> Objective(const std::vector<T>& x)
  {
    size_t dim_in = 5;
    auto xx = x;
    // transfer interval from [0, 1] to [0, pi]
    for (int i = 0; i < dim_in; i++)
        xx[i] = M_PI * x[i];
    double sum = 0.;
    double term = 0.;
    double m = 10.;
    for(size_t i = 0; i < dim_in; i++)
    {
        term = std::sin(xx[i]) * std::pow(std::sin(i * xx[i] * xx[i]/M_PI), 2 * m);
        sum = sum + term;
    }
    double obj = sum;
    return {obj}; //max= -1.8013(2D) at (2.20,1.57)/-4.687658(5D)/-9.66015(10D)
  }
};

I tried to tune the parameters but it always convergence to the local optimal (about 3.69), but the global optimal is 4.6876. Here EA looks for the maximum. I run the experiment ten times. No one is convergence to the global optimal.

Can you give me some ideas?

Hi,

Good luck! - this function was designed against GA!

We provide the global optimization community with new
optimality proofs for 6 deceptive benchmark functions (5
bound-constrained functions and one nonlinearly constrained
problem). These highly multimodal nonlinear test problems
are among the most challenging benchmark functions for
global optimization solvers; some have not been solved even
with approximate method

https://pdfs.semanticscholar.org/6e82/d0cd7acbd55774c131af8941db6c2f84b7ec.pdf

AL

hi, Alanthie,

Thank you very much for the share.
But still It is not convergence to the optimal for few functions, like SCHWEFEL function, STYBLINSKI-TANG (it convergences sometimes). Take SCHWEFEL function, I also tested it 10 runs and took the average. The figure is shown as follows. The red dashed line is optimal, the black line is the best (average), the black dot is the average per generations each run.
schwefel_sigma_0.075.pdf

Could you give me some ideas about this? If you need the configuration of parameters, I will paste it.

hi, Alanthie,

How can I replace the initial individuals with my data? The data format is std::vector< double > indiv;. Actually, I have an idea to improve the beginning of EA. I used some methods to generate the special initial individuals for EA. Therefore, I need to pass the special initial individuals into EA as the initial individuals. But I do not how to code it in our code. I tried:

    inline void Chromosome<T>::create()
    {
        chr.clear();
        int i(0);
        for (const auto& x : ptr->param)
        {
            std::string str = x->encode();
            chr.append(str);
            param[i] = indiv[i];
            _sigma[i] = 0.0;
            _sigma_iteration[i] = 0;
            i++;
        }
    }

Because I think the our EA is start from the create() function. But I found the individuals have not been updated. The EA still starts to evolve from the intial inviduals of EA, not starts from my special individuals.
Could you give me a hand?
Thanks a lot!

Hi,

In my branch I use the method call like (in void test_ga_binairo(int no = 0)):
galgo::GeneticAlgorithmN<BINAIRO_TEST_TYPE, NBIT> ga(config, vlow, vhigh, vinit);

I dont know if your are able to compile the template class GeneticAlgorithmN in your environment, you had some problem the last time you tried.

OR

initGene(i, indiv[i]) will init the parameter i

AL

hi, Alanthie,

It looks works as follows:

    inline void Chromosome<T>::create()
    {
        chr.clear();
        int i(0);
        for (const auto& x : ptr->param)
        {
            std::string str = x->encode();
            chr.append(str);
            T newvalue = (T) indiv[i];
            initGene(i, newvalue);
            _sigma[i] = 0.0;
            _sigma_iteration[i] = 0;
            i++;
        }
    }

But I have a question about initGene(i, newvalue); in for (const auto& x : ptr->param){ }. It create a indivual once. Take 2 dimensions individuals as example, we have initGene(0, newvalue) for i = 0, initGene(1, newvalue) for i = 1. If popsize = 20, that means the we also initGene(0, newvalue) and initGene(1, newvalue) for all rest individuals (19 individuals).
My question is why the same initGene(0, *), and initGene(1, *) do not replace the last individuals? I tested it that next generation have the right individual from last generation. The following is the special initial individuals (we see the fitness here) from other methods I mentioned before.

fitness0gen: -0.208807
fitness0gen: -0.304377
fitness0gen: -0.471944
fitness0gen: -0.499104
fitness0gen: -0.569336
fitness0gen: -0.619478
fitness0gen: -0.646309
fitness0gen: -0.661959
fitness0gen: -0.67193
fitness0gen: -0.678206
fitness0gen: -0.6824
fitness0gen: -0.684969
fitness0gen: -0.687315
fitness0gen: -0.689161
fitness0gen: -0.690344
fitness0gen: -0.69154
fitness0gen: -0.691996
fitness0gen: -0.692465
fitness0gen: -0.693179
fitness0gen: -0.693649
 Generation =   0 | X1 = 0.5001509786 | X2 = 0.5007539988 | F(x) = -0.2088071643

The following is the individuals before TNT in second generation.

x[0]fitness: -0.2088071643
x[1]fitness: -0.3043769839
x[2]fitness: -0.4719438822
x[3]fitness: -0.4991042813
x[4]fitness: -0.5693364160
x[5]fitness: -0.6194775181
x[6]fitness: -0.6463089924
x[7]fitness: -0.6619587092
x[8]fitness: -0.6719297516
x[9]fitness: -0.6782055116
x[10]fitness: -0.6824004377
x[11]fitness: -0.6849687433
x[12]fitness: -0.6873146298
x[13]fitness: -0.6891614621
x[14]fitness: -0.6903437218
x[15]fitness: -0.6915403313
x[16]fitness: -0.6919958815
x[17]fitness: -0.6924654243
x[18]fitness: -0.6931794691
x[19]fitness: -0.6936492204

We could see they are same. This means the initGene(i, newvalue); updated the individuals right. But I do not understand about my above question? could you tell me the answer?
Thanks a lot!

hi, Alanthie,

Another small question, How can I call nogen from void GeneticAlgorithm<T>::run() {for (nogen = 1; nogen <= nbgen; ++nogen){ }} in void GAM_UncorrelatedNStepSizeBoundary(galgo::CHR< T > &chr){ }? Because I want to make an adaptive sigma over nogen for std::normal_distribution< double > distribution01(0.0, 1.0);, not a fixed sigma = 1.

I tried to use the following code for testing

  auto nogens = galgo::GeneticAlgorithm::nogen;
  std::cout << "nogen: " << nogens << std::endl;

But I got errors as:

Evolution.hpp:854:24: error: 'GeneticAlgorithm' is not a class, namespace, or enumeration

Thank you very much!

Hi,

chr.nogen()

hi, Alanthie,
It works with chr->nogen()
but why the value nogen is changing (see the following) during a generation. I think it is becasue the individuals from different generations.

nogen: 4
nogen: 4
Nu_evaluation_re: 1 param[0]: 0.5385897160 param[1]: 0.9728716016 fitness: -725.7636153229
Nu_evaluation_re- 2 param[0]: 0.7855494022 param[1]: 0.8774535060 fitness: -896.6737010010
nogen: 0
Nu_evaluation_com: 3 param[0]: 0.4803634286 param[1]: 0.9018497467 fitness: -445.0523364075
nogen: 0
...
Nu_evaluation_com: 12 param[0]: 0.4820629358 param[1]: 0.9322044849 fitness: -418.9475752838
nogen: 2
Nu_evaluation_com: 13 param[0]: 0.5676433444 param[1]: 0.8978191018 fitness: -421.1274363525
nogen: 3
Nu_evaluation_com: 14 param[0]: 0.5507441163 param[1]: 0.0000000000 fitness: -619.5801150330
nogen: 0
Nu_evaluation_com: 15 param[0]: 0.5308289528 param[1]: 0.0000000000 fitness: -677.9540335663
nogen: 3
Nu_evaluation_com: 16 param[0]: 0.5960704088 param[1]: 0.9870103598 fitness: -910.8542277344
nogen: 0
Nu_evaluation_com: 19 param[0]: 0.4062004983 param[1]: 0.8896992207 fitness: -510.7010046967
 Generation =   4 | X1 = 0.5664529800 | X2 = 0.9243094921 | F(x) = -356.8659350403

How can I get the nogen that always equal the number of generations?
Thanks a lot!

hi,

Yes chr.nogen() gives nogen when the chromosome was created or copied.

Use
this->nogen // if in an algorithm function
or
x.nogen() where x is a population (see void RNK(galgo::Population& x)
or
chr.ptr->nogen() // if in a chromosome function
or
add a public function in Chromosome.hpp (so this will work : chr.get_ga_nogen())
int get_ga_nogen() const;

template <typename T>
inline int Chromosome<T>::get_ga_nogen() const
{
    return ptr->nogen() ;
}

AL

hi, Alanthie,
It works. In addition, I found there is the same problem in

void GAM_sigma_adapting_per_generation(galgo::CHR< T > &chr){      
    for (int z = 1; z < chr->nogen() / 2; z++)
      {
        norm01 = distribution01(galgo::rng);
        sigma = std::max(double(0), sigma * exp(norm01));
      }
}

and, I do not understand why we update the sigma with sigma = std::max(double(0), sigma * exp(norm01)). Did you get this from articles or books? Maybe this inspires me. Furthermore, why it is z < chr->nogen() / 2 ?
Thanks a lot!

Hi,

Thanks for the bug.
No books!
This is a prototype I created to test some of my algorithms (before I had a sigma per chromosome).
The chr->nogen() / 2 was to slow down sigma changes - but you can invent your own formula.
The max is to remove the negative value in exp()
Repetive call to norm01 give new randomness every time like a MonteCarlo simulation.

AL

hi, Alanthie,
I see. Thank you for the answer.

Still, can you give me some ideas about the following question if you have time. You know, I am learning c++, therefore, I want to figure out how it works.

hi, Alanthie,

It looks works as follows:

    inline void Chromosome<T>::create()
    {
        chr.clear();
        int i(0);
        for (const auto& x : ptr->param)
        {
            std::string str = x->encode();
            chr.append(str);
            T newvalue = (T) indiv[i];
            initGene(i, newvalue);
            _sigma[i] = 0.0;
            _sigma_iteration[i] = 0;
            i++;
        }
    }

But I have a question about initGene(i, newvalue); in for (const auto& x : ptr->param){ }. It create a indivual once. Take 2 dimensions individuals as example, we have initGene(0, newvalue) for i = 0, initGene(1, newvalue) for i = 1. If popsize = 20, that means the we also initGene(0, newvalue) and initGene(1, newvalue) for all rest individuals (19 individuals).
My question is why the same initGene(0, *), and initGene(1, *) do not replace the last individuals? I tested it that next generation have the right individual from last generation. The following is the special initial individuals (we see the fitness here) from other methods I mentioned before.

fitness0gen: -0.208807
fitness0gen: -0.304377
fitness0gen: -0.471944
fitness0gen: -0.499104
fitness0gen: -0.569336
fitness0gen: -0.619478
fitness0gen: -0.646309
fitness0gen: -0.661959
fitness0gen: -0.67193
fitness0gen: -0.678206
fitness0gen: -0.6824
fitness0gen: -0.684969
fitness0gen: -0.687315
fitness0gen: -0.689161
fitness0gen: -0.690344
fitness0gen: -0.69154
fitness0gen: -0.691996
fitness0gen: -0.692465
fitness0gen: -0.693179
fitness0gen: -0.693649
 Generation =   0 | X1 = 0.5001509786 | X2 = 0.5007539988 | F(x) = -0.2088071643

The following is the individuals before TNT in second generation.

x[0]fitness: -0.2088071643
x[1]fitness: -0.3043769839
x[2]fitness: -0.4719438822
x[3]fitness: -0.4991042813
x[4]fitness: -0.5693364160
x[5]fitness: -0.6194775181
x[6]fitness: -0.6463089924
x[7]fitness: -0.6619587092
x[8]fitness: -0.6719297516
x[9]fitness: -0.6782055116
x[10]fitness: -0.6824004377
x[11]fitness: -0.6849687433
x[12]fitness: -0.6873146298
x[13]fitness: -0.6891614621
x[14]fitness: -0.6903437218
x[15]fitness: -0.6915403313
x[16]fitness: -0.6919958815
x[17]fitness: -0.6924654243
x[18]fitness: -0.6931794691
x[19]fitness: -0.6936492204

We could see they are same. This means the initGene(i, newvalue); updated the individuals right. But I do not understand about my above question? could you tell me the answer?

Thanks a lot!

Hi,

I dont understand your question...
create() is only called one time ever to initialize the first population.
initGene(i, newvalue) IS NOT updating individuals after that.

void GeneticAlgorithm::run()
{
...
// creating population
pop.creation(); // calling create() ONLY ONE TIME EVER
// for (int i = start; i < ptr->popsize; ++i) {
// curpop[i] = std::make_shared<Chromosome>(*ptr);
// curpop[i]->create();
// curpop[i]->evaluate();
// }
...
for (nogen = 1; nogen <= nbgen; ++nogen)
{
// evolving population
pop.evolution();
...
}

}

AL

hi, Alanthie,
I see it. But I meant if we have 20 individuals per generation, 2 dimensions per individual. That means initGene(i, newvalue) runed 20 times for initialization, i = 0, 1 each time. But why the individuals not be replaced each time?
Is this clear?

inline void Chromosome<T>::create()
    {
        chr.clear();
        int i(0);
        for (const auto& x : ptr->param)
        {
            std::string str = x->encode();
            chr.append(str);
            T newvalue = (T) indiv[i];
            initGene(i, newvalue);
            _sigma[i] = 0.0;
            _sigma_iteration[i] = 0;
            i++;
        }
    }

Thanks a lot!

Hi,

You should print fitness values only after new population evalute() was called.
This is not before TNT, but at end of recombination() after crossover().

Check code in Population::recombination()
// crossing-over mating population to create 2 new chromosomes
ptr->CrossOver(*this, newpop[i], newpop[i+1]);

 // evaluating new chromosomes
  newpop[i]->evaluate();
  newpop[i+1]->evaluate(); 

AL

hi, Alanthie,

I am sorry it is not the answer for my question. I think I can describe it better as:

for (const auto &x : ptr->param) //this is the iteration for dimension of parameters
{            
initGene(i, newvalue); //update value of parameters.
}

Why the parameters not be replaced for the different points? The i is the same for different points. For example, i is from 0 to 4 for each point if the dimension of parameters is 5. That is, each point runs initGene(0, newvalue). Why the initGene(0, newvalue) of next point not replace initGene(0, newvalue) of last point?
Is this better?
Thanks a lot!

Hi,

In Galgo, the first chromosome is initialize with value passed, all other are randomly initialized.

What is your needs for initializing the starting population?
AL

/-------------------------------------------------------------------------------------------------/
// create a population of chromosomes
template
void Population::creation()
{
int start = 0;
// initializing first chromosome
if (!ptr->initialSet.empty()) {
curpop[0] = std::make_shared<Chromosome>(*ptr);
curpop[0]->initialize();
curpop[0]->evaluate();
start++;
}
// getting the rest
#ifdef _OPENMP
#pragma omp parallel for num_threads(MAX_THREADS)
#endif
for (int i = start; i < ptr->popsize; ++i) {
curpop[i] = std::make_shared<Chromosome>(*ptr);
curpop[i]->create(); // RANDOM init
curpop[i]->evaluate();
}
// updating population
this->updating();
}

/-------------------------------------------------------------------------------------------------/
// initialize chromosome (from known parameter values)
template
inline void Chromosome::initialize()
{
chr.clear();

int i(0);
for (const auto& x : ptr->param)
{
	// encoding parameter initial value
	std::string str = x->encode(ptr->**initialSet**[i++]);
	chr.append(str);
}

}

/-------------------------------------------------------------------------------------------------/
// create new chromosome
template
inline void Chromosome::create()
{
chr.clear();

int i(0);
for (const auto& x : ptr->param)
{
	// encoding parameter random value
	std::string str = x->**encode**(); // RANDOM
	chr.append(str);

	_sigma[i] = 0.0;
	_sigma_iteration[i] = 0;

	i++;
}

}

-------------------------------------------------------------------------------------------------/
// encoding random unsigned integer
std::string encode() const override
{
std::string str = GetBinary(galgo::Randomize::generate());
return str.substr(str.size() - N, N);
}

-------------------------------------------------------------------------------------------------/
// encoding known unsigned integer
std::string encode(T z) const override
{
if (std::is_integral::value)
{
uint64_t value = (uint64_t)(z - data[0]);
std::string str = GetBinary(value);
return str.substr(str.size() - N, N);
}
else
{
uint64_t value = (uint64_t)(Randomize::MAXVAL * (z - data[0]) / (data[1] - data[0]));
std::string str = GetBinary(value);
return str.substr(str.size() - N, N);
}
}

hi, Alanthie,

I want to instead of the initial population with my special population that from another algorithm. Therefore, I implemented it based on your suggestion as following:

inline void Chromosome<T>::create()
    {
        chr.clear();
        int i(0);
        for (const auto& x : ptr->param)
        {
            std::string str = x->encode();
            chr.append(str);
            T newvalue = (T) indiv[i]; //this is added, indiv is the special population from another algorithm
            initGene(i, newvalue); // this is added, but I do not how it works for different population.
            _sigma[i] = 0.0;
            _sigma_iteration[i] = 0;
            i++;
        }
    }

I know how initGene works for different parameters in a point (multi-dimensions parameters). But my question is how initGene works for different point? Why the newvalue in initGene(i, newvalue) of next point does not replace the newvalue of last point in initGene(i, newvalue) ?
Is this clear?

In addition, I think I understand most of the basic structure of GALGO, although all of them.
Thanks a lot!

Hi,

global_counter = 0;
std::vector global_indiv(N*K); //global_indiv[] should contains N individual * K parameters (gene) values.
..
Look like you should use some kind of global counter for indiv[i];

T newvalue = (T) global_indiv[global_counter++];
initGene(i, newvalue);

hi, Alanthie,

It already worked before. I just not understand how initGene works for the different point? because in my understanding, the newvalue in initGene(i, newvalue) of next point will replace the newvalue of last point in initGene(i, newvalue), that is the next point will be same with last point. But actually, It is not. Therefore, I do not understand how it works?

Hi,

I added the ability to initialize all individuals of the initial population (in my branch).
See example.cpp
for (int z = 0; z < 3 * config.popsize; z++) v[z] = (_TYPE) (-4.0 + z *0.01);
galgo::GeneticAlgorithm<_TYPE> my_ga(config, v);

AL

hi, Alanthie,
I am sorry I am not understand why you added this? Is it for my above question? If yes, I do not understand how it answers my question? But anyway, my code works well, I just want to understand more about the code that is why I have above question. In a word for my question, why initGene(i, newvalue) works for the different individual during population? If it is still not clear for you, do not mind. just forget it because it is not important.

Hi,

I added the ability to initialize all individuals of the initial population (in my branch).
See example.cpp

for (int z = 0; z < 3 * config.popsize; z++) v[z] = (_TYPE) (-4.0 + z *0.01);
galgo::GeneticAlgorithm<_TYPE> my_ga(config, v);

AL
Thanks a lot!

hi, Alanthie,

Thanks a lot for your help in these issues. Do you have time to have look at the new issue about galgo?