Online demo#
Please open via JuypterNoteBook / Jupyter Lab#
Five steps:
Implement a sampler
Implement a evaluator
Prepare a template heuristic
Choose the LLM-EPS method and complete the config, and run
Preparation: download the project file from GitHub. And update system path.#
Download code from GitHub.
[1]:
from __future__ import annotations
import sys
sys.path.append('../../')
from typing import Any, List
import llm4ad
from llm4ad.tools.profiler import TensorboardProfiler
from _obp_evaluate import evaluate
1. Implement a sampler#
The sampler defines the way to use local LLM or LLM API. You should create a new Sampler class by implementing llm4ad.base.Sampler.
You should implement “draw_sample” function, to let the package know how to get a LLM’s response by given a prompt.
If you want more acceleration (such as batch inference, multi-threading sampling) you can also override “draw_samples” function.
The following example shows a fake sampler, which returns a random function in the database.
[2]:
import pickle
import random
class FakeSampler(llm4ad.base.LLM):
"""We select random functions from rand_function.pkl
This sampler can help you debug your method even if you don't have an LLM API / deployed local LLM.
"""
def __init__(self):
super().__init__()
try:
with open('data/rand_function.pkl', 'rb') as f:
self._functions = pickle.load(f)
except:
with open('/content/py-llm4ad/example/online_bin_packing/data/rand_function.pkl', 'rb') as f:
self._functions = pickle.load(f)
def draw_samples(self, prompts: List[str | Any], *args, **kwargs) -> List[str]:
return super().draw_samples(prompts)
def draw_sample(self, prompt: str | Any, *args, **kwargs) -> str:
"""Generate an LLM response of the given prompt.
"""
return random.choice(self._functions)
[3]:
# test: get a sample
sampler = FakeSampler()
sample = sampler.draw_sample('Fake sampler does not need a prompt.')
print(sample)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
The following example shows a sampler that uses GPT-3.5-turbo API. If you want to use this sampler in this notebook, please complete following two variables.
[4]:
api_endpoint: str = '' # the ip of your API provider, no "https://", such as "api.bltcy.top".
api_key: str = '' # your API key which may start with "sk-......"
[5]:
import time
import http.client
import json
class MySampler(llm4ad.base.LLM):
def __init__(self):
super().__init__()
def draw_samples(self, prompts: List[str | Any], *args, **kwargs) -> List[str]:
return super().draw_samples(prompts)
def draw_sample(self, prompt: str | Any, *args, **kwargs) -> str:
while True:
try:
conn = http.client.HTTPSConnection(f'{api_endpoint}', timeout=30)
payload = json.dumps({
'max_tokens': 512,
'model': 'gpt-3.5-turbo',
'messages': [{'role': 'user', 'content': prompt}]
})
headers = {
'Authorization': f'Bearer {api_key}',
'User-Agent': 'Apifox/1.0.0 (https://apifox.com)',
'Content-Type': 'application/json'
}
conn.request('POST', '/v1/chat/completions', payload, headers)
res = conn.getresponse()
data = res.read().decode('utf-8')
data = json.loads(data)
response = data['choices'][0]['message']['content']
return response
except Exception as e:
print(e)
time.sleep(2)
continue
[6]:
# test 'MySampler' if you have an API key
if api_key != '' and api_endpoint != '':
sampler = MySampler()
response = sampler.draw_sample('Hello!')
print(response)
2. Implement an evaluator#
The evaluator defines how to evaluate the generated heuristic function. You should create a new Evaluator class by implementing llm4ad.base.Evaluator. You should override “evaluate_program” function to specify. Return None if the function is invalid.
The llm4ad.base.Evaluator class provide acceleration and safe evaluation methods. You can use them by simply setting respective arguments. The commonly used two argument are:
use_numba_accelerate: If set to True, we will wrap the heuristic function with ‘@numba.jit(nopython=True)’. Please note that not all functions support numba.jit(), so use it appropriately.timeout_second: Terminate the evaluation after timeout seconds. If set toNone, the evaluator will wait until the evaluation finish.
For more arguments, please refer to docstring in algo.base.Evaluator.
[7]:
class OBPEvaluator(llm4ad.base.Evaluation):
"""Evaluator for online bin packing problem."""
def __init__(self):
super().__init__(
use_numba_accelerate=True,
timeout_seconds=10,
task_description='',
template_program=''
)
try:
with open('data/weibull_train.pkl', 'rb') as f:
self._bin_packing_or_train = pickle.load(f)['weibull_5k_train']
except:
with open('/content/py-llm4ad/example/online_bin_packing/data/weibull_train.pkl', 'rb') as f:
self._bin_packing_or_train = pickle.load(f)['weibull_5k_train']
def evaluate_program(self, program_str: str, callable_func: callable) -> Any | None:
"""Evaluate a given function. You can use compiled function (function_callable),
as well as the original function strings for evaluation.
Args:
program_str: The function in string. You can ignore this argument when implementation.
callable_func: The callable Python function of your sampled heuristic function code.
You can call the program using 'program_callable(args..., kwargs...)'
Return:
Returns the fitness value. Return None if you think the result is invalid.
"""
# we call the _obp_evaluate.evaluate function to evaluate the callable code
return evaluate(self._bin_packing_or_train, callable_func)
[8]:
evaluator = OBPEvaluator()
secure_evaluator = llm4ad.base.SecureEvaluator(evaluator=evaluator, debug_mode=True)
[9]:
# test the evaluator
test_program = '''
import numpy as np
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
return bins - item
'''
res = secure_evaluator.evaluate_program(test_program)
print(res)
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
return bins - item
-5000.0
[10]:
# we test an invalid program
test_program = '''
import numpy as np
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
while True:
pass
'''
res = secure_evaluator.evaluate_program(test_program)
print(res)
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
while True:
pass
DEBUG: the evaluation time exceeds 10s.
None
3. Implement a template program#
[11]:
template_program = '''
import numpy as np
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
return item - bins
'''
4. Choose the LLM-EPS method and complete the config, and run#
Our package support multiprocess running. However, the Colab backend has limited CPU support, so we set num_evlauators to 2.
Common args in Config:
num_samplers: number of threads used in sampling.num_evaluators: number of processes used in evaluation (supports using multi-core CPUs).
[12]:
def run_randsample():
from llm4ad.method.randsample import RandSample
profiler = TensorboardProfiler(log_dir='')
randsample = RandSample(template_program, sampler, evaluator, profiler, max_sample_nums=10, debug_mode=True)
randsample.run()
def run_hillclimb():
from llm4ad.method.hillclimb import HillClimb
profiler = TensorboardProfiler(log_dir='')
hillclimb = HillClimb(template_program, sampler, evaluator, profiler, max_sample_nums=10)
hillclimb.run()
def run_funsearch():
from llm4ad.method.funsearch import FunSearch
profiler = TensorboardProfiler(log_dir='')
funsearch = FunSearch(template_program, sampler, evaluator, profiler, max_sample_nums=10)
funsearch.run()
def run_eoh():
# Please note that you can simply pass the template program without function body, such as:
# --------------------------------------------------------------------------------------------
# import numpy as np
#
# def priority(item: float, bins: np.ndarray) -> np.ndarray:
# """Returns priority with which we want to add item to each bin.
# Args:
# item: Size of item to be added to the bin.
# bins: Array of capacities for each bin.
# Return:
# Array of same size as bins with priority score of each bin.
# """
# pass
# --------------------------------------------------------------------------------------------
# This is because EoH can sample a valid code by sampling.
from llm4ad.method.eoh import EoH
profiler = TensorboardProfiler(log_dir='')
# You can choose to add some task descriptions or not.
task_description = """Please help me design a heuristic function for Online Bin Packing function. Given a item with its size S, the heuristic function finds the most suitable bin with remaining capacity C to pack it. We want to design a heuristic function that evaluate the priority of bins to which we want to assign the item to each bin."""
eoh = EoH(
task_description=task_description,
template_program=template_program,
max_generations=3,
sampler=sampler,
evaluator=evaluator,
profiler=profiler
)
eoh.run()
[13]:
# It should be noted that the if __name__ == '__main__' is required.
# Because the inner code uses multiprocess evaluation.
if __name__ == '__main__':
# you can also try other LLM-EPS methods.
run_randsample()
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
return item - bins
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
return item - bins
------------------------------------------------------
Score : -2088.6
Sample time : None
Evaluate time: 1.344438076019287
Sample orders: 1
------------------------------------------------------
Current best score: -2088.6
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
if item > bins.max():
raise ValueError('Item is larger than the maximum bin size')
scores = bins / (bins - item)
scores -= np.arange(len(bins)) ** 2 / 2
scores += bins + np.abs(bins - item)
scores /= item
scores = scores.min() + (scores - scores.min()) / (scores.max() - scores.min())
return scores
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.2
scores += 1.2 * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores -= 1.5 * item * len(bins)
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
return scores
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins + item)
scores[np.argmax(bins)] = 0
scores -= 0.8 * np.power(np.arange(1, len(bins) + 1), 2)
scores += bins * 1.4
scores += item / bins
if item < np.max(bins) and item > 0:
scores -= 0.5 * item
return scores
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.2
scores += 1.2 * bin_weight * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores -= item_weight * item * len(bins)
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
return scores
Failed in nopython mode pipeline (step: nopython frontend)
NameError: name 'bin_weight' is not defined
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.2
scores += 1.2 * bin_weight * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores -= item_weight * item * len(bins)
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
return scores
------------------------------------------------------
Score : None
Sample time : 3.886222839355469e-05
Evaluate time: 0.6960251331329346
Sample orders: 2
------------------------------------------------------
Current best score: -2088.6
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
max_capacity = bins.max()
penalty = np.arange(1, len(bins) + 1)
scores = bins / (bins - item) - penalty
max_capacity_bins = np.argpartition(bins, -1)[-1]
scores[max_capacity_bins] = -np.inf
scores = scores + max_capacity - item - np.abs(bins - max_capacity)
full_bins = np.where(bins >= max_capacity)
scores[full_bins] -= 2 * len(full_bins)
empty_bins = np.where(bins <= item)
scores[empty_bins] += bins[empty_bins] - item
similar_size_bins = np.where(np.abs(bins - item) <= item)
scores[similar_size_bins] += bins[similar_size_bins] - item
return scores.astype(np.int64)
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins + item)
scores[np.argmax(bins)] = 0
scores -= 0.8 * np.power(np.arange(1, len(bins)+1), 2)
scores += bins * 1.4 # We increase the score of bins with large capacities
scores += item / bins # We adjust for the item size, but only if it's smaller than bins
if item < np.max(bins) and item > 0: # We add a penalty for item size, but only if it's smaller than bins and greater than 0
scores -= 0.5 * item
return scores
------------------------------------------------------
Score : -2164.0
Sample time : 2.5987625122070312e-05
Evaluate time: 3.1523659229278564
Sample orders: 3
------------------------------------------------------
Current best score: -2088.6
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.1
scores += 1.2 * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores -= 1.5 * item * len(bins)
min_score, max_score = (np.min(scores), np.max(scores))
scores = (scores - min_score) / (max_score - min_score)
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
# Penalty for bins with larger capacities
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
# Reduce the scores to allow larger numbers
scores /= 1.2
# Give bins with larger capacities higher scores
scores += 1.2 * bins
# Give the first item in bins a small penalty to ensure even distribution of items
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
# Subtract a penalty that seems to favor items that fit in bins with larger capacities
scores -= 1.5 * item * len(bins)
# Normalize the scores to be between 0 and 1
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
return scores
------------------------------------------------------
Score : -2020.8
Sample time : 8.0108642578125e-05
Evaluate time: 3.732250213623047
Sample orders: 4
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0]
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins)
penalty = np.arange(len(non_empty_bins), 0, -1) ** 2
scores = non_empty_bins / (non_empty_bins - item) - penalty
max_capacity = non_empty_bins.max()
scores = max_capacity - scores
scores[bins > 0] -= 0.001 * len(bins)
scores += 0.5 * bins / max_capacity
scores -= (np.sum(bins[bins > 0]) / max_capacity) ** 2
item_counts = bins / max_capacity
scores += 0.01 * item_counts ** 2
scores *= (1 - 0.1 * item_counts / max_capacity) ** 2
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
if item > bins.max():
raise ValueError("Item is larger than the maximum bin size")
scores = bins / (bins - item)
# Add penalty based on the bin index
scores -= np.arange(len(bins)) ** 2 / 2
# Add priority based on bin size and item size difference
scores += bins + np.abs(bins - item)
# Normalize the scores related to the item size
scores /= item
# Improve normalization, such that less than average is better
scores = scores.min() + (scores - scores.min()) / (scores.max() - scores.min())
return scores
------------------------------------------------------
Score : -2022.2
Sample time : 0.00017595291137695312
Evaluate time: 3.7596330642700195
Sample orders: 5
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
if item > np.max(bins):
raise ValueError('Item size exceeds bin capacities!')
scores = bins / (bins - item)
max_bin_index = np.argmax(bins)
scores[max_bin_index] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.2
scores += 1.2 * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores += 1.5 * item * len(bins)
min_scores = np.min(scores)
if min_scores < 0:
scores -= min_scores
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.1
scores += 1.2 * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores -= 1.5 * item * len(bins)
# Normalize scores to be between 0 and 1
min_score, max_score = np.min(scores), np.max(scores)
scores = (scores - min_score) / (max_score - min_score)
return scores
------------------------------------------------------
Score : -2022.0
Sample time : 8.225440979003906e-05
Evaluate time: 3.519761800765991
Sample orders: 6
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
penalty = np.arange(len(bins), 0, -1)
scores_v0 = bins / (bins - item) - penalty
scores_v1 = bins / (bins + item)
return scores_v0 + scores_v1
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
if item > np.max(bins):
raise ValueError("Item size exceeds bin capacities!")
scores = bins / (bins - item)
max_bin_index = np.argmax(bins)
scores[max_bin_index] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores /= 1.2
scores += 1.2 * bins
scores += 0.5 * (np.arange(len(bins)) * (len(bins) - np.arange(len(bins))))
scores += 1.5 * item * len(bins)
min_scores = np.min(scores)
if min_scores < 0:
scores -= min_scores
return scores
------------------------------------------------------
Score : -2020.8
Sample time : 0.00011110305786132812
Evaluate time: 3.5252459049224854
Sample orders: 7
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0]
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins)
penalty = np.arange(len(non_empty_bins), 0, -1) ** 2
scores = non_empty_bins / (non_empty_bins - item) - penalty
max_capacity = non_empty_bins.max()
scores = scores + max_capacity - np.abs(non_empty_bins - max_capacity) - 1e-05 * len(bins)
scores[bins > 0] -= 0.001 * np.sum(bins[bins > 0])
scores += bins / max_capacity
scores -= np.sum(bins[bins > 0]) / max_capacity
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0]
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins) # all bins are empty
# compute the penalty
penalty = np.arange(len(non_empty_bins), 0, -1) ** 2
scores = non_empty_bins / (non_empty_bins - item) - penalty
# normalize the scores
max_capacity = non_empty_bins.max()
scores = max_capacity - scores # we want to maximize the remaining capacity in the bins
scores[bins > 0] -= 1e-3 * len(bins) # but we also want to minimize the filling rate of occupied bins
# add more criteria to the score
scores += 0.5 * bins / max_capacity # distribute items equally to all bins at the same rate
scores -= (np.sum(bins[bins > 0]) / max_capacity)**2 # we want to minimize the total filling rate
# calculate the number of items in each bin
item_counts = bins / max_capacity
# add more scores to bins with too many items
scores += 1e-2 * item_counts**2 # we want to distribute items more evenly
# add more criteria to the score
scores *= (1 - 0.1 * item_counts/max_capacity)**2 # we want to keep a small buffer for future items
return scores
------------------------------------------------------
Score : -2117.0
Sample time : 6.103515625e-05
Evaluate time: 4.2456042766571045
Sample orders: 8
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0]
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins)
scores = non_empty_bins / (non_empty_bins + item)
scores -= 1e-05 * len(bins) * np.ones_like(bins)
return -scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
max_capacity = bins.max()
penalty = np.arange(1, len(bins) + 1)
scores = bins / (bins - item) - penalty
max_capacity_bins = np.argpartition(bins, -1)[-1]
scores[max_capacity_bins] = -np.inf
scores = scores + max_capacity - item - np.abs(bins - max_capacity)
# Penalize bins that are too full
full_bins = np.where(bins >= max_capacity)
scores[full_bins] -= 2 * len(full_bins)
# Give more priority to bins that are nearly empty
empty_bins = np.where(bins <= item)
scores[empty_bins] += bins[empty_bins] - item
# Prefer bins that have similar size to the item
similar_size_bins = np.where(np.abs(bins - item) <= item)
scores[similar_size_bins] += bins[similar_size_bins] - item
return scores.astype(np.int64)
------------------------------------------------------
Score : -2070.6
Sample time : 0.00020885467529296875
Evaluate time: 7.351511001586914
Sample orders: 9
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
max_capacity = bins.max()
penalty = np.arange(len(bins), 0, -1)
scores = bins / (bins - item) - penalty
scores = scores + np.minimum(bins, max_capacity)
max_indices = np.where(bins == max_capacity)[0]
scores[max_indices] -= 0.001 * len(bins)
item_indices = np.where(bins == item)[0]
scores[item_indices] += 100
scores -= penalty
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
penalty = np.arange(len(bins), 0, -1)
scores_v0 = bins / (bins - item) - penalty
scores_v1 = bins / (bins + item)
# Returns the sum of the original calculated scores and a new score.
return scores_v0 + scores_v1
------------------------------------------------------
Score : -2085.6
Sample time : 5.91278076171875e-05
Evaluate time: 1.9645700454711914
Sample orders: 10
------------------------------------------------------
Current best score: -2020.8
======================================================
DEBUG: evaluated program:
import numba
import numpy as np
@numba.jit(nopython=True)
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
scores[np.argmax(bins)] = 0
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
scores += 0.8 * bins
scores += 0.5 * (np.arange(len(bins)) + 1)
scores -= 1.2 * item * len(bins)
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
return scores
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0] # get bins with items in them
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins) # all bins are empty
# calculate scores based on item size and available capacity
scores = non_empty_bins / (non_empty_bins + item)
# prevent divide by zero errors
scores -= 1e-5 * len(bins) * np.ones_like(bins)
return -scores # return negative scores for minimization objective
------------------------------------------------------
Score : -2088.6
Sample time : 5.1021575927734375e-05
Evaluate time: 2.181065797805786
Sample orders: 11
------------------------------------------------------
Current best score: -2020.8
======================================================
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
max_capacity = bins.max()
penalty = np.arange(len(bins), 0, -1)
# No need to check if max_capacity > item, as you'd otherwise divide by zero
scores = bins / (bins - item) - penalty
# Use np.minimum to ensure priority scores do not exceed maximum capacity
scores = scores + np.minimum(bins, max_capacity)
max_indices = np.where(bins == max_capacity)[0]
scores[max_indices] -= 1e-3 * len(bins) # To prevent divide by zero errors
# If item fits exactly in a bin, give a higher priority: Increase the score
item_indices = np.where(bins == item)[0]
scores[item_indices] += 100
# Favor filling to lower capacities: Subtract the original penalty
scores -= penalty
return scores
------------------------------------------------------
Score : -2030.6
Sample time : 8.225440979003906e-05
Evaluate time: 3.0832607746124268
Sample orders: 12
------------------------------------------------------
Current best score: -2020.8
======================================================
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
non_empty_bins = bins[bins > 0]
if len(non_empty_bins) == 0:
return -np.inf * np.ones_like(bins) # all bins are empty
# compute the penalty
penalty = np.arange(len(non_empty_bins), 0, -1) ** 2
scores = non_empty_bins / (non_empty_bins - item) - penalty
# normalize the scores
max_capacity = non_empty_bins.max()
scores = scores + max_capacity - np.abs(non_empty_bins - max_capacity) - 1e-5 * len(bins)
scores[bins > 0] -= 1e-3 * np.sum(bins[bins > 0]) # less penalty for bins with items
# add more criteria to the score
scores += bins / max_capacity
scores -= np.sum(bins[bins > 0]) / max_capacity
return scores
------------------------------------------------------
Score : -2030.2
Sample time : 7.390975952148438e-05
Evaluate time: 4.0933449268341064
Sample orders: 13
------------------------------------------------------
Current best score: -2020.8
======================================================
================= Evaluated Function =================
def priority(item: float, bins: np.ndarray) -> np.ndarray:
"""Returns priority with which we want to add item to each bin.
Args:
item: Size of item to be added to the bin.
bins: Array of capacities for each bin.
Return:
Array of same size as bins with priority score of each bin.
"""
scores = bins / (bins - item)
# Score for bins with maximum capacity is zero
scores[np.argmax(bins)] = 0
# Subtract smaller penalty based on the bin index using quadratic function
# This ensures that bins with lower capacities have a higher score
scores -= 0.7 * np.square(np.arange(1, len(bins) + 1))
# Fine tune the score distribution by adding bins size score
scores += 0.8 * bins
# Add an extra factor based on bin index
scores += 0.5 * (np.arange(len(bins)) + 1)
# Subtract item capacity times bins length to ensure bins with item
# capacity are given zero score
scores -= 1.2 * item * len(bins)
# Normalize scores to be between 0 and 1
scores = (scores - np.min(scores)) / (np.max(scores) - np.min(scores))
# Return the final scores
return scores
------------------------------------------------------
Score : -2029.4
Sample time : 0.00032591819763183594
Evaluate time: 3.3694519996643066
Sample orders: 14
------------------------------------------------------
Current best score: -2020.8
======================================================
[ ]: