Music playlist generation by adapted simulated annealing

Steffen Pauws*, Wim Verhaegh, Mark Vossen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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

Pauws, Steffen ; Verhaegh, Wim ; Vossen, Mark. / Music playlist generation by adapted simulated annealing. In: Information Sciences. 2008 ; Vol. 178, No. 3. pp. 647-662.
@article{a08387ce5d6144828f20650b4861e771,
title = "Music playlist generation by adapted simulated annealing",
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.",
keywords = "local search, simulated annealing, music playlist generation, music retrieval",
author = "Steffen Pauws and Wim Verhaegh and Mark Vossen",
year = "2008",
month = "2",
day = "1",
doi = "10.1016/j.ins.2007.08.019",
language = "English",
volume = "178",
pages = "647--662",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Science Inc.",
number = "3",

}

Music playlist generation by adapted simulated annealing. / Pauws, Steffen; Verhaegh, Wim; Vossen, Mark.

In: Information Sciences, Vol. 178, No. 3, 01.02.2008, p. 647-662.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Music playlist generation by adapted simulated annealing

AU - Pauws, Steffen

AU - Verhaegh, Wim

AU - Vossen, Mark

PY - 2008/2/1

Y1 - 2008/2/1

N2 - 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.

AB - 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.

KW - local search

KW - simulated annealing

KW - music playlist generation

KW - music retrieval

U2 - 10.1016/j.ins.2007.08.019

DO - 10.1016/j.ins.2007.08.019

M3 - Article

VL - 178

SP - 647

EP - 662

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 3

ER -