Alguém com experiência em GA pode examinar minha função de condicionamento físico?

Question

Aqui está o meu problema, estou modificando o código que encontrei para Algoritmos Genéticos para fazer otimização numérica de uma função.Essencialmente, dada uma função F e nosso Valor Desejado, o programa usa GA para procurar valores de x e y que forneçam o Valor Desejado apropriado.Continuo mexendo na minha função de condicionamento físico, o que considero ser a raiz do problema.

A divisão básica do código é:

Gerar uma população cromossômica aleatória

Use uma classificação de bolha com base na aptidão de cada cromossomo

Verifique se algum deles resolveu a função

Se alguém resolver, pare e imprima

Caso contrário, gerar crianças com base na classificação dos pais, verifique a melhor resposta, loop

Espero que alguém possa me indicar a direção certa. Vou dissecá-lo novamente esta noite, mas parece que encontrei um obstáculo nisso.Para funções mais complexas do que as que codifiquei, parece convergir em torno de uma porcentagem aleatória (geralmente menor que 20)...mas deve estar muito mais próximo de 0.A função codificada simples continua retornando cerca de 99% de diferença...então não estou 100% informado sobre o que está acontecendo.

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

Na verdade, foi um erro simples que me escapou, que eu deveria ter percebido.O principal problema estava no uso de return (3*x)^(2*y);^ é um XOR bit a bit em java, mas um expoente.(Opa) O problema foi corrigido usando Math.pow(3*x,2*y);... e uma pequena verificação da função de condicionamento físico a colocou em funcionamento com algumas outras pequenas alterações :)