Music playlist generation by adapted simulated annealing

Steffen Pauws*, Wim Verhaegh, Mark Vossen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Citations (Scopus)


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
Issue number3
Publication statusPublished - 1 Feb 2008
Externally publishedYes


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


Dive into the research topics of 'Music playlist generation by adapted simulated annealing'. Together they form a unique fingerprint.

Cite this