0

这是我的问题,我正在修改为遗传算法找到的代码,以对函数进行数值优化。本质上,给定函数 F 和我们的期望值,程序使用 GA 搜索提供适当期望值的 x 和 y 值。我一直在修改我的健身功能,我觉得这是问题的根源。

基本代码分解是:

生成随机染色体群体

使用基于每个染色体适应度的冒泡排序

检查其中是否有任何一个碰巧解决了该功能

如果一个人解决了它,然后停止并打印它

否则,根据父母生成孩子排序,检查最佳答案,循环

我希望有人能指出我正确的方向,今晚我将再次剖析它,但我似乎在这方面遇到了障碍。对于比我硬编码的更复杂的函数,它似乎收敛于一个随机百分比(通常小于 20)......但它应该更接近于 0。简单编码的函数不断返回大约 99% 的差异......所以我不是 100% 的。

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());
}
}
4

1 回答 1

1

实际上,这是一个简单的错误,我应该抓住它。主要问题是使用 return (3*x)^(2*y); ^ 是 java 中的按位异或,但是是指数。(哎呀)使用 Math.pow(3*x,2*y); 解决了这个问题;...并且对适应度函数进行了一点仔细检查,使其启动并运行,并进行了一些其他小的更改:)

于 2012-10-04T05:43:25.580 回答