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.
