Résolution des problèmes de sac à dos avec des algorithmes génétiques et des modèles MGG

Qu'est-ce qu'un algorithme génétique?

Une méthode pour obtenir un gène (solution) adapté à l'environnement (problème à résoudre) en répétant des générations par croisement et mutation de gènes, comme l'évolution des organismes vivants.

Untitled Diagram.jpg

Quel est le problème du sac à dos?

Si nous essayons simplement de trouver une solution à ce problème, nous l'aborderons avec un round-robin de O (2 ^ n). Par conséquent, nous essayons de trouver une solution approximative relativement rapidement à l'aide d'un algorithme génétique.

Flux d'algorithme génétique

Problème de réglage

Supposons qu'il y ait 30 produits cette fois. Le premier élément de tapple est le poids et le deuxième élément est la valeur.

production = [(2, 21), (3, 4), (2, 28), (4, 21), (8, 7),
              (10, 22), (10, 22), (10, 22), (7, 2), (5, 40),
              (7, 28), (9, 36), (7, 14), (8, 25), (7, 14),
              (2, 21), (8, 2), (9, 36), (5, 28), (5, 4),
              (4, 12), (8, 7), (7, 28), (2, 28), (7, 28),
              (9, 24), (5, 40), (2, 21), (3, 4), (3, 40),
              (10, 15), (7, 14), (10, 18), (10, 22), (9, 33),
              (7, 2), (3, 40), (4, 12), (9, 36), (7, 35),
              (8, 25), (9, 33), (9, 24), (7, 31), (7, 21),
              (5, 28), (7, 21), (10, 15), (8, 2), (9 ,20),]

Génération de première génération

Pour le gène, préparez deux valeurs, une avec chaque produit (= 1) et une sans (= 0), et le nombre de chiffres pour chaque produit. De plus, n gènes sont préparés pour chaque génération. La première génération se voit attribuer une valeur au hasard et devient plus sophistiquée à chaque génération.

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

Évaluation

L'évaluation des gènes varie d'un problème à l'autre et il est important de bien les définir. Par exemple, pour ce numéro

Lorsque le poids du produit que vous avez est sévèrement limité,

Cette fois,

En conséquence, si tous les gènes sont plus qu'acceptables, nous les considérerons dans l'ordre des produits les plus légers.

def f(g):
    weight = sum([production[j][0] * g[j] for j in range(dim)])
    if weight <= w_max:
        return sum([production[j][1] * g[j] for j in range(dim)]), weight
    else:
        return 1, weight

Choix

Sélectionnez le gène à croiser. Cette fois, nous utiliserons la sélection de la roulette. La sélection est effectuée par des nombres aléatoires, avec le rapport des résultats d'évaluation de chaque gène comme probabilité pondérée.

def select(score):
    total = sum(score)
    threshold = random.random() * total
    sum_s = 0
    for i, s in enumerate(score):
        sum_s += s
        if sum_s > threshold:
            return i

Il intègre également la sélection d'élite en parallèle avec la sélection de roulette. Le meilleur gène peut être transmis à la génération suivante. Le poids total pris en compte dans l'évaluation est pris en compte ici.

def find_elite(score, weight=None):
    if not weight is None and len(list(set(score))) == 1:
        min_weight = 1e+6
        min_index = None
        for i, w in enumerate(weight):
            if min_weight > w:
                min_weight = w
                min_index = i
        return min_index
    else:
        max_score = -1
        max_index = None
        for i, val in enumerate(score):
            if max_score < val:
                max_score = val
                max_index = i
        return max_index

Traversée

Combinez les deux gènes pour créer un nouveau gène. Cette fois, nous utiliserons un croisement à deux points. Une méthode de spécification aléatoire de deux points et de basculement entre les deux points. 「000|101|111」 <- 「000|010|111」<Traversée> 「001|101|110」

def cross(parent1, parent2):
    length = len(parent1)
    r1 = int(math.floor(random.random() * length))
    r2 = r1 + int(math.floor(random.random() * (length - r1)))

    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]

    return child

mutation

Au fil des générations, avec uniquement des croisements, la solution sera améliorée, mais peut conduire à une solution locale optimale. Par conséquent, nous introduisons une mutation qui réécrit le gène avec une faible probabilité.

def mutate(geen):
    for i in range(n):
        for l in range(dim):
            if random.random() > cross_rate:
                geen[i][l] = 1 - geen[i][l]

    return geen

Courir

Combinez ce qui précède et exécutez.

n = 10
w_max = 50
dim = len(production)
cross_rate = 0.99
g_num = 10000

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

for stage in range(g_num):
    #Évaluation
    score = []
    weight = []
    for g in geen:
        s, w = f(g)
        score.append(s)
        weight.append(w)

    #Choix
    elite_index = find_elite(score, weight)
    if stage % 100 == 0:
        print("Generation: {}".format(stage))
        print(f(geen[elite_index]), geen[elite_index])

    #Traversée
    next_geen = [geen[elite_index]]
    while len(next_geen) < n:
        selected_index1 = select(score)
        selected_index2 = select(score)
        while selected_index1 == selected_index2:
            selected_index2 = select(score)
        next_geen.append(cross(geen[selected_index1], geen[selected_index2]))

    #mutation
    geen = mutate(next_geen)

Le résultat de l'exécution est le suivant. La vue est (Résultat d'évaluation (valeur) du meilleur gène, même poids) [Gène]

Résultat d'exécution


Generation: 0
(1, 102) [0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0]
Generation: 100
(243, 50) [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 200
(358, 47) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 300
(319, 50) [0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 400
(247, 50) [0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 500
(349, 48) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 600
(394, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
Generation: 700
(382, 49) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 800
(328, 47) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 900
(315, 48) [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 1000
(333, 49) [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]

Modèle MGG

Un modèle dérivé d'un algorithme génétique, une méthode de maintien de la diversité génétique en localisant les changements générationnels. Untitled Diagram (1).jpg

Courir

n = 10
w_max = 50
dim = len(production)
cross_rate = 0.99
g_num = 10000

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

for stage in range(g_num):
    #Sélectionnez au hasard deux
    selected_index1, selected_index2 = random.sample(range(n), 2)
    parent1 = geen[selected_index1]
    parent2 = geen[selected_index2]

    #Génération multiple par croisement / mutation des deux sélectionnés
    children = [cross(parent1, parent2) for i in range(n)]
    children = mutate(children)

    #Calculer le score de l'enfant
    score = []
    weight = []
    for c in children:
        s, w = f(c)
        score.append(s)
        weight.append(w)

    #Élite enfant
    elite_index = find_elite(score, weight=weight)
    if stage % 100 == 0:
        print("Generation: {}".format(stage))
        print(f(geen[elite_index]), geen[elite_index])

    #Sélection de roulette enfant
    score[elite_index] = 0
    selected_index = select(score)

    #Renvoyer l'enfant sélectionné au parent
    geen[selected_index1] = children[elite_index]
    geen[selected_index2] = children[selected_index]

Résultat d'exécution


Generation: 0
(1, 131) [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]
Generation: 100
(164, 50) [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
Generation: 200
(303, 48) [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Generation: 300
(334, 47) [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 400
(369, 50) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 500
(369, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 600
(375, 49) [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 700
(366, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Generation: 800
(328, 48) [0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 900
(382, 49) [0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 1000
(395, 50) [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]

Épilogue

On peut voir que les résultats des deux s'améliorent à chaque génération. De plus, l'algorithme génétique semble avoir des vagues dans les résultats de génération en génération, mais le modèle MGG semble avoir des vagues relativement petites.

Recommended Posts

Résolution des problèmes de sac à dos avec des algorithmes génétiques et des modèles MGG
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Étude des algorithmes génétiques (1) - Problème de base OneMax
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée
Premiers pas avec les algorithmes génétiques Python
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)
Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Résolution du modèle Lorenz 96 avec Julia et Python
Résolvez le problème du sac à dos Python avec l'algorithme glouton