Trovare la migliore combinazione di set che dà il numero massimo di oggetti unici

Puoi usare algoritmi genetici con una semplice rappresentazione binaria per gli individui:

individual = 01010100000111000011010111001110

Ogni luogo di un individuo è correlato alle registrazioni di uno spettacolo specifico. Se:

individual[k] == 1

quindi comprerai l'album k-th .

Dovresti codificare due / tre funzioni:

unique_songs(individual) = number of unique songs

duplicates(individual) = number of duplicates

cost(individual) = total purchase cost

La funzione fitness è qualcosa come:

fitness(individual) =        unique_songs(individual)
                      - k1 *   duplicates(individual)
                      - k2 *         cost(individual)

k1 / k2 devono essere sintonizzati. Questo tratterà duplicates(individual) come un vincolo software .

Se vuoi il maggior numero di brani possibile con un numero massimo fisso di duplicati ( limit ) hai bisogno di un vincolo rigido . L'approccio più semplice sta cambiando l'idoneità da un valore scalare a un vettore bidimensionale:

fitness(individual) = [-penalty(individual),
                       unique_songs(individual) - k * cost(individual)]


                       / duplicates(individual) - limit   constraint not satisfied
penalty(individual) = {
                       \ 0                                otherwise

Per ulteriori dettagli su questo approccio puoi leggere Un metodo efficiente di gestione dei vincoli per gli algoritmi genetici - Kalyanmoy Deb.

È possibile utilizzare la stessa libreria / framework, basta cambiare l'operatore di confronto del fitness in una confronto lessicografico .

La ricottura simulata è una tecnica utile per generare risultati approssimativi per problemi computazionalmente difficili in cui è facile determinare se una soluzione potenziale è migliore di un'altra.

Nel modo più semplice, scegli una soluzione casuale e generi una piccola modifica (ad esempio, scambiando una registrazione con un'altra) e vedi se questo ti ha avvicinato al risultato. Se è così, mantieni la nuova soluzione e ripeti. In caso contrario, hai comunque la possibilità casuale di accettare il cambiamento. Il processo è governato da una variabile "temperatura" che diminuisce all'approssimarsi del limite di iterazione; la possibilità di accettare un cambiamento meno ottimale si riduce man mano che la temperatura diminuisce. Oltre a tracciare la soluzione corrente, tieni traccia della migliore soluzione in assoluto.

Per molti tipi di problemi, questo approccio di solito converge in un'approssimazione ragionevole della soluzione migliore.

Se hai un limite al numero di album che sei disposto ad acquistare e quel numero non è grande, penso che ci sia un approccio abbastanza semplice. Per prima cosa si desidera creare una funzione distanza tra un set e l'altro. Al livello più semplice, è il numero di brani che non sono presenti in entrambi i set. Dici che vuoi limitare il numero di duplicati, ma io lo interrogo perché potrebbe anche limitare il numero di brani diversi con cui finisci. Ad esempio, se una registrazione ha tutte le nuove canzoni tranne una che hai già un sacco di volte, la rifiuterai e possibilmente sceglierai un album con pochissime nuove canzoni. Dato l'artista, immagino che alcune canzoni (ad esempio "Born in the USA", "Born to Run", "Born ...") si presenteranno molto spesso se non in ogni registrazione.

Una volta ottenuto questo calcolo. Prendi le tue due registrazioni e le unisci in un unico set. Calcola la distanza di quel set e ogni altra registrazione. Quindi prendi quei set e ripeti fino a raggiungere il numero massimo di registrazioni che sei disposto ad acquistare.

Potrebbe essere molto costoso se sei disposto a comprare molte registrazioni e non sono sicuro di quante ce ne siano ma suona come un mucchio. Se ciò richiederà troppo tempo, puoi scegliere i set iniziali in base al loro punteggio per ogni iterazione. Non è garantito che otterrai il risultato migliore in questo modo, ma probabilmente sarà molto vicino.

Ecco un esempio per dimostrare perché potresti non voler impostare un limite rigido per i duplicati:

Supponiamo che il tuo set iniziale sia:

Apple
Banana
Carrot
Durian

E hai i seguenti 4 set tra cui scegliere.

Apple       Apple        Banana  Carrot
Escarole    Horseradish  Durian  Escarole
Fig         Jalapeno        
Grapefruit  Kale        
            Lemon       

E vuoi selezionare i 2 set migliori tra questi quattro da aggiungere al tuo set. Ecco le 6 opzioni:

 1 & 2          1 & 3     1 & 4
Apple       3  Apple  2  Apple    2
Banana      1  Banana 2  Banana   2
Carrot      1  Carrot 1  Carrot   2
Durian      1  Durian 2  Durian   1
Escarole    1            Escarole 1
Fig         1           
Grapefruit  1           
Horseradish 1           
Jalapeno    1           
Kale        1           
Lemon       1           

 2 & 3          2 & 4          3 & 4    
Apple       2  Apple       2  Apple    1
Banana      2  Banana      1  Banana   2
Carrot      1  Carrot      2  Carrot   2
Durian      2  Durian      1  Durian   2
Horseradish 1  Horseradish 1  Escarole 1
Jalapeno    1  Jalapeno    1        
Kale        1  Kale        1        
Lemon       1  Lemon       1        
               Escarole    1        

Ora diciamo che hai iniziato con la regola che nessun elemento può essere ripetuto più di due volte. Questo escluderebbe l'opzione di 1 & 2. Direi che esclude l'opzione migliore dal momento che fornisce il maggior numero di oggetti unici.

Ovviamente questo è un esempio forzato, ma poiché ottieni molti set in cui appaiono spesso gli stessi valori, questa situazione diventa più probabile.

Questo mi sembra una variazione del problema dello zaino per me. Ho risolto il problema con la Jenetics libreria di Google:

import static java.util.Objects.requireNonNull;

import java.util.function.Function;
import java.util.stream.Collectors;

import org.jenetics.BitGene;
import org.jenetics.engine.Codec;
import org.jenetics.engine.Engine;
import org.jenetics.engine.EvolutionResult;
import org.jenetics.engine.Problem;
import org.jenetics.engine.codecs;
import org.jenetics.util.ISeq;

public class Springsteen
    implements Problem<ISeq<Springsteen.Record>, BitGene, Double>
{

    public static final class Record {
        final String name;
        final double price;
        final ISeq<String> songs;

        public Record(
            final String name,
            final double price,
            final ISeq<String> songs
        ) {
            this.name = requireNonNull(name);
            this.price = price;
            this.songs = requireNonNull(songs);
        }
    }

    private final ISeq<Record> _records;
    private final double _maxPricePerUniqueSong;

    public Springsteen(final ISeq<Record> records, final double maxPricePerUniqueSong) {
        _records = requireNonNull(records);
        _maxPricePerUniqueSong = maxPricePerUniqueSong;
    }

    @Override
    public Function<ISeq<Record>, Double> fitness() {
        return records -> {
            final double cost = records.stream()
                .mapToDouble(r -> r.price)
                .sum();

            final int uniqueSongCount = records.stream()
                .flatMap(r -> r.songs.stream())
                .collect(Collectors.toSet())
                .size();

            final double pricePerUniqueSong = cost/uniqueSongCount;

            return pricePerUniqueSong <= _maxPricePerUniqueSong
                ? uniqueSongCount
                : 0.0;
        };
    }

    @Override
    public Codec<ISeq<Record>, BitGene> codec() {
        return codecs.ofSubSet(_records);
    }

    public static void main(final String[] args) {
        final double maxPricePerUniqueSong = 2.5;

        final Springsteen springsteen = new Springsteen(
            ISeq.of(
                new Record("Record1", 25, ISeq.of("Song1", "Song2", "Song3", "Song4", "Song5", "Song6")),
                new Record("Record2", 15, ISeq.of("Song2", "Song3", "Song4", "Song5", "Song6", "Song7")),
                new Record("Record3", 35, ISeq.of("Song5", "Song6", "Song7", "Song8", "Song9", "Song10")),
                new Record("Record4", 17, ISeq.of("Song9", "Song10", "Song12", "Song4", "Song13", "Song14")),
                new Record("Record5", 29, ISeq.of("Song1", "Song2", "Song13", "Song14", "Song15", "Song16")),
                new Record("Record6", 5, ISeq.of("Song18", "Song20", "Song30", "Song40"))
            ),
            maxPricePerUniqueSong
        );

        final Engine<BitGene, Double> engine = Engine.builder(springsteen)
            .build();

        final ISeq<Record> result = springsteen.codec().decoder().apply(
            engine.stream()
                .limit(10)
                .collect(EvolutionResult.toBestGenotype())
        );

        final double cost = result.stream()
            .mapToDouble(r -> r.price)
            .sum();

        final int uniqueSongCount = result.stream()
            .flatMap(r -> r.songs.stream())
            .collect(Collectors.toSet())
            .size();

        final double pricePerUniqueSong = cost/uniqueSongCount;

        System.out.println("Overall cost:  " + cost);
        System.out.println("Unique songs:  " + uniqueSongCount);
        System.out.println("Cost per song: " + (cost/uniqueSongCount));
        System.out.println("Records:       " + result.map(r -> r.name).toString(", "));

    }
}

La funzione fitness è semplice: il numero di brani unici, limitato dal prezzo massimo per canzone, che sei disposto a pagare. L'esecuzione del codice stamperà il seguente output:

Overall cost:  37.0
Unique songs:  15
Cost per song: 2.466666666666667
Records:       Record2, Record4, Record6