双目标生成树的转基因算法及性能分析

IJIJIJQ可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）449-460www.elsevier.com/locate/entcs求解双目标生成树问题伊斯拉梅湾C. Fernandes，1，2Silvia M.D. M.3Elizabeth F.G. 4Marco C.Goldbarg5巴西纳塔尔北里奥格兰德联邦大学信息学和应用数学系摘要双目标生成树（BiST）是最小生成树（MST）问题的NP-难扩展。BiST模型的情况下，其中两个conciliicting目标需要同时优化。BiST已在文献中研究，并提出了几种启发式算法，其中大多数是进化技术。转基因算法是成功应用于BiST的这些进化技术之一。然而，先验定义的参数可以限制算法中使用的搜索机制。 在这项研究中，我们提出了一种新的转基因算法，对于BiST，其中自动做出关于在其执行过程中使用的搜索机制的决定。对165个基准实例的计算结果分析表明，该算法对两个不同的质量指标产生了良好的近似集.保留字：双目标生成树，进化算法，组合优化1介绍带和目标的多目标生成树（MoST）是最小生成树（MST）问题的NP难设G=（V，E）是一个无向连通图，其中V ={v1，v2，...， v n}表示顶点的有限集合，并且E={（i，j）|v i，v j∈V}一个有限边集，使得|E|=m。令w：E →Eq是分配向量w ij=（w1，w2，.，w），q> 1，1 本 研 究 部 分 得 到 了 NPAD/UFRN （ 北 里 奥 格 兰 德 州 联 邦 大 学 高 性 能 计 算 中 心 ） 、 CAPES （ CoordenacampaigndeAperveicampaignntodePessoaldeN'estivelSuperior）和巴西CNPq（ConselhoNacionaldeDese nvolvime ntoCie nt′ficicoe Tecno l′ogico）的支持 ，资助金额为301845/2013-1和308062/2014-0。2电子邮件：islamifelipe@gmail.com3电子邮件：silvia@dimap.ufrn.br4电子邮件：beth@dimap.ufrn.br5电子邮件：marcocgold@gmail.comhttps://doi.org/10.1016/j.entcs.2019.08.0401571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。450I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449ΣW∗ΣIJΣ的非负实权重的集合（i，j）∈E。 图G的一个生成树T=（V，ET）是图G的一个无圈生成子图，其中ET<$E.设X是G和Z的所有生成树的集合，且Z是目标空间。函数f：X→Z将每个T ∈ X与向量f（T）=（ f1（T）， f2（T），.， f q（T））∈ Z，其中f k（T），k∈{1，.， q}，由等式qua tion（1）定义。(1)fk（T）=k（i，j）∈ET设T1和T2∈X.T1弱控制T2，记为T1≤T2，当且仅当fk （T1）≤fk （T2），k∈{1，.，q}。 T1优于T2，记为yT1<$T2，如果且o <$如果T1≤T2且<$j∈{1，.， q}满足fj（T1）或如果在全局档案中p ，则由操作产生的p替换当前群体中的p，使得pp。转座 子包括干 扰程序 ，适用于 内共生 体的限制TLP 有两 个转座子 ，称为remTransp和primTransp。remTransp的扰动方法包括移除从p中随机选择的#sizeRem边缘并向p添加新边缘，其中#sizeRem是参数。从p中移除的每条边被重新连接树的边替换，并且其标度化成本在所有可能的边中是最好的。每个边移除/添加操 作都会生 成一棵 新树。 新的树存 储在非 支配解 的本地档 案中。 最后，remTransp返回从本地存档中随机选择的解决方案p该算法从p中移除l条边，其中l是从范围[[0. [0. 95 n.]。边缘的标度化成本越高，其被移除的概率就越高。然后，primTransp使用rmcPrim方法重新构建解决方案。每次迭代的TLP，所有的内共生体提交给质粒或转座子。选择质粒类型的概率为#probPlasm（因此，选择转座子的概率为1- #probPlasm）。对于TLP算法的#intGerSet迭代，#probPlasm概率保持固定，然后#probPlasm增加。 如果质粒类型是选择的，则算法在范围内选择简单或重组类型I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449453概 率 一 致 的 概 率 。 如 果 选 择 转 座 子 类 型 ， 则 remTransp 具 有 被 选 择 的 概 率#probRemTransp （ primTransp 具 有 概 率 1- #probRemTransp ） ， 其 中#probRemTransp是参数。TLP应用于[15]提出的多达1000个顶点的基准实例。它优于[26]和[2]提出的BiST的先前算法。3多智能体转基因算法转基因代理是在转基因算法的搜索过程中对解进行修改的工具可能存在许多转基因剂，其中一些用于多样化，另一些用于加强搜索。本节介绍了一种转基因算法，它可以自动控制选择哪种代理来操纵当前种群中的内共生体。程序TMA显示了本研究中提出的算法的一般伪代码。TMA源自TLP，并保留了后者的一些要素。TMA维护了有限的非支配解的存档，GA。为了初始化GA，用[13]（第2行）提出的几何方法生成具有#numSup良好分布支持解的集合，其中#numSup是参数。每个支持的解决方案都是用几何方法计算的权重向量来计算的。每个权重向量诱导边的排序。该算法维护#numSup权重向量和对应的排序边列表因此，我们认为，在主机的存储库中维护的信息存储支持的解决方案列表的原因是G A存档有限，更新时可能会丢失某些解决方案。用于创建TMA初始种群的方法是由第2节中描述的TLP执行。TMA中有7个质粒和3个转座子。它们的成功率最初设置为0（第4行）。每 次 迭 代 ， 创 建 一 个 具 有 #numPlas 质 粒 的 集 合 （ 第 7 行 ， 程 序Plasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplasplaspl质粒有两种类型：简单质粒和重组质粒。该算法处理三个简单的质粒和四个重组体。与TLP中一样，质粒的信息是一个具有pl边的集合。简单plas-plasm的信息是由两种方法中的一种创建的：第2节中描述的s1和s4。方法s4从随机支持的解中选择pl个随机边。重组质粒的信息通过两种方法中的一种创建：第2节中描述的s2和s3。s3方法通过s1方法构建质粒信息的40%，通过s2方法构建质粒信息的对质粒实施了两种操作方法：第2节中描述的m1和m2。在m2方法中，来自p的边和质粒的信息被连接起来，并根据从宿主库中随机选择的权重向量进行排序。一个新的解决方案，p，是由Kruskal如果p不是一棵树，则将原始图的新边添加到p，并使用相同的权重向量和Prim方法。表1总结了质粒中使用TLP中实施的验收标准454I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449在TMA中也得到了使用，并在程序中得到了更好的实施（）。算法1TMA算法一曰： 过程TMA（level：real;#numSup，#popSize，#numPlas，#GerReset：integer）2：preProcessingPhase（#numSup，GA）3：生成种群（P ={p1，...，p#popSize}，G A）4：成功[t]= 0，成功转基因剂t5：gen←16：重复7：setProbPlas（）; setProbTrans（）; setProbPlas（#numPlas）8：对于所有p∈P，9：如果随机（0，1）水平，则10：pl←getPlasm（#numPlas）;p←plasmid（pl，p）11：如果更好（p，p），则12：p←p;成功[pl]++13：如果结束14：其他15：tr←getTransp（）; p←transpid（tr，p）16：如果更好（p，p），则17：p←p;成功[tr]++18：如果结束19：如果结束20：结束21：updateLevel（level）22：如果gen mod#GerReset== 0，则23：成功[t]= 0，不含转基因剂t24：如果结束25：gen++26：直到满足停止标准27：返回G A28：结束程序表1增塑剂名称类型信息操纵名称类型信息操纵PLM1重组S2M1PLM5重组S3M1PLM2重组S2M2PLM6重组S3M2PLM3简单S1M1PLM7简单S4M2PLM4简单S1M2实 现 了 三 种 转 座 子 ： newRemTransp 、 krusTransp 和 swap-Transp 。newRemTransp源自第2节中介绍的remTransp。它们之间的区别在于选择要返回的解决方案的方法。两个转座子都创建了一个非支配解列表。newRemTransp可以返回最接近理想点的解，涉及目标空间中的欧几里得距离或以均匀概率选择的随机解。前者返回的概率为70%。该krusTransp工程同样I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449455primTransp，除了Kruskal的方法在前者中重建树。最后，swapTransp从内共生体p移除随机边缘e，从而产生两个连接的分量。然后，所有的树所导致的包括每个边缘之间的两个连通的组件之间的割集进行测试。这个操作产生一组成对的非支配树。swapTranp从这个集合中返回一棵树，它是由newRemTransp的相同方法选择的。每当由转基因代理创建解决方案p时，GA被更新，并且f∈ pJ∈GA，使得pJ∈p。每次迭代，所有内共生体都受到随机选择的转基因试剂的攻击（第8-20行）。质粒被选择的概率由水平（第9行）给出，因此，转座子被选择是1-level（第14行 ） 。 最 初 ， 选 择 质 粒 或 转 座 子 的 概 率 是 相 同 的 ， 即 ， level = 0. 5. 过 程updateLevel（第21行）如下更新变量level的值。5的值保持不变。105目标函数的评价。然后，在剩余的迭代中，到countEvel/106，其中countEvel是当前评估的数量。因此，转座子被选择的概率随着时间的推移而降低。采用这种策略是因为，如[20]所观察到的，转座子似乎在初始迭代中更有效，而质粒在最终迭代中更有效一旦选择了转基因剂类型，质粒或转座子，算法从该类中选择（第10行和第15行，分别用于质粒或转座子）。选择取决于转基因代理为每种转基因剂维持一个计数器。每当转基因试剂的操作成功时，计数器就递增当过程更好地返回真值时。计数器较高的转基因剂更有可能被选中。轮盘赌选择用于选择转基因剂。最初，相同类型的代理人同样可能。每次迭代，与质粒和转座子相关的概率都在第7行中更新，涉及它们的成功率。在每个# GerReset迭代序列之后，成功计数器被设置为零，并且概率被重新初始化（第23行）。因此，TMA可以处理长期（高#GerReset）或短期（低#GerReset）成功率历史。4计算实验实验是在UFRN高性能计算中心（NPAD/UFRN）提供的基础设施上进行的。每个测试都分配给Intel Xeon处理器E5- 2698 v3的一个核心，具有2.3 GHz和4Gb RAM每个核心，运行CentOS 6.5，64位。在[15]提出的方法生成的165个完全图上进行了实验。 这组实例它被称为KNW。KNW集合被分为三类：相关（Corr），反相关（Anticorr）和凹（Conc）实例。每个类包含55个由n.ID标识的实例，其中n是顶点的数量，范围从50到1000，ID∈ {1， 2， 3， 4， 5}标识用相同的顶点生成的实例。456I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449∈Σ参数 生成了ID= 1、 2、 3、 4、 5的相关系数为0。1，0。三，零。五，零。七，零。9，分别。反相关实例类似地用相应的负相关因子生成。生成凹实例所需的参数η和η分别从[0. 0009，0。3]和[0.0001，0。03]。我们将TMA与TLP以及[8]提出的一种经典的成功的双目标问题遗传算法--非支配排序遗传算法（NSGA-II）进行了比较。NSGA-II的初始群体P是通过第2节中描述的相同方法产生的。解采用边表数据结构进行编码。 每一次迭代，一个O-弹簧种群P，使得|为|P|，已创建。|, is created. 一个二元锦标赛的变体[25]被用作选择方案在P中随机选择两对个体：第一对竞争第一个目标，第二对竞争第二个目标。一个O型弹簧由[23]建议的重组和突变算子生成。重组运营商包括在应用randomWalk方法的父母边集的工会。突变会向树中添加一条新边，并从创建的循环中删除另一条边下一代的个体选择的非显性秩和拥挤距离在标准NSGA-Ⅱ。对每个实例执行每个启发式算法的30次独立执行。所有算法的停止标准均为106次评价。我们分析了处理时间和产生的近似集的质量两个指标被用来评估近似集的质量：超容量和倒置世代距离。超体积（HV）指标由[32]提出，并且是已知关于帕累托优势严格单调的唯一单集质量度量[3]。HV测量由近似集支配的目标空间的体积。为了计算HV，我们需要一个参考点来约束目标空间。我们使用[16]提出的方法来计算参考点。反向代际距离（IGD）指标[6]用于评估近似集中解的多样性。IGD用等式（4）计算，其中ZJ是近似集，R是参考集，并且ds（r，ZJ）是点r R与ZJ中的最近目标向量之间的距离。 在这项研究中，实例的参考集R是通过从所有测试算法生成的所有近似集的并集中过滤非支配点来获得的[16]。（四）IGD（Z<$J，R）=r∈Rds（r，Z<$J）|R|弗里德曼检验[11]用于验证测试算法产生的解决方案。Holm事后检验[14]用于检测TMA与其他算法之间的特异性差异。显著性水平为0。05.我们使用[ 20 ]定义的值作为TLP参数，包括#sizeRem = 0。05 n和β = 0。03、关于TMA 其他TMA参数使用IRACE软件包进行了调整：#popSize= 150，#numSup= 59，#numPlas= 21，#GerReset= 196。既然我们想给同样的概率-I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449457为了使算法在第一次迭代中选择质粒或转座子，我们将水平参数设置为0.5。TMA中使用的外部存档仅限于300个解决方案，并使用[15]提出的自适应网格技术进行更新。NSGA-II算法的交叉率和变异率分别为0。97和0。04.与TLP和TMA一样，NSGA-II采用的人口规模为150人。表2显示了通过Friedman检验为每组和各类KNW实例计算的平均排名。值越低，算法排名越好。以秒为单位的平均处理时间显示在列T（s）中。通过Friedman检验计算的所有p值均小于0。05，这意味着，从统计学上讲，TMA、TLP和NSGA-II在HV和IGD方面存在显著差异。除了针对反相关ID= 1组（红细胞）计算的HV指标外，TMA算法的排名优于关于HV和IGD（绿细胞）的其他算法。对于TMA排名更好的大多数情况，Holm事后检验表明存在显著差异。HV指示符的例外情况是：相关实例的组1和5，反相关实例的组2以及凹实例的组1、2和3。这些例外涉及TLP。关于TLP的IGD指示符的例外情况是：相关实例的组5和凹实例的组1、2和3。对于IGD指标，仅观察到一个例外，即关于NSGA-II算法的第1组反相关实例和第1、2和3组凹实例。列T（s）显示，平均而言，TMA比其他算法花费更少的处理时间我们可以得出这样的结论，自动决定哪个转基因代理，基于成功率，提高了算法的解决方案质量和处理时间。表2KNW实例的结果。IDAlg.Corr.反校正浓HVIGDT（s）HVIGDT（s）HVIGDT（s）1TMA1.271.733.001.002.003.0081.99194.72513.061.821.272.911.452.821.7341.44198.42579.211.361.912.731.272.002.7351.63172.32547.15TLPNSGA-II2TMA1.002.003.001.002.003.0091.77198.23499.361.091.913.001.182.092.7336.88204.04580.151.272.002.731.272.002.7358.35168.20551.37TLPNSGA-II3TMA1.002.003.001.002.003.0092.30195.22486.201.002.003.001.092.092.8237.75203.65582.271.182.002.821.182.002.8264.70176.33546.83TLPNSGA-II4TMA1.002.003.001.002.003.0092.76195.44474.421.002.003.001.002.092.9143.79209.36584.221.002.003.001.002.003.0067.63197.55537.84TLPNSGA-II5TMA1.141.952.911.141.952.9182.01188.60458.881.002.003.001.002.003.0060.04209.06582.731.092.002.911.092.002.9160.21186.78633.06TLPNSGA-II图1的图形显示了每个KNW类别的质粒（a-c）和转座子（c-d）计算代理的成功率458I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449(a) 相关（b）反相关(c) 凹(d) 相关（e）反相关(f)凹图1.一、质粒（a-c）和转座子（d-f）在KNW实例上的成功率通过成功操作的数量除以该转基因试剂进行的操作的总数。平均而言，对于相关和凹的情况，使用m2操作方法的质粒，例如，plm4和plm7对搜索的贡献更大。plm2 也 对 相 关 实 例 做 出 了 重 大 贡 献 。 所 有 质 粒 都 有 助 于 搜 索 反 相 关 类 。newRemTransp和swapTransp的成功率相似，并且是最有效的5结论本文提出了一种用于求解BiST，TMA的转基因算法，该算法处理10个转基因代理。关于选择哪个代理进行搜索的决定I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449459给定解的区域是自动形成的，并且是基于特定试剂的成功应用。TMA与有效的转基因算法进行了比较，其中转基因试剂的选择取决于用户定义的参数和NSGA-II。计算实验包括分为三类的165个基准实例。对每种算法产生的解的分析是基于两个质量指标，这两个质量指标测量近似集和统计检验的不同特征。并对加工时间进行了分析。在这项研究中提出的算法的结果是优越的解决方案的质量和处理时间。在未来的工作中，该算法将被扩展到多目标问题。引用[1] Aggarwal，V.，Y. Aneja和K. Nair，Minimal spanning tree subject to a side constraint，ComputersOperations Research，9（1982），287[2] 阿 罗 约 C. 的 方 法 ， P. S. Vieira 和 D. S. Vianna ， A GRASP algorithm for the multi-criteria minimumspanning tree problem，Annals of Operations Research，159（2008），125[3] Bader，J.，和E.兹兹勒Hype：An algorithm for fast hypervolume-based many-objective optimization，Evolutionary Computation，19（2011），45[4] 巴蒂蒂河，和G.特基奥利反应式禁忌搜索，ORSA Iournal on Computing，6（2）（1994），126-140。[5] 陈，G.，S.陈威Guo和H. Chen，基于多准则最小生成树问题的遗传算法，信息科学，117（2007），5050[6] 科 埃 洛 角 A. 和 M. R. Sierra ， A study of the parallelization of a coevolutionary multi-objectiveevolutionary algorithm ， in ： Mexican International Conference on Arti ficial Intelligence ， Springer2004，688-697.[7] Corley，H. W.，最优化理论与应用期刊，45（1985），481-485[8] 黛布，K.，A.普拉塔普河Agarwal和T. Meyarivan，一种快速和精英多目标遗传算法：NSGA-II，IEEETransactions on Evolutionary Computation，6（2002），182[9] Davis-Moradkhan，M.，和W. N. Browne，A knowledge-based evolution strategy for the multi-objectiveminimum spanning tree problem ， in： IEEE Congress on Evolutionary Computation ， CEC 2006 ，1391- 1398.[10] Ehrgott，M.，和X. Gandibleux，多目标组合优化的调查和注释书目，或Spektrum，22（2000）425[11] Friedman ， M. ， 使 用 秩 来 避 免 方 差 分 析 中 隐 含 的 正 态 性 假 设 ， Journal of the American StatisticalAssociation，32（1937），675[12] Goldbarg ， E. F. G. ， M. C. Goldbarg ， A new endosynbiotic approach for evolutionaryalgorithms，Foundations of Computational Intelligence，3（2009），425[13] Hamacher ， H. W. ， 和 G. Ruhe ， On Spanning Tree Problems with Multiple Objectives ， Annals ofOperations Research，52（1994），209[14]Holm，S.，一个简单的顺序拒绝多重检验程序，斯堪的纳维亚统计杂志6（1979），65[15] Knowles，J.D、“Local-search 英国雷丁大学计算机科学系，雷丁，2002年。[16] Knowles，J.，L. Thiele和E. Zitzler，460I.F.C. Fernandes等人/理论计算机科学电子笔记346（2019）449[17] Kruskal ， J. B. ， 关 于 图 的 最 短 生 成 子 树 和 旅 行 商 问 题 ， Proceedings of the American MathematicalSociety，7（1956），48[18] L'o pez-Ib'anpezez，M.， J. 杜布瓦拉科斯特湖P. C'aceres，M. Birattari和T. Sttzle，Ira cepackage：自动算法配置的迭代竞赛，运筹学展望，2016年3月，43- 58。[19] J. 帕拉加-A'l ava，M. Dorn和M. Inostroza-Pon ta，使用局部算法改进NSGA-II在多标准最小生成树问题中的性能，在：IEEE进化计算大会，CEC 2017，1119-1126。[20] 蒙泰罗山M. D、E. F. G. Goldbarg和M. C. Goldbarg，A new transgenetic approach for the biobjectivespanning tree problem，in：Proceedings of IEEE Congress on Evolutionary Computation，IEEE CEC2010，1，519[21] 普里姆河C.的方法，最短连接网络和一些推广，贝尔系统技术杂志，36（1957），1389[22] 普 列 塞 湖 P. ， F. Guerriero 和 J.L. Santos ， 动 态 规 划 生 成 树 问 题 ： 应 用 于 多 目 标 情 况 优 化 快 报 ， 9（2015），437-450[23] 雷德尔湾R.，和B. A. Julstrom，Edge sets：an effective evolutionary coding of spanning trees，IEEETransactions on Evolutionary Computation，7（2003），225[24] 拉莫斯河M.，S. Alonso，J. Sicilia和C. 张文龙，张文龙，等.最优决策树问题的研究[J].运筹学杂志，1998，11（2）： 117[25] 罗查湾 A. M.， E. F. G. Goldbarg和M. C. Goldbarg，一种模因算法为的双目标最小生成树问题，在：欧洲进化计算会议 在Combinatorial Optimization，EvoCOP 2006，222-233中。[26] 罗查湾A. M.，E. F. G. Goldbarg和M. C. Goldbarg，一种新的双目标最小生成树的进化算法，在：第七届智能系统设计与应用国际会议论文集，ISDA 2007，735[27] Ruzika，S.，和H. W.李国忠，“多目标最小生成树问题的研究”，《大型复杂网络设计、分析与仿真》，北京大学学报，2000年。D.和Zweig，K.一、104[28] Seada，H.，和Deb，K. A unified evolutionary optimization procedure for single，multiple，and manyobjectives，IEEE Transactions on Evolutionary Computation，20（3）（2016），358[29] Sourd ， F. ， 和 O. Spanjaard ， A multiobjective branch-and-bound framework ： Application to thebibodimeter spanning tree problem，INFORMS Journal on Computing，20（2008），472[30] Steiner，S.，和T. Radzik，Computing all efficient solutions of the biobjective minimum spanning treeproblemComputers Operations Research，35（2008），198[31] Zhou，G.和M.陈文，遗传算法在多目标最小生成树问题中的应用，中国科学院学报，1999年，第114期，第141[32] Zitzler，E.和L. Thiele，使用进化算法的多目标优化比较案例研究，在：自然并行问题求解第五届国际会议V 1998，1498，292