背包问题:蛇优化算法(Snake Optimizer,SO)求解背包问题(Knapsack Problem,KP)提供Matlab代码

本文主要是介绍背包问题:蛇优化算法(Snake Optimizer,SO)求解背包问题(Knapsack Problem,KP)提供Matlab代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、背包问题

1.1背包问题描述

背包问题(Knapsack Problem,KP)是一种重要的组合优化问题,在生活的许多领域都有着十分广泛的应用。背包问题可以描述为:给定一个背包和n种物品,其中,背包的容量为 V V V ,第i 种物品的质量为 c i c_{i} ci ,价值为 p i p_{i} pi ,如何通过物品选择,使得装入背包中的物品总价值最大。其数学模型如下:
f = max ⁡ ∑ i = 1 n p i x i s.t.  ∑ i = 1 n c i x i ≤ V , i = 1 , 2 , … , n x i = 0 , 1 \begin{array}{ll} & f=\max \sum_{i=1}^{n} p_{i} x_{i} \\ \text { s.t. } & \sum_{i=1}^{n} c_{i} x_{i} \leq V, i=1,2, \ldots, n \\ & x_{i}=0,1 \end{array}  s.t. f=maxi=1npixii=1ncixiV,i=1,2,,nxi=0,1

1.2背包问题测试集

选取9个经典的背包问题测试集,下表中, c c c为物品的质量, p p p为物品的价值, V V V为背包的最大容量。
在这里插入图片描述
参考文献:
[1]耿亚,吴访升.基于粒子群-模拟退火算法的背包问题研究[J].控制工程,2019,26(05):991-996.DOI:10.14107/j.cnki.kzgc.161767.

二、蛇优化算法

蛇优化算法(Snake Optimizer,SO)由Fatma A. Hashim和Abdelazim G. Hussien于2022年提出,该算法思路新颖,快速高效,模拟了蛇的觅食和繁殖行为。

在这里插入图片描述

2.1算法原理

雄性蛇和雌性蛇之间交配的发生受到某些因素的影响。蛇在春末和初夏交配,那时温度低。但交配过程不仅取决于温度,还取决于食物的充足性。如果温带低,食物充足;雄性蛇会互相争斗,以吸引雌性的注意力。雌性有权决定是否交配。如果发生交配,雌性开始在巢穴或洞穴中产卵,一旦卵出现,它就会离开。
在这里插入图片描述

蛇优化算法受蛇交配行为的启发,如果温度低且食物充足,则会发生交配,否则蛇只会寻找食物或吃掉剩余的食物。蛇优化算法分为两个阶段即全局探索或局部开发。探索取决于环境因素,即寒冷的地方和食物,在这种情况下,蛇只在周围寻找食物。对于开发,此阶段包括许多过渡阶段,以使全局更有效率。在食物可用但温度高的情况下,蛇只会专注于吃可用的食物。如果食物可用并且该区域寒冷,则会导致交配过程的发生;交配过程进行战斗模式或交配模式。在战斗模式中,每个雄性都会为获得最好的雌性而战,每个雌性都会尝试选择最好的雄性。在交配模式下,每对配对之间发生交配与食物数量的可用性有关。如果交配过程发生,则雌性产卵并将其孵化成新的蛇。SO将群体分成两个相等的群体即雄性和雌性。

2.1.1全局搜索(无食物)

如果Q<0.25,蛇通过选择任何随机位置来搜索食物,并更新它们的位置。

雄性蛇位置更新:
在这里插入图片描述

雌性蛇位置更新:
在这里插入图片描述

2.1.2局部搜索(有食物)

如果Q>0.25,且温度>0.6,则蛇只会向食物移动:
在这里插入图片描述

如果Q>0.25,且温度<0.6,则蛇将处于战斗模式或交配模式

(1)战斗模式

雄性蛇位置更新:
在这里插入图片描述

雌雄蛇位置更新:
在这里插入图片描述

(2)交配模式

雄性蛇位置更新:

在这里插入图片描述

雌雄蛇位置更新:
在这里插入图片描述

2.2算法流程

在这里插入图片描述

三、蛇优化算法求解背包问题

% 背包问题,共包含9个数据集,修改Function_name即可测试不同数据集
close all
clear 
clc
SearchAgents_no=30; % 种群大小
Function_name='F5'; %F1-F9
Max_iteration=300; % 最大迭代次数
[lb,ub,dim,fobj]=Get_Functions_details(Function_name);%获取数据集信息
[fMin,bestX,DBO_curve]=SO(SearchAgents_no,Max_iteration,lb,ub,dim,fobj);%算法求解
ShowResult;%显示结果

3.1数据集1求解结果

在这里插入图片描述
所求得的背包总价值 : 295
背包的理论最大容量 : 269
所求得的背包的容量 : 269
算法选取的物品序号 : 2 3 4 8 9 10
算法选取的物品质量 : 4 60 32 62 65 46
算法选取的物品价值 : 10 47 5 61 85 87

3.2数据集2求解结果

在这里插入图片描述

所求得的背包总价值 : 481.0694
背包的理论最大容量 : 375
所求得的背包的容量 : 354.9607
算法选取的物品序号 : 3 5 7 8 10 11 12 14 15
算法选取的物品质量 : 47.9873 74.6605 51.3535 1.49846 16.5899 44.5692 0.4669 57.1184 60.7166
算法选取的物品价值 : 58.5009 82.284 71.0501 30.3995 14.7313 98.8525 11.9083 53.1663 60.1764

3.3数据集3求解结果

在这里插入图片描述

所求得的背包总价值 : 1018
背包的理论最大容量 : 878
所求得的背包的容量 : 837
算法选取的物品序号 : 1 2 3 4 5 6 7 9 10 11 12 13 15 17 18 19 20
算法选取的物品质量 : 92 4 43 83 84 68 92 6 44 32 18 56 25 70 48 14 58
算法选取的物品价值 : 44 46 90 72 91 40 75 8 54 78 40 77 61 75 29 75 63

3.4数据集4求解结果

在这里插入图片描述

所求得的背包总价值 : 9767
背包的理论最大容量 : 10000
所求得的背包的容量 : 9768
算法选取的物品序号 : 1 2 3 4 5 6 7 8 10 16 17
算法选取的物品质量 : 983 982 981 980 979 978 488 976 486 969 966
算法选取的物品价值 : 981 980 979 978 977 976 487 974 485 976 974

3.5数据集5求解结果

在这里插入图片描述

所求得的背包总价值 : 3029
背包的理论最大容量 : 1000
所求得的背包的容量 : 1000
算法选取的物品序号 : 1 4 6 7 8 10 11 12 13 14 15 16 17 19 20 22 25 26 27 28 30 35 37 38 40 41 45 49
算法选取的物品质量 : 80 70 70 66 50 25 50 55 40 48 50 32 22 30 32 38 25 28 30 22 30 20 20 25 10 20 10 2
算法选取的物品价值 : 220 192 180 165 162 158 155 130 125 122 120 118 115 105 101 100 95 90 88 82 77 69 65 63 58 56 15 3

3.5数据集6求解结果

在这里插入图片描述

所求得的背包总价值 : 15899
背包的理论最大容量 : 11258
所求得的背包的容量 : 11246
算法选取的物品序号 : 2 3 4 5 8 10 12 13 14 18 19 21 23 25 27 28 30 31 33 34 35 37 38 40 41 43 49
算法选取的物品质量 : 754 699 587 789 347 287 784 676 198 4 355 144 531 741 321 84 483 205 399 747 118 806 9 121 370 494 193
算法选取的物品价值 : 490 651 833 883 337 441 934 467 661 774 595 424 807 501 834 851 459 111 159 858 793 651 856 285 405 391 448

3.7数据集7求解结果

在这里插入图片描述

所求得的背包总价值 : 8327
背包的理论最大容量 : 2400
所求得的背包的容量 : 2398
算法选取的物品序号 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 46 47 49 50 51 53 56 57 59
算法选取的物品质量 : 135 133 130 11 128 123 20 75 9 66 105 43 18 5 37 90 22 85 9 80 70 17 60 35 57 35 61 40 8 50 32 40 72 35 100 2 7 19 28 10 22 27 30 47 68 10 12 43 20 4 3 10
算法选取的物品价值 : 350 310 300 295 290 287 283 280 272 270 265 251 230 220 215 212 207 203 202 200 198 196 190 182 181 175 160 155 154 140 132 125 110 105 101 92 83 77 75 73 72 70 69 58 45 38 36 33 27 19 10 4

3.8数据集8求解结果

在这里插入图片描述
所求得的背包总价值 : 4822
背包的理论最大容量 : 1173
所求得的背包的容量 : 1173
算法选取的物品序号 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 20 22 24 25 26 27 30 31 32 33 36 39 43 45 46 49 50 51 54 62 63 67 68 72 77
算法选取的物品质量 : 40 27 5 21 51 16 42 18 52 28 57 34 44 43 52 53 42 56 44 2 12 9 40 3 39 16 54 5 23 22 10 16 40 1 43 32 2 23 11 35 6 4
算法选取的物品价值 : 199 194 193 191 189 178 174 169 164 164 161 158 157 154 152 149 142 125 124 122 119 116 114 110 109 100 97 82 80 77 74 72 69 68 65 56 36 34 29 29 22 5

3.9数据集9求解结果

在这里插入图片描述

所求得的背包总价值 : 14791
背包的理论最大容量 : 3820
所求得的背包的容量 : 3818
算法选取的物品序号 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 58 59 60 61 62 63 64 65 66 67 68 70 71 74 75 77 78 79 83 87 96 99
算法选取的物品质量 : 54 95 36 18 4 71 83 16 27 84 88 45 94 64 14 80 4 23 75 36 90 20 77 32 58 6 14 86 84 59 71 21 30 22 96 49 81 48 37 28 6 84 19 55 88 38 51 52 79 55 70 53 64 99 61 86 64 32 60 42 45 34 22 49 37 33 1 43 85 32 99 23 8 10 95 6 13 5
算法选取的物品价值 : 297 295 293 292 291 289 284 284 283 283 281 280 279 277 276 275 273 264 260 257 250 236 236 235 235 233 232 232 228 218 217 214 211 208 205 204 203 201 196 194 193 193 192 191 190 187 187 184 184 184 181 179 176 173 172 171 128 123 114 113 107 105 101 100 100 99 98 94 94 80 74 72 63 63 56 48 15 6

四、完整MATLAB代码

这篇关于背包问题:蛇优化算法(Snake Optimizer,SO)求解背包问题(Knapsack Problem,KP)提供Matlab代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/406715

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t