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

自然選擇的概念

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

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

遺傳算法含以下五步：

1. 初始化
2. 個(gè)體評(píng)價(jià)（計(jì)算適應(yīng)度函數(shù)）
3. 選擇運(yùn)算
4. 交叉運(yùn)算
5. 變異運(yùn)算

初始化

該過(guò)程從種群的一組個(gè)體開始，且每一個(gè)體都是待解決問(wèn)題的一個(gè)候選解。

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

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

種群、染色體和基因

個(gè)體評(píng)價(jià)（計(jì)算適應(yīng)度函數(shù)）

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

選擇運(yùn)算

選擇運(yùn)算的目的是選出適應(yīng)性***的個(gè)體，并使它們將基因傳到下一代中?；谄溥m應(yīng)度評(píng)分，我們選擇多對(duì)較優(yōu)個(gè)體（父母）。適應(yīng)度高的個(gè)體更易被選中繁殖，即將較優(yōu)父母的基因傳遞到下一代。

交叉運(yùn)算

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

舉個(gè)例子，下圖的交叉點(diǎn)為 3。

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

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

變異運(yùn)算

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

變異運(yùn)算前后

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

終止

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

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

這一迭代過(guò)程的偽代碼：

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

Java 中的示例實(shí)現(xiàn)

以下展示的是遺傳算法在 Java 中的示例實(shí)現(xiàn)，我們可以隨意調(diào)試和修改這些代碼。給定一組五個(gè)基因，每一個(gè)基因可以保存一個(gè)二進(jìn)制值 0 或 1。這里的適應(yīng)度是基因組中 1 的數(shù)量。如果基因組內(nèi)共有五個(gè) 1，則該個(gè)體適應(yīng)度達(dá)到***值。如果基因組內(nèi)沒(méi)有 1，那么個(gè)體的適應(yīng)度達(dá)到最小值。該遺傳算法希望***化適應(yīng)度，并提供適應(yīng)度達(dá)到***的個(gè)體所組成的群體。注意：本例中，在交叉運(yùn)算與突變運(yùn)算之后，適應(yīng)度***的個(gè)體被新的，適應(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 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() {
        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
    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() {
        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();
    }

}