优化装置、优化方法和优化程序

摘要

本发明公开了优化装置、优化方法和优化程序。装置包括存储器和一个或更多个处理器，所述一个或更多个处理器耦接至存储器并且被配置成执行以下操作：针对多个单目标函数中的每一个单目标函数执行基于退火的解搜索，以便获得通过解搜索产生的第一解，多个单目标函数各自通过在利用多个加权模式中的对应一个加权模式对多个目标函数进行加权之后将多个目标函数相加在一起而生成；以及通过从包括第一解的至少一部分的初始状态执行多点搜索来获得帕累托解或其近似解，执行多点搜索以使得从存在于多点搜索的迭代的任一给定迭代中的多个第二解中选择至少包括目标函数的非支配解的解，并且然后保留所选择的解以用于迭代中的下一迭代。

说明书

技术领域

本文中的公开内容涉及优化装置、优化方法和优化程序。

背景技术

在用户遇到的现实世界优化问题中，并非仅基于特定用户需求(即，特定评估度量)来确定最优解。通常有必要基于多个评估度量之间的折衷来确定针对用户的最佳解。例如，当要执行某个任务时，不可能以最优方式同时满足缩短工作时间的需求以及降低工作成本的需求两者。所期望的是获得满足竞争性需求的解。多目标优化问题被定义为在给定的约束下使用公式表示相应需求的多个目标函数最小化的问题。

多目标优化问题不具有使所有目标函数最小化的解。不是将一个最优解作为结果呈现给用户，而是将多个解作为结果呈现给用户，由此多个目标函数的值变小以提供整体满意度。用户通过考虑所有相关因素来确定满足多个需求的程度，从而从多个呈现的解中选择针对他/她自己的最佳解。

作为结果呈现给用户的多个解优选地是针对多个需求的具有无偏分布的多样化的解的集合。即，优选地是针对多个需求中的每一个——即多个目标函数中的每一个——获得针对至少一个目标函数具有满意值的一个或更多个解。此外，这样的多个解优选地以有效的方式在短时间内生成。

因此，可能期望提供可以有效地生成针对多目标优化问题的多样化的解的集合的机制。

[相关技术文献]

[专利文献]

[专利文献1]日本公开特许公报第2002-302257号

[专利文献2]日本公开特许公报第H11-143938号

发明内容

根据实施方式的方面，一种优化装置包括存储器和一个或更多个处理器，所述一个或更多个处理器耦接至存储器并且被配置成执行以下操作：针对多个单目标函数中的每一个单目标函数执行基于退火的解搜索，以便获得通过解搜索产生的第一解，多个单目标函数各自通过经由下述方式生成单目标函数的处理来生成：在利用多个加权模式中的对应一个加权模式对多个目标函数进行加权之后，将多个目标函数相加在一起；以及通过从包括第一解的至少一部分的初始状态执行多点搜索来获得帕累托解或其近似解，其中，执行多点搜索以使得从存在于多点搜索的迭代的任一给定迭代中的多个第二解中选择至少包括多个目标函数的非支配解的解，并且然后保留所选择的解以用于迭代中的下一迭代。

附图说明

图1是示出优化装置的硬件配置的示例的图；

图2是示出优化装置的功能配置的示例的图；

图3是示出优化方法的过程的示例的流程图；

图4是示意性地示出通过执行使多个单目标函数最小化的优化处理而获得的解的图；

图5是示出模拟退火中的温度变化模式的示例的图；

图6是示出模拟退火中的温度变化模式的另一示例的图；

图7是示出模拟退火中的温度变化模式的又一示例的图；

图8是示意性地示出初始解的分布的图；

图9是示意性地示出通过多点搜索获得的解的分布的变化的图；

图10是示出在图3中所示的步骤S10和S11中执行的处理的细节的流程图；

图11是示意性地示出如何通过保留具有高帕累托秩(pareto rank)的解以用于下一代来逐步优化解的图；

图12是示意性地示出针对多点搜索的终止条件的示例的图；以及

图13是示意性地示出针对多点搜索的终止条件的另一示例的图。

具体实施方式

在下面，将参照附图描述本发明的实施方式。

图1是示出优化装置的硬件配置的示例的图。图1所示的优化装置包括CPU 11、显示单元12、输入单元13、ROM 14、RAM 15、HDD 16、网络接口17、可移除存储介质驱动器18和元启发式计算单元19。

输入单元13提供用户接口，并且接收用于操作优化装置的各种命令和响应于数据请求等的用户响应。显示单元12显示由优化装置进行的处理的结果，并且还显示使得用户可以与优化装置进行通信的各种数据。网络接口17用于与外围设备进行通信以及与远程位置进行通信。

图1所示的优化装置是计算机，并且优化方法作为可由优化装置执行的计算机程序被提供。该计算机程序存储在存储器介质M中，所述存储器介质M可安装至可移除存储介质驱动器18。计算机程序通过可移除存储介质驱动器18从存储器介质M加载至RAM 15或加载至HDD 16。可替选地，计算机程序可以存储在存储器介质(未示出)中并且通过网络接口17从存储器介质加载至RAM 15或加载至HDD 16，所述存储器介质设置在外围装置中或远程位置处。

当从输入单元13接收到用于程序执行的用户指令时，CPU 11将程序从存储器介质M、外围装置、远程存储器介质加载至RAM 15或HDD 16。CPU 11通过使用RAM 15的可用存储器空间作为工作区域来执行加载至RAM 15的程序，并且当出现这样的需要时，在与用户进行通信的同时继续处理。ROM 14存储用于控制CPU 11等的基本操作的控制程序。通过执行如上所述的计算机程序，优化装置执行获得多目标优化问题的多个解的功能。

元启发式计算单元19是专门设计用于执行元启发式算法的专用硬件。元启发式计算单元19可以包括例如通过针对伊辛(Ising)问题等进行退火来执行解搜索的伊辛机。元启发式计算单元19还可以包括用于执行多点搜索方法例如遗传算法的专用硬件。元启发式计算单元19可以包括用于执行退火的退火硬件例如伊辛机以及用于执行多点搜索方法的多点搜索硬件两者，或者可以仅包括其中之一。在可替选配置中，可以不设置实现为专用硬件的元启发式计算单元19。在这样的情况下，作为通用计算机的处理器的CPU 11用作执行元启发式算法的元启发式计算单元。

图2是示出优化装置的功能配置的示例的图；图2所示的优化装置包括数据读取单元20、退火计算单元21、多点搜索计算单元22和数据输出单元23。退火计算单元21包括加权模式生成单元30、单目标函数生成单元31、伊辛机执行单元32以及温度设置单元33。多点搜索计算单元22包括初始解设置单元40、较高秩提取单元41、帕累托秩计算单元42、多点搜索单元43以及终止确定单元44。

数据读取单元20和数据输出单元23可以由图1所示的CPU 11来实现。标注为退火计算单元21和多点搜索计算单元22的功能单元可以由CPU 11或元启发式计算单元19来实现。

可以注意到，作为框示出的功能块之间的边界指示功能边界，并且不一定对应于程序模块之间的边界或控制逻辑方面的分隔。一个功能块和另一功能块可以组合成用作一个块的一个功能块。一个功能块可以被划分成协同操作的多个功能块。

数据读取单元20经由输入单元13、网络接口17或可移动存储介质驱动器18从外部源读取定义用公式表示的多目标优化问题的数据。当求解多目标优化问题时，从外部源读取的数据或在从外部源读取之后存储在HDD 16中的数据由数据读取单元20加载至RAM 15。定义多目标优化问题的数据可以包括定义相应目标函数的QUBO(二次无约束二进制优化)格式的表达式、定义约束的QUBO格式的表达式等。

用公式表示问题的变量可以例如是以下列向量。

x＝(x

此处，T表示转置。x

E＝x

此处，A是对应于第i个目标函数f

约束可以由关于x的等式来定义。具体地，可以针对关于x

退火计算单元21通过针对多目标优化问题进行退火(例如，模拟退火或量子退火)来执行优化处理。出于说明由退火计算单元21执行的处理的目的，下面的实施方式的描述使用通过模拟退火执行优化处理的示例。

在执行优化处理时，退火计算单元21针对通过将利用参数加权后的多个目标函数相加在一起而获得的单个函数(single function)改变加权模式，从而生成具有不同加权模式的多个单个函数。单个函数是包括多个目标函数的复合函数。退火计算单元21执行基于退火的优化处理，以针对以上述方式生成的多个单个函数中的每一个单个函数获得一个最优解，并且还获得在到达每个最优解的途中存在的多个中间解。在本申请中，退火计算单元21获得的最优解不是严格真正的最优解，而是通过退火找到的最佳解。

单个函数可以表示如下。

∑w

此处，求和符号∑计算i从1到N的范围内的和。此外，w

使用强调多个目标函数f

然而，通过如上所述的退火获得的最优解是重点放在一个或更多个特定目标函数上的最优解，并且因此可能不够多样化。提高多样化可能需要针对大量不同加权模式获得最优解。然而，正确设置加权因子的方法是难以设计的。此外，当针对在数量上对应于目标函数的组合数量的大量加权模式执行退火时，难以实现有效的处理。因此，图2所示的优化装置被配置成使得通过基于在到达通过退火获得的最优解的途中存在的多个中间解使用多点搜索方法来执行解搜索。

多点搜索计算单元22从包括多个中间解的至少一部分的初始状态执行多点搜索，并且从多点搜索迭代的某个阶段中存在的多个解中选择至少包括多个目标函数的非支配解的解，接着留下所选择的解以保留用于下一阶段。利用这种布置，多点搜索计算单元22获得多个目标函数的帕累托解或其近似解。此处使用的多点搜索方法指的是通过重复执行下述处理来得到目标解的方法：生成多个解，并且然后优先从中选择优选解，接着通过使用所选择的解来生成下一个解。多点搜索方法的示例包括遗传算法、分散搜索方法和蚁群方法。出于说明由多点搜索计算单元22执行的处理的目的，以下实施方式的描述使用遗传算法作为示例。

在多目标优化问题中，非支配解和帕累托解由解之间的支配关系定义。在可行区域(即，满足约束的区域)中，当针对所有目标函数x'等于或优于x(即具有较小的目标函数值)并且针对至少一个目标函数x'优于x时，根据定义，x'优于x(即x'支配x)。非支配解是指在感兴趣的解的集合中没有优于其的解的解。用数学术语来说，非支配解是不存在满足下述的支配解x'的解x*。

帕累托解被定义为存在于可行域中的所有解的集合中的非支配解。换句话说，帕累托解是多目标优化问题中的多个最佳解，并且非支配解是特定解集合中的多个最佳解。由非支配解的集合形成的平面称为非支配前沿(non-dominated front)。由帕累托解的集合形成的平面称为帕累托前沿。

多点搜索计算单元22使用在到达由退火计算单元21确定的最优解的途中的多个中间解作为初始状态，从而例如通过执行遗传算法来生成下一代解。多点搜索计算单元22重复执行下述处理：在下一代解当中优先选择多个非支配解(即，优选解)，以及通过利用所选择的解来生成用于下一后续代的多个解。利用这种布置，从包括分布在每个最优解周围的相对有利的中间解的开始点执行多点搜索，从而在对特定目标函数没有任何关注的情况下均匀地生成解。因此，多个目标函数的非支配解前沿逐渐接近帕累托前沿。由多点搜索计算单元22以上述方式获得的帕累托解或其近似解以及由退火计算单元21获得的最优解被输出作为最终解。这种布置使得能够获得在多个需求上具有无偏分布的多样化的解的集合，即下述解：针对所述解中的每一个解，至少一个目标函数具有满意值，使得多个目标函数中的任一给定目标函数在所述解中的至少一个解中具有满意值。

如上所述，由退火计算单元21生成的最优解可以不用于由多点搜索计算单元22获得下一代解。这些最优解用于确定多点搜索是否在多点搜索计算单元22中终止。即，多点搜索计算单元22基于由多点搜索获得的解与最优解的比较，对多点搜索进行终止条件检查。利用这种布置，多点搜索计算单元22可以确定非支配解前沿是否已经充分接近最优解，即，非支配解前沿是否已经充分接近帕累托前沿。基于这样的确定，可以终止获得解的操作。这种布置使得能够获得下述解：针对所述解中的每个解，至少一个目标函数具有足够接近最优解的满意值，使得多个目标函数中的任一给定目标函数在所述解中的至少一个解中具有这样的满意值。

图3是示出优化方法的过程的示例的流程图。图2所示的优化装置执行图3所示的优化方法。

可以注意到，在图3和随后的流程图中，执行流程图中示出的步骤的顺序仅仅是示例。所公开的技术的范围不限于所公开的顺序。例如，可以说明在执行B步骤之前执行A步骤的描述。尽管有这样的描述，但是在A步骤之前执行B步骤在物理上和逻辑上可以是可能的，同时在B步骤之前执行A步骤是可能的。在这样的情况下，不管首先执行哪个步骤，影响流程图的结果的所有结果都可以是相同的。接下来，出于所公开技术的目的，显然可以在执行A步骤之前执行B步骤。尽管说明了在B步骤之前执行A步骤，但是这样的描述并不旨在将如上所述的明显情况置于所公开技术的范围之外。这样的明显的情况不可避免地落入本公开内容所意图的技术的范围内。

在步骤S1中，设置各种初始值。例如，退火计算单元21将加权模式列表WeightPatternList设置为空阵列以进行初始化，并且准备空集合以用作最优解集合S

在步骤S2中，退火计算单元21的加权模式生成单元30生成多个加权模式，并且将所生成的加权模式存储在WeightPatternList中。加权模式生成单元30可以例如从多个目标函数中选择一个目标函数，并且生成下述加权模式：其中，该目标函数的权重被设置为非零值(例如，1)并且其他目标函数的权重被设置为零。加权模式生成单元30可以针对所有多个N个目标函数执行该处理以生成N个加权模式。可替选地，加权模式生成单元30可以例如从多个目标函数中选择两个目标函数，并且生成下述加权模式：其中，这两个目标函数的权重被设置为非零值(例如，1)并且其他目标函数的权重被设置为零。加权模式生成单元30可以针对可从多个目标函数中选择的所有对执行该处理，以生成N(N/1)/2个加权模式。

在步骤S3中，退火计算单元21的单目标函数生成单元31确定WeightPatternList是否为空。当发现列表不为空时，即，当存在要对其执行退火的加权模式时，处理进行到步骤S4。

在步骤S4中，单目标函数生成单元31检索存储在WeightPatternList的顶部的加权模式。作为结果，从WeightPatternList中移除该加权模式。单目标函数生成单元31将检索出的加权模式存储在WeightPattern中。

在步骤S5中，单目标函数生成单元31根据存储在WeightPattern中的加权模式创建单目标函数，接着将创建的单目标函数表示为F(x)。作为示例，加权模式可以是下述模式：在该模式中，在从多个目标函数中选择一个目标函数f

在步骤S6中，退火计算单元21的伊辛机执行单元32在改变温度设置的情况下，通过针对单目标函数F(x)进行模拟退火来执行优化处理。伊辛机执行单元32将通过优化处理获得的最优解添加至最优解集合S

在模拟退火中，先前描述的可变列向量x可以用于表示单个状态。对当前状态的目标函数值E进行计算，并且然后，对通过根据当前状态进行稍微改变(例如，1位反转)而获得的下一状态的目标函数值E'进行计算，接着计算这两个状态之间的差ΔE(＝E'-E)。在使用玻尔兹曼分布来表示x的概率分布并且使用Metropolis方法的情况下，例如，发生到下一状态的转变的概率P可以由下面的公式限定。

P＝min[1, exp(-βΔE)] (6)

此处，β是热力学贝塔(即，绝对温度的倒数)。函数min[1,x]取值1或值x，以较小者为准。根据以上公式，在ΔE≦0的情况下，以概率“1”发生到下一状态的转变，以及在0<ΔE的情况下，以概率exp(-βΔE)发生到下一状态的转变。可以注意到，为了如前所述改变温度设置，可以改变热力学贝塔β。

在执行状态转变的情况下以足够低的速率降低温度在理论上使得状态能够收敛于具有最小目标函数值的最优解。Metropolis方法是非限制性示例，并且可替选地使用其他转变控制算法例如吉布斯采样(Gibbs sampling)。

图4是示意性地示出通过执行使多个单目标函数最小化的优化处理而获得的解的图。在图4中，第一目标函数f

当单目标函数是f

通过从多个目标函数中选择一个目标函数并且仅将该目标函数的权重设置为非零值，可以获得仅关注该目标函数的最优解。针对所有目标函数中的每个目标函数执行该处理使得能够获得针对这些目标函数中的相应一个目标函数的最优解，并且使得能够获得使得仅关注相应的目标函数的最优解。因此，这种布置有助于容易地生成最优解，每个最优解对应于多目标优化问题中期望的多样化的解的集合当中的相应目标函数。

通过从多个目标函数中选择两个目标函数作为一对，并且仅将这两个目标函数的权重设置为非零值，可以获得位于两个最优解之间的中间位置处的最优解，两个最优解各自是通过分别关注这两个目标函数中的相应一个目标函数而获得的。针对可从多个目标函数中选择的每一对执行该处理使得能够针对可从多个目标函数中选择的对中的相应一对获得最优解，并且使得最优解能够位于与构成相应对的两个目标函数相对应的两个位置之间的中间位置处。因此，这种布置有助于容易地生成最优解(例如，B2)，最优解各自位于多目标优化问题中期望的多样化的解的集合当中与两个目标函数相对应的两个位置之间。

平滑地连接解B1、B2和B3的曲线PF是近似匹配帕累托前沿的线。上述布置有助于生成位于帕累托前沿上或帕累托前沿附近的最优解。然而，优选地进一步获得位于解B1与B2之间以及解B2与B3之间的帕累托前沿上或帕累托前沿附近的解，以便增加解的多样性。在图3所示的优化处理中，在后续步骤中基于中间解来执行多点搜索方法，从而有助于同时生成多样化的解的集合。

当通过模拟退火执行优化处理以获得中间解时，如前所述适当地改变温度设置。具体地，退火计算单元21的温度设置单元33可以设置温度变化模式，使得伊辛机执行单元32可以根据该温度变化模式执行模拟退火。在如上所述改变模拟退火中的温度设置的的情况下获得多个中间解使得能够获得针对各种不同的温度条件的中间解，从而保证中间解的多样性。

图5是示出模拟退火中的温度变化模式的示例的图。在图5中，横轴表示模拟退火中的迭代次数，并且纵轴表示温度设置。在图5所示的温度变化模式的示例中，温度从最大温度连续地降低，并且在达到预定的最小温度时返回到最大温度，接着一次又一次地从最大温度连续地降低。在使用该温度变化模式的情况下，可以在多次出现的最低温度处获得的多个解当中选择具有最低单目标函数值的解作为最优解。用于获得最优解的定时不限于这种布置。例如，在最后的最低温度处获得的解可以用作最优解。每次执行预定次数的迭代(例如，1000次迭代)时获得的解可以用作中间解。优选地将在相对较低温度处获得的解用作中间解，但这不是限制性示例。

图6是示出模拟退火中的温度变化模式的另一示例的图。在图6所示的温度变化模式的该示例中，温度以步进方式从最高温度降低。在使用该温度变化模式的情况下，可以选择在最后的迭代处获得的解作为最优解。每次执行预定次数的迭代(例如，1000次迭代)时获得的解可以用作中间解。

图7是示出模拟退火中的温度变化模式的又一示例的图。在图7所示的温度变化模式的该示例中，设置多个伊辛机M1至M4，它们中的每一个执行模拟退火，并且在它们相应的温度被驱动。每个伊辛机以固定温度操作，但是通过多个伊辛机实现在不同温度条件的模拟退火，因此实现与温度变化等同的条件。可以注意到，例如，每次执行预定次数的迭代时，温度设置可以在伊辛机M1至M4之间切换，从而使每个伊辛机以步进方式经历温度变化。

在使用图7所示的温度变化模式的情况下，例如，可以针对伊辛机中的每一个获得在整个迭代处理中具有最小单目标函数值的解，并且可以选择所获得的在伊辛机当中具有最小单目标函数值的解中的一个解作为最优解。每次执行预定次数的迭代(例如，1000次迭代)时在每个伊辛机中获得的解可以用作中间解。

再次参照图3，在步骤S6之后，过程返回到步骤S3，从步骤S3重复后续处理。当在步骤S3中发现WeightPatternList是空的时，即针对所有加权模式完成优化处理时，处理进行到步骤S7。

在步骤S7中，多点搜索计算单元22的初始解设置单元40生成初始解集合S

秩1：解集合中的所有非支配解；以及

秩k：通过从解集合中移除秩1至k-1的解而获得的集合中的非支配解。

此外，较高秩提取单元41从中间解当中提取具有相对较高帕累托秩的中间解。初始解设置单元40将由较高秩提取单元41提取的中间解存储在初始解集合S

图8是示意性示出初始解的分布的图。在图8中，与图4中一样，第一目标函数f

图9是示意性示出通过多点搜索获得的解的分布的变化的图。针对图8所示的解61执行多点搜索。在这样做时，从在迭代的一个阶段处出现的多个解中选择至少包括非支配解的解，并且一次又一次地留下所选择的非支配解以保留用于下一阶段。作为结果，获得如图9所示的解61。示出了从最优解B1、B2和B3中的每一个延伸的两个箭头，并且两个箭头分别向右延伸和向上延伸。最优解B1、B2和B3中的每一个解支配位于这两个箭头之间的区域中的解(参见表达式(4)和(5))。解61中的一些解是非支配解，这些非支配解不插入在这些箭头之间，并且还位于最优解B1与最优解B2之间或最优解B2与最优解B3之间的帕累托前沿PF附近(见图4)。在下文中，将给出获得这样的多样化的、满意的解的集合的遗传算法的描述。

在步骤S8中，多点搜索计算单元22的多点搜索单元43将属于初始解集合S

在步骤S9中，多点搜索单元43检查计数值LoopCounter是否小于LoopNum。在检查结果指示“是”的情况下，过程进行到步骤S10。

在步骤S10中，多点搜索单元43通过基于存储在父集合S

图10是示出在图3所示的步骤S10和S11中执行的处理的细节的流程图。在图10中，步骤S21至S25对应于步骤S10中的处理，并且步骤S26至S31对应于步骤S11中的处理。

在步骤S21中，多点搜索单元43准备空集合作为临时解集合S

在步骤S23中，多点搜索单元43从父集合S

在步骤S24中，多点搜索单元43从父集合S

在步骤S25中，多点搜索单元43从父集合S

在步骤S26中，多点搜索单元43准备空集合作为子集合S

在步骤S28中，多点搜索单元43通过使用“target”作为初始解来执行近似解方法以求解约束满足问题，从而获得位于“target”附近的约束满足解或其近似解。多点搜索单元43将所获得的解指定为“result”。当“target”本身满足所有约束时，足以在没有任何改变的情况下使用“target”作为“result”。近似解算法不限于任何特定的算法，并且可以是例如贪婪方法、局部搜索方法、禁忌搜索或退火。

在步骤S29中，多点搜索单元43检查“result”是否满足所有约束。当发现不满足所有约束时，过程返回到步骤S27以重复随后的步骤。当发现满足所有约束时，过程进行到步骤S30。

在步骤S30中，多点搜索单元43将“result”添加至子集合S

当如上所述完成图3中的步骤S10和步骤S11的处理时，在图3的步骤S12中，帕累托秩计算单元42针对存储在子集合S

图11是示意性地示出如何通过保留具有高帕累托秩的解以用于下一代来逐步优化解的图。在图11中，与图4中一样，第一目标函数f

返回到图3，在步骤S13中，终止确定单元44基于父集合S

图12是示意性地示出用于多点搜索的终止条件的示例的图。在图12中，与图4中一样，第一目标函数f

通过基于属于该父集合S

如图12所示，多点搜索计算单元22的终止确定单元44可以决定当包括通过多点搜索获得的解和最优解的解集合中的非支配解集合在迭代中已经停止改变时终止多点搜索。这样的终止条件检查有助于当具有足够满意的值的、甚至不受最优解支配的解已经充分收敛时多点搜索的及时终止。

图13是示意性示出用于多点搜索的终止条件的另一示例的图。图13所示的方法与图12所示的相同。如图13的上图所示，在属于子集合S

通过基于属于该父集合S

如图13所示，多点搜索计算单元22的终止确定单元44可以决定当包括由多点搜索获得的解和最优解的解集合中的非支配解的数量在迭代中已经停止改变时终止多点搜索。这样的终止条件检查有助于在已经产生了足够数量的具有足够满意的值并且甚至不受最优解支配的解时多点搜索的及时终止。

返回到图3，在步骤S14中，多点搜索单元43基于终止条件检查的结果来确定是否终止该过程，该终止条件检查由终止确定单元44进行并且指示解是否已经收敛到帕累托解(或其近似解)。当发现还没有发生到帕累托解(或其近似解)的收敛时，该过程返回到步骤S9以重复后续处理。在发现已经发生到帕累托解(或其近似解)的收敛时，过程进行到步骤S15。此外，当在步骤S9中发现计数值LoopCounter不小于LoopNum时，过程进行到步骤S15。

在步骤S15中，数据输出单元23输出父集合S

此外，虽然已经参考实施方式描述了本发明，但是本发明不限于这些实施方式，并且在不脱离权利要求所限定的范围的情况下可以进行各种变化和修改。

例如，图3所示的优化方法被配置成使得在步骤S10中执行遗传算子例如交叉和变异，并且在步骤S11中找到满足约束的解，但是这样的方法不旨在是限制性的。例如，可以修改步骤S10中遗传算子例如交叉和变异，使得不违反约束。可替选地，在步骤S10中可以执行大量次数的遗传算子，使得仅满足约束的那些解被保留作为解。在这种情况下，在步骤S11中获得约束满足解的处理是不必要的。

根据至少一个实施方式，可以针对多目标优化问题有效地生成多样化的解的集合。