遗传算法 WebForms 所有主题中级开发 Visual Studio Windows .NET Visual Basic

遗传算法求解 Visual Basic 中的二维迷宫

Emiliano Musso

5.00/5 (6投票s)

2015年2月8日

CPOL

16分钟阅读

20818

如何将 GA 技术应用于 VB.NET 中的问题解决。示例演示了如何为二维迷宫创建解决方案，该解决方案将演化以找到两点之间的最短路径。

范围

在本文中，作为«用 Visual Basic 进行图标生成的遗传算法»的续篇，我们将看到遗传算法如何应用于我们事先没有模型（或没有理想目标可达）的问题，尽管我们知道哪些是趋向于解决方案的最佳参数。换句话说，我们将讨论遗传算法（GA）在解决方案优化方面的应用。我们将再次使用 Visual Basic .NET 来开发一个示例应用程序。

引言

在上篇文章中，我们考虑了如何从给定的图形模型开始，生成一组随机且混乱的解决方案，然后通过不断选择每组中的最佳样本，将它们的信息进行交叉以创建新的冠军，可能还会改进，从而朝着目标演化。虽然这些是探索 GA 的有趣方式，但当讨论那些编码为严格模型而增长的算法时，它们显然需要一个完整且理想的起始解决方案。这意味着如果我们没有最终结果来匹配我们创建的每个解决方案，我们就无法从混乱中演化，因为它们不会针对任何特定性进行定向，我们的算法将陷入无限的随机样本循环。

显然，GA 无论如何都必须有一个目标。然而，一个整体模型并非总是必需的，但——在我们定义了预期的最佳条件后——让算法找到满足这些要求的解决方案（或给定问题的最佳解决方案）。这在人类知识的许多领域都有很多实际应用。但由于我们玩得更好，我们将在此看到一个 Visual Basic GA 的例子，该算法旨在解决二维迷宫，并尝试——通过先前看到的功能——不仅连接空间中的两点，而且以一种更好的方式做到这一点——即寻找最短路径。

简要回顾

让我们回顾一些之前强调过的概念，以便随用随查。GA 之所以如此命名，是因为它试图模仿物种进化核心中的生物过程。我们可以说它的目标是创建一个能够自我调整以适应特定上下文的计算机模型，生成个体（给定问题的解决方案），用于评估实现给定目标的真实程度。要解决的问题是生物环境中个体的数字等价物，遵循“适者生存”的原则。在上一篇文章中，我使用了充满捕食者的世界的例子，其中最快的居民（更适合高效飞行）或最善战的（更适合高效战斗）代表了生存的最佳候选者，与更慢或更弱的样本相比。同样，如果我们有一个数字目标（生物生存的基本参数的等价物），我们可以根据潜在解决方案接近给定目标的程度来谈论“适宜的个体”。其中，正如大自然所做的那样，我们将尝试识别最佳解决方案以使其繁殖，生成承载其父母特征的新解决方案。第一篇文章中展示了一个快速示例：给定一个特定的图形图标（一个生成图像的字节数组），从固定数量的混乱解决方案开始，在每一代中，最佳解决方案是那些类似于它们的目标的解决方案。

GA 的生物学灵感也体现在其术语中。在该领域，我们将讨论：

个体/染色体的概念，即给定问题的单个解决方案；
种群，或所有可能解决方案的集合；
基因，即个体的一部分（字节）；
适应度（Fitness），意指解决方案/个体中的有效性比率；
交叉（Crossing-over），即解决方案的重组以产生新的模型、新的染色体/个体；
变异（Mutation），意指可能发生在解决方案中的随机（或伪随机）变化；

所有这些概念在数字世界中都是有效的，并且必须以某种方式实现才能被称为真正的基于 GA 的解决方案，或能够自动进化的解决方案。开发者必须在理论和实践上定义它们中的每一个，以处理每个阶段。

优化解决方案

原则上，即使在处理图像复制的情况下，在谈论 GA 时，我们总是可以想到优化。事实上，每个 GA 的情况——最终——都是寻找最佳解决方案，无论它是指达到理想目标还是陷入令人满意的局部最优。我们所说的“局部最优”，是指由于某些种群特征，在交叉后无法产生改进，导致无法进一步提高到给定的精度率。防止停滞的方法可以通过变异来应用，通过变异，我们随机地在新建的解决方案中引入变化，以保持在代与代之间传递信息时一个小的混乱常数。

尽管我们可以一直引用优化的概念，但在应用于后勤问题时，它会更加明显。假设我们在迷宫中，它提供了多种到达目的地的方法。在那里，我们可以根据内部地形允许的方式移动，并且不能排除我们可能会走回头路，或者永远无法到达目的地。本质上，在这样的迷宫中，有许多方法可以达到解决方案……但也存在一个比其他解决方案更好的解决方案。在这样的地方，最好的道路是引导我们从起点到终点以直线方式，用最少的步数（即最优解决方案）。GA 可以帮助我们找到那条路径，而无需事先知道可能性是什么。我们注意到这不仅仅是找到到达的方法，而是测试其有效性，并考虑什么将是更好的。

基本结构

为了能够思考一个迷宫，我们必须有一个迷宫。在这里，我们将看到我在示例中使用的基础，以简要解释我们将要工作的地面是什么。像往常一样，在文章的末尾，您会找到下载示例源代码的链接，我邀请您参考该链接以更详细地了解本文未涉及的方面。运行示例代码，我们将看到一个类似这样的窗口

该程序将创建两个具有 20 个单元格的窗口，它们将用作构成用户定义的迷宫（左侧）和显示找到的解决方案（右侧）的元素的图形表示。在左侧面板中，用户可以单击每个单元格一定次数。下表简要说明了每次单击对单元格的影响：

1 次单击 = “墙”单元格（灰色，无法通行）
2 次单击 = 起点（绿色，迷宫的入口点）
3 次单击 = 终点（红色，迷宫的出口点）
4 次单击 = 有效单元格（在创建迷宫时未使用，将属于 GA）
5 次单击 = “空”单元格（黑色，可穿越的单元格）

为了能够快速测试程序，我实现了两个按钮来保存和加载先前创建的迷宫。在源代码包中，我提供了“test_maze.txt”文件，这就是我们在本示例中使用的文件。加载该文件后，我们将获得以下迷宫：

我们可以立即看到起点和终点之间有许多可能的解决方案。在深入 GA 部分之前，我将花一些时间谈谈迷宫的创建，以解释其底层逻辑：这将有助于更好地理解算法本身。

在 VB 中实现迷宫

我们的迷宫有一个由二维字节数组组成的基座，名为 sourceMaze()。其中的每个单元格都代表数组的一个位置，形式为 (X,Y)。这些字节中的每一个都设置为一个值，该值表示特定单元格的当前状态。这些值与一个枚举相关联，该枚举在 Globals.vb 文件中可见。

Module Globals
    Public Const MAZESIZE As Byte = 20
    Public Const MAZESIDE As Byte = 15
 
    Public Enum CELLSTATE
        Free = 0
        Wall = 1
        Start = 2
        Finish = 3
        Valid = 4
        FakeWall = 5
    End Enum
End Module

除了上面讨论的值之外，还有一个附加值，即 FakeWall = 5。当我们分析解决方案如何创建时，我们将很快谈论它。

在窗体加载期间，会调用绘制迷宫的例程。绘图操作通过 MazeCell 控件完成，这些控件是 PictureBox 的扩展，用于包含数据数组中的数据。

Private Sub GenerateMaze(container As Panel)
    Dim _TOP As Integer = 0
    Dim _LEFT As Integer = 0
 
    For _Y As Integer = 0 To MAZESIZE - 1
        For _X As Integer = 0 To MAZESIZE - 1
 
            Dim pb As New MazeCell
            With pb
                .Name = container.Name & _Y.ToString("00") & _X.ToString("00")
                .Top = _TOP
                .Left = _LEFT
                .Width = MAZESIDE
                .Height = MAZESIDE
                .BackColor = Color.Black
                .BorderStyle = BorderStyle.FixedSingle
                .Cursor = Cursors.Hand
 
                .MatX = _X
                .MatY = _Y
 
                AddHandler pb.Click, AddressOf MazeClickCell
            End With
 
            _LEFT += MAZESIDE
            container.Controls.Add(pb)
        Next
        _LEFT = 0
        _TOP += MAZESIDE
    Next
End Sub

GenerateMaze() needs an argument of type Panel, which represents the owner control in which we'll generate our strcture. Next, with two nested loops, cells are created. They will be bound with the sourceMaze array during MazeClickCell event, defined as:

Private Sub MazeClickCell(sender As Object, e As EventArgs)
    Dim pb As MazeCell = CType(sender, MazeCell)
 
    pb.CellStatus += 1
    If pb.CellStatus > CELLSTATE.Valid Then pb.CellStatus = CELLSTATE.Free
 
    sourceMaze(pb.MatX, pb.MatY) = pb.CellStatus
    pb.BackColor = pb.CellBrush
End Sub

我们可以注意到，与标准的 PictureBox 相比，MazeCell 控件具有额外的属性，例如 MatX，它标识矩阵中的单元格横坐标，MatY，它表示纵坐标，CellStatus，它公开单元格的内容，以及 CellBrush，它——根据单元格的状态——用颜色表示该单元格。实现 MazeCell 扩展的源代码如下：

Public Class MazeCell
    Inherits PictureBox
 
    Dim _STATUS As Byte = 0
    Dim _MATX As Byte = 0
    Dim _MATY As Byte = 0
 
    Public Property CellStatus As Byte
        Get
            Return _STATUS
        End Get
        Set(value As Byte)
            _STATUS = value
        End Set
    End Property
 
    Public ReadOnly Property CellBrush As Color
        Get
            Select Case CellStatus
                Case CELLSTATE.Free
                    Return Color.Black
                Case CELLSTATE.Valid
                    Return Color.Violet
                Case CELLSTATE.Start
                    Return Color.Green
                Case CELLSTATE.Finish
                    Return Color.Red
                Case CELLSTATE.Wall
                    Return Color.Gray
                Case CELLSTATE.FakeWall
                    Return Color.Yellow
            End Select
        End Get
    End Property
 
    Public Property MatX As Byte
        Get
            Return _MATX
        End Get
        Set(value As Byte)
            _MATX = value
        End Set
    End Property
 
    Public Property MatY As Byte
        Get
            Return _MATY
        End Get
        Set(value As Byte)
            _MATY = value
        End Set
    End Property
 
    Public ReadOnly Property StringMatrix As String
        Get
            Return _MATX.ToString & ";" & _MATY.ToString
        End Get
    End Property
End Class

当前的结构允许用户定义自己的基础迷宫，然后将其作为 GA 的基础传递，或将其保存以供将来参考（我已经实现——但未优化——基本的保存和加载迷宫数据的例程，但为了专注于主题的基本原理，我不会在这里讨论它们）。

遗传算法逻辑

现在我们有了一个操作上下文，我们可以开始考虑自动机的探索可能性。我们上面提到了每种单元格类型的适用规则，因此我们知道通用探索算法必须具备的基本要求（请注意：是通用，不是遗传）。我们知道它必须从绿色单元格开始移动，尝试到达红色单元格，而不穿越灰色单元格。所有黑色单元格都可以探索/踩踏。我们可以考虑一个例程，给定一个起始点，评估四个相邻单元格的状态，然后递归地穿越那些被认为是空的单元格。

换句话说，设 solverBytes() 是包含给定解决方案的数组，如下所示的函数将完成：

Private Function Solve(_X As Integer, _Y As Integer) As Boolean
    If solverBytes(_endPos(0), _endPos(1)) = CELLSTATE.Valid Then Return True
 
    If solverBytes(_X + 1, _Y) = CELLSTATE.Free Or solverBytes(_X + 1, _Y) = CELLSTATE.Start Or solverBytes(_X + 1, _Y) = CELLSTATE.Finish Then
        solverBytes(_X + 1, _Y) = CELLSTATE.Valid
        If Solve(_X + 1, _Y) Then Return True
    End If
 
    If solverBytes(_X - 1, _Y) = CELLSTATE.Free Or solverBytes(_X - 1, _Y) = CELLSTATE.Start Or solverBytes(_X - 1, _Y) = CELLSTATE.Finish Then
        solverBytes(_X - 1, _Y) = CELLSTATE.Valid
        If Solve(_X - 1, _Y) Then Return True
    End If
 
    If solverBytes(_X, _Y + 1) = CELLSTATE.Free Or solverBytes(_X, _Y + 1) = CELLSTATE.Start Or solverBytes(_X, _Y + 1) = CELLSTATE.Finish Then
        solverBytes(_X, _Y + 1) = CELLSTATE.Valid
        If Solve(_X, _Y + 1) Then Return True
    End If
 
    If solverBytes(_X, _Y - 1) = CELLSTATE.Free Or solverBytes(_X, _Y + 1) = CELLSTATE.Start Or solverBytes(_X, _Y + 1) = CELLSTATE.Finish Then
        solverBytes(_X, _Y - 1) = CELLSTATE.Valid
        If Solve(_X, _Y - 1) Then Return True
    End If
 
    Return False
End Function

如您所见，给定起始点和 [_X,_Y] 坐标将导致函数循环（并递归调用自身），直到所有导致解决方案的单元格都被穿越。换句话说，算法将探索整个解决方案域。将函数应用于我们的迷宫，我们将得到一个类似这样的解决方案：

显然，这将是一个包含性的解决方案，其唯一目的是追踪所有可能性。它是最具分散性的解决方案。尽管如此，它在特定情况下可能有其用处（请注意，在概念层面，我们的函数是微不足道的图形洪水填充，考虑到绘图边距），但这并不是我们在这里想要获得的。我们开始看到 GA 的特点：它必须能够做什么？在我们的例子中，它必须尝试解决迷宫，而不是试图大规模占用空间。因此，通过生成能够解决我们问题的个体，我们可以引入一种限制器。

我们在 CELLSTATE 枚举中看到了上面的限制器，值为 FakeWall = 5。当我们生成一个新个体时，我们将在其中引入一些“污垢”，以“伪墙”来改变 Solve() 函数的结果，精确地说是墙，它们不是基本迷宫结构中的墙，但具有标准墙的相同行为。

为了更容易发现，我们将使用黄色绘制它们。如前所述，这些是任意限制器，它们响应与传统墙壁相同的不可逾越定律，并且对于每个生成的个体，用于界定解决方案域。事实上，我们可以注意到，在有黄色墙壁的地方，从那里开始的迷宫探索就被阻塞了。这种随机性允许我们生成一个多样的种群：它将包含解决迷宫的个体，以及无法到达出口的个体（例如，想想一个位于红色单元格正前方的黄色单元格）。接下来，每个解决方案将需要一定步数才能完成。有些个体将以更直接的方式到达红色单元格，而其他个体将遵循更曲折的路径，变得更分散。

VB 中的一个假设解决方案

现在让我们看看 GASolver 类的代码，它代表单个个体或解决方案。请注意，它有一个通用构造函数，其中一个参数期望用户定义的迷宫的数组，以便在每个解决方案中复制代表墙壁、起点、终点的字节，这些是解决迷宫的基本先决条件，因为它们是固定的。通过一定的概率，一个或多个单元格将取 FakeWall 值，以便在绘制迷宫时，用户保留的空白单元格处添加限制器。

Public Class GASolver
 
    Dim _startpos(1) As Byte
    Dim _endPos(1) As Byte
    Dim _isSolved As Boolean
 
    Dim solverBytes(MAZESIZE, MAZESIZE) As Byte
 
    Public ReadOnly Property StartPos As Byte()
        Get
            Return _startpos
        End Get
    End Property
 
    Public ReadOnly Property EndPos As Byte()
        Get
            Return _endPos
        End Get
    End Property
 
    Public ReadOnly Property GetBytes As Byte(,)
        Get
            Return solverBytes
        End Get
    End Property
 
    Public ReadOnly Property Steps As Integer
        Get
            Dim _steps As Integer = 0
            For _Y As Integer = 0 To MAZESIZE - 1
                For _X As Integer = 0 To MAZESIZE - 1
                    If solverBytes(_X, _Y) = CELLSTATE.Valid Then _steps += 1
                Next
            Next
 
            Return _steps
        End Get
    End Property
 
    Public ReadOnly Property isSolved As Boolean
        Get
            Return Solve(_startpos(0), _startpos(1))
        End Get
    End Property
 
    Private Function Solve(_X As Integer, _Y As Integer) As Boolean
        If solverBytes(_endPos(0), _endPos(1)) = CELLSTATE.Valid Then Return True
 
        If solverBytes(_X + 1, _Y) = CELLSTATE.Free Or solverBytes(_X + 1, _Y) = CELLSTATE.Start Or solverBytes(_X + 1, _Y) = CELLSTATE.Finish Then
            solverBytes(_X + 1, _Y) = CELLSTATE.Valid
            If Solve(_X + 1, _Y) Then Return True
        End If
 
        If solverBytes(_X - 1, _Y) = CELLSTATE.Free Or solverBytes(_X - 1, _Y) = CELLSTATE.Start Or solverBytes(_X - 1, _Y) = CELLSTATE.Finish Then
            solverBytes(_X - 1, _Y) = CELLSTATE.Valid
            If Solve(_X - 1, _Y) Then Return True
        End If
 
        If solverBytes(_X, _Y + 1) = CELLSTATE.Free Or solverBytes(_X, _Y + 1) = CELLSTATE.Start Or solverBytes(_X, _Y + 1) = CELLSTATE.Finish Then
            solverBytes(_X, _Y + 1) = CELLSTATE.Valid
            If Solve(_X, _Y + 1) Then Return True
        End If
 
        If solverBytes(_X, _Y - 1) = CELLSTATE.Free Or solverBytes(_X, _Y + 1) = CELLSTATE.Start Or solverBytes(_X, _Y + 1) = CELLSTATE.Finish Then
            solverBytes(_X, _Y - 1) = CELLSTATE.Valid
            If Solve(_X, _Y - 1) Then Return True
        End If
 
        Return False
    End Function
 
    Public Sub New(bytes01(,) As Byte, bytes02(,) As Byte, startPos As Byte(), endPos As Byte())
        _startpos = startPos
        _endPos = endPos
 
        For _Y As Integer = 0 To MAZESIZE - 1
            For _X As Integer = 0 To MAZESIZE - 1
                If bytes01(_X, _Y) = CELLSTATE.Wall Then solverBytes(_X, _Y) = bytes01(_X, _Y)
                If bytes01(_X, _Y) = CELLSTATE.FakeWall Then solverBytes(_X, _Y) = bytes01(_X, _Y)
            Next
        Next
 
        For _Y As Integer = 0 To MAZESIZE - 1
            For _X As Integer = 0 To MAZESIZE - 1
                If bytes02(_X, _Y) = CELLSTATE.Wall Then solverBytes(_X, _Y) = bytes02(_X, _Y)
                If bytes02(_X, _Y) = CELLSTATE.FakeWall Then solverBytes(_X, _Y) = bytes02(_X, _Y)
            Next
        Next
 
        For _Y As Integer = 0 To MAZESIZE - 1
            For _X As Integer = 0 To MAZESIZE - 1
 
                If solverBytes(_X, _Y) <> CELLSTATE.Wall Then
                    Randomize()
                    If Int(Rnd() * 100) Mod 99 = 0 Then
                        If Int(Rnd() * 100) Mod 99 = 0 Then
                            solverBytes(_X, _Y) = CELLSTATE.FakeWall
                        Else
                            solverBytes(_X, _Y) = CELLSTATE.Free
                        End If
                    End If
                End If
 
            Next
        Next
 
        solverBytes(startPos(0), startPos(1)) = CELLSTATE.Start
        solverBytes(endPos(0), endPos(1)) = CELLSTATE.Finish
    End Sub
 
    Public Sub New(sourceBytes(,) As Byte)
        For _Y As Integer = 0 To MAZESIZE - 1
            For _X As Integer = 0 To MAZESIZE - 1
 
                If sourceBytes(_X, _Y) = CELLSTATE.Start Then _startpos(0) = _X : _startpos(1) = _Y
                If sourceBytes(_X, _Y) = CELLSTATE.Finish Then _endPos(0) = _X : _endPos(1) = _Y
 
                If sourceBytes(_X, _Y) = CELLSTATE.Free Then
                    Randomize()
                    If Int(Rnd() * 100) Mod 50 = 0 Then
                        solverBytes(_X, _Y) = CELLSTATE.FakeWall
                    Else
                        solverBytes(_X, _Y) = CELLSTATE.Free
                    End If
                Else
                    solverBytes(_X, _Y) = sourceBytes(_X, _Y)
                End If
 
            Next
        Next
 
    End Sub
End Class

Solve() 函数也存在，以便能够确定解决方案是否可以到达出口单元格，或者它在其他地方失败。还有其他属性和函数将很快进行分析。

解决方案的适应度

正如我们在上一篇文章中看到的，GA 的一个基本部分是能够确定在面对给定问题时的适应度得分。不言而喻，该得分的计算方式取决于问题的类型。适应度至关重要，因为当我们有一个由或多或少接近我们目标的解决方案组成的种群时，它允许我们提取一些具有我们可能想要尝试改进个体生成的潜在特征的冠军。因此，很明显，设计适应度计算器函数中的错误将是实现 GA 失败的基石。

在尝试限制因错误地将适应度归因于一个或多个解决方案而产生的问题时，深入分析问题是必须的。在图像复制等情况下更为简单：我们知道它——本质上——是一个以特定方式排序的字节数组，解决方案的适应度通过检查目标和解决方案之间共享了多少字节来计算。当面对开放问题时，例如当前问题，需要向前迈出一步。在这里，我们不关心评估与预定义模型的亲和力，而是想讨论解决方案的潜在有效性。

简化地说，在迷宫的情况下，我们关心上面已经提到的两个方面：

解决方案必须导致一个有效的结局，它必须到达目的地
解决方案必须快速：在满足先决条件 1）之后，它必须能够以最简洁的方式实现它

我们可以说，在我们的案例中，适应度计算通过两个属性实现：第一个是目标的可达性，第二个是所花费的步数，步数越少，解决方案的质量越高。为此，GASolver 类实现了两个相应的属性：isSolver，它返回一个布尔值以了解某个个体是否到达目标，以及 Steps，它计算解决方案中有效单元格的数量。

初始化和交叉

初始化的概念遵循简单的规则：它是关于创建第一代解决方案，使用标准的构造函数。在附加的源代码中，该操作发生在 btnInit 按钮的 Click 事件中。

Private Sub btnInit_Click(sender As Object, e As EventArgs) Handles btnInit.Click
    epochs = 0
 
    For _Y As Integer = 0 To MAZESIZE - 1
        For _X As Integer = 0 To MAZESIZE - 1
            If sourceMaze(_X, _Y) = CELLSTATE.Start Then _startPos(0) = _X : _startPos(1) = _Y
            If sourceMaze(_X, _Y) = CELLSTATE.Finish Then _endPos(0) = _X : _endPos(1) = _Y
        Next
    Next
 
    gaList = New List(Of GASolver)
    For ii As Integer = 0 To 999
        gaList.Add(New GASolver(sourceMaze))
    Next
 
    gaCursor = 0
    MazePaintItem(mazeDest)
 
    btnStart.Enabled = True
    btnStop.Enabled = False
End Sub

我们重置一个将用于计算代数的计数器，然后保存用户定义的起点和终点单元格。在一个 List(OF GASolver) 中，我们将通过 LINQ 查询它，我们将添加所需数量的新创建的 GASolver（在本例中为 1000 个），以便进行图形表示。每个初始解决方案，如我们所见，将通过在用户保留的空白处添加虚拟限制器来初始化，以在种群中创建多样性。

通过按下 btnStart 按钮，将开始搜索解决方案。请注意，我们将在每次循环中提取那些解决迷宫的元素（ga.isSolved = True），并按完成任务的步数排序（Order By ga.Steps Ascending）。这样，我们将确保一次提取两个最佳解决方案。这些元素将被重组，产生两个新元素，遵循我们将稍后看到的规则。最后，按步数降序排列我们的列表，我们可以丢弃两个最差的元素。请注意，我们不会对解决方案的质量应用任何区分，并且有可能丢弃那些得出有效解决方案的元素，但它们有一个缺陷，即——在所有解决方案中——它们是最分散的。

生成两个新元素的交叉是通过 GASolver 类的四参数构造函数来解释的，如下所示：

Public Sub New(bytes01(,) As Byte, bytes02(,) As Byte, startPos As Byte(), endPos As Byte())
    _startpos = startPos
    _endPos = endPos
 
    For _Y As Integer = 0 To MAZESIZE - 1
        For _X As Integer = 0 To MAZESIZE - 1
            If bytes01(_X, _Y) = CELLSTATE.Wall Then solverBytes(_X, _Y) = bytes01(_X, _Y)
            If bytes01(_X, _Y) = CELLSTATE.FakeWall Then solverBytes(_X, _Y) = bytes01(_X, _Y)
        Next
    Next
 
    For _Y As Integer = 0 To MAZESIZE - 1
        For _X As Integer = 0 To MAZESIZE - 1
            If bytes02(_X, _Y) = CELLSTATE.Wall Then solverBytes(_X, _Y) = bytes02(_X, _Y)
            If bytes02(_X, _Y) = CELLSTATE.FakeWall Then solverBytes(_X, _Y) = bytes02(_X, _Y)
        Next
    Next
 
    For _Y As Integer = 0 To MAZESIZE - 1
        For _X As Integer = 0 To MAZESIZE - 1
 
            If solverBytes(_X, _Y) <> CELLSTATE.Wall Then
                Randomize()
                If Int(Rnd() * 100) Mod 99 = 0 Then
                    If Int(Rnd() * 100) Mod 99 = 0 Then
                        solverBytes(_X, _Y) = CELLSTATE.FakeWall
                    Else
                        solverBytes(_X, _Y) = CELLSTATE.Free
                    End If
                End If
            End If
 
        Next
    Next
 
    solverBytes(startPos(0), startPos(1)) = CELLSTATE.Start
    solverBytes(endPos(0), endPos(1)) = CELLSTATE.Finish
End Sub

本质上，它需要两个数组，分别对应于要重组的元素的字节，以及两对坐标，即迷宫的起点和终点。

循环遍历两个矩阵，生成一个结果矩阵，其中包含 Wall 和 FakeWall 类型的组合。Wall 单元格在两者之间是相同的，但 FakeWall 可能会有所不同。如果两个解决方案都到达了一个有效的终点，这意味着来自两个矩阵的 FakeWall 都可以应用而不会影响解决方案，从而通过移除潜在的有效步数单元格来使其更好。当过程结束时，一个附加的变异循环计算非 Wall 单元格转换为 Wall 或 FakeWall 单元格的最终转换。新创建的解决方案将具有与父代相同的 Wall、相同的起点/终点，但拥有两者的虚拟墙，再加上一些变异（如果发生的话）。

逻辑很简单：决定一个更经济的解决方案的东西是移动的自由度。自由单元格越多，解决方案的域就越大，从而——相应地——朝着终点的步数也越多。通过上述方式，我们对基本路径应用了渐进式限制，该路径将由过去几代代表并帮助实现这一目标的限制器的总和构成。

通过让算法运行，交替进行代际，在几百个时期内，我们将获得最优解决方案，或从起点到终点没有“犹豫”的解决方案。同时，通过优先选择高性能解决方案而逐渐淘汰差的解决方案，将导致一个可以接受的解决方案种群。

在上例中，可以看到在溶液生成大约 14000 代后，结果非常接近最优解：还有改进的空间，通过继续进行各个时期，有可能取得更好的结果，尽管由于重组近乎理想的解决方案（它们几乎只能依赖变异来进一步改进）而速度较慢。最后，请注意——在给定潜在解决方案数量的情况下——算法选择的路径将受到实际计算的影响：例如，如果变异抑制了某个特定路径，算法将专注于剩余的解决方案。因此，我们将无法获得最终的总体最佳解决方案，而是根据当前上下文和我们可用的代理的最佳解决方案，在概念上模仿生物界发生的事情。

源代码

二维迷宫解决和路径优化的遗传算法

演示

此处提供了一个关于程序会话的示例视频：http://youtu.be/4cqsjThCrRA

参考文献

其他语言

本文的意大利语版本：http://social.technet.microsoft.com/wiki/contents/articles/29756.vb-net-algoritmi-genetici-nella-risoluzione-di-labirinti-bidimensionali-it-it.aspx

历史

2015-02-08: CodeProject 首次发布