用Java编写的GA

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

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

由于我的Java生疏，因此非常感谢任何帮助实现这些想法。

Answer 1

以下是GA的完整概述。 我确保非常详细，因此可以很容易地编码为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()0; idx++) { rnd -= pop[idx].fitness } indiv1 = pop[idx-1] // select 2nd individual rnd = getRandomDouble([0,1]) * totalFitness for(idx=0; idx0; 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 

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

---

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

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 

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; idx0; ++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 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
		      	
 为什么不使用像JGAP这样的开源框架： http ：//jgap.sf.net 

Answer 2

我通过创建“累积适应度数组”和二进制搜索来实现此算法，从而减少了在选择期间迭代遍历数组中每个元素的需要 ：

1. 对于种群大小N，创建累积适应度数组：arr [N]。
2. 设置arr [0]：= computeFitness（个体[0]）。
3. 然后，对于每个后续元素：X，arr [X] = arr [X-1] + computeFitness（个体[X]）。
4. 生成0到arr [N]之间的随机数（即总适​​应度）。
5. 使用二进制搜索（例如Collections.binarySearch）在累积适应度数组中找到适当的索引，并使用此索引选择个体。

请注意，您只需要在再现阶段开始时创建适应度数组，然后可以多次重复使用它以在O（log N）时间内执行选择。

另外，请注意比赛选择更容易实现！

Answer 3

您正在寻找的概念称为“轮盘赌轮选择”。 你还没有已建立的适应度函数（你可能暗示每个人的适应度是其染色体的整数值），但是当你做一般计划时：

1. 总结整个人口的适应性。
2. 获取0和总体适应度之间的随机数（称之为x）。
3. 通过人口迭代。 对于每个成员：
   1. 从x中减去成员的适应度。
   2. 如果x现在小于或等于零，请选择当前成员。

还有其他等效实现，但一般的想法是选择具有与其适合度成比例的概率的成员。

编辑：关于健身function的一些注释。 染色体的表示（在您的情况下为32位整数）与用于评估染色体的适应度函数无关。 例如，二进制编码通常将染色体视为一组打包成适当大小的整数值的位域。 然后可以通过适当的位掩码操作来完成交叉和变异。 如果您有兴趣，我可以发布一些简单的GA代码（在C和Python中），它使用按位运算来实现这些function。 我不确定你对这些语言有多舒服。

Answer 4

我在java中做了一个可扩展的实现，其中运算符和单个结构由一起工作的接口很好地定义。 Github repo在这里https://github.com/juanmf/ga

它具有每个运营商的标准实施，以及具有特定个人/人口结构和健身计的示例问题实施。 示例性问题实施是找到一支优秀的足球队，其中包括20支球队中的球员和预算限制。

要使其适应您当前的问题，您需要提供这些接口的实现：

 juanmf.ga.structure.Gen; juanmf.ga.structure.Individual; juanmf.ga.structure.IndividualFactory; juanmf.ga.structure.Population; // Has a basic implementation already juanmf.ga.structure.PopulationFactory; 

在pkg juanmf.grandt您有示例问题实现类，以及如何发布它们，如下面的代码片段所示。

要发布实现，您只需从这个Spring bean返回正确的类：

 /** * Make sure @ComponentScan("pkg") in juanmf.ga.App.java includes this class' pkg * so that these beans get registered. */ @Configuration public class Config { @Bean(name="individualFactory") public IndividualFactory getIndividualFactory() { return new Team.TeamFactory(); } @Bean(name="populationFactory") public PopulationFactory getPopulationFactory() { return new Team.TeamPopulationFactory(); } @Bean(name="fitnessMeter") public FitnessMeter getFitnessMeter() { return new TeamAptitudeMeter(); } } 

Crosser运算符有两种相同技术的实现，一种顺序和一种并发，远远超过顺序。

可以指定停止条件。 如果没有给出，它有一个默认停止条件，在100代之后停止而没有任何改进（这里你必须小心精英，不要放松每一代的最佳状态，以便有效地触发这个停止条件）。

所以，如果有人愿意试一试，我很乐意提供帮助。 欢迎任何人提供建议，更好的运营商实施：D或任何改进拉动请求。

Answer 5

关于轮盘赌选择的其他问题应该有助于：

• 轮盘赌选择算法
• 遗传算法中的轮盘选择

在第一个中， 我试图解释轮盘赌轮是如何工作的。 第二， Jarod Elliott提供了一些伪代码 。 结合Adamski对高效实现的描述 ，这些应该足以让某些工作变得有效。

Answer 6

只是值得一提的一点。 轮盘赌选择（如伪代码所示）不适用于最小化问题 – 但它对最大化问题有效。

由于选择最适合的个体的方式，最小化情况将不成立。 详细信息请参阅 ： 计算智能：第2版