【调度算法】快速非支配排序算法

这篇具有很好参考价值的文章主要介绍了【调度算法】快速非支配排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这段代码实现的是快速非支配排序算法(Fast Non-dominated Sorting Algorithm)。

算法输入和输出:
这个函数的输入是两个列表 values1values2,分别表示多目标优化问题中每个解在两个目标函数下的取值。输入的两个列表应该具有相同长度,即每个解在两个目标函数下均有取值。

这个函数的输出是一个二维列表 front,其中包含 Pareto 前沿中每层非支配解的索引。具体而言,front[i] 表示第 i 层 Pareto 前沿中非支配解的索引列表。前沿的层数不确定,因此 front 列表中的子列表数量也不确定,需要根据具体的解集确定。每个非支配解只会出现在其中的一个 Pareto 前沿层级中。

举个例子,如果返回结果是 [[1, 4], [0, 3], [2]],表示在多目标优化问题中存在三个 Pareto 前沿层级。其中第一层包含解索引 1 和 4,第二层包含解索引 0 和 3,第三层包含解索引 2。

算法思路:
快速非支配排序算法是一种用于多目标优化问题的非支配解搜索算法。所谓“非支配解”指的是在多个优化目标下,无法找到一个解集中的解,比这个解更好。

具体实现过程:
首先,算法输入两个向量 values1 和 values2,对于其中的每一个解 p,在 values1 和 values2 上进行比较寻找支配解 q,如果 p 被 q 支配,那么就将 p 加入到 q 的被支配集合 S[q] 中。同时记录下 q 被支配的次数,即 n[q],表示有多少个解与 q 相比,更优秀或者等价。如果一个解 p 的 n[p] 为 0,那么它就是一个非支配解,将其放入 Pareto 前沿的第一层 front[0] 中。

接下来,将 front[0] 中的所有非支配解从解集中删除,并将其加入到 Pareto 前沿的列表 front 中。循环处理直到没有解可以放入前沿。

最后,返回计算得到的 Pareto 前沿集合 front,其中的元素是按照被支配的关系排列的。

python代码:

def fast_non_dominated_sort(values1, values2):
    # 初始化 S, front, n 和 rank 列表
    S = [[] for i in range(0, len(values1))]  # 记录每个解的被支配解集合
    front = [[]]  # 记录 Pareto 前沿层级
    n = [0 for i in range(0, len(values1))]  # 记录每个解被支配的次数
    rank = [0 for i in range(0, len(values1))]  # 记录每个解所处的 Pareto 前沿层级

    # 对每个解计算被支配解集合 S 和支配该解的次数 n
    for p in range(0, len(values1)):
        S[p] = []
        n[p] = 0
        for q in range(0, len(values1)):
            if (values1[p] > values1[q] and values2[p] > values2[q]) or (
                    values1[p] >= values1[q] and values2[p] > values2[q]) or (
                    values1[p] > values1[q] and values2[p] >= values2[q]):
                if q not in S[p]:
                    S[p].append(q)
            elif (values1[q] > values1[p] and values2[q] > values2[p]) or (
                    values1[q] >= values1[p] and values2[q] > values2[p]) or (
                    values1[q] > values1[p] and values2[q] >= values2[p]):
                n[p] = n[p] + 1
        # 如果一个解没有被任何其他解支配,则将其归为 Pareto 前沿的第一层
        if n[p] == 0:
            rank[p] = 0
            if p not in front[0]:
                front[0].append(p)

    # 循环计算 Pareto 前沿集合
    i = 0
    while (front[i] != []):
        Q = []
        for p in front[i]:
            # 遍历被支配解集合 S,更新其 n 值
            for q in S[p]:
                n[q] = n[q] - 1
                # 如果某个解 q 不被其他解支配,则将其归为下一层 Pareto 前沿
                if (n[q] == 0):
                    rank[q] = i + 1
                    if q not in Q:
                        Q.append(q)
        i = i + 1
        # 将下一层 Pareto 前沿加入到 front 中
        front.append(Q)

    # 删除最后一个空元素
    del front[len(front) - 1]
    # 返回 Pareto 前沿集合
    return front

用例测试:
假设有以下输入:

values1 = [5, 2, 9, 3, 7, 4]
values2 = [6, 4, 8, 2, 5, 3]

那么根据该测试用例,函数的返回结果应该是:

[[2], [0, 4], [1, 5], [3]]

解释一下返回结果的含义:返回列表中的第一个子列表 [2] 表示 Pareto 前沿的第一层,其中的解索引是 2 。这表示在给定的输入中,解 2 是非支配解且无法被其他解支配。返回列表中的第二个子列表 [0, 4] 表示 Pareto 前沿的第二层,其中的解索引分别是 0 和 4。这表示在给定的输入中,解 2 支配解 0和 4 ,解 0和 4 之间是非支配解。返回列表中的第三个子列表 [1, 5] 表示 Pareto 前沿的第三层,其中的解索引分别是 1 和 5。这表示在给定的输入中,解 0 和解 4 支配解 1和 5 ,解 1 和 5 之间是非支配解。其余类推。文章来源地址https://www.toymoban.com/news/detail-725787.html

到了这里,关于【调度算法】快速非支配排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python算法——快速排序

    快速排序(Quick Sort)是一种高效的分治排序算法,它选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后递归地排序子数组。快速排序通常比冒泡排序和选择排序更高效,特别适用于大型数据集。本文将详细介绍快速排序的工作原理

    2024年02月05日
    浏览(40)
  • python实现快速排序算法

    1. 快速排序 快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行

    2024年02月06日
    浏览(44)
  • 排序算法的巅峰之选:学习Python快速排序!

    快速排序(Quick Sort)是一种高效的排序算法,它的基本思想是通过分治的策略将一个大问题分解成小问题并解决。快速排序的核心操作是选取一个基准元素,将待排序序列划分成左右两部分,其中左部分的元素都小于基准元素,右部分的元素都大于基准元素。然后递归地对左

    2024年02月13日
    浏览(56)
  • python算法 之 快速排序(Quick Sort)

    时间复杂度 名称 示例算法 O(1) 常数时间复杂度 哈希表查找 O(logn) 对数时间复杂度 二分查找 O(n) 线性时间复杂度 遍历数组 O(nlogn) 线性对数时间复杂度 快速排序 O(n^2) 平方时间复杂度 冒泡排序、插入排序 O(n^3) 立方时间复杂度 矩阵乘法 O(2^n) 指数时间复杂度 穷举搜索 O(n!) 阶

    2024年02月04日
    浏览(38)
  • 【排序算法】快速排序的基本算法

            快速排序是应用最广泛的排序算法,流行的原因是它实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点是原地排序,只需要一个很小的辅助栈,且将长度为N的数组排序所需时间和NlgN成正比。另外,快速排序

    2024年01月22日
    浏览(49)
  • 【排序算法】归并排序与快速排序

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 算法训练笔记       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家分享两种排序,一种是

    2024年01月19日
    浏览(37)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(50)
  • 排序算法1:冒泡排序、快速排序、插入排序

    排序算法:交换类排序,插入类排序、选择类排序、归并类排序 交换类排序:冒泡排序、快速排序 一、冒泡排序  时间复杂度:内层是ji,外层是从0到n-1,运行的总次数是1+2+3+4+...+n-1,即O() 空间复杂度:O(1),没有使用额外空间,不会因为n的变化而变化 如果数组本身有序,最

    2024年02月21日
    浏览(42)
  • 【算法】排序——选择排序和交换排序(快速排序)

     ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法头疼记:算法专栏  =========================

    2024年02月08日
    浏览(43)
  • 【算法系列 | 5】深入解析排序算法之——快速排序

    你只管努力,其他交给时间,时间会证明一切。 文章标记颜色说明: 黄色 :重要标题 红色 :用来标记结论 绿色 :用来标记一级论点 蓝色 :用来标记二级论点 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包