多目标禁忌搜索用于聚类和分区问题

摘要：本文描述了一种嵌入多目标框架中的禁忌搜索算法，该算法通过优化多个目标来寻找分区问题的解决方案。紧凑性（指分配给一组对象的集群（分区问题中的区域单元）的含义）是待优化的目标之一，另一个目标是同质性，即每个对象（在问题中具有并被选为算法输入的变量）的分布的平衡。这两个目标都将被最小化。

一、引言

分区是城市研究领域的一项技术，首次出现在19世纪，用于将住宅区与工业区分开。这项技术在城市化中最受欢迎，其主要思想是根据某些标准生成同质区域的划分。在我们的例子中，每个变量都匹配一个标准，每个基本地理统计区域都拥有一系列值，每个值代表该变量在问题中的值。这些变量可以是人口统计学上的，例如20岁以上的人。

我们将使用“基本地理统计区域 (BGA)”来指代要聚类的基本或原始区域。任何 BGA 都由一对 (position, variables_values) 组成，其中 position 标记区域在空间中的位置（通常是两个坐标），而 variables_values 表示问题中每个变量的值列表。

禁忌搜索是由 Fred Glover 创建的一种元启发式算法，它继承了局部搜索一种流行的优化方法。它通常应用于组合优化问题，如 TSP（旅行商问题）或 QAP（二次分配问题）。由于分区问题和 TSP 的 NP 完全性质，必须使用元启发式算法来解决。事实上，大多数时候我们找不到最优解，而是最优解的近似值，有时如果我们足够幸运，这些近似值可能等于某个最优解。

我们的禁忌搜索嵌入在多目标框架中；这意味着同时优化多个目标函数。由于这是一个多目标算法，其主要目标是找到非支配解。到目前为止我们看到过的任何未知定义将在下一节中介绍。

二、初步和定义

在本节中，我们将定义我们认为与理解本文内容相关且必要的一些理论方面。

许多优化问题通常涉及多个目标函数，这些问题称为**多目标优化问题** (MOP)。它可以表述如下：

其中 表示可行空间，即所有有效解的集合，即满足问题所有约束的解。

如果且仅当 ，则称向量 支配另一个向量 ，表示为 。

拥有多个目标会带来一个重要问题。一个目标函数的改进可能导致另一个目标的恶化。因此，很少存在一个解能优化所有目标，所以我们不是寻找那个解，而是寻找一个权衡。**帕累托最优解**代表了这种权衡。如果存在一个可行解 使得 ，并且不存在其他可行解 ，那么称该解是**帕累托最优的**。所有帕累托最优解的集合称为**帕累托集**，其图像称为**帕累托前沿**。本文提出的算法找到了一组帕累托最优解的近似值，形成了一个帕累托前沿。下一节将描述禁忌搜索及其所有组成部分。

不相似度矩阵

在本工作中，我们考虑使用两个不相似度矩阵，一个用于每个区域的坐标，另一个用于每个区域中每个变量的值。

三、禁忌搜索

禁忌搜索 (TS) 是 Glover 提出的一种元启发式算法，它使用自适应记忆和响应式探索。它继承了局部搜索 (LS) 的思想，局部搜索可能是最古老、最简单的元启发式方法。可以说，禁忌搜索只是局部搜索的一些显著改进或升级。它的核心功能与 LS 相同；它从一个给定的初始解（通常是随机生成的）开始，运行直到达到停止规则，并且在每次迭代中，将当前解替换为改进目标函数并且位于当前解邻域中的另一个解。LS 的停止规则是在当前解的任何邻域都无法改进目标函数时达到，这意味着我们找到了一个局部最优解。这是 LS 的主要缺点；它只找到局部最优解，而禁忌搜索不具有这个缺点，因为它包含用于多样化的机制，可以防止它陷入局部最优解。

编码和邻域

解被编码为一对 (elements, centers)，第一个是长度为 的数组，其中 是 BGA 的数量， 是簇的数量，而 表示对象（在本例中为区域） 位于簇 。另一个长度为 的数组 centers 包含所有中心。给定解 的邻域，表示为 ，是通过交换所有对 元素获得的，其中 是任何中心， 是任何元素，因此拥有 形式的解意味着 。

自适应记忆

这可能是禁忌搜索最重要的特性：它通过使用数据结构来记住搜索的演变。**禁忌列表**是这些数据结构之一，用于保存先前交换的对，避免了在一段时间内（因为内存是有限的，列表的长度必须是有限的）循环相同的解决方案的可能性。**强化**一词指的是许多元启发式算法实现的机制，用于优先利用迄今为止找到的最佳解决方案，在这种情况下，更有希望的区域会被更彻底地探索。另一方面，**多样化**指的是对搜索空间的探索，试图访问未探索的解决方案。在 TS 中，这些机制体现在**中期记忆**和长期记忆或频率记忆中。强化由中期记忆管理，存储有史以来找到的最佳解决方案。多样化由频率记忆处理，显示某个元素作为中心被包含在解决方案中的次数。

我们的算法使用频率记忆，在多样化阶段优先考虑频率最低的对象（区域）作为中心。

解决最优分区问题

禁忌搜索嵌入在多目标框架中，因此为了解决这个问题，我们必须考虑几个目标函数。第一个函数最小化**类内**距离，即每个对象到其类别或簇中心的距离。

在此公式中，表示欧几里得距离，表示一个中心，表示属于以 为中心的簇的元素集合。

第二个目标考虑了解决方案的**同质性**。同质性意味着属于同一簇的元素共享某些特征，在这种情况下是某些变量的值。当我们根据同质性标准进行分区时，其思想是为每个变量在每个簇中找到平衡或均衡，因此要优化的实际函数是同质性的平衡。要找到一个组相对于某个变量的**平衡**，我们计算具有该变量期望值的元素数量，并从理想值中减去该数量；当组中的所有元素都具有期望值时，就实现了理想值。所有组平衡的总和代表要最小化的**同质性平衡**。对于我们希望实现同质性的每个变量，都应该将一个同质性平衡函数添加到优化模型中，因此如果我们想实现三个变量的同质性，我们的模型将有四个目标：类内函数和每个变量的一个同质性平衡函数。

 

其中 表示在组 中具有正确值的元素的数量，而 表示理想值。

现在我们已经陈述了优化模型，是时候描述 TS 寻找非支配解并构建帕累托前沿的策略了。

该策略分为三个不同的阶段。

1. 找到区域的聚类（我们只优化类内目标）。
2. 一旦我们有了聚类，就计算其同质性。
3. 我们检查该解决方案是否是非支配的，如果是，我们使用 PSET（我们将很快看到这意味着什么）将其添加，否则我们不做任何事情。

从这些步骤来看，该策略非常简单。我们将类内优化与同质性优化分开，然后验证新解决方案的非支配性。

PSET

PSET（**帕累托集**）是负责构建帕累托集的算法组件。一旦找到一个解决方案，PSET 将验证该解决方案是否“适合”被考虑在解决方案集中。适合意味着它不是重复的（已经在 PSET 中）并且是非支配的。如果该解决方案恰好是非支配的，那么我们可能需要移除 PSET 中一些不再符合帕累托最优条件的旧解决方案，因为它们现在被新解决方案支配。PSET 有一个容差率 （默认为 0）作为参数，该参数允许将实际上被支配但非常接近某个非支配解（其差值小于或等于 ）的解决方案包含在 PSET 中。

停止规则

停止规则，顾名思义，定义了算法应停止的时刻或迭代次数。在我们的例子中，我们固定了迭代次数，如果达到该迭代次数，算法将停止。但是，还有一个停止算法的条件，那就是当连续固定次数的迭代中不再出现新的非支配解时。

算法

这是 TS 算法的骨架

1. 随机生成一个初始解。
2. 生成当前解的邻域。
3. 如果存在改进当前解的解，则将其选为新的当前解。如果不存在，则进入多样化阶段。
4. 获取新解以供 PSET 验证。
5. 重复步骤 3，直到达到停止规则。

四、结果

为了测试该算法，使用了真实世界的问题。其说明如下：将 Toluca Valley 都市区的 BGA 聚类为五个同质组，这些组仅包含变量值在以下范围内内的元素。

• 6岁以下男性人口 (X001)。
• 6至11岁男性人口 (X003)。
• 15至17岁男性人口 (X007)。

将在所有三个变量上实现同质性。

使用此示例运行了多次禁忌搜索迭代，获得了以下结果：

表 1 - Toluca Valley 区域设计 

 

从表 1 可以看出，结果相当令人满意。前面解决方案的帕累托前沿（帕累托集）在下图所示。

五、比较

本次比较是针对一个 VNS（可变邻域搜索）算法进行的，该算法也应用于相同的问题。如以下结果所示，禁忌搜索在许多方面（同质性、紧凑性、解决方案数量等）都优于 VNS。

结论

多目标问题出现在许多现实世界的问题中；本文重点关注其中一个问题，即分区问题。禁忌搜索被证明是一种解决该问题的有效方法，并在实验中取得了有趣的成果。

在当今存在的各种元启发式算法中，我们选择禁忌搜索是因为它作为一种智能搜索方法具有非凡的优势。我们希望未来在分区问题上的工作能够带来新的方法、思想以及与我们 TS 的比较。

参考文献

[1]     Bernábe Loranca B., Coello Coello A.C., Osorio Lama M.，“一种用于最优分区中紧凑性和同质性启发式优化的多目标方法”。

[2]     Beausoleil P. Ricardo，“使用禁忌搜索的多目标聚类”，控制论、数学和物理研究所。

[3]     Talbi El-Ghazali，Metaheuristics: from design to implementation。新泽西州：Wiley and Sons，2009 年，第 2 章。