我的遗传算法不会 converge/reaches 局部最小值
My genetic algorithm won't converge/reaches local minima
我已经为这个小项目苦苦挣扎了一段时间，非常感谢您的帮助。
我正在尝试建立一个遗传算法来使用反式 parent 形状（三角形）绘制图片，像这样：https://chriscummins.cc/s/genetics/，但我已经尝试了很多不同的超参数和不同的技术，我真的无法像上面的网站那样得到任何融合。有时候会运行很久，还是会卡在下图这样的东西里，好像收敛到什么东西了，因为个体不多，但又不完全一样！
算法的工作原理基本上是这样的：
- 人口中的每个人都是 empty/black canvas 固定数量三角形上的一幅画。
- 个人的适应度是通过pixel-wise个人绘画与目标图像之间的平均绝对误差来计算的。
- 我使用锦标赛 selection select 可以选择哪些个体进行繁殖以产生下一代个体。
- 两幅画之间的交叉基本上是随机select每个parent基因的一半，也就是它们的三角形。
- 突变基本上包括对绘画中每个三角形的顶点坐标应用一些变化。
- 我将突变应用于 children 代。
- 每一代中最好的总是自动晋级到下一代。 （精英主义）
我将在下面附上代码，希望它是可以理解的，尝试将其记录下来以便人们更容易地帮助我。
这是我的三角形（基因） class:
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:
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}')
好的，我发现了主要错误！
问题出在 _error 函数中。每当 PIL 图像被转换为 numpy 数组时（当在两个 2D numpy 数组（图像通道）之间调用 np.subtract() 时），它就会被转换为 np.uint8 类型的 numpy 数组（unsigned int 8 字节），因为图像在 [0-255] 范围内，这是有道理的。但是在使用np.subtract的时候，如果你得到一个负值，那么它就会下溢，你的适应度函数就会乱了。
为了解决这个问题，只需在执行 np.subtract()
之前使用 np.array(channel, np.int32) 投射图像通道
我已经为这个小项目苦苦挣扎了一段时间，非常感谢您的帮助。
我正在尝试建立一个遗传算法来使用反式 parent 形状（三角形）绘制图片，像这样：https://chriscummins.cc/s/genetics/，但我已经尝试了很多不同的超参数和不同的技术，我真的无法像上面的网站那样得到任何融合。有时候会运行很久，还是会卡在下图这样的东西里，好像收敛到什么东西了，因为个体不多，但又不完全一样！
算法的工作原理基本上是这样的：
- 人口中的每个人都是 empty/black canvas 固定数量三角形上的一幅画。
- 个人的适应度是通过pixel-wise个人绘画与目标图像之间的平均绝对误差来计算的。
- 我使用锦标赛 selection select 可以选择哪些个体进行繁殖以产生下一代个体。
- 两幅画之间的交叉基本上是随机select每个parent基因的一半，也就是它们的三角形。
- 突变基本上包括对绘画中每个三角形的顶点坐标应用一些变化。
- 我将突变应用于 children 代。
- 每一代中最好的总是自动晋级到下一代。 （精英主义）
我将在下面附上代码，希望它是可以理解的，尝试将其记录下来以便人们更容易地帮助我。
这是我的三角形（基因） class:
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:
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}')
好的，我发现了主要错误！
问题出在 _error 函数中。每当 PIL 图像被转换为 numpy 数组时（当在两个 2D numpy 数组（图像通道）之间调用 np.subtract() 时），它就会被转换为 np.uint8 类型的 numpy 数组（unsigned int 8 字节），因为图像在 [0-255] 范围内，这是有道理的。但是在使用np.subtract的时候，如果你得到一个负值，那么它就会下溢，你的适应度函数就会乱了。
为了解决这个问题，只需在执行 np.subtract()
np.array(channel, np.int32) 投射图像通道