001/* 002 * Java Genetic Algorithm Library (jenetics-3.7.0). 003 * Copyright (c) 2007-2016 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at) 019 */ 020package org.jenetics.tool.problem; 021 022import static java.lang.String.format; 023import static java.util.Objects.requireNonNull; 024 025import java.io.Serializable; 026import java.util.Random; 027import java.util.Set; 028import java.util.function.Function; 029import java.util.stream.Collector; 030import java.util.stream.Stream; 031 032import org.jenetics.internal.util.require; 033 034import org.jenetics.BitGene; 035import org.jenetics.engine.Codec; 036import org.jenetics.engine.Problem; 037import org.jenetics.engine.codecs; 038import org.jenetics.tool.problem.Knapsack.Item; 039import org.jenetics.util.ISeq; 040 041/** 042 * <i>Canonical</i> definition of the <i>Knapsack</i> problem. This 043 * <i>reference</i> implementation is used for (evolution) performance tests of 044 * the GA {@link org.jenetics.engine.Engine}. 045 * 046 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a> 047 * @version 3.4 048 * @since 3.4 049 */ 050public final class Knapsack implements Problem<ISeq<Item>, BitGene, Double> { 051 052 /** 053 * This class represents a knapsack item with the specific <i>size</i> and 054 * <i>value</i>. 055 */ 056 public static final class Item implements Serializable { 057 private static final long serialVersionUID = 1L; 058 059 private final double _size; 060 private final double _value; 061 062 private Item(final double size, final double value) { 063 _size = require.nonNegative(size); 064 _value = require.nonNegative(value); 065 } 066 067 /** 068 * Return the item size. 069 * 070 * @return the item size 071 */ 072 public double getSize() { 073 return _size; 074 } 075 076 /** 077 * Return the item value. 078 * 079 * @return the item value 080 */ 081 public double getValue() { 082 return _value; 083 } 084 085 @Override 086 public int hashCode() { 087 int hash = 1; 088 long bits = Double.doubleToLongBits(_size); 089 hash = 31*hash + (int)(bits^(bits >>> 32)); 090 091 bits = Double.doubleToLongBits(_value); 092 return 31*hash + (int)(bits^(bits >>> 32)); 093 } 094 095 @Override 096 public boolean equals(final Object obj) { 097 return obj instanceof Item && 098 Double.compare(_size, ((Item)obj)._size) == 0 && 099 Double.compare(_value, ((Item)obj)._value) == 0; 100 } 101 102 @Override 103 public String toString() { 104 return format("Item[size=%f, value=%f]", _size, _value); 105 } 106 107 /** 108 * Return a new knapsack {@code Item} with the given {@code size} and 109 * {@code value}. 110 * 111 * @param size the item size 112 * @param value the item value 113 * @return a new knapsack {@code Item} 114 * @throws IllegalArgumentException if one of the parameters is smaller 115 * then zero 116 */ 117 public static Item of(final double size, final double value) { 118 return new Item(size, value); 119 } 120 121 /** 122 * Create a new <i>random</i> knapsack item for testing purpose. 123 * 124 * @param random the random engine used for creating the knapsack item 125 * @return a new <i>random</i> knapsack item 126 * @throws NullPointerException if the random engine is {@code null} 127 */ 128 public static Item random(final Random random) { 129 return new Item(random.nextDouble()*100, random.nextDouble()*100); 130 } 131 132 /** 133 * Return a {@link Collector}, which sums the size and value of knapsack 134 * items. 135 * 136 * @return a knapsack item sum {@link Collector} 137 */ 138 public static Collector<Item, ?, Item> toSum() { 139 return Collector.of( 140 () -> new double[2], 141 (a, b) -> {a[0] += b._size; a[1] += b._value;}, 142 (a, b) -> {a[0] += b[0]; a[1] += b[1]; return a;}, 143 r -> new Item(r[0], r[1]) 144 ); 145 } 146 } 147 148 149 private final Codec<ISeq<Item>, BitGene> _codec; 150 private final double _knapsackSize; 151 152 /** 153 * Create a new {@code Knapsack} definition with the given 154 * 155 * @param items the basic {@link Set} of knapsack items. 156 * @param knapsackSize the maximal knapsack size 157 * @throws NullPointerException if the {@code items} set is {@code null} 158 */ 159 public Knapsack(final ISeq<Item> items, final double knapsackSize) { 160 _codec = codecs.ofSubSet(items); 161 _knapsackSize = knapsackSize; 162 } 163 164 @Override 165 public Function<ISeq<Item>, Double> fitness() { 166 return items -> { 167 final Item sum = items.stream().collect(Item.toSum()); 168 return sum._size <= _knapsackSize ? sum._value : 0; 169 }; 170 } 171 172 @Override 173 public Codec<ISeq<Item>, BitGene> codec() { 174 return _codec; 175 } 176 177 /** 178 * Factory method for creating <i>same</i> Knapsack problems for testing 179 * purpose. 180 * 181 * @param itemCount the number of knapsack items in the basic set 182 * @param random the random engine used for creating random knapsack items. 183 * This allows to create reproducible item sets and reproducible 184 * {@code Knapsack} problems, respectively. 185 * @return a {@code Knapsack} problem object (for testing purpose). 186 */ 187 public static Knapsack of(final int itemCount, final Random random) { 188 requireNonNull(random); 189 190 return new Knapsack( 191 Stream.generate(() -> Item.random(random)) 192 .limit(itemCount) 193 .collect(ISeq.toISeq()), 194 itemCount*100.0/3.0 195 ); 196 } 197 198}