首页 > 编程语言 >基于微粒群算法的0-1背包问题求解

基于微粒群算法的0-1背包问题求解

时间:2022-09-30 20:12:09浏览次数:48  
标签:Dim 背包 random 算法 适应度 xSize xbest np 微粒

import random
import math
import matplotlib.pyplot as plt
import numpy as np
import time
def init(b_=700,xSize_=200,iteration_=1000,c1_=0.5,c2_=0.5,w_=0.8):
    global a,c,b,Dim,xSize,iteration,c1,c2,w,A,C,x,v,xbest,fxbest,gbest,fgbest
    '''
    a = []
    b = []
    for i in range(100):
        a.append(random.randint(1,99))
        b.append(random.randint(1,99))
    #自定义初始数据    
    '''
    a = [90, 33, 94, 69, 77, 91, 39, 74, 24, 34, 14, 89, 98, 37, 32, 45, 15, 98, 40, 16, 17, 4, 3, 5, 94, 3, 64, 47, 85, 9, 6, 39, 44, 67, 33, 59, 17, 16, 55, 95, 69, 88, 91, 28, 66, 54, 85, 82, 24, 17, 30, 66, 96, 8, 74, 20, 84, 35, 53, 19, 25, 64, 98, 93, 86, 24, 30, 68, 56, 37, 6, 98, 48, 76, 61, 9, 29, 76, 55, 41, 93, 19, 56, 85, 20, 84, 12, 64, 94, 29, 26, 93, 83, 72, 76, 86, 4, 99, 29, 4]
    c = [68, 20, 125, 85, 113, 109, 19, 93, 17, 19, 18, 79, 92, 39, 45, 50, 12, 77, 53, 16, 8, 2, 2, 7, 47, 4, 67, 9, 62, 6, 8, 51, 61, 93, 33, 35, 14, 15, 34, 136, 87, 72, 121, 28, 84, 54, 110, 44, 15, 23, 36, 95, 77, 11, 74, 14, 75, 50, 63, 26, 34, 56, 67, 77, 73, 34, 41, 59, 84, 44, 7, 112, 70, 65, 54, 6, 20, 92, 56, 21, 125, 24, 83, 113, 14, 99, 18, 49, 70, 15, 34, 88, 105, 48, 61, 128, 3, 110, 19, 4] 
    b = b_  #背包容量
    #初始化种群
    Dim = len(a)           #维度
    xSize = xSize_         #种群数
    iteration = iteration_        #迭代次数
    c1 = c1_
    c2 = c2_           #加速因子
    w = w_            #定义惯性因子 
    A = np.array([a]*xSize)                #将a扩展成种群数*维度的矩阵  
    C = np.array([c]*xSize)                #将c扩展为种群数*维度的矩阵
    x = np.random.randint(0,2,(xSize,Dim)) #随机生成一个种群数*维度的矩阵
    v = np.random.rand(xSize,Dim)          #随机生成一个种群数*维度的速度矩阵
    xbest = np.zeros((xSize,Dim))            #单个粒子的初始最佳位置
    fxbest = np.zeros((xSize,1))             #xbest的适应度
    gbest = np.zeros((1,Dim))                #全局最优解
    fgbest = 0                             #全局最优解的适应度        

def solve():   
    #寻找粒子群最优位置和单个粒子
    global x,fgbest,v
    fx = np.sum(np.multiply(C,x), axis=1) # 粒子适应度,即背包内物品的价格
    sx = np.sum(np.multiply(A,x), axis=1) # 限制函数,即背包内物品的体积
    #print(sx)
    for i in range(xSize):
        if list(sx)[i] > b:
            fx[i] = 0
    for i in range(xSize):
        if fxbest[i] < fx[i]:   # 如果当前粒子适应度大于最佳适应度,替代最佳适应度fxbest,替代最佳粒子xbest
            fxbest[i] = fx[i]
            xbest[i] = x[i] # 替换矩阵第i行
    if fgbest <= max(fxbest):
        fgbest = max(fxbest)
        g = list(fxbest).index(fgbest)
        gbest = xbest[g]     #当存在粒子的最佳适应度fxbext(i)大于种群最佳适应度fgbext(i)时,替代
    for i in range(xSize):
        if (x[i]==gbest).all():
            x[i] = np.random.randint(0,2,(1,Dim)) #随机生成一个种群数*维度的矩阵
    R1 = np.random.rand(xSize,Dim) 
    R2 = np.random.rand(xSize,Dim) # xSize行Dim列的0~1随机矩阵

    '''速度v和位置x的迭代公式'''
    v = v * w  + c1 * np.multiply(R1,xbest-x) + c2 * np.multiply(2,(np.array([gbest]*xSize)-x))
    x = x + v
    
    for i in range(xSize):   #更新粒子群的位置
        for j in range(Dim):
            if x[i][j] < 0.5: # 粒子的位置只有(0,1)两种状态R
                x[i][j] = 0
            else:
                x[i][j] = 1   

if __name__ == "__main__":
    k = 0 # 功能选项
    if(k==1):
        '''在不同种群规模下的算法性能表现'''
        tmp = []
        y = []
        for scale in range(50,200,20):
            tmp.append(scale)
            print(scale)
            init(xSize_=scale,iteration_=1500)
            for i in range(iteration):
                solve()
            y.append(fgbest[0])
        plt.plot(tmp,y)
        plt.xlabel('population scale')
        plt.ylabel('value')
        plt.title('the effect of population scale')
    elif(k==2):
        '''在不同惯性因子下的算法性能表现'''
        tmp = []
        y = []
        for w in range(4,9):
            w = w / 10
            tmp.append(w)
            print(w)
            init(w_=w,iteration_=1500)
            for i in range(iteration):
                solve()
            y.append(fgbest[0])
        plt.plot(tmp,y)
        plt.xlabel('inertia factor')
        plt.ylabel('value')
        plt.title('the effect of inertia factor')
    elif(k==3):
        '''在不同加速因子下的算法性能表现'''
        tmp = []
        y = []
        for c in range(1,20,2):
            c = c / 10
            tmp.append(c)
            print(c)
            init(c1_=c,c2_=c,iteration_=1500)
            for i in range(iteration):
                solve()
            y.append(fgbest[0])
        plt.plot(tmp,y)
        plt.xlabel('acceleration factor')
        plt.ylabel('value')
        plt.title('the effect of acceletation factor')
    elif(k==4):
        '''在不同背包容量下的算法最佳迭代次数'''
        tmp = []
        y = []
        for capacity in range(500,3501,500):
            tmp.append(capacity)
            best = []
            print(capacity)
            init(b_=capacity,iteration_=5000)
            for i in range(iteration):
                solve()
                best.append(fgbest[0])
            print(best)
            for i in range(len(best)):
                if(best[len(best)-i-1] != best[len(best)-i-2]):
                    print(4)
                    y.append(len(best)-i)
                    break
            
        plt.xlabel('capacity')
        plt.ylabel('epochs')
        plt.plot(tmp,y)
    elif(k==5):
        '''禁忌搜索算法与微粒群算法的性能比较'''
        from TSA import TSA_bag
        i = 500
        tmp = [x for x in range(i)]
        pso = []
        init(iteration_=i)
        for i in range(iteration):
            solve()
            pso.append(fgbest[0])
        plt.plot(tmp,pso,color='red',label='PSO')
        plt.plot(tmp,TSA_bag(interation=i),color='blue',label='TSA')
        plt.xlabel('interation')
        plt.ylabel('value')
        plt.title('the comparison between PSA and TSA')
    elif(k==6):
        '''在不同背包容量下,禁忌搜索算法与微粒群算法的性能比较'''
        #import TSA
        tmp = []
        pso = []
        tsa = []
        for i in range(500,3501,250):
            import TSA
            TSA_tmp = TSA.main(capacity_=i,interation=300)
            tmp.append(i)
            print(i)
            init(b_=i,iteration_=1000)
            for i in range(iteration):
                solve()
            pso.append(fgbest[0])
            tsa.append(TSA_tmp)
        plt.plot(tmp,pso,color='red',label='PSO')
        plt.plot(tmp,tsa,color='blue',label='TSA')
        plt.xlabel('capacity')
        plt.ylabel('value')
        plt.title('the comparison between PSA and TSA')
    
    plt.legend()
    plt.show()
    '''有参考MATLAB代码。自己仿照写了整个python程序、6个探究、并且增加了惯性权重、删除了Vmax等变量限制。'''

标签:Dim,背包,random,算法,适应度,xSize,xbest,np,微粒
From: https://www.cnblogs.com/chengjunkai/p/16745979.html

相关文章

  • Raft 共识算法
    转载请注明出处:https://www.cnblogs.com/morningli/p/16745294.htmlraft是一种管理复制日志的算法,raft可以分解成三个相对独立的子问题:选主(Leaderelection):原有的lead......
  • 通关基本算法 day_10 -- 区间合并
    区间合并给我们很多很多区间,这两个区间有交集,我们合并成一个区间例如[1,9]和[3,13]可以合并为[1,13]原理按所有区间的左端点排序扫描整个区间,把所有可能有交点......
  • 求100以内的素数,简单算法
    算法思路:将1-100的数进行标识,从2开始求其2倍,则该数为合数,将标识置1;则依次向后进行,最后标识为0的数,即为素数。constintn=100;intisprim[n+1]={0};//每位数......
  • 【CV算法理解】SORT(Simple Online and Realtime Tracking)跟踪算法理解
      SORT 是一种简单的在线实时多目标跟踪算法。文章要点为:以IoU作为前后帧间目标关系度量指标;利用卡尔曼滤波器预测当前位置;通过匈牙利算法关联检测框到目标;应......
  • 【ML算法基础】马氏距离
       直观解释(x−μ)(\bold{x}-\bold{\mu})(x−μ)本质上是向量与平均值的距离。然后,将其除以协方差矩阵(或乘以协方差矩阵的逆数)。这实际上是多元变量的常规标......
  • 【CV算法基础】直方图的定义与扩展
    前言直方图、直方图归一化、直方图均衡化,使用情况,优缺点;图像增强;全局、局部增强;直方图离散函数,图像中每个灰度级的像素个数;归一化直方图图像中每个灰度级发生的概率估......
  • Windows Server 服务器漏洞:OpenSSL 信息泄露漏洞(CVE-2016-2183)和 OpenSSL弱加密算法
    一、更新openssl版本这个漏洞我目前了解到是直接使用系统自带版本,版本过低引起的弱加密信息泄露,直接更新。更新会同时把标题两个漏洞都补上先下载一波安装包: http://sl......
  • 字节笔试算法题
    题目1给定一个字符串,进行以下操作:三个同样的字母连在一起,去掉一个:比如helllo->hello两对一样的字母(AABB型)连在一起,去掉第二对的一个字母:比如helloo->hello上面......
  • AM5728 Opencl 案例汇总:实现sobel算法,计算向量和,矩阵转置
    案例一:实现sobel算法OpenCV(Open Source Computer Vision Library)是一个基于BSD许可开源发行的跨平台计算机视觉库。实现图像处理和计算机视觉方面的很多通用计算。......
  • 算法判断矩形和圆形相交 OBB & Circle
        转自:https://www.zhihu.com/question/24251545......