Music playlist generation by adapted simulated annealing

Steffen Pauws*, Wim Verhaegh, Mark Vossen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)

Abstract

We present the design of an algorithm for use in an interactive music system that automatically generates music playlists that fit the music preferences of a user. To this end, we introduce a formal model, define the problem of automatic playlist generation (APG), and prove its NP-hardness. We use a local search (LS) procedure employing a heuristic improvement to standard simulated annealing (SA) to solve the APG problem. In order to employ this LS procedure, we introduce an optimization variant of the APG problem, which includes the definition of penalty functions and a neighborhood structure. To improve upon the performance of the standard SA algorithm, we incorporated three heuristics referred to as song domain reduction, partial constraint voting, and a two-level neighborhood structure. We evaluate the developed algorithm by comparing it to a previously developed approach based on constraint satisfaction (CS), both in terms of run time performance and quality of the solutions. For the latter we not only considered the penalty of the resulting solutions, but we also performed a conclusive user evaluation to assess the subjective quality of the playlists generated by both algorithms. In all tests, the LS algorithm was shown to be a dramatic improvement over the CS algorithm. (c) 2007 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)647-662
Number of pages16
JournalInformation Sciences
Volume178
Issue number3
DOIs
Publication statusPublished - 1 Feb 2008
Externally publishedYes

Keywords

  • local search
  • simulated annealing
  • music playlist generation
  • music retrieval

Cite this