So che le domande di GA sono spesso quasi impossibili da rispondere esattamente, ma sto cercando qualche consiglio generale (anche se un consiglio specifico sarebbe fantastico!).
Ho appena scritto il mio secondo GA, che cerca di trovare una frase (dire "mi piacciono le banane"), che fa generando stringhe binarie di 5 volte la lunghezza della stringa di destinazione (come ho permesso 32 = 2 ^ 5 caratteri nelle mie corde, l'alfabeto in minuscolo, lo spazio e cinque caratteri di punteggiatura) e l'allevamento e la modifica.
Questo è tutto basato su un esempio in Practical Genetic Algorithms di Randy e Sue Ellen Haupt (non sono sicuro che mi sia permesso collegarmi ad Amazon, quindi non l'ho fatto). altre fonti mostrano profili simili, quindi non penso che ci sia qualcosa di specifico su quel bok, stavo solo leggendolo, e così ho provato il loro esempio.
Ho provato la mia GA su "colorado", che era quella usata nel libro. Ha trovato la risposta giusta in circa 200-800 generazioni, che rispetto alle possibili combinazioni 1E12 dei caratteri consentiti non è male. Tuttavia, gli autori del libro hanno detto che la loro GA ha trovato la risposta in sole 17 generazioni, il che rende il mio algoritmo incredibilmente lento.
Se ce l'avessimo riuscito (diciamo) 100-300, avrei potuto scrivere la mia prestazione peggiore per mancanza di esperienza, ma 17 è un'enorme differenza dai miei risultati. Voglio sapere come migliorare il mio GA per arrivare ovunque.
Inserirò del codice qui sotto. Questo è C #, ma chiunque abbia familiarità con una qualsiasi delle famiglie di linguaggi C dovrebbe essere in grado di capirlo. Non uso molto roba specifica per C # qui. Non includerò alcune delle funzioni di utilità, in quanto sono state testate, quindi so che funzionano, e questo aiuterà a mantenere bassa la quantità di codice. Se pensi di aver perso qualcosa di importante, faccelo sapere e lo aggiungerò.
Per prima cosa, ecco la mia semplice classe Chromosome ...
public class Chromosome {
public Chromosome(string genes) {
Genes = genes;
}
public string Genes { get; set; }
public double Fitness { get; set; }
}
Ecco la routine principale ...
void Main() {
// We are assuming that each character is mapped to a number between 0 (a) and 25 (z),
// with space . , ! ? and - taking up the numbers from 26 to 31.
// Thus, each character can be encoded in a binary string of length 5 (ie "00000"
// is a, "11001" is z and so on), and so any string can be encoded as a sequence
// of 1s and 0s, with the encoded length being five times the original string length
int len = target.Length * 5; // Length of gene string in each chromosome
int totalChromosomes = 32; // Number of chromosomes in the population
double crossover = 0.5;
// The gene number at which crossover will take place
int crossoverGene = (int)(len * crossover);
double mutationRate = 0.04;
// Generate the initial (random) population
List<Chromosome> population = Initial(totalChromosomes, len);
int generations = 10000;
int genNumber = 0;
Chromosome best;
do {
// get the next generation
population = Breed(population, crossoverGene, mutationRate);
// Find the best chromosome
best = population.OrderBy(c => c.Fitness).First();
genNumber++;
}
while (genNumber < generations && best.Fitness > 0);
Console.WriteLine("Best fitness: " + best.Fitness.ToString("F3") + "\tGenes: "
+ Decode(best.Genes) + "\t@ generation " + genNumber + "/" + generations);
}
Ecco la funzione fitness, che restituisce il numero di caratteri errati ...
private static int Fitness(Chromosome c) {
int fitness = 0;
for (int i = 0; i < target.Length; i++) {
int cTarget = (int)target[i];
string genes = c.Genes.Substring(i * 5, 5);
char cChromosome = BinaryToChar(genes);
if (cTarget != (int)cChromosome) {
// Add 1 to the fitness for every incorrect character
fitness++;
}
}
return fitness;
}
La funzione Razza prende la nostra attuale popolazione, genera i cromosomi insieme e restituisce una nuova popolazione (si spera meglio). Diciamo che abbiamo una popolazione di n cromosomi, generiamo n / 2 nuovi cromosomi, quindi aggiungiamo il miglior n / 2 della popolazione attuale.
La funzione di roulette qui usata è un'implementazione semplice della selezione di una ruota di roulette. Non ho incluso il codice come ho provato molto sul GA precedente, e sembra funzionare bene ...
private static List<Chromosome> Breed(List<Chromosome> population, int crossoverGene,
double mutationRate) {
List<Chromosome> nextGeneration = new List<Chromosome>();
for (int nChromosome = 0; nChromosome < population.Count() / 2; nChromosome++) {
Chromosome daddy = Roulette(population);
Chromosome mummy = Roulette(population);
string babyGenes = daddy.Genes.Substring(0, crossoverGene)
+ mummy.Genes.Substring(crossoverGene);
string mutatedGenes = "";
foreach (char gene in babyGenes) {
// P() returns a random number between 0 and 1
mutatedGenes += P() < mutationRate ? (gene == '1' ? '0' : '1') : gene;
}
Chromosome baby = new Chromosome(mutatedGenes);
baby.Fitness = Fitness(baby);
nextGeneration.Add(baby);
}
// Add on the best of the previous generation to make up the numbers in the next gen
nextGeneration = nextGeneration // the new chromosomes we just bread
// join with the previous generation, order by fitness, best first
.Union(population.OrderBy(p => p.Fitness)
// Only take the first n chromosomes, discarding the rest
.Take(population.Count() - nextGeneration.Count())).ToList();
return nextGeneration;
}
Spero che sia abbastanza del codice per vedere cosa sto facendo. Non credo che nessuna delle funzioni omesse abbia un codice significativo.
Ho provato questo su varie stringhe, variando la dimensione della popolazione, il crossover e la mutazione, ma a parte il fatto che non riesce a trovare una risposta su stringhe più lunghe, nulla sembra aver fatto alcuna differenza evidente.
Chiunque è in grado di darmi qualche idea su come posso migliorare il mio algoritmo?
Gli autori del libro hanno menzionato che hanno usato una popolazione di 16. Ho provato a variare la popolazione, e ho scoperto che i valori intorno a 16 impiegavano molto più tempo per convergere (100 generazioni o più), mentre una volta mi sono alzato a circa 50 intorno ai 200-800.
Modifica Seguendo un suggerimento di amon, ho provato una funzione di fitness che confronta le stringhe correnti e di destinazione su base bit per bit. Ho codificato la stringa di destinazione in una stringa binaria e ho usato la seguente funzione di fitness ...
private static int Fitness(Chromosome c) {
int fitness = 0;
for (int i = 0; i < encodedTarget.Length; i++) {
if (c.Genes[i] != encodedTarget[i]) {
fitness++;
}
}
return fitness;
}
Tuttavia, questo non ha fatto alcuna differenza. Lo includo qui nel caso in cui qualcuno possa dare suggerimenti su come migliorarlo.