Lille1大学工程科学博士学位论文：GPU上的并行元启发式算法

50 浏览量更新于2023-12-03 收藏 15.15MB PDF 举报

博士学位论文

计算机科学

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

0为获得博士学位而提交的论文0Lille 1大学 - 科学与技术学院0工程科学博士学院，Lille Nord-de-France大学0Lille基础计算机科学实验室（UMR CNRS 8022）0INRIA Lille Nord Europe研究中心0订单号：407050学科：计算机科学0GPU上的并行元启发式算法0作者：Thé Van Luong0评审委员会成员：0评阅人：Pascal Bouvry，卢森堡大学教授0评阅人：Pierre Manneback，比利时蒙斯大学教授0评审人：Didier El Baz，LAAS CNRS Toulouse研究员0主席：Pierre Boulet，Lille 1大学教授0导师：Nouredine Melab，Lille 1大学教授0联合导师：El-Ghazali Talbi，Lille 1大学教授0答辩日期：1/12/20110Thé Van Luong的博士论文，Lille 1，20110© 2011 版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr0Thé Van Luong的博士论文，Lille 1，20110© 2011 版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr0致谢0首先，我要感谢我的导师Nouredine Melab和El-GhazaliTalbi。我要向他们表达我对他们的支持、鼓励和宝贵建议的深深感激，这些支持、鼓励和宝贵建议贯穿了整个博士期间。0我还要向评审委员会的所有成员表示衷心的感谢：主席Pierre Boulet，评阅人PierreManneback和Pascal Bouvry，以及Didier El Baz，本论文的评审人。0我首先要感谢DOLPHIN团队的所有成员，我在这三年的博士期间与他们一起工作非常愉快。特别感谢博士生、工程师和实习生：Marie-Éléonore（化名mon petitboudin），Yacine（化名Yaya），Mathieu（化名petitMathieu），Nadia，Karima，Mostepha，Ahcène，Tuan，Moustapha，Martin，两位Julie，Imen，Sezin，Ines，Clive和FrançoisLegillon。感谢团队的常驻人员：Arnaud，Sébastien，Bilel，Clarisse，Laetitia，François，Luce和Dimo。还要感谢团队的前成员：Mahmoud，Waldo，Mathieu（化名le Breton），Mohand，Jean-Charles Boisson（像饮料一样），RémyChevrier，Feryal，Salma，Emilia，Alexandru，Ali，Jérôme，Gaël，Antonio，Jérémie（感谢SC2），Loukil和MalikaMehdi。还要感谢不同的助理：Malika和Julie Jonas。0此外，我还要向EricTaillard表示衷心的感谢，感谢他在瑞士为我提供了一个温暖的博士后环境。0此外，我还要向尼斯的所有朋友表示深深的感谢，感谢他们对我的友谊的见证：David（化名Dav la frite），Cédric（化名Debeaume），Sarco（或Elium le tombeurd’Idra），Aurélie，Rivière，Stéphane，Christophe，Christopher，Oliv，Guitou，Savino和Julien。我还要向在我生活中分享了一部分生活并在整个论文期间给我带来了某种平衡的不同女性表示敬意：Jo Ferrari，Fleur，Eva，CarolineGastaldi，Hélèna和Isabelle。0最后，我要衷心感谢我的母亲、父亲和两个兄弟Vinh和Phuc，在我整个博士期间以及过去的28年里，他们对我的爱和支持。0Thé Van Luong的博士论文，Lille 1，20110© 2011 版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.friiThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.frContentsIntroduction11GPU Computing for Parallel Metaheuristics51.1Parallel Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.1.1Optimization Context . . . . . . . . . . . . . . . . . . . . . . . . . .61.1.2Principles of Metaheuristics . . . . . . . . . . . . . . . . . . . . . . .71.1.2.1Solution Representation . . . . . . . . . . . . . . . . . . . .71.1.2.2Evaluation Function . . . . . . . . . . . . . . . . . . . . . .81.1.2.3Principles of S-metaheuristics . . . . . . . . . . . . . . . . .81.1.2.4Principles of P-metaheuristics. . . . . . . . . . . . . . . .101.1.3Parallel Models of Metaheuristics . . . . . . . . . . . . . . . . . . . .111.2Metaheuristics and GPU Computing . . . . . . . . . . . . . . . . . . . . . .131.2.1GPU Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.2.2GPU Challenges for Metaheuristics . . . . . . . . . . . . . . . . . . .151.2.3General GPU Model: CPU-GPU Cooperation . . . . . . . . . . . . .161.2.4GPU Threads Model: Parallelism Control . . . . . . . . . . . . . . .161.2.5Kernel Management: Memory Management . . . . . . . . . . . . . .171.3Related Works on Parallel Metaheuristics. . . . . . . . . . . . . . . . . . .201.3.1Metaheuristics on Parallel and Distributed Architectures . . . . . . .201.3.2Research Works on GPU-based Metaheuristics. . . . . . . . . . . .211.4Experimental Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .261.4.1Optimization Problems. . . . . . . . . . . . . . . . . . . . . . . . .261.4.1.1Permuted Perceptron Problem . . . . . . . . . . . . . . . .271.4.1.2The Quadratic Assignment Problem . . . . . . . . . . . . .271.4.1.3The Weierstrass Continuous Function . . . . . . . . . . . .271.4.1.4The Traveling Salesman Problem . . . . . . . . . . . . . . .281.4.1.5The Golomb Rulers . . . . . . . . . . . . . . . . . . . . . .281.4.1.6Problem Characteristics . . . . . . . . . . . . . . . . . . . .291.4.2Machines Conﬁguration . . . . . . . . . . . . . . . . . . . . . . . . .301.4.3Metric and Statistical Tests . . . . . . . . . . . . . . . . . . . . . . .31iiiThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr2Eﬃcient CPU-GPU Cooperation352.1Task Repartition for Metaheuristics on GPU. . . . . . . . . . . . . . . . .372.1.1Model of Parallel Evaluation of Solutions. . . . . . . . . . . . . . .372.1.2Parallelization Scheme on GPU . . . . . . . . . . . . . . . . . . . . .372.2Data Transfer Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . .382.2.1Generation of the Neighborhood in S-metaheuristics . . . . . . . . .392.2.2The Proposed GPU-based Algorithm . . . . . . . . . . . . . . . . . .402.2.3Additional Data Transfer Optimization. . . . . . . . . . . . . . . .422.3Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .432.3.1Analysis of the Data Transfers from CPU to GPU . . . . . . . . . .432.3.2Additional Data Transfer Optimization. . . . . . . . . . . . . . . .492.4Comparison with Other Parallel and Distributed Architectures. . . . . . .502.4.1Parallelization Scheme on Parallel and Distributed Architectures . .522.4.2Conﬁgurations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .522.4.3Cluster of Workstations . . . . . . . . . . . . . . . . . . . . . . . . .542.4.4Workstations in a Grid Organization . . . . . . . . . . . . . . . . . .553Eﬃcient Parallelism Control593.1Thread Control for Metaheuristics on GPU . . . . . . . . . . . . . . . . . .613.1.1Execution Parameters at Runtime. . . . . . . . . . . . . . . . . . .613.1.2Thread Control Heuristic. . . . . . . . . . . . . . . . . . . . . . . .623.2Eﬃcient Mapping of Neighborhood Structures on GPU . . . . . . . . . . . .643.2.1Binary Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . .643.2.2Discrete Vector Representation . . . . . . . . . . . . . . . . . . . . .653.2.3Vector of Real Values. . . . . . . . . . . . . . . . . . . . . . . . . .653.2.4Permutation Representation . . . . . . . . . . . . . . . . . . . . . . .663.2.4.12-exchange Neighborhood . . . . . . . . . . . . . . . . . . .663.2.4.23-exchange Neighborhood . . . . . . . . . . . . . . . . . . .683.2.4.3Mapping Tables for General Neighborhoods . . . . . . . . .693.3First Improvement S-metaheuristics on GPU. . . . . . . . . . . . . . . . .693.4Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .713.4.1Thread Control for Preventing Crashes. . . . . . . . . . . . . . . .713.4.1.1Application to the Traveling Salesman Problem. . . . . .713.4.1.2Thread Control Applied to the Traveling Salesman Problem 733.4.2Thread Control for Further Optimization. . . . . . . . . . . . . . .743.4.3Performance of User-deﬁned Mappings . . . . . . . . . . . . . . . . .743.4.4First Improvement S-metaheuristics on GPU. . . . . . . . . . . . .773.5Large Neighborhoods for Improving Solutions Quality. . . . . . . . . . . .80ivThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr3.5.1Application to the Permuted Perceptron Problem . . . . . . . . . . .813.5.1.1Neighborhood based on a 1-Hamming Distance . . . . . . .813.5.1.2Neighborhood based on a 2-Hamming Distance . . . . . . .823.5.1.3Neighborhood based on a 3-Hamming Distance . . . . . . .823.5.1.4Performance Analysis . . . . . . . . . . . . . . . . . . . . .834Eﬃcient Memory Management874.1Common Concepts of Memory Management . . . . . . . . . . . . . . . . . .894.1.1Memory Coalescing Issues . . . . . . . . . . . . . . . . . . . . . . . .894.1.2Coalescing Transformation. . . . . . . . . . . . . . . . . . . . . . .904.1.3Texture Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . .914.1.4Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . .924.2Memory Management in Cooperative Algorithms . . . . . . . . . . . . . . .944.2.1Parallel and Cooperative Model . . . . . . . . . . . . . . . . . . . . .9404.2.2用于合作算法的并行化策略。04.2.2.1在GPU上并行评估种群。04.2.2.2在GPU上完全分布合作算法。04.2.2.3使用共享内存进行完全分布。04.2.3与完全分布方案相关的问题。04.3性能评估。04.3.1合并对全局内存的访问。04.3.2优化问题的内存关联。04.4合作算法的性能。04.4.1配置。04.4.2效率方面的度量。04.4.3效果方面的度量。05扩展基于GPU的ParadisEO的范围。05.1 ParadisEO框架。05.1.1动机和目标。05.1.2框架的介绍。05.2启用GPU的ParadisEO。05.2.1 ParadisEO-GPU的架构。05.2.2 ParadisEO-GPU组件。05.2.3案例研究：邻域的并行评估。05.2.4映射函数的自动构建。05.3性能评估。05.3.1使用ParadisEO-GPU进行实验。0五0Thèse de Thé Van Luong，Lille 1，20110© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr05.3.1.1应用于排列感知器问题。05.3.1.2应用于二次分配问题。0结论和未来工作1330附录1370.1映射证明。0.1.1二对一索引转换。0.1.2一对二索引转换。0.1.3一对三索引转换。0.1.4三对一索引转换。0.2统计测试。0参考文献1580国际出版物1600六0Thèse de Thé Van Luong，Lille 1，20110© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr10介绍0在优化领域中，学术和工业问题通常都很复杂且难以解决。0NP-hard。实际上，它们的建模在约束方面不断发展。0目标和目标。因此，科学、工程、经济和商业中的大量现实优化问题都是复杂且难以解决的。它们的解决方案0工程、经济和商业中的优化问题都是复杂且难以解决的。它们的解决方案0不能以合理的时间精确执行，它们的资源需求不断增加。为了解决这个问题，解决方案的设计0优化，大规模并行和工程方法。0解决方法必须基于组合优化和大规模并行的先进方法的联合使用0应用于解决优化问题。事实上，这类方法可以产生0在过去几十年中，元启发式方法是一种近似算法，已成功应用于0通常被认为是困难的问题的实例，通过探索通常的大规模解决方案搜索0在合理的时间内找到近似最优解。元启发式方法可以解决问题的实例0搜索空间，并以高效的方式探索该空间。然而，尽管元启发式方法0这些实例的空间。通过减少实际大小来实现这一点0解决大型问题。使用大型问题的实验通常会停止，没有任何0低，以减少问题解决的时间复杂度，但它们仍然不令人满意0在问题实例的大小和计算复杂性之间找到平衡0达到收敛。因此，在设计元启发式方法时，通常存在权衡0大型问题。0探索它。因此，只有使用并行性才能设计新的方法来解决0处理大型问题实例的困难优化问题的设计和实现。0在过去几十年中，并行计算已被证明是处理问题的一种不可避免的方式0已经提出了许多关于并行设计和实现的贡献0并行元启发式方法的实现受到计算平台的强烈影响。0站[CTG95，BSB + 01]，共享内存机器[JRG09，Bev02]。所提出的0使用大规模并行处理器[CSK93]，网络或工作集群0并行评估解决方案和并行（合作或独立）执行多个0这些方法基于三种并行模型：单个解的并行评估，0计算网格[TMT07]。事实上，网格计算是一种令人印象深刻的强大方式0eral元启发式方法。这些并行方法后来被重新评估为大规模0提供大量资源并不容易获得和访问。0解决组合优化中具有挑战性的实例。然而，计算网格0© 2011版权所有。http://doc.univ-lille1.fr0Thèse de Thé Van Luong, Lille 1, 2011Thèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr20介绍0最近，图形处理单元（GPU）已成为新的流行支持0大规模并行计算[RRS + 08，OML + 08]。这些资源提供了巨大的计算能力0计算能力强，能源效率高，并且与网格不同，它们随处可用：0笔记本电脑，台式机，集群等。多年来，GPU计算的使用被认为是0专用于图形和视频应用。最近，它的使用范围已扩展到0其他应用领域[CBM + 08，GLGN + 08]（例如科学计算）得益于0发布了CUDA（计算统一设备架构）开发工具包0允许使用类似C语言的GPU编程[NBGS08]。在某些领域，例如科学计算，由于0merical计算[TSP + 08]，我们现在见证了软件库的大量增加0如CUBLAS用于GPU。然而，在其他领域，如组合优化方面，0特别是元启发式算法，GPU的利用并没有以同样的速度增长。随着0开放标准编程语言在GPU上的到来以及未来0这些语言的编译器，就像其他应用领域一样，组合优化在0GPU将引起越来越多的关注0事实上，GPU计算在近年来已经成为一个重要的挑战，对0并行计算研究领域的重要挑战。这种新兴技术被认为是0加速许多复杂算法非常有用。其中一个主要问题是0元启发式算法是重新思考现有的并行模型和编程范例，以实现0在GPU加速器上部署它们。换句话说，挑战是重新审视0并行模型和范例，以有效地考虑GPU的特性0然而，并行模型的利用并不是一件简单的事情，与之相关的问题很多0必须考虑到该架构的GPU内存层次管理0总的来说，我们需要处理的主要问题是：数据的分布0CPU和GPU之间的处理，线程同步，数据优化0在不同内存之间的传输，内存容量限制等0本论文的贡献是解决这些问题，重新设计并行模型0元启发式算法的模型，以在GPU上解决大规模优化问题0架构。我们的目标是重新思考现有的并行模型，并使其能够0在此目的下，我们在本文中提出了一条新的通用指导方针0用于在GPU上构建高效的并行元启发式算法。我们的挑战是提出0整个并行模型层次结构的基于GPU的设计。不同的贡献0并在本文中处理了一些重要问题：（1）在CPU和GPU之间实现有效的协作0CPU和GPU之间的数据传输进行优化0GPU；（2）有效的并行控制，将工作单元与线程关联起来，以及0以满足内存约束；（3）不同数据结构的有效映射0模型，这些模型利用了GPU提供的不同访问延迟的内存层次结构0GPU；（4）基于软件框架的实现，使GPU对用户来说尽可能透明0Thé Van Luong的博士论文，Lille 1，20110© 2011 版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr30介绍0对用户来说尽可能透明0提出了非常高效的CPU-GPU数据传输优化、线程0控制、将解决方案映射到GPU线程或内存管理。这些方法0已经使用五个优化问题和四个GPU配置进行了详尽的实验0配置。与基于CPU的执行相比，加速比高达×800用于大型组合问题的加速比可达到×2000，用于连续问题的加速比可达到×80。不同0与本论文相关的工作已经在十几个出版物中被接受，包括0IEEE计算机期刊0文档组织0第1章0第一章介绍了并行元启发式算法和GPU计算的一般概念0为此，我们将首先介绍元启发式算法的并行模型。然后，0我们将介绍一般GPU架构，并强调与在GPU上部署元启发式算法相关的不同挑战0处理元启发式算法时会出现一些挑战。本章的其余部分专门讨论0对于全面理解本文所需的定义和协议。0第2章0下一章有助于CPU和GPU之间的高效协作。0因此，我们将强调在两个组件之间优化数据传输的方法0两个组件之间的优化对基于GPU的元启发式算法的性能有重要影响。此外，0广泛的实验证明了基于GPU的元启发式算法的巨大潜力0与集群或网格并行架构相比，基于GPU的元启发式算法具有强大的潜力。0第3章0第三章重点是在设计GPU上的元启发式算法时的高效并行控制0GPU上的元启发式算法。一方面，这一步骤可以建立清晰的关联0根据GPU的空间线程组织来处理要处理的元素。一方面，0另一方面，控制线程的生成将在GPU应用程序中引入一些鲁棒性0GPU应用程序。因此，它可以防止应用程序崩溃，并且可能导致0对性能的一些改进。0第4章0在第四章中，我们将描述优化结构的不同内存关联0处理不同基于GPU的元启发式算法的不同内存关联。作为一个例子，0Thé Van Luong的博士论文，Lille 1，2011年0© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr40引言0本章的目的是重新定义并行和协作算法，其中这种内存管理非常重要0管理方面非常突出。我们将研究如何使用相同的算法进行重新设计0不同的内存关联对全局性能有影响。0第5章0最后一章介绍了ParadisEO框架的扩展，用于透明地0在GPU上部署元启发式算法。为此，我们将介绍概念方面0允许用户编写基于GPU的元启发式算法，同时最小化他或她的0参与其管理。0Thé Van Luong的博士论文，Lille 1，2011年0© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr1.1.3Parallel Models of Metaheuristics . . . . . . . . . . . . . . . . . .111.2Metaheuristics and GPU Computing. . . . . . . . . . . . . . .1350第1章基于GPU的并行元启发式算法0本章首先介绍了理解本文所需的所有背景和先决条件。0全局文档的理解。0首先，我们将描述优化背景下的元启发式算法的原则。0概述了加速搜索的元启发式算法的并行模型。为了实现这个目的，0过程。然后，将在元启发式算法的背景下介绍GPU计算。0我们将介绍与在并行和GPU架构上部署元启发式算法相关的不同优势和挑战0这种新兴技术。此外，对文献中不同作品的回顾0将介绍在并行和GPU架构上部署元启发式算法时所面临的挑战。最后，我们将强调0关于本文中实验所使用的实验方案。0目录01.1 并行元启发式算法 . . . . . . . . . . . . . . . . . . . . . . . . 601.1.1 优化背景 . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 元启发式算法的原则 . . . . . . . . . .. . . . . . . . . . . 701.2.1 GPU架构...13 1.2.2元启发式算法的GPU挑战...151.2.3通用GPU模型：CPU-GPU协作...1601.1.3元启发式算法的并行模型...11 1.2元启发式算法和GPU计算...1301.3并行元启发式算法的相关工作...20 1.3.1并行和分布式架构上的元启发式算法...2001.2.4 GPU线程模型：并行控制...16 1.2.5内核管理：内存管理...1701.4.2机器配置...30 1.4.3度量和统计测试...3101.3.2基于GPU的元启发式算法研究工作...21 1.4实验协议...26 1.4.1优化问题...260© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr60Thèse de Thé Van Luong，Lille 1，20110图1.1：优化问题解决方法的分类法。0第1章：用于并行元启发式算法的GPU计算01.1.1优化背景01.1并行元启发式算法0（单目标优化）或一组成本函数的向量（多目标优化）的成本函数（单目标优化）。0优化问题可以被形式化为优化（最小化或最大化）的优化问题。0在本文中，考虑最小化问题，不失一般性。0（多目标优化）。这个（这些）函数被称为目标函数。0（OP）=0优化问题（OP）可以如下形式化：0s.t. x ∈ S0Min F（x）=（f1（x），f2（x），...，fn（x））0sion变量，S表示与等式和不等式约束相关的可行解集合。0其中n是目标的数量，x =（x1，...，xk）是表示决策变量的向量。0要优化的目标数量。对于n = 1（n≥2），分别是单目标（多目标）优化。0不等式约束和显式边界。F（x）=（f1（x），f2（x），...，fn（x））是向量。0因此，单目标优化问题的解决方案是找到一组帕累托最优解，这被称为帕累托前沿。0可行解，使目标函数最小化。在多目标情况下，考虑多目标优化。0根据问题的复杂性，可以使用两种主要的解决方法家族。确切方法（例如分支和限界法、动态规划或约束编程）可以找到最优解并保证其最优性。然而，对于大问题来说，它们变得不切实际。0帕累托前沿。0Thèse de Thé Van Luong，Lille 1，20110可以使用两种方法：精确方法和启发式方法。图1.1说明了不同的解决方法。0第1章：用于并行元启发式算法的GPU计算0编程）可以找到最优解并保证其最优性。然而，它们对于大问题来说变得不切实际。0变得对于大问题来说不切实际。0相反，启发式算法可以在合理的时间内产生高质量的解决方案，以便在实际应用中使用。0© 2011版权所有。http://doc.univ-lille1.fr0© 2011版权所有。http://doc.univ-lille1.frThèse de Thé Van Luong, Lille 1, 2011© 2011 Tous droits réservés.http://doc.univ-lille1.fr70图1.1：用于优化问题的解决方法的分类法。0大规模问题实例。启发式算法可以是特定的，即设计用于解决特定问题的。0问题和/或实例。它们也可以是通用的，并适用于不同的问题0类型。在这种情况下，它们被称为元启发式方法。后者基于迭代0改进单个解决方案（例如爬山法，模拟退火或禁忌搜索）或一组解决方案0搜索）或一组解决方案（例如进化算法或蚁群算法）的给定0优化问题。在本文档中，重点将仅放在元启发式方法上。01.1.2元启发式原则0与精确方法不同，元启发式方法允许通过0在合理的时间内提供满意的解决方案。无法保证找到全局0最优解或有界解。元启发式方法越来越受到关注和0在过去的20年中越来越受欢迎。它们在许多应用中的使用显示了它们的效率和0解决大型和复杂问题的有效性。元启发式方法分为两类：0基于单个解的元启发式方法（S元启发式方法）和基于群体的元启发式方法0元启发式方法（P元启发式方法）。0S元启发式方法在搜索过程中操作和转换单个解决方案，而在0P元启发式方法演化整个解决方案的群体。这两个家族有0互补的特征：S元启发式方法是以开发为导向的；它们具有0能够加强对局部区域的搜索。P元启发式方法是以探索为导向的；0它们在整个搜索空间中提供了更好的多样性。在本书的后几章中0在本文中，我们主要使用这种分类。01.1.2.1解决方案表示0设计任何迭代元启发式方法都需要对解决方案进行编码（表示）。0编码在任何元启发式方法的效率和有效性中起着重要作用，0因此，它是设计元启发式方法的重要步骤。编码必须是0适合并与手头的优化问题相关的编码。此外，解决方案的质量0表示对应用的搜索算子的效率有很大影响0在这种表示上进行操作。文献中有四种主要编码：二进制0编码（例如背包问题，可满足性），离散值向量（例如位置问题，0分配问题），排列（例如旅行商问题，调度问题）0和实值向量（例如连续函数）。图1.2示例说明了一个0每个表示。0Thèse de Thé Van Luong, Lille 1, 2

下载后可阅读完整内容，剩余1页未读，立即下载