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}