基于遗传算法和分解程序的块角结构多目标非线性整数规划问题的交互式模糊满足方法

摘要

我们主要研究具有块角结构的多目标非线性整数规划问题，它通常被视为大规模离散系统优化的数学模型。通过考虑决策者判断的模糊性，引入决策者的模糊目标，并将其解释为对多个模糊目标的总体满意度的最大化。为了得到决策者的满意解，我们发展了一种交互式模糊满意方法。实现了可用于解决问题的块角结构，我们还提出了带有分解程序的遗传算法。算例说明了该方法的可行性和有效性。

1.介绍

遗传算法(GAs) [1，是由霍兰德、他的同事和他在密歇根大学的学生于20世纪70年代发起的，是基于自然选择和自然遗传学机制的随机搜索技术，它们作为解决离散优化问题或其他困难优化问题的优化技术的潜力受到了广泛的关注。尽管遗传算法一开始并不为人所知，但在Goldberg的书[2，遗传算法作为一种优化、适应和学习的方法，最近在许多领域引起了相当大的关注。当我们研究遗传算法在优化问题上的最新应用时，特别是在各种单目标离散优化问题和/或其他硬优化问题上，我们可以看到持续的进展[3.- - - - - -13］．

Sakawa等人提出了双字符串遗传算法(GADS) [14求解多目标多维0-1背包问题的近似最优解。他们还提出了基于参考解决方案更新的双字符串遗传算法(GADSRSU) [15求解既有正系数又有负系数的多目标一般0-1规划问题。此外，他们提出了使用线性规划松弛(GADSLPR)的双字符串遗传算法[16基于参考解更新的线性规划松弛算法(GADSLPRRSU)求解多目标多维整数背包问题[17］．注意到已对特殊类型的非线性整数规划问题提出了一些求解方法[18- - - - - -23，作为一般非线性整数规划问题的近似解方法，Sakawa等[24提出了基于参考解更新的连续松弛双字符串遗传算法(GADSCRRSU)。

然而，一般来说，实际的决策问题以数学规划问题的形式表述，涉及大量的变量和约束条件。在现实世界中，大多数这样的大规模问题通常都有特殊的结构，可以用来解决问题。约束的一个常见的特殊结构是块角结构，并提出了几种具有块角结构的线性和非线性规划问题的分解方法[25］．然而，不幸的是，对于离散变量的大规模问题，似乎很难发展出一种有效的方法来获得精确的最优解。Sakawa等人针对具有块角结构的多维0-1背包问题，利用可用于求解问题的块角结构[9，26]提出了遗传算法与分解过程(GADPs)。Sakawa等人利用三弦表示处理具有块角结构的多维0-1背包问题[9，26给出了遗传算法的分解过程。此外，通过纳入决策者的模糊目标，他们[9提出了一种具有块角结构的多目标多维0-1背包问题的交互式模糊满足方法。

在这种情况下，本文作为大规模多目标离散系统优化的典型数学模型，研究了块角结构的多目标非线性整数规划问题。通过考虑决策者判断的模糊性，引入决策者的模糊目标，并将其解释为对多个模糊目标的总体满意度的最大化。为了得到决策者的满意解，我们发展了一种交互式模糊满意方法。同时，本文还针对具有块角结构的非线性整数规划问题，提出了带有分解程序的遗传算法。

论文组织如下。部分2建立了块角结构的多目标非线性整数规划问题。部分3.开发了一种交互式模糊满足方法来为决策者提供一个满意的解决方案。部分4提出了将GADPCRRSU作为块角结构非线性整数规划问题的近似解。部分5通过算例说明了该方法的可行性和有效性。最后，本节对结论进行了讨论6和引用。

2.问题公式化

考虑块角结构的多目标非线性整数规划问题，公式为

在哪里，,都是维数整数决策变量列向量和．的约束称为耦合约束与维度，而每个约束，作为块约束调用维度。在(2．1)，则假定，，是一般的非线性函数。的正整数，，表示的上界．下式中，为便于记法，(2．1)表示为．

作为实际应用中块角结构非线性整数规划问题的一个例子，Bretthauer等[27]制定了医疗能力规划，资源约束的生产计划，以及行业约束下的投资组合优化。

3.一种交互式模糊满足方法

为了考虑决策者对(中的每个目标函数的判断的模糊性2．1)，如果我们引入模糊的目标，如“应该大大小于或等于某个值，”(2．1)可以重写为 在哪里隶属函数是否用于量化模糊目标的目标函数2．1)．更具体地说，如果决策者觉得应该小于或等于至少和时，一个典型隶属函数的形状如图1．

自(3．1)作为一个模糊多目标优化问题，当多个目标函数相互冲突时，不总是存在同时使所有目标函数最小化的完全最优解。因此，作为普通多目标规划问题Pareto最优性概念的自然扩展，Sakawa等人[28，29]引入了M- pareto最优解的概念，用隶属函数而不是目标函数来定义，其中M为隶属度。

定义3.1 (M-Pareto最优)。一个可行的解决方案对于一个模糊多目标优化问题，当且仅当不存在另一个可行解时，称为M-Pareto最优如，和至少一个．

引入聚合函数为(3．1)，这个问题可以重写为 其中聚合函数代表决策者对整体的满意程度或偏好程度模糊的目标。在传统的模糊方法中，隐含地假设最小算子是决策者模糊偏好的恰当表示。然而，这里应该强调的是，只有当决策者认为最小运算符是合适的时，这种方法才是可取的。换句话说，在一般决策情况下，决策者在结合模糊目标和/或约束时并不总是使用最小运算符。可能是……3．2)是识别一个合适的聚合函数，它能很好地表示决策者的模糊偏好。如果，则(3．2)简化为一个标准的数学规划问题。然而，这种情况很少发生，作为替代，与决策者的交互是必要的，以找到一个满意的解决方案(3．1)．

为了生成M-Pareto最优解的候选解，决策者被要求指定所有成员函数的期望成就级别，称为参考成员级别。参考由决策者提供的成员级别，，对应的M-Pareto最优解为，它在极小极大意义上最接近要求，或在可达到参考隶属度的情况下优于要求，可通过求解以下增广极小极大问题得到: 在哪里是一个足够小的正实数。

我们现在可以构造一个交互式算法，以便从M-Pareto最优解集中推导出决策者的满意解。交互式模糊满足法的过程总结如下。

3．1.一种交互式模糊满足方法

步骤1。通过求解以下问题，计算给定约束条件下各目标函数的个体最小值和最大值:

步骤2。决策者通过考虑每个目标函数的个体最小值和最大值，主观地指定隶属函数，量化目标函数的模糊目标。

步骤3。决策者设置初始参考成员级别，．

步骤4。对于当前的参考成员级别，解决增广极小极大问题(3．3)，得到M-Pareto最优解和隶属函数值。

第5步。如果决策者对M-Pareto最优解的当前水平感到满意，停止。那么当前的M-Pareto最优解就是决策者的满意解。否则，请决策者更新当前的参考成员级别，通过考虑成员函数的当前值并返回Step4．

在交互式模糊满足方法中，需要求解块角结构的非线性整数规划问题(3．3)连同(3．4)．值得注意的是，这些问题是具有块角结构的单目标整数规划问题。鉴于这一困难，在下一节中，我们提出了基于参考解更新的连续松弛分解过程的遗传算法(GADPCRRSU)。

4.遗传算法与分解程序

如上所述，在本节中，我们提出了基于参考解更新的连续松弛分解过程的遗传算法(GADPCRRSU)，作为具有块角结构的非线性整数规划问题的近似解方法。

考虑块角结构的单目标非线性整数规划问题，公式为

注意，这个问题可以看作是原始问题的一个单目标版本(2．1)．

Sakawa等人[24]已经研究了基于参考解更新的连续松弛双字符串遗传算法(GADSCRRSU)，用于一般非线性整数规划问题，公式为 其中，个体由双字符串表示。如图所示，用双字符串表示2在一定程度上， 表示解空间中变量的索引，而，其中的价值的th变量．

鉴于(的块角结构4.1)，给一个人下定义似乎是很合理的作为集合晶片，，对应于块约束如图所示3.．

如果这些子个体用双字符串表示，对于每个子个体，，可以通过GADSCRRSU中的解码算法得到满足每个块约束条件的表型(子解)。

然而，不幸的是，这些子解决方案的简单组合并不总是满足耦合约束．为了解决这个问题，可以使用如图所示的三字符串表示4在双串表示的基础上，提出了相应的译码算法和译码算法。利用所提出的表示和解码算法，可以得到一个同时满足块约束和耦合约束的表型(解)．

更具体地说，在一个三元字符串中，表示对应于的子个体块,的优先级块,每个是一个变量的指标在表型和每个其中取整数值．在GADSCRRSU中，一个可行的解决方案，称为参考解决方案，对于三重字符串的解码是必要的。在我们提出的GADPCRRSU中，参考溶液作为溶液获得求解约束违背的极小化问题。下面，我们用一个参考解来总结三重字符串的译码算法,在那里是个人的数量和是个人号码的计数器。

4．1.三重串的解码算法

步骤1。让．

步骤2。如果，转到步骤3.．否则，请执行步骤步骤11．

步骤3。让，，．

步骤4。找到这样．让，．

第5步。让．

步骤6。如果和,让，，然后转到步骤7．否则,让然后转到步骤7．

步骤7。如果,让然后转到步骤8．否则，请执行步骤步骤5．

步骤8。如果，转到步骤9．否则，请执行步骤步骤4．

第9步。如果和，转到步骤11．否则，请执行步骤步骤10．

第10步。找到这样为．然后,让，．此外,发现这样,让，．剩余的元素将．终止解码过程。

步骤11。让，然后转到步骤12．

步骤12。找到这样,让．

步骤13。让．如果,让然后转到步骤15．如果，转到步骤14．

步骤14。如果和,让然后转到步骤15．否则,让，然后转到步骤15．

步骤15。如果，转到步骤13．否则,让然后转到步骤16．

步骤16。如果，转到步骤12．否则,然后转到步骤17．

步骤17。如果，转到步骤2．否则，终止解码过程。

期望连续松弛问题的最优解成为原始非线性整数规划问题的一个很好的近似最优解。在该方法中，在得到一个(近似)最优解后，，对于连续松弛问题，我们假设每个决策变量取完全或近似于所做的事。特别是决策变量如很可能是相等的．

更具体地说，是(近似)最优解的信息的连续松弛问题(4.1)用于产生初始种群和进行突变。为了生成初始总体，当我们确定每个的值时在三串的最低一行，我们使用一个带有均值的高斯随机变量和方差．在突变中，当我们改变的值对于一些，我们也使用一个带有均值的高斯随机变量和方差．

人们提出了各种繁殖方法。其中，Sakawa等[14]研究了六种再生产算子的性能，即排序选择、精英排序选择、期望值选择、精英期望值选择、轮盘选择、精英轮盘选择。结果证实了精英期望值选择对于包含决策者模糊目标的多目标0-1规划问题是相对有效的。因此，采用了精英期望选择——精英主义与期望选择相结合。这里将精英主义和期望值选择归纳如下。

精英主义
如果过去种群中一个个体的适合度大于当前种群中每个个体的适合度，那么将这个字符串保留到当前这一代。

期望值选择
对于一个由每个个体的预期数量，，每个子个体th个人，在下一个种群中，是 然后，积分部分 表示的确定数目保存在下一个种群中。While，用的小数部分 ，保存的概率，，在下一个种群中是由 如果单点交叉或多点交叉直接应用于三重串类型的上或中个体串，则子字符串的第Th元素可以取与子字符串相同的数字th元素。同样的情况也发生在通过遗传算法解决旅行商问题或调度问题上。为了避免这种违背，将一种称为部分匹配交叉(PMX)的交叉方法修改为适合于三重字符串。PMX通常用于上弦，而对于一对中弦和下弦，PMX用于双弦[14]适用于每一个亚个体。

现在是适当的介绍三重弦交叉方法的详细程序。

4．2．部分匹配交叉(PMX)上部字符串

让 做一个人的上级，让 成为另一个人的上级。准备副本和的和,分别。

步骤1。在这些弦上随机选择两个交点，和．

步骤2。集并重复以下步骤。(一)找到这样．然后,交换与并设置．(b)如果，停下来让是…的后代．否则返回(a)。一步是为了，如图所示5．

4．3．部分匹配交叉(PMX)双字符串

让 是一个亚个体的中下部分th族群,

是另一个亚个体的中下部分组人口。首先,准备副本和的和,分别。

步骤1。在这些弦上随机选择两个交点，和．

步骤2。集并重复以下步骤。(一)找到这样．然后,交换与并设置．(b)如果,停止。否则返回(a)。

步骤3。更换零件来的与,让是…的后代．

此程序是为和，如图所示6．

研究认为，遗传算法中突变起着局部随机搜索的作用。仅对三元串的下串采用位反转类型的突变，并对每一个子个体应用。

对于三重串的上串和中、下串，采用如下算法定义的反转

步骤1。确定两个反转点后和，挑出弦的一部分来．

步骤2。以相反的顺序排列子字符串。

步骤3。将排列好的子字符串放回字符串中。

数字7举例说明变异的例子。

现在我们准备介绍遗传算法的分解过程作为一个近似解的非线性整数规划问题的块角结构。程序概要如图所示8．

4．4.计算程序

步骤1。设置迭代索引(生成)并确定种群大小的参数值，交叉概率，突变概率，反转的概率、方差，，最小搜索生成和最大搜索生成．

步骤2。生成其子个体随机为三元串类型的个体。

步骤3。根据解码算法得到的表型对每个个体(亚个体)进行评估，并计算平均适应度以及最大适应度的人口。如果和,或者,如果，将适应度最大的个体视为最优个体，终止本程序。否则,设置然后进入步骤4．

步骤4。将复制操作符应用于所有子种群，．

第5步。根据交叉概率，将双串PMX应用到每个子个体的中下部分．

步骤6。根据变异概率对每个子个体的下半部分应用位反转型变异算子并根据反演概率对每个子个体的中下部分应用反演算子．

步骤7。上弦用PMX，请按．

步骤8。对上串应用逆运算符返回Step3.．

这里需要注意的是，在算法中，步骤4、5、6中的操作可以独立应用于所有个体的每个子个体。因此，理论上可以减少解决问题所需的工作记忆量，并进行并行处理。

5.数值例子

为了证明所提方法的可行性和有效性，考虑以下块角结构的多目标二次整数规划问题:

比较而言，使用基于参考解决方案更新的连续松弛(GADSCRRSU)的双字符串遗传算法[24也被采用。这里需要注意的是，GADSCRRSU中不涉及分解过程。

对于这个问题，我们设置，，，和，，，．的元素和在目标和约束条件上，以上问题均由均匀随机数确定和在约束条件中确定使可行域不为空。

在个人计算机(CPU: Intel赛扬处理器，900mhz，内存:256mb, C_Compiler: Microsoft Visual c++ 6.0)上进行了数值实验。

GADPCRRSU的参数值设置为:种群大小,交叉率,变异率,反转率、方差，，最小搜索代数和最大搜索代数．

在这个数值例子中，为了简单起见，线性隶属函数 ，确定参数值为[30.］ 为初始参考水平，增广极小极大问题(3．3)是解决。得到的解如表第二列所示1．假设假设的决策者对当前的解决方案不满意，他感觉到了和改进的代价是什么．然后，决策者将参考成员级别更新为．更新后的引用成员级别的结果显示在表的第三列1．由于决策者对当前的解决方案不满意，他将参考成员级别更新为以获得更好的价值．类似的过程以这种方式继续进行，在本例中，在第三次交互时为决策者导出了一个令人满意的解决方案。

表格1结果表明，与没有分解过程的GADPCRRSU交互方法相比，使用带有分解过程的GADPCRRSU交互方法可以在更短的时间内找到每个相互作用的(近似)最优解。

此外，为了了解块角非线性整数规划问题的计算时间随大小的增加而变化，GADPCRRSU和GADSCRRSU分别求解了10、20、30、40和50个变量的典型问题。如图所示9，可以看出，本文提出的GADPCRRSU的计算时间几乎随问题大小线性增加，而GADSCRRSU的计算时间则快速非线性增加。

6.结论

作为大规模离散系统优化的典型数学模型，本文考虑了块角结构的多目标非线性整数规划问题。考虑到决策者判断的模糊性，引入决策者的模糊目标，并将其解释为对多个模糊目标的总体满意度的最大化。提出了一种交互式模糊满足方法，以求得决策者的满意解。在实现了可开发的块角结构的基础上，我们提出了带分解程序的遗传算法来求解块角结构的非线性整数规划问题。算例说明了该方法的可行性和有效性。扩展到具有块角结构的多目标两层整数规划问题将在别处考虑。在不久的将来，还需要将其推广到具有块角结构的随机多目标两层整数规划问题。

参考文献

1. j . h .荷兰,自然和人工系统的适应:生物、控制和人工智能应用的入门分析，美国密歇根大学出版社，安阿伯，1975年。视图:MathSciNet
2. d·e·戈德堡搜索、优化和机器学习中的遗传算法，艾迪生韦斯利，美国马萨诸塞州雷丁，1989年。
3. z Michalewicz,遗传算法+数据结构=进化程序，人工智能，施普林格，柏林，德国，1992。视图:MathSciNet
4. z Michalewicz,遗传算法+数据结构=进化程序，施普林格，柏林，德国，第二版，1994。视图:MathSciNet
5. z Michalewicz,遗传算法+数据结构=进化程序，施普林格，柏林，德国，第三版，1996。
6. t .回来,进化算法的理论和实践:进化策略，进化规划，遗传算法，《克拉伦登出版社》，牛津大学出版社，美国纽约，1996年。视图:Zentralblatt数学|MathSciNet
7. T. Bäck D. B. Fogel和Z. Michalewicz，进化计算手册，英国布里斯托尔物理研究所，1997。视图:Zentralblatt数学|MathSciNet
8. k . Deb,基于进化算法的多目标优化， Wiley- interscience系列的系统和优化，John Wiley & Sons，奇切斯特，英国，2001。视图:MathSciNet
9. m . Sakawa大规模交互式模糊多目标规划，物理学，海德堡，德国，2000。
10. m . Sakawa遗传算法与模糊多目标优化，第14卷运筹学/计算机科学接口系列， Kluwer学术出版社，波士顿，马萨诸塞州，美国，2002。视图:MathSciNet
11. C. A. C. Coello, D. A. Van Veldhuizen和G. B. Lamont，求解多目标问题的进化算法， Kluwer学术出版社，纽约，纽约，美国，2002。
12. 艾本和史密斯，进化计算简介，自然计算系列，施普林格，柏林，德国，2003。视图:MathSciNet
13. “基于变量分组的大规模整数规划遗传算法”，信息科学第176期19，第2869-2885页，2006。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
14. M. Sakawa, K. Kato, H. Sunada, T. Shibano，《通过修正遗传算法的多目标0-1规划问题的模糊规划》，欧洲运筹学研究杂志，第97卷，第149-158页，1997。视图:谷歌学术搜索
15. M. Sakawa, K. Kato, S. Ushiro，和K. Ooura，“通过双字符串遗传算法的一般多目标0-1编程问题的模糊编程”，在IEEE国际模糊系统会议论文集，第3卷，第1522-1527页，1999。视图:谷歌学术搜索
16. M. Sakawa, K. Kato, T. Shibano，和K. Hirose，“使用双串表示和关于连续松弛问题的解的信息的遗传算法的模糊多目标整数程序”，在IEEE系统、人与控制论国际会议论文集，页967-972,1999。视图:谷歌学术搜索
17. M. Sakawa和K. Kato，“通过基于参考解决方案更新的双字符串遗传算法进行整数编程”IEEE工业电子、控制与仪器仪表国际会议论文集， 2000。视图:谷歌学术搜索
18. P.汉森，“用隐式枚举的二次0 - 1规划”，载非线性优化的数值方法(Conf.， Univ. Dundee, Dundee, 1971)， F. A. Lootsma主编，265-278页，学术出版社，伦敦，英国，1972。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
19. 李俊，“一种求解可靠性冗余优化的启发式算法”，微电子学和可靠性，第36卷，335-339页，1996。视图:谷歌学术搜索
20. 李丹，孙晓林，“非线性整数规划的精确解:收敛的拉格朗日和目标水平割法，”全局优化学报第39卷第3期1，页127-154,2007。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
21. R. H. Nickel, I. Mikolic-Torreira, J. W. Tolle，《计算航空节约政策:解决一个大的非线性整数规划》，计算优化与应用第35期1，页109-126,2006。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
22. M. S. Sabbagh，“纯非线性整数规划的部分枚举算法”，应用数学建模，第32卷，第2期12, pp. 2560-2569, 2008。视图:谷歌学术搜索|MathSciNet
23. 朱伟，“非线性整数规划的离散动态凸化方法”，计算与应用数学学报，第223卷，第2期。1, pp. 356 - 373,2009。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
24. M. Sakawa, K. Kato, M. A. K. Azad，和R. Watanabe，“非线性整数规划问题的双字符串遗传算法”，载IEEE系统、人与控制论国际会议论文集，页3281-3286,2005。视图:谷歌学术搜索
25. l . s . Lasdon大系统优化理论《麦克米伦》，纽约，纽约，美国，1970年。视图:MathSciNet
26. K. Kato和M. Sakawa，“带有块角结构的多维0-1背包问题的分解程序的遗传算法”，系统、人与控制论汇刊，B辑，第33卷，第410-419页，2003年。视图:谷歌学术搜索
27. K. M. Bretthauer, B. Shetty, S. Syam，“一个特殊结构的非线性整数资源分配问题”，海军研究物流，第50卷，第5期。7，页770-792,2003。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
28. M. Sakawa, H. Yano, T. Yumine，“多目标线性规划问题的交互式模糊满足方法及其应用”，IEEE系统、人与控制论汇刊，第十七卷，第二期4，第654-661页，1987。视图:谷歌学术搜索|MathSciNet
29. m . Sakawa模糊集与交互式多目标优化《应用信息技术》，三中全会出版社，美国纽约，1993年。视图:MathSciNet
30. 周宏儒。齐默尔曼，《带有多个目标函数的模糊规划和线性规划》模糊集与系统， vol. 1, no. 11，第45-55页，1978。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet

版权

版权所有©2009 Masatoshi Sakawa和Kosuke Kato。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。