Hi All
Please find my comments below:
>
>> Hi All
>>
>> The newly proposed design of "commons-math4-ga2" has two primary
>> issues which I would like to mention here.
>>
>> *1) GA logic*: The design does not conform to the basic genetic algorithm
>I understand the concern about providing the standard ("historical") GA.
>The theorem assumes the standard GA, but the example shows that
>convergence is also achieved with the variant.
-- Yes the new variant can accommodate the standard GA too.
>
>> However, the new design proposed as part of "commons-math4-ga2"
>> deviates from the basic logic. It does not distinguish the operators i.e.
>> crossover and mutation and treats them uniformly. The order of
>> operator application is also not considered.
>
>All intended as "features". ;-)
>[One being that, in the variant implementation, it is possible to apply
>any number of operators, not just one specific crossover followed by
>one mutation.]
>
>Shouldn't we be able (IIUC) to define the standard GA procedure by
>an extension of the API like the following (untested):
>---CUT---
>public class CrossoverThenMutate<G>
> extends AbstractCrossover<G> {
> private AbstractCrossover<G> c;
> private AbstractMutation<G> m;
> [...]
> private List<G> mutate(G parent,
> UniformRandomProvider rng) {
> final List<G> p = new ArrayList<G>(1);
> p.add(parent);
> return m.apply(p, rng);
> }
>}
>---CUT---
>
>AFAICT, a standard GA would thus be performed if this combined
>operator would be used as a unique operator in the GA variant.
--If we consider this approach we may need to modify our examples which
assume the standard GA.
This variant design is more appropriate for a *generalized population based
stochastic optimizer* which can accommodate other algorithms like
multi-agent gradient descent/simulated annealing, genetic algorithm(already
implemented), particle swarm optimization and large neighbourhood search
etc.
If we want to stick to this new design I would rather suggest *renaming* of
the existing interfaces so that the API can be more generic and can be used
for all other algorithms. GA should be a specific implementation for that
API.
However, we might have to think more on the multiple operator scenarios.
>
>> Along with that it executes
>> parent selection two times instead of one.
>
>That would also be taken care of with the above combined operator.
>
>> These are clear deviations from the standard approach used so far and
would
>> require a fix.
>>
>>
>> *2) Determination of mutation probability*: The newly proposed design of
>> "commons-math4-ga2" determines the probability of mutation at the
algorithm
>> level. Same approach was used in math 3.x implementation. However, this
>> approach considers the probability of mutation at the chromosome level
not
>> at the allele/gene level. I have found a considerable difference in the
>> quality of optimization between two cases. Determining the mutation
>> probability at the gene/allele level has given a
>> considerably better result.
>
>A runnable test case (that creates a comparison) would be quite useful
>to illustrate the feature.
>
>> Usage of mutation probability at the chromosome
>> level would only ensure mutation of a single allele irrespective of
>> probability
>
>?
>In the basic implementation for the "binary" genotype (in class
>"o.a.c.m.ga2.gene.binary.Mutation"), there is a loop over all the
>alleles.
>
>> or chromosome size. There is no such limitation in case the
>> mutation probability is decided at the allele level and can be easily
>> controlled by users for fine tuning. This has helped to improve the
>> optimization quality thus providing better results. This is only related
to
>> mutation not crossover. But we can maintain an uniform approach and let
the
>> operator decide on the probability.
>
>I don't understand.
>Please refer to the class mentioned above and describe the required
>modifications.
-- E.g. assume the user is having a chromosome population of size 10 and
chromosome length is 10.
mutation probability no of alleles modified per chromosome no of
alleles modified in population
.2 2
20
.1 1
10
.05 --
5
.02 --
2
.2 2
20
This way users can have more freedom over allele variation in the entire
population.
Thanks & Regards
--Avijit Basak
On Tue, 16 Aug 2022 at 05:55, Gilles Sadowski <[email protected]> wrote:
> Hello.
>
> Le lun. 15 août 2022 à 17:23, Avijit Basak <[email protected]> a
> écrit :
> >
> > Hi All
> >
> > The newly proposed design of "commons-math4-ga2" has two primary
> > issues which I would like to mention here.
> >
> > *1) GA logic*: The design does not conform to the basic genetic algorithm
> > concepts proposed by John Holland. The pseudocode representing the
> original
> > algorithm logic is provided below:
> > --CUT--
> > while(!converged(population)) {
> > Population newPopulation = new Population();
> > for(int i = 0; i < size(population)/2; i++) {
> > // select parents
> > ChromosomePair parents = select(population);
> > // do crossover
> > ChromosomePair offsprings = crossover(parents);
> > //do mutation
> > Chromosome chromosome1 = mutate(offsprings[0]);
> > Chromosome chromosome2 = mutate(offsprings[1]);
> > // Add mutated chromosomes to population
> > newPopulation.add(chromosome1);
> > newPopulation.add(chromosome2);
> > }
> > }
> > --CUT--
> >
> > However, the implementation proposed in "commons-math4-ga2" can be
> > represented by the pseudocode provided below.
> > --CUT--
> > while(!converged(population)) {
> > List<GeneticOperator> operators;
> > Population newPopulation = new Population();
> > for(int i = 0; i < size(population)/2; i++) {
> > for(GeneticOperator operator : operators) {
> > // select parents
> > ChromosomePair parents = select(population);
> > // apply operator
> > ChromosomePair offsprings = operator.apply(parents);
> > // Add chromosomes to population
> > newPopulation.add( offsprings[0] );
> > newPopulation.add( offsprings[1] );
> > }
> > }
> > }
> > --CUT--
> > N.B. The use of probability and elitism has been avoided to keep the
> logic
> > simplified.
> >
> > The first one has been used by the engineering community for decades
> > and is proved to be effective. There is also a mathematical model based
> on
> > schema theorem(
> >
> https://en.wikipedia.org/wiki/Holland%27s_schema_theorem#:~:text=The%20Schema%20Theorem%20says%20that,the%20power%20of%20genetic%20algorithms
> .)
> > to support the effectiveness of the algorithm. Same has been followed by
> me
> > for implementation of "commons-math4-ga" module.
>
> I understand the concern about providing the standard ("historical") GA.
> The theorem assumes the standard GA, but the example shows that
> convergence is also achieved with the variant.
>
> > However, the new design proposed as part of "commons-math4-ga2"
> > deviates from the basic logic. It does not distinguish the operators i.e.
> > crossover and mutation and treats them uniformly. The order of
> > operator application is also not considered.
>
> All intended as "features". ;-)
> [One being that, in the variant implementation, it is possible to apply
> any number of operators, not just one specific crossover followed by
> one mutation.]
>
> Shouldn't we be able (IIUC) to define the standard GA procedure by
> an extension of the API like the following (untested):
> ---CUT---
> public class CrossoverThenMutate<G>
> extends AbstractCrossover<G> {
> private AbstractCrossover<G> c;
> private AbstractMutation<G> m;
>
> public CrossoverThenMutate(AbstractCrossover<G> c,
> AbstractMutation<G> m) {
> this.c = c;
> this.m = m;
> }
>
> @Override
> protected List<G> apply(G parent1,
> G parent2,
> UniformRandomProvider rng) {
> // Crossover.
> final List<G> cR = c.apply(parent1, parent2, rng);
>
> // Mutate.
> final List<G> r = new ArrayList<G>(2);
> r.add(mutate(cR.get(0), rng));
> r.add(mutate(cR.get(1), rng));
>
> return r;
> }
>
> private List<G> mutate(G parent,
> UniformRandomProvider rng) {
> final List<G> p = new ArrayList<G>(1);
> p.add(parent);
> return m.apply(p, rng);
> }
> }
> ---CUT---
>
> AFAICT, a standard GA would thus be performed if this combined
> operator would be used as a unique operator in the GA variant.
>
> > Along with that it executes
> > parent selection two times instead of one.
>
> That would also be taken care of with the above combined operator.
>
> > These are clear deviations from the standard approach used so far and
> would
> > require a fix.
> >
> >
> > *2) Determination of mutation probability*: The newly proposed design of
> > "commons-math4-ga2" determines the probability of mutation at the
> algorithm
> > level. Same approach was used in math 3.x implementation. However, this
> > approach considers the probability of mutation at the chromosome level
> not
> > at the allele/gene level. I have found a considerable difference in the
> > quality of optimization between two cases. Determining the mutation
> > probability at the gene/allele level has given a
> > considerably better result.
>
> A runnable test case (that creates a comparison) would be quite useful
> to illustrate the feature.
>
> > Usage of mutation probability at the chromosome
> > level would only ensure mutation of a single allele irrespective of
> > probability
>
> ?
> In the basic implementation for the "binary" genotype (in class
> "o.a.c.m.ga2.gene.binary.Mutation"), there is a loop over all the
> alleles.
>
> > or chromosome size. There is no such limitation in case the
> > mutation probability is decided at the allele level and can be easily
> > controlled by users for fine tuning. This has helped to improve the
> > optimization quality thus providing better results. This is only related
> to
> > mutation not crossover. But we can maintain an uniform approach and let
> the
> > operator decide on the probability.
>
> I don't understand.
> Please refer to the class mentioned above and describe the required
> modifications.
>
> Regards,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [email protected]
> For additional commands, e-mail: [email protected]
>
>
--
Avijit Basak
