MusicScheduling EA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# *Music Scheduling using Evolutionary Algorithms*\n",
    "This notebook implements a music scheduling algorithm for generating playlists which have an exact length (e.g. 60 minutes) while respecting constraints, i.e. specific categories of playlist elements. This could be used to create playlists for radio stations which need to backtime to a specific point of time.\n",
    "\n",
    "## General\n",
    "For using the algorithm, different data is required.\n",
    "- playlistelements.csv\n",
    "- playliststructure.csv\n",
    "\n",
    "### playlistelements.csv\n",
    "The playlistelements.csv contains information about elements which can be placed into the playlist. More specifically, this is the length of the element in seconds, the category of the element and a unique identifier.\n",
    "\n",
    "### playliststructure.csv\n",
    "The playliststructure.csv maintains information about the desired playlist structure, i.e. which element has to be played at a specific point of time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _Data Generation_\n",
    "\n",
    "## Retrieve playlistelements.csv\n",
    "For now, we are going to retrieve a PlaylistElements from the [CORGIS Dataset Project](https://think.cs.vt.edu/corgis/csv/music/music.html). We download the original file and create a new csv file which contains only the necessary data.\n",
    "\n",
    "### Download File"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('playlistelementstmp.csv', <http.client.HTTPMessage at 0x20f7bb89588>)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Imports\n",
    "import urllib\n",
    "import urllib.request\n",
    "\n",
    "# Download file\n",
    "urllib.request.urlretrieve('https://think.cs.vt.edu/corgis/csv/music/music.csv?forcedownload=1', 'playlistelementstmp.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clean File / Create cleaned File"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tranformed and wrote 9999 rows and found 241 genres\n"
     ]
    }
   ],
   "source": [
    "# Imports\n",
    "import csv\n",
    "\n",
    "# Genre list. later used for playliststructure.csv\n",
    "genres = []\n",
    "\n",
    "def getgenre(fieldname):\n",
    "    if len(fieldname) > 0 and ' ' in fieldname:\n",
    "            return fieldname.split(' ')[0]\n",
    "    return fieldname\n",
    "\n",
    "fieldnames = ['artist', 'song', 'duration', 'genre']\n",
    "with open('playlistelementstmp.csv', newline='') as readcsv, open('playlistelements.csv', 'w', newline='') as writecsv:\n",
    "        csvreader = csv.DictReader(readcsv, delimiter=',')\n",
    "        csvwriter = csv.DictWriter(writecsv, delimiter=',', fieldnames=fieldnames)\n",
    "        csvwriter.writeheader()\n",
    "        for i, row in enumerate(csvreader):\n",
    "            genre = getgenre(row['artist_mbtags'])\n",
    "            csvwriter.writerow({'artist': row['artist.name'],\n",
    "                                'song': row['title'],\n",
    "                                'duration': round(float(row['duration'])),\n",
    "                                'genre': genre})\n",
    "            if len(genre) > 0:\n",
    "                genres.append(genre)\n",
    "        print('Tranformed and wrote', i, 'rows and found', len(set(genres)), 'genres')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create a playliststructure.csv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import random\n",
    "\n",
    "# Set seed for reproducability\n",
    "random.seed(1)\n",
    "\n",
    "# Number of elements\n",
    "NO_ELEMENTS = 20\n",
    "# Probability of 'any' element (== Any Element can be played)\n",
    "PROB_ANY = 0.45\n",
    "\n",
    "fieldnames = ['element_categorie']\n",
    "with open('playliststructure.csv', 'w', newline='') as writecsv:\n",
    "    csvwriter = csv.DictWriter(writecsv, delimiter=',', fieldnames=fieldnames)\n",
    "    csvwriter.writeheader()\n",
    "    for i in range(NO_ELEMENTS):\n",
    "        if random.random() <= PROB_ANY:\n",
    "            element_categorie = 'ANY' # ANY means we can put any song of any categorie in there!\n",
    "        else:\n",
    "            element_categorie = genres[random.randrange(0, len(genres))]\n",
    "        csvwriter.writerow({'element_categorie': element_categorie})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _Playlist Generation_\n",
    "\n",
    "Now this is where things get interesting: We are gonna create a playlist with evolutionary algorithms. Therefore we first load the elements and the playliststructure.\n",
    "\n",
    "## Read CSV Files"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ANY', 'soul', 'ANY', 'ANY', 'american', 'rock', 'ANY', 'british', 'american', 'uk', 'ANY', 'ANY', 'alternative', 'hip', 'classic', 'ANY', 'soul', 'hip', 'jazz', 'dancehall']\n"
     ]
    }
   ],
   "source": [
    "# Imports\n",
    "\n",
    "import csv\n",
    "import random\n",
    "\n",
    "playlist_structure = []\n",
    "playlist_elements = []\n",
    "playlist_categories = dict()\n",
    "\n",
    "with open('playliststructure.csv', 'r', newline='') as readstructure:\n",
    "    structurereader = csv.DictReader(readstructure, delimiter=',')\n",
    "    for r in structurereader:\n",
    "        playlist_structure.append(r['element_categorie'])\n",
    "        \n",
    "with open('playlistelements.csv', 'r', newline='') as readelements:\n",
    "    elementsreader = csv.DictReader(readelements, delimiter=',')\n",
    "    for i, r in enumerate(elementsreader):\n",
    "        if 'genre' in r:\n",
    "            genrelist = playlist_categories.get(r['genre'], [])\n",
    "            genrelist.append(i)\n",
    "            playlist_categories[r['genre']] = genrelist\n",
    "        playlist_elements.append(r)\n",
    "print(playlist_structure)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define Evolutionary Algorithms\n",
    "**General**\n",
    "This is subset sum problem, since we want to find a subset of the songs which are - in sum - exactly 60 Minutes long. Following wikipedia, this problem is [np-complete](https://en.wikipedia.org/wiki/Subset_sum_problem).\n",
    "\n",
    "### Generate Helping Functions\n",
    "The most important point is, that the helping functions need to respect the restrictions, i.e. the categories of the element (genre). Thus, they look more \"complex\" than the usual EA operations.\n",
    "\n",
    "**mutatation(solution, probability)***\n",
    "Mutates a given solution. The probability indicates, how likely it is that an element of the solution gets mutated. The mutation works like this: For each position in the solution, determine (randomized) if a mutation shall take place. If this is the case, look at the playlist_structure if any element can be fit there. In this case, just put one random element for the mutation. Otherwise add an element of the determined category.\n",
    "\n",
    "**crossover(solution0, solution1)***\n",
    "Performs a crossover of solution0 and solution1. For this, we talk the first half of soltion0 and fill up the rest of the child with the elements of solution1. However, we do this again considering the restrictions of the problem.\n",
    "\n",
    "**generatechild()***\n",
    "Generates a solution (TODO: change method name) for the given problem which resprects the restrictions.\n",
    "\n",
    "**evaluate(solution, maxlength)**\n",
    "Determines, how much a solution differs from the maximum length. We take the MSE for this.\n",
    "\n",
    "**validate(solution)**\n",
    "Checks if a solution respects the given restrictions. This is, however, only used in the summary of the EA result, since the EA methods themselve should respect the restrictions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Permutation changes one item of the solution to another one\n",
    "def mutation(solution, probability = 0.05):\n",
    "    for i in range(len(solution)):\n",
    "        if random.random() <= probability:\n",
    "            # Do permutation\n",
    "            while True:\n",
    "                if playlist_structure[i] == 'ANY':\n",
    "                    v = random.randrange(0, len(playlist_elements))\n",
    "                else:\n",
    "                    glist = playlist_categories[playlist_structure[i]]\n",
    "                    v = glist[random.randrange(0, len(glist))]\n",
    "                if not(v in solution):\n",
    "                    break\n",
    "            solution[i] = v\n",
    "    return solution\n",
    "\n",
    "def crossover(solution0, solution1):\n",
    "    # This crossover works like this\n",
    "    # We take the first half of solution0\n",
    "    # and then we try to add elements of solution1.\n",
    "    # If we are not able to add an element of solution1, i.e.\n",
    "    # because solution1 does not contain an element which is ok\n",
    "    # with the categorie-restrictions, we instead choose another element\n",
    "    # of the first solution0, so we do not violate the restrictions.\n",
    "    cutpoint = len(solution0) // 2\n",
    "    child = solution0[0:cutpoint]\n",
    "    changed = True\n",
    "    while len(child) != len(solution0):\n",
    "        if not(changed):\n",
    "            child.append(solution0[len(child)])\n",
    "            continue\n",
    "        changed = False\n",
    "        for x in solution1:\n",
    "            if x in child:\n",
    "                continue\n",
    "            # Get required type\n",
    "            req_type = playlist_structure[len(child)]\n",
    "            if req_type == 'ANY':\n",
    "                changed = True\n",
    "                child.append(x)\n",
    "            elif x in playlist_categories[req_type]:\n",
    "                changed = True\n",
    "                child.append(x)\n",
    "    return child\n",
    "\n",
    "def generatechild():\n",
    "    solution = []\n",
    "    for i in range(len(playlist_structure)):\n",
    "        while True:\n",
    "            if playlist_structure[i] == 'ANY':\n",
    "                v = random.randrange(0, len(playlist_elements))\n",
    "            else:\n",
    "                glist = playlist_categories[playlist_structure[i]]\n",
    "                v = glist[random.randrange(0, len(glist))]\n",
    "            if not(v in solution):\n",
    "                break\n",
    "        solution.append(v)\n",
    "    return solution\n",
    "\n",
    "def evaluate(solution, maxlength):\n",
    "    playlist_length = [int(x['duration']) for x in [playlist_elements[p] for p in solution]]\n",
    "    return abs(maxlength-sum(playlist_length))\n",
    "\n",
    "def validate(solution):\n",
    "    for i in range(len(solution)):\n",
    "        desired_type = playlist_structure[i]\n",
    "        if desired_type == 'ANY':\n",
    "            continue\n",
    "        else:\n",
    "            if solution[i] in playlist_categories[desired_type]:\n",
    "                continue\n",
    "        print('+++ INVALID SOLUTION! +++')\n",
    "        return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### EA\n",
    "\n",
    "The evolutionary algorithm itself. At the beginning we have some constraints and parameters for the EA.\n",
    "Then the EA proceeds:\n",
    "\n",
    " 1. Generate GEN_SIZE initial solutions\n",
    " 2. Evaluate the solutions and order the solution-array by their fitness (starting with the \"best\" solution, ending with the worst)\n",
    " 3. Perform a crossover by choosing a random solution from the best 10% of the solutions as parents*.\n",
    " 4. Perform a mutation on the child\n",
    " 4. Add the child to the solution pool.\n",
    " 5. Evaluate the solutions and order their solution-array by their fitness. Discard the worst solutions, so we keep the GEN_SIZE\n",
    " 6. Check if the best solution already has an MSE of 0 --> Terminate\n",
    " 7. Continue with (3), until MAX_EVAL is reached.\n",
    " \n",
    "Then, a summary of the best solution is printed.\n",
    "\n",
    "\\*: This is obviously not a good selection method, since we only select the best 10% (which is kinda against the EA idea). A fitness proportional solution would be much better. However, for now this is enough for my purposes and since the EA performs already very good with this \"naive\" selection, I am going to keep it like this. For greater projects another selection strategy should be choosen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 0 - Best Value - 100\n",
      "Generation 1 - Best Value - 6\n",
      "Generation 2 - Best Value - 1\n",
      "Generation 3 - Best Value - 0\n",
      "\n",
      "Best Solution:\n",
      "1 -- The Baltimore Consort -- You Lasses and Lads\n",
      "2 -- Steel Pulse -- We Can Do It\n",
      "3 -- Scar Symmetry -- The Illusionist\n",
      "4 -- Jerry Goldsmith -- The Keys\n",
      "5 -- Bobby Darin -- Hi De Ho\n",
      "6 -- John Mayall & The Bluesbreakers -- I'm Your Witchdoctor\n",
      "7 -- The Gone Jackals -- Faith Healer (Digital Single)\n",
      "8 -- Arctic Monkeys -- From The Ritz To The Rubble\n",
      "9 -- The Shirelles -- Dedicated To The One I Love\n",
      "10 -- UK Subs -- Crash Course\n",
      "11 -- Les Malpolis -- Les Amours de Nathalie\n",
      "12 -- Chris Clark -- Tyre\n",
      "13 -- Sick Puppies -- Master Of The Universe\n",
      "14 -- Erick Sermon -- Freak Out\n",
      "15 -- Kathy Mattea -- Isle Of Inishmore - Part 1 (Air)\n",
      "16 -- Danny Wright -- Walking in Faith_ Reprise\n",
      "17 -- Redman -- WKYA (drop)\n",
      "18 -- Fat Joe -- Get It Poppin' [Featuring Nelly]  (Album Version - Exp. Version) [Serban Main 4/20/05]\n",
      "19 -- Chico Hamilton -- Denise (Jeremy Carlstedt Funk Variation)\n",
      "20 -- Capleton -- Conscience Ah Heng Dem (interlude)\n",
      "Playlist-Length: 3600 seconds.\n",
      "Generation-Duration: 0.044005393981933594 seconds.\n",
      "Validation of Solution was successful? True\n"
     ]
    }
   ],
   "source": [
    "MAX_SUM = 60 * 60 #60 Seconds * 60 Minutes = 3600 Seconds\n",
    "GEN_SIZE = 100 # Amount of child\n",
    "MAX_EVAL = 100 # Maximum Evaluations\n",
    "\n",
    "#imports\n",
    "import time\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "solutions = [generatechild() for i in range(GEN_SIZE)]\n",
    "solution_evaluation = [evaluate(x, MAX_SUM) for x in solutions]\n",
    "sorted_indices = sorted(range(len(solution_evaluation)),key=lambda x:solution_evaluation[x])\n",
    "solutions = [solutions[x] for x in sorted_indices[0:GEN_SIZE]]\n",
    "\n",
    "for iteration in range(MAX_EVAL):\n",
    "    for i in range(GEN_SIZE):        #For now: Just take parents from the best 10%. --> Maybe change later!\n",
    "        #This differs strongly from general EAs, but for this task it is suitable.\n",
    "        parent1 = solutions[random.randrange(0, int(len(solutions) * .1))]\n",
    "        parent2 = solutions[random.randrange(0, int(len(solutions) * .1))]\n",
    "        co_child = crossover(parent1[:], parent2[:])\n",
    "        co_child = mutation(co_child, 0.1)\n",
    "        solutions.append(co_child)\n",
    "\n",
    "    solution_evaluation = [evaluate(x, MAX_SUM) for x in solutions]\n",
    "    sorted_indices = sorted(range(len(solution_evaluation)),key=lambda x:solution_evaluation[x])\n",
    "    #if iteration % 10 == 0:\n",
    "    print('Generation', iteration, '-', 'Best Value -', solution_evaluation[sorted_indices[0]])\n",
    "    solutions = [solutions[x] for x in sorted_indices[0:GEN_SIZE]]\n",
    "    if solution_evaluation[sorted_indices[0]] == 0:\n",
    "        break\n",
    "t1 = time.time()\n",
    "print()\n",
    "#print('Best Solution:', solutions[0])\n",
    "print('Best Solution:')\n",
    "for i,x in enumerate(solutions[0]):\n",
    "    print((i+1), '--', playlist_elements[x]['artist'], '--', playlist_elements[x]['song'] )\n",
    "print('Playlist-Length:', sum(int(playlist_elements[x]['duration']) for x in solutions[0]), 'seconds.')\n",
    "print('Generation-Duration:', t1-t0, 'seconds.')\n",
    "print('Validation of Solution was successful?', validate(solutions[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}