服务代理数组优化搜索算法改进技术咨询

问题背景 #

现有服务代理数量数组array = [4,7,9,10,9,8,8,9,9,9,7,7,6,5]，初始平均服务水平为0.86。目标是逐个减少代理数量，使数组平均服务水平趋近于0.8，且每个位置的代理数需始终高于vector_of_lambdas[i]/rate_of_service阈值。

现有实现代码 #

import numpy as np

# 假设rate_of_service和sum_agents为已定义的全局变量
rate_of_service = 1.0
def sum_agents(agents, new_lambda):
    total = 0.0
    for k in range(agents):
        total += ((new_lambda/rate_of_service)**k)/np.math.factorial(k)
    return total

def optimization_of_agents(list_of_new_agents, vector_of_lambdas):
    search_round = 0
    continue_search = True
    while continue_search:
        index = 0
        service_level_score = 0
        for i in range(len(list_of_new_agents)):
            if list_of_new_agents[i] > vector_of_lambdas[i]/rate_of_service:
                temp_array = list_of_new_agents.copy()
                temp_array[i] = temp_array[i]-1
                temp_service_level = calculate_service_level_optimized_vector(temp_array, vector_of_lambdas)
                if temp_service_level > 0.8 and temp_service_level > service_level_score:
                    service_level_score = temp_service_level
                    index = i
                    print("Search iteration: ", i)
                    print(temp_array)
                    print(service_level_score)
                         
        if service_level_score <= 0.8:
            continue_search = False
        else:    
            list_of_new_agents[index] = list_of_new_agents[index]-1  
            search_round = search_round + 1
            print("\n")
            print("Search After Round: ", search_round)
            print("Improved Vector Of Service Agents: ", list_of_new_agents)
            print("Average Service Level: ", service_level_score)
            print("\n")       

def calculate_service_level(agents, new_lambda):
    N=(((new_lambda/rate_of_service)**agents)/np.math.factorial(agents))
    P=1-(new_lambda/rate_of_service)/agents
    K= sum_agents(agents,new_lambda)
    probability_delay = N / ((P*K)+N)
    service_level = 1-(probability_delay*(np.exp(-(rate_of_service*(agents-(new_lambda/rate_of_service))*0.5))))
    return service_level


def calculate_service_level_optimized_vector(list_of_new_agents, new_vector_lambdas_list):
    service_level_list=[]
    for agents, lambdas in zip(list_of_new_agents, new_vector_lambdas_list):
        new_service_level = calculate_service_level(agents, lambdas)
        service_level_list.append(new_service_level)
    average_array = np.array(service_level_list)
    average = np.mean(average_array)
    return average

现有代码输出 #

Search iteration:  0
[3, 7, 9, 10, 9, 8, 8, 9, 9, 9, 7, 7, 6, 5]
0.8485658691850712
Search iteration:  1
[4, 6, 9, 10, 9, 8, 8, 9, 9, 9, 7, 7, 6, 5]
0.854410495947378
Search iteration:  2
[4, 7, 8, 10, 9, 8, 8, 9, 9, 9, 7, 7, 6, 5]
0.8561148487593274
Search iteration:  3
[4, 7, 9, 9, 9, 8, 8, 9, 9, 9, 7, 7, 6, 5]
0.8568206633443681
Search iteration:  11
[4, 7, 9, 10, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8571998848973724


Search After Round:  1
Improved Vector Of Service Agents:  [4, 7, 9, 10, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
Average Service Level:  0.8571998848973724


Search iteration:  0
[3, 7, 9, 10, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8394202679038497
Search iteration:  1
[4, 6, 9, 10, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8452648946661565
Search iteration:  2
[4, 7, 8, 10, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.846969247478106
Search iteration:  3
[4, 7, 9, 9, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8476750620631467


Search After Round:  2
Improved Vector Of Service Agents:  [4, 7, 9, 9, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
Average Service Level:  0.8476750620631467


Search iteration:  0
[3, 7, 9, 9, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8298954450696241
Search iteration:  1
[4, 6, 9, 9, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8357400718319309
Search iteration:  2
[4, 7, 8, 9, 9, 8, 8, 9, 9, 9, 7, 6, 6, 5]
0.8374444246438804
Search iteration:  8
[4, 7, 9, 9, 9, 8, 8, 9, 8, 9, 7, 6, 6, 5]
0.8375936706851099
Search iteration:  9
[4, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 6, 5]
0.8380728605009203


Search After Round:  3
Improved Vector Of Service Agents:  [4, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 6, 5]
Average Service Level:  0.8380728605009203


Search iteration:  0
[3, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 6, 5]
0.8202932435073976
Search iteration:  1
[4, 6, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 6, 5]
0.8261378702697044
Search iteration:  2
[4, 7, 8, 9, 9, 8, 8, 9, 9, 8, 7, 6, 6, 5]
0.8278422230816539
Search iteration:  8
[4, 7, 9, 9, 9, 8, 8, 9, 8, 8, 7, 6, 6, 5]
0.8279914691228836
Search iteration:  12
[4, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 5, 5]
0.8280279465736201


Search After Round:  4
Improved Vector Of Service Agents:  [4, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 5, 5]
Average Service Level:  0.8280279465736201


Search iteration:  0
[3, 7, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 5, 5]
0.8102483295800973
Search iteration:  1
[4, 6, 9, 9, 9, 8, 8, 9, 9, 8, 7, 6, 5, 5]
0.8160929563424041
Search iteration:  2
[4, 7, 8, 9, 9, 8, 8, 9, 9, 8, 7, 6, 5, 5]
0.8177973091543536
Search iteration:  8
[4, 7, 9, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
0.8179465551955832


Search After Round:  5
Improved Vector Of Service Agents:  [4, 7, 9, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
Average Service Level:  0.8179465551955832


Search iteration:  0
[3, 7, 9, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
0.8001669382020605
Search iteration:  1
[4, 6, 9, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
0.8060115649643675
Search iteration:  2
[4, 7, 8, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
0.807715917776317


Search After Round:  6
Improved Vector Of Service Agents:  [4, 7, 8, 9, 9, 8, 8, 9, 8, 8, 7, 6, 5, 5]
Average Service Level:  0.807715917776317

问题与需求 #

现有算法每次选择调整后平均服务水平仍高于0.8且最优的元素进行减1操作，直至无法满足条件。但该算法存在局限性：当某一元素调整至接近阈值时，平均服务水平触达0.8边界，无法尝试调整数组其他元素。

期望改进算法逻辑：当当前调整路径触达服务水平边界时，回溯至原始数组，从下一个元素开始执行相同的调整优化流程，寻求该需求的Python实现方案。

改进实现方案 #

思路说明 #

采用回溯法遍历所有可能的调整路径，每次尝试调整一个符合阈值要求的元素，递归进行后续调整，直到无法再调整（调整后服务水平≤0.8），记录当前的代理数组和对应的服务水平。最后从所有可行的结果中，筛选出平均服务水平最接近0.8且代理总数最少的方案。

代码实现 #

import numpy as np

# 全局参数，需根据实际场景设置
rate_of_service = 1.0

def sum_agents(agents, new_lambda):
    total = 0.0
    for k in range(agents):
        total += ((new_lambda / rate_of_service)**k) / np.math.factorial(k)
    return total

def calculate_service_level(agents, new_lambda):
    rho = new_lambda / rate_of_service
    if agents <= rho:
        return 0.0  # 避免无效计算
    N = (((new_lambda / rate_of_service)**agents) / np.math.factorial(agents))
    P = 1 - rho / agents
    K = sum_agents(agents, new_lambda)
    probability_delay = N / ((P * K) + N)
    service_level = 1 - (probability_delay * np.exp(-(rate_of_service * (agents - rho) * 0.5)))
    return service_level

def calculate_service_level_optimized_vector(list_of_new_agents, new_vector_lambdas_list):
    service_level_list = []
    for agents, lambdas in zip(list_of_new_agents, new_vector_lambdas_list):
        service_level_list.append(calculate_service_level(agents, lambdas))
    return np.mean(service_level_list)

def backtrack_optimization(current_agents, lambdas, threshold, results):
    # 记录当前可行解
    current_sl = calculate_service_level_optimized_vector(current_agents, lambdas)
    results.append((current_sl, current_agents.copy()))
    
    # 遍历所有可调整的元素
    for i in range(len(current_agents)):
        if current_agents[i] > lambdas[i]/rate_of_service:
            # 尝试减1操作
            new_agents = current_agents.copy()
            new_agents[i] -= 1
            new_sl = calculate_service_level_optimized_vector(new_agents, lambdas)
            # 若服务水平仍达标，继续递归探索
            if new_sl > threshold:
                backtrack_optimization(new_agents, lambdas, threshold, results)

def find_best_solution(original_agents, lambdas, target_sl=0.8):
    results = []
    # 启动回溯搜索
    backtrack_optimization(original_agents, lambdas, target_sl, results)
    
    # 过滤出有效解
    valid_results = [res for res in results if res[0] > target_sl]
    if not valid_results:
        return None, None
    
    # 按服务水平接近0.8、代理总数最少的优先级排序
    valid_results.sort(key=lambda x: (x[0], sum(x[1])))
    
    # 返回最优解
    best_sl, best_agents = valid_results[0]
    return best_agents, best_sl

# 示例调用
if __name__ == "__main__":
    original_array = [4,7,9,10,9,8,8,9,9,9,7,7,6,5]
    # 示例lambda数组，需替换为实际值
    vector_of_lambdas = [3.0, 6.0, 8.0, 9.0, 8.0, 7.0, 7.0, 8.0, 8.0, 8.0, 6.0, 6.0, 5.0, 4.0]
    
    best_agents, best_sl = find_best_solution(original_array, vector_of_lambdas)
    print("最优代理数组:", best_agents)
    print("对应平均服务水平:", best_sl)

代码说明 #

1. 回溯函数：递归遍历所有合法的调整路径，记录每一步的可行解，确保