Computational Darwinism Java program

Punjabi Megastar

I've been teaching myself Java for a few months and I've written a version of Dawkin's weasel program that simulates the process of natural selection and "evolves" the string "Methinks is it like a weasel.". Can someone tell me if it's any good or crap? Thanks.

import java.util.*;

public class Darwin {

    public static final String CHAR_LIST = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" +
        "0123456789!\"&#163;$%^&*()_+-={}[];'#:@~\\|,./<>? ";
    private static final int NUM_CHARS = CHAR_LIST.length();
    private static final int MAX_TARGET_LEN = 50;
    private static final int LITTER_SIZE = 10;
    private static final int MAX_MUTATION = 5;
    private static final double MUTATION_RATE = 0.01;
    private static final int LEN_ERROR_PENALTY = NUM_CHARS / 4;
    private static final int PAUSE_BTW_GENS = 10;
    
    private String target, current;
    private String[] litter;
    private Random rgen;
    private int generation, targetLen;
    
    public Darwin() {
        rgen = new Random();
        litter = new String[LITTER_SIZE];
    }
        
    public void evolve(String targetString) {
        target = filter(targetString);
        targetLen = target.length();
        current = "" + getRandomChar();
        generation = 1;
        while (compareToTarget(current) > 0) {
            nextGeneration();
            try {Thread.sleep(PAUSE_BTW_GENS);}
            catch (InterruptedException ex) {}
        }
        System.out.println("---Finished---");
    }
    
    private String filter(String text) {
        StringBuilder filtered = new StringBuilder();
        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length && i <= MAX_TARGET_LEN; i++) {
            char ch = chars[i];
            if (CHAR_LIST.indexOf(ch) >= 0) {
                filtered.append(ch);
            }
        }
        return filtered.toString();
    }
        
    private char getRandomChar() {
        return CHAR_LIST.charAt(rgen.nextInt(NUM_CHARS));
    }
    
    private void nextGeneration() {
        System.out.println("Generation " + generation + ":");
        for (int i = 0; i < LITTER_SIZE; i++) {
            litter[i] = getChild();
            System.out.println("Child" + i + ": " + litter[i]);
        }
        current = getWinner();
        System.out.println("Target: " + target);
        System.out.println("Winner: " + current);
        System.out.println();
        generation++;
    }
    
    private String getChild() {
        int newLen = current.length();
        if (rgen.nextDouble() <= MUTATION_RATE) {
            int tmp = newLen + randomMutation();
            newLen = tmp < 1 ? 1 : tmp;
        }
        StringBuilder child = new StringBuilder();
        for (int i = 0; i < newLen; i++) {
            char ch;
            if (i < current.length()) {
                ch = current.charAt(i);
                if (rgen.nextDouble() <= MUTATION_RATE) {
                    ch = mutate(ch);
                }
            } else {
                ch = getRandomChar();
            }
            child.append(ch);
        }
        return child.toString();
    }
    
    private char mutate(char ch) {
        int posInCharList = CHAR_LIST.indexOf(ch);
        posInCharList += randomMutation();
        while (posInCharList < 0) {
            posInCharList += NUM_CHARS;
        }
        while (posInCharList >= NUM_CHARS) {
            posInCharList -= NUM_CHARS;
        }
        return CHAR_LIST.charAt(posInCharList);
    }
    
    private int randomMutation() {
        int mutationSize = rgen.nextInt(MAX_MUTATION) + 1;
        return rgen.nextBoolean() ? mutationSize : -mutationSize;
    }
    
    private String getWinner() {
        int indexOfLowest = 0;
        int lowestScore = compareToTarget(litter[0]);
        for (int i = 1; i < litter.length; i++) {
            int score = compareToTarget(litter[i]);
            if (score < lowestScore) {
                indexOfLowest = i;
                lowestScore = score;
            }
        }
        return litter[indexOfLowest];
    }
    
    private int compareToTarget(String text) {
        int textLen = text.length();
        int charPenalty = 0;
        for (int i = 0; i < textLen && i < targetLen; i++) {
            int targetCharPos = CHAR_LIST.indexOf(target.charAt(i));
            int textCharPos = CHAR_LIST.indexOf(text.charAt(i));
            int penalty = Math.abs(targetCharPos - textCharPos);
            if (penalty > NUM_CHARS / 2) {penalty = NUM_CHARS - penalty;}
            charPenalty += penalty;
        }
        int lengthPenalty = LEN_ERROR_PENALTY * Math.abs(textLen - targetLen);
        return charPenalty + lengthPenalty;
    }
    
    public static void main(String[] args) {
        Darwin darwin = new Darwin();
        darwin.evolve("Methinks it is like a weasel.");
    }
}

Aswerty

Your code is quite neat and very readable. Some potential changes:

I think it'd be cleaner to have a class called NaturalSelectionProgram that contains the main method and have the Darwin class completely seperate. It would also make your access modifiers relevant.

Also while the code looks to be neat I still have almost no idea what is going on (unless I go through it line by line). Comments are definietly needed for non biologists!

Also would it not make more sense to pass a few of the private variables in as constructor parameters? I don't know what LITTER_SIZE does but it looks like I might want it to vary at some point. And does everything need to be final? Your first 8 variables look like they might need to be changed at some point to vary your simulation. You could have a DarwinianParameters class which you could pass to the constructor which would allow your simulation parameters to be easily assigned via the main method.

henryporter

Agreed on all of Aswertys points (except maybe for more comments :-)

The variable and method names could be a bit more explicit which may help the understanding of the code rather than comments (Robert C. Martin hates the use of comments as the code should be self explanatory - I tend to agree on that point).

Other than that well done - keep up the good work!

percy212

I love this concept. Nice job.

lemon_remon

Looks good. CHAR_LIST may have been been better implemented as a regular expression - this is the exact kind of thing they were created for.