Но как же подобрать оптимальные коэффициенты, когда они нелинейно взаимодействуют друг с другом, когда не известны их границы и не возможно предсказать их влияние на результат исходя из теоретической модели. В голову пришло написание генетического алгоритма.
Чтобы с чего-то начать с генетическим алгоритмом, я написал генетический 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!
Конечно, запуская алгоритм снова и снова будут получатся другие результаты, ведь изначально выбираются случайные строки.
Мне нравятся https://cryptograph.life/post_crypto/kak-sozdat-svoyu-birzhu-kriptovalyut В выборе криптовалютного рынка. И торговле криптовалютой.
ReplyDelete