kylin-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nju_y...@apache.org
Subject [4/5] kylin git commit: APACHE-KYLIN-2730: Introduce genetic algorithm for cube planner
Date Tue, 22 Aug 2017 10:28:04 GMT
APACHE-KYLIN-2730: Introduce genetic algorithm for cube planner


Project: http://git-wip-us.apache.org/repos/asf/kylin/repo
Commit: http://git-wip-us.apache.org/repos/asf/kylin/commit/697f848b
Tree: http://git-wip-us.apache.org/repos/asf/kylin/tree/697f848b
Diff: http://git-wip-us.apache.org/repos/asf/kylin/diff/697f848b

Branch: refs/heads/yaho-cube-planner
Commit: 697f848b0eb82318114778062f196ea1e4c29b30
Parents: 913e975
Author: Zhong <nju_yaho@apache.org>
Authored: Tue Aug 22 14:59:02 2017 +0800
Committer: Zhong <nju_yaho@apache.org>
Committed: Tue Aug 22 14:59:02 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          | 125 ++++++++
 .../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, 1779 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kylin/blob/697f848b/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/697f848b/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/697f848b/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/697f848b/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/697f848b/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/697f848b/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..d9d13c1
--- /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 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/697f848b/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/697f848b/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/697f848b/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/697f848b/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/697f848b/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 (&lt; 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 (&lt; 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/697f848b/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..4388e12
--- /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/697f848b/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 &lt; 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/697f848b/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 (&lt; 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 (&lt; 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 (&lt; 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/697f848b/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/697f848b/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..02617b8
--- /dev/null
+++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java
@@ -0,0 +1,125 @@
+/*
+ * 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 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/697f848b/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/697f848b/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/697f848b/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/697f848b/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/697f848b/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));
+    }
+}


Mime
View raw message