英语原文共 5 页，支付完成后下载完整资料

基于满意度函数的交互式目标规划模型

Aouni Belaid, Hassaine Amal, Martel Jean-Marc

摘要：交互式目标规划模型的现有公式没有明确地集成决策者的偏好。此外，这些公式需要来自DM的信息太多。本文的目的是提出一个基于满意函数概念的IGP模型，通过学习过程来阐明DM的偏好。在任何时候的决策过程中，DM都可以修改决策情境的参数，包括满意度函数。这个框架允许DM朝着最佳折中的解决方案发展。

关键词:交互式目标规划；满意度函数；决策者的偏好

1. 介绍

目标规划(GP)模型是一种著名的和最常用的多目标规划(MOP)模型[1]。这个模型是基于一种令人满意的哲学，它帮助DM同时满足几个目标，从而发展为最令人满意的解决方案[2]、[3]、[4]。这些目标通常是相互冲突的，并通过不同的单元进行度量。GP的标准版本最初由[5]和[6]开发。从那时起，[7]取得了令人印象深刻的发展，为他撰写了大量的文章、应用程序甚至会议。在实践中，GP和他的不同变体在过去的几十年中被证明是各种决策环境下的一个有用工具。GP公式将与不同目标相关的不需要的偏差变量最小化，如下所示:在这样的条件下, 其中 是目标的期望水平, 是目标与解的实现水平, 变量 分别表示与期望水平的正偏差和负偏差 表示可行的解决方案集。

尽管标准GP广受欢迎，但它也存在一些缺陷。这些缺点之一在于其聚合过程，其意味着通过不同的和不可通知的单元测量的偏差的增加。这可能会导致隐含和不理想的加权。DM在决策过程中的参与受到一定的限制，因为他主要被要求设定目标和相关目标。

在相关文献中已经提出了基于交互过程的目标规划（GP）模型的一些表述。因此，它们允许克服一些通常针对该模型的批评。但是，他们中的大多数都没有明确考虑DM的偏好。此外，对于DM来说，有些方法似乎很难使用，因为它需要太多的信息，或者可能会造成混淆的信息。

在下一节中，我们将简要回顾主要的交互式GP（IGP）模型。第三部分介绍了由[8]开发的具有满意度函数（GPF）的GP。在第四部分中，我们提出了GPSF的交互式版本，它允许DM更好地识别决策背景并明确地揭示他的偏好。

2. 交互式目标规划模型

在文献中已经提出了几种交互式多目标编程（MOP）方法。这些方法是基于逐步引入决策者(DM)的偏好。通常，DM被要求在每次迭代中提供与他对获得的解决方案的偏好相关的显式或隐式信息。在这个领域，[9]和[10]被认为是开创性的工作，使得其他的互动方法得以发展。随后又发展了[11]、[12]、[13]、[14]等方法。

交互方法通常是基于以下步骤[15]，[16]，[17]: a）找到解决方案; b）与DM交互以评估所获得的解决方案并使用与其偏好相关的信息来生成新的解决方案; c）重复这两个步骤，直到DM满足给定的解决方案或满足某个停止标准。根据最后一次迭代，向积极参与拟订工作的DM提出最后建议，从而有更大的机会被接受和执行。

此外，应该注意的是，一般而言，在不同时刻并在某种程度上决策辅助模型涉及与DM对话，例如，定义要考虑的目标[17]，[18]。但是，[18]指出，这种对话被视为一种互动方式，必须在获得令人满意的解决方案方面发挥重要作用。换句话说，根据同一作者的说法，DM必须在解决方案的构建中发挥直接作用，在这种情况下，这种作用不再局限于决策环境的定义和制定。

早期的交互式GP (IGP)过程结合了GP的特点和现有的交互式MOP方法。因此，[19]开发的第一个IGP是[10]模型的改编，其中DM决定不同目标成就之间的局部权衡。参考文献[20]将标准GP模型与[9]的STEM方法相结合，从而提出了GPSTEM方法。虽然[19]和[20]的方法是基于开创性的工作，代表了GP模型发展的根本贡献，但它们也呈现了GDF和STEM方法的一些缺点。例如，根据[18]，STEM的主要缺点在于DM不能修改先前在某些标准上做出的妥协。

参考文献[21]开发了GP的交互式版本，其中要求DM评估在每次迭代中获得的一组解决方案，并相应地调整其期望的目标值。这个集合包括一个代表最佳折中解决方案的主解决方案，以及一个对应于决策情况中所考虑的目标数量的给定数量的备选解决方案。参考文献[22]开发了基于DM愿望水平设置和调整的GP (VIG)程序的可视化交互，其主要贡献在于使DM能够使用基于图形的用户友好界面自由探索一组可行的解决方案。一些VIG的应用可以在[23]和[24]，[25]中找到。参考文献[16]开发了两种迭代算法，用于调整由DM建立的相对重要性参数。它们建议需要从DM获得定性信息，而不是定量信息。实际上，大多数最接近的方法使DM能够调整与不同目标相关的目标，它们的相对重要性参数（无论是以权重的形式还是作为词典顺序），或者两者同时进行。而且，它们通常基于一个学习过程，允许在一个方面DM重新考虑他先前排除的解决方案，并且在另一方面，为了在方便时停止交互过程。我们可以在这里提到由[26]开发的交互式Meta-GP。

一般来说，IGP公式或多或少带来了响应，以减轻GP模型的一些限制。然而，这些交互方法大多基于最初开发的GP模型，因此对针对GP的批评提供了部分回应。此外，我们认为由[8]开发的GP满意度函数（GPSF）模型提供了有趣的观点。在下一节中，我们将简要介绍GPSF模型。

3. 具有满意度函数的GP模型

参考文献[8]通过结合满意度函数（GPSF）的概念提出了GP模型的一个公式。这些函数是与DM共同确定的，他们可以根据每个不同的目标指定不同的方式，以及偏差是积极的还是消极的。这些功能可以被认为是反映DM对每个目标的实现和期望水平之间偏差的满意程度的一种度量。满意度函数的一般形式如下:

图1 满意度函数的一般形式

满意度函数在0和1之间变化，并且单调递减。因此，偏差越趋近于0,DM就越被满足，相应的满足函数也就越接近于1。此外，GPSF模型只包含三种类型的阈值，它们反映了DM偏好的强度。这些阈值确保模型部分不具有补偿性，即某个目标的不良表现无法通过其他目标的良好表现得到补偿。阈值的类型如下:

• 无差异阈值（）：对于目标 ，DM完全满足，因为偏差不超过该阈值。

• 零满意度阈值（）：对于目标，如果与解决方案相关联的偏差达到该阈值，则不满足DM，但是他不拒绝它。

• 否决权阈值（）：如果至少有一个偏差大于此阈值，则任何解决方案都不可接受。

GPSF的表述如下：

(1)

满足以下条件：

x

其中 和 分别是与正偏差和负偏差相关的满意度函数。

因此，GPSF模型一方面克服了量表不可通约的问题，因为满意函数表达的是对不同偏差的满意程度，而不是偏差本身。另一方面，它明确地考虑了DM的偏好。此外,[27]和[28]已经开发出两个变量的GPSF来处理DM的决策环境中只有部分,不精确或不确定的信息。最近，[29]提出了一种交互式不精确模型，它通过满意度函数明确地整合了DM的偏好。他们利用Taboo Central Memory-Simulated Annealing算法来求解他们的模型。使用metaheuristics使DM能够处理大规模的决策问题。鉴于决策过程的演化性质和GPSF的吸引力，我们在下一节中提出一种将GPSF模型与交互方法相结合的算法。

4. 交互式GPSF模型

为了说明GPSF模型的交互方法，我们提出了一种基于迭代过程的算法，该算法使计算和交互阶段与DM交替。该算法在于求解与GPSF相关的连续数学程序，使得DM可以调整和修改与该方法所需的不同参数有关的信息。该程序允许DM根据其绩效以及与所考虑的决策背景相关的任何新信息，以连续的方式审查和重新考虑决策。这个迭代过程一直持续到DM对给定的解决方案满意为止，或直到他认为他对他的决策情况有了更多的见解以做出选择。

提出的交互式GPSF（IGPSF）算法包括以下五个步骤：

步骤0：确定与决策背景相关的目标，决策变量和约束系统。

步骤1:与DM共同确定所有目标(，迭代h的参数如下:

• 目标 与不同目标 相关联；

• 相对重要的系数；

• 满意度函数的类型；

• 偏好阈值与所选择的满意度函数有关; 设。

步骤2:制定并求解GPSF模型。

• 设为得到的解。

步骤3：要求DM评估解决方案：

• 如果满意，转到步骤4;
• 否则，设h = h 1并返回步骤1。

步骤4：停止交互过程并根据解决方案详细说明最终建议。

我们算法的不同步骤可以用图2所示的流程图表示。

图2 交互式GPSF（IGPSF）算法的流程图

IGPSF的前两个步骤是与DM交互的步骤。因此，初始阶段（阶段0）在于确定决策变量和所考虑的决策背景的目标。我们假设DM能够提供此类信息。此外，在交互过程中，所有其他条件相同的情况下，此信息被视为已修复。在步骤1中，要求DM提供反映其偏好并且与GPSF参数相关的信息。

IGPSF的计算阶段从步骤2开始。GPSF模型是在前面步骤中指定的参数的基础上建立并求解的。该公式对应于GPSF模型的一般公式（程序1）。下一步是与DM的交互。他被要求基于所实现的满意度（即与解决方案相关的不同目标相关联的满意度函数值）和各种目标的实现程度来评估在每次迭代时获得的解。基于该信息，如果DM对当前解决方案感到满意，则交互过程结束并且详细说明最终建议。否则，DM可以修改先前迭代中提供的信息。应该注意的是，他可以自由地做出他认为相关的任何改变。例如，DM可以通过减少相关无差异阈值的间隔来对某些目标进行更严格的限制。因此,他可以改变先前保留的满意度函数而不必改变目标和相对重要性系数，这在某些情况下对DM来说是很难执行的。随后，对GPSF模型进行增益公式化和求解。然后将新的解决方案提交给DM进行分析。这个交互过程一直持续到DM决定停止为止。事实上，IGPSF算法在以下情况下终止:

• 当DM认为在给定迭代中获得的解是令人满意的。
• 当DM认为他有足够的证据，并且了解了更多关于选择解决方案的决策情况时。
• 当他认为目前的解决办法没有可能改进时。

这里描述的交互过程属于基于学习过程的交互方法。此外，DM决定何时停止交互过程，因此这种方法不是基于数学收敛。我们可以假设当DM在决策环境中有足够的响应元素时，他将停止迭代过程。实际上，要提前确定停止搜索新解决方案的适当时机并不容易。这种选择取决于经验，并且受到与每个背景相关的一些约束作为时间的约束。我们认为，重要的是，分析人员应鼓励DM不要过早地停止交互过程，以便在做出最终决策之前能够分析多个备选方案。

这个程序的优点在于帮助DM以建设性和渐进的方式阐述他的偏好。该正式框架使DM有机会重新考虑先前设定的参数，无论是在决策过程的开始还是在每次迭代时获得的结果。此外，IGPSF不需要DM系统地修改他的目标，就像一些基于参考点原则和调整期望水平的方法那样。如果目标数量过高，这可能是一个缺点。分析人员可以依次观察DM偏好的演变，并了解更多关于它们的信息，以便更好地满足DM的需求。因此，它似乎为有效的合作提供了空间，通过在DM和分析师之间的观点和信息的交换中得到了丰富的信息。这可以导致建立一种积极的决策援助关系，让DM更多地参与决策过程。

最后，考虑将来开发支持IGPSF模型的软件似乎是有用的。它必须是一种用户友好的工具，可以方便地输入数据和清晰地显示结果，同时汇总关键信息并以快速方便的方式显示它们。

5.结论

GPSF模型的交互式版本的开发允许将交互式方法的固有优点与GPSF的优势相结合。一方面，该模型明确地集成了DM的偏好; 它结合了GP模型的令人满意的理念，同时避免了一些缺点，特别是那些与聚合过程相关的缺点。另外，GPSF模型对信息的要求似乎不太苛刻，满足函数的概念对于DM来说相对容易得到。另一方面，交互式方法的特点是灵活性，并在决策过程中为DM提供更多空间。最后，这种方法为DM提供了机会，通过计算和评估的连续阶段，更多地了解决策背景。

参考文献:

[1] C. Romero, Handbook of Critical Issues in Goal Programming, Pergamon Press, Oxford, 1991.

[2] J. P. Ignizio, Linear Programming in Single and Multiple Objective Systems, Englewood Cliffs, NJ: Prentice-Hall, 1982.

[3] B. Aouni, “Le modegrave;le de programmation matheacute;matique avec buts dans un environnement impreacute;cis: sa formulation, sa reacute;solution et une application”, Thegrave;se de doctorat non publieacute;e,

Faculteacute; des Sciences de lrsquo;Administration, Universiteacute; Laval, 1998.

[4] J. Gonzaacute;lez-Pachoacute;n and C. Romero, “Satisficing Logic and Goal Programmi

资料编号：[3117]