lundi 25 avril 2016

Evolving strings? How to find the cause of an infinite loop?

I realize this is a beginners sort of question, but I'm really stumped with my code. Im creating a program that will take random letters and evolve it into your name in a certain number of generations. I have all the logic correct, but I am getting an infinite loop of different letters when I run the program. I have 3 classes, Genome, which contains mutate and crossover, Population which is called every breeding cycle and stores the genomes in a list, and a main, which calls the day() method until the fitness of the string is 0, i have not posted this.

I think my issue is sorting the genomes, because my mutate and crossover seem to work fine. Im using merge sort to sort the genomes, and have tried Collections.sort with a comparator, and it didn't work. If anyone could take a look at my program to maybe find the bug, that would be great! Im stumped and have been stuck on this for a while. This is an assignment so a hint would be nice.

Here is Genome:

      import java.util.ArrayList;
import java.util.Random;

public class Genome {
/**
 * Data element initialized to name.
 */
private String target = "TEST NAME";
private StringBuilder myCurrentStr;
private double myMutationRate;
private Random myRandom = new Random();
private int myFitness = 100000;
private boolean isFitness;
private final char[] myCharList = "ABCDEFGHIJKLMNOPQRSTUVWXYZ -'".toCharArray();

/**
 * Initializes a Genome with value'A', 
 * assigns internal mutation rate.
 * @param mutationRate
 */

public Genome(double mutationRate) { // mutationrate must be between 0 and 1
    this.myMutationRate = mutationRate;
    myCurrentStr = new StringBuilder("A");
    //myFitness = 0;
    isFitness = false;
}

/**
 * Copy constructor, initializes a Genome with
 * the same values as the input gene.
 * @param gene
 */
public Genome(Genome gene) {
//  myCurrentStr = gene.myCurrentStr;
    this.myCurrentStr = new StringBuilder(gene.myCurrentStr);
    this.myFitness = gene.myFitness;
    myMutationRate = gene.myMutationRate;
    this.target = gene.target;
    this.isFitness = gene.isFitness;

}
public void setTarget(String name) {
    this.target = name;
}

/**
 * Mutates string in this Genome.
 */
public void mutate() {
    if(myRandom.nextDouble() <= myMutationRate) {
        addChar();
    }
    if(myRandom.nextDouble() <= myMutationRate) {
        deleteChar();
    }
    for(int i = 0; i < myCurrentStr.length(); i++) {
        if(myRandom.nextDouble() <= myMutationRate) {
            replaceChar(i);
        }
    }

}
public int getFitness() {
    if(!isFitness){
        fitness();
    }

    return myFitness;
}
private void addChar() {
    myRandom = new Random();
    int charIndex = myRandom.nextInt(29);
    int place = myRandom.nextInt(myCurrentStr.length() + 1);
    char letter = myCharList[myRandom.nextInt(myCharList.length)];


    if(place < myCurrentStr.length()) {
         myCurrentStr.insert(place, letter);
    }
    else{
        myCurrentStr.append(myCharList[charIndex]);
    }
}
private void replaceChar(int replaceHere) {
    if(replaceHere >= myCurrentStr.length()) {
        return;

    }
    myRandom = new Random();
    char letter = myCharList[myRandom.nextInt(myCharList.length)];
    myCurrentStr.setCharAt(replaceHere, letter);

}
private void deleteChar() {
    if(myCurrentStr.length() == 1) {
        return;
    }
    myRandom = new Random();
    int place = myRandom.nextInt(myCurrentStr.length());
    myCurrentStr.deleteCharAt(place);

}
/**
 * Will update current Genome by crossing it over
 * with other.
 * @param other
 */
public void crossOver(Genome other) {       
    Random rand = new Random();

    for(int i = 0; i < myCurrentStr.length(); i++) {
        int coinFlip = rand.nextInt(2);

        if(coinFlip == 0) {
            continue;

        } else {
            if(i < other.getString().length()){
                myCurrentStr.setCharAt(i, other.getString().charAt(i));

            } else{
                myCurrentStr.delete(i, myCurrentStr.length());
                break;
            }
        }
    }

}
public StringBuilder getString() {
    return myCurrentStr;

}
/**
 * Returns the fitness of the Genome calculated.
 * @return
 */
public Integer fitness() {
    int n = myCurrentStr.length();
    int m = target.length();
    int l = n < m ? n : m;
    int f = Math.abs(m-n) *2 ;

    for(int i = 0; i < l; i++) {
        if(myCurrentStr.charAt(i) != target.charAt(i)) {
            f = f + 1;
        } 
    }   
    myFitness = f;
    isFitness = true;
    return f;

}
public String toString() {
    StringBuilder result = new StringBuilder();
    result.append("(\"");
    result.append(myCurrentStr);
    result.append("\",");
    result.append(fitness());
    result.append(')');

    return result.toString();


}

}

Here is Population:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class Population {
/**
 * A data element that is equal
 * to the most fit Genome.
 */
public Genome mostFit = null;
private Integer myNumGenomes;
private Double myMutationRate;
private ArrayList<Genome> myGenomeList;

/**
 * Initializes a population with a number of 
 * default genomes.
 * @param numGenomes is 100
 * @param mutationRate is .05
 */
public Population(Integer numGenomes, Double mutationRate) {
    this.myNumGenomes = numGenomes;
    this.myMutationRate = mutationRate;
    this.myGenomeList= new ArrayList<Genome>(numGenomes);
    if(myMutationRate < 0 || myMutationRate > 1) {
        System.out.println("Mutation rate must be between 0 & 1.");
    }
    for(int i = 0; i < numGenomes; i++) {
        myGenomeList.add(new Genome(mutationRate));
    }
}
/**
 * Called every breeding cycle.
 */
public void day() {
    mergeSort(myGenomeList, 0, myGenomeList.size() - 1); // using merge sort 
    mostFit = myGenomeList.get(0);

    int i = myNumGenomes / 2;
    int j = myNumGenomes/2;
    while(i++ < myNumGenomes -1 ) {
        Random rand = new Random();
        int coinFlip = rand.nextInt(2);
        Genome selectedG = myGenomeList.get(rand.nextInt(j));

        if(coinFlip == 0) {
            Genome g2 = new Genome(selectedG);
            g2.mutate();
            myGenomeList.add(g2);
        } 
        else{
            Genome g2 = new Genome(selectedG);
            Genome g3 = myGenomeList.get(rand.nextInt(j));

            g2.crossOver(g3);
            g2.mutate();
            myGenomeList.add(g2);

        }

    }

}

private  void merge(List<Genome> list, int start, int finish){
    int mid = (start+finish)/2;
    int i = start;
    int j = mid + 1;
    List<Genome> temp = new ArrayList<Genome>();
    while(i < mid + 1 && j < finish + 1) {

        temp.add(list.get(i).getFitness()<list.get(j).getFitness()?list.get(i++):list.get(j++));
    }
    while(i < mid +1){
        temp.add(list.get(i++));
    }
    while(j < finish) {
        temp.add(list.get(j++));
    }
    for(i = 0;i<temp.size();i++){
        list.set(start+i, temp.get(i));
    }
}

private void mergeSort(List<Genome> list, int start, int finish){
    if(start < finish){
        int mid = (start + finish)/2;
        mergeSort(list,start,mid);
        mergeSort(list,mid+1,finish);
        merge(list, start,finish);
    }
}

here is my output:

 ("G",29)
 ("V",29)
("-",29)
("J",29)
("H",29)
("A",29)
("H",29)
("V",29)
("A",29)
("A",29)
("L",29) this continues infinitely, should be evolving into TEST NAME, or      target in the genome class. 




Aucun commentaire:

Enregistrer un commentaire