基于Apache math3 的遗传算法计算复杂函数在定义域内的最值(一)
今天是:
我需要三件东西:爱情友谊和图书。然而这三者之间何其相通!炽热的爱情可以充实图书的内容,图书又是人们最忠实的朋友。
User Image 基于Apache math3 的遗传算法计算复杂函数在定义域内的最值(一) 2020-01-12

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

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

 

 

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

Interface Summary 
Interface Description
CrossoverPolicy

交叉策略.

Fitness

适应度

MutationPolicy

突变策略.

PermutationChromosome<T>

染色器排列.

Population

人口

SelectionPolicy 选择策略
StoppingCondition

算法的停止条件.

Class Summary 
Class Description
AbstractListChromosome<T> 由固定长度的不可变列表表示的染色体。
BinaryChromosome

二进制表示的染色体

BinaryMutation

二进制突变

Chromosome

染色体

ChromosomePair

染色体对

CycleCrossover<T> 周期交叉[CX]通过识别两个亲本染色体之间的周期,从有序的染色体中产生后代。
ElitisticListPopulation 利用精英主义的染色体种群(一定比例的最好的染色体被直接复制到下一代)。
FixedElapsedTime 在经过一定时间后停止。
FixedGenerationCount 在固定的代数之后停止。
GeneticAlgorithm

GA实现

ListPopulation 由一个列表表示的染色体群。
NPointCrossover<T>

多点交叉

OnePointCrossover<T>

单点交叉

OrderedCrossover<T>

Order 1交叉【OX1】通过从一个亲本中复制一个连续的切片,

并在另一个亲本的剩余基因出现时将其填满,从而从有序的染色体中产生后代。

RandomKey<T> 随机密钥染色体用于排列表示。
RandomKeyMutation

随机秘钥突变

TournamentSelection

锦标赛选择方案。

UniformCrossover<T> 对指定的染色体执行一致交叉[UX]。

 

 

 

 

 

 

 

 

 

 

 

 

 

假设需要优化的函数为: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)

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

 

分享到:

我的

类型标签

外部链接

网站访问总量