跳转至

面试问题总结

约 4988 个字 预计阅读时间 17 分钟

工程

  1. 如何验证策略有效性？
    • ABtest

运筹八股

  1. 对偶

    • 对于带约束的最小化问题，不等式约束（小于等于）乘以一个大于0的乘子\(\lambda\)，等式约束乘以一个无符号限制的乘子\(\nu\)，然后把结果加到原目标函数上，得到的一个新的函数称为拉格朗日函数，它是原目标函数的一个下界，要求原问题的最小值，相当于求拉格朗日函数的最大值，故对偶问题是最大化拉格朗日函数（约束是乘子对应的符号限制）.
    • 由于拉格朗日函数是原目标函数的下界可知对偶问题的最优值总是小于等于原问题的最优值，这称为弱对偶性. 如果对偶问题的最优值等于原问题的最优值，这称原问题满足强对偶性.
    • 如果原问题是凸函数，且存在一个解严格可行，那么强对偶性成立.
    • 如果原问题满足强对偶性，在最优解处，对偶变量与原问题约束函数乘积为0，这称为互补松驰性.
    • 对于这个带约束问题的一个可行解\(x^∗\)，如果它是最优解，那么必须满足 KKT 条件（kkt条件包括可行性、梯度关系、互补松弛性和拉格朗日乘子的非负性）. 如果原问题是凸优化问题，那么一个可行解满足kkt条件的话，那么它就是最优解，且此时原问题满足强对偶性.

  2. 线性规划问题

    • 目标函数是线性函数，约束是线性不等式.

  3. 单纯形法

    • 单纯形法的思想就是通过寻找基本可行解来得到最优解.
    • 基本可行解是基本可行解是在线性规划中，满足约束方程（通过选取约束矩阵的基矩阵，令非基变量为 0 求解得到）且所有变量均非负的解， 其几何意义为可行域的顶点，数量有限，若线性规划问题存在可行解，则必定存在基本可行解.
    • 单纯形法的入基和出基操作是为了找到使目标函数更优的基本可行解
    • 对于最大化问题（线性规划的标准型），入基变量选择检验数为正且最大的变量，出基变量通过最小比值法确定.
    • 对于最大化问题，检验数为正且最大的变量，对应的对偶问题的约束被违反得最严重，所以原问题加入对应变量，对应对偶问题就是加入对应约束
    • 影子价格是对偶问题的最优解
    • 对于最大化问题，单纯形法终止的条件为
      1. 基本可行解不存在
      2. 检验数满足最优性条件（所有检验数小于扽与0）
      3. 目标函数无界

  4. 松弛

    • 线性松弛

      • 操作：去掉整数规划中的变量整数约束，转化为线性规划（LP）.
      • 作用：可行域包含原问题可行域，为原问题提供上下界（最大化时是上界，最小化时是下界），是分支定界等算法的基础.

    • 拉格朗日松弛

      • 操作：将复杂约束通过非负乘子 \(\lambda\) 融入目标函数，松弛后求解不含复杂约束的简化问题.
      • 作用：可行域扩大，为原问题提供上下界，且这个界比线性松弛要紧，拉格朗日松弛问题的最优值是原问题最优值的上界，且求解拉格朗日松弛问题通常比原问题更容易.
      • 拉格朗日乘子确定 : 拉格朗日松弛问题的目标函数是有限个线性函数的包络，它几乎处处可微，但是在最优点通常不可微，所以可以次梯度法确定最优乘子.

  5. 混合整数线性规划问题

    • 目标函数和约束都是线性的，但是有一部分变量要求是整数. 求解混合整数线性规划的最优值等价于在可行域的凸包 (\(conv(S)\)) 上求目标函数的最优值.（S是混合整数线性规划的可行域）
    • 混合整数线性规划的可行域的凸包是其线性松弛可行域的凸包和一些有效不等式的交集. 有效不等式是这样一种不等式：它对于问题的所有可行解都成立，并且至少有一个可行解使得该不等式取等号.
    • 分支定界：首先求整数规划的线性松弛问题，如果线性松弛的解是整数解，那么这个解就是最优解；如果这个解是分数解，那么将约束可行域依据这个分数解的上取整值和下取整值划分成两部分（作为约束加入新的线性松弛问题中），然后继续在这两个区域中求解线性松弛问题. 对于其中一部分来说，如果线性松弛的解比划分前的线性松弛解要大，那么就对其继续进行分支定界，否则这一部分被剪枝.
    • 割平面法：本质是构造不断趋于整数规划可行域的凸包的凸多面体. 首先求整数规划的线性松弛问题，如果线性松弛的解是整数解，那么这个解就是最优解；如果这个解是分数解，寻找一个割平面（有效不等式）将这个分数解从线性松弛的可行域中分离，接着继续从新的可行域中求解最优值. 割平面选择方法： Gomory 割平面法
    • 列生成：线性规划的列生成相当于对偶问题的行生成，线性规划含大量变量，此时其对偶问题含大量约束. 我们先取部分约束来求解主问题，如果主问题的解违反了某些约束，就再将这个约束加入主问题，重新求取，循环往复求得最优解，我们通常是将违反最严重的约束加入到主问题，对应于原问题就是把对应检验数最大（对于最大化问题就是最大）的列加入主问题中. 当检验数满足最优性条件（全都小于0），则停止加入.

  6. 目标函数线性化

    • 泰勒展开，max函数转成多个线性约束

  7. 约束线性化

    • 大M法(核心是引入一个足够大的常数 \(M\) 和 0-1 整数变量 \(z\) ，通过构造松弛的线性不等式，将非线性或非凸约束转化为混合整数线性约束)，max转成多个线性约束

  8. VNS

    • 变邻域搜索
    • VNS 是一种元启发式优化算法，旨在通过系统地改变邻域结构来跳出局部最优，探索更广阔的解空间. 其核心逻辑是：不同的邻域结构可能引导搜索到达不同的局部最优解，通过切换邻域结构，可逐步逼近全局最优解
    • 在某个邻域结构找到更优的值后，切换到这个邻域的第一个邻域结构；没找到更优值的话，切换到这个邻域的下一个邻域结构.
    • 关键部分：邻域结构定义，局部搜索策略，邻域切换策略

  9. ALNS

    • 自适应大邻域搜索
    • ALNS是大邻域搜索（Large Neighborhood Search, LNS）的扩展，通过自适应机制动态调整破坏（Destruction）和修复（Repair）策略的权重，提升搜索效率. LNS 的核心是通过 “破坏现有解→修复生成新解” 的过程探索解空间，而 ALNS 进一步引入策略的自适应选择，避免陷入低效策略.
    • 关键部分：破坏算子和修复算子，算子权重调整准则，接受准则

  10. VRP常用邻域算子

机器学习八股

  1. AUC
  2. ROC
  3. L1和L2正则化
  4. 交叉熵
  5. AIC、BIC：选择模型中的信息准则，平衡拟合优度和模型复杂度选择模型，公式有一个拟合项和一个惩罚项.

强化学习和因果推断（问道就说了解一点）

  1. 与运筹学习如何结合？

仓储项目：（原理+为什么用）

  1. 平稳性、纯随机性检验：
    • 平稳性检验是判别一个序列是否为平稳序列，只有是平稳序列才可以输给SARIMA模型. 使用ADF检验进行检验，如果p值小于显著性，则认为序列平稳，
    • 纯随机性检验是判别一个序列是否是纯随机序列，如果是，那么没有必要进行时序预测，代码使用statsmodels库的函数实现
  2. SARIMA
    • SARIMA适合用于处理含季节性趋势的时间序列，代码使用auto-arima实现，auto-arima基于BIC准则进行最优参数选择，用于预测商品未来三十日的需求量.
  3. 熵权法-Topsis
    • 熵权法用于求解指标的权重.
    • Topsis依据熵权法的指标权重，求解每一种商品的评分，构造理想解（最优方案）和负理想解（最劣方案），通过计算各方案与两者的距离，衡量方案的优劣：离理想解越近、离负理想解越远，方案越优.
  4. fp-growth
    • 起因：Apriori算法耗时很久，而且跑下来会爆内存
    • 首先寻找频繁项集
      • fp-growth输入：一个bool值矩阵，行对应订单，列对应商品，如果这个商品在这个订单有出现，则值为True，否则为False和一个支持度阈值，高于这个阈值的项集被视为频繁项集.
      • fp-growth输出：频繁项集及其对应的支持度，支持度的基本定义是项集在订单中出现的频率.
    • 其次进行关联规则挖掘
      • 利用前面得到的频繁项集计算规则的置信度:
        • 输入：所有频繁项集及其支持度。
        • 生成规则：对每个频繁项集 \(L\)，枚举所有非空真子集 \(X\)，得到规则 \(X \rightarrow (L \setminus X)\)。
        • 计算置信度：利用公式 \(\text{Confidence} = \frac{\text{Support}(L)}{\text{Support}(X)}\)。
        • 筛选规则：保留置信度 ≥ 最小置信度阈值的规则。

  5. louvain

    • 起因，fp-growth最终输出是关联规则，即我们知道买了A商品同时又买B商品的置信度是多少，还不是我们需要的商品关联社群
    • Louvain是一种网络社区检测算法，它是一种贪心算法，首先每个节点每个节点自成一个社区，接着遍历每个节点，计算将其移至相邻节点所在社区后模块度的增量，如果增量大于0，则把节点移到社区里. 我们将关联规则抽象成有向边，置信度作为边的权重，然后使用Louvian算法得到商品关联社群.

  6. 目标函数和约束：

    • 目标函数1：热度评分权重乘以每一种商品距离拣货台的曼哈顿距离（各维度坐标差绝对值之和），使用曼哈顿距离是因为货架拣货可行区域有约束，就是只能沿着货架行走，货架一般是垂直x轴或者垂直y轴放置.
    • 目标函数2：商品关联类间各商品的曼哈顿距离之和.
    • 约束：考虑的约束就是货架仓位的体积约束，放置商品的体积之和不能超过仓位的可使用体积.
  7. 问题求解：
    • 使用两个目标函数的加权和作为适应度
    • 编码：使用的数据结构是python的字典，字典的键对应仓位编号，值是对应放置的商品编号和放置的数量.
    • 初始解：使用贪心算法构造初始解，即热度高的商品放在距离拣货台近的仓位.
    • 优化：使用自适应大规模搜索算法，破坏算子只有一个，就是随机从多个仓位拿出多种商品，修复算子有两个，一个是随机重新分配这些商品，另外一个就是打乱商品后，商品分配优先考虑距离拣货台最近的仓位，设置一个随机数对应接受新解标准，有三种标准：无论好坏，接受新解，只接受变好的解，不接受新解. 动态调整算子权重，好的算子权重增加，差的算子权重降低.

VRP项目（原理+为什么用）

  1. 项目流程
    • 起因：受公司客户的运输项目启发，有的客户商品只能用冷冻车运输，有的客户商品只能用常温车运输.
    • vrp问题可以用可行路径来描述目标函数和约束，目标函数是选择的可行路径成本之和，约束是每一个客户只能被一条可行路径访问以及所有可行路径之和小于车辆数目，但是枚举所有可行路径并不可行，所以可以使用列生成算法来求解问题. 列生成算法框架下，首先求解一个受限主问题的线性松弛，受限是指可行路径集有限，接着依据对偶值找出检验数为负且最小对应的可行路径（对于这个多需求的vrp问题，可行路径是指满足容量约束、满足时间窗约束、满足车型商品匹配约束、满足起点和终点都是车库的约束的路径），这是一个资源受限基本最短路问题，这里我们使用cspy库中的双向标签搜索算法求解得到这个新的可行路径，然后把新的可行路径加入到受限主问题，再次求解受限主问题线性松弛问题，松弛问题的解可能会是分数解，这里就使用分支定界算法分别求解两个分支对应的受限主问题获取更优的解，优先选择最接近0.5的变量作为分支点. 算法对于每日100到150单的数据在5分钟内可以得出结果.
  2. labeling算法，双向标签算法
    • 双向标签算法是标签算法的优化版本，标签算法的核心思想是通过为每个节点维护一个 “标签”（Label），记录从起点到达该节点时的状态信息（已经消耗的成本、时间和容量以及前驱节点、已经访问过的节点），并通过扩展规则和支配规则筛选有效路径，避免枚举所有可能路径. 双向标签算法同时从起点和终点出发进行双向搜索，当两个方向的搜索在中间节点或边上 “相遇” 时，合并得到完整路径.
    • 扩展规则：从当前节点的标签出发，遍历所有可行的后续边（如从客户点到下一个客户点或车库），生成到达后续节点的新标签。
    • 支配规则：对同一节点的多个标签，若某标签在所有资源维度和目标函数上均不劣于其他标签，则后者可被删除（称为 “劣势标签”）。

车间调度项目（原理+为什么用）

  1. 工件、工序、机器
  2. MSOS编码
    • MSOS 整数编码将解分为机器选择和工序排序，机器选择部分的基因表示工序在可选机器集的顺序编号，机器选择部分的基因表示工序加工顺序）两部分.
  3. 机器选择均匀交叉
    • 通过随机选取若干位置并交换父代对应基因组成新的子代基因
  4. 工序排序改进POX交叉
    • 先划分工件集，再分别从父代复制对应工件集内的工序顺序、非集内工件顺序从另一父代继承的交叉方法
  5. 机器选择变异
    • 从工序可用的机器中任选一个
  6. 工序排序变异
    • 编码的全排列，选择适应度较好的一个
  7. 外部记忆库策略
    • 外部记忆库用于保护精英个体，搜索初期，采用记忆库与种群个体交叉；迭代后期，采用种群内个体交叉，以此避免早熟陷入局部最优.

时序项目（原理+为什么用）

  1. 缺失值填充策略

    • 起因：数据为2018到2021每隔15分钟的数据，缺失的数据段大多是某一整天的数据.
    • 对原始负荷数据进行 STL 分解，去除残差项，保留周期项和趋势项，生成新序列数据集 B, 从后往前遍历原始数据集 A，遇到缺失值时，利用数据集B中后一天对应时间点的值乘以 0.9~1.1 的随机数填充（利用负荷数据的日相似性，缺失段多为整天数据，后一天数据已存在）。

  2. 异常值修复策略

    • 孤立森林（Isolation Forest）是一种无监督异常检测算法，通过随机分割数据空间来孤立数据点。其核心假设是：异常数据在数据空间中分布稀疏，更容易被快速孤立（即通过更少的分割次数被划分到单独的子空间），而正常数据因分布密集，需要更多次分割才能被孤立.
    • 对检测出的异常点，用其前一个时间点及前 1、2、3 小时相同时刻点的平均值修正.
  3. 滚动预测策略
    • 预测第一个点时，用初始训练集训练 XGBOOST 模型，输入当前点特征得到预测值。将预测值和对应特征并入训练集，更新数据集，训练下一个模型来预测下一个点，依次类推，直至完成所有点预测。

  4. XGBOOST

    • 目标函数：分轮次，对于第t轮迭代，目标函数真实值和上一轮的标签加上本轮训练的基模型的预测值，然后进行二阶泰勒展开.

    • XGBOOST的目标函数由加法训练（逐轮添加新树拟合残差）结合泰勒展开近似与正则化（L1/L2惩罚项）得到. XGBOOST在第\(t\)轮迭代中的目标函数为：

      \[ \begin{align*} \tilde{\mathcal{L}}_t&=\sum_{i = 1}^{n}\left[g^{(i)}f_t(\mathbf{x}^{(i)})+\frac{1}{2}h^{(i)}f_t^2(\mathbf{x}^{(i)})\right]+\gamma T+\frac{1}{2}\lambda\sum_{j = 1}^{T}w_j^2\\ &=\sum_{j = 1}^{T}\left[\left(\sum_{i\in I_j}g^{(i)}\right)w_j + \frac{1}{2}\left(\sum_{i\in I_j}h^{(i)} + \lambda\right)w_j^2\right]+\gamma T \end{align*} \]

    • XGBOOST通过正则化项（限制树复杂度）、收缩（学习率缩放权重）、列子采样（随机选特征）防止过拟合.

    • XGBOOST通过精确贪心（枚举分裂点）、近似算法（加权分位数草图生成候选点）、稀疏感知（缺失值默认缺失方向）决定最优分裂.

    • XGBOOST的并行化体现在列块存储并行统计、缓存预取优化、核外数据分片处理.

    • 为什么使用二阶泰勒展开？

      • 使用二阶泰勒展开可以使保真项是一个二次凸函数，二次凸函数使用牛顿法可以快速求得最优值.
    • XGBOOST比GBDT好在哪里？
      • 二阶信息：利用泰勒二阶展开（梯度 + 海森矩阵），优化更精准，收敛更快。
      • 正则化：显式添加 L1/L2 正则项，控制树复杂度，防过拟合能力更强。
      • 缺失值处理：自动学习缺失值默认方向.