本文經(jīng)機(jī)器之心（微信公眾號：almosthuman2014）授權(quán)轉(zhuǎn)載，禁止二次轉(zhuǎn)載

作者：MallawaarachchiFollow

原文：https://medium.com/towards-data-science/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

機(jī)器之心編譯，參與：俞云開、蔣思源

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

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

遺傳算法的概念

自然選擇的過程從選擇群體中最適應(yīng)環(huán)境的個體開始。后代繼承了父母的特性，并且這些特性將添加到下一代中。如果父母具有更好的適應(yīng)性，那么它們的后代將更易于存活。迭代地進(jìn)行該自然選擇的過程，最終，我們將得到由最適應(yīng)環(huán)境的個體組成的一代。

這一概念可以被應(yīng)用于搜索問題中。我們考慮一個問題的諸多解決方案，并從中搜尋出最佳方案。

遺傳算法含以下五步：

初始化

個體評價（計算適應(yīng)度函數(shù)）

選擇運(yùn)算

交叉運(yùn)算

變異運(yùn)算

初始化

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

個體以一組參數(shù)（變量）為特征，這些特征被稱為基因，串聯(lián)這些基因就可以組成染色體（問題的解）。

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

種群、染色體和基因

個體評價（計算適應(yīng)度函數(shù)）

個體評價利用適應(yīng)度函數(shù)評估了該個體對環(huán)境的適應(yīng)度（與其它個體競爭的能力）。每一個體都有適應(yīng)度評分，個體被選中進(jìn)行繁殖的可能性取決于其適應(yīng)度評分。適應(yīng)度函數(shù)值越大，解的質(zhì)量就越高。適應(yīng)度函數(shù)是遺傳算法進(jìn)化的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。

選擇運(yùn)算

選擇運(yùn)算的目的是選出適應(yīng)性最好的個體，并使它們將基因傳到下一代中。基于其適應(yīng)度評分，我們選擇多對較優(yōu)個體（父母）。適應(yīng)度高的個體更易被選中繁殖，即將較優(yōu)父母的基因傳遞到下一代。

交叉運(yùn)算

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

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

父母間在交叉點之前交換基因，從而產(chǎn)生了后代。

父母間交換基因，然后產(chǎn)生的新后代被添加到種群中。

變異運(yùn)算

在某些形成的新后代中，它們的某些基因可能受到低概率變異因子的作用。這意味著二進(jìn)制位串中的某些位可能會翻轉(zhuǎn)。

變異運(yùn)算前后

變異運(yùn)算可用于保持種群內(nèi)的多樣性，并防止過早收斂。

終止

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

?

案例實現(xiàn)

種群的規(guī)模恒定。新一代形成時，適應(yīng)度最差的個體凋亡，為后代留出空間。這些階段的序列被不斷重復(fù)，以產(chǎn)生優(yōu)于先前的新一代。

這一迭代過程的偽代碼：

START Generate the?initial?population Compute?fitness REPEATSelectionCrossoverMutationCompute?fitness UNTIL?population has converged STOP

Java?中的實例實現(xiàn)

以下展示的是遺傳算法在 Java 中的示例實現(xiàn)，我們可以隨意調(diào)試和修改這些代碼。給定一組五個基因，每一個基因可以保存一個二進(jìn)制值?0?或 1。這里的適應(yīng)度是基因組中 1 的數(shù)量。如果基因組內(nèi)共有五個 1，則該個體適應(yīng)度達(dá)到最大值。

如果基因組內(nèi)沒有 1，那么個體的適應(yīng)度達(dá)到最小值。該遺傳算法希望最大化適應(yīng)度，并提供適應(yīng)度達(dá)到最大的個體所組成的群體。注意：本例中，在交叉運(yùn)算與突變運(yùn)算之后，適應(yīng)度最低的個體被新的，適應(yīng)度最高的后代所替代。

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 populationdemo.population.initializePopulation(10);//Calculate fitness of each individualdemo.population.calculateFitness();System.out.println("Generation: "?+ demo.generationCount +?" Fittest: "?+ demo.population.fittest);//While population gets an individual with maximum fitnesswhile?(demo.population.fittest <?5) {++demo.generationCount;//Do selectiondemo.selection();//Do crossoverdemo.crossover();//Do mutation under a random probabilityif?(rn.nextInt()%7?<?5) {demo.mutation();}//Add fittest offspring to populationdemo.addFittestOffspring();//Calculate new fitness valuedemo.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("");}//Selectionvoid?selection()?{//Select the most fittest individualfittest = population.getFittest();//Select the second most fittest individualsecondFittest = population.getSecondFittest();}//Crossovervoid?crossover()?{Random rn =?new?Random();//Select a random crossover pointint?crossOverPoint = rn.nextInt(population.individuals[0].geneLength);//Swap values among parentsfor?(int?i =?0; i < crossOverPoint; i++) {int?temp = fittest.genes[i];fittest.genes[i] = secondFittest.genes[i];secondFittest.genes[i] = temp;}}//Mutationvoid?mutation()?{Random rn =?new?Random();//Select a random mutation pointint?mutationPoint = rn.nextInt(population.individuals[0].geneLength);//Flip values at the mutation pointif?(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 offspringIndividual?getFittestOffspring()?{if?(fittest.fitness > secondFittest.fitness) {return?fittest;}return?secondFittest;}//Replace least fittest individual from most fittest offspringvoid?addFittestOffspring()?{//Update fitness values of offspringfittest.calcFitness();secondFittest.calcFitness();//Get index of least fit individualint?leastFittestIndex = population.getLeastFittestIndex();//Replace least fittest individual from most fittest offspringpopulation.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 individualfor?(int?i =?0; i < genes.length; i++) {genes[i] = rn.nextInt() %?2;}fitness =?0;}//Calculate fitnesspublic?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 populationpublic?void?initializePopulation(int?size)?{for?(int?i =?0; i < individuals.length; i++) {individuals[i] =?new?Individual();}}//Get the fittest individualpublic?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 individualpublic?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 individualpublic?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 individualpublic?void?calculateFitness()?{for?(int?i =?0; i < individuals.length; i++) {individuals[i].calcFitness();}getFittest();}}

總結(jié)

以上是生活随笔為你收集整理的遗传算法的基本概念和实现，附Java实现案例！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。