Friday, May 21, 2010

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!


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

No comments:

Post a Comment