全球校园人工智能算法精英大赛碳中和优化题解析

多策略混合

保留原先的贪心策略主框架，做一些策略抽象。

sort_strategy # 排序策略
choice_strategy # 挑选策略

# task 按 策略 sort_strategy 排序
tasks.sort(key=sort_strategy)

# 遍历每个任务
for task in tasks:
    candidate_list = []
    for server in servers:
        # 如果该服务器，添加该任务后，依旧满足约束
        if server.satisfy(task):
            candidate_list.append(server)
    
    # 如果存在候选服务器列表
    if candidate_list:
        # 按挑选策略，选择具体的 svr
        svr = choice_strategy(candidate_list)
        task -> svr

这里抽象了 2 个策略，sort_strategy / choice_strategy。

任务的排序策略

• 按收益值从高到低 排序
• 按收益/功耗 比值，从高到低 排序
• 按收益/热度 比值，从高到低 排序
• 按收益/(功耗 + 热度) 的比值，从高到低 排序
• 按热度值，从低到高排序

服务器的挑选策略

• FF(First-Fit) 选择第一个满足要求服务器
• BF(Best-Fit) 按最优策略，比如定义 加权 功耗利用率 + 热量利用率的函数，越高越好
• RF(Random-Fit) 随机挑选任一个满足要求的服务器
• 概率放弃 按一定概率放弃此次选择任务和服务器配对，否则采用上述几种策略挑选

而任务的排序策略 + 服务器的挑选策略，做一个组合搭配。 取排序策略 N 种，服务器挑选策略 M 种，做 N*M 的组合，取最优结果为最后的构造解。

如选择排序策略 3 种 * 挑选策略 FF+RF，混合策略效果较好。 这边都是以任务 task 为主导，实际上以服务器 server 为主导，也是类似的效果。

模拟退火

模拟退火也可以做这题，但操作因子设计就很复杂，不太好实现。

这边以最简单的任务重分配操作因子 为例（纯展示）。

import math, random
from math import inf

class Task(object):
    def __init__(self, value, power, heat):
        self.value = value
        self.power = power
        self.heat = heat

class Server(object):
    def __init__(self, p_limit, h_limit):
        self.p_limit = p_limit
        self.h_limit = h_limit

N, M, K = input().split()
N, M, K = int(N), int(M), float(K)
tasks = []
for _ in range(N):
    value, power, heat = list(map(int, input().split()))
    tasks.append(Task(value, power, heat))
servers = []
for _ in range(M):
    p_limit, h_limit = list(map(int, input().split()))
    servers.append(Server(p_limit, h_limit))

def fitness(assigns):
    ans = 0
    tmp_power = [0] * M
    tmp_heat = [0] * M
    for i in range(N):
        id = assigns[i]
        if id >= 0:
            tmp_power[id] += tasks[i].power
            tmp_heat[id] += tasks[i].heat
            ans += tasks[i].value
    # check
    for i in range(M):
        if tmp_power[i] > servers[i].p_limit:
            return -inf
        heat = tmp_heat[i]
        if i > 0:
            heat += tmp_heat[i - 1] * K
        if i + 1 < M:
            heat += tmp_heat[i + 1] * K
        if heat > servers[i].h_limit:
            return -inf
    return ans

assigns = [-1] * N
current_score = 0
best_score = 0
best_ans = assigns[:]
a = 0.999
T = 1000
while T > 1e-6:
    # reassign
    idx = random.randint(0, N - 1)
    old = assigns[idx]
    assigns[idx] = random.randint(-1, M - 1)
    score = fitness(assigns)
    if score == -inf:
        # 不合法的方案立马拒绝
        assigns[idx] = old
        T = T * a
        continue
    delta = score - current_score
    if delta > 0 or random.random() < math.exp(delta / T):
        # accept
        current_score = score
        if current_score > best_score:
            best_score = current_score
            best_ans = assigns[:]
    else:
        # reject
        assigns[idx] = old
    T = T * a
print(*[v + 1 for v in best_ans])

这个大概可以拿 300+ 分。 这个操作因子，效率太低了，间接反映了比赛实际的数据相对较弱，容易得分。 具体更有效率的操作因子，可参考相关 AI 大模型建议。

基准测试数据和打分器拟合

这个数据其实挺难构造的，如何任务和服务器的配对不对，很容易变成没有区分度的 case。

比赛的数据，感觉有些松，使得得分的差异其实并不是那么明显。

实际造的数据，是按任务数/服务器数，[1/20~1/5] 之间配比，任务数量覆盖 [10, 4000]，服务器数覆盖 [2, 800]。

考虑到这题左右侧热量限制，很容易导致 0 分。所以不知道是不是因为这个，主委会给这题特殊的打分机制，即合理解 (全 0 是个特殊的合理解）有一个基础分。

case 设计和基准得分

$$score_i = \begin{cases} \text{结果收益}_i / \text{基准收益}_i \times \text{权重分}_i + \text{基础分}_i, & \text{构造解合理} \ 0, & \text{构造解不合理} \end{cases}$$

最后总分为 $\sum score_i$。

基准测试