Skip to content

Instantly share code, notes, and snippets.

@kevinrpb

kevinrpb/Readme.md

Created May 31, 2021 09:15
Show Gist options
  • Save kevinrpb/0c5e23935a8c542baa803dbd42353ed4 to your computer and use it in GitHub Desktop.
Save kevinrpb/0c5e23935a8c542baa803dbd42353ed4 to your computer and use it in GitHub Desktop.
Download ZIP
Basketball MOO
Raw
Readme.md

Basketball MOO

Raw
main.py
from argparse import ArgumentParser, Namespace
import numpy as np
from pymoo.algorithms.moead import MOEAD
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.algorithms.rnsga2 import RNSGA2
from pymoo.factory import get_reference_directions
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter
from matplotlib import pyplot as plt
from problem import BasketballProblem
# * --------------------
# * Parser
# * --------------------
def parse_args() -> Namespace:
parser = ArgumentParser('Basketball MOO')
parser.add_argument('-p', '--players',
type = int,
default = 8,
help = 'Number of players in the team.'
)
parser.add_argument('-t', '--tplayers',
type = int,
default = 2,
help = 'Number of *talented* players in the team.'
)
parser.add_argument('-e', '--easy',
action = 'store_true',
default = False,
help = 'Use easier minute limits. This will allow algorithms to converge faster.'
)
parser.add_argument('-a', '--algorithm',
type = str.lower,
choices = ['moead', 'nsga2', 'rnsga2'],
default = 'moead',
help = 'Algorithm to solve the problem with.'
)
parser.add_argument('-g', '--generations',
type = int,
default = 1000,
help = 'Number of generations to run the algorithm for.'
)
parser.add_argument('--pareto',
action = 'store_true',
default = False,
help = 'Show Pareto front in a graph.'
)
parser.add_argument('--violations',
action = 'store_true',
default = False,
help = 'Show constraint violations in a graph.'
)
parser.add_argument('-s', '--seed',
type = int,
default = None,
help = 'Seed to init random values.'
)
return parser.parse_args()
# * --------------------
# * Helpers
# * --------------------
def run(args):
# Create problem and algorithm
problem = BasketballProblem(args.players, args.tplayers, simple_limits=args.easy, seed=args.seed)
# Creamos la población inicial
np.random.seed(args.seed)
algorithm = None
if args.algorithm == 'moead':
X = 2 * np.random.random((500, problem.n_var))
algorithm = MOEAD(
get_reference_directions('das-dennis', 3, n_partitions=12),
n_neighbors = 15,
decomposition = 'pbi',
prob_neighbor_mating = 0.7,
seed = args.seed,
sampling = X
)
elif args.algorithm == 'nsga2':
X = 2 * np.random.random((100, problem.n_var))
algorithm = NSGA2(
pop_size = 100,
n_offsprings = 10,
eliminate_duplicates = True,
seed = args.seed,
sampling = X
)
elif args.algorithm == 'rnsga2':
X = 2 * np.random.random((100, problem.n_var))
algorithm = RNSGA2(
ref_points = np.array([[0.5, 0.2], [0.1, 0.6]]),
pop_size = 100,
epsilon = 0.01,
normalization = 'front',
eliminate_duplicates = True,
seed = args.seed,
sampling = X
)
# Solve problem
result = minimize(problem, algorithm,
termination = ('n_gen', args.generations),
# termination = ('time', '00:30:00'),
seed = args.seed,
save_history = args.violations,
verbose = True
)
return problem, result
def plot_results(problem, result):
pareto_front = problem.pareto_front(use_cache=False, flatten=False)
plot = Scatter(
title = "Pareto front",
labels=["1 / Minutes", "1 / Performance"]
)
plot.add(result.F)
plot.add(pareto_front, plot_type="line", color="black", alpha=0.7)
plot.show()
def plot_violations(result):
cv = []
for index, algorithm in enumerate(result.history):
cv.append([index, algorithm.opt.get('CV').min()])
cv = np.array(cv)
plot = Scatter(
title = "Constraint Violations",
labels=["Generation", "CV"]
)
plot.add(cv, plot_type="line")
plot.show()
# * --------------------
# * Main program
# * --------------------
if __name__ == '__main__':
args = parse_args()
print(args)
problem, result = run(args)
if result.F is None:
print('Could not find a solution')
exit()
print(f'\nFound {result.F.shape[0]} solutions')
# Plot
if args.pareto:
plot_results(problem, result)
if args.violations:
plot_violations(result)
Raw
problem.py
import numpy as np
from pymoo.model.problem import Problem
from pymoo.util.misc import stack
from util import get_allowed_quintets, get_partials, get_player_minutes
EPSILON = 0.5
class BasketballProblem(Problem):
def __init__(self, n_players=8, n_talented=2, simple_limits=True, seed=None):
self.n_players = n_players
self.n_talented = n_talented
self.simple_limits = simple_limits
self.quintets = get_allowed_quintets(self.n_players)
self.partials = get_partials(self.quintets, self.n_talented, seed=seed)
# Cada variable nos dice los minutos que juega cada quinteto
n_var = len(self.quintets)
# Cada jugador tiene dos restricciones (limites superior e inferior)
# y añadimos otra para que la suma total de minutos sea 40
n_constr = 2 * self.n_players + 1
super().__init__(
n_var = n_var,
n_obj = 2,
n_constr = n_constr,
xl = 0,
xu = 40,
elementwise_evaluation = True
)
def _evaluate(self, X, out, *args, **kwargs):
# Obtenemos los minutos que ha jugado cada jugador según el muestreo
player_minutes = get_player_minutes(self.quintets, X)
# ! Objetivo M: maximizar la cantidad de minutos que juegan los jugadores talentosos
# Incluímos '-' para minimizar
M = 1 / np.sum(player_minutes[:self.n_talented])
# Calculamos el valor que otorga cada quinteto en base a su parcial
performance = [minutes*partial for minutes, partial in zip(X, self.partials)]
# ! Objetivo R: maximizar el rendimiento de partido
# Incluímos '-' para minimizar
R = 1 / np.sum(performance)
# La suma total de minutos debe ser igual a 40. Para suavizar el problema,
# añadimos un épsilon que da lugar a "holgura"
# https://pymoo.org/misc/constraint_handling.html#Equality-to-Inequality-Constraints
total_minutes_constr = (sum(X) - 40)**2 - EPSILON
# Calculamos los límites de tiempo de cada jugador
if self.simple_limits:
lower_limits = [5] * self.n_players
upper_limits = [40] * self.n_players
else:
lower_limits = []
upper_limits = []
# Los jugadores talentosos juegan entre 5 y 40.
for i in range(self.n_talented):
lower_limits.append(5)
upper_limits.append(40)
# Los demás jugadores, tendrán la restricción basada en los anteriores
for i in range(self.n_talented, self.n_players):
previous_minutes = sum(player_minutes[:i])
remaining_players = self.n_players - (i+1)
lower = min(40, max(5, 200 - previous_minutes - 40 * remaining_players))
upper = max(5, min(40, 200 - previous_minutes - 5 * remaining_players))
lower_limits.append(lower)
upper_limits.append(upper)
# ! Restricciones
# ! - de minutos: la suma tiene que ser 40 minutos
# ! - de jugadores: dos por jugador para los límites
# Las desigualdades de los jugadores se cambian de signo para ser <= 0
C = np.concatenate((
[total_minutes_constr],
[lower-played for played, lower in zip(player_minutes, lower_limits)],
[played-upper for played, upper in zip(player_minutes, upper_limits)]
))
# ! Out
out['F'] = np.column_stack([M, R])
out['G'] = np.column_stack(C)
Raw
util.py
import random
def int_to_binary_string(_int: int, size: int) -> str:
"""Converts an integer into a string with its binary representation.
Args:
_int (int): The integer.
size (int): How much should the string be sized to (this adds leading
zeroes if less).
Returns:
str: The binary string.
"""
return format(_int, f'0{size}b')
def binary_string_to_int(_str: str) -> int:
"""Converts a binary string to the integer it represents.
Args:
_str (str): The binary string.
Returns:
int: The integer.
"""
return int(_str, 2)
def get_allowed_quintets(n_players: int) -> list:
"""Given a number of players, generates all the possible combinations of
quintets.
Args:
n_players (int): Number of players in the team.
Returns:
list<str>: List with binary strings representing the quintets. The strings
have a size of `n_players` and each bits represents whether that player
is in the quintet (value is '1') or not (value is '0').
"""
_ints = range(0, 2**n_players)
_strs = [int_to_binary_string(_int, n_players) for _int in _ints]
list_q = list(filter(lambda s: s.count('1') == 5, _strs))
return list_q
def get_partials(list_q: list, n_talented: int, seed: int = None) -> list:
"""Given a list of quintets and how many talented players there are in the team,
generate random partial values for each quintet. By default, these partials span
between [-2, 2]. If all the talented players are in the team, it spans [-1, 1].
Args:
list_q (list<str>): [description]
n_talented (int):
seed (int, optional): [description]. Defaults to None.
Returns:
list: [description]
"""
list_p = []
random.seed(seed)
for quinteto in list_q:
# La primera parte de la expresión selecciona los n primeros caracteres del
# quinteto. La segunda parte crea n '1's. Si estos valores son iguales,
# entonces los jugadores talentosos están en el equipo.
if quinteto[:n_talented] == '1'*n_talented:
parcial = random.random() * 2 + 1 # [1, 3]
else:
parcial = random.random() * 4 #- 2 # [0, 4]
parcial = round(parcial, 2)
list_p.append(parcial)
random.seed(None)
return list_p
def get_player_minutes(list_q: list, X: list) -> list:
"""Calculates the amount of minutes each player has played based on the quintets
and how many minutes each quintet plays.
Args:
list_q (list): List of quintets.
X (list): Minutes each quintet plays.
Returns:
list: Minutes each player plays.
"""
n_players = len(list_q[0])
list_m = []
for index in range(n_players):
qs = [int(q[index]) for q in list_q]
ms = [q*m for q, m in zip(qs, X)]
list_m.append(sum(ms))
return list_m
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment