遺傳算法的基本概念和實現(附 Java 實現案例)

　　基因遺傳算法是一種靈感源於達爾文自然進化理論的啟發式搜索算法。該算法反映了自然選擇的過程，即最適者被選定繁殖，並產生下一代。本文簡要地介紹了遺傳算法的基本概念和實現，希望能為讀者展示啟發式搜索的魅力。

　

　　如上圖（左）所示，遺傳算法當個體由多條染色體組成，每條染色體由多個基因組成。上圖（右）展示了染色體分割和組合方式。

　　自然選擇的概念

　　自然選擇的過程從選擇群體中最適應環境的個體開始。後代繼承了父母的特性，並且這些特性將添加到下一代中。如果父母具有更好的適應性，那麼它們的後代將更易於存活。迭代地進行該自然選擇的過程，最終，我們將得到由最適應環境的個體組成的一代。

　　這一概念可以被應用於搜索問題中。我們考慮一個問題的諸多解決方案，並從中搜尋出最佳方案。

　　遺傳算法含以下五步：

　　初始化

　　個體評價（計算適應度函數）

　　選擇運算

　　交叉運算

　　變異運算

　　初始化

　　該過程從種群的一組個體開始，且每一個體都是待解決問題的一個候選解。

　　個體以一組參數（變量）為特徵，這些特徵被稱為基因，串聯這些基因就可以組成染色體（問題的解）。

　　在遺傳算法中，單個個體的基因組以字符串的方式呈現，通常我們可以使用二進位（1和0的字符串）編碼，即一個二進位串代表一條染色體串。因此可以說我們將基因串或候選解的特徵編碼在染色體中。

　　

　　種群、染色體和基因

　　個體評價利用適應度函數評估了該個體對環境的適應度（與其它個體競爭的能力）。每一個體都有適應度評分，個體被選中進行繁殖的可能性取決於其適應度評分。適應度函數值越大，解的質量就越高。適應度函數是遺傳算法進化的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

　　選擇運算

　　選擇運算的目的是選出適應性最好的個體，並使它們將基因傳到下一代中。基於其適應度評分，我們選擇多對較優個體（父母）。適應度高的個體更易被選中繁殖，即將較優父母的基因傳遞到下一代。

　　交叉運算

　　交叉運算是遺傳算法中最重要的階段。對每一對配對的父母，基因都存在隨機選中的交叉點。

　　舉個例子，下圖的交叉點為3。

　　

　　父母間在交叉點之前交換基因，從而產生了後代。

　　父母間交換基因，然後產生的新後代被添加到種群中。

　　

　　變異運算

　　在某些形成的新後代中，它們的某些基因可能受到低概率變異因子的作用。這意味著二進位位串中的某些位可能會翻轉。

　

　　變異運算前後

　　變異運算可用於保持種群內的多樣性，並防止過早收斂。

　　終止

　　在群體收斂的情況下（群體內不產生與前一代差異較大的後代）該算法終止。也就是說遺傳算法提供了一組問題的解。

案例實現

　　種群的規模恆定。新一代形成時，適應度最差的個體凋亡，為後代留出空間。這些階段的序列被不斷重複，以產生優於先前的新一代。

　　這一迭代過程的偽代碼：

　　START

Generate the initial population

Compute fitness

REPEAT

Selection

Crossover

Mutation

Compute fitness

UNTIL population has converged

STOP

　　Java中的示例實現

　　以下展示的是遺傳算法在Java中的示例實現，我們可以隨意調試和修改這些代碼。給定一組五個基因，每一個基因可以保存一個二進位值0或1。這裡的適應度是基因組中1的數量。如果基因組內共有五個1，則該個體適應度達到最大值。如果基因組內沒有1，那麼個體的適應度達到最小值。該遺傳算法希望最大化適應度，並提供適應度達到最大的個體所組成的群體。注意：本例中，在交叉運算與突變運算之後，適應度最低的個體被新的，適應度最高的後代所替代。

　　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();

}

//Add fittest offspring to population

demo.addFittestOffspring();

//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() {

//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() {

//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 {

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

if (secondFittest.genes[mutationPoint] == 0) {

secondFittest.genes[mutationPoint] = 1;

//Get fittest offspring

Individual getFittestOffspring() {

if (fittest.fitness > secondFittest.fitness) {

return fittest;

return secondFittest;

//Replace least fittest individual from most fittest offspring

void addFittestOffspring() {

//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() {

//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() {

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;

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;

if (individuals[i].fitness > individuals[maxFit1].fitness) {

maxFit2 = maxFit1;

} else if (individuals[i].fitness > individuals[maxFit2].fitness) {

//Get index of least fittest individual

public int getLeastFittestIndex() {

int minFit = 0;

if (minFit >= individuals[i].fitness) {

minFit = i;

return minFit;

//Calculate fitness of each individual

public void calculateFitness() {

individuals[i].calcFitness();

getFittest();

}