KYLIN-2730 Introduce genetic algorithm for cube planner Signed-off-by: Li Yang <liy...@apache.org>
Project: http://git-wip-us.apache.org/repos/asf/kylin/repo Commit: http://git-wip-us.apache.org/repos/asf/kylin/commit/7b6606ad Tree: http://git-wip-us.apache.org/repos/asf/kylin/tree/7b6606ad Diff: http://git-wip-us.apache.org/repos/asf/kylin/diff/7b6606ad Branch: refs/heads/pr70 Commit: 7b6606ad7ff6e89595c3db791a80607fe816c423 Parents: 01fe425 Author: Zhong <nju_y...@apache.org> Authored: Tue Aug 22 14:59:02 2017 +0800 Committer: Li Yang <liy...@apache.org> Committed: Sat Sep 23 18:16:48 2017 +0800 ---------------------------------------------------------------------- .../algorithm/generic/BitsChromosome.java | 133 +++++++++ .../generic/CombinedStoppingCondition.java | 43 +++ .../cuboid/algorithm/generic/CuboidEncoder.java | 44 +++ .../algorithm/generic/GeneticAlgorithm.java | 283 +++++++++++++++++++ .../generic/RouletteWheelSelection.java | 61 ++++ .../algorithm/generic/lib/BitsMutation.java | 59 ++++ .../algorithm/generic/lib/Chromosome.java | 104 +++++++ .../lib/ChromosomeMismatchException.java | 48 ++++ .../algorithm/generic/lib/ChromosomePair.java | 67 +++++ .../algorithm/generic/lib/CrossoverPolicy.java | 37 +++ .../generic/lib/ElitisticListPopulation.java | 117 ++++++++ .../cuboid/algorithm/generic/lib/Fitness.java | 33 +++ .../generic/lib/FixedGenerationCount.java | 71 +++++ .../algorithm/generic/lib/ListPopulation.java | 223 +++++++++++++++ .../algorithm/generic/lib/MutationPolicy.java | 34 +++ .../generic/lib/OnePointCrossover.java | 126 +++++++++ .../algorithm/generic/lib/Population.java | 59 ++++ .../algorithm/generic/lib/SelectionPolicy.java | 33 +++ .../generic/lib/StoppingCondition.java | 34 +++ .../generic/lib/TournamentSelection.java | 114 ++++++++ .../cuboid/algorithm/GeneticAlgorithmTest.java | 57 ++++ 21 files changed, 1780 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java new file mode 100755 index 0000000..6445ca6 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java @@ -0,0 +1,133 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic; + +import java.util.BitSet; +import java.util.List; +import java.util.Set; + +import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy; +import org.apache.kylin.cube.cuboid.algorithm.CuboidBenefitModel; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome; +import org.apache.kylin.cube.cuboid.algorithm.CuboidStats; + +import com.google.common.collect.Sets; + +public class BitsChromosome extends Chromosome { + + private BitSet key; + private int length; + private BenefitPolicy benefitPolicy; + private CuboidStats cuboidStats; + private CuboidEncoder cuboidEncoder; + private double spaceLimit; + private double spaceCost; + private double fitness = -1; + + public BitsChromosome(final BitSet key, final BenefitPolicy benefitPolicy, final CuboidStats cuboidStats, + final double spaceLimit) { + super(); + this.key = key; + this.length = cuboidStats.getAllCuboidsForSelection().size(); + this.benefitPolicy = benefitPolicy.getInstance(); + this.cuboidStats = cuboidStats; + this.cuboidEncoder = new CuboidEncoder(cuboidStats); + this.spaceLimit = spaceLimit; + initSpaceCost(); + } + + public BitsChromosome newBitsChromosome(BitSet newkey) { + return new BitsChromosome(newkey, this.benefitPolicy, this.cuboidStats, this.spaceLimit); + } + + private void initSpaceCost() { + spaceCost = 0; + List<Long> remainingCuboids = cuboidEncoder.toCuboidList(key); + for (Long cuboid : remainingCuboids) { + spaceCost += cuboidStats.getCuboidSize(cuboid); + } + } + + public BitSet getKey() { + return key; + } + + public int getLength() { + return length; + } + + public CuboidEncoder getCuboidEncoder() { + return cuboidEncoder; + } + + @Override + public double fitness() { + if (fitness == -1) { + fitness = calculateFitness(); + } + return fitness; + } + + @Override + protected boolean isSame(final Chromosome another) { + return this.equals(another); + } + + private synchronized double calculateFitness() { + List<Long> remainingCuboids = cuboidEncoder.toCuboidList(key); + Set<Long> selectedCuboidSets = Sets.newHashSet(); + selectedCuboidSets.addAll(cuboidStats.getAllCuboidsForMandatory()); + + CuboidBenefitModel.BenefitModel benefitModel = benefitPolicy.calculateBenefitTotal(remainingCuboids, selectedCuboidSets); + double totalBenefit = benefitModel.getBenefit(); + if (spaceCost > spaceLimit) { + totalBenefit = totalBenefit * spaceLimit / spaceCost; + } + return totalBenefit; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((key == null) ? 0 : key.hashCode()); + result = prime * result + length; + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + BitsChromosome other = (BitsChromosome) obj; + if (length != other.length) { + return false; + } + if (key == null) { + if (other.key != null) + return false; + } else if (!key.equals(other.key)) + return false; + return true; + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java new file mode 100755 index 0000000..bc4bb99 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java @@ -0,0 +1,43 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic; + +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.StoppingCondition; + +import java.util.List; + +public class CombinedStoppingCondition implements StoppingCondition { + private List<StoppingCondition> conditions; + + public CombinedStoppingCondition(List<StoppingCondition> conditions) { + this.conditions = conditions; + } + + @Override + public boolean isSatisfied(Population population) { + for (StoppingCondition condition : conditions) { + if (condition.isSatisfied(population)) { + return true; + } + } + return false; + } + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java new file mode 100755 index 0000000..7e48413 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic; + +import java.util.BitSet; +import java.util.Collections; +import java.util.List; + +import org.apache.kylin.cube.cuboid.algorithm.CuboidStats; + +import com.google.common.collect.Lists; + +public class CuboidEncoder { + private List<Long> selectionCuboids; + + public CuboidEncoder(CuboidStats cuboidStats) { + selectionCuboids = Lists.newArrayList(cuboidStats.getAllCuboidsForSelection()); + Collections.sort(selectionCuboids, Collections.reverseOrder()); + } + + public List<Long> toCuboidList(BitSet bits) { + List<Long> cuboids = Lists.newArrayListWithCapacity(bits.cardinality()); + for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) { + cuboids.add(selectionCuboids.get(i)); + } + return cuboids; + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java new file mode 100755 index 0000000..e2545b9 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java @@ -0,0 +1,283 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic; + +import java.util.BitSet; +import java.util.List; +import java.util.Random; + +import org.apache.kylin.cube.cuboid.algorithm.AbstractRecommendAlgorithm; +import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.BitsMutation; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ChromosomePair; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.CrossoverPolicy; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ElitisticListPopulation; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.FixedGenerationCount; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.MutationPolicy; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.OnePointCrossover; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.SelectionPolicy; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.StoppingCondition; +import org.apache.kylin.cube.cuboid.algorithm.CuboidStats; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import com.google.common.collect.Lists; + +/** + * Implementation of a genetic algorithm to recommend a list of cuboids. All factors that govern the processing + * of the algorithm can be configured. + * + */ +public class GeneticAlgorithm extends AbstractRecommendAlgorithm { + + private static final Logger logger = LoggerFactory.getLogger(GeneticAlgorithm.class); + public static ThreadLocal<Random> RANDGEN = new ThreadLocal<Random>() { + @Override + protected Random initialValue() { + return new Random(System.currentTimeMillis() * Thread.currentThread().getId()); + } + }; + /** the rate of crossover for the algorithm. */ + private final double crossoverRate = 0.9; + /** the rate of mutation for the algorithm. */ + private final double mutationRate = 0.001; + /** the init population size. */ + private final int populationSize = 500; + /** the max population size. */ + private final int maxPopulationSize = 510; + private CrossoverPolicy crossoverPolicy; + private MutationPolicy mutationPolicy; + private SelectionPolicy selectionPolicy; + private CuboidEncoder cuboidEncoder; + /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */ + private int generationsEvolved = 0; + + public GeneticAlgorithm(final long timeout, BenefitPolicy benefitPolicy, CuboidStats cuboidStats) { + super(timeout, benefitPolicy, cuboidStats); + this.crossoverPolicy = new OnePointCrossover(); + this.mutationPolicy = new BitsMutation(); + this.selectionPolicy = new RouletteWheelSelection(); + + this.cuboidEncoder = new CuboidEncoder(getCuboidStats()); + } + + @Override + public List<Long> recommend(double expansionRate) { + double spaceLimit = getCuboidStats().getBaseCuboidSize() * expansionRate; + return start(spaceLimit); + } + + @Override + public List<Long> start(double maxSpaceLimit) { + logger.info("Genetic Algorithm started."); + + getBenefitPolicy().initBeforeStart(); + + //Initial mandatory cuboids + double remainingSpace = maxSpaceLimit; + for (Long mandatoryOne : getCuboidStats().getAllCuboidsForMandatory()) { + if (getCuboidStats().getCuboidSize(mandatoryOne) != null) { + remainingSpace -= getCuboidStats().getCuboidSize(mandatoryOne); + } + } + + //Generate a population randomly + Population initial = initRandomPopulation(remainingSpace); + + //Set stopping condition + List<StoppingCondition> conditions = Lists.newArrayList(); + conditions.add(new FixedGenerationCount(550)); + CombinedStoppingCondition stopCondition = new CombinedStoppingCondition(conditions); + + //Start the evolution + Population current = evolve(initial, stopCondition); + BitsChromosome chromosome = (BitsChromosome) current.getFittestChromosome(); + logger.info("Genetic Algorithm finished."); + List<Long> finalList = Lists.newArrayList(); + finalList.addAll(getCuboidStats().getAllCuboidsForMandatory()); + finalList.addAll(cuboidEncoder.toCuboidList(chromosome.getKey())); + + double totalSpace = 0; + if (logger.isInfoEnabled()) { + for (Long cuboid : finalList) { + Double unitSpace = getCuboidStats().getCuboidSize(cuboid); + if (unitSpace != null) { + logger.info(String.format("cuboidId %d and Space: %f", cuboid, unitSpace)); + totalSpace += unitSpace; + } else { + logger.info(String.format("mandatory cuboidId %d", cuboid)); + } + } + logger.info("Total Space:" + totalSpace); + logger.info("Space Expansion Rate:" + totalSpace / getCuboidStats().getBaseCuboidSize()); + } + return finalList; + } + + protected Population initRandomPopulation(double maxSpaceLimit) { + List<Chromosome> chromosomeList = Lists.newArrayListWithCapacity(populationSize); + List<Long> cuboidsForSelection = Lists.newArrayList(getCuboidStats().getAllCuboidsForSelection()); + int selectionSize = cuboidsForSelection.size(); + + while (chromosomeList.size() < populationSize) { + BitSet bitSetForSelection = new BitSet(selectionSize); + + //Initialize selection genes + double totalSpace = 0; + while (totalSpace < maxSpaceLimit) { + int j = RANDGEN.get().nextInt(selectionSize); + if (!bitSetForSelection.get(j)) { + totalSpace += getCuboidStats().getCuboidSize(cuboidsForSelection.get(j)); + bitSetForSelection.set(j); + } + } + + Chromosome chromosome = new BitsChromosome(bitSetForSelection, getBenefitPolicy(), getCuboidStats(), + maxSpaceLimit); + chromosomeList.add(chromosome); + } + return new ElitisticListPopulation(chromosomeList, maxPopulationSize, 0.8); + } + + /** + * Evolve the given population. Evolution stops when the stopping condition + * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved} + * property with the number of generations evolved before the StoppingCondition + * is satisfied. + * + * @param initial the initial, seed population. + * @param condition the stopping condition used to stop evolution. + * @return the population that satisfies the stopping condition. + */ + protected Population evolve(final Population initial, final StoppingCondition condition) { + Population current = initial; + generationsEvolved = 0; + while (!condition.isSatisfied(current) && (!shouldCancel())) { + current = nextGeneration(current); + generationsEvolved++; + logger.info("Generations evolved count:" + generationsEvolved); + } + return current; + } + + /** + * Evolve the given population into the next generation. + * <p> + * <ol> + * <li>Get nextGeneration population to fill from <code>current</code> + * generation, using its nextGeneration method</li> + * <li>Loop until new generation is filled:</li> + * <ul><li>Apply configured SelectionPolicy to select a pair of parents + * from <code>current</code></li> + * <li>With probability = {@link #getCrossoverRate()}, apply + * configured {@link CrossoverPolicy} to parents</li> + * <li>With probability = {@link #getMutationRate()}, apply + * configured {@link MutationPolicy} to each of the offspring</li> + * <li>Add offspring individually to nextGeneration, + * space permitting</li> + * </ul> + * <li>Return nextGeneration</li> + * </ol> + * + * @param current the current population. + * @return the population for the next generation. + */ + protected Population nextGeneration(final Population current) { + Population nextGeneration = current.nextGeneration(); + + while (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { + // select parent chromosomes + ChromosomePair pair = getSelectionPolicy().select(current); + + // crossover? + if (RANDGEN.get().nextDouble() < getCrossoverRate()) { + // apply crossover policy to create two offspring + pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond()); + } + + // mutation? + if (RANDGEN.get().nextDouble() < getMutationRate()) { + // apply mutation policy to the chromosomes + pair = new ChromosomePair(getMutationPolicy().mutate(pair.getFirst()), + getMutationPolicy().mutate(pair.getSecond())); + } + + // add the first chromosome to the population + nextGeneration.addChromosome(pair.getFirst()); + // is there still a place for the second chromosome? + if (nextGeneration.getPopulationSize() < nextGeneration.getPopulationLimit()) { + // add the second chromosome to the population + nextGeneration.addChromosome(pair.getSecond()); + } + } + return nextGeneration; + } + + /** + * Returns the crossover policy. + * @return crossover policy + */ + public CrossoverPolicy getCrossoverPolicy() { + return crossoverPolicy; + } + + /** + * Returns the crossover rate. + * @return crossover rate + */ + public double getCrossoverRate() { + return crossoverRate; + } + + /** + * Returns the mutation policy. + * @return mutation policy + */ + public MutationPolicy getMutationPolicy() { + return mutationPolicy; + } + + /** + * Returns the mutation rate. + * @return mutation rate + */ + public double getMutationRate() { + return mutationRate; + } + + /** + * Returns the selection policy. + * @return selection policy + */ + public SelectionPolicy getSelectionPolicy() { + return selectionPolicy; + } + + /** + * Returns the number of generations evolved to reach {@link StoppingCondition} in the last run. + * + * @return number of generations evolved + */ + public int getGenerationsEvolved() { + return generationsEvolved; + } + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java new file mode 100755 index 0000000..db84171 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java @@ -0,0 +1,61 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic; + +import java.util.List; + +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ChromosomePair; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ListPopulation; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population; +import org.apache.kylin.cube.cuboid.algorithm.generic.lib.SelectionPolicy; + +import com.google.common.collect.Lists; + +public class RouletteWheelSelection implements SelectionPolicy { + + @Override + public ChromosomePair select(Population population) throws IllegalArgumentException { + // create a copy of the chromosome list + List<Chromosome> chromosomes = Lists.newArrayList(((ListPopulation) population).getChromosomes()); + + double maxFitness = 0; + double totalFitness = 0; + for (Chromosome o : chromosomes) { + double fitness = o.getFitness(); + totalFitness += fitness; + if (fitness > maxFitness) { + maxFitness = fitness; + } + } + return new ChromosomePair(rouletteWheel(chromosomes, totalFitness), rouletteWheel(chromosomes, totalFitness)); + } + + private Chromosome rouletteWheel(final List<Chromosome> chromosomes, final double totalFitness) { + float rnd = (float) (GeneticAlgorithm.RANDGEN.get().nextDouble() * totalFitness); + float runningScore = 0; + for (Chromosome o : chromosomes) { + if (rnd >= runningScore && rnd <= runningScore + o.getFitness()) { + return o; + } + runningScore += o.getFitness(); + } + return null; + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java new file mode 100755 index 0000000..b349eb6 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java @@ -0,0 +1,59 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import java.util.BitSet; + +import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosome; +import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm; + +/** + * Mutation for {@link BitsChromosome}s. Randomly changes one gene. + * + */ +public class BitsMutation implements MutationPolicy { + + /** + * Mutate the given chromosome. Randomly changes one gene. + * + * @param original the original chromosome. + * @return the mutated chromosome. + * @throws IllegalArgumentException if <code>original</code> is not an instance of {@link BitsChromosome}. + */ + public Chromosome mutate(Chromosome original) throws IllegalArgumentException { + if (!(original instanceof BitsChromosome)) { + throw new IllegalArgumentException("Chromosome " + original.getClass() + " must be of type BitsChromosome."); + } + + BitsChromosome origChrom = (BitsChromosome) original; + BitSet newNey = (BitSet) origChrom.getKey().clone(); + + // randomly select a gene + int geneIndex = getMutationGeneIndex(origChrom); + // change it + boolean value = newNey.get(geneIndex); + newNey.set(geneIndex, !value); + Chromosome newChrom = origChrom.newBitsChromosome(newNey); + return newChrom; + } + + protected int getMutationGeneIndex(BitsChromosome origChrom) { + return GeneticAlgorithm.RANDGEN.get().nextInt(origChrom.getLength()); + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java new file mode 100755 index 0000000..f8fa489 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java @@ -0,0 +1,104 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Individual in a population. Chromosomes are compared based on their fitness. + * <p> + * The chromosomes are IMMUTABLE, and so their fitness is also immutable and + * therefore it can be cached. + * + */ +public abstract class Chromosome implements Comparable<Chromosome>, Fitness { + /** Value assigned when no fitness has been computed yet. */ + private static final double NO_FITNESS = Double.NEGATIVE_INFINITY; + + /** Cached value of the fitness of this chromosome. */ + private double fitness = NO_FITNESS; + + /** + * Access the fitness of this chromosome. The bigger the fitness, the better the chromosome. + * <p> + * Computation of fitness is usually very time-consuming task, therefore the fitness is cached. + * + * @return the fitness + */ + public double getFitness() { + if (this.fitness == NO_FITNESS) { + // no cache - compute the fitness + this.fitness = fitness(); + } + return this.fitness; + } + + /** + * Compares two chromosomes based on their fitness. The bigger the fitness, the better the chromosome. + * + * @param another another chromosome to compare + * @return + * <ul> + * <li>-1 if <code>another</code> is better than <code>this</code></li> + * <li>1 if <code>another</code> is worse than <code>this</code></li> + * <li>0 if the two chromosomes have the same fitness</li> + * </ul> + */ + public int compareTo(final Chromosome another) { + return Double.compare(getFitness(), another.getFitness()); + } + + /** + * Returns <code>true</code> iff <code>another</code> has the same representation and therefore the same fitness. By + * default, it returns false -- override it in your implementation if you need it. + * + * @param another chromosome to compare + * @return true if <code>another</code> is equivalent to this chromosome + */ + protected boolean isSame(final Chromosome another) { + return false; + } + + /** + * Searches the <code>population</code> for another chromosome with the same representation. If such chromosome is + * found, it is returned, if no such chromosome exists, returns <code>null</code>. + * + * @param population Population to search + * @return Chromosome with the same representation, or <code>null</code> if no such chromosome exists. + */ + protected Chromosome findSameChromosome(final Population population) { + for (Chromosome anotherChr : population) { + if (this.isSame(anotherChr)) { + return anotherChr; + } + } + return null; + } + + /** + * Searches the population for a chromosome representing the same solution, and if it finds one, + * updates the fitness to its value. + * + * @param population Population to search + */ + public void searchForFitnessUpdate(final Population population) { + Chromosome sameChromosome = findSameChromosome(population); + if (sameChromosome != null) { + fitness = sameChromosome.getFitness(); + } + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java new file mode 100755 index 0000000..51d5cb3 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java @@ -0,0 +1,48 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Exception to be thrown when two Chromosomes length differ. + * + */ +public class ChromosomeMismatchException extends IllegalArgumentException { + private static final long serialVersionUID = -7483865132286153255L; + + private final int length; + + /** + * Construct an exception from the mismatched chromosomes. + * + * @param errorMsg error info. + * @param wrong Wrong length. + * @param expected Expected length. + */ + public ChromosomeMismatchException(String errorMsg, int wrong, int expected) { + super(errorMsg); + length = expected; + } + + /** + * @return the expected length. + */ + public int getLength() { + return length; + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java new file mode 100755 index 0000000..05da4b5 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java @@ -0,0 +1,67 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * A pair of {@link Chromosome} objects. + * + */ +public class ChromosomePair { + /** the first chromosome in the pair. */ + private final Chromosome first; + + /** the second chromosome in the pair. */ + private final Chromosome second; + + /** + * Create a chromosome pair. + * + * @param c1 the first chromosome. + * @param c2 the second chromosome. + */ + public ChromosomePair(final Chromosome c1, final Chromosome c2) { + super(); + first = c1; + second = c2; + } + + /** + * Access the first chromosome. + * + * @return the first chromosome. + */ + public Chromosome getFirst() { + return first; + } + + /** + * Access the second chromosome. + * + * @return the second chromosome. + */ + public Chromosome getSecond() { + return second; + } + + /** {@inheritDoc} */ + @Override + public String toString() { + return String.format("(%s,%s)", getFirst(), getSecond()); + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java new file mode 100755 index 0000000..fa287cf --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java @@ -0,0 +1,37 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Policy used to create a pair of new chromosomes by performing a crossover + * operation on a source pair of chromosomes. + * + */ +public interface CrossoverPolicy { + + /** + * Perform a crossover operation on the given chromosomes. + * + * @param first the first chromosome. + * @param second the second chromosome. + * @return the pair of new chromosomes that resulted from the crossover. + * @throws IllegalArgumentException if the given chromosomes are not compatible with this {@link CrossoverPolicy} + */ + ChromosomePair crossover(Chromosome first, Chromosome second) throws IllegalArgumentException; +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java new file mode 100755 index 0000000..f66e941 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java @@ -0,0 +1,117 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import java.util.Collections; +import java.util.List; + +import org.apache.commons.math3.exception.NotPositiveException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.exception.NumberIsTooLargeException; +import org.apache.commons.math3.exception.OutOfRangeException; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.util.FastMath; + +/** + * Population of chromosomes which uses elitism (certain percentage of the best + * chromosomes is directly copied to the next generation). + * + */ +public class ElitisticListPopulation extends ListPopulation { + + /** percentage of chromosomes copied to the next generation */ + private double elitismRate = 0.9; + + /** + * Creates a new {@link ElitisticListPopulation} instance. + * + * @param chromosomes list of chromosomes in the population + * @param populationLimit maximal size of the population + * @param elitismRate how many best chromosomes will be directly transferred to the next generation [in %] + * @throws NullArgumentException if the list of chromosomes is {@code null} + * @throws NotPositiveException if the population limit is not a positive number (< 1) + * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit + * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range + */ + public ElitisticListPopulation(final List<Chromosome> chromosomes, final int populationLimit, + final double elitismRate) + throws NullArgumentException, NotPositiveException, NumberIsTooLargeException, OutOfRangeException { + + super(chromosomes, populationLimit); + setElitismRate(elitismRate); + } + + /** + * Creates a new {@link ElitisticListPopulation} instance and initializes its inner chromosome list. + * + * @param populationLimit maximal size of the population + * @param elitismRate how many best chromosomes will be directly transferred to the next generation [in %] + * @throws NotPositiveException if the population limit is not a positive number (< 1) + * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range + */ + public ElitisticListPopulation(final int populationLimit, final double elitismRate) + throws NotPositiveException, OutOfRangeException { + + super(populationLimit); + setElitismRate(elitismRate); + } + + /** + * Start the population for the next generation. The <code>{@link #elitismRate}</code> + * percents of the best chromosomes are directly copied to the next generation. + * + * @return the beginnings of the next generation. + */ + public Population nextGeneration() { + // initialize a new generation with the same parameters + ElitisticListPopulation nextGeneration = new ElitisticListPopulation(getPopulationLimit(), getElitismRate()); + + final List<Chromosome> oldChromosomes = getChromosomeList(); + Collections.sort(oldChromosomes); + + // index of the last "not good enough" chromosome + int boundIndex = (int) FastMath.ceil((1.0 - getElitismRate()) * oldChromosomes.size()); + for (int i = boundIndex; i < oldChromosomes.size(); i++) { + nextGeneration.addChromosome(oldChromosomes.get(i)); + } + return nextGeneration; + } + + /** + * Access the elitism rate. + * @return the elitism rate + */ + public double getElitismRate() { + return this.elitismRate; + } + + /** + * Sets the elitism rate, i.e. how many best chromosomes will be directly transferred to the next generation [in %]. + * + * @param elitismRate how many best chromosomes will be directly transferred to the next generation [in %] + * @throws OutOfRangeException if the elitism rate is outside the [0, 1] range + */ + public void setElitismRate(final double elitismRate) throws OutOfRangeException { + if (elitismRate < 0 || elitismRate > 1) { + throw new OutOfRangeException(LocalizedFormats.ELITISM_RATE, elitismRate, 0, 1); + } + this.elitismRate = elitismRate; + } + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java new file mode 100755 index 0000000..83f4b65 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java @@ -0,0 +1,33 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Fitness of a chromosome. + * + */ +public interface Fitness { + + /** + * Compute the fitness. + * @return fitness + */ + double fitness(); + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java new file mode 100755 index 0000000..c0c8316 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java @@ -0,0 +1,71 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import org.apache.commons.math3.exception.NumberIsTooSmallException; + +/** + * Stops after a fixed number of generations. Each time {@link #isSatisfied(Population)} is invoked, a generation + * counter is incremented. Once the counter reaches the configured <code>maxGenerations</code> value, + * {@link #isSatisfied(Population)} returns true. + * + */ +public class FixedGenerationCount implements StoppingCondition { + /** Maximum number of generations (stopping criteria) */ + private final int maxGenerations; + /** Number of generations that have passed */ + private int numGenerations = 0; + + /** + * Create a new FixedGenerationCount instance. + * + * @param maxGenerations number of generations to evolve + * @throws NumberIsTooSmallException if the number of generations is < 1 + */ + public FixedGenerationCount(final int maxGenerations) throws NumberIsTooSmallException { + if (maxGenerations <= 0) { + throw new NumberIsTooSmallException(maxGenerations, 1, true); + } + this.maxGenerations = maxGenerations; + } + + /** + * Determine whether or not the given number of generations have passed. Increments the number of generations + * counter if the maximum has not been reached. + * + * @param population ignored (no impact on result) + * @return <code>true</code> IFF the maximum number of generations has been exceeded + */ + public boolean isSatisfied(final Population population) { + if (this.numGenerations < this.maxGenerations) { + numGenerations++; + return false; + } + return true; + } + + /** + * Returns the number of generations that have already passed. + * @return the number of generations that have passed + */ + public int getNumGenerations() { + return numGenerations; + } + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java new file mode 100755 index 0000000..c146274 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java @@ -0,0 +1,223 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; + +import org.apache.commons.math3.exception.NotPositiveException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.exception.NumberIsTooLargeException; +import org.apache.commons.math3.exception.NumberIsTooSmallException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +/** + * Population of chromosomes represented by a {@link List}. + * + */ +public abstract class ListPopulation implements Population { + + /** List of chromosomes */ + private List<Chromosome> chromosomes; + + /** maximal size of the population */ + private int populationLimit; + + /** + * Creates a new ListPopulation instance and initializes its inner chromosome list. + * + * @param populationLimit maximal size of the population + * @throws NotPositiveException if the population limit is not a positive number (< 1) + */ + public ListPopulation(final int populationLimit) throws NotPositiveException { + this(Collections.<Chromosome> emptyList(), populationLimit); + } + + /** + * Creates a new ListPopulation instance. + * <p> + * Note: the chromosomes of the specified list are added to the population. + * + * @param chromosomes list of chromosomes to be added to the population + * @param populationLimit maximal size of the population + * @throws NullArgumentException if the list of chromosomes is {@code null} + * @throws NotPositiveException if the population limit is not a positive number (< 1) + * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit + */ + public ListPopulation(final List<Chromosome> chromosomes, final int populationLimit) + throws NullArgumentException, NotPositiveException, NumberIsTooLargeException { + + if (chromosomes == null) { + throw new NullArgumentException(); + } + if (populationLimit <= 0) { + throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); + } + if (chromosomes.size() > populationLimit) { + throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, + chromosomes.size(), populationLimit, false); + } + this.populationLimit = populationLimit; + this.chromosomes = new ArrayList<Chromosome>(populationLimit); + this.chromosomes.addAll(chromosomes); + } + + /** + * Add a {@link Collection} of chromosomes to this {@link Population}. + * @param chromosomeColl a {@link Collection} of chromosomes + * @throws NumberIsTooLargeException if the population would exceed the population limit when + * adding this chromosome + * @since 3.1 + */ + public void addChromosomes(final Collection<Chromosome> chromosomeColl) throws NumberIsTooLargeException { + if (chromosomes.size() + chromosomeColl.size() > populationLimit) { + throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, + chromosomes.size(), populationLimit, false); + } + this.chromosomes.addAll(chromosomeColl); + } + + /** + * Returns an unmodifiable list of the chromosomes in this population. + * @return the unmodifiable list of chromosomes + */ + public List<Chromosome> getChromosomes() { + return Collections.unmodifiableList(chromosomes); + } + + /** + * Sets the list of chromosomes. + * <p> + * Note: this method removes all existing chromosomes in the population and adds all chromosomes + * of the specified list to the population. + * + * @param chromosomes the list of chromosomes + * @throws NullArgumentException if the list of chromosomes is {@code null} + * @throws NumberIsTooLargeException if the list of chromosomes exceeds the population limit + * @deprecated use {@link #addChromosomes(Collection)} instead + */ + @Deprecated + public void setChromosomes(final List<Chromosome> chromosomes) + throws NullArgumentException, NumberIsTooLargeException { + + if (chromosomes == null) { + throw new NullArgumentException(); + } + if (chromosomes.size() > populationLimit) { + throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, + chromosomes.size(), populationLimit, false); + } + this.chromosomes.clear(); + this.chromosomes.addAll(chromosomes); + } + + /** + * Access the list of chromosomes. + * @return the list of chromosomes + * @since 3.1 + */ + protected List<Chromosome> getChromosomeList() { + return chromosomes; + } + + /** + * Add the given chromosome to the population. + * + * @param chromosome the chromosome to add. + * @throws NumberIsTooLargeException if the population would exceed the {@code populationLimit} after + * adding this chromosome + */ + public void addChromosome(final Chromosome chromosome) throws NumberIsTooLargeException { + if (chromosomes.size() >= populationLimit) { + throw new NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE, + chromosomes.size(), populationLimit, false); + } + this.chromosomes.add(chromosome); + } + + /** + * Access the fittest chromosome in this population. + * @return the fittest chromosome. + */ + public Chromosome getFittestChromosome() { + // best so far + Chromosome bestChromosome = this.chromosomes.get(0); + for (Chromosome chromosome : this.chromosomes) { + if (chromosome.compareTo(bestChromosome) > 0) { + // better chromosome found + bestChromosome = chromosome; + } + } + return bestChromosome; + } + + /** + * Access the maximum population size. + * @return the maximum population size. + */ + public int getPopulationLimit() { + return this.populationLimit; + } + + /** + * Sets the maximal population size. + * @param populationLimit maximal population size. + * @throws NotPositiveException if the population limit is not a positive number (< 1) + * @throws NumberIsTooSmallException if the new population size is smaller than the current number + * of chromosomes in the population + */ + public void setPopulationLimit(final int populationLimit) throws NotPositiveException, NumberIsTooSmallException { + if (populationLimit <= 0) { + throw new NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE, populationLimit); + } + if (populationLimit < chromosomes.size()) { + throw new NumberIsTooSmallException(populationLimit, chromosomes.size(), true); + } + this.populationLimit = populationLimit; + } + + /** + * Access the current population size. + * @return the current population size. + */ + public int getPopulationSize() { + return this.chromosomes.size(); + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return this.chromosomes.toString(); + } + + /** + * Returns an iterator over the unmodifiable list of chromosomes. + * <p>Any call to {@link Iterator#remove()} will result in a {@link UnsupportedOperationException}.</p> + * + * @return chromosome iterator + */ + public Iterator<Chromosome> iterator() { + return getChromosomes().iterator(); + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java new file mode 100755 index 0000000..99ba876 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java @@ -0,0 +1,34 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Algorithm used to mutate a chromosome. + * + */ +public interface MutationPolicy { + + /** + * Mutate the given chromosome. + * @param original the original chromosome. + * @return the mutated chromosome. + * @throws IllegalArgumentException if the given chromosome is not compatible with this {@link MutationPolicy} + */ + Chromosome mutate(Chromosome original) throws IllegalArgumentException; +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java new file mode 100755 index 0000000..1f484cb --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java @@ -0,0 +1,126 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import java.util.BitSet; + +import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosome; +import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm; + +/** + * One point crossover policy. A random crossover point is selected and the + * first part from each parent is copied to the corresponding child, and the + * second parts are copied crosswise. + * + * Example: + * <pre> + * -C- denotes a crossover point + * -C- -C- + * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1) + * \------------/ \-----/ \------------/ \-----/ + * || (*) || (**) + * VV (**) VV (*) + * /------------\ /-----\ /------------\ /-----\ + * c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1) + * </pre> + * + * This policy works only on {@link BitsChromosome}, and therefore it + * is parameterized by T. Moreover, the chromosomes must have same lengths. + * + * + */ +public class OnePointCrossover implements CrossoverPolicy { + + /** + * Performs one point crossover. A random crossover point is selected and the + * first part from each parent is copied to the corresponding child, and the + * second parts are copied crosswise. + * + * Example: + * <pre> + * -C- denotes a crossover point + * -C- -C- + * p1 = (1 0 1 0 0 1 | 0 1 1) X p2 = (0 1 1 0 1 0 | 1 1 1) + * \------------/ \-----/ \------------/ \-----/ + * || (*) || (**) + * VV (**) VV (*) + * /------------\ /-----\ /------------\ /-----\ + * c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1) + * </pre> + * + * @param first first parent (p1) + * @param second second parent (p2) + * @return pair of two children (c1,c2) + * @throws IllegalArgumentException if one of the chromosomes is + * not an instance of {@link BitsChromosome} + * @throws ChromosomeMismatchException if the length of the two chromosomes is different + */ + @SuppressWarnings("unchecked") // OK because of instanceof checks + public ChromosomePair crossover(final Chromosome first, final Chromosome second) + throws IllegalArgumentException, ChromosomeMismatchException { + + if (!(first instanceof BitsChromosome && second instanceof BitsChromosome)) { + throw new IllegalArgumentException("Chromosome first " + first.getClass() + " and second " + + second.getClass() + " must be of type BitsChromosome."); + } + return crossover((BitsChromosome) first, (BitsChromosome) second); + } + + /** + * 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 ChromosomeMismatchException if the length of the two chromosomes is different + */ + private ChromosomePair crossover(final BitsChromosome first, final BitsChromosome second) + throws ChromosomeMismatchException { + final int length = first.getLength(); + if (length != second.getLength()) { + throw new ChromosomeMismatchException("BitsChromosome length mismatch.", second.getLength(), length); + } + + final BitSet parent1Key = first.getKey(); + final BitSet parent2Key = second.getKey(); + + final BitSet child1Key = new BitSet(length); + final BitSet child2Key = new BitSet(length); + + // select a crossover point at random (0 and length makes no sense) + final int crossoverIndex = 1 + (GeneticAlgorithm.RANDGEN.get().nextInt(length - 2)); + + BitSet a = (BitSet) parent1Key.clone(); + a.clear(crossoverIndex, length); + BitSet b = (BitSet) parent2Key.clone(); + b.clear(0, crossoverIndex); + + BitSet c = (BitSet) parent1Key.clone(); + c.clear(crossoverIndex, length); + BitSet d = (BitSet) parent2Key.clone(); + d.clear(0, crossoverIndex); + + child1Key.or(a); + child1Key.or(d); + + child2Key.or(c); + child2Key.or(b); + return new ChromosomePair(first.newBitsChromosome(child1Key), second.newBitsChromosome(child2Key)); + } +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java new file mode 100755 index 0000000..8e35420 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java @@ -0,0 +1,59 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import org.apache.commons.math3.exception.NumberIsTooLargeException; + +/** + * A collection of chromosomes that facilitates generational evolution. + * + */ +public interface Population extends Iterable<Chromosome> { + /** + * Access the current population size. + * @return the current population size. + */ + int getPopulationSize(); + + /** + * Access the maximum population size. + * @return the maximum population size. + */ + int getPopulationLimit(); + + /** + * Start the population for the next generation. + * @return the beginnings of the next generation. + */ + Population nextGeneration(); + + /** + * Add the given chromosome to the population. + * @param chromosome the chromosome to add. + * @throws NumberIsTooLargeException if the population would exceed the population limit when adding + * this chromosome + */ + void addChromosome(Chromosome chromosome) throws NumberIsTooLargeException; + + /** + * Access the fittest chromosome in this population. + * @return the fittest chromosome. + */ + Chromosome getFittestChromosome(); +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java new file mode 100755 index 0000000..1c32f88 --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java @@ -0,0 +1,33 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Algorithm used to select a chromosome pair from a population. + * + */ +public interface SelectionPolicy { + /** + * Select two chromosomes from the population. + * @param population the population from which the chromosomes are choosen. + * @return the selected chromosomes. + * @throws IllegalArgumentException if the population is not compatible with this {@link SelectionPolicy} + */ + ChromosomePair select(Population population) throws IllegalArgumentException; +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java new file mode 100755 index 0000000..28b879a --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java @@ -0,0 +1,34 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +/** + * Algorithm used to determine when to stop evolution. + * + */ +public interface StoppingCondition { + /** + * Determine whether or not the given population satisfies the stopping condition. + * + * @param population the population to test. + * @return <code>true</code> if this stopping condition is met by the given population, + * <code>false</code> otherwise. + */ + boolean isSatisfied(Population population); +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java ---------------------------------------------------------------------- diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java new file mode 100755 index 0000000..cca44ca --- /dev/null +++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java @@ -0,0 +1,114 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm.generic.lib; + +import java.util.List; + +import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm; + +import com.google.common.collect.Lists; + +/** + * Tournament selection scheme. Each of the two selected chromosomes is selected + * based on n-ary tournament -- this is done by drawing {@link #arity} random + * chromosomes without replacement from the population, and then selecting the + * fittest chromosome among them. + * + */ +public class TournamentSelection implements SelectionPolicy { + + /** number of chromosomes included in the tournament selections */ + private int arity; + + /** + * Creates a new TournamentSelection instance. + * + * @param arity how many chromosomes will be drawn to the tournament + */ + public TournamentSelection(final int arity) { + this.arity = arity; + } + + /** + * Select two chromosomes from the population. Each of the two selected + * chromosomes is selected based on n-ary tournament -- this is done by + * drawing {@link #arity} random chromosomes without replacement from the + * population, and then selecting the fittest chromosome among them. + * + * @param population the population from which the chromosomes are chosen. + * @return the selected chromosomes. + * @throws IllegalArgumentException if the tournament arity is bigger than the population size + */ + public ChromosomePair select(final Population population) throws IllegalArgumentException { + return new ChromosomePair(tournament((ListPopulation) population), tournament((ListPopulation) population)); + } + + /** + * Helper for {@link #select(Population)}. Draw {@link #arity} random chromosomes without replacement from the + * population, and then select the fittest chromosome among them. + * + * @param population the population from which the chromosomes are chosen. + * @return the selected chromosome. + * @throws IllegalArgumentException if the tournament arity is bigger than the population size + */ + private Chromosome tournament(final ListPopulation population) throws IllegalArgumentException { + if (population.getPopulationSize() < this.arity) { + throw new IllegalArgumentException("Tournament arty is too large."); + } + // 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 = Lists.newArrayList(population.getChromosomes()); + for (int i = 0; i < this.arity; i++) { + // select a random individual and add it to the tournament + int rind = GeneticAlgorithm.RANDGEN.get().nextInt(chromosomes.size()); + tournamentPopulation.addChromosome(chromosomes.get(rind)); + // do not select it again + chromosomes.remove(rind); + } + // the winner takes it all + return tournamentPopulation.getFittestChromosome(); + } + + /** + * Gets the arity (number of chromosomes drawn to the tournament). + * + * @return arity of the tournament + */ + public int getArity() { + return arity; + } + + /** + * Sets the arity (number of chromosomes drawn to the tournament). + * + * @param arity arity of the tournament + */ + public void setArity(final int arity) { + this.arity = arity; + } + +} http://git-wip-us.apache.org/repos/asf/kylin/blob/7b6606ad/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GeneticAlgorithmTest.java ---------------------------------------------------------------------- diff --git a/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GeneticAlgorithmTest.java b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GeneticAlgorithmTest.java new file mode 100755 index 0000000..4cefbd4 --- /dev/null +++ b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GeneticAlgorithmTest.java @@ -0,0 +1,57 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +package org.apache.kylin.cube.cuboid.algorithm; + +import java.util.List; + +import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm; +import org.junit.Test; + +public class GeneticAlgorithmTest extends AlgorithmTestBase { + + @Test + public void testBPUSCalculator() { + BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats); + GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats); + + List<Long> recommendList = algorithm.recommend(10); + System.out.println("recommendList by BPUSCalculator: " + recommendList); + System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats, recommendList)); + } + + @Test + public void testPBPUSCalculator() { + BenefitPolicy benefitPolicy = new PBPUSCalculator(cuboidStats); + GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats); + + List<Long> recommendList = algorithm.recommend(10); + System.out.println("recommendList by PBPUSCalculator:" + recommendList); + System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats, recommendList)); + } + + @Test + public void testSPBPUSCalculator() { + BenefitPolicy benefitPolicy = new SPBPUSCalculator(cuboidStats); + GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats); + + List<Long> recommendList = algorithm.recommend(10); + System.out.println("recommendList by SPBPUSCalculator:" + recommendList); + System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats, recommendList)); + } +}
