用Java编写的GA

本文介绍了用Java编写的GA的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图根据我从用于游戏程序员的AI技术一书中选择的技术编写遗传算法，该技术使用二进制编码和健身比例选择（也称为轮盘赌选择）对基因进行编写。在二维数组中在程序中随机生成的总体。

I am attempting to write a Genetic Algorithm based on techniques I had picked up from the book "AI Techniques for Game Programmers" that uses a binary encoding and fitness proportionate selection (also known as roulette wheel selection) on the genes of the population that are randomly generated within the program in a two-dimensional array.

我最近遇到了一段伪代码并试图实现它，但是遇到了我需要做的具体细节问题。我检查过一些书籍和一些开源代码，但仍在努力取得进展。 我明白我必须得到总人口的总体适应度的总和，在总和与零之间选择一个随机数，然后如果数字大于父母要覆盖它，但我正在努力实现这些想法。

I recently came across a piece of pseudocode and have tried to implement it, but have come across some problems with the specifics of what I need to be doing. I've checked a number of books and some open-source code and am still struggling to progress. I understand that I have to get the sum of the total fitness of the population, pick a random number between the sum and zero, then if the number is greater than the parents to overwrite it, but I am struggling with the implementation of these ideas.

由于我的Java生锈，所以对这些想法的实施有任何帮助都会非常感激。

Any help in the implementation of these ideas would be very much appreciated as my Java is rusty.

推荐答案

以下是GA的完整概述。我确保非常详细，因此它可以很容易地编码为C / Java / Python /.../ p>

The following is a complete outline of the GA. I made sure to be very detailed so it can be easily coded to C/Java/Python/..

/* 1. Init population */ POP_SIZE = number of individuals in the population pop = newPop = [] for i=1 to POP_SIZE { pop.add( getRandomIndividual() ) } /* 2. evaluate current population */ totalFitness = 0 for i=1 to POP_SIZE { fitness = pop[i].evaluate() totalFitness += fitness } while not end_condition (best fitness, #iterations, no improvement...) { // build new population // optional: Elitism: copy best K from current pop to newPop while newPop.size()<POP_SIZE { /* 3. roulette wheel selection */ // select 1st individual rnd = getRandomDouble([0,1]) * totalFitness for(idx=0; idx<POP_SIZE && rnd>0; idx++) { rnd -= pop[idx].fitness } indiv1 = pop[idx-1] // select 2nd individual rnd = getRandomDouble([0,1]) * totalFitness for(idx=0; idx<POP_SIZE && rnd>0; idx++) { rnd -= pop[idx].fitness } indiv2 = pop[idx-1] /* 4. crossover */ indiv1, indiv2 = crossover(indiv1, indiv2) /* 5. mutation */ indiv1.mutate() indiv2.mutate() // add to new population newPop.add(indiv1) newPop.add(indiv2) } pop = newPop newPop = [] /* re-evaluate current population */ totalFitness = 0 for i=1 to POP_SIZE { fitness = pop[i].evaluate() totalFitness += fitness } } // return best genome bestIndividual = pop.bestIndiv() // max/min fitness indiv

请注意，目前您缺少健身功能（取决于域名）。交叉将是一个简单的单点交叉（因为您使用的是二进制表示）。变异可以是一个随意的简单翻转。

Note that currently you're missing a fitness function (depends on the domain). The crossover would be a simple one point crossover (since you are using a binary representation). Mutation could be a simple flip of a bit at random.

编辑：我已经在Java中实现了上面的伪代码，考虑到了你当前的代码结构和符号（请记住，我比ac更喜欢ac / c ++）。请注意，这绝不是最有效或最完整的实现，我承认我写得很快：

EDIT: I have implemented the above pseudocode in Java taking into consideration your current code structure and notations (keep in mind i am more of a c/c++ guy than java). Note this is in no way the most efficient or complete implementation, I admit I wrote it rather quickly:

Individual.java

import java.util.Random; public class Individual { public static final int SIZE = 500; private int[] genes = new int[SIZE]; private int fitnessValue; public Individual() {} public int getFitnessValue() { return fitnessValue; } public void setFitnessValue(int fitnessValue) { this.fitnessValue = fitnessValue; } public int getGene(int index) { return genes[index]; } public void setGene(int index, int gene) { this.genes[index] = gene; } public void randGenes() { Random rand = new Random(); for(int i=0; i<SIZE; ++i) { this.setGene(i, rand.nextInt(2)); } } public void mutate() { Random rand = new Random(); int index = rand.nextInt(SIZE); this.setGene(index, 1-this.getGene(index)); // flip } public int evaluate() { int fitness = 0; for(int i=0; i<SIZE; ++i) { fitness += this.getGene(i); } this.setFitnessValue(fitness); return fitness; } }

Population.java

import java.util.Random; public class Population { final static int ELITISM_K = 5; final static int POP_SIZE = 200 + ELITISM_K; // population size final static int MAX_ITER = 2000; // max number of iterations final static double MUTATION_RATE = 0.05; // probability of mutation final static double CROSSOVER_RATE = 0.7; // probability of crossover private static Random m_rand = new Random(); // random-number generator private Individual[] m_population; private double totalFitness; public Population() { m_population = new Individual[POP_SIZE]; // init population for (int i = 0; i < POP_SIZE; i++) { m_population[i] = new Individual(); m_population[i].randGenes(); } // evaluate current population this.evaluate(); } public void setPopulation(Individual[] newPop) { // this.m_population = newPop; System.arraycopy(newPop, 0, this.m_population, 0, POP_SIZE); } public Individual[] getPopulation() { return this.m_population; } public double evaluate() { this.totalFitness = 0.0; for (int i = 0; i < POP_SIZE; i++) { this.totalFitness += m_population[i].evaluate(); } return this.totalFitness; } public Individual rouletteWheelSelection() { double randNum = m_rand.nextDouble() * this.totalFitness; int idx; for (idx=0; idx<POP_SIZE && randNum>0; ++idx) { randNum -= m_population[idx].getFitnessValue(); } return m_population[idx-1]; } public Individual findBestIndividual() { int idxMax = 0, idxMin = 0; double currentMax = 0.0; double currentMin = 1.0; double currentVal; for (int idx=0; idx<POP_SIZE; ++idx) { currentVal = m_population[idx].getFitnessValue(); if (currentMax < currentMin) { currentMax = currentMin = currentVal; idxMax = idxMin = idx; } if (currentVal > currentMax) { currentMax = currentVal; idxMax = idx; } if (currentVal < currentMin) { currentMin = currentVal; idxMin = idx; } } //return m_population[idxMin]; // minimization return m_population[idxMax]; // maximization } public static Individual[] crossover(Individual indiv1,Individual indiv2) { Individual[] newIndiv = new Individual[2]; newIndiv[0] = new Individual(); newIndiv[1] = new Individual(); int randPoint = m_rand.nextInt(Individual.SIZE); int i; for (i=0; i<randPoint; ++i) { newIndiv[0].setGene(i, indiv1.getGene(i)); newIndiv[1].setGene(i, indiv2.getGene(i)); } for (; i<Individual.SIZE; ++i) { newIndiv[0].setGene(i, indiv2.getGene(i)); newIndiv[1].setGene(i, indiv1.getGene(i)); } return newIndiv; } public static void main(String[] args) { Population pop = new Population(); Individual[] newPop = new Individual[POP_SIZE]; Individual[] indiv = new Individual[2]; // current population System.out.print("Total Fitness = " + pop.totalFitness); System.out.println(" ; Best Fitness = " + pop.findBestIndividual().getFitnessValue()); // main loop int count; for (int iter = 0; iter < MAX_ITER; iter++) { count = 0; // Elitism for (int i=0; i<ELITISM_K; ++i) { newPop[count] = pop.findBestIndividual(); count++; } // build new Population while (count < POP_SIZE) { // Selection indiv[0] = pop.rouletteWheelSelection(); indiv[1] = pop.rouletteWheelSelection(); // Crossover if ( m_rand.nextDouble() < CROSSOVER_RATE ) { indiv = crossover(indiv[0], indiv[1]); } // Mutation if ( m_rand.nextDouble() < MUTATION_RATE ) { indiv[0].mutate(); } if ( m_rand.nextDouble() < MUTATION_RATE ) { indiv[1].mutate(); } // add to new population newPop[count] = indiv[0]; newPop[count+1] = indiv[1]; count += 2; } pop.setPopulation(newPop); // reevaluate current population pop.evaluate(); System.out.print("Total Fitness = " + pop.totalFitness); System.out.println(" ; Best Fitness = " + pop.findBestIndividual().getFitnessValue()); } // best indiv Individual bestIndiv = pop.findBestIndividual(); } }