ナップサック問題
Published:
By nobCategory: Posts
Tags: 数理最適化 Python-MIP Platypus Python
数理最適化問題で目的関数を複数設定したい。
ナップサック問題で実験してみる。
まず目的関数が1つの場合を実験する。
整数ナップサック問題
ナップサックのサイズの範囲で出来るだけ価値が高くなるような組み合わせを求める。
同じ品物を複数個入れてもよい。
データ
ナップサックのサイズ
capacity = 65
品物
import pandas as pd
from IPython.display import display
items = pd.DataFrame(
[
["缶コーヒー", 120, 10],
["水入りペットボトル", 130, 12],
["バナナ", 80, 7],
["りんご", 100, 9],
["おにぎり", 250, 21],
["パン", 185, 16],
],
columns=["name", "value", "size"],
)
display(items)
| name | value | size | |
|---|---|---|---|
| 0 | 缶コーヒー | 120 | 10 |
| 1 | 水入りペットボトル | 130 | 12 |
| 2 | バナナ | 80 | 7 |
| 3 | りんご | 100 | 9 |
| 4 | おにぎり | 250 | 21 |
| 5 | パン | 185 | 16 |
データの出典
モデル
from mip import INTEGER, Model, OptimizationStatus, maximize, xsum
mip_model = Model(solver_name="cbc")
mip_items = items.copy()
mip_items["var"] = mip_model.add_var_tensor(
(len(mip_items),), "var", var_type=INTEGER
)
mip_model += xsum(mip_items["size"] * mip_items["var"]) <= capacity
mip_model.objective = maximize(xsum(mip_items["value"] * mip_items["var"]))
mip_model.optimize()
Welcome to the CBC MILP Solver
Version: devel
Build Date: Aug 4 2024
Starting solution of the Linear programming relaxation problem using Primal Simplex
Coin0506I Presolve 0 (-1) rows, 0 (-6) columns and 0 (-6) elements
Clp0000I Optimal - objective value 780
Coin0511I After Postsolve, objective 780, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 780 - 0 iterations time 0.002, Presolve 0.00, Idiot 0.00
Starting MIP optimization
<OptimizationStatus.OPTIMAL: 0>
確認
if mip_model.status == OptimizationStatus.OPTIMAL:
print("total value:", mip_model.objective_value)
mip_items["val"] = mip_items["var"].astype(float)
print("total size:", (mip_items["size"] * mip_items["val"]).sum())
display(mip_items[["name", "value", "size", "val"]])
else:
print(mip_model.status)
total value: 770.0
total size: 65.0
| name | value | size | val | |
|---|---|---|---|---|
| 0 | 缶コーヒー | 120 | 10 | 3.0 |
| 1 | 水入りペットボトル | 130 | 12 | 0.0 |
| 2 | バナナ | 80 | 7 | 2.0 |
| 3 | りんご | 100 | 9 | 0.0 |
| 4 | おにぎり | 250 | 21 | 1.0 |
| 5 | パン | 185 | 16 | 0.0 |
0/1ナップサック問題
ナップサックのサイズの範囲で出来るだけ価値が高くなるような組み合わせを求める。
同じ品物を複数個入れることはできない(0個または1個)。
モデル
from mip import BINARY
mip_model = Model(solver_name="cbc")
mip_items = items.copy()
mip_items["var"] = mip_model.add_var_tensor(
(len(mip_items),), "var", var_type=BINARY
)
mip_model += xsum(mip_items["size"] * mip_items["var"]) <= capacity
mip_model.objective = maximize(xsum(mip_items["value"] * mip_items["var"]))
mip_model.optimize()
maxSavedSolutions was changed from 1 to 10
Continuous objective value is 780 - 3.7e-05 seconds
Cgl0004I processed model has 1 rows, 6 columns (6 integer (0 of which binary)) and 6 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 0.000%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0045I Nauty did not find any useful orbits in time 2.6e-05
Cbc0012I Integer solution of 760 found by DiveCoefficient after 0 iterations and 0 nodes (0.00 seconds)
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 3 columns
Cbc0012I Integer solution of 770 found by RINS after 0 iterations and 0 nodes (0.00 seconds)
Cbc0031I 1 added rows had average density of 3
Cbc0013I At root node, 3 cuts changed objective from 779.52381 to 770 in 2 passes
Cbc0014I Cut generator 0 (Probing) - 2 row cuts average 2.0 elements, 2 column cuts (2 active) in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2 row cuts average 3.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (ZeroHalf) - 1 row cuts average 6.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0001I Search completed - best objective 770, took 2 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 1 variables fixed on reduced cost
Cuts at root node changed objective from 779.524 to 770
Probing was tried 2 times and created 4 cuts (5.4e-05 seconds)
Gomory was tried 2 times and created 2 cuts (5.2e-05 seconds)
Knapsack was tried 2 times and created 0 cuts (1e-05 seconds)
Clique was tried 2 times and created 0 cuts (1.1e-05 seconds)
OddWheel was tried 2 times and created 0 cuts (5e-06 seconds)
MixedIntegerRounding2 was tried 2 times and created 0 cuts (1.3e-05 seconds)
FlowCover was tried 2 times and created 0 cuts (7e-06 seconds)
TwoMirCuts was tried 1 times and created 0 cuts (1.9e-05 seconds)
ZeroHalf was tried 1 times and created 1 cuts (3.3e-05 seconds)
Result - Optimal solution found
Objective value: 770
Enumerated nodes: 0
Total iterations: 2
Time (CPU seconds): 0.002176
Time (Wallclock seconds): 0.00341201
Total time (CPU seconds): 0.002239 (Wallclock seconds): 0.00352001
Starting solution of the Linear programming relaxation problem using Primal Simplex
Coin0506I Presolve 1 (0) rows, 6 (0) columns and 6 (0) elements
Clp1000I sum of infeasibilities 0 - average 0, 6 fixed columns
Coin0506I Presolve 0 (-1) rows, 0 (-6) columns and 0 (-6) elements
Clp0000I Optimal - objective value -0
Clp0000I Optimal - objective value -0
Coin0511I After Postsolve, objective 0, infeasibilities - dual 0 (0), primal 0 (0)
Clp0000I Optimal - objective value 756.66667
Clp0000I Optimal - objective value 756.66667
Clp0000I Optimal - objective value 756.66667
Clp0032I Optimal objective 756.6666667 - 0 iterations time 0.002, Idiot 0.00
Starting MIP optimization
maxSavedSolutions was changed from 1 to 10
Continuous objective value is 756.667 - 4.7e-05 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0004I processed model has 1 rows, 6 columns (6 integer (6 of which binary)) and 6 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 7.692%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0045I Nauty did not find any useful orbits in time 5.4e-05
Cbc0038I Initial state - 1 integers unsatisfied sum - 0.142857
Cbc0038I Pass 1: suminf. 0.04762 (1) obj. 753.095 iterations 1
Cbc0038I Solution found of 515
Cbc0038I Rounding solution of 615 is better than previous of 515
Cbc0038I Before mini branch and bound, 4 integers at bound fixed and 0 continuous
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 2 columns
Cbc0038I Mini branch and bound improved solution from 615 to 685 (0.00 seconds)
Cbc0038I Round again with cutoff of 696.357
Cbc0038I Pass 2: suminf. 0.04762 (1) obj. 753.095 iterations 0
Cbc0038I Pass 3: suminf. 0.27457 (1) obj. 696.357 iterations 1
Cbc0038I Pass 4: suminf. 0.37104 (1) obj. 696.357 iterations 1
Cbc0038I Pass 5: suminf. 0.11357 (1) obj. 696.357 iterations 2
Cbc0038I Pass 6: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 7: suminf. 0.14286 (1) obj. 749.286 iterations 2
Cbc0038I Pass 8: suminf. 0.35457 (1) obj. 696.357 iterations 1
Cbc0038I Pass 9: suminf. 0.35457 (1) obj. 696.357 iterations 0
Cbc0038I Pass 10: suminf. 0.47619 (1) obj. 745.952 iterations 2
Cbc0038I Pass 11: suminf. 0.32543 (1) obj. 696.357 iterations 1
Cbc0038I Pass 12: suminf. 0.47619 (1) obj. 745.952 iterations 1
Cbc0038I Pass 13: suminf. 0.14286 (1) obj. 749.286 iterations 1
Cbc0038I Pass 14: suminf. 0.31813 (1) obj. 696.357 iterations 2
Cbc0038I Pass 15: suminf. 0.31813 (1) obj. 696.357 iterations 0
Cbc0038I Pass 16: suminf. 0.31813 (1) obj. 696.357 iterations 0
Cbc0038I Pass 17: suminf. 0.14286 (1) obj. 749.286 iterations 2
Cbc0038I Pass 18: suminf. 0.35457 (1) obj. 696.357 iterations 1
Cbc0038I Pass 19: suminf. 0.47915 (1) obj. 696.357 iterations 1
Cbc0038I Pass 20: suminf. 0.11357 (1) obj. 696.357 iterations 1
Cbc0038I Pass 21: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 22: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 23: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 24: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 25: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 26: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 27: suminf. 0.11357 (1) obj. 696.357 iterations 0
Cbc0038I Pass 28: suminf. 0.08842 (1) obj. 696.357 iterations 2
Cbc0038I Pass 29: suminf. 0.47619 (1) obj. 745.952 iterations 2
Cbc0038I Pass 30: suminf. 0.32543 (1) obj. 696.357 iterations 1
Cbc0038I Pass 31: suminf. 0.31813 (1) obj. 696.357 iterations 2
Cbc0038I Rounding solution of 735 is better than previous of 685
Cbc0038I Before mini branch and bound, 1 integers at bound fixed and 0 continuous
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 4 columns
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I Round again with cutoff of 742.714
Cbc0038I Reduced cost fixing fixed 1 variables on major pass 3
Cbc0038I Pass 31: suminf. 0.04762 (1) obj. 753.095 iterations 0
Cbc0038I Pass 32: suminf. 0.08914 (1) obj. 742.714 iterations 1
Cbc0038I Pass 33: suminf. 0.00914 (1) obj. 742.714 iterations 2
Cbc0038I Solution found of 745
Cbc0038I Before mini branch and bound, 2 integers at bound fixed and 0 continuous
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 4 columns
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I Round again with cutoff of 751.071
Cbc0038I Reduced cost fixing fixed 4 variables on major pass 4
Cbc0038I Pass 34: suminf. 0.06250 (1) obj. 753.438 iterations 1
Cbc0038I Pass 35: suminf. 0.07529 (1) obj. 751.071 iterations 1
Cbc0038I Pass 36: suminf. 0.06250 (1) obj. 753.438 iterations 1
Cbc0038I Pass 37: suminf. 0.07529 (1) obj. 751.071 iterations 1
Cbc0038I Pass 38: suminf. 0.17411 (1) obj. 751.071 iterations 1
Cbc0038I Pass 39: suminf. 0.06250 (1) obj. 753.438 iterations 2
Cbc0038I Pass 40: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 41: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 42: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 43: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 44: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 45: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 46: suminf. 0.17411 (1) obj. 751.071 iterations 2
Cbc0038I Pass 47: suminf. 0.17411 (1) obj. 751.071 iterations 0
Cbc0038I Pass 48: suminf. 0.17411 (1) obj. 751.071 iterations 0
Cbc0038I Pass 49: suminf. 0.17411 (1) obj. 751.071 iterations 0
Cbc0038I Pass 50: suminf. 0.06250 (1) obj. 753.438 iterations 2
Cbc0038I Pass 51: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 52: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 53: suminf. 0.17411 (1) obj. 751.071 iterations 2
Cbc0038I Pass 54: suminf. 0.06250 (1) obj. 753.438 iterations 2
Cbc0038I Pass 55: suminf. 0.06250 (1) obj. 753.438 iterations 0
Cbc0038I Pass 56: suminf. 0.17411 (1) obj. 751.071 iterations 2
Cbc0038I Pass 57: suminf. 0.17411 (1) obj. 751.071 iterations 0
Cbc0038I Pass 58: suminf. 0.17411 (1) obj. 751.071 iterations 0
Cbc0038I Pass 59: suminf. 0.07529 (1) obj. 751.071 iterations 1
Cbc0038I Pass 60: suminf. 0.06250 (1) obj. 753.438 iterations 1
Cbc0038I Pass 61: suminf. 0.17411 (1) obj. 751.071 iterations 2
Cbc0038I Pass 62: suminf. 0.06250 (1) obj. 753.438 iterations 2
Cbc0038I Pass 63: suminf. 0.17411 (1) obj. 751.071 iterations 2
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 4 integers at bound fixed and 0 continuous
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 2 columns
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I After 0.00 seconds - Feasibility pump exiting with objective of 745 - took 0.00 seconds
Cbc0012I Integer solution of 745 found by feasibility pump after 0 iterations and 0 nodes (0.00 seconds)
Cbc0038I Full problem 1 rows 6 columns, reduced to 1 rows 2 columns
Cbc0006I The LP relaxation is infeasible or too expensive
Cbc0013I At root node, 0 cuts changed objective from 753.57143 to 685 in 1 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 1 column cuts (1 active) in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0001I Search completed - best objective 745, took 0 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 3 variables fixed on reduced cost
Cuts at root node changed objective from 753.571 to 685
Probing was tried 1 times and created 1 cuts (2.2e-05 seconds)
Gomory was tried 0 times and created 0 cuts (0 seconds)
Knapsack was tried 0 times and created 0 cuts (0 seconds)
Clique was tried 0 time
<OptimizationStatus.OPTIMAL: 0>
確認
if mip_model.status == OptimizationStatus.OPTIMAL:
print("total value:", mip_model.objective_value)
mip_items["val"] = mip_items["var"].astype(float)
print("total size:", (mip_items["size"] * mip_items["val"]).sum())
display(mip_items[["name", "value", "size", "val"]])
else:
print(mip_model.status)
total value: 745.0
total size: 65.0
| name | value | size | val | |
|---|---|---|---|---|
| 0 | 缶コーヒー | 120 | 10 | 0.0 |
| 1 | 水入りペットボトル | 130 | 12 | 1.0 |
| 2 | バナナ | 80 | 7 | 1.0 |
| 3 | りんご | 100 | 9 | 1.0 |
| 4 | おにぎり | 250 | 21 | 1.0 |
| 5 | パン | 185 | 16 | 1.0 |
次に目的関数を2つにしてみる。
多目的・多制約整数ナップサック問題
ナップサックの価値が最大かつ最軽量となる組み合わせを求める。
同じ品物を複数個入れてもよい。
多目的最適化のために Platypus を使う。
$ poetry add platypus-opt
データ
moo_data = [
["缶コーヒー", 120, 10, 350],
["水入りペットボトル", 130, 12, 500],
["バナナ", 80, 7, 200],
["りんご", 100, 9, 350],
["おにぎり", 120, 21, 120],
["パン", 110, 16, 100],
]
moo_items = pd.DataFrame(
data=moo_data,
columns=["name", "value", "volume", "weight"],
)
display(moo_items)
| name | value | volume | weight | |
|---|---|---|---|---|
| 0 | 缶コーヒー | 120 | 10 | 350 |
| 1 | 水入りペットボトル | 130 | 12 | 500 |
| 2 | バナナ | 80 | 7 | 200 |
| 3 | りんご | 100 | 9 | 350 |
| 4 | おにぎり | 120 | 21 | 120 |
| 5 | パン | 110 | 16 | 100 |
モデル
from platypus import NSGAII, Constraint, Integer, Problem
class MultiObjectiveKnapsack(Problem):
def __init__(self, items, capacity, max_qty_per_item):
super().__init__(nvars=len(items), nobjs=2, nconstrs=2)
self.items = items
self.capacity = capacity
self.types[:] = Integer(0, max_qty_per_item)
self.constraints[:] = [Constraint("<=", capacity), Constraint(">", 0)]
self.directions[:] = [Problem.MAXIMIZE, Problem.MINIMIZE]
def evaluate(self, solution):
item_values = self.items["value"].values
item_volumes = self.items["volume"].values
item_weights = self.items["weight"].values
item_qtys = solution.variables
solution.objectives[0] = sum(
value * qty for value, qty in zip(item_values, item_qtys)
)
solution.objectives[1] = sum(
weight * qty for weight, qty in zip(item_weights, item_qtys)
)
solution.constraints[0] = sum(
volume * qty for volume, qty in zip(item_volumes, item_qtys)
)
solution.constraints[1] = sum(item_qtys)
求解
problem = MultiObjectiveKnapsack(
moo_items,
capacity=capacity,
max_qty_per_item=capacity // moo_items["volume"].min(),
)
algorithm = NSGAII(problem)
algorithm.run(1000)
確認
import matplotlib.pyplot as plt
from platypus import nondominated, unique
def plot_solutions(solutions):
# 実現可能解
feasible_solutions = unique(
[solution for solution in solutions if solution.feasible]
)
feasible_values = []
feasible_weights = []
for solution in feasible_solutions:
feasible_values.append(solution.objectives[0])
feasible_weights.append(solution.objectives[1])
# パレート解
pareto_solutions = unique(nondominated(solutions))
pareto_values = []
pareto_weights = []
for solution in pareto_solutions:
pareto_values.append(solution.objectives[0])
pareto_weights.append(solution.objectives[1])
fig = plt.figure(figsize=(5, 5))
ax = fig.add_subplot()
ax.scatter(feasible_values, feasible_weights, alpha=0.5, label="feasible")
ax.scatter(
pareto_values,
pareto_weights,
color="yellow",
edgecolor="black",
label="pareto",
)
ax.set(xlabel="total value", ylabel="total weight")
ax.legend()
plt.minorticks_on()
plt.grid(which="major", color="black", alpha=0.4)
plt.grid(which="minor", color="gray", linestyle=":")
plt.show()
解の候補を表示する。
plot_solutions(algorithm.result)
from platypus import bin2int, gray2bin
def display_solutions(items, solutions):
pareto_solutions = unique(nondominated(solutions))
moo_result = []
for solution in sorted(
pareto_solutions, key=lambda x: x.objectives[0], reverse=True
)[0:10]:
item_qtys = [bin2int(gray2bin(bits)) for bits in solution.variables]
moo_result.append(
[*item_qtys, *solution.objectives, solution.constraints[0]]
)
result = pd.DataFrame(
moo_result,
columns=[
*moo_items["name"].values,
"total value",
"total weight",
"total volume",
],
)
display(result)
求めた解を価値の高い順に10件表示する。
display_solutions(moo_items, algorithm.result)
| 缶コーヒー | 水入りペットボトル | バナナ | りんご | おにぎり | パン | total value | total weight | total volume | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 5 | 2 | 0 | 0 | 720 | 2050 | 63 |
| 1 | 1 | 0 | 3 | 3 | 0 | 0 | 660 | 2000 | 58 |
| 2 | 2 | 1 | 2 | 0 | 0 | 1 | 640 | 1700 | 62 |
| 3 | 0 | 0 | 5 | 1 | 1 | 0 | 620 | 1470 | 65 |
| 4 | 0 | 0 | 6 | 0 | 1 | 0 | 600 | 1320 | 63 |
| 5 | 0 | 0 | 4 | 1 | 1 | 0 | 540 | 1270 | 58 |
| 6 | 0 | 0 | 4 | 1 | 0 | 1 | 530 | 1250 | 53 |
| 7 | 0 | 0 | 5 | 0 | 1 | 0 | 520 | 1120 | 56 |
| 8 | 0 | 0 | 2 | 1 | 2 | 0 | 500 | 990 | 65 |
| 9 | 0 | 0 | 2 | 1 | 1 | 1 | 490 | 970 | 60 |
多目的・多制約0/1ナップサック問題
ナップサックの価値が最大かつ最軽量となる組み合わせを求める。
同じ品物を複数個入れることはできない(0個または1個)。
モデル
problem = MultiObjectiveKnapsack(
moo_items,
capacity=capacity,
max_qty_per_item=1,
)
algorithm = NSGAII(problem)
algorithm.run(100)
確認
解の候補を表示する。
plot_solutions(algorithm.result)
求めた解を価値の高い順に10件表示する。
display_solutions(moo_items, algorithm.result)
| 缶コーヒー | 水入りペットボトル | バナナ | りんご | おにぎり | パン | total value | total weight | total volume | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 550 | 1520 | 59 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 540 | 1500 | 54 |
| 2 | 1 | 0 | 1 | 1 | 1 | 1 | 530 | 1120 | 63 |
| 3 | 1 | 1 | 0 | 0 | 1 | 1 | 480 | 1070 | 59 |
| 4 | 1 | 0 | 0 | 1 | 1 | 1 | 450 | 920 | 56 |
| 5 | 1 | 0 | 1 | 0 | 1 | 1 | 430 | 770 | 54 |
| 6 | 1 | 0 | 0 | 0 | 1 | 1 | 350 | 570 | 47 |
| 7 | 0 | 0 | 1 | 0 | 1 | 1 | 310 | 420 | 44 |
| 8 | 0 | 0 | 0 | 0 | 1 | 1 | 230 | 220 | 37 |
| 9 | 0 | 0 | 0 | 0 | 0 | 1 | 110 | 100 | 16 |
試行回数を増やす
試行回数を増やしてみる。
problem = MultiObjectiveKnapsack(
moo_items,
capacity=capacity,
max_qty_per_item=1,
)
algorithm = NSGAII(problem)
algorithm.run(10000)
plot_solutions(algorithm.result)
display_solutions(moo_items, algorithm.result)
| 缶コーヒー | 水入りペットボトル | バナナ | りんご | おにぎり | パン | total value | total weight | total volume | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 550 | 1520 | 59 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 540 | 1270 | 65 |
| 2 | 1 | 0 | 1 | 1 | 1 | 1 | 530 | 1120 | 63 |
| 3 | 1 | 1 | 0 | 0 | 1 | 1 | 480 | 1070 | 59 |
| 4 | 1 | 0 | 0 | 1 | 1 | 1 | 450 | 920 | 56 |
| 5 | 1 | 0 | 1 | 0 | 1 | 1 | 430 | 770 | 54 |
| 6 | 0 | 1 | 0 | 0 | 1 | 1 | 360 | 720 | 49 |
| 7 | 1 | 0 | 0 | 0 | 1 | 1 | 350 | 570 | 47 |
| 8 | 0 | 0 | 1 | 0 | 1 | 1 | 310 | 420 | 44 |
| 9 | 0 | 0 | 0 | 0 | 1 | 1 | 230 | 220 | 37 |