Relative Percent Difference As A Loss Function For Sorting Algorithms
For this project we will write a sorting algorithm using Relative Percent Difference (RPD) as a loss function to sort items with random concentrations into groups with predetermined concentrations.
Hypothetical Problem
A processing facility has containers of leftover trim with weights ranging from 20g-30g, and cannabinoid concentrations ranging from 5%-35%. An algorithm is needed to determine how to to combine these containers into different bins to yield predetermined cannabinoid concentrations.
For example, combine 100 containers of trim with random weights and concentrations into five bins with targets of: 10%, 15%, 20%, 25%, and 30%. This is required so that the trim can be processed into accurately dosed products.
Container and Bin Classes
For starters we'll define classes that will represent the containers in the processing facilty.
We will use Object Oriented Programming (OOP) for this, so that we can create an instance of the class
for each container in the facilty. The Container() class needs two properties: weight
and percentage.
class Container:
def __init__(self, weight, percentage):
self.weight = weight
self.percentage = percentage
def get_info(self):
return {
'type':'container',
'weight':self.weight,
'percent':self.percentage
}
Next, let's create a class to represent the bins in the processing facility. The bins will need
weight and percentage properties, as well as target_percentage, a container_list holding the contents of the bin,
and the relative percent difference (RPD) between the percentage and the target_percentage. We'll also include
a few methods to help us use these properties.
class Bin:
def __init__(self, target_percentage):
self.capacity = 50
self.target_percentage = target_percentage
self.container_list = []
self.weight = 0
self.percentage = 0
self.rpd = self.calc_rpd(self.percentage)
def get_info(self):
return {
'type': 'bin',
'weight': self.weight,
'actual_percentage': self.percentage,
'target_percentage': self.target_percentage,
'RPD': self.rpd,
'capacity': str(len(self.container_list))+'/'+str(self.capacity)
}
def calc_rpd(self, percentage):
if self.target_percentage + percentage == 0:
return 0
avg = abs(self.target_percentage + percentage)/2
return abs(self.target_percentage - percentage)/avg*100
def evaluate_container(self, container):
if self.weight + container.weight == 0:
return 0, self.calc_rpd(0)
percent_wt = (self.weight * self.percentage) \
+ (container.weight * container.percentage)
eval_percentage = percent_wt / (self.weight + container.weight)
return eval_percentage, self.calc_rpd(eval_percentage)
def add_container(self, container):
self.container_list.append(container)
self.percentage, self.rpd = self.evaluate_container(container)
self.weight += container.weight
def remove_container(self):
removed_container = self.container_list.pop()
removed_container.weight *= -1
self.percentage, self.rpd = self.evaluate_container(removed_container)
self.weight += removed_container.weight
return removed_container
RPD Calculation
The Bin() class uses the following calculation to find RPD. a and b are the values
that are being compared. For this project, a and b are the percentage
and target_percentage properties of the Bin() class.
RPD = |a - b| / (|a + b|/2)
You can see form this calculation the the RPD will be 2, or 200%, if one value is 0 and the other is not.
You can also see that the RPD is undefined if a + b = 0. For these reasons, we will add a condition
to our calc_rpd() method to return an RPD of 0 when a + b = 0. Also, we will initialize
the sorting algorithm with a lowest_rpd variable set at 200%.
Create Lists Of Objects
For this project, we will sort 100 containers of trim with random weights and concentrations into five bins with targets of: 10%, 15%, 20%, 25%, and 30%. Let's create a list of containers and a list of bins:
bin_list = [Bin(10), Bin(15), Bin(20), Bin(25), Bin(30)]
container_list = [
Container(randint(20,30), randint(5,35))
for n in range(100)
]
RPD Sorting Algorithm
The RPD sorting algorithm iterates through every container in container_list
and evaluates them one at a time. Each container is added to the bin that yields
the lowest average RPD among all bins.
while len(container_list) > 0:
selected_container = container_list.pop()
rpd_list = [bin.rpd for bin in bin_list]
lowest_index = 0
lowest_rpd = 200
for i in range(len(bin_list)):
eval_list = copy(rpd_list)
eval_list[i] = bin_list[i].evaluate_container(selected_container)[1]
avg_rpd = sum(eval_list)/len(eval_list)
if avg_rpd < lowest_rpd:
lowest_index = i
lowest_rpd = avg_rpd
bin_list[lowest_index].add_container(selected_container)
Visualize The Sorting Algorithm
This visualization shows how the average RPD is reduced as containers are added to bins, and as the actual percentages converge on their targets. There are 100 frames in the visualization: one frame for each container that is sorted.
These are the results after sorting the containers shown in the visualization above:
[{
'type': 'bin',
'weight': 542,
'actual_percentage': 10.095940959409594,
'target_percentage': 10,
'RPD': 0.9548292324641942,
'capacity': '21/40'
},
{
'type': 'bin',
'weight': 77,
'actual_percentage': 15.0,
'target_percentage': 15,
'RPD': 0.0,
'capacity': '3/40'
},
{
'type': 'bin',
'weight': 858,
'actual_percentage': 20.06876456876457,
'target_percentage': 20,
'RPD': 0.343232787457472,
'capacity': '34/40'
},
{
'type': 'bin',
'weight': 461,
'actual_percentage': 25.071583514099782,
'target_percentage': 25,
'RPD': 0.28592470649395146,
'capacity': '18/40'
},
{
'type': 'bin',
'weight': 578,
'actual_percentage': 29.77854671280277,
'target_percentage': 30,
'RPD': 0.7409122482056026,
'capacity': '24/40'
}]
© alchemy.pub 2022 BTC: bc1qxwp3hamkrwp6txtjkavcsnak9dkj46nfm9vmef
