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

• 下载源文件 - 3.1 MB

摘要

本文档描述了一种禁忌搜索算法，该算法嵌入在多目标框架中，能够通过优化多个目标来解决分区问题。紧凑性，即赋予对象集（分区问题中的地域单元）的簇，代表了要优化的一个目标；另一个目标是同质性，即在问题中每个对象都具有并被选作算法输入的几个变量的分布平衡，这两个目标都应最小化。

一、引言

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

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

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

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

二、预备知识和定义

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

许多优化问题通常涉及多个目标函数。这类问题被称为多目标优化问题（MOP）。它可以表述如下：

(1)

其中 代表可行空间，即所有有效解的集合，这些解满足问题的每个约束。

一个向量 被称为支配另一个向量 ，记作 当且仅当 。

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

不相似矩阵

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

三、禁忌搜索

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

编码和邻域

一个解被编码为一对（elements，centers），首先是一个长度为 的数组，其中 是BGA的数量， 是簇的数量， 表示对象（在我们的例子中是区域） 位于簇 。另一个长度为 的数组 centers 包含所有中心。给定解 的邻域，记作 ，通过交换所有元素对 获得，其中 是任意中心， 是任意元素，因此 作为解意味着 。

自适应记忆

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

我们的算法在多样化阶段使用频率记忆来偏好作为中心频率最低的对象（区域）。

解决最优分区问题

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

(2)

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

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

(3)

其中  表示该组中变量值正确的元素数量。   和  表示理想值。

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

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

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

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

PSET

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

停止规则

停止规则，顾名思义，定义了算法何时停止的时刻或迭代。在我们的案例中，我们设置了一个固定的迭代次数，如果达到该迭代次数，算法将停止。然而，还有另一个停止算法的条件，即在固定的迭代次数内，新的非支配解决方案也停止出现。

算法

这是TS算法的骨架

1. 随机生成初始解。
2. 生成当前解的邻域。
3. 如果存在改进当前解的解，则选择它作为新的当前解。如果不是，则进入多样化阶段。
4. 将新解提交给PSET进行验证。
5. 重复步骤3直到达到停止规则。

四、结果

为了测试该算法，使用了实际世界问题。具体如下：托卢卡谷大都会区的BGAs将被聚类成五个同质组，这些组只包含其变量值在以下所示范围内的元素。

Male Population under 6 years (X001). 
Male population between 6 and 11 years (X003). 
Male population between 15 and 17 (X007). 

同质性将在所有三个变量中获得。

禁忌搜索用这个例子运行了几次迭代，得到了以下结果

表1

托卢卡谷地域设计

 

托卢卡谷的同质性和紧凑性结果，迭代次数=15，区域=5。

从表1可以看出，结果相当令人满意。

五、结论

多目标问题在许多实际问题中都会出现；本文重点讨论了其中一个问题，即分区问题。禁忌搜索被证明是解决该问题的有效方法，并在实验中给出了一些有趣的结果。

在当今可能找到的各种元启发式算法中，我们选择了禁忌搜索，因为它作为一种智能搜索方法的非凡条件。我们希望未来在分区问题上的工作能够产生新的方法、思想以及与我们的TS进行比较。

参考文献

• [1] Bernábe Loranca B.、Coello Coello A.C.、Osorio Lama M.，“一种用于优化最优分区中紧凑性和同质性的多目标启发式方法”。
• [2] Beausoleil P. Ricardo，“使用禁忌搜索的多目标聚类”，控制论、数学和物理研究所。
• [3] Talbi El-Ghazali，元启发式算法：从设计到实现。新泽西：Wiley and Sons，2009，第2章。