Visual Basic 中的遗传算法用于图标生成
0/5 (0投票)
遗传算法的定义和示例；通过模型和随机初始解范围生成图标的 Visual Basic 示例。
范围
在本文中，我们将探讨遗传算法的一些基础知识，即它们是什么，有什么用，为什么我们称它们为“遗传”等等。这不会是一篇纯理论文章，我们将了解如何使用 Visual Basic .NET 实现一个简单的遗传算法。提供了源代码以供进一步实验。
引言
遗传算法可以看作是人工智能领域的一个组成部分。它们本质上是一种搜索技术，利用元启发式算法来实现特定目标，或寻找问题的解决方案。我们使用“遗传”一词是因为，为了解决问题，我们将使用受自然选择过程启发的方法。我们不只是想简单地找到一个解决方案：我们希望创建一个可以“成长”或“进化”以达到我们目标的代码，自己（嗯，差不多）找到出路。
我们的自然世界
赫伯特·斯宾塞在他的《生物学原理》中创造了“适者生存”一词，作为“最能适应当前环境”的同义词。达尔文在他的《物种起源》中引用了斯宾塞的话，并将其与“自然选择”的概念联系起来，这可以理解为“更适合于即时、局部环境”。在任何环境中，环境本身都会设定标准来确定谁是“适者”。
例如，在捕食者众多的地方，生存的基本要求可能是能够高速逃跑，或者熟练地反击。在这样的世界里，跑得快或打得强的人将比那些不具备这些能力的人更有可能长期/更好地生存。我们可以说世界提出了一个问题，比如“你将如何应对这些捕食者？”，那些能找到谜题的好解决方案的人就能生存下来（这是一种过度简化，但毕竟我们不是生物学家！）。
我们可以识别一些参数：一个生存的世界（或“一个待解决的问题”），一个将面对世界挑战的种群（或者，将尝试解决其自然条件所提出问题的个体），一个关于个体如何传承其经验、其成功特征（以及不成功特征）、其 DNA 的故事，希望其后代能越来越好。
在计算机科学中，我们可以从生物学方法中获得启发来解决问题。自然界不会蛮力解决问题，它通过以前答案的重组来创造多种可能的解决方案。同样，这是一种过度简化，因为在现实世界中挑战本身也会改变，但这种方法的基础在数字世界中仍然有效。遗传算法（GAs）继承了一些生物学术语。我们可以识别：染色体/个体，作为给定问题的单一解决方案；种群，作为可能解决方案的数组；基因，或个体的一部分（字节）；适应度，或特定解决方案的充分程度；交叉/近亲繁殖，作为解决方案重组为新解决方案的过程；突变，或可能发生在解决方案中的随机变化。
遗传算法概述
让我们考虑一个简单的问题：我们有一个数值目标，比如说数字 5。这个数字可以看作是我们世界的挑战（或解域）。在我们的世界中，我们将有“居民”，假设种群由一定数量的数学运算组成。
例如，我们一开始取 100 个随机操作。每个操作都必须面对挑战，尝试解决它。这种匹配被称为“适应度”。适应度可以定义为，正如我们上面关于生物所看到的，在给定解域中的充分率。
例如，操作“0 + 0”的适应度会很低，因为它无法产生接近我们目标的值，而“0 + 5”将是一个完美的有效答案。我们必须评估我们种群的每个成员，计算它们每个的适应度。通过这个过程，我们将找到我们问题的最佳（或“最适应”）答案。此时，我们从最好的个体中选取几对，“近亲繁殖”它们以产生共享父母双方特征的新元素，并对我们整个种群重复这个过程（如果我们希望保持特定数量的元素，在过程结束时，我们必须丢弃与新创建元素数量相等的质量最差的元素）。
新一代的解决方案诞生了——我们希望它们更接近我们的目标——等待着接受我们问题的测试。重复这个过程直到诞生有效的解决方案。生物体将其 DNA、其遗传密码传递给它们的子孙后代。在计算机科学中，一切都由字节组成，我们可以将它们视为一种数字 DNA，是个体是什么的表示。在上面的例子中，我们可以用六个字节来表示一个操作：前两个和最后两个字节表示 0 到 255 之间的数字（从 00 到 FF），而它们之间的两个字节可以表示操作符（例如 00 = +，01 = - 等）。
通过繁殖阶段，我们从一个亲本中提取一部分字节，从另一个亲本中提取一部分字节，并将它们组合起来，我们就得到了一个新个体。就像在真实环境中一样，我们可以考虑引入一种“突变”，它可以在某些方面改变传递的基因。换句话说，遗传算法就是通过创造越来越好的解决方案来找到解决特定问题的最佳途径。有关更具体的信息，请查看文章末尾的参考文献。
一个实际的实现
言语是好的，但当涉及到编程时，它们相当廉价，而一段代码抵得上千言万语。所以，让我们看看如何以实际的方式从遗传算法中获益。在下面的代码中，我们将讨论一个图形问题：给定一个目标图标，并从由随机字节组成的图像种群开始，尝试将我们的随机像素“进化”到目标，希望能完全达到它。
正如我在开头所说，我们将为此使用 Visual Basic。最终用户必须能够选择一个 16x16 像素的 ICO 文件，程序将生成 100 个随机图标。对于这些图标中的每一个，我们将评估它们的适应度。这很简单：由于图标是字节数组，我们只需将目标字节与每个种群元素的字节进行匹配。它们越相似，我们的图像就越好。对于每一代解决方案，我将提取 4 个元素进行近亲繁殖，生成 4 个全新的个体，其中复制了它们父母的字节，并丢弃 4 个最差的元素以保持 100 个元素的恒定种群。
遗传图像类
我们的“遗传图像”类可以这样写
Public Class GAImage
Const _FIXED_BYTES As Integer = 42
Dim _targetBytes() As Byte
Dim _personalBytes() As Byte
Dim _isMutable() As Boolean
Public ReadOnly Property FixedBytes As Integer
Get
Return _FIXED_BYTES
End Get
End Property
Public Property PersonalBytes As Byte()
Get
Return _personalBytes
End Get
Set(value As Byte())
_personalBytes = value
End Set
End Property
Public ReadOnly Property Fitness As Single
Get
Dim _fitness As Single = 0
For ii As Integer = 0 To _targetBytes.Length - 1
If _targetBytes(ii) = _personalBytes(ii) Then
_fitness += 1
_isMutable(ii) = False
End If
Next
Return _fitness
End Get
End Property
Public ReadOnly Property FitnessPercent As Single
Get
Return (Me.Fitness * 100 / _targetBytes.Length).ToString("000.00")
End Get
End Property
Public Function isByteMutable(numByte As Integer) As Boolean
Return _isMutable(numByte)
End Function
Public Sub New(_target() As Byte, _code() As Byte, Optional randomInit As Boolean = True)
ReDim _personalBytes(_target.Length - 1)
ReDim _targetBytes(_target.Length - 1)
_targetBytes = _target
ReDim _isMutable(_target.Length - 1)
For ii As Integer = 0 To _isMutable.Length - 1
_isMutable(ii) = True
Next
For ii As Integer = 0 To _FIXED_BYTES
_personalBytes(ii) = _targetBytes(ii)
Next
If Not randomInit Then Exit Sub
Randomize()
For ii As Integer = _FIXED_BYTES + 1 To _targetBytes.Length - 1
_personalBytes(ii) = _code(Int(Rnd() * (_code.Length - 1)))
Next
End Sub
End Class
它的构造函数需要目标字节的副本、从中提取的遗传池以及一个标志来确定是否必须进行随机初始化（我们将在几行中看到原因）。该类公开了一些属性：PersonalBytes 允许访问我们个体的“遗传密码”，返回其字节数组；Fitness 计算当前图像和目标图像的相似程度。
在 _isMutable 数组的帮助下，我们将设置一个特定字节是否对突变具有抵抗力（模仿一种坚实的遗传获得性状）；FitnessPercent 简单地以百分比格式公开之前的值；FixedBytes 具有纯技术实用性：由于前 42 个字节代表图标的头部，这些字节必须从目标图像复制到个体中，以生成一组有效的图标。在这个类中，我们拥有生成成熟遗传图标所需的一切。
我们需要一个环境来展示我们的游戏。一个简单的表单，可以观察我们的世代如何变化。
操场
让我们看看我们的表单最终会是什么样子
“选择目标”按钮允许用户选择一个图标，这将是我们要通过进化解决方案达到的图像。动态创建了 100 个 PictureBox 以包含每个 GAImage 的输出。生成了随机的 GAImage，我们可以看到它们与目标之间没有明显的关联（其中充满了混乱！）。尽管如此，通过评估它们，我们可以识别出更好的样本，并开始我们的繁殖循环。
让我们看一个典型的执行过程，稍后讨论它的每个部分。
我将完全跳过与控件创建或使用相关的部分，读者可以在源代码中看到。这里讨论的仅与遗传算法的各个方面相关。为了便于理解，下面的大部分代码都是不完整的。我建议下载源代码以获得最完整的概览。
创建起始解决方案集
在打开目标图像时，我们可以访问它的字节。目标图像的字节将是我们理想的遗传密码，每个字节代表每个创建的个体从中获取其个人 DNA 的遗传池中的一个元素。
Private Sub LoadImage(path As String)
Dim b As New Icon(path)
pbOriginal.Image = b.ToBitmap
Dim ms As New MemoryStream
b.Save(ms)
ReDim _targetBytes(ms.ToArray.Length - 1)
_targetBytes = ms.ToArray
_GACode = New List(Of Byte)
Dim _tmpCode As New List(Of Byte)
_tmpCode.AddRange(_targetBytes)
_GACode.AddRange(From bt As Byte In _tmpCode Distinct Select bt)
End Sub
目标图标写入 pbOriginal PictureBox 中。之后，通过 MemoryStream 访问图像的字节并写入 _targetBytes 数组。从该数组中，我们选择不同的值来填充一个可能的“基因”列表，用于创建新图标。将其视为我们的遗传密码：DNA 由腺嘌呤、鸟嘌呤、胞嘧啶、胸腺嘧啶组成。我们的图标遗传密码必须遵循一条不完全随机的路径：如果原始集合不包含字节 AF，例如，我们的起始字节池也不会包含它（即，不可能生成包含“标准”池中缺失字节的样本）。
Private Sub InitializePopulation()
_GAPopulation = New List(Of GAImage)
For ii As Integer = 0 To _SAMPLE_NUMBER - 1
Dim _ga As New GAImage(_targetBytes, _GACode.ToArray)
_GAPopulation.Add(_ga)
Dim pb As PictureBox = CType(GroupBox3.Controls("pbSample" & ii.ToString("00")), PictureBox)
Try
pb.Image = Image.FromStream(New MemoryStream(_ga.PersonalBytes))
Catch
End Try
Next
End Sub
我们填充一个由 GAImages 组成的起始列表，使用目标字节数组初始化它们（正如我们所看到的，这对于适应度计算很有用），并传递可以从中提取字节的池。有关初始化过程的详细信息，请参阅上面的 GAImage 代码。
我在上面的例子中使用的图标长 318 字节：起始种群的成员不太可能产生我们的最终结果。
有必要通过代际循环，结合每组中最好的项目。
进化的建议
让我们看看我提出的进化行为。在我的代码中，它发生在单击 Button2 控件时。省略了与遗传算法无关的代码（请参阅源代码）。
Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click
' omission
While _runFlag
' omission
Dim bestSamples As IEnumerable(Of GAImage) = From ga As GAImage In _GAPopulation Order By ga.Fitness Descending Take (4)
' omission
If bestSamples(0).FitnessPercent > 95 Then Button3_Click(sender, e)
Dim sample01 As GAImage = GenerateImage(bestSamples(0), bestSamples(1))
Dim sample02 As GAImage = GenerateImage(bestSamples(1), bestSamples(0))
Dim sample03 As GAImage = GenerateImage(bestSamples(2), bestSamples(3))
Dim sample04 As GAImage = GenerateImage(bestSamples(3), bestSamples(2))
_GAPopulation.Insert(0, sample01)
_GAPopulation.Insert(1, sample02)
_GAPopulation.Insert(2, sample03)
_GAPopulation.Insert(3, sample04)
Dim worstSamples As IEnumerable(Of GAImage) = From ga As GAImage In _GAPopulation Order By ga.Fitness Ascending Take (4)
_GAPopulation.Remove(worstSamples(0))
_GAPopulation.Remove(worstSamples(1))
_GAPopulation.Remove(worstSamples(2))
_GAPopulation.Remove(worstSamples(3))
' omission
End While
End Sub
就像这样，我们无限循环遍历 GAImages 列表（或者，至少直到达到 95% 的结果），每次取 4 个最适应的样本，并交叉它们的字节。我们将新创建的个体插入列表的顶部（假设它们是最好的），并删除数量相等、适应度最差的元素。在生成阶段，如果出现问题，新创建的元素可能比现有元素更差。在这种情况下，它仍然会被丢弃。
Private Function GenerateImage(firstGA As GAImage, secondGA As GAImage) As GAImage
Dim _ga As New GAImage(_targetBytes, _GACode.ToArray, False)
For ii As Integer = _ga.FixedBytes To firstGA.PersonalBytes.Length - 1 Step 1
_ga.PersonalBytes(ii) = IIf(secondGA.isByteMutable(ii), Mutation(secondGA.PersonalBytes(ii), 2), Mutation(secondGA.PersonalBytes(ii), 20))
Next
Return _ga
End Function
近亲繁殖非常简单：遍历第一个元素的每个可访问字节，计算结果字节如下：如果第二个元素的相同字节具有抗突变性，我们以 1/20 的概率调用突变例程。否则，我们使用 1/2 的概率。
Private Function Mutation(bt As Byte, rate As Byte) As Byte
Randomize()
Dim prob As Integer = Int(Rnd() * rate)
If prob Mod rate = 0 Then
Return _GACode(Int(Rnd() * (_GACode.Count - 1)))
Else
Return bt
End If
End Function
突变() 以一定的概率发生：如果突变率达到，特定字节会从标准池中随机提取。否则，第二个元素字节会在后代中复制。每个世代/种群的单代循环最终会进化到最终（预期的）结果。这只是实现进化算法的方法之一：每个编码器在定义要质疑的参数以及解决特定问题的通用规则时都是裁判。
在我们的案例中，只要能带来有效的结果，其他类型的方法也是可能的。
示例视频
示例运行会话可在此处查看：http://youtu.be/g6_JebAjtWQ
下载源代码
参考文献
- http://en.wikipedia.org/wiki/DNA
- http://en.wikipedia.org/wiki/Natural_selection
- http://en.wikipedia.org/wiki/Genetic_algorithm
历史
- 2015-01-16：CodeProject 首次发布