pso解决01背包问题的python代码
时间: 2024-10-05 10:03:44 浏览: 14
粒子群优化(PSO,Particle Swarm Optimization)是一种模拟鸟群觅食行为的优化算法,用于寻找解空间中的全局最优解。将它应用于01背包问题可以用来找到物品组合使得总重量不超过背包容量的同时价值最大。以下是简单的Python代码示例,展示了如何使用PSO来求解01背包问题:
```python
import numpy as np
# 定义01背包问题的物品数据
items = [(60, 10), (100, 20), (120, 30)] # (weight, value)
capacity = 500 # 背包容量
def fitness(particle): # 计算当前粒子的适应度函数(总价值)
values, weights = zip(*particle)
total_weight, total_value = sum(weights), sum(v * w for v, w in zip(values, weights))
return -total_value if total_weight > capacity else total_value
def update_velocity(particle, best_particle, global_best_particle):
r1, r2 = np.random.rand(2)
velocity = particle['velocity']
position = particle['position']
vel_new = r1 * velocity + r2 * (best_particle['position'] - position) + \
r2 * (global_best_particle['position'] - position)
# 更新位置,保证粒子不会超过物品边界
new_position = [max(0, min(capacity, item[0] + pos)) for pos, item in zip(vel_new, items)]
particle['velocity'], particle['position'] = vel_new, new_position
def optimize(num_particles=50, max_iter=100):
particles = [{'position': np.zeros(len(items)), 'velocity': np.zeros(len(items)),
'fitness': fitness(particles[0]['position'])} for _ in range(num_particles)]
best_particle = max(particles, key=lambda x: x['fitness'])
global_best_particle = {'position': best_particle['position'], 'fitness': best_particle['fitness']}
for _ in range(max_iter):
for particle in particles:
update_velocity(particle, best_particle, global_best_particle)
# 更新最佳个体
particles = sorted(particles, key=lambda x: x['fitness'], reverse=True)
best_particle = particles[0]
if best_particle['fitness'] > global_best_particle['fitness']:
global_best_particle = best_particle
return global_best_particle['position'], global_best_particle['fitness']
solution, max_value = optimize()
print(f"最优物品选择:{solution}, 最大价值:{max_value}")
```