如何复现云计算资源分配EMCDA算法？含建模、计算与匹配难点

1. 多属性竞价者建模 #

用类封装客户和提供商的多属性特征，区分两者竞价逻辑差异（客户期望低价格、高服务质量/可靠性；提供商期望高价格、高服务质量/可靠性）：

class Bidder:
    def __init__(self, bid_id, price, quality, reliability):
        self.bid_id = bid_id  # 唯一标识
        self.price = price    # 客户：最高支付价；提供商：最低接受价
        self.quality = quality  # 服务质量评分（如1-10）
        self.reliability = reliability  # 服务可用率（0-1）

class Customer(Bidder):
    # 客户竞价逻辑：倾向更低价格、更高质量/可靠性
    pass

class Provider(Bidder):
    # 提供商竞价逻辑：倾向更高价格、更高质量/可靠性
    pass

实例化示例：

# 创建3个客户
customers = [
    Customer("C1", 50, 8, 0.95),
    Customer("C2", 45, 7, 0.92),
    Customer("C3", 55, 9, 0.98)
]

# 创建3个提供商
providers = [
    Provider("P1", 40, 8, 0.94),
    Provider("P2", 38, 7, 0.90),
    Provider("P3", 42, 9, 0.97)
]

2. 归一化与效用、价格计算 #

由于不同属性量纲差异大，需先做线性归一化，再按权重计算效用。

归一化函数 #

区分正向属性（越高越优：质量、可靠性）和负向属性（越低越优：客户价格）：

def normalize(values, is_positive=True):
    min_v, max_v = min(values), max(values)
    if max_v == min_v:
        return [1.0]*len(values)
    if is_positive:
        return [(x - min_v)/(max_v - min_v) for x in values]
    else:
        return [(max_v - x)/(max_v - min_v) for x in values]

批量归一化属性 #

分别处理客户和提供商的所有属性：

# 客户属性归一化
cust_prices = [c.price for c in customers]
cust_qualities = [c.quality for c in customers]
cust_reliabilities = [c.reliability for c in customers]

norm_cust_price = normalize(cust_prices, is_positive=False)  # 价格负向归一化
norm_cust_quality = normalize(cust_qualities)
norm_cust_reliability = normalize(cust_reliabilities)

# 提供商属性归一化
prov_prices = [p.price for p in providers]
prov_qualities = [p.quality for p in providers]
prov_reliabilities = [p.reliability for p in providers]

norm_prov_price = normalize(prov_prices)  # 价格正向归一化
norm_prov_quality = normalize(prov_qualities)
norm_prov_reliability = normalize(prov_reliabilities)

效用计算 #

按论文设定的权重（示例采用价格0.4、质量0.3、可靠性0.3）计算每个竞价者的效用：

WEIGHTS = {"price": 0.4, "quality": 0.3, "reliability": 0.3}

def calc_cust_utility(i):
    return (WEIGHTS["price"] * norm_cust_price[i] +
            WEIGHTS["quality"] * norm_cust_quality[i] +
            WEIGHTS["reliability"] * norm_cust_reliability[i])

def calc_prov_utility(j):
    return (WEIGHTS["price"] * norm_prov_price[j] +
            WEIGHTS["quality"] * norm_prov_quality[j] +
            WEIGHTS["reliability"] * norm_prov_reliability[j])

# 计算所有客户和提供商的效用
cust_utilities = [calc_cust_utility(i) for i in range(len(customers))]
prov_utilities = [calc_prov_utility(j) for j in range(len(providers))]

成交价格计算 #

参考论文逻辑，成交价格可采用客户最高支付价与提供商最低接受价的折中，结合效用加权：

def calc_deal_price(customer, provider):
    # 示例：取两者价格的均值，可根据论文公式调整
    return (customer.price + provider.price) / 2

3. 匈牙利算法实现最优匹配 #

利用scipy库的linear_sum_assignment实现二分图最优匹配，最大化总匹配效用。

构建效用矩阵 #

矩阵元素为客户i与提供商j匹配的联合效用（示例采用两者效用之和）：

from scipy.optimize import linear_sum_assignment

# 构建联合效用矩阵
utility_matrix = []
for cust_u in cust_utilities:
    row = [cust_u + prov_u for prov_u in prov_utilities]
    utility_matrix.append(row)

# 转化为成本矩阵（因为linear_sum_assignment默认求最小化）
cost_matrix = [[-u for u in row] for row in utility_matrix]

执行匹配 #

# 求解最优匹配
cust_indices, prov_indices = linear_sum_assignment(cost_matrix)

# 输出匹配结果及成交价格
print("最优匹配结果：")
for c_idx, p_idx in zip(cust_indices, prov_indices):
    cust = customers[c_idx]
    prov = providers[p_idx]
    deal_price = calc_deal_price(cust, prov)
    print(f"客户{cust.bid_id} ↔ 提供商{prov.bid_id} | 成交价格: {deal_price:.2f}")

注意事项 #

• 若客户与提供商数量不一致，需添加虚拟节点（效用为0）补全矩阵，避免匹配失败；
• 可根据论文中匹配的约束条件（如资源容量限制）对匹配结果做二次筛选。

参考建议 #

• 严格对照论文中的效用计算、价格调整公式调整代码中的权重和计算逻辑；
• 若需自定义匈牙利算法实现（不依赖scipy），可参考二分图最大权匹配的手动实现逻辑。

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