我的遗传算法不会在局部最小值处收敛。

Question

我一直在为这个小项目苦恼，我真的很感谢你的帮助。

我正试图建立一个使用透明形状（三角形）绘制图片的遗传算法，类似于这样。https:/chriscummins.CCSgenetics但我试过很多不同的超参数和不同的技术，但我真的不能像上面的网站那样得到任何收敛。有时它会运行很长时间，但它还是会卡在像下图这样的东西中，这似乎是它收敛的东西，因为没有多少不同的个体，但它还没有完全收敛!

算法的工作原理基本上是这样的。

• 人口中的每一个个体都是一张空的黑色画布上的画，画布上有固定数量的三角形。
• 个体的适配度是通过对个体的画作和目标图像之间做一个像素的平均绝对误差来计算的。
• 我使用锦标赛选择来选择哪些个体可以被选择来繁殖产生下一代的个体。
• 两幅画之间的交叉，基本上是随机选择每个父母的一半基因，也就是他们的三角形。
• 突变的内容基本上是对画中每个三角形的顶点坐标进行一些改变。
• 我将突变应用于子代。
• 每一代中的佼佼者总是自动晋级到下一代。(Elitism)

我把代码附在下面，希望能看懂，尽量把它记录下来，方便大家帮我解决。

下面是我的 三角形(吉恩) 类。

class Triangle:

    def __init__(self, image):
        '''
        Parameters
        ------------

        image: PIL.Image
            Image where the triangle will be drawn.

            This must be passed in order for the random triangle's vertices
            to have correct coordinates.
        '''
        self.max_width, self.max_height = image.size
        self.vertices = self.random_polygon()

        # RGBA
        self.color = Triangle.random_color()

    def __str__(self):
        return f'Vertices: {[(round(x, 2), round(y, 2)) for (x, y) in self.vertices]} | Color: {self.color}'

    def draw(self, draw_object, fill=True) -> None:
        '''
        Method to draw the polygon using a Pillow ImageDraw.Draw object

        Parameters
        ------------

        draw_object: ImageDraw.Draw
            Object to draw the image

        fill: bool
            Whether to fill the polygon or just outline it.

        '''

        if fill:
            draw_object.polygon(self.vertices, fill=self.color)
        else:
            draw_object.polygon(self.vertices, outline=self.color)

    def noise(self, ratio):
        '''Generate noise into this object'''

        def vertex_noise(vertex):
            x, y = vertex
            x = random.uniform(max(0.0, x - ratio * x), min(self.max_width, x + ratio * x))
            y = random.uniform(max(0.0, y - ratio * y), min(self.max_height, y + ratio * y))
            return (x, y)

        for i in range(3):
            self.vertices[i] = vertex_noise(self.vertices[i])

        return self

    def random_polygon(self) -> list:
        '''Generate a random triangle in the form [(x, y), (x, y), (x, y)]'''

        def random_vertex() -> tuple:
            x = random.uniform(0.0, self.max_width)
            y = random.uniform(0.0, self.max_height)
            return (x, y)

        return [random_vertex() for _ in range(3)]

    @classmethod
    def random_color(cls) -> tuple:
        '''Generate a random RGBA color tuple'''
        def _random(lower, upper):
            return random.randint(lower, upper)

        return (_random(0, 255), _random(0, 255), _random(0, 255), _random(85, 255))

    @classmethod
    def collection(cls, size, image) -> list:
        '''
        Generate collection of triangles

        Parameters
        ------------

        size: int
            Number of triangles to generate

        image: PIL.Image
            Image to use for the Triangle constructor.
            See help(Triangle) for more info.

        Return
        --------

        collection: list
            Collection of polygons.

        '''
        return [cls(image) for _ in range(size)]   

这里是... 绘画（个人） 类。

class Painting:
    def __init__(self, num_objects, img):
        '''
        Parameters
        ------------

        num_objects: int
            Number of triangles in each painting (this is the DNA size).

        img: PIL.Image
            Target image that we're trying to approximate

        '''
        self.polygons = Triangle.collection(num_objects, img)
        self.target = img
        self.fitness = float('inf')

    def __lt__(self, other):
        return self.fitness < other.fitness

    def __del__(self):
        if hasattr(self, 'canvas'):
            self.canvas.close() 

    def fit(self):
        '''Fits individual's painted canvas against target image'''
        self.paint()
        self.fitness = self._error(self.canvas, self.target)   
        return self

    @classmethod
    def crossover(cls, indA, indB, ratio):
        '''
        Reproduces two painting objects and generates a painting child
        by randomly choosing genes from each parent in some given proportion.

        Parameters
        ------------

        indA: Painting

        indB: Painting

        ratio: float
            Proportion of genes to be taken from the father object.

        Return
        ---------

        child: Painting
        '''
        if len(indA.polygons) != len(indB.polygons):
            raise ValueError('Parents\' number of polygons don\'t match.')

        if indA.target != indB.target:
            raise ValueError('Parents\' target images don\'t match.')

        num_objects = len(indA.polygons)
        target = indA.target
        child = cls(num_objects, target)

        indA_ratio = int(ratio * num_objects)

        # Crossover Parents' triangles
        child.polygons = deepcopy(random.sample(indA.polygons, k=indA_ratio))
        child.polygons.extend(deepcopy(random.sample(indB.polygons, k=num_objects-indA_ratio)))

        return child

    @classmethod
    def random_population(cls, size, num_objs, img):
        '''Generates a random population of paintings'''
        return [cls(num_objs, img) for _ in range(size)]

    def mutate(self, mutation_chance, mutation_ratio):
        '''
        Applies noise to the painting objects' genes, which is basically a "mutation"

        Parameters
        ------------

        mutation_chance: float
            chance that each gene will be mutated

        mutation_ratio: float
            intensity of the mutation that will be caused in case it happens.

            The noise caused is just a small change in the polygons' vertices coordinates.

            See help(Painting.noise()) for more info.
        '''
        num_objs = len(self.polygons)

        rng = random.uniform(0.0, 1.0)

        if mutation_chance < rng:
            return self

        for i in range(num_objs):
            rng = random.uniform(0.0, 1.0)

            if mutation_chance < rng:
                continue

            self.polygons[i].noise(mutation_ratio)

        return self

    def paint(self):
        '''Paints genoma into an empty canvas.'''
        if hasattr(self, 'canvas'):
            self.canvas.close()

        # Create white canvas
        self.canvas = Image.new(mode='RGB', size=self.target.size)
        draw_obj = ImageDraw.Draw(self.canvas, mode='RGBA')

        for poly in self.polygons:
            poly.draw(draw_obj)

    @staticmethod
    def _error(canvas, target):
        '''Mean Squared Error between PIL Images'''
        r_canvas, g_canvas, b_canvas = canvas.split()
        r_target, g_target, b_target = target.split()

        def mse(a, b):
            return np.square(np.subtract(a, b)).mean()

        return (mse(r_canvas, r_target) + mse(g_canvas, g_target) + mse(b_canvas, b_target)) / 3.0

最后，这是算法本身的大致流程。

def k_way_tournament_selection(population, number_of_winners, K=3):
    selected = []
    while len(selected) < number_of_winners:
        fighters = random.sample(population, k=min(number_of_winners-len(selected), K))

        selected.append(min(fighters))

    return selected

EPOCHS = 200
POP_SIZE = 100
DNA_SIZE = 100
MUTATION_CHANCE = 0.01
MUTATION_RATIO = 0.2
SELECTION_RATIO = 0.3

pop = Painting.random_population(POP_SIZE, DNA_SIZE, lisa)
initial = time()
generation_best = []

for ep in range(EPOCHS):
    pop = [p.fit() for p in pop]
    pop = sorted(pop)

    # Save Best
    best = pop[0]
    generation_best.append(deepcopy(best.canvas))
    pop = pop[1:]


    # Tournament selection
    selected = []
    selected = k_way_tournament_selection(pop, int(len(pop) * SELECTION_RATIO))
    selected.append(best)

    # Reproduce
    children = []
    while len(children) < POP_SIZE:
        indA = random.choice(selected)
        indB = random.choice(selected)

        cross = Painting.crossover(indA, indB, 0.5)
        children.append(cross)

    # Mutate
    children = [child.mutate(MUTATION_CHANCE, MUTATION_RATIO) for child in children]
    children.append(best)

    pop = deepcopy(children)

    del children
    del selected
    gc.collect()

    t = time()
    print(f'EPOCH: {ep} | SIZE: {len(pop)} | ELAPSED: {round(t - initial, 2)}s | BEST: {best.fitness}')

Answer 1

好了，我找到了主要的bug！问题出在_error中。

问题出在_error函数中。每当PIL图像被转换为numpy数组时（当调用 np.subtract() 之间的两个二维numpy数组，也就是图像通道），它被转换为一个类型为 np.uint8 (unsigned int 8 bytes)，因为图像的范围是[0-255]，这很合理。但是当使用 np.subtract如果你得到一个负值，那么它就会下溢，你的健身函数就会被搞乱。

为了解决这个问题，只需将图像通道用 np.array(channel, np.int32) 才 np.subtract()