Выполнение tkinter прекращается после 140 итераций без сообщения об ошибке (утечка памяти?)

Question

Мой код умирает после 140+ итераций, и я не знаю почему.Я предполагаю, что утечка памяти возможна, но я не смог ее найти.Я также обнаружил, что изменение некоторых арифметических констант может продлить время до сбоя.

У меня есть генетический алгоритм, который пытается найти лучший (то есть минимальные шаги) маршрут из точки A (src) в точку B(dst).

Я создаю список случайных хромосом, где каждая хромосома имеет:

1. src + dst [всегда одно и то же]
2. списокнаправления (случайные)

Затем я запускаю алгоритм:

1. найду лучший маршрут и нарисую его (для целей визуализации)
2. Учитывая вероятность P -замените хромосомы перекрестными переходами (то есть выберите 2 и возьмите «конец» своего направления и замените «конец» второго)
3. При заданной вероятности Q - мутировать (заменить следующее направление наслучайное направление)

Все идет хорошо, и в большинстве случаев я нахожу маршрут (обычно не идеальный), но иногда, когда он ищет долго (скажем, около 140+ итерации) это просто давит.Нет предупрежденияБез ошибок.

Как я могу предотвратить это (простой предел итерации может работать, но я действительно хочу, чтобы алгоритм работал долго [~ 2000 + итерации])?

Я думаюсоответствующие части кода:

1. update функция внутри класса GUI
2. , которая вызывает cross_over
3. при игре со счетом update_fitness()значения (при изменении score -= (weight+1)*2000*(shift_x + shift_y) на score -= (weight+1)*2*(shift_x + shift_y) он работает дольше. Может быть какое-то арифметическое переполнение?

---

import tkinter as tk
from enum import Enum
from random import randint, sample
from copy import deepcopy
from time import sleep
from itertools import product


debug_flag = False

class Direction(Enum):
    Up      = 0
    Down    = 1
    Left    = 2
    Right   = 3

    def __str__(self):
        return str(self.name)

    def __repr__(self):
        return str(self.name)[0]

# A chromosome is a list of directions that should lead the way from src to dst.
# Each step in the chromosome is a direction (up, down, right ,left)
# The chromosome also keeps track of its route
class Chromosome:   
    def __init__(self, src = None, dst = None, length = 10, directions = None):
        self.MAX_SCORE = 1000000

        self.route = [src]
        if not directions:
            self.directions = [Direction(randint(0,3)) for i in range(length)]
        else:
            self.directions = directions
        self.src = src
        self.dst = dst
        self.fitness = self.MAX_SCORE

    def __str__(self):
        return str(self.fitness)

    def __repr__(self):
        return self.__str__()

    def set_src(self, pixel):
        self.src = pixel

    def set_dst(self, pixel):
        self.dst = pixel

    def set_directions(self, ls):
        self.directions = ls

    def update_fitness(self):
        # Higher score - a better fitness
        score = self.MAX_SCORE - len(self.route)

        score += 4000*(len(set(self.route)) - len(self.route))  # penalize returning to the same cell
        score += (self.dst in self.route) * 500                 # bonus routes that get to dst

        for weight,cell in enumerate(self.route):
            shift_x = abs(cell[0] - self.dst[0])
            shift_y = abs(cell[1] - self.dst[1])
            score -= (weight+1)*2000*(shift_x + shift_y)        # penalize any wrong turn

        self.fitness = max(score, 0)

    def update(self, mutate_chance = 0.9):
        # mutate #
        self.mutate(chance = mutate_chance)

        # move according to direction
        last_cell = self.route[-1]

        try:
            direction = self.directions[len(self.route) - 1]
        except IndexError:
            print('No more directions. Halting')
            return

        if  direction == Direction.Down:
            x_shift, y_shift =  0,  1
        elif direction == Direction.Up:
            x_shift, y_shift =  0, -1
        elif direction == Direction.Left:
            x_shift, y_shift = -1,  0
        elif direction == Direction.Right:
            x_shift, y_shift =  1,  0

        new_cell = last_cell[0] + x_shift, last_cell[1] + y_shift
        self.route.append(new_cell)
        self.update_fitness()


    def cross_over(p1, p2, loc = None):
        # find the cross_over point
        if not loc:
            loc = randint(0,len(p1.directions))

        # choose one of the parents randomly
        x = randint(0,1)
        src_parent = (p1, p2)[x]
        dst_parent = (p1, p2)[1 - x]
        son = deepcopy(src_parent)
        son.directions[loc:] = deepcopy(dst_parent.directions[loc:])

        return son   

    def mutate(self, chance = 1):
        if 100*chance > randint(0,99):
            self.directions[len(self.route) - 1] = Direction(randint(0,3))




class GUI:
    def __init__(self, rows = 10, cols = 10, iteration_timer = 100, chromosomes = [], cross_over_chance = 0.5, mutation_chance = 0.3, MAX_ITER = 100):        

        self.rows = rows
        self.cols = cols
        self.canv_w = 800
        self.canv_h = 800
        self.cell_w = self.canv_w // cols
        self.cell_h = self.canv_h // rows

        self.master = tk.Tk()
        self.canvas = tk.Canvas(self.master, width = self.canv_w, height = self.canv_h)       
        self.canvas.pack()

        self.rect_dict          = {}
        self.iteration_timer    = iteration_timer
        self.iterations         = 0
        self.MAX_ITER           = MAX_ITER

        self.chromosome_list = chromosomes
        self.src             = chromosomes[0].src # all chromosomes share src + dst
        self.dst             = chromosomes[0].dst

        self.prev_best_route    = []
        self.cross_over_chance  = cross_over_chance
        self.mutation_chance    = mutation_chance
        self.no_obstacles       = True

        # init grid #
        for r in range(rows):
            for c in range(cols):
                self.rect_dict[(r, c)] = self.canvas.create_rectangle(r    *self.cell_h, c    *self.cell_w,
                                                                      (1+r)*self.cell_h, (1+c)*self.cell_w,
                                                                      fill="gray")
        # init grid #

        # draw src + dst #
        self.color_src_dst()
        # draw src + dst #

        # after + mainloop #
        self.master.after(iteration_timer, self.start_gui)
        tk.mainloop()
        # after + mainloop #

    def start_gui(self):
        self.start_msg = self.canvas.create_text(self.canv_w // 2,3*self.canv_h // 4, fill = "black", font = "Times 25 bold underline", 
                                text="Starting new computation.\nPopulation size = %d\nCross-over chance = %.2f\nMutation chance = %.2f" %
                                (len(self.chromosome_list), self.cross_over_chance, self.mutation_chance))
        self.master.after(2000, self.update)

    def end_gui(self, msg="Bye Bye!"):
        self.master.wm_attributes('-alpha', 0.9) # transparency
        self.canvas.create_text(self.canv_w // 2,3*self.canv_h // 4, fill = "black", font = "Times 25 bold underline", text=msg)

        cell_ls = []
        for idx,cell in enumerate(self.prev_best_route):
            if cell in cell_ls:
                continue
            cell_ls.append(cell)
            self.canvas.create_text(cell[0]*self.cell_w, cell[1]*self.cell_h, fill = "purple", font = "Times 16 bold italic", text=str(idx+1))


        self.master.after(3000, self.master.destroy)

    def color_src_dst(self):
        r_src = self.rect_dict[self.src]
        r_dst = self.rect_dict[self.dst]
        c_src = 'blue'
        c_dst = 'red'
        self.canvas.itemconfig(r_src, fill=c_src)
        self.canvas.itemconfig(r_dst, fill=c_dst)

    def color_route(self, route, color):
        for cell in route:
            try:
                self.canvas.itemconfig(self.rect_dict[cell], fill=color)
            except KeyError:
                # out of bounds -> ignore
                continue

        # keep the src + dst
        self.color_src_dst()
        # keep the src + dst

    def compute_shortest_route(self):
        if self.no_obstacles:
            return (1 + 
                    abs(self.chromosome_list[0].dst[0] - self.chromosome_list[0].src[0]) + 
                    abs(self.chromosome_list[0].dst[1] - self.chromosome_list[0].src[1]))
        else:
            return 0

    def create_weighted_chromosome_list(self):
        ls = []
        for ch in self.chromosome_list:
            tmp = [ch] * (ch.fitness // 200000)
            ls.extend(tmp)
        return ls

    def cross_over(self):
        new_chromosome_ls = []
        weighted_ls = self.create_weighted_chromosome_list()

        while len(new_chromosome_ls) < len(self.chromosome_list):
            try:
                p1, p2 = sample(weighted_ls, 2)
                son = Chromosome.cross_over(p1, p2)
                if son in new_chromosome_ls:
                    continue
                else:
                    new_chromosome_ls.append(son)
            except ValueError:
                continue

        return new_chromosome_ls

    def end_successfully(self):
        self.end_gui(msg="Got to destination in %d iterations!\nBest route length = %d" % (len(self.prev_best_route), self.compute_shortest_route()))

    def update(self): 
        # first time #
        self.canvas.delete(self.start_msg)
        # first time #

        # end #
        if self.iterations >= self.MAX_ITER:
            self.end_gui()
            return
        # end #

        # clean the previously best chromosome route #
        self.color_route(self.prev_best_route[1:], 'gray')
        # clean the previously best chromosome route #

        # cross over #
        if 100*self.cross_over_chance > randint(0,99):
            self.chromosome_list = self.cross_over()
        # cross over #

        # update (includes mutations) all chromosomes #
        for ch in self.chromosome_list:
            ch.update(mutate_chance=self.mutation_chance)
        # update (includes mutations) all chromosomes #

        # show all chromsome fitness values #
        if debug_flag:
            fit_ls = [ch.fitness for ch in self.chromosome_list]
            print(self.iterations, sum(fit_ls) / len(fit_ls), fit_ls)
        # show all chromsome fitness values #

        # find and display best chromosome #
        best_ch = max(self.chromosome_list, key=lambda ch : ch.fitness)
        self.prev_best_route = deepcopy(best_ch.route)
        self.color_route(self.prev_best_route[1:], 'gold')
        # find and display best chromosome #

        # check if got to dst #
        if best_ch.dst == best_ch.route[-1]:
            self.end_successfully()
            return
        # check if got to dst #

        # after + update iterations #
        self.master.after(self.iteration_timer, self.update)
        self.iterations += 1
        # after + update iterations #



def main():
    iter_timer, ITER = 10, 350
    r,c              = 20,20
    s,d              = (13,11), (7,8)
    population_size     = [80,160]
    cross_over_chance   = [0.2,0.4,0.5]

    for pop_size, CO_chance in product(population_size, cross_over_chance):
        M_chance = 0.7 - CO_chance
        ch_ls = [Chromosome(src=s, dst=d, directions=[Direction(randint(0,3)) for i in range(ITER)]) for i in range(pop_size)]
        g = GUI(rows=r, cols=c, chromosomes = ch_ls, iteration_timer=iter_timer, 
                cross_over_chance=CO_chance, mutation_chance=M_chance, MAX_ITER=ITER-1)
        del(ch_ls)
        del(g)

if __name__ == "__main__":
    main()

Answer 1

Я не знаю, знаете ли вы инструмент Python Profiling в Visual Studio, но он весьма полезен в таких случаях, как ваш (хотя я обычно программирую с редакторами, такими как VS Code).

Я запустил вашу программу, и, как вы сказали, она иногда вылетает.Я проанализировал код с помощью инструмента профилирования, и кажется, что проблема заключается в функции cross_over, а именно в случайной функции:

Я бы настоятельно рекомендовал рассмотреть ваши cross_over и mutation функции.Случайная функция не должна вызываться так много раз (2 миллиона).

Я ранее запрограммировал генетические алгоритмы, и мне кажется, что ваша программа падает до локального минимума .В этих случаях предлагается играть с процентом мутации .Попробуйте немного увеличить его, чтобы вы могли выйти за локальный минимум.