我试图根据我从书“人工智能技术为游戏程序员”使用上是人口的基因的二进制编码和健身比例选择（也称为赌轮选择）拿起技术来写一个遗传算法在两维阵列在程序中随机生成的。
我最近碰到一件伪代码 ，并试图实现它，但所遇到的一些问题，什么我需要做的细节。 我查了一些书籍和一些开放源代码的和至今还在努力进步。 我明白，我必须得到居民的总健身的总和，挑选和与零之间的随机数，那么如果数大于父母覆盖它，但我有这些想法的实现挣扎。
在这些想法的实现任何帮助会非常赞赏，因为我的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()<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
需要注意的是目前你缺少一个健身功能（视域）。 交叉将是一个简单的单点交叉（因为你使用的是二进制表示）。 突变可能是有点随意简单的翻转。
编辑 ：我已经实现了在Java中考虑到当前的代码结构和注释上述伪代码（记住我比较C / C ++的家伙比Java的）。 注意，这是没有办法的最有效或完整的实现，我承认我相当快写的：
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();
}
}
Answer 2:
为什么不使用像JGAP一个开源框架： http://jgap.sf.net
Answer 3:
我已经通过创建“累积健身阵列”和二进制搜索 ，从而减少了需要通过选择期间阵列中的每个元件进行迭代执行该算法：
- 对于人口大小N创建累积健身数组：ARR [N]。
- 设置ARR [0]：= computeFitness（个体[0]）。
- 然后，对于每个随后的元件：X，ARR [X] = ARR [X-1] + computeFitness（个体[X]）。
- 生成0和ARR [N]之间的随机数（即，总的健身）。
- 使用二进制搜索（例如Collections.binarySearch）来定位，累计健身数组中的相应指数，并使用该指数来选择个体。
请注意，您只需要建立在复制阶段开始健身阵列，并且可以重新使用它多次执行为O选项（日志N）的时间。
顺便说一句，请注意锦标赛选择是更容易实现！
Answer 4:
你要找的这个概念被称为“轮盘赌选择。” 你没有一个既定的适应度函数，但（你可能会暗示每个个体的适应度的染色体的两个积分值），但是当你做一个总体规划是：
- 总结整个种群的适应度。
- 得到一个随机数（称之为X）0和总健身之间。
- 通过人口迭代。 对于每个成员：
- 减去X的成员的健康。
- 如果x现在小于或等于是零，选择当前构件。
还有其他等同的实施，但总的想法是用概率成正比，他们的健身选择成员。
编辑：健身功能的一些注意事项。 染色体（你的情况作为一个32位整数）的表示是独立于用于评估它的适应度函数。 例如，二进制编码典型地治疗所述染色体为一组包装成适当大小的积分值的位域。 交叉和变异然后可以通过适当的位屏蔽操作完成。 如果你有兴趣，我可以张贴它使用位操作来实现这些功能的一些简单的GA代码，我周围铺设（在C和Python）。 我不知道你是多么的惬意与这些语言。
Answer 5:
余由在Java一个可扩展的实施方式中，在该运营商和个别结构被很好地一起工作的接口定义。 Github上回购这里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你有例题实现类，以及如何将它们发布，如下面的代码片段。
要发布你实现你就必须从今年春天豆返回适当类：
/**
* 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或任何改善pull请求。
Answer 6:
关于轮盘赌选择这些其他的问题应该有所帮助：
- 轮盘赌选择算法
- 在遗传算法的轮盘赌选择
在第一个， 我试图解释轮盘赌是如何工作的。 在第二， 贾罗德埃利奥特提供了一些伪代码 。 联合的有效实施亚当斯基的描述 ，这些应该足以得到的东西的工作。
Answer 7:
只是一个点值得一提。 轮盘赌选择（如伪代码所示）将不会为最小化问题的工作 - 但它是，有效的最大化问题。
由于这是选择最适合个人的方式，最小化的情况下将不会举行。 ：在中提供了详细的计算智能：第二版
文章来源: GA written in Java
