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.
Quel est le problème du sac à dos?
- Supposons qu'un voleur vienne au magasin pour voler. Il existe un produit avec différents poids et valeurs. Le poids qu'un voleur peut porter est limité, mais il recherche la valeur maximale qui peut être volée dans ces conditions. * C'est le problème.
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
- Valeur totale des produits que vous possédez (lorsque le poids des produits que vous possédez est inférieur à l'acceptable)
- 1 (si plus qu'acceptable)
Lorsque le poids du produit que vous avez est sévèrement limité,
- Il est difficile d'obtenir une solution car elle n'évolue jamais à partir d'un gène qui pèse plus que le poids *
Cette fois,
- Valeur totale des produits que vous possédez (lorsque le poids des produits que vous possédez est inférieur à l'acceptable)
- Poids total des produits que vous avez (si plus qu'acceptables)
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.
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