[PYTHON] Lösung von Rucksackproblemen mit genetischen Algorithmen und MGG-Modellen

Was ist ein genetischer Algorithmus?

Eine Methode, um ein für die Umwelt geeignetes Gen (Lösung) zu erhalten (zu lösendes Problem), indem Generationen durch Kreuzung und Mutation von Genen wiederholt werden, wie die Evolution lebender Organismen.

Was ist das Rucksackproblem?

• Angenommen, ein Dieb kommt in den Laden, um zu stehlen. Es gibt ein Produkt mit verschiedenen Gewichten und Werten. Der Dieb hat ein begrenztes Gewicht, sucht aber den Maximalwert, der unter diesen Bedingungen gestohlen werden kann. * * Ist das Problem.

Wenn wir einfach versuchen, eine Lösung für dieses Problem zu finden, werden wir es mit einem Round-Robin von O (2 ^ n) angehen. Daher versuchen wir, mithilfe eines genetischen Algorithmus relativ schnell eine ungefähre Lösung zu finden.

Fluss des genetischen Algorithmus

Problemstellung

Angenommen, diesmal gibt es 30 Produkte. Das erste Element von Tapple ist das Gewicht und das zweite Element ist der Wert.

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),]

Generation der ersten Generation

Bereiten Sie für das Gen zwei Werte vor, einen mit jedem Produkt (= 1) und einen ohne (= 0), und die Anzahl der Stellen für die Anzahl der Produkte. Zusätzlich werden n Gene für jede Generation hergestellt. Der ersten Generation wird zufällig ein Wert zugewiesen und sie wird mit jeder Generation komplexer.

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

Auswertung

Die Bewertung von Genen variiert von Problem zu Problem, und es ist wichtig, sie gut einzustellen. Zum Beispiel für dieses Problem

• Gesamtwert der Produkte, die Sie haben (wenn das Gewicht der Produkte, die Sie haben, nicht akzeptabel ist)
• 1 (wenn mehr als akzeptabel)

Wenn das Gewicht Ihres Produkts stark eingeschränkt ist,

• Es ist schwierig, eine Lösung zu erhalten, da sie sich niemals aus einem Gen entwickelt, das mehr wiegt als das Gewicht *

Diesmal,

• Gesamtwert der Produkte, die Sie haben (wenn das Gewicht der Produkte, die Sie haben, nicht akzeptabel ist)
• Gesamtgewicht der Produkte, die Sie haben (falls mehr als akzeptabel)

In der Tat, wenn alle Gene mehr als akzeptabel sind, werden wir sie in der Reihenfolge der leichtesten Produkte betrachten.

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

Wahl

Wählen Sie das zu kreuzende Gen aus. Dieses Mal werden wir die Roulette-Auswahl verwenden. Die Auswahl erfolgt durch Zufallszahlen, wobei das Verhältnis der Bewertungsergebnisse jedes Gens als gewichtete Wahrscheinlichkeit gilt.

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

Parallel zur Roulette-Auswahl wird auch die Elite-Auswahl berücksichtigt. Das beste Gen kann an die nächste Generation weitergegeben werden. Hierbei wird das bei der Bewertung berücksichtigte Gesamtgewicht berücksichtigt.

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

Kreuzung

Kombinieren Sie die beiden Gene, um ein neues Gen zu erstellen. Dieses Mal werden wir eine Zwei-Punkt-Frequenzweiche verwenden. Eine Methode zum zufälligen Festlegen von zwei Punkten und zum Umschalten zwischen den beiden Punkten. 「000|101|111」 <- 「000|010|111」 「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

Über Generationen mit nur Frequenzweichen wird die Lösung verbessert, kann jedoch zu einer lokal optimalen Lösung führen. Daher führen wir eine Mutation ein, die das Gen mit geringer Wahrscheinlichkeit umschreibt.

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

Lauf

Kombinieren Sie das Obige und führen Sie es aus.

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):
    #Auswertung
    score = []
    weight = []
    for g in geen:
        s, w = f(g)
        score.append(s)
        weight.append(w)

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

    #Kreuzung
    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)

Das Ausführungsergebnis ist wie folgt. Die Aussicht ist (Bewertungsergebnis (Wert) des besten Gens, gleiches Gewicht) [Gen]

Ausführungsergebnis

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]

MGG-Modell

Ein abgeleitetes Modell eines genetischen Algorithmus, eine Methode zur Aufrechterhaltung der genetischen Vielfalt durch Lokalisierung von Generationswechseln.

Lauf

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):
    #Wähle zufällig zwei aus
    selected_index1, selected_index2 = random.sample(range(n), 2)
    parent1 = geen[selected_index1]
    parent2 = geen[selected_index2]

    #Mehrfacherzeugung durch Kreuzung / Mutation aus den beiden ausgewählten
    children = [cross(parent1, parent2) for i in range(n)]
    children = mutate(children)

    #Berechnen Sie die Kinderpunktzahl
    score = []
    weight = []
    for c in children:
        s, w = f(c)
        score.append(s)
        weight.append(w)

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

    #Roulette-Auswahl für Kinder
    score[elite_index] = 0
    selected_index = select(score)

    #Geben Sie das ausgewählte Kind an das Elternteil zurück
    geen[selected_index1] = children[elite_index]
    geen[selected_index2] = children[selected_index]

Ausführungsergebnis

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]

Nachwort

Es ist ersichtlich, dass die Ergebnisse beider mit jeder Generation besser werden. Auch der genetische Algorithmus scheint Wellen in den Ergebnissen von Generation zu Generation zu haben, aber das MGG-Modell scheint relativ kleine Wellen zu haben.