基于Apache math3 的遗传算法计算复杂函数在定义域内的最值（一）

遗传算法（英语：genetic algorithm (GA) ）是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。

遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。                                               --引自维基百科

遗传算法可计算复杂函数的最大值（最小值），遗传算法在Python,Matlab中应用较多,在java中的实现比较少，在Apahce Commons Math3 有一个专门的genetic包用来实现遗传算法。主要接口与类如下

假设需要优化的函数为：f(x1,x2) =x1*x1+x2*x2; x1,与x2的取值范围为[0,4],x1,x2的一个随机取值为（1.2,1.5）。 将函数的每个解用二进制表示。为了支持在double范围类的解，我这里采用double的二进制表示基因，长度为64位，如解基因表现为：

x1:0011111111110011001100110011001100110011001100110011001100110011

x2:0011111111111000000000000000000000000000000000000000000000000000

此时一个基因为表现为：00111111111100110011001100110011001100110011001100110011001100110011111111111000000000000000000000000000000000000000000000000000，

接下来通过选择，交叉，突变选择下一代

1：选择（TournamentSelection） 源码如下

public ChromosomePair select(final Population population) throws MathIllegalArgumentException {
    return new ChromosomePair(tournament((ListPopulation) population),
                              tournament((ListPopulation) population));
}

private Chromosome tournament(final ListPopulation population) throws MathIllegalArgumentException {
    if (population.getPopulationSize() < this.arity) {
        throw new MathIllegalArgumentException(LocalizedFormats.TOO_LARGE_TOURNAMENT_ARITY,
                                               arity, population.getPopulationSize());
    }
    // auxiliary population
    ListPopulation tournamentPopulation = new ListPopulation(this.arity) {
        /** {@inheritDoc} */
        public Population nextGeneration() {
            // not useful here
            return null;
        }
    };

    // create a copy of the chromosome list
    List<Chromosome> chromosomes = new ArrayList<Chromosome> (population.getChromosomes());
    for (int i=0; i<this.arity; i++) {
        // select a random individual and add it to the tournament
        int rind = GeneticAlgorithm.getRandomGenerator().nextInt(chromosomes.size());
        tournamentPopulation.addChromosome(chromosomes.get(rind));
        // do not select it again
        chromosomes.remove(rind);
    }
    // the winner takes it all
    return tournamentPopulation.getFittestChromosome();
}

tournamentPopulation.getFittestChromosome()方法 通过 compareTo方法比较将函数大的选择

public int compareTo(final Chromosome another) {
    return Double.compare(getFitness(), another.getFitness());
}

2.交叉 

这里选择两点交叉，（NPointCrossover）

/**
 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
 *
 * @param first the first chromosome
 * @param second the second chromosome
 * @return the pair of new chromosomes that resulted from the crossover
 * @throws DimensionMismatchException if the length of the two chromosomes is different
 * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes
 */
private ChromosomePair mate(final AbstractListChromosome<T> first,
                            final AbstractListChromosome<T> second)
    throws DimensionMismatchException, NumberIsTooLargeException {

    final int length = first.getLength();
    if (length != second.getLength()) {
        throw new DimensionMismatchException(second.getLength(), length);
    }
    if (crossoverPoints >= length) {
        throw new NumberIsTooLargeException(crossoverPoints, length, false);
    }

    // array representations of the parents
    final List<T> parent1Rep = first.getRepresentation();
    final List<T> parent2Rep = second.getRepresentation();
    // and of the children
    final List<T> child1Rep = new ArrayList<T>(length);
    final List<T> child2Rep = new ArrayList<T>(length);

    final RandomGenerator random = GeneticAlgorithm.getRandomGenerator();

    List<T> c1 = child1Rep;
    List<T> c2 = child2Rep;

    int remainingPoints = crossoverPoints;
    int lastIndex = 0;
    for (int i = 0; i < crossoverPoints; i++, remainingPoints--) {
        // select the next crossover point at random
        final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints);

        // copy the current segment
        for (int j = lastIndex; j < crossoverIndex; j++) {
            c1.add(parent1Rep.get(j));
            c2.add(parent2Rep.get(j));
        }

        // swap the children for the next segment
        List<T> tmp = c1;
        c1 = c2;
        c2 = tmp;

        lastIndex = crossoverIndex;
    }

    // copy the last segment
    for (int j = lastIndex; j < length; j++) {
        c1.add(parent1Rep.get(j));
        c2.add(parent2Rep.get(j));
    }

    return new ChromosomePair(first.newFixedLengthChromosome(child1Rep),
                              second.newFixedLengthChromosome(child2Rep));
}

第一个交叉点11，25

x1:00111111111100110011001100110011001100110011001100110011001100110011111111111000000000000000000000000000000000000000000000000000

x2:00111111111100110011001100110011001100110011001100110011001100110011111111111000000000000000000000000000000000000000000000000000

3.突变

/**
 * Mutate the given chromosome. Randomly changes one gene.
 *
 * @param original the original chromosome.
 * @return the mutated chromosome.
 * @throws MathIllegalArgumentException if <code>original</code> is not an instance of {@link BinaryChromosome}.
 */
public Chromosome mutate(Chromosome original) throws MathIllegalArgumentException {
    if (!(original instanceof BinaryChromosome)) {
        throw new MathIllegalArgumentException(LocalizedFormats.INVALID_BINARY_CHROMOSOME);
    }

    BinaryChromosome origChrom = (BinaryChromosome) original;
    List<Integer> newRepr = new ArrayList<Integer>(origChrom.getRepresentation());

    // randomly select a gene
    int geneIndex = GeneticAlgorithm.getRandomGenerator().nextInt(origChrom.getLength());
    // and change it
    newRepr.set(geneIndex, origChrom.getRepresentation().get(geneIndex) == 0 ? 1 : 0);

    Chromosome newChrom = tuorigChrom.newFixedLengthChromosome(newRepr);
    return newChrom;
}

随机选择基因中以为将0变为1，1变为0. 作为下一代

gene1:00111111111100110011001100110011001100110011001100110011001100110011111111111000000000000000000000000000000000000000000000000001 (1.2,2.670088630208644E-308)

gene2:00111111111100110011001100110011001100110011001100110011001101110011111111111000000000000000000000000000000000000000000000000000 (3.337610787760802E-308,1.5)

下一篇中将用具体的代码实现。