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

基因遗传算法，其灵感源自于达尔文的自然进化理论，是一种启发式的搜索算法。此算法模拟了自然选择的过程，即最适应环境的个体被选中进行繁殖，进而繁衍出下一代。本文旨在对遗传算法的基本理念和具体实现进行简要介绍，以期向读者展现启发式搜索的独特魅力。

如上图左侧所示，遗传算法中的个体是由若干条染色体构成的，而每一条染色体又是由众多基因所组成。在图右侧，我们可以观察到染色体的分割与组合的具体方法。

自然选择的概念

自然选择的过程始于挑选出适应环境能力最强的个体。这些个体所拥有的特性会被后代所继承，并随之传递至下一代。若父母具备更强的适应性，那么他们的子女存活的机会也将更大。通过不断重复这一自然选择的过程，最终，我们将见证一个由最适应环境的个体所构成的新一代诞生。

此理念适用于解决搜索相关的问题。在众多可能的解决方案中，我们需筛选，以找到最为理想的那个。

遗传算法含以下五步：

初始化

个体评价（计算适应度函数）

选择运算

交叉运算

变异运算

初始化

此流程始于一个种群中的若干个体，且每个个体均被视为待求解问题的一个潜在答案。

个体具有一系列参数（变量）作为其特征，这些特征即所谓的基因，将这些基因依次连接起来，便能够构成染色体（即问题的解决方案）。

在遗传算法领域，个体的遗传信息以字符串形式展现kaiyun全站app登录入口，我们通常采用二进制编码方式，即由1和0组成的字符串来表示染色体。这样，基因串或候选解的特性就被嵌入到了染色体之中。

种群、染色体和基因

个体评价通过适应度函数来衡量个体对环境的适应性，这实际上反映了个体与其他个体竞争的能力。每个个体都拥有一个适应度分数，而个体被选为繁殖对象的机会则直接与这个分数挂钩。适应度函数的数值越高，得到的解的质量也就越优良。适应度函数不仅是遗传算法进化的核心动力开yun体育app官网网页登录入口，而且是自然选择的唯一评判标准，其设计必须紧密贴合所求解问题的具体需求。

选择运算

挑选运算的目标在于挑选出最适应环境的个体，并将这些个体的基因传承至下一代。依据它们的适应度评价，我们倾向于选择多对较为优秀的个体（即父母）。那些适应度较高的个体更容易被选中用于繁殖，从而使得优秀父母的基因得以延续至下一代。

交叉运算

遗传算法的核心环节是交叉运算，在这个过程中，每一对匹配的亲本基因都会随机确定交叉的位置。

举个例子，下图的交叉点为3。

父母间在交叉点之前交换基因，从而产生了后代。

父母间交换基因，然后产生的新后代被添加到种群中。

变异运算

在这些新产生的后代个体中，部分基因或许会受到低概率变异因素的影响。这表明kaiyun.ccm，在二进制序列中，某些特定的位可能会发生翻转。

变异运算前后

变异运算可用于保持种群内的多样性，并防止过早收敛。

终止

当群体趋于稳定（即群体内部不再出现与前代显著不同的后代）时，该算法便会停止运行。换言之，遗传算法能够为特定问题提供一组可能的解决方案。

案例实现

种群数量保持稳定。每当新一代诞生，那些适应能力最弱的个体便会淘汰，从而为下一代腾出生存空间。这一过程循环往复，不断进行，旨在孕育出比上一代更优秀的个体。

这一迭代过程的伪代码：

START

构建初始种群

Compute fitness

REPEAT

Selection

Crossover

Mutation

Compute fitness

直至人口趋于一致，

STOP

Java中的示例实现

此部分呈现了遗传算法在Java语言中的具体应用案例，我们有权对这些代码进行自由调整和优化。在示例中，每组基因包含五个成员，每个成员均能存储一个二进制数字，0或1。适应度值取决于基因组中1的数量。当基因组中全部五个位置均为1时，该个体的适应度达到最高点。反之，若基因组中不包含任何1，则该个体的适应度将降至最低。该遗传算法旨在追求个体适应度的最大化，并形成由适应度最高的个体构成的群体。值得注意的是，在本例中，经过交叉和突变操作后，那些适应度较低的个体将被适应度更高的新一代后代所取代。

import java.util.Random;

/**

* @author Vijini

*/

//Main class

public class SimpleDemoGA {

创建了一个名为Population的新对象，其初始化为Population类型。

Individual fittest;

Individual secondFittest;

int generationCount = 0;

args) {

Random rn = new Random();

创建了一个名为SimpleDemoGA的实例，并将其赋值给变量demo。

//Initialize population

初始化人口数量为10的种群，调用demo.population的initializePopulation方法。

对每一个个体进行体质评估

执行demo群体中的计算适应度函数；对demo人口进行适应度评估；调用demo的人口计算适配度方法。

输出信息：当前代数为 ${demo.generationCount}，最适应的个体为 ${demo.population.fittest}。

随着人口的增加，个体中那些具有最高适应度的成员被纳入其中。

当（演示）的种群中，最优秀的个体< 5) {

++demo.generationCount;

//Do selection

demo.selection();

//Do crossover

demo.crossover();

在随机概率的指导下进行变异操作。

if (rn.nextInt()%7 < 5) {

demo.mutation();

将最健壮的后代纳入种群之中。

demo.addFittestOffspring();

//Calculate new fitness value

demo.population.calculateFitness();

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

在演示的代数中，成功找到了解决方案，当前处于第 + demo.generationCount + 代。

输出结果为：“健康指数：”+demo种群中适应度最高的个体适应度值。

System.out.print("Genes: ");

for (int i = 0; i < 5; i++) {

系统输出demo种群中适应度最高的个体所拥有的基因。

);

System.out.println("");

//Selection

void selection() {

挑选出最适应环境的个体

获取种群中最适应的个体，即：fittest = population.getFittest();

请挑选出第二位最适应环境的个体。

获取种群中第二适应度的个体：secondFittest = population.getSecondFittest();

//Crossover

void crossover() {

请随机选择一个交叉点。

int crossOverPoint = rn生成一个随机数，该数位于population.individuals的范围内。

.geneLength);

//Swap values among parents

for (int i = 0; i < crossOverPoint; i++) {

int temp = fittest.genes

fittest.genes

= secondFittest.genes

secondFittest.genes

= temp;

//Mutation

void mutation() {

请随机选择一个变异位点。

定义变量mutationPoint，其值为随机数生成器rn在population.individuals范围内产生的随机整数。

.geneLength);

在突变点处对数值进行翻转

if (fittest.genes

mutationPoint

== 0) {

fittest.genes

mutationPoint

= 1;

} else {

设定突变点为随机数生成器rn在种群个体集合population.individuals中生成的任意值。

.geneLength);

if (secondFittest.genes

mutationPoint

== 0) {

secondFittest.genes

mutationPoint

= 1;

//Get fittest offspring

个体获取最健壮的后代函数{

若（fittest的适应度值）高于（secondFittest的适应度值），{

return fittest;

return secondFittest;

从最优秀的后代中淘汰掉最不适应的个体。

void addFittestOffspring() {

更新后代个体的适应度数值

fittest.calcFitness();

secondFittest.calcFitness();

获取最不适应个体的索引

获取种群中最不适应的索引值，将其赋值给变量leastFittestIndex。

//Replace least fittest individual from most fittest offspring

population.individuals

leastFittestIndex

= getFittestOffspring();

//Individual class

class Individual {

int fitness = 0;

int

genes = new int

int geneLength = 5;

public Individual() {

为每位个体随机设定基因序列。

for (int i = 0; i < genes.length; i++) {

genes

= rn.nextInt() % 2;

fitness = 0;

//Calculate fitness

public void calcFitness() {

if (genes

== 1) {

++fitness;

//Population class

class Population {

int popSize = 10;

Individual

individuals = new Individual

10

int fittest = 0;

//Initialize population

public void 对种群进行初始化，参数为种群规模，其值为 size。

for (int i = 0; i < individuals.length; i++) {

individuals

= new Individual();

//Get the fittest individual

的最优个体

设定一个最大适应值变量maxFit为整型最小值。

if (maxFit individuals

maxFit1

.fitness) {

maxFit2 = maxFit1;

} else if (individuals

.fitness > individuals

maxFit2

.fitness) {

获取最不适应个体的索引

公开方法getLeastFittestIndex用于获取最适应的索引值，其返回类型为整型。

int minFit = 0;

if (minFit >= individuals

.fitness) {

minFit = i;

return minFit;

//Calculate fitness of each individual

public方法calculateFitness执行，用于计算适应度。

individuals

.calcFitness();

getFittest();