Skip to content

Instantly share code, notes, and snippets.

@filyp

filyp/group_allocate.ipynb

Created December 3, 2022 19:10
Show Gist options
  • Save filyp/c3fa06d5a7a898047d5f9b71f83820ba to your computer and use it in GitHub Desktop.
Save filyp/c3fa06d5a7a898047d5f9b71f83820ba to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
group_allocate.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# %%html\n",
"# <style>\n",
"# .cell-output-ipywidget-background {\n",
"# background-color: transparent !important;\n",
"# }\n",
"# .jp-OutputArea-output {\n",
"# background-color: transparent;\n",
"# } \n",
"# </style>"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import ipywidgets\n",
"import numpy as np\n",
"\n",
"# make np print options wider\n",
"np.set_printoptions(linewidth=200)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"choice_names = [\n",
" \"Malaria Consortium\",\n",
" \"The Humane League\",\n",
" \"Wild Animal Initiative\",\n",
" \"Nuclear Threat Initiative (Biosecurity)\",\n",
" \"StrongMinds\",\n",
" \"Otwarte Klatki\",\n",
" \"Invincible Wellbeing\",\n",
" \"Center on Long-term Risk\",\n",
" \"GovAI\",\n",
" \"Center for Human-Compatible AI\",\n",
" \"Johns Hopkins Center for Health Security\",\n",
"]\n",
"\n",
"choice_shortcuts = [\n",
" \"Malaria\",\n",
" \"Hum_Lea\",\n",
" \"Wild_An\",\n",
" \"Nuc_Thr\",\n",
" \"Str_Min\",\n",
" \"Otw_Kla\",\n",
" \"Inv_Wel\",\n",
" \"CLR____\",\n",
" \"GovAI__\",\n",
" \"CHAI___\",\n",
" \"Hopkins\",\n",
"]"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "e881767a89f7456cbe03c12267392c95",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"VBox(children=(Text(value='', description='Name'), Checkbox(value=False, description='Malaria Consortium'), Ch…"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# create a list of checkboxes for each choice\n",
"checkboxes = [ipywidgets.Checkbox(description=choice) for choice in choice_names]\n",
"\n",
"# create a name text field\n",
"name = ipywidgets.Text(description=\"Name\")\n",
"\n",
"# create a button to submit the form\n",
"submit = ipywidgets.Button(description=\"Submit\")\n",
"\n",
"# combine the widgets into a form\n",
"form = ipywidgets.VBox([name] + checkboxes + [submit])\n",
"\n",
"names = []\n",
"choices = []\n",
"\n",
"\n",
"def on_submit(sender):\n",
" names.append(name.value)\n",
" personal_choices_binary = [checkbox.value for checkbox in checkboxes]\n",
" choices.append(personal_choices_binary)\n",
" # clear the form\n",
" name.value = \"\"\n",
" for checkbox in checkboxes:\n",
" checkbox.value = False\n",
"\n",
"submit.on_click(on_submit)\n",
"\n",
"form"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def group_quality(group_choices):\n",
" quality = 0\n",
" for i in range(len(group_choices)):\n",
" for j in range(i):\n",
" match = group_choices[i] * group_choices[j]\n",
" # print(sum(match))\n",
" quality += sum(match)\n",
" return quality\n",
"\n",
"\n",
"def global_quality(group_assignments, num_of_groups, choices_arr):\n",
" quality = 0\n",
" for group_num in range(num_of_groups):\n",
" group_choices = choices_arr[group_assignments == group_num]\n",
" quality += group_quality(group_choices)\n",
" return quality\n",
"\n",
"\n",
"# randomly swap two people\n",
"def swap_people(group_assignments):\n",
" num_of_people = len(group_assignments)\n",
" new_assignments = group_assignments.copy()\n",
" i = np.random.randint(num_of_people)\n",
" j = np.random.randint(num_of_people)\n",
" new_assignments[i], new_assignments[j] = new_assignments[j], new_assignments[i]\n",
" return new_assignments"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [],
"source": [
"def simulated_annealing(names, choices, num_of_groups=3, verbose=False, cooldown_len=1000, starting_temperature=0.5):\n",
" num_of_people = len(names)\n",
" choices_arr = np.array(choices)\n",
"\n",
" # assign [0, 1, 2, 0, 1, 2, ...]\n",
" group_assignments = np.tile(np.arange(num_of_groups), num_of_people // num_of_groups + 1)[:num_of_people]\n",
"\n",
" # shuffle the group assignments\n",
" np.random.shuffle(group_assignments)\n",
"\n",
" current_quality = global_quality(group_assignments, num_of_groups, choices_arr)\n",
" for i in range(cooldown_len + 100):\n",
" # epsilon starts at starting_temperature and decays to 0 at the end of cooldown_len\n",
" epsilon = max(starting_temperature * (1 - i / cooldown_len), 0)\n",
" new_assignments = swap_people(group_assignments)\n",
" new_quality = global_quality(new_assignments, num_of_groups, choices_arr)\n",
" # with probability epsilon, accept the new assignments\n",
" randomly_swap = (np.random.rand() < epsilon)\n",
" quality__swap = (new_quality > current_quality)\n",
" if randomly_swap or quality__swap:\n",
" group_assignments = new_assignments\n",
" current_quality = new_quality\n",
" \n",
" if verbose:\n",
" iter_type = \"quality\" if quality__swap else (\"rand\" if randomly_swap else \"\")\n",
" print(f\"iteration {i:4}, quality {current_quality:3}, group assignments {group_assignments}, epsilon {epsilon:.3f}, {iter_type}\")\n",
" \n",
" return group_assignments, current_quality"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0 0 1 1 0 2 1 2] 14\n",
"[2 2 0 0 1 1 0 1] 17\n",
"[2 2 0 0 1 1 0 1] 17\n",
"[0 0 1 1 0 2 1 2] 14\n",
"[2 2 0 0 1 1 0 1] 17\n",
"[0 0 1 1 0 2 1 2] 14\n",
"[0 0 2 2 0 1 1 1] 15\n",
"[0 0 1 1 0 2 1 2] 14\n",
"[0 0 1 1 0 2 1 2] 14\n",
"[1 1 2 2 1 0 0 0] 15\n",
"\n",
"best quality: 17\n",
"best assignments: [2 2 0 0 1 1 0 1]\n"
]
}
],
"source": [
"# find the best of some num of runs\n",
"num_of_runs = 10\n",
"num_of_groups = 3\n",
"\n",
"best_quality = 0\n",
"best_assignments = None\n",
"for i in range(num_of_runs):\n",
" assignments, quality = simulated_annealing(names, choices, num_of_groups=num_of_groups, verbose=False, cooldown_len=1000, starting_temperature=0.5)\n",
" print(assignments, quality)\n",
" if quality > best_quality:\n",
" best_quality = quality\n",
" best_assignments = assignments\n",
"\n",
"print()\n",
"print(\"best quality:\", best_quality)\n",
"print(\"best assignments:\", best_assignments)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"Group 0:\n",
"c Nuc_Thr Str_Min Otw_Kla \n",
"d Str_Min Otw_Kla CLR____ \n",
"g Str_Min Otw_Kla Inv_Wel GovAI__ CHAI___ \n",
"\n",
"Group 1:\n",
"e Wild_An Nuc_Thr Str_Min Inv_Wel CLR____ GovAI__ \n",
"f Inv_Wel CLR____ GovAI__ \n",
"h Hum_Lea Inv_Wel CLR____ GovAI__ CHAI___ \n",
"\n",
"Group 2:\n",
"a Malaria Hum_Lea Wild_An \n",
"b Hum_Lea Wild_An Nuc_Thr \n"
]
}
],
"source": [
"# print the final group assignments\n",
"names_arr = np.array(names)\n",
"choices_arr = np.array(choices)\n",
"for group_num in range(num_of_groups):\n",
" group_names = names_arr[best_assignments == group_num]\n",
" this_groups_choices = choices_arr[best_assignments == group_num]\n",
" print(f\"\\nGroup {group_num}:\")\n",
" for name, persons_choices in zip(group_names, this_groups_choices):\n",
" print(f\"{name:20}\", end=\"\")\n",
" for choice, shortcut in zip(persons_choices, choice_shortcuts):\n",
" if choice:\n",
" print(f\"{shortcut:9}\", end=\"\")\n",
" else:\n",
" print(\" \" * 9, end=\"\")\n",
" print()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.10.7 64-bit",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.7"
},
"orig_nbformat": 4,
"vscode": {
"interpreter": {
"hash": "e7370f93d1d0cde622a1f8e1c04877d8463912d04d973331ad4851f04de6915a"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment