Hello World генетический алгоритм

Возвращаясь к Queue ICPC Challenge. Когда алгоритм решения был уже написан и оставались считанные дни до конца соревнования мне пришло в голову поиграть с коэффициентами. Ведь в моем решении, как и почти в любом недетерминированном алгоритме были коэффициенты и от их настройки зависела эффективность алгоритма.

Но как же подобрать оптимальные коэффициенты, когда они нелинейно взаимодействуют друг с другом, когда не известны их границы и не возможно предсказать их влияние на результат исходя из теоретической модели. В голову пришло написание генетического алгоритма.

Чтобы с чего-то начать с генетическим алгоритмом, я написал генетический Hello World. Что он делает? Он берет случайные строки мутирует и скрещивает их до тех пор пока не получится строка ”Hello World!”. На мой взгляд, этот пример является наглядным пособием по реализации генетического алгоритма и помогает в написании генетических алгоритмов для реальных задач.

  

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


public class GAHelloWorld {

    public static final int POPULATION_SIZE = 1000;
    public static final double ELITE_RATE = 0.1;
    public static final double SURVIVE_RATE = 0.5;
    public static final double MUTATION_RATE = 0.2;
    public static final String TARGET = "Hello World!";
    private static final int MAX_ITER = 1000;

    void initializePopulation(List<Genome> population) {
        int tsize = TARGET.length();

        for (int i = 0; i < POPULATION_SIZE; i++) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < tsize; j++) {
                str.append((char) (Math.random() * 255));
            }
            Genome citizen = new Genome(str.toString());
            population.add(citizen);
        }

    }



    String mutate(String str) {
        int tsize = TARGET.length();
        int ipos = (int) (Math.random() * tsize);
        char delta = (char) (Math.random() * 255);

        return str.substring(0, ipos) + delta + str.substring(ipos + 1);

    }

    List<Genome> mate(List<Genome> population) {
        int esize = (int) (POPULATION_SIZE * ELITE_RATE);
        int tsize = TARGET.length();
        List<Genome> children = new ArrayList<Genome>();

        selectElite(population, children, esize);

        for (int i = esize; i < POPULATION_SIZE; i++) {
            int i1 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
            int i2 = (int) (Math.random() * POPULATION_SIZE * SURVIVE_RATE);
            int spos = (int) (Math.random() * tsize);

            String str = population.get(i1).str.substring(0, spos) +
                    population.get(i2).str.substring(spos);
            if (Math.random() < MUTATION_RATE) {
                str = mutate(str);
            }
            Genome child = new Genome(str);
            children.add(child);


        }
        return children;
    }

    private void selectElite(List<Genome> population, List<Genome> children, int esize) {
        for(int i=0; i<esize; i++){
            children.add(population.get(i));
        }
    }

    private void go(){
        List<Genome> population = new ArrayList<Genome>();
        initializePopulation(population);

        for (int i=0; i< MAX_ITER; i++) {
            Collections.sort(population);
            System.out.println(i + " > " + population.get(0));

            if (population.get(0).fitness == 0) {
                break;
            }

            population = mate(population);
        }

    }

    public static void main(String[] args) {
       new GAHelloWorld().go();
   }

}
class Genome implements Comparable<Genome> {
    final String str;
    final int fitness;

    public Genome(String str) {
        this.str = str;
        int fitness = 0;
        for (int j = 0; j < str.length(); j++) {
            fitness += Math.abs(str.charAt(j) - GAHelloWorld.TARGET.charAt(j));
        }
        this.fitness = fitness;
    }

    public int compareTo(Genome o) {
        return fitness - o.fitness;
    }

    public String toString(){
        return fitness + " " + str;
    }

}

Результат работы генетического Hello World-а:

  
0 > 419 Un~?z^Kr??p┬
1 > 262 Un~?z^Kr?j?↨
2 > 262 Un~?z^Kr?j?↨
…
15 > 46 Afpdm'Ynosa"
16 > 46 Afpdm'Ynosa"
17 > 42 Afpdm'Ynoia"
18 > 27 Jfpmm↓Vopoa"
…
33 > 9 Ielmo▼Wnole"
34 > 8 Ielmo▲Vopld"
35 > 8 Ielmo▲Vopld"
…
50 > 1 Hello World"
51 > 1 Hello World"
52 > 0 Hello World!

Конечно, запуская алгоритм снова и снова будут получатся другие результаты, ведь изначально выбираются случайные строки.