01背包问题蚁群算法python

以下是使用蚁群算法解决01背包问题的Python代码：

import random

# 蚂蚁数量
ant_count = 50
# 迭代次数
iterations = 200
# 信息素挥发系数
rho = 0.1
# 信息素强度
Q = 1
# 信息素启发因子
alpha = 1
# 距离启发因子
beta = 2
# 最大质量
max_weight = 100
# 物品数量
item_count = 20
# 物品重量
item_weights = [random.randint(1, 10) for _ in range(item_count)]
# 物品价值
item_values = [random.randint(1, 10) for _ in range(item_count)]
# 信息素矩阵
pheromone = [[1.0 for _ in range(max_weight + 1)] for _ in range(item_count)]
# 最优解
best_solution = []
best_value = 0


# 计算每个物品的价值密度
def calculate_density():
    density = []
    for i in range(item_count):
        density.append(item_values[i] / item_weights[i])
    return density


# 计算每个物品被选中的概率
def calculate_probabilities(ant, selected_items, density):
    probabilities = []
    total_prob = 0
    for i in range(item_count):
        if i not in selected_items:
            if ant['current_weight'] + item_weights[i] <= max_weight:
                p = pow(pheromone[i][ant['current_weight'] + item_weights[i]], alpha) * pow(density[i], beta)
                probabilities.append(p)
                total_prob += p
            else:
                probabilities.append(0)
        else:
            probabilities.append(0)
    if total_prob == 0:
        return [1 / (item_count - len(selected_items)) if i not in selected_items else 0 for i in range(item_count)]
    else:
        return [p / total_prob if i not in selected_items else 0 for i, p in enumerate(probabilities)]


# 选择下一个物品
def select_next_item(ant, selected_items, density):
    probabilities = calculate_probabilities(ant, selected_items, density)
    r = random.uniform(0, 1)
    total_prob = 0
    for i, p in enumerate(probabilities):
        total_prob += p
        if total_prob >= r:
            return i
    return -1


# 更新信息素矩阵
def update_pheromone():
    global pheromone
    for i in range(item_count):
        for j in range(max_weight + 1):
            pheromone[i][j] *= (1 - rho)
            for ant in ants:
                if ant['value'] > 0:
                    pheromone[i][j] += (Q / ant['value']) * ant['items'].count(i) * int(j == ant['current_weight'])


# 初始化蚂蚁
def init_ants():
    ants = []
    for i in range(ant_count):
        ant = {'items': [], 'value': 0, 'current_weight': 0}
        ants.append(ant)
    return ants


# 计算蚂蚁的价值和重量
def calculate_ant_value(ant):
    value = 0
    weight = 0
    for i in ant['items']:
        value += item_values[i]
        weight += item_weights[i]
    ant['value'] = value
    ant['current_weight'] = weight


# 蚁群算法主函数
def ant_colony_optimization():
    global best_solution, best_value
    density = calculate_density()
    ants = init_ants()
    for it in range(iterations):
        for ant in ants:
            selected_items = []
            while ant['current_weight'] < max_weight:
                next_item = select_next_item(ant, selected_items, density)
                if next_item == -1:
                    break
                ant['items'].append(next_item)
                selected_items.append(next_item)
                ant['current_weight'] += item_weights[next_item]
            calculate_ant_value(ant)
            if ant['value'] > best_value:
                best_solution = ant['items']
                best_value = ant['value']
        update_pheromone()
    return best_solution, best_value


# 测试
best_solution, best_value = ant_colony_optimization()
print('最优解：', best_solution)
print('最优价值：', best_value)