在生活中找到Mona Lisa

此视频可能需要几秒钟才能加载。请眯着眼睛以获得最佳结果:)。此实验的结果并不完全接近我的目标，但我认为无论如何都值得博客。有这个粗糙的想法，我一直在考虑康威的生活游戏很长一段时间。

我想知道它是否可以使用某种随机算法，这为您提供了一种初始状态，在许多周期之后形成清晰的文本。

- yakinavault（@yakinavault）2020年8月7日

我最近遇到了一篇相同的标题的文章，我以为我可以使用不同的方法做一些类似的事情。如果代替使用SAT求解器，我使用某种启发式算法可以以某种方式“程序”一个大量的生活游戏，在几代之后展示图像？

还有其他方法可以实现这一目标。一个是通过在该码头道问题中描述的特定像素来放置静物状态。

我所想到的是为单一帧/生成的“非静止”生活中展示Mona Lisa。

我开始使用山坡攀爬算法致力于概念证明。这个想法非常简单。迭代地修改一个随机的生命状态游戏，直到它的第n代看起来类似于蒙娜丽莎。这是完整的算法。

best_score：= Infinity target：= mona lisa with尺寸mxn canvas：= mxn best_result的随机矩阵：= canvas do modified_canvas：=与单个随机细胞反转的canvas副本indized_canvas of life _canvas计算得分如果分数＆lt; best_score然后best_score：= score best_result：= modified_canvas canvas：= best_result，而（max_镜头限制通过或best_score＆lt;阈值）

def修改（画布，形状）：x，y =形状px = int（np.random.uniform（x + 1）） - 1 py = int（np.random.uniform（y + 1）） - 1 canvas [px ] [py] =不是画布[px] [py]返回canvasdef rmse（预测，目标）：返回np.sqrt（np.mean（（predictions-targets）** 2）），而best_score＆gt; limit：canvases = np。瓷砖（NP.Copy（Best_seed），（Batch_size，1,1））RMS_ERRORS = []范围内的CANVAS（LEN（CANVASES））：CANVASES [CANVAS] =修改（状态[状态]，（m，n）） RMSE_VAL = RMSE（目标，NTH_GERACER（NP.COPY（CANVASES [CANVAS]）））RMS_ERRORS.APPEND（RMSE_VAL）LOWEST = min（RMS_ERRORS）如果最低且更低） best_score：best_score = lobest best_result = canvases [rms_errors.index（最低）]

爬山攀登工程通过将最近的相邻状态找到最近的状态，其中“target_state”（Mona Lisa）的错误。我在每一步中找到最近的邻居的方式是创建我们到目前为止的最佳解决方案的副本并反转一个随机单元格。这种变化足够小，以至于我们不会冒险踩过任何当地最小值。我们还使用均均方误差度量来比较最佳状态和目标。可以尝试其他错误指标，但对于此问题，我发现RMSE足够了。

经过几天的CPU时间（！），我能够在运行4代生命之后获得类似Mona Lisa的东西。

我的算法确实有效，但我意识到我犯了一堆错误，当然它对更大的图像或快速来说并不是可以扩展。

目标Mona Lisa，我们的随机状态与维基百科占据的中等分辨率版本进行了比较，并使用Pil的形象转换为单色。（＆＃39; target.png＆＃39;）。转换（＆＃39; l＆＃39 ;）

当您与布尔变量进行比较时，从维基百科取自维基百科，我们将成为二进制矩阵而不是整个灰度范围更好。

在此尝试中，我简单地将这些灰度值舍入为0s和1s。这是一个错误，因为它已经冲走了很多细节。

我们只能绕过所有并与灰度版本进行比较，但有更好的方法。

不是0s和1s的每个随机矩阵都是生命状态的有效游戏。绝不是任何细胞自动机的第n代（N＆GT; 0）所谓的伊甸园。我们的单色圆形Mona Lisa几乎是不可能的，这是生命一代的有效游戏。我们只能希望有一个大约接近目标的解决方案。

通过纹理来判断，生活模式的方式发展和从实验到图像，我发现与1位抖动版本相比，目标应该提高结果的质量。

在Mona Lisa抖动图像上的1位抖动具有稍微均匀的0和1个细胞的分布，这有些近似于几代人的初始化的生命状态将如下所示。当您扩展图像时，此属性也会维护，（我们很快就会优化）。

我们可以使用pil（它是Floyd-steinberg抖动）使用image.open（＆＃39; target.png＆＃39;）。转换（＆＃39; 1＆＃39;）

您还可以从最后一个结果中看到，因此无法获得连续的白细胞阵列，因为它们将被过度规则的规则杀死。完全黑暗的区域在生活中稳定。最终结果将是更高的对比度，但Mona Lisa的版本略微变暗。在更高的分辨率下，这种效果并不明显。

单个核心的未驾驶版本非常慢。我在第8个Gen Core i7和Google Colab CPU机器中尝试过这一点，但您需要等待小时/天（取决于目标分辨率）以获取类似于原始的东西。

JAX是一个Python库，可允许您使用Numpy版本并将其编译为可以在GPU / TPU上运行的高度矢量化代码。我们需要为GPU返工此算法。

GPU通常适用于具有良好数据并行性的高吞吐量计算。我们需要利用SIMD（单指令多数据）架构来增益更快的执行速度。

我们将目标（MONA LISA）和帆布（初始随机状态）挤出到第3维度，第3尺寸是Batch_size Long Tensor Boafs（考虑一条面包，每个切片抖动Mona Lisa）。

初始画布将是完全随机的（与图不同）。此外，对于每个循环迭代，我们需要使用此属性生成称为virator（与目标相同的形状）的随机张量：每个切片应该具有所有零，但是在随机位置的一个地方。

数组（[[[1,0]，[0,0]，[0,0]，[[1,0]，[0,0]，[0，0]，[[0,0]， [0,1]，[0，0]，[[0,1]，[0,0]，[0，0]，[[1,0]，[0,0]，[0，0 ]]]）

示例突变仪具有形状5,3,2。Batch_size为5，想法是在每个循环中，我们使用virator从我们的best_canvas计算最近的相邻状态，如本画布=（best_canvas + mutator）％2。

我们在这款修改的画布的每一片中计算了N代的生命游戏。然后，我们做一个3D RMSE（仅用于对阵Mona Lisa的第n个生成画布上的3D RMSE（仅用于切片），并找到具有最低错误的切片。然后将切片挤出并设置为Best_Canvas，循环重复，直到一个有限数量的迭代通行证。

此项目的笔记本电脑可在GitHub中获得。我将解释每个块在本节中正在做些什么。如果要查看结果，请跳到文章的末尾。

这个项目的核心，实际职能的游戏实际上是从这篇文章中取出的。谢谢Bojan Nikolic :)。我按照他的进口JAX.Numpy作为n，JAX.LAX作为L.

％matplotlib内联导入jaxn = jax.numpyl = jax.laxfrom jax.prax.prax.prax.primation导入循环从Jax导入Opsimport Matplotlib.pyplot作为Pltimport Numpy作为onPimport时间从Google.Colab导入文件中的Pilimport over

batch_size = 100image_file = image.open（＆＃34; target.png＆＃34;）image_file = image_file.convert（＆＃39; 1＆＃39;）lisa = n.array（image_file，dtype = n.int32）宽度， height = lisa.shapelisa_loaf = onp.repeat（lisa [onp.newaxis，：：：，]，batch_size，axis = 0）

key = jax.random.progkey（42）canvas_loaf = jax.random.randint（key，（batch_size，宽度，高度），0,2，dtype = n.int32）＃for tests，初始化随机LISA

在这里，我们正在播种Jax PRNG（将很快解释）。此外，我们还使用整数0和1创建初始随机Canvas_LoAF。

@ jax.jitdef rgen（a）：＃此减少超越了直播单元的邻居，因为它包括＃中央单元格本身。减去数组以纠正此问题。 nghbrs = l.reduce_window（a，0，l.add，（3,3），（1,1），＆＃34;同一个＆＃34;） - 出生= n.logical_and（a == 0，nghbrs = = 3）下面= n.logical_and（a == 1，nghbrs＆lt; 2）overpop = n.logical_and（a == 1，nghbrs＆gt; 3）death = n.logical_or（下面，offpop）na = l.select（出生，n。（a.shape，n.int32），a）na = l.select（死亡，n.zeros（a.shape，n.int32），na）返回naverized_ren = jax.vmap (rgen) .jitdef nv_rgen（状态）：对于范围（n_generations）：state =矢量化_rgen（州）返回状态

请阅读B. Nikolc的帖子，以解释RGen功能，这是一代生命游戏。

JAX.VMAP允许我们创建一个函数映射参数轴（矢量化）的输入功能。这让我们在帆布中的每一片中都会在各个切片上运行一代生命游戏。

此外，@ jax.jit python decorator刚刚告诉编译器jit编译此功能。我不确定我们是否在这种情况下有任何改进，因为nv_rgen只是由其他jitted函数组成。

def mutate_nj（b，w，h，subkey）：a = jax.random.normal（subkey，（b，w，h））return（a == a.max（axach =（1,2））[:,无，无]。Astype（int）mutate = jax.jit（mutate_nj，static_argnums =（0,1,2））

Mutate_nj（nj = nonjited）生成我们之前谈过的突变符号。它使用Jax.Random.normal和将每块切片的最大设置为1，并静置到0.即将解释Subkey参数。

我们将此功能作为变异。此外，我们需要将B，W，H参数标记为静态，以便编译器在整个执行中都知道它们是常量。

RMSE非常自我解释。 CPU版本的唯一主要变更是我们在第一个轴上计算平均值（面包的长轴）。

def hill_climb（原始，画布，prng_key，迭代）：使用loops.cope（）作为s：s.best_score = n.inf s.best_canvas = canvas s.canvas = canvas s.prng_key = prng_key for s.range in s.range运行（迭代）：s.prng_key，subkey = jax.random.split（s.prng_key）s.canvas + =修改（batch_size，宽度，高度，子项）s.canvas％= 2 rmse_vals = RMSE（原始，nv_rgen（s.canvas ），batch_size，宽度，高度）curr_min = n.min（rmse_vals）_在s.cond_range（curr_min＆lt; s.best_score）：s.best_score = curr_min s.best_canvas = n.repeat（（s.canvas [n .argmin（rmse_vals）]）[n.newaxis，：：，]，batch_size，axis = 0）s.canvas = s.best_canvas返回s.canvas

Hill_Climb是程序中的主要功能。它是一个大的jax循环构造。我们可以在这里使用标准Python循环，但我们需要充分利用JAX。

JAX循环（JAX.EXPEXPERISHIVAL.LOOPS）是一个像LAX.FORI_LOOP_和LAX.cond这样的句法糖函数。具有多于几个陈述和嵌套的LAX循环（实际XLA循环）变得非常复杂。 JAX（实验）环绕但是将其带来靠近标准Python循环的Somehwat。唯一的警告是环形状态，即。在跨交互突变的任何内容都必须存储为范围成员。对于我们来说，这包括Best_Score，Best_Canvas，我们运行生活和PRNG键的临时画布。

numpy为所有函数都使用托管prng使用。即，播种它并管理它的状态完全由numpy管理。正如我理解的那样，在并行执行（如在GPU中）和需要大量随机的情况下，这种方法具有缺陷。很难确保我们有足够的熵用于生产足够大量的随机性。

与Numpy不同，JAX随机生成是“非托管”。每个JAX.Random函数都需要PRNG当前状态作为第一个参数，并且每次执行其中一个函数时，都必须使用JAX.Random.split更新PRNG状态。

不更新PRNG状态将在又一遍地迅速产生同一组随机。我第一次写入循环时，这部分确实很明白，它导致算法停止查找帆布状态的新变体。这发生了，因为我们一遍又一遍地生成相同的突变纹身。

分离PRNG状态也是确保算法的每个平行分量生成不同的随机性的方法。查找此处Jax Prng Design的更多详细信息

为什么有条件还在JAX中循环？呃..我对此并不肯定。 Cond_Range应该可以输出常规布尔而不是0/1长迭代器。但由于某种原因，它是这样的。

如果我们找到了一个更好的帆布切片，我们会挤出并将其设置为我们的Best_Canvas，它是Best_Score的得分。

经过有限数量的迭代之后，我们获得了一个生命状态的游戏，在一代之后揭示了蒙娜丽莎。

在Google Colab GPU运行时运行〜1000个拍摄483px宽的Mona Lisa仅需要大约40秒！与CPU版本相比，需要几个小时的时间为较小的图像做同样的事情，我认为我们已经实现了我们的目标。

在运行〜23000次迭代（10分钟）后，实现了与目标最高相似性的寿命。 23k后，增益开始大大减少，即使您运行100K迭代，似乎也没有太多。

Mona Lisa，10代棋盘测试模式，7代文本测试模式，5代David由Michelangelo，3代月亮，7代，7代（https://unsplash.com/photos/pd4lo70ldbi）Neil Armstrong，7代我真的在寻找潜入JAX的借口，不一定涉及它是自动差异化能力。 JAX可用于任何适用于张量的一般计算问题。我相信我在这里犯了很多错误，但这对我来说是一种学习经历。

谢谢凯文嘉吉为原来的想法和Bojan Nikolic为寿命游戏。 John Horton Conway FRS（1937年12月26日 - 4月11日4月11日）RIP