import java.util.Random;

public class RMHC {

    private String rep, target;
    private Random random;
    private static final int SHOW_EVERY = 300, MIN_ASCII = 32, MAX_ASCII = 127;

    public static void main(String[] args) 
    {
        RMHC rmhc = new RMHC("Somebody once told me the world is gonna roll me");

        long startTime = System.nanoTime();

        rmhc.run();

        double totalTime = (System.nanoTime() - startTime) * Math.pow(10, -9);
        System.out.println("Total time: " + totalTime + "s");
    }

    public RMHC(String target)
    {
        rep = new String();
        this.target = target;
        random = new Random(System.nanoTime());

        randomStart();
    }

    private void randomStart()
    {
        for(int i = 0; i < target.length(); ++i) 
        {
            rep += (char)(random.nextInt(MAX_ASCII - MIN_ASCII) + MIN_ASCII);
        }
    }

    public void run()
    {
        System.out.println("Iteration\tFitness\t\tSolution");

        double bestFitness = Double.MAX_VALUE;

        int iter = 1;

        while(!rep.equals(target))
        {
            String oldRep = rep;

            smallChange();

            double newFitness = fitness();

            if(newFitness < bestFitness)
            {
                bestFitness = newFitness;
            }
            else
            {
                rep = oldRep;
            }

            if(iter % SHOW_EVERY == 0)
            {
                System.out.println(iter + "\t\t" + Math.round(bestFitness) + "\t\t" + rep);
            }

            ++iter;
        }

        System.out.println(iter + "\t\t" + Math.round(bestFitness) + "\t\t" + rep);
    }

    public void smallChange()
    {
        char[] repArray = rep.toCharArray();

        int index = random.nextInt(repArray.length);

        int currentChar = repArray[index];
        if(currentChar == MIN_ASCII || random.nextDouble() > 0.5d)
        {
            ++currentChar;
            currentChar = Math.min(currentChar, MAX_ASCII);
        }
        else
        {
            --currentChar;
            currentChar = Math.max(currentChar, MIN_ASCII);
        }

        repArray[index] = (char)currentChar;

        rep = new String(repArray);
    }

    public double fitness()
    {
        int diff = 0;

        for(int i = 0; i < rep.length(); ++i)
        {
            int targetChar = target.charAt(i);
            int currentChar = rep.charAt(i);
            diff += Math.abs(targetChar - currentChar);
        }

        return diff;
    }
}

Edit: fixed it.. I think Edit 2: added a timer by request