Qualcuno può con GA Experience esaminare la mia funzione di fitness?

Question

Ecco il mio problema, sto modificando il codice che ho trovato per gli algoritmi genetici per fare ottimizzazione numerica di una funzione. In sostanza, data una funzione F e il nostro valore desiderato, il programma utilizza GA per cercare valori di X e Y che forniscono il valore desiderato appropriato. Continuo a tingere con la mia funzione di fitness, che sento è la radice del problema.

La rottura del codice di base è:

Genera una popolazione cromosoma casuale

Utilizzare una bolla Ordina in base a ciascun cromosomi fitness

Verifica se qualcuno di essi succede per risolvere la funzione

Se uno risolve, quindi interrompere e stamparlo

altro, Genera i bambini in base ai genitori Ordina, controlla la migliore risposta, loop

Spero che qualcuno possa indicarmi nella giusta direzione, lo segnerò ancora un po 'stasera, ma mi sembra di aver colpito un ostacolo su questo. Per funzioni più complesse di quelle che ho codificato duro, sembra convergere attorno a una percentuale casuale (di solito inferiore a 20) ... ma dovrebbe essere molto più vicina a 0. La semplice funzione codificata continua a restituire circa il 99% di differenza ... Quindi non sono al 100% su cosa succede.

import java.util.*;
import java.util.Comparator;
import java.util.TreeMap; 
/**
 * Modified from a file created Jul 9, 2003
 * Original @author Fabian Jones
 * Modified @author Cutright
 * @version 2
 */
public class ScratchGA
{
private static int NUM_CHROMOSOMES = 100;   //num of chromosomes in population
private static double MUTATE =  .01;  //chance of a mutation i.e. 88.8%
private static int desiredValue = 60466176; //desired value of function 
private static int cutoff = 1000; // number of iterations before cut off
private static int longPrint = 0;  //1 means print out each iteration of the population
private boolean done = false;
private Chromosome[] population;
int iteration = 0;

/**
 * Constructor for objects of class ScratchGA
 */
public ScratchGA()
{
    generateRandomPopulation(NUM_CHROMOSOMES);
    printPopulation();
}

/**
 * Generate a random population of chromosomes  - WORKS
 * 
 */
private void generateRandomPopulation(int pop)
{
    System.out.println("Generating random population of " + pop + ", now." +"\n");

    population = new Chromosome[pop];

    for(int i=0; i<pop; i++)
    {
        int rand = (int)(Math.random()*4095);  // Range 0 to 4095
        population[i] = (new Chromosome(rand, 12));
    }
}

/**
 * Codesaver for generating a new line in the output
 */
private void newLine()
{
    System.out.println("\n");
}

/**
 * Prints the population (the chromosomes)
 */
private void printPopulation()
{
    int x=1; // variable to print 10 chromosomes on a line
    if (iteration==0)
    {
    System.out.println("Initial population: " + "\n" );
    }
    else
    {
        if (longPrint ==1)
        {
    System.out.println("Population " + iteration + " :" + "\n");
    for(int i=0; i<=(NUM_CHROMOSOMES-1); i++)
    {
        System.out.print(population[i] + " ");
        if(x == 10)
        {
            newLine();
            x=1;
        }
        else
        {
            x++;
        }
    }

    newLine();
      }
      else
      {
      System.out.println("Best answer for iteration " + iteration + " is: " + population[0] + " with a % difference of " +population[0].getFitness());
      newLine();
    }
}
}
 /** 
 * Start
 * Bubblesort initial population by their fitness, see if the first chromosome
 * in the sorted array satisfies our constraint.
 * IF done ==true or max num of iterations
 *        Print best solution and its fitness
 * ELSE
 *    generate new population based on old one, and continue on
 */
public void start()
{
   // System.out.println("Starting bubblesort... Please Wait.");
    bubbleSort();
    //System.out.println("After Bubblesort: " );
    //printPopulation();
    topFitness();

    if(done || iteration==cutoff){
        System.out.println("DONE!!");   
        System.out.println("Best solution: " + population[0] + " % Difference: " + population[0].getFitness());
    }
    else{
        iteration++;
        generateNewPopulation();
        printPopulation();
        start();
    }
}
 /**
 * If the top chromosomes fitness (after being sorted by bubblesort) is 100%
 * done == true
 */
private void topFitness()
{
    if (population[0].getFitness() == 0)
    {
        done = true;
    }
}

/**
 * Called from chromosome,
 * Tests the x and y values in the function and returns their output
 */
public static double functionTest(int x, int y)
{
    return (3*x)^(2*y); // From our desired value we're looking for x=2, y=5 
}

/**
 * Returns the desired outcome of the function, with ideal x and y
 * Stored above in a private static
 */
public static int getDesired()
{
    return desiredValue;
}

/**
 * Sort Chromosome array, based on fitness
 * utilizes a bubblesort
 */
 private void bubbleSort()
 {
     Chromosome temp;

     for(int i=0; i<NUM_CHROMOSOMES; i++){
         for(int j=1; j<(NUM_CHROMOSOMES-i); j++){
             if(population[j-1].getFitness() > population[j].getFitness())
             {
                 //swap elements
                 temp = population[j-1];
                 population[j-1] = population[j];
                 population[j] = temp;
                }
            }
        }
    }
/**
* Top 30: Elitism
* Next 60: Offspring of Elitists
* Next 10: Random
*/
  private void generateNewPopulation(){

    System.out.println("***Generating New Population");
    Chromosome[] temp = new Chromosome[100];
    for (int i = 0; i < 30; i++)
    {
     Chromosome x = population[i];
     if (shouldMutate())
     mutate(x);
     temp[i]=x;
    } 
   for (int i = 0; i < 30; i++)
   {
    temp[i+30] =cross1(population[i], population[i+1]);
    temp[i+60] = cross2(population[i], population[i+1]);
   } 
   for (int i = 90; i<100; i++)
   {
        int rand = (int)(Math.random()*4095);  // Range 0 to 4095
        Chromosome x = new Chromosome(rand, 12);
        temp[i] = x;
    }
    population = temp;
}
/**
 * First cross type, with two parents
 */
private Chromosome cross1(Chromosome parent1, Chromosome parent2){
    String bitS1 = parent1.getBitString();
    String bitS2 = parent2.getBitString();
    int length = bitS1.length();
    int num = (int)(Math.random()*length); // number from 0 to length-1
    String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
    Chromosome offspring = new Chromosome();
    offspring.setBitString(newBitString);

    if(shouldMutate()){
        mutate(offspring);
    }

    return offspring;
}

/**
 * Second cross type, parents given in same order as first, but reverses internal workings
 */
private Chromosome cross2(Chromosome parent1, Chromosome parent2){
    String bitS1 = parent1.getBitString();
    String bitS2 = parent2.getBitString();
    int length = bitS1.length();
    int num = (int)(Math.random()*length); // number from 0 to length-1
    String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
    Chromosome offspring = new Chromosome();
    offspring.setBitString(newBitString);

    if(shouldMutate()){
        mutate(offspring);
    }

    return offspring;
}

/**
 * Returns a boolean of whether a character should mutate based on the mutation value at top
 */
private boolean shouldMutate(){
    double num = Math.random()*100;
    return (num <= MUTATE);
}

/**
 * Returns a boolean of whether a character should mutate based on the mutation value at top
 */
private void mutate(Chromosome offspring){
    String s = offspring.getBitString();
    int num = s.length();
    int index = (int) (Math.random()*num);
    String newBit = flip(s.substring(index, index+1));
    String newBitString = s.substring(0, index) + newBit + s.substring(index+1, s.length());
    offspring.setBitString(newBitString);
}
/**
 * Flips bits in a string 1 to 0, 0 to 1
 */
private String flip(String s){
    return s.equals("0")? "1":"0";
}

.

}

import java.lang.Comparable;
import java.math.*;
/**
* Modified from a file created on Jul 9, 2003
* Unsure of original author
* 
*/
public class Chromosome implements Comparable
{
protected String bitString;

/**
 * Constructor for objects of class Chromosome
 */
public Chromosome()
{
}

public Chromosome(int value, int length)
{
    bitString = convertIntToBitString(value, length);
}

public void setBitString(String s)
{
    bitString = s;
}

public String getBitString()
{
    return bitString;
}

public int compareTo(Object o)
{
    Chromosome c = (Chromosome) o;
    int num = countOnes(this.bitString) - countOnes(c.getBitString());
    return num;
}

public double getFitness()
{
    String working = bitString;
    int x1 = Integer.parseInt(working.substring(0,6),2);
    int x2 = Integer.parseInt(working.substring(6),2);
    double result = ScratchGA.functionTest(x1,x2);
    double percentDiff =  ((ScratchGA.getDesired() - result)/ScratchGA.getDesired())*100;
    if (percentDiff >= 0)
    {
    return percentDiff;
}
    else
    {
    return -percentDiff;
}
}

public boolean equals(Object o)
{
    if(o instanceof Chromosome)
    {
        Chromosome c = (Chromosome) o;
        return c.getBitString().equals(bitString);
    }
    return false;
}

public int hashCode()
{
    return bitString.hashCode();
}


public String toString()
{
    return bitString;
}

public static int countOnes(String bits)
{
    int sum = 0;
    for(int i = 0; i < bits.length(); ++ i){
        String test = bits.substring(i, i+1);
        if(test.equals("1")){
            sum = sum + 1;
        }
    }
    return sum;
}

public static String convertIntToBitString(int val, int length)
{
    int reval = val;

    StringBuffer bitString = new StringBuffer(length);
    for(int i = length-1; i >=0; --i ){
        if( reval - (Math.pow(2, i)) >= 0 ){
            bitString.append("1");
            reval = (int) (reval - Math.pow(2, i));
        }
        else{
            bitString.append("0");
        }
    }
    return bitString.toString();
}

public static void main(String[] args
){
    //System.out.println(convertIntToBitString(2046, 10));
    Chromosome c = new Chromosome(1234, 10);
    //System.out.println(c.fitness());
}
}

.

Answer 1

In realtà, è stato un semplice errore che mi ha elulato, che avrei dovuto prendere.Il problema principale era nell'uso di ritorno (3 * x) ^ (2 * y);^ è un XOR bitwise in Java, ma un esponente.(Whoops) il problema è stato rettificato usando math.pow (3 * x, 2 * y);... e un piccolo controllo doppio della funzione fitness ha avuto e funzionante con alcune altre modifiche minori :)