# 教程 | 遗传算法的基本概念和实现（附Java实现案例）

#### 遗传算法的概念

1. 初始化
2. 个体评价（计算适应度函数）
3. 选择运算
4. 交叉运算
5. 变异运算

#### 案例实现

```START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP```

Java 中的实例实现

```import java.util.Random;

/**
*
* @author Vijini
*/

//Main class
public class SimpleDemoGA {

Population population = new Population();
Individual fittest;
Individual secondFittest;
int generationCount = 0;

public static void main(String[] args) {

Random rn = new Random();

SimpleDemoGA demo = new SimpleDemoGA();

//Initialize population
demo.population.initializePopulation(10);

//Calculate fitness of each individual
demo.population.calculateFitness();

System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);

//While population gets an individual with maximum fitness
while (demo.population.fittest < 5) {
++demo.generationCount;

//Do selection
demo.selection();

//Do crossover
demo.crossover();

//Do mutation under a random probability
if (rn.nextInt()%7 < 5) {
demo.mutation();
}

//Calculate new fitness value
demo.population.calculateFitness();

System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
}

System.out.println("\nSolution found in generation " + demo.generationCount);
System.out.println("Fitness: "+demo.population.getFittest().fitness);
System.out.print("Genes: ");
for (int i = 0; i < 5; i++) {
System.out.print(demo.population.getFittest().genes[i]);
}

System.out.println("");

}

//Selection
void selection() {

//Select the most fittest individual
fittest = population.getFittest();

//Select the second most fittest individual
secondFittest = population.getSecondFittest();
}

//Crossover
void crossover() {
Random rn = new Random();

//Select a random crossover point
int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

//Swap values among parents
for (int i = 0; i < crossOverPoint; i++) {
int temp = fittest.genes[i];
fittest.genes[i] = secondFittest.genes[i];
secondFittest.genes[i] = temp;

}

}

//Mutation
void mutation() {
Random rn = new Random();

//Select a random mutation point
int mutationPoint = rn.nextInt(population.individuals[0].geneLength);

//Flip values at the mutation point
if (fittest.genes[mutationPoint] == 0) {
fittest.genes[mutationPoint] = 1;
} else {
fittest.genes[mutationPoint] = 0;
}

mutationPoint = rn.nextInt(population.individuals[0].geneLength);

if (secondFittest.genes[mutationPoint] == 0) {
secondFittest.genes[mutationPoint] = 1;
} else {
secondFittest.genes[mutationPoint] = 0;
}
}

//Get fittest offspring
Individual getFittestOffspring() {
if (fittest.fitness > secondFittest.fitness) {
return fittest;
}
return secondFittest;
}

//Replace least fittest individual from most fittest offspring

//Update fitness values of offspring
fittest.calcFitness();
secondFittest.calcFitness();

//Get index of least fit individual
int leastFittestIndex = population.getLeastFittestIndex();

//Replace least fittest individual from most fittest offspring
population.individuals[leastFittestIndex] = getFittestOffspring();
}

}

//Individual class
class Individual {

int fitness = 0;
int[] genes = new int[5];
int geneLength = 5;

public Individual() {
Random rn = new Random();

//Set genes randomly for each individual
for (int i = 0; i < genes.length; i++) {
genes[i] = rn.nextInt() % 2;
}

fitness = 0;
}

//Calculate fitness
public void calcFitness() {

fitness = 0;
for (int i = 0; i < 5; i++) {
if (genes[i] == 1) {
++fitness;
}
}
}

}

//Population class
class Population {

int popSize = 10;
Individual[] individuals = new Individual[10];
int fittest = 0;

//Initialize population
public void initializePopulation(int size) {
for (int i = 0; i < individuals.length; i++) {
individuals[i] = new Individual();
}
}

//Get the fittest individual
public Individual getFittest() {
int maxFit = Integer.MIN_VALUE;
for (int i = 0; i < individuals.length; i++) {
if (maxFit <= individuals[i].fitness) {
maxFit = i;
}
}
fittest = individuals[maxFit].fitness;
return individuals[maxFit];
}

//Get the second most fittest individual
public Individual getSecondFittest() {
int maxFit1 = 0;
int maxFit2 = 0;
for (int i = 0; i < individuals.length; i++) {
if (individuals[i].fitness > individuals[maxFit1].fitness) {
maxFit2 = maxFit1;
maxFit1 = i;
} else if (individuals[i].fitness > individuals[maxFit2].fitness) {
maxFit2 = i;
}
}
return individuals[maxFit2];
}

//Get index of least fittest individual
public int getLeastFittestIndex() {
int minFit = 0;
for (int i = 0; i < individuals.length; i++) {
if (minFit >= individuals[i].fitness) {
minFit = i;
}
}
return minFit;
}

//Calculate fitness of each individual
public void calculateFitness() {

for (int i = 0; i < individuals.length; i++) {
individuals[i].calcFitness();
}
getFittest();
}

}```

0 条评论

## 相关文章

3515

### 机器学习研究和开发所需的组件列表

Here is a list of components that are needed for the successful machine learning...

1022

2191

1191

2680

### 用金庸、古龙群侠名称训练 LSTM，会生成多么奇葩的名字？

AI 研习社按：本文转载自 Magicly 博客，获作者授权。阅读原文请见：http://magicly.me/2017/04/07/rnn-lstm-gene...

40011

1.9K6

### 基于seq2seq的中国对联自动配对技术实践

Sequence to Sequence模型这种基于编码--解码的模型已经被谷歌成功应用于机器翻译上。而理论上任意的序列到序列的有监督问题都可以用这种模型。如...

3418

### 第1篇：ATAC-seq的背景介绍以及与ChIP-Seq的异同

ATAC-seq（Assay for Transposase-Accessible Chromatin with high throughput sequenc...

3912

### 叫一声lncRNA你敢答应么[男女不限]

lncRNA 的全称是long noncoding RNA。即又长又表达且还不能编码翻译成蛋白质的一类RNA。

2141