Created
October 31, 2018 21:11
-
-
Save jrecursive/d73a50c572e315fa75b82e741fd0de97 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.nio.file.*; | |
| import java.nio.*; | |
| import java.util.*; | |
| import java.math.*; | |
| import org.jgap.*; | |
| import org.jgap.data.*; | |
| import org.jgap.impl.*; | |
| public class WingComputer { | |
| private static final int MAX_ALLOWED_EVOLUTIONS = 10000; | |
| public final static double[] wingCount = { | |
| 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, | |
| 24, 25, 26, 27, 28, 29, 30, 35, 40, 45, 50, 60, 70, 75, 80, 90, 100, 125, | |
| 150, 200 }; | |
| public final static double[] wingPrice = { | |
| 4.55, 5.70, 6.80, 7.95, 9.10, 10.20, 11.35, 12.50, 13.60, 14.75, 15.90, 17.00, | |
| 18.15, 19.30, 20.40, 21.55, 22.70, 23.80, 24.95, 26.10, 27.25, 27.80, 28.95, | |
| 30.10, 31.20, 32.35, 33.50, 39.15, 44.80, 50.50, 55.60, 67.00, 78.30, 83.45, | |
| 89.10, 100.45, 111.25, 139.00, 166.85, 222.50 }; | |
| public static String wingResult = ""; | |
| /* | |
| * fitness function | |
| */ | |
| class Wings extends FitnessFunction { | |
| private final double numWings; | |
| public Wings(double numWings) { | |
| this.numWings = numWings; | |
| } | |
| public double evaluate(IChromosome chrom) { | |
| double totalPrice = getTotalPrice(chrom); | |
| int numberOfItems = getTotalNumberOfItems(chrom); | |
| int orders = 0; | |
| int numberOfGenes = chrom.size(); | |
| for (int i = 0; i < numberOfGenes; i++) { | |
| orders+=getNumberOfItemsAtGene(chrom, i); | |
| } | |
| /* | |
| * if we don't have the right number of wings overall for this | |
| * configuration, return a score below the minimum score for | |
| * perfectly-sized orders (i.e., 10000), increasing as the | |
| * candidate order's size converges on the desired number of | |
| * wings; this influences later generations positively | |
| */ | |
| double itemDiff = Math.abs(numWings - numberOfItems); | |
| if (itemDiff > 0) { | |
| return 1.0d / (itemDiff * itemDiff); | |
| } | |
| /* | |
| * since we've got a candidate solution that produces the | |
| * desired number of wings perfectly, let's compute a score | |
| * that increases as the total price and number of individual | |
| * orders decrease. we do this because 1) we want the lowest | |
| * possible total price for our wing order, and 2) based on | |
| * the pricing for the menu, for the most part larger orders | |
| * have lower average wing costs (with a few exceptions), so | |
| * giving a better score to candidate solutions with fewer | |
| * individual orders will positively influence future generations | |
| * (by implicitly capitalizing on the lower average wing price | |
| * for larger-count single order items). i think i said that right? | |
| */ | |
| double fitness = (10000.0d + (1.0d / (1.0d + totalPrice))) / (double)(orders*orders); | |
| return fitness; | |
| } | |
| public double getTotalPrice(IChromosome chrom) { | |
| double price = 0.0d; | |
| for (int i = 0; i < chrom.size(); i++) { | |
| price += getNumberOfItemsAtGene(chrom, i) * | |
| WingComputer.wingPrice[i]; | |
| } | |
| return price; | |
| } | |
| public int getNumberOfItemsAtGene(IChromosome chrom, | |
| int pos) { | |
| Integer numItems = | |
| (Integer) chrom.getGene(pos).getAllele(); | |
| return numItems.intValue(); | |
| } | |
| public int getTotalNumberOfItems(IChromosome chrom) { | |
| int totalItems = 0; | |
| int numberOfGenes = chrom.size(); | |
| for (int i = 0; i < numberOfGenes; i++) { | |
| totalItems += getNumberOfItemsAtGene(chrom, i) * WingComputer.wingCount[i]; | |
| } | |
| return totalItems; | |
| } | |
| } | |
| /* | |
| * wing computer | |
| */ | |
| public void findPriceForWings(double desiredWings) | |
| throws Exception { | |
| wingResult = ""; | |
| Configuration.reset(); | |
| Configuration conf = new DefaultConfiguration(); | |
| conf.setPreservFittestIndividual(true); | |
| conf.addGeneticOperator(new CrossoverOperator(conf)); | |
| conf.addGeneticOperator(new MutationOperator(conf, 10)); | |
| //conf.addGeneticOperator(new MutationOperator(conf, new DefaultMutationRateCalculator(conf))); | |
| /* | |
| BestChromosomesSelector bestChromsSelector = | |
| new BestChromosomesSelector(conf, 0.1); | |
| bestChromsSelector.setDoubletteChromosomesAllowed(true); | |
| conf.addNaturalSelector(bestChromsSelector, true); | |
| */ | |
| FitnessFunction myFunc = | |
| new Wings(desiredWings); | |
| conf.setFitnessFunction(myFunc); | |
| Gene[] sampleGenes = new Gene[wingCount.length]; | |
| for (int i = 0; i < wingCount.length; i++) { | |
| sampleGenes[i] = new IntegerGene(conf, 0, 4); | |
| } | |
| IChromosome sampleChromosome = new Chromosome(conf, sampleGenes); | |
| conf.setSampleChromosome(sampleChromosome); | |
| conf.setPopulationSize(250); | |
| Genotype population; | |
| population = Genotype.randomInitialGenotype(conf); | |
| // EVOLVE-O-TRON | |
| double prevPrice = Double.MAX_VALUE; | |
| int emptyCycles = 0; | |
| int MAX_EMPTY_CYCLES = 30; | |
| for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) { | |
| population.evolve(); | |
| if (i % 100 == 0) { | |
| IChromosome bestSolutionSoFar = population.getFittestChromosome(); | |
| int count; | |
| double totalPrice = 0.0d; | |
| double totalWings = 0.0d; | |
| String exp = ""; | |
| for (int z = 0; z < bestSolutionSoFar.size(); z++) { | |
| count = ( (Integer) bestSolutionSoFar.getGene(z).getAllele()).intValue(); | |
| if (count > 0) { | |
| exp += "\t " + count + " x " + wingCount[z] + " wing orders @ $" + | |
| wingPrice[z] + "\n"; | |
| totalPrice += wingPrice[z] * count; | |
| totalWings += wingCount[z] * count; | |
| } | |
| } | |
| if (i == MAX_ALLOWED_EVOLUTIONS-1 || | |
| (totalPrice < prevPrice && totalWings == desiredWings)) { | |
| exp = "\n"+ ((int)totalWings) + " wings, total cost $" + | |
| round(totalPrice,2) + ", avg $" + round((totalPrice / totalWings),2) + | |
| "/wing: \n" + exp; | |
| System.out.println(exp); | |
| prevPrice = totalPrice; | |
| wingResult = exp; | |
| emptyCycles = 0; | |
| } else { | |
| emptyCycles++; | |
| System.out.print(" " + emptyCycles + " "); | |
| if (emptyCycles == MAX_EMPTY_CYCLES && prevPrice < Double.MAX_VALUE) { | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| public static double round(double value, int places) { | |
| if (places < 0) throw new IllegalArgumentException(); | |
| BigDecimal bd = new BigDecimal(value); | |
| bd = bd.setScale(places, RoundingMode.HALF_UP); | |
| return bd.doubleValue(); | |
| } | |
| public static void appendResult(String res) throws Exception { | |
| System.out.println("-----------------------------------------\n"); | |
| System.out.println(res); | |
| System.out.println("-----------------------------------------\n"); | |
| Files.write(Paths.get("wings.txt"), res.getBytes(), StandardOpenOption.APPEND); | |
| } | |
| public static void main(String[] args) throws Exception { | |
| // let's compute mrb's wing problem | |
| if (args.length != 1) { | |
| for (int i=0; i<wingCount.length; i++) { | |
| double ct = wingCount[i]; | |
| double pr = wingPrice[i]; | |
| appendResult(ct + " wings @ " + pr + " => avg $" + round((pr/ct),2) + " / wing\n"); | |
| } | |
| appendResult("\n\n"); | |
| int priceIdx = 0; | |
| for(int i=100; i<999; i++) { | |
| boolean foundIt = false; | |
| for(int j=0; j<wingCount.length; j++) { | |
| int ct = (int)wingCount[j]; | |
| if (ct == i) { | |
| foundIt = true; | |
| priceIdx = j; | |
| break; | |
| } | |
| } | |
| if (!foundIt) { | |
| System.out.println("minimizing for " + i + " wings ... "); | |
| WingComputer wm = new WingComputer(); | |
| wm.findPriceForWings(i); | |
| if (!wingResult.trim().equals("")) { | |
| appendResult(wingResult + "\n\n"); | |
| } else { | |
| appendResult("found no result for " + i + " wings :(\n\n"); | |
| } | |
| } else { | |
| appendResult("\n*** exact price for " + i + " wings: " + wingPrice[priceIdx] + | |
| ", avg $" + round((wingPrice[priceIdx]/wingCount[priceIdx]),2) + "\n\n"); | |
| } | |
| } | |
| } | |
| // otherwise we're just testing i guess | |
| else { | |
| try { | |
| double wings = Math.floor(Double.parseDouble(args[0])); | |
| if (wings < 4) { | |
| System.out.println("The <#wings> argument must be > 4"); | |
| } | |
| else { | |
| try { | |
| WingComputer wm = new WingComputer(); | |
| wm.findPriceForWings(wings); | |
| } | |
| catch (Exception e) { | |
| e.printStackTrace(); | |
| } | |
| } | |
| } | |
| catch (NumberFormatException e) { | |
| System.out.println( | |
| "The <#wings> argument must be a valid value"); | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment