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 */
020 package org.jenetics.tool.problem;
021
022 import static java.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024
025 import java.io.Serializable;
026 import java.util.Random;
027 import java.util.Set;
028 import java.util.function.Function;
029 import java.util.stream.Collector;
030 import java.util.stream.Stream;
031
032 import org.jenetics.internal.util.require;
033
034 import org.jenetics.BitGene;
035 import org.jenetics.engine.Codec;
036 import org.jenetics.engine.Problem;
037 import org.jenetics.engine.codecs;
038 import org.jenetics.tool.problem.Knapsack.Item;
039 import 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 */
050 public 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 }
|