Bicriteria方法识别Nondominated组合

文摘

我们探索投资组合构建模型,制定满足给定的技术要求,与项目的最小数量和最小冗余。一个算法发出强劲的投资组合建模是适应一个向量模型,修改方便的优势条件,为了找到nondominated组合的集合,一个bicriteria整数线性规划问题的解决方案。为了改进前算法,找到一个最优解的monocriteria版本提出了这个问题,这是进一步用作第一个可行的解决方案帮助更快地找到nondominated的解决方案。接下来,排序过程应用于输入数据或信息矩阵,这是打算修剪nonfeasible在建设性的早期解决方案的算法。数值例子表明,该优化和排序过程既能改善原算法的计算效率。他们的限制也显示在某些复杂的情况下。

1。介绍

马科维茨的第一个全面的理论框架提供了投资组合选择问题1]。在他的提议,每个投资组合的预期收益和风险评估。有效集,或有效边界,对应于最大的投资组合预期回报,风险水平。从这个框架,预期回报通常是评价的加权和每个项目的投资组合的预期回报,而风险值是评价投资组合的方差。因此,投资者可以选择投资组合的有效边界,最佳匹配她/他的需求。

在投资组合选择两个向量的定义2]。首先,投资比例向量对应的比例资金投资者接受每个成员一组证券投资(项目)。的标准向量相反,包含措施评价投资组合的价值。从这个意义上说,一个有效的投资组合,第一个向量,是nondominated组合,第二个的感觉。多准则组合选择问题设一个标准向量和三个或更多的标准(3),预计将nondominated组合的计算更加困难。然而,下面,我们表明,取决于是考虑作为一个评估措施,即使两个标准投资组合的生成是一个困难的组合问题。

自投资组合选择问题本质上包含了商业标准,预算限制,并返回波动(4在文献中),问题是制定预期收益的最大化,收益的不确定性。当多准则被认为是版本,一些需要最大化效用函数,约束定义可行的投资组合(1,4,5]。在这种背景下,nondominated组合可以使用多目标算法计算(6多目标模型[],进化方法7,8),或喜好编程(9]。

在本文中,我们专注于投资组合生成过程,当业务、预算,甚至波动信息差。一些严格的情况下预留至少将项目组合选择过程分为两个阶段:技术和业务问题。我们将在第一阶段,制定我们的问题在满足给定的技术要求,与项目的最小数量和最小冗余。这是一个特殊的角度选择问题在哪里。如下解释,事实上,我们关心的是一代的有趣组合多的问题选择最佳组合。

因此,我们把问题在很早期阶段的nondominated组合识别。为了解决这个想法,一般选择多准则决策协助(MCDA)框架(10),集中我们的注意力问题公式化的阶段,假设的集合的定义(即潜在的行动。选择候选人,或决策主体)11]。然而,在许多实际情况下,我们假设行动不明确的元素。的确,西蒙是第一个科学家提出,行动不完美的定义和表示在决策过程12]。因此,当行动不是事先给定的,一个搜索的过程必须被激活,以发现或设计。在某些情况下,除了抽象的或非常基本的决定过程,必须由一个潜在的行动对象可用剧目的基本元素。项目组合的问题类似这种情况很好。规定的经营活动,投资组合选择是受孕的过程从离散的组合,甚至相互关联的项目。

我们提出一种方法来支持探索性搜索的分析师,帮助他/她确定的限制列表nondominated有趣的组合从一组项目,满足整个组的需求。观察到最相关的项目投资组合并不一定对应于这些满足最大数量的需求,而是那些混合与其他项目,我们提出了一个算法,提供了一个列表的所有潜在的有趣的组合,根据需求覆盖率和集体最小冗余。适用的方法是在详细的业务信息的情况下是贫穷和nondominated有趣的组合可以在进一步的发展阶段,分析当更好的信息是可用的13]。

本文组织如下。节2问题陈述被建模为一个bicriteria整数线性规划和建设性的过程允许探索一套项目以识别nondominated组合定义。这样的命题保证过程是收敛的证明。接下来,一个算法基于建设性方法介绍部分3。提出这一过程的改进,意识到获得的方法对初始值很敏感的一个独立工党模型的标准。节4我们的方法是测试和获得的结果相比以前的工作。最后,部分6致力于的结论。

2。模型公式

让我们考虑一个经理参与投资组合选择和组合的过程,寻找项目的不同组合,满足技术要求。此外,让我们假设她/他喜欢最初探索一套限制的项目,只有寻找一些有趣的投资组合选择。碎片的小勘探显示他/她的可能性进一步考虑它们与新业务标准(成本、收益、利润等)或市场相关功能(扩张,搭配,领土范围,等等),等等。因此,这个问题由识别组投资组合满足给定的需求定义的分析师,知道一个系统的探索可能是一个非常困难的任务,甚至是不合理的。在这样的背景下,有可能帮助分析师早期建设的有趣的解决方案,使用有限的信息?

方法论上,这是一个决策活动展开第二阶段(11]。

2.1。问题公式化

配方的问题是一个语句定义三联体,在那里是一组动作,在我们的案例中投资组合,是一组的观点(例如,维度)认为评价的元素,是一个语句定义完成的元素是什么(选择、排序、分类等)。

2.2。评价模型

正式的评价模型是一个元组,在那里是一组标准,最终来源于,允许evaltation的元素在每个标准;模型不确定性关于可用的信息;和是一个聚合逻辑定义有关的信息和是为了获得一个全球结论解决问题吗。评价模型产生一个输出的过程。

2.3。建议

评价模型的输出转换为决策者的语言,验证它在技术上是声音和决策者的设置和部署过程。

在问题公式化阶段,通常应该是一个已知的事实或一个建模任务的结果,通常在线性规划,例如,当一组可行的替代方案是由线性建模的限制。在这样的假设,元素的成为问题的分析、评价和建议。然后,可以应用在一个常规的方式进一步的阶段。

在我们的例子中,一个投资组合是事先不知道,成为替代一旦被构思或设计为一个项目组合。我们限制自己定义的一组投资组合的问题,考虑到游泳池的项目先天的。然后,将组件的子集组合覆盖一组预定义的要求。

发现nondominated组合的制定作为bicriteria整数线性规划。让我们考虑(我) 是项目的集合;(2) 一组可能的投资组合,,;(3) ;矩阵的项目和要求;(iv) 如果覆盖的需求否则。(v) 如果是包含在一个可行的解决方案,如果不是;(vi) 次要求覆盖。

下面的程序是一个模型的问题,整个组nondominated组合同时最小化项目的数量在复合和冗余度;的次数,由多个项目的需求。考虑 检查这个模型我们观察,只考虑目标(),这个程序对应的实例集合覆盖问题,众所周知的赋权。结果是,在一些实例中,这个程序不能通过传统的方法解决分支定界方法(14]。相反,我们提出一个算法基于一个建设性的过程改编自[偏爱的编程方法9),帮助找到一个高效的算法的鲁棒性nondominated组合引入了。这种算法最初是在不完全信息的背景下提出的评估项目的持续价值函数和各自的权重。有趣的是,该算法也是基于进步代nondominated组合,可分成两个阶段:一代的候选人和修剪。

命题1以下担保程序寻找帕累托的每个nondominated解决方案方面,基于两阶段方法描述。

命题1。让,是一组项目,投资组合有最多k项目。同样,让和被定义为的冗余和覆盖水平,需求的满足,nondominated组合的集合在考虑到集,定义如下: 然后

证明。让我们继续用归纳法。因此,假设包含一整套nondominated组合结合1、2,或规模的项目。通过建设,包含一整套可行的和不可行的项目组合改善,或至少等于最小冗余值的计算阶段。任何投资组合恶化这个值不包括在这个集合。因此,。让被定义为
然后,很明显,和,。结果是,设置nondominated组合发现直到舞台。在圆,将包含一整套nondominated组合。

在下一节中,我们提出一个算法基于命题1。此外,介绍了改善注意到项目组合的逐步建设和修剪时可能会加速一个方便的设置上限和一个方便的排序是应用于信息矩阵。

3所示。算法

在这一节中给出的算法的主要目的是识别的一整套nondominated组合。不同的算法和方法已经提出了这个任务(14]。然而,我们专注于提供的解决方案(9],我们适应了作为一个战略计划(1)。它是基于候选人的建筑和修剪过程实现建设性的一代的项目组合。在该算法中,为了产生候选人可能选为可行的解决方案,任何投资组合有冗余大于或等于最小冗余,发现在当前水平的过程,是修剪。接下来,潜在的可行的解决方案是nondominated候选人相比,已发现的先例迭代。该算法在算法中定义1。

这个函数候选人(算法2在这种方法中)是生成模块。它很有趣,因为我们可以改变为了改变算法的行为(15]。注意到一个初始冗余值设置数量足够大,将修改后的第一次找到可行解(即。,一个投资组合)。实际上,该算法逐步生成nonfeasible候选人,直到找到一个可行的解决方案,制定第一个值最小冗余和投资组合的大小。然而,这种行为意味着,根据组件对需求的覆盖结构,这些初始值可以确定后一个非常昂贵的搜索过程。

事实上,程序可以改进,如果方便的初始值是一开始的算法。然后,让我们考虑以下项目:

在这种情况下,我们执行的monocriteria版本bicriteria独立程序,在它的最优解不一定解决原来的问题,但它给一个好的上界的冗余和投资组合的大小。接下来一位比较有和没有一个上界进行了分析。结果提出了两个项目4。

4所示。结果

为了知道差异之间存在原始算法和一个上界的版本,都应用于模型(1),定义了一组实例。一个实例对应一组项目,需求,信息矩阵。根据勘探结果(15,实例测试不同比例的0,或密度:50%,75%,80%。为每个实例和预期比率为0,30随机矩阵使用蒙特卡洛过程已经招满,同意给定密度值。在结果中,每个实例模拟了30次,平均时间的解决方案,以毫秒计,已被计算。MacBook Pro I5, 8 Gb RAM, 2.3 Ghz用于实验。

平均时间为该算法找到帕累托面前的上界(WUB)和算法没有绑定(核心)提出了表1。我们比较这些结果与发现Apriori-based算法(13,14]。在该算法中,我们称之为美联社,修剪规则是一样的:最小数量的对象和冗余。只有平均时间小于等于1分钟报告,既强调情况或一个算法在很短的时间内做出反应。没有条目显示为一个实例的情况下意味着各自的模型不能在这样的时间解决这个问题。

当一个特定的模拟WUB算法被认为是冗余的初始值是选为最优值获得各自的模拟运行的核心。通过这种方式,我们执行WUB模型来展示其最好的行为。正如预期的那样,更多的需求或项目数量增加,增加更多的时间解决方案。结果表明,WUB模型优于其他人,除了一种情况(下划线)。密度(0的比例)算法是一个重要的条件。要点和美联社非常敏感特性,但它允许我们考虑这个密度如何作用于该算法的性能。我们假设分布的零信息矩阵可能是重要的,因为它决定了第一个找到可行的解决方案。

为了知道零影响的分布算法,排序过程应用于信息矩阵每一个实验的情况如下。(我)需求(列)从左到右排序,根据他们的次数。(2)项目(行)按降序排序根据需求的数量。因此,两个过程被添加到分析:WUB和核心算法,排序过程的早期,应用于当前信息矩阵,分别名为WUB /奥德和核心/奥德。在表2,结果WUB和新工艺进行了比较。

可以看出WUB /奥德表现优于其他算法。这表明,排序会对结果有良好的影响。在表3,WUB /奥德是相对于其他两个版本的先验的算法,第一排序过程和冗余的上限(WAP /奥德)和第二排序过程但没有上限(小睡/奥德)。

这些结果表明,WUB /奥德并非在所有情况下的最佳方法。例如,它不能解决某些情况下解决了基于先验的流程。相反,WUB /奥德可能超越这些过程在不同的情况下。一般来说,我们得出这样的结论:0的分布信息矩阵是一个至关重要的问题。此外,排序过程是一个很好的策略,但它不规模的稀疏结构(例如,)。

5。讨论

结果表明,算法的性能取决于项目的数量,需求的数量,零的分布信息矩阵的一个给定的实例。一个简单的策略应用由小尺寸的实例。这种方法可能在其他的研究发现。实际上,投资组合问题已经使用多准则框架建模。这些方法的基本原理包括确定有趣的项目和未来组成的投资组合。

在[16)离散和连续的两级组合多准则决策援助方法提出了共同基金选择和组合。在第一阶段,多准则决策方法用于选择最有前途的共同基金。在第二阶段,应用目标规划方法,以寻找最好的最终共同基金的投资组合比例。标准用于选择和组合分为三个类别:标准关于共同基金投资的预期结果;标准测量风险来获取一个结果;和标准对共同基金的效率。在[5两级过程应用的选择和组合构成的一组项目。在第一级,ELECTRE三决定援助方法用于排序项目根据给定的类别,例如,好的,平均水平,而坏的项目。在第二个层次,一个投资组合在每个类别被确定为项目满足特定约束条件的列表。

在[4),选择和组合投资组合问题也解决的过程分为两个阶段,但方式不同。首先,多准则决策分析应用于评估项目。接下来,一个背包优化问题,投资效益最大化,预算约束,解决找到一个有效的投资组合。优化问题是包含在一个算法寻找有效的投资组合的集合。

上述几个方面的技术可能适合我们的目的。例如,以下(16]或[5),这一过程可能适用于过滤noninteresting项目的大小,减少实例进行分析。此外,根据(4),建设性的算法可以实现为一个接一个的优化问题协助找到帕累托前沿。然而,这些程序不一定允许检测一整套高效的解决方案。作为一个例子,让我们考虑表4,由8个项目的一个实例的信息矩阵和八个需求。这个问题有三个解决方案,每一个相当于一个冗余值3:,,。在这种情况下,我们提出以上任何详尽的算法允许识别这些投资组合,同时优化问题发现只是其中之一。

我们的主要目的是确定有趣的解决方案,在消耗资源和时间的信息有关的项目和投资组合。因此,我们建立了这里的问题包括有一个减少的投资组合和项目数量有限的资源可能注定要更详尽的分析。事实上,我们可以把有趣的项目如下9]:(我)核心:项目目前在每个nondominated组合,(2)边缘:项目出现在一些nondominated组合,(3)外观:项目排除在任何nondominated组合。

例如,在前面的例子中,没有项目nondominated组合是核心,但边缘。总的来说,我们认为最好的是使用资源和核心和边缘项目的时间更好的信息。换句话说,马科维茨的投资组合问题可以应用这些有趣的项目。

算法的效率是一个关键问题。观察表3,WUB /奥德方法是否一个信息矩阵是稀疏的,或者说,它是充满了至少50。在[9]分析了50个项目使用原来的算法我们适应这里。在这种情况下,项目评估关于四个标准,预算约束。他们表明,这个问题的解决是耗费时间,但如果最初的有趣nondominated组合算法,介绍了时间分辨率的提高。这个想法是用于WUB /奥德方法,发现冗余值的上限,也证实了这样的战略工作正常甚至提出了离散模型。

6。结论

制定投资组合提出了建设性的模型,在满足给定的技术要求,与项目的最小数量和最小冗余。艾滋病的方法支持探索性搜索的分析师,帮助他/她确定的限制列表nondominated有趣的组合项目设置,满足整个组的需求。认为该方法是适用于情况详细的业务信息项目是贫穷或很难获得,可用资源。Nondominated有趣的组合可以在进一步的发展阶段进行分析,获得更好的信息时。

解决一个整数线性规划可以首先找到一个最优的解决方案,用于帮助构建新的nondominated解决方案可行的结果。数值例子表明,这个过程提高了原算法的计算效率。我们发现0的比例在信息矩阵是一个关键问题,因为它决定了时间的流逝之前找到第一个可行解的算法。因此,排序过程,提出了改善时间来寻找解决方案。

需要做进一步的研究,以测试修剪不同分布的零矩阵的信息。进一步的研究还包括分析和模拟研究有关的影响metaheuristics(或混合方法)(17]和hyperheuristics [18在质量和时间的解决方案。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

Broderick克劳福德支持格兰特CONICYT / FONDECYT /普通/ 1140897。里卡多·索托支持格兰特CONICYT / FONDECYT / INICIACION / 11130459。哈维尔·佩雷拉和费尔南多帕雷德斯支持格兰特CONICYT / FONDECYT /普通/ 1130455。

引用

1. h·马科维茨,“投资组合选择”,《金融卷,1952年,第91 - 77页,1952年。视图:谷歌学术搜索
2. r . Steuer y气,m . Hirschberger”投资组合选择的多个标准,”金融工程手册18卷施普林格优化及其应用页,3-24施普林格,2008年。视图:谷歌学术搜索
3. p . j . Liesio温和,a .萨罗城“稳健投资组合建模与不完整的成本信息和项目相互依赖关系,“欧洲运筹学杂志》上,卷190,不。3、679 - 695年,2008页。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. j . c . Lourenco a·莫顿和c·a·巴纳e科斯塔”探索组合多准则决策支持系统的鲁棒性评估,”决策支持系统,54卷,不。1,第550 - 534页,2012。视图:谷歌学术搜索
5. j .郑o . Cailloux摩梭诉,“限制多准则排序方法应用于投资组合选择,”第二届国际会议上算法的决策理论罗格斯大学,页26 - 28日期间,DIMACS,新泽西,新泽西,美国,2011年10月。视图:谷歌学术搜索
6. m . Ehrgott x Gandibleux,“多目标组合优化的调查和注释的书目,“或Spektrum:定量管理方法,22卷,不。4、425 - 460年,2000页。视图:出版商的网站|谷歌学术搜索|MathSciNet
7. k . Doerner w . j . Gutjahr r·f·哈特尔c·施特劳斯和c的葡萄汁,”帕累托蚁群优化:metaheuristic方法多目标投资组合选择,”《运筹学,卷131,不。1 - 4、79 - 99年,2004页。视图:出版商的网站|谷歌学术搜索|MathSciNet
8. k . Metaxiotis和k . Liagkouras”,对项目组合管理的多目标进化算法:一个全面的文献综述,”专家系统与应用程序,39卷,不。14日,第11698 - 11685页,2012年。视图:出版商的网站|谷歌学术搜索
9. p . j . Liesio温和,a .萨罗城”偏好稳健投资组合建模编程和项目选择,”欧洲运筹学杂志》上,卷181,不。3、1488 - 1505年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
10. b·罗伊多准则方法决策帮助Kluwer学术出版商,多德雷赫特,荷兰,1996年。
11. d . Bouyssou t Marchant, m . Pirlot, p . Vincke认为,评价与决策模型与多个标准卷,86国际系列运筹学和管理科学施普林格,纽约,纽约,美国,2006年。视图:MathSciNet
12. h·西蒙,“理性选择行为模型,”经济学的季刊,卷69,不。1,第118 - 99页,1955。视图:出版商的网站|谷歌学术搜索
13. c·洛佩兹·h·Astudillo和j·佩雷拉,“对基于组件的系统鲁棒性分析建立在不完全信息,”学报第一国际研讨会上与不确定性(IWLU ' 07)和22日自动化软件工程国际会议(ASE ' 07)2007年11月,亚特兰大,乔治亚州,美国。视图:谷歌学术搜索
14. f .裴瑞兹和j·佩雷拉”bi-criteria整数规划和软件架构选择建模算法,”《LIO-INFORMS联合国际会议布宜诺斯艾利斯,阿根廷,2010年6月。视图:谷歌学术搜索
15. 裴瑞兹·j·佩雷拉,a .干地亚”向requirementsbased bi-criteria方法确定有趣的项目投资组合,”21国际会议的程序多标准决策Jyvaskyla,页,北京,芬兰,2011年6月。视图:谷歌学术搜索
16. k . Pendaraki c . Zopounidis和m . Doumpos”建设的共同基金投资组合:多准则方法和一个应用程序来希腊股票共同基金市场,”欧洲运筹学杂志》上,卷163,不。2、462 - 481年,2005页。视图:出版商的网站|谷歌学术搜索
17. b·克劳福德r·索托e . Monfroy c·卡斯特罗w·帕尔马和f .帕雷德斯,“混合子集的软计算方法问题,”数学问题在工程文章ID 716069卷,2013年,12页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
18. b·克劳福德r·索托e . Monfroy w·帕尔马,c·卡斯特罗和f .帕雷德斯,“选择函数的参数调优hyperheuristic使用粒子群优化的基础上,“专家系统与应用程序,40卷,不。5,1690 - 1695年,2013页。视图:出版商的网站|谷歌学术搜索

版权

版权©2014哈维尔·佩雷拉等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。