小编Gra*_*per的帖子

我有一个日历，通常是一个包含多行的 csv 文件。每行对应一个个体，是一个连续值“0”和“1”的序列，其中“0”表示空时隙，“1”表示占用时隙。一行中不能有两个分隔的序列（例如，两个由“0”分隔的“1”序列，例如“1,1,1,0,1,1,1,1”）。

问题是通过组合个体并解决时隙之间的冲突来最小化行数。注意时隙不能重叠。例如，对于 4 个个体，我们有以下序列：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,0,0,0,0,0,0

可以将它们排列成两行，同时跟踪排列的个人（记录）。在我们的例子中，它产生：

1,1,1,0,1,0,1,1,1,1 (id1 + id2 + id3)
1,1,1,1,0,0,0,0,0,0 (id4)

约束条件如下：

1. 人数从500到1000不等，
2. 序列的长度永远不会超过30
3. 文件中的每个序列都具有完全相同的长度，
4. 算法需要在执行时间上合理，因为这个任务最多可能重复 200 次。
5. 我们不需要寻找最优解，一个接近最优的解就足够了。
6. 我们需要跟踪组合的个体（如上例所示）

遗传算法似乎是一个不错的选择，但它如何随着这个问题的规模（在执行时间方面）扩展？

Matlab或R 中的建议将（非常）感谢。

这是一个示例测试：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,1,0,0,0,0,0
id5:0,1,1,1,0,0,0,0,0,0
id6:0,0,0,0,0,0,0,1,1,1
id7:0,0,0,0,1,1,1,0,0,0
id8:1,1,1,1,0,0,0,0,0,0
id9:1,1,0,0,0,0,0,0,0,0
id10:0,0,0,0,0,0,1,1,0,0
id11:0,0,0,0,1,0,0,0,0,0
id12:0,1,1,1,0,0,0,0,0,0
id13:0,0,0,1,1,1,0,0,0,0
id14:0,0,0,0,0,0,0,0,0,1
id15:0,0,0,0,1,1,1,1,1,1
id16:1,1,1,1,1,1,1,1,0,0

解决方案

@Nuclearman 提供了一个基于贪婪算法的工作解决方案O(NT)（其中N是个体（id）T的数量，是时隙（列）的数量）。

假设我们只实例化少于 20 个 Blob 类对象，并且考虑到效率（执行时间）和内存管理问题，是否有最佳选择：

• 将随机生成器和生成的分布设置为私有类成员，例如：

  class Blob {
  private:
  std::mt19937 engine;
  std::uniform_real_distribution<double> R_distribution;
  std::binomial_distribution<int> B_distribution;
  }
  

  Run Code Online (Sandbox Code Playgroud)

  并直接在 Blob 方法中使用它们。因此，当我们调用发行版时，我们也会更改作为成员的引擎的状态。

• 或者将随机生成器设置为私有类成员并通过引用方法传递分布？例如：

  class Blob {
  private:
  std::mt19937 engine; //engine
  }
  
  void Blob::run() {
  int blabla = 10;
  std::uniform_real_distribution<double> R_distribution(0, 10);
  do_something(blabla, R_distribution);
  ...
  }
  

  Run Code Online (Sandbox Code Playgroud)

虽然通过引用传递通常会降低开销，但在这种情况下特别重要吗？当多次调用分布（10^9 或更多）时，总体问题如何扩展？

我目前正在为大矩阵（数百万行，列数< 1000）的每个值计算少量，同时独立考虑每一行。

更准确地说，对于该矩阵的每行i、列j中的每个值M ( i , j ) ，其数量就是 [ M ( i , j ) -mean( i , s ) ] / std( i , s ) ，其中s是M ( i ,:) - j中的子集s ， 换句话说，s是行i中没有值j的所有值的子集。

#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <armadillo>
#include <chrono>

using namespace …