You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ch...@apache.org on 2018/05/08 13:46:45 UTC
ignite git commit: IGNITE-8041: Add a GA Grid example that solves
'Knapsack Problem'
Repository: ignite
Updated Branches:
refs/heads/master e8b846b3f -> 297df324d
IGNITE-8041: Add a GA Grid example that solves 'Knapsack Problem'
This closes #3947
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/297df324
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/297df324
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/297df324
Branch: refs/heads/master
Commit: 297df324d27e3904545bef880aaa4b35b7d0fe5c
Parents: e8b846b
Author: Turik Campbell <ad...@techbysample.com>
Authored: Tue May 8 16:46:37 2018 +0300
Committer: Yury Babak <yb...@gridgain.com>
Committed: Tue May 8 16:46:37 2018 +0300
----------------------------------------------------------------------
.../examples/ml/genetic/knapsack/Item.java | 90 +++++
.../knapsack/KnapsackFitnessFunction.java | 69 ++++
.../ml/genetic/knapsack/KnapsackGAExample.java | 325 +++++++++++++++++++
.../knapsack/KnapsackTerminateCriteria.java | 100 ++++++
4 files changed, 584 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/ignite/blob/297df324/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/Item.java
----------------------------------------------------------------------
diff --git a/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/Item.java b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/Item.java
new file mode 100644
index 0000000..f64cb17
--- /dev/null
+++ b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/Item.java
@@ -0,0 +1,90 @@
+/*
+ * 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.ignite.examples.ml.genetic.knapsack;
+
+import java.io.Serializable;
+
+/**
+ * POJO to model an Item
+ */
+public class Item implements Serializable {
+ /** weight of item in lbs. */
+ private double weight;
+ /** value of item */
+ private double value;
+ /** name of item */
+ private String name;
+
+ /**
+ * Get the weight
+ *
+ * @return Weight
+ */
+ public double getWeight() {
+ return weight;
+ }
+
+ /**
+ * Set the weight
+ *
+ * @param weight Weight
+ */
+ public void setWeight(double weight) {
+ this.weight = weight;
+ }
+
+ /**
+ * Get the value
+ *
+ * @return Value
+ */
+ public double getValue() {
+ return value;
+ }
+
+ /**
+ * @param value Value
+ */
+ public void setValue(double value) {
+ this.value = value;
+ }
+
+ /**
+ * Get the name
+ *
+ * @return Name
+ */
+ public String getName() {
+ return name;
+ }
+
+ /**
+ * Set the name
+ *
+ * @param name Name
+ */
+ public void setName(String name) {
+ this.name = name;
+ }
+
+ /** {@inheritDoc} */
+ @Override public String toString() {
+ return "Item [weight=" + weight + ", value=" + value + ", name=" + name + "]";
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/297df324/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackFitnessFunction.java
----------------------------------------------------------------------
diff --git a/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackFitnessFunction.java b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackFitnessFunction.java
new file mode 100644
index 0000000..5ccaa8b
--- /dev/null
+++ b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackFitnessFunction.java
@@ -0,0 +1,69 @@
+/*
+ * 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.ignite.examples.ml.genetic.knapsack;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.apache.ignite.ml.genetic.Gene;
+import org.apache.ignite.ml.genetic.IFitnessFunction;
+
+/**
+ * This example demonstrates how to create a IFitnessFunction
+ *
+ * Your IFitnessFunction will vary depending on your particular use case.
+ *
+ * For this fitness function, we simply want to calculate the weight and value of
+ *
+ * an individual solution relative to other solutions.
+ *
+ *
+ * To do this, we total the weights and values of all the genes within a chromosome.
+ */
+public class KnapsackFitnessFunction implements IFitnessFunction {
+ /** weight capacity of knapsack */
+ private double maximumWeight = 20;
+
+ /**
+ * Calculate fitness
+ *
+ * @param genes List of Genes
+ * @return Fitness value
+ */
+ public double evaluate(List<Gene> genes) {
+
+ double value = 0;
+ double weight = 0;
+
+ List<Long> dups = new ArrayList<Long>();
+ int badSolution = 1;
+
+ for (Gene agene : genes) {
+ weight = weight + ((Item)(agene.getValue())).getWeight();
+ value = value + ((Item)(agene.getValue())).getValue();
+
+ if (dups.contains(agene.id()) || (weight > maximumWeight)) {
+ badSolution = 0;
+ break;
+ }
+ else
+ dups.add(agene.id());
+ }
+
+ return (value * badSolution);
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/297df324/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackGAExample.java
----------------------------------------------------------------------
diff --git a/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackGAExample.java b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackGAExample.java
new file mode 100644
index 0000000..0029a9e
--- /dev/null
+++ b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackGAExample.java
@@ -0,0 +1,325 @@
+/*
+ * 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.ignite.examples.ml.genetic.knapsack;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.ignite.Ignite;
+import org.apache.ignite.Ignition;
+
+import org.apache.ignite.ml.genetic.GAGrid;
+import org.apache.ignite.ml.genetic.Gene;
+import org.apache.ignite.ml.genetic.parameter.GAConfiguration;
+
+/**
+ * This example demonstrates how to use the GAGrid framework.
+ *
+ * Example demonstrates Knapsack Problem: Given a set of 30 items, each with a weight and a value, pack 10 items in
+ * knapsack so that the total weight is less <= 20 lbs. and the total value is maximized.
+ *
+ *
+ * How To Run:
+ *
+ * mvn exec:java -Dexec.mainClass="org.apache.ignite.examples.ml.genetic.knapsack.KnapsackGAExample"
+ *
+ * <p> Remote nodes should always be started with special configuration file which enables P2P class loading: {@code
+ * 'ignite.{sh|bat} examples/config/example-ignite.xml'}.</p> <p> Alternatively you can run ExampleNodeStartup in
+ * another JVM which will start node with {@code examples/config/example-ignite.xml} configuration.</p>
+ */
+public class KnapsackGAExample {
+ /** Ignite instance */
+ private static Ignite ignite = null;
+ /** GAGrid */
+ private static GAGrid gaGrid = null;
+ /** GAConfiguration */
+ private static GAConfiguration gaConfig = null;
+
+ /**
+ * @param args Command line arguments, none required.
+ */
+ public static void main(String args[]) {
+ System.setProperty("IGNITE_QUIET", "false");
+
+ try {
+
+ //Create an Ignite instance as you would in any other use case.
+ ignite = Ignition.start("examples/config/example-ignite.xml");
+
+ // Create GAConfiguration
+ gaConfig = new GAConfiguration();
+
+ // set Gene Pool
+ List<Gene> genes = getGenePool();
+
+ // set the Chromosome Length to '10' since our knapsack may contain a total of 10 items.
+ gaConfig.setChromosomeLength(10);
+
+ // initialize gene pool
+ gaConfig.setGenePool(genes);
+
+ // create and set Fitness function
+ KnapsackFitnessFunction function = new KnapsackFitnessFunction();
+ gaConfig.setFitnessFunction(function);
+
+ // create and set TerminateCriteria
+ KnapsackTerminateCriteria termCriteria = new KnapsackTerminateCriteria(ignite);
+ gaConfig.setTerminateCriteria(termCriteria);
+
+ ignite.log();
+
+ gaGrid = new GAGrid(gaConfig, ignite);
+ // evolve the population
+ gaGrid.evolve();
+
+ Ignition.stop(true);
+
+ ignite = null;
+
+ }
+ catch (Exception e) {
+ System.out.println(e);
+ }
+
+ }
+
+ /**
+ * Helper routine to initialize Gene pool
+ *
+ * In typical usecase genes may be stored in database.
+ *
+ * @return List<Gene>
+ */
+ private static List<Gene> getGenePool() {
+ List<Gene> list = new ArrayList<Gene>();
+
+ Item item1 = new Item();
+ item1.setName("Swiss Army Knife");
+ item1.setWeight(0.08125);
+ item1.setValue(15);
+ Gene gene1 = new Gene(item1);
+
+ Item item2 = new Item();
+ item2.setName("Duct Tape");
+ item2.setWeight(1.3);
+ item2.setValue(3);
+ Gene gene2 = new Gene(item2);
+
+ Item item3 = new Item();
+ item3.setName("Rope (50 feet)");
+ item3.setWeight(7);
+ item3.setValue(10);
+ Gene gene3 = new Gene(item3);
+
+ Item item4 = new Item();
+ item4.setName("Satellite phone");
+ item4.setWeight(2);
+ item4.setValue(8);
+ Gene gene4 = new Gene(item4);
+
+ Item item5 = new Item();
+ item5.setName("Elmer's Glue");
+ item5.setWeight(0.25);
+ item5.setValue(2);
+ Gene gene5 = new Gene(item5);
+
+ Item item6 = new Item();
+ item6.setName("Toilet Paper Roll");
+ item6.setWeight(.5);
+ item6.setValue(4);
+ Gene gene6 = new Gene(item6);
+
+ Item item7 = new Item();
+ item7.setName("Binoculars");
+ item7.setWeight(3);
+ item7.setValue(5);
+ Gene gene7 = new Gene(item7);
+
+ Item item8 = new Item();
+ item8.setName("Compass");
+ item8.setWeight(0.0573202);
+ item8.setValue(15);
+ Gene gene8 = new Gene(item8);
+
+ Item item9 = new Item();
+ item9.setName("Jug (prefilled with water)");
+ item9.setWeight(4);
+ item9.setValue(6);
+ Gene gene9 = new Gene(item9);
+
+ Item item10 = new Item();
+ item10.setName("Flashlight");
+ item10.setWeight(2);
+ item10.setValue(4);
+ Gene gene10 = new Gene(item10);
+
+ Item item11 = new Item();
+ item11.setName("Box of paper clips");
+ item11.setWeight(.9);
+ item11.setValue(2);
+ Gene gene11 = new Gene(item11);
+
+ Item item12 = new Item();
+ item12.setName("Gloves (1 pair)");
+ item12.setWeight(.8125);
+ item12.setValue(3);
+ Gene gene12 = new Gene(item12);
+
+ Item item13 = new Item();
+ item13.setName("Scissors");
+ item13.setWeight(0.2);
+ item13.setValue(2);
+ Gene gene13 = new Gene(item13);
+
+ Item item14 = new Item();
+ item14.setName("Signal Flair (4pk)");
+ item14.setWeight(4);
+ item14.setValue(5);
+ Gene gene14 = new Gene(item14);
+
+ Item item15 = new Item();
+ item15.setName("Water Purifying System");
+ item15.setWeight(0.5125);
+ item15.setValue(4);
+ Gene gene15 = new Gene(item15);
+
+ Item item16 = new Item();
+ item16.setName("Whistle");
+ item16.setWeight(0.075);
+ item16.setValue(2);
+ Gene gene16 = new Gene(item16);
+
+ Item item17 = new Item();
+ item17.setName("Sleeping Bag");
+ item17.setWeight(0.38125);
+ item17.setValue(4);
+ Gene gene17 = new Gene(item17);
+
+ Item item18 = new Item();
+ item18.setName("Insect Repellent");
+ item18.setWeight(1.15);
+ item18.setValue(3);
+ Gene gene18 = new Gene(item18);
+
+ Item item19 = new Item();
+ item19.setName("Trowel");
+ item19.setWeight(0.31875);
+ item19.setValue(3);
+ Gene gene19 = new Gene(item19);
+
+ Item item20 = new Item();
+ item20.setName("Lighter");
+ item20.setWeight(.2);
+ item20.setValue(4);
+ Gene gene20 = new Gene(item20);
+
+ Item item21 = new Item();
+ item21.setName("Safety Horn");
+ item21.setWeight(.21);
+ item21.setValue(3);
+ Gene gene21 = new Gene(item21);
+
+ Item item22 = new Item();
+ item22.setName("Headlamp");
+ item22.setWeight(.8);
+ item22.setValue(4);
+ Gene gene22 = new Gene(item22);
+
+ Item item23 = new Item();
+ item23.setName("Freeze Dried Food Kit");
+ item23.setWeight(2);
+ item23.setValue(6);
+ Gene gene23 = new Gene(item23);
+
+ Item item24 = new Item();
+ item24.setName("Sunscreen");
+ item24.setWeight(.5);
+ item24.setValue(4);
+ Gene gene24 = new Gene(item24);
+
+ Item item25 = new Item();
+ item25.setName("Trekking Pole (Adjustable)");
+ item25.setWeight(1.3);
+ item25.setValue(4);
+ Gene gene25 = new Gene(item25);
+
+ Item item26 = new Item();
+ item26.setName("Counter Assault Bear Spray");
+ item26.setWeight(.5);
+ item26.setValue(4);
+ Gene gene26 = new Gene(item26);
+
+ Item item27 = new Item();
+ item27.setName("Insect Spray");
+ item27.setWeight(.5);
+ item27.setValue(3);
+ Gene gene27 = new Gene(item27);
+
+ Item item28 = new Item();
+ item28.setName("Hand sanitizer");
+ item28.setWeight(.625);
+ item28.setValue(3);
+ Gene gene28 = new Gene(item28);
+
+ Item item29 = new Item();
+ item29.setName("Mirror");
+ item29.setWeight(.5);
+ item29.setValue(3);
+ Gene gene29 = new Gene(item29);
+
+ Item item30 = new Item();
+ item30.setName("First Aid Kit");
+ item30.setWeight(3);
+ item30.setValue(6);
+ Gene gene30 = new Gene(item30);
+
+ list.add(gene1);
+ list.add(gene2);
+ list.add(gene3);
+ list.add(gene4);
+ list.add(gene5);
+ list.add(gene6);
+ list.add(gene7);
+ list.add(gene8);
+ list.add(gene9);
+ list.add(gene10);
+ list.add(gene11);
+ list.add(gene12);
+ list.add(gene13);
+ list.add(gene14);
+ list.add(gene15);
+ list.add(gene16);
+ list.add(gene17);
+ list.add(gene18);
+ list.add(gene19);
+ list.add(gene20);
+ list.add(gene21);
+ list.add(gene22);
+ list.add(gene23);
+ list.add(gene24);
+ list.add(gene25);
+ list.add(gene26);
+ list.add(gene27);
+ list.add(gene28);
+ list.add(gene29);
+ list.add(gene30);
+
+ return list;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/297df324/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackTerminateCriteria.java
----------------------------------------------------------------------
diff --git a/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackTerminateCriteria.java b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackTerminateCriteria.java
new file mode 100644
index 0000000..a10a6fc
--- /dev/null
+++ b/examples/src/main/java/org/apache/ignite/examples/ml/genetic/knapsack/KnapsackTerminateCriteria.java
@@ -0,0 +1,100 @@
+/*
+ * 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.ignite.examples.ml.genetic.knapsack;
+
+import java.util.List;
+
+import org.apache.ignite.Ignite;
+import org.apache.ignite.IgniteLogger;
+import org.apache.ignite.ml.genetic.Chromosome;
+import org.apache.ignite.ml.genetic.Gene;
+import org.apache.ignite.ml.genetic.parameter.ITerminateCriteria;
+import org.apache.ignite.ml.genetic.utils.GAGridUtils;
+
+/**
+ * Represents the terminate condition for Knapsack Genetic algorithm
+ *
+ * Class terminates Genetic algorithm when once GA Grid has performed 30 generations.
+ */
+public class KnapsackTerminateCriteria implements ITerminateCriteria {
+ /** Ignite instance */
+ private static Ignite ignite = null;
+
+ /** Ignite logger */
+ private IgniteLogger igniteLogger = null;
+
+ /**
+ * @param ignite Ignite
+ */
+ public KnapsackTerminateCriteria(Ignite ignite) {
+ this.ignite = ignite;
+ this.igniteLogger = this.ignite.log();
+ }
+
+ /**
+ * @param fittestChromosome Most fit chromosome at for the nth generation
+ * @param averageFitnessScore Average fitness score as of the nth generation
+ * @param currentGeneration Current generation
+ * @return Boolean value
+ */
+ public boolean isTerminationConditionMet(Chromosome fittestChromosome, double averageFitnessScore,
+ int currentGeneration) {
+ boolean isTerminate = true;
+
+ igniteLogger.info("##########################################################################################");
+ igniteLogger.info("Generation: " + currentGeneration);
+ igniteLogger.info("Fittest is Chromosome Key: " + fittestChromosome);
+ igniteLogger.info("Total value is: " + fittestChromosome.getFitnessScore());
+ igniteLogger.info("Total weight is: " + calculateTotalWeight(GAGridUtils.getGenesInOrderForChromosome(ignite, fittestChromosome)));
+ igniteLogger.info("Avg Chromosome Fitness: " + averageFitnessScore);
+ igniteLogger.info("Chromosome: " + fittestChromosome);
+ printItems(GAGridUtils.getGenesInOrderForChromosome(ignite, fittestChromosome));
+ igniteLogger.info("##########################################################################################");
+
+ if (!(currentGeneration > 29))
+ isTerminate = false;
+
+ return isTerminate;
+ }
+
+ /**
+ * @param genes List of Genes
+ * @return double value
+ */
+ private double calculateTotalWeight(List<Gene> genes) {
+ double totalWeight = 0;
+ for (Gene gene : genes)
+ totalWeight = totalWeight + ((Item)gene.getValue()).getWeight();
+
+ return totalWeight;
+ }
+
+ /**
+ * Helper to print items in knapsack
+ *
+ * @param genes List of Genes
+ */
+ private void printItems(List<Gene> genes) {
+ for (Gene gene : genes) {
+ igniteLogger.info("------------------------------------------------------------------------------------------");
+ igniteLogger.info("Name: " + ((Item)gene.getValue()).getName().toString());
+ igniteLogger.info("Weight: " + ((Item)gene.getValue()).getWeight());
+ igniteLogger.info("Value: " + ((Item)gene.getValue()).getValue());
+ }
+ }
+}