私の遺伝的アルゴリズムは収束しない/極小値に達する

私はこの小さなプロジェクトにしばらく苦労してきました、そして私はあなたの助けに本当に感謝します。

https://chriscummins.cc/s/genetics/のように、透明な形状（三角形）を使用して画像を描画するための遺伝的アルゴリズムを構築しようとしていますが、さまざまなハイパーパラメータとさまざまな手法を試しました。上記のウェブサイトのように、実際には収束を得ることができません。時々それは長い間実行され、それでも下の画像のようなもので立ち往生するでしょう、それは多くの異なる個人がいないのでそれが何かに収束しているように見えます、しかしそれは完全にはありません！

アルゴリズムは基本的に次のように機能します。

• 人口のすべての個人は、固定数の三角形の空/黒いキャンバス上の絵画です。
• 個人の適合性は、個人の絵画とターゲット画像の間でピクセル単位の平均絶対誤差を実行することによって計算されます。
• 私はトーナメントセレクションを使用して、次世代の個体を生み出すために繁殖するために選択できる個体を選択します。
• 2つの絵の間のクロスオーバーは、基本的に、各親の遺伝子の半分、つまり三角形をランダムに選択することです。
• 突然変異は、基本的に、絵画の各三角形の頂点の座標にいくつかの変更を適用することで構成されます。
• 私は子供世代に突然変異を適用します。
• 各世代の最高のものは常に自動的に次の世代に進みます。（エリート主義）

以下にコードを添付します。理解できることを願って、人々が私を助けやすくするためにそれを文書化しようとしました。

これが私のTriangle（Gene）クラスです：

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}')