Quantcast

Minimizing function

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Minimizing function

Norbert Lesniewski
Hi,

I have a problem with minimizing function from Michalewicz`s book - Genetic Algorithms + Data Structures = Evolution Programs

Here is the problem:
http://i48.tinypic.com/i76c83.jpg

Bounds:
http://i48.tinypic.com/14jn6kp.png

and optimal points:
http://i46.tinypic.com/fly6au.png , there the function value equals -1.

I can`t make the algorithm find any of those points. Can JGAP find chromosome with minimal value of fitness function? Is there any possibility to make fitness function values lover then 0?

Thanks in advance!
Norbert

P.S. Here is code of my program:


The main class;


package project;

import org.jgap.*;
import org.jgap.impl.*;

public class RunnerClass {

    private static final int MAX_ALLOWED_EVOLUTIONS = 200;

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        // Start with a DefaultConfiguration, which comes setup with the
        // most common settings.
        //
        // -------------------------------------------------------------
        Configuration conf = new DefaultConfiguration();
        // Set the fitness function we want to use, which is our
        // MinimizingFitnessFunction that we created earlier.
        // We construct it with the target amount of change provided
        // by the user.
        //
        // ------------------------------------------------------------
        FitnessFunction myFunc = new MinimizingFitnessFunction();
        conf.setFitnessFunction(myFunc);
        ;

        // Now we need to tell the Configuration object how we want our
        // Chromosomes to be setup. We do that by actually creating a
        // sample Chromosome and then setting it on the Configuration
        // object. As mentioned earlier, we want our Chromosomes to
        // each have four genes, one for each of the coin types. We
        // want the values of those genes to be integers, which represent
        // how many coins of that type we have. We therefore use the
        // IntegerGene class to represent each of the genes. That class
        // also lets us specify a lower and upper bound, which we set
        // to sensible values for each coin type.
        //
        // --------------------------------------------------------------
        Gene[] sampleGenes = new Gene[2];

        sampleGenes[0] = new DoubleGene(conf, 0, 2); // X1
        sampleGenes[1] = new DoubleGene(conf, 0, 4); // X2

        Chromosome sampleChromosome = new Chromosome(conf, sampleGenes);

        conf.setSampleChromosome(sampleChromosome);

        // Finally, we need to tell the Configuration object how many
        // Chromosomes we want in our population. The more Chromosomes,
        // the larger the number of potential solutions (which is good
        // for finding the answer), but the longer it will take to evolve
        // the population each round. We'll set the population size to
        // 500 here.
        // --------------------------------------------------------------
        conf.setPopulationSize(100);

        // first population - randomly
        Genotype population = Genotype.randomInitialGenotype(conf);

        // initialize first best chromosome
        IChromosome bestSolutionSoFar = population.getFittestChromosome();

        // evolving population
        for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
            population.evolve();
        }
        bestSolutionSoFar = population.getFittestChromosome();
        // at the end show best solution
        System.out.println("The best solution contained the following: ");
        System.out.println("x1 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 0));
        System.out.println("x2 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 1));
        System.out.println("value : "
                + MinimizingFitnessFunction.functionValue(bestSolutionSoFar));
        System.out.println(MinimizingFitnessFunction.addPenalty(bestSolutionSoFar));

    }

}

and the fitness function class:

package project;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class MinimizingFitnessFunction extends FitnessFunction {

    @Override
    protected double evaluate(IChromosome aChromosome) {
        // step 1 - fitness function
        double fitness = functionValue(aChromosome);
        System.out.print(fitness + " ");
        // step 2 - check bounds and add penalty
        fitness += addPenalty(aChromosome);
        System.out.println("\t" + fitness);
        return Math.abs(1 / (1 - fitness));
    }

    // check bounds and add penalty
    public static double addPenalty(IChromosome aChromosome) {
        double penalty = 0.0;
        double penaltyValue = 10.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if (!((x1 / Math.sqrt(3.0) - x2) >= 0.0)) {
            penalty += penaltyValue;
        }
        if (!(-x1 - Math.sqrt(3.0) * x2 + 6.0 >= 0.0)) {
            penalty += penaltyValue;
        }
        if (x2 < 0.0) {
            penalty += penaltyValue;
        }
        System.out.print("x1 " + x1 + "\tx2 " + x2 + "\tpen " + penalty);
        return penalty;
    }

    // fitness function value
    public static double functionValue(IChromosome aChromosome) {
        double value = 0.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if ((x1 >= 0.0) || (x1 < 2.0)) {
            value = x2 + Math.pow(10, -5) * Math.pow(x2 - x1, 2) - 1.0;
        } else if ((x1 >= 2.0d) || (x1 < 4.0d)) {
            value = ((Math.pow(x1 - 3.0, 2.0) - 9.0) * Math.pow(x2, 3.0))
                    / (27.0 * Math.sqrt(3.0));
        } else if ((x1 >= 4.0) || (x1 < 6.0)) {
            value = Math.pow(x1 - 2.0, 3.0) / 3.0 + x2 - 11.0 / 3.0;
        }
        // return diffrence beetween best solution = -1 and chromosome value
        return value;
    }

    public static double getValueAtGene(IChromosome aChromosome, int i) {
        Double value = (Double) aChromosome.getGene(i).getAllele();
        return value.doubleValue();
    }

}


------------------------------------------------------------------------------
This SF.Net email is sponsored by the Verizon Developer Community
Take advantage of Verizon's best-in-class app development support
A streamlined, 14 day to market process makes app distribution fast and easy
Join now and get one step closer to millions of Verizon customers
http://p.sf.net/sfu/verizon-dev2dev 
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimizing function

Klaus Meffert-5
Norbert,
 
the fitness function value -1 is a reserved value.
To get your program working, it should be enough to simply add a positive offset to the fitness value computed, before returning it in method evaluate. So you have to care that the fitness value is positive, optimally.
I didn't try it but this should work.
 
Best
 


From: Norbert Lesniewski [mailto:[hidden email]]
Sent: Tuesday, January 12, 2010 12:55 AM
To: [hidden email]
Subject: [jgap-users] Minimizing function

Hi,

I have a problem with minimizing function from Michalewicz`s book - Genetic Algorithms + Data Structures = Evolution Programs

Here is the problem:
http://i48.tinypic.com/i76c83.jpg

Bounds:
http://i48.tinypic.com/14jn6kp.png

and optimal points:
http://i46.tinypic.com/fly6au.png , there the function value equals -1.

I can`t make the algorithm find any of those points. Can JGAP find chromosome with minimal value of fitness function? Is there any possibility to make fitness function values lover then 0?

Thanks in advance!
Norbert

P.S. Here is code of my program:


The main class;


package project;

import org.jgap.*;
import org.jgap.impl.*;

public class RunnerClass {

    private static final int MAX_ALLOWED_EVOLUTIONS = 200;

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        // Start with a DefaultConfiguration, which comes setup with the
        // most common settings.
        //
        // -------------------------------------------------------------
        Configuration conf = new DefaultConfiguration();
        // Set the fitness function we want to use, which is our
        // MinimizingFitnessFunction that we created earlier.
        // We construct it with the target amount of change provided
        // by the user.
        //
        // ------------------------------------------------------------
        FitnessFunction myFunc = new MinimizingFitnessFunction();
        conf.setFitnessFunction(myFunc);
        ;

        // Now we need to tell the Configuration object how we want our
        // Chromosomes to be setup. We do that by actually creating a
        // sample Chromosome and then setting it on the Configuration
        // object. As mentioned earlier, we want our Chromosomes to
        // each have four genes, one for each of the coin types. We
        // want the values of those genes to be integers, which represent
        // how many coins of that type we have. We therefore use the
        // IntegerGene class to represent each of the genes. That class
        // also lets us specify a lower and upper bound, which we set
        // to sensible values for each coin type.
        //
        // --------------------------------------------------------------
        Gene[] sampleGenes = new Gene[2];

        sampleGenes[0] = new DoubleGene(conf, 0, 2); // X1
        sampleGenes[1] = new DoubleGene(conf, 0, 4); // X2

        Chromosome sampleChromosome = new Chromosome(conf, sampleGenes);

        conf.setSampleChromosome(sampleChromosome);

        // Finally, we need to tell the Configuration object how many
        // Chromosomes we want in our population. The more Chromosomes,
        // the larger the number of potential solutions (which is good
        // for finding the answer), but the longer it will take to evolve
        // the population each round. We'll set the population size to
        // 500 here.
        // --------------------------------------------------------------
        conf.setPopulationSize(100);

        // first population - randomly
        Genotype population = Genotype.randomInitialGenotype(conf);

        // initialize first best chromosome
        IChromosome bestSolutionSoFar = population.getFittestChromosome();

        // evolving population
        for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
            population.evolve();
        }
        bestSolutionSoFar = population.getFittestChromosome();
        // at the end show best solution
        System.out.println("The best solution contained the following: ");
        System.out.println("x1 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 0));
        System.out.println("x2 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 1));
        System.out.println("value : "
                + MinimizingFitnessFunction.functionValue(bestSolutionSoFar));
        System.out.println(MinimizingFitnessFunction.addPenalty(bestSolutionSoFar));

    }

}

and the fitness function class:

package project;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class MinimizingFitnessFunction extends FitnessFunction {

    @Override
    protected double evaluate(IChromosome aChromosome) {
        // step 1 - fitness function
        double fitness = functionValue(aChromosome);
        System.out.print(fitness + " ");
        // step 2 - check bounds and add penalty
        fitness += addPenalty(aChromosome);
        System.out.println("\t" + fitness);
        return Math.abs(1 / (1 - fitness));
    }

    // check bounds and add penalty
    public static double addPenalty(IChromosome aChromosome) {
        double penalty = 0.0;
        double penaltyValue = 10.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if (!((x1 / Math.sqrt(3.0) - x2) >= 0.0)) {
            penalty += penaltyValue;
        }
        if (!(-x1 - Math.sqrt(3.0) * x2 + 6.0 >= 0.0)) {
            penalty += penaltyValue;
        }
        if (x2 < 0.0) {
            penalty += penaltyValue;
        }
        System.out.print("x1 " + x1 + "\tx2 " + x2 + "\tpen " + penalty);
        return penalty;
    }

    // fitness function value
    public static double functionValue(IChromosome aChromosome) {
        double value = 0.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if ((x1 >= 0.0) || (x1 < 2.0)) {
            value = x2 + Math.pow(10, -5) * Math.pow(x2 - x1, 2) - 1.0;
        } else if ((x1 >= 2.0d) || (x1 < 4.0d)) {
            value = ((Math.pow(x1 - 3.0, 2.0) - 9.0) * Math.pow(x2, 3.0))
                    / (27.0 * Math.sqrt(3.0));
        } else if ((x1 >= 4.0) || (x1 < 6.0)) {
            value = Math.pow(x1 - 2.0, 3.0) / 3.0 + x2 - 11.0 / 3.0;
        }
        // return diffrence beetween best solution = -1 and chromosome value
        return value;
    }

    public static double getValueAtGene(IChromosome aChromosome, int i) {
        Double value = (Double) aChromosome.getGene(i).getAllele();
        return value.doubleValue();
    }

}


------------------------------------------------------------------------------
This SF.Net email is sponsored by the Verizon Developer Community
Take advantage of Verizon's best-in-class app development support
A streamlined, 14 day to market process makes app distribution fast and easy
Join now and get one step closer to millions of Verizon customers
http://p.sf.net/sfu/verizon-dev2dev 
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimizing function

Jakub Siberski
Hey Norbert.
As Klaus said, you need to make your fitness function produce positve values. I think that it is actually said in comment in one of the classes or in tutorial maybe? Anyway make it positive.
In Michalewicz book look at page 93, paragraph 4.2 - Function Properties. There are actually presented some fitness Function transformations that won't break algorithm. Although they serve different purpose, they may give you hint how to deal with this situation. There is also solution proposed by Klaus discussed (it is valid but in some cases there are drawbacks).


P.S. I haven't look at your code, so there may be other issues.
P.S.2 While Fitness Function transformations don't break logic of GA, you may still experience problems when dealing with some specific implementation. JGAPs requirement for fitness function to produce positive numbers is just one example. Other GA libraries may surprise you with others.
------------------------------------------------------------------------------
This SF.Net email is sponsored by the Verizon Developer Community
Take advantage of Verizon's best-in-class app development support
A streamlined, 14 day to market process makes app distribution fast and easy
Join now and get one step closer to millions of Verizon customers
http://p.sf.net/sfu/verizon-dev2dev 
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimizing function

ShankhaB
In reply to this post by Norbert Lesniewski
Hi

I also try to solve some simple minimization problem with constraints. As you already tried out with JGAP and facing some issue with - value of the fitness function.
As you have alreday started working in this - I just want to know is the below mentioned type of problem can be soleved by JGAP.

Problem :

Minimize Z = 2x1+ 8x2  
Subject To -   5x1+x2>=10  
                    2x1+2x2>=14
                    x1+4x2>=12
                    x1,x2>=0   and 1<x1<=7    |   0<x2<=4



What I understand I have to check the my Fitness function or objective function (Z) in the

public double evaluate(IChromosome a_subject)  method , where a_subject  is the one of the potential solution.

from the "a_subject"  object I have to get the value of X1 and X2 then , I have to chek all the above mentioned constraints as well as the Fitness function (Z).

But this will be determined that for which IChromosome ( a_subject) - Z will be minimized ?

Please guide me?

Thank you,
shankha


<quote author="Norbert Lesniewski">
Hi,

I have a problem with minimizing function from Michalewicz`s book - Genetic
Algorithms + Data Structures = Evolution Programs

Here is the problem:
http://i48.tinypic.com/i76c83.jpg

Bounds:
http://i48.tinypic.com/14jn6kp.png

and optimal points:
http://i46.tinypic.com/fly6au.png , there the function value equals -1.

I can`t make the algorithm find any of those points. Can JGAP find
chromosome with minimal value of fitness function? Is there any possibility
to make fitness function values lover then 0?

Thanks in advance!
Norbert

P.S. Here is code of my program:


The main class;


package project;

import org.jgap.*;
import org.jgap.impl.*;

public class RunnerClass {

    private static final int MAX_ALLOWED_EVOLUTIONS = 200;

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        // Start with a DefaultConfiguration, which comes setup with the
        // most common settings.
        //
        // -------------------------------------------------------------
        Configuration conf = new DefaultConfiguration();
        // Set the fitness function we want to use, which is our
        // MinimizingFitnessFunction that we created earlier.
        // We construct it with the target amount of change provided
        // by the user.
        //
        // ------------------------------------------------------------
        FitnessFunction myFunc = new MinimizingFitnessFunction();
        conf.setFitnessFunction(myFunc);
        ;

        // Now we need to tell the Configuration object how we want our
        // Chromosomes to be setup. We do that by actually creating a
        // sample Chromosome and then setting it on the Configuration
        // object. As mentioned earlier, we want our Chromosomes to
        // each have four genes, one for each of the coin types. We
        // want the values of those genes to be integers, which represent
        // how many coins of that type we have. We therefore use the
        // IntegerGene class to represent each of the genes. That class
        // also lets us specify a lower and upper bound, which we set
        // to sensible values for each coin type.
        //
        // --------------------------------------------------------------
        Gene[] sampleGenes = new Gene[2];

        sampleGenes[0] = new DoubleGene(conf, 0, 2); // X1
        sampleGenes[1] = new DoubleGene(conf, 0, 4); // X2

        Chromosome sampleChromosome = new Chromosome(conf, sampleGenes);

        conf.setSampleChromosome(sampleChromosome);

        // Finally, we need to tell the Configuration object how many
        // Chromosomes we want in our population. The more Chromosomes,
        // the larger the number of potential solutions (which is good
        // for finding the answer), but the longer it will take to evolve
        // the population each round. We'll set the population size to
        // 500 here.
        // --------------------------------------------------------------
        conf.setPopulationSize(100);

        // first population - randomly
        Genotype population = Genotype.randomInitialGenotype(conf);

        // initialize first best chromosome
        IChromosome bestSolutionSoFar = population.getFittestChromosome();

        // evolving population
        for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
            population.evolve();
        }
        bestSolutionSoFar = population.getFittestChromosome();
        // at the end show best solution
        System.out.println("The best solution contained the following: ");
        System.out.println("x1 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 0));
        System.out.println("x2 : "
                + MinimizingFitnessFunction
                        .getValueAtGene(bestSolutionSoFar, 1));
        System.out.println("value : "
                +
MinimizingFitnessFunction.functionValue(bestSolutionSoFar));

System.out.println(MinimizingFitnessFunction.addPenalty(bestSolutionSoFar));

    }

}

and the fitness function class:

package project;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class MinimizingFitnessFunction extends FitnessFunction {

    @Override
    protected double evaluate(IChromosome aChromosome) {
        // step 1 - fitness function
        double fitness = functionValue(aChromosome);
        System.out.print(fitness + " ");
        // step 2 - check bounds and add penalty
        fitness += addPenalty(aChromosome);
        System.out.println("\t" + fitness);
        return Math.abs(1 / (1 - fitness));
    }

    // check bounds and add penalty
    public static double addPenalty(IChromosome aChromosome) {
        double penalty = 0.0;
        double penaltyValue = 10.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if (!((x1 / Math.sqrt(3.0) - x2) >= 0.0)) {
            penalty += penaltyValue;
        }
        if (!(-x1 - Math.sqrt(3.0) * x2 + 6.0 >= 0.0)) {
            penalty += penaltyValue;
        }
        if (x2 < 0.0) {
            penalty += penaltyValue;
        }
        System.out.print("x1 " + x1 + "\tx2 " + x2 + "\tpen " + penalty);
        return penalty;
    }

    // fitness function value
    public static double functionValue(IChromosome aChromosome) {
        double value = 0.0;
        double x1 = getValueAtGene(aChromosome, 0);
        double x2 = getValueAtGene(aChromosome, 1);
        if ((x1 >= 0.0) || (x1 < 2.0)) {
            value = x2 + Math.pow(10, -5) * Math.pow(x2 - x1, 2) - 1.0;
        } else if ((x1 >= 2.0d) || (x1 < 4.0d)) {
            value = ((Math.pow(x1 - 3.0, 2.0) - 9.0) * Math.pow(x2, 3.0))
                    / (27.0 * Math.sqrt(3.0));
        } else if ((x1 >= 4.0) || (x1 < 6.0)) {
            value = Math.pow(x1 - 2.0, 3.0) / 3.0 + x2 - 11.0 / 3.0;
        }
        // return diffrence beetween best solution = -1 and chromosome value
        return value;
    }

    public static double getValueAtGene(IChromosome aChromosome, int i) {
        Double value = (Double) aChromosome.getGene(i).getAllele();
        return value.doubleValue();
    }

}

------------------------------------------------------------------------------
This SF.Net email is sponsored by the Verizon Developer Community
Take advantage of Verizon's best-in-class app development support
A streamlined, 14 day to market process makes app distribution fast and easy
Join now and get one step closer to millions of Verizon customers
http://p.sf.net/sfu/verizon-dev2dev 
_______________________________________________
jgap-users mailing list
jgap-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jgap-users


Loading...