我正在尝试根据我从“游戏程序员的人工智能技术”一书中学到的技术编写一个遗传算法，该技术使用二进制编码和适应度比例选择（也称为轮盘赌选择）对人口的基因进行选择在程序中随机生成一个二维数组。
我最近遇到了一段伪代码并尝试实现它，但是在我需要做的细节方面遇到了一些问题。我检查了许多书籍和一些开源代码，但仍在努力取得进展。我知道我必须得到人口总适应度的总和，在总和和零之间选择一个随机数，然后如果该数字大于父母将其覆盖，但我正在努力实现这些想法.
由于我的 Java 生锈了，因此非常感谢您对实现这些想法的任何帮助。
以下是 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 中实现了上述伪代码（请记住，我比 java 更喜欢 ac/c++）。请注意，这绝不是最有效或最完整的实现，我承认我写得相当快：
个人.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;
}
}
人口.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();
}
}
为什么不使用像 JGAP 这样的开源框架：http: //jgap.sf.net
我通过创建“累积适应度数组”和二分搜索实现了这个算法，从而减少了在选择过程中遍历数组中每个元素的需要：
请注意，您只需要在复制阶段开始时创建适应度数组，然后可以多次重复使用它以在O(log N)时间内执行选择。
顺便说一句，请注意锦标赛选择更容易实现！
您正在寻找的概念称为“轮盘赌选择”。您还没有确定的适应度函数（您可能暗示每个个体的适应度是其染色体的积分值），但是当您进行总体规划时：
还有其他等效的实现，但总体思路是选择概率与其适应度成正比的成员。
编辑：关于健身功能的一些说明。染色体的表示（在您的情况下为 32 位整数）与用于评估它的适应度函数无关。例如，二进制编码通常将染色体视为一组位域，这些位域打包成一个适当大小的整数值。然后可以通过适当的位掩码操作来完成交叉和变异。如果您有兴趣，我可以发布一些我已经放置的简单 GA 代码（在 C 和 Python 中），它使用按位运算来实现这些功能。我不确定您对这些语言是否满意。
我在 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您有示例问题实现类，以及如何发布它们，如下面的代码片段所示。
要发布你的实现，你只需要从这个 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 或任何改进的拉取请求。
这些有关轮盘赌选择的其他问题应该会有所帮助：
在第一个中，我试图解释轮盘赌的工作原理。第二，Jarod Elliott 提供了一些伪代码。结合Adamski 对有效实现的描述，这些应该足以让某些东西发挥作用。
只是值得一提的一点。轮盘选择（如伪代码中所示）不适用于最小化问题 - 但是，它对最大化问题有效。
由于选择最适合的个体的方式，最小化的情况将不成立。详细信息见：计算智能：第 2 版