基于双准则的K候选解筛选算法优化：求线性复杂度方案

背景 #

本场景针对优化算法（如差分进化）的初始化阶段，需要生成代表解参数的随机向量种群。我们正在设计比随机初始化更优的新方法，最终要从M个候选解中筛选出N个（通常M超过100，N取30）。

核心需求 #

筛选出的N个解需同时满足两个准则：

• 最大化解间距离
• 整体适应度表现更优（本算法中适应度值越低，解的性能越好）

当前方案及问题 #

当前采用全组合枚举法：生成所有N个解的组合，计算每个组合的总距离与总适应度，绘制帕累托前沿后从中选取解。但该方法在种群规模较大时运行速度极慢。

代码实现 #

import math
import itertools
import numpy as np
import matplotlib.pyplot as plt

from paretoset import paretoset


def distance_matrix(a):
    b = a.reshape(a.shape[0], 1, a.shape[1])
    dist = np.sqrt(np.einsum('ijk, ijk->ij', a-b, a-b))
    return dist

samples = np.random.random([10, 2])*10.0
fitness = [math.dist(p, [0,0]) for p in samples]
n_pop = 3

for s,f in zip(samples, fitness):
    print(f'{s}({f})')

# 筛选最优n_pop个分散点的附加代码
# 计算距离矩阵
dist = distance_matrix(samples)
print(f'{dist})')

# 计算所有组合的总距离与总适应度
aggregated_distances = []
aggregated_fitness = []
solutions = []
combs = itertools.combinations(range(len(samples)), n_pop)
print('main loop')
for c in combs:
    # 存储当前组合
    solutions.append(c)
    # 计算组合总距离
    agg_dist = 0.0
    for i in c:
        for j in c:
            agg_dist += dist[i][j]
    aggregated_distances.append(agg_dist)
    # 计算组合总适应度
    agg_fit = 0.0
    for s in c:
        agg_fit += fitness[s]
    aggregated_fitness.append(agg_fit)

aggregated_distances = np.array(aggregated_distances)
aggregated_fitness = np.array(aggregated_fitness)
solutions = np.array(solutions)

plt.plot(aggregated_distances, aggregated_fitness, 'o')

for s,d,f in zip(solutions, aggregated_distances, aggregated_fitness):
    print(f'{s} {d} {f})')

# 计算帕累托最优解
objective_values_array = np.vstack([aggregated_distances, aggregated_fitness]).T
print(f'{objective_values_array.shape}')
mask = paretoset(objective_values_array, sense=['max', 'min'])
print(f'{mask}')
print(solutions[mask])
plt.plot(aggregated_distances[mask], aggregated_fitness[mask], 'o')
plt.show()

问询 #

是否存在更优的实现方法？理想为线性复杂度方案，线性规划是否可作为解决方案？

内容的提问来源于stack exchange，提问作者mariolpantunes