MATLAB:找到最小化矩阵元素总和的矩阵的缩写版本

Question

我有一个 151-by-151 矩阵 A。它是一个相关矩阵，因此主对角线上有 1，主对角线上下有重复值。每行/每列代表一个人。

对于给定的整数n，我会通过将人踢出去来减小矩阵的大小，这样我就得到了一个n-by-n相关性最小化元素总和的矩阵。除了获得缩略矩阵之外，我还需要知道应该从原始矩阵中引导出的人的行号(或他们的列号 - 他们将是相同的数字)。

作为起点，我采用 A = tril(A)，它将从相关矩阵中删除多余的非对角线元素。

所以，如果 n = 4 并且我们有上面假设的 5-by-5 矩阵，很明显第 5 个人应该被踢出矩阵，因为那个人贡献了很多非常高的相关性。

同样清楚的是，第 1 个人不应该被踢出，因为这个人贡献了很多负相关，从而降低了矩阵元素的总和。

我知道 sum(A(:)) 会对矩阵中的所有内容求和。但是，我不清楚如何搜索最小可能答案。

我注意到一个类似的问题 Finding sub-matrix with minimum elementwise sum ，它有一个蛮力解决方案作为公认的答案。虽然这个答案工作正常，但它对于 151-by-151 矩阵是不切实际的。

编辑: 我曾考虑过迭代，但我认为这并不能真正最小化缩减矩阵中的元素总和。下面我有一个粗体的 4-by-4 相关矩阵，边上有行和列的总和。很明显，n = 2 时，最佳矩阵是 2-by-2 单位矩阵，其中涉及人员 1 和 4，但根据迭代方案 我会在迭代的第一阶段踢出 Person 1，因此该算法会得出一个不是最优的解决方案。我写了一个总是生成最优解的程序，当 n 或 k 很小时它运行良好，但是当试图从151-by-151 矩阵我意识到我的程序需要数十亿年才能终止。

我依稀记得有时这些 n choose k 问题可以通过避免重新计算的动态规划方法来解决，但我不知道如何解决这个问题，谷歌搜索也没有启发我.

如果没有其他选择，我愿意牺牲精度来换取速度，否则最好的程序需要一周以上的时间才能生成精确的解决方案。但是，如果程序能够生成精确的解决方案，我很乐意让程序运行长达一周。

如果程序不可能在合理的时间范围内优化矩阵，那么我会接受一个解释为什么n 选择 k 这种特定类型的任务无法在合理的时间内解决的答案时间表。

Answer 1

这是使用遗传算法的近似解。

我从你的测试用例开始:

data_points = 10; % How many data points will be generated for each person, in order to create the correlation matrix.
num_people = 25; % Number of people initially.
to_keep = 13; % Number of people to be kept in the correlation matrix.
to_drop = num_people - to_keep; % Number of people to drop from the correlation matrix.
num_comparisons = 100; % Number of times to compare the iterative and optimization techniques.
for j = 1:data_points
    rand_dat(j,:) = 1 + 2.*randn(num_people,1); % Generate random data.
end
A = corr(rand_dat);

然后我定义了进化遗传算法所需的函数:

function individuals = user1205901individuals(nvars, FitnessFcn, gaoptions, num_people)

individuals = zeros(num_people,gaoptions.PopulationSize);
for cnt=1:gaoptions.PopulationSize
    individuals(:,cnt)=randperm(num_people);
end

individuals = individuals(1:nvars,:)';

是个体生成函数。

function fitness = user1205901fitness(ind, A)

fitness = sum(sum(A(ind,ind)));

是适应度评价函数

function offspring = user1205901mutations(parents, options, nvars, FitnessFcn, state, thisScore, thisPopulation, num_people)

offspring=zeros(length(parents),nvars);
for cnt=1:length(parents)
    original = thisPopulation(parents(cnt),:);
    extraneus = setdiff(1:num_people, original);
    original(fix(rand()*nvars)+1) = extraneus(fix(rand()*(num_people-nvars))+1);
    offspring(cnt,:)=original;
end

是变异个体的函数

function children = user1205901crossover(parents, options, nvars, FitnessFcn, unused, thisPopulation)

children=zeros(length(parents)/2,nvars);
cnt = 1;
for cnt1=1:2:length(parents)
    cnt2=cnt1+1;
        male = thisPopulation(parents(cnt1),:);
        female = thisPopulation(parents(cnt2),:);
        child = union(male, female);
        child = child(randperm(length(child)));
        child = child(1:nvars);
        children(cnt,:)=child;
        cnt = cnt + 1;

end

是产生一个新个体耦合两个 parent 的功能。

此时您可以定义您的问题:

gaproblem2.fitnessfcn=@(idx)user1205901fitness(idx,A)
gaproblem2.nvars = to_keep
gaproblem2.options = gaoptions()
gaproblem2.options.PopulationSize=40
gaproblem2.options.EliteCount=10
gaproblem2.options.CrossoverFraction=0.1
gaproblem2.options.StallGenLimit=inf
gaproblem2.options.CreationFcn= @(nvars,FitnessFcn,gaoptions)user1205901individuals(nvars,FitnessFcn,gaoptions,num_people)
gaproblem2.options.CrossoverFcn= @(parents,options,nvars,FitnessFcn,unused,thisPopulation)user1205901crossover(parents,options,nvars,FitnessFcn,unused,thisPopulation)
gaproblem2.options.MutationFcn=@(parents, options, nvars, FitnessFcn, state, thisScore, thisPopulation) user1205901mutations(parents, options, nvars, FitnessFcn, state, thisScore, thisPopulation, num_people)
gaproblem2.options.Vectorized='off'

打开遗传算法工具

gatool

从 File 菜单中选择 Import Problem... 并在打开的窗口中选择 gaproblem2。

现在，运行该工具并等待迭代停止。

gatool 使您能够更改数百个参数，因此您可以在所选输出中以速度换取精度。

生成的向量是您必须保留在原始矩阵中的索引列表，因此 A(garesults.x,garesults.x) 是仅包含所需人员的矩阵。