基于Netlogo平台求解01背包问题的一种改进贪心算法.docx

【摘要】基于0-1背包问题的主要研究主体是多个分别带有不同价值、重量的物品，因此通过复杂适应系统理论的多主体建模方法研究0-1背包问题具有很高的仿真性。与传统贪心算法相比，由于Netlogo平台能够模拟微观个体的行为和宏观模式的集体涌现及其两者之间的联系，因此基于Netlogo平台求解0-1背包问题，则此算法具有真正的并行性、随机性、高度仿真性等特点。并且实验表明，改进后的贪心算法能够得到或接近目前最优的结果。【关键词】贪心算法；0-1背包问题；组合优化问题；Netlogo平台；多主体建模1序言目前，解决0-1背包问题的主要方法有贪心算法、回溯法、分支-界限法、动态规划法等。贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。本文通过Netlogo平台提出了一种改进的贪心算法，此算法既保留了传统算法中贪心算法的局部最优选择策略，又更贴近现实中的实际情况、实现真正的并行、随机性，也避免出现早熟现象，并且实验表明能够取得目前或接近最优结果。本文下面的内容组织如下：第二节为对于0-1背包问题的描述及相关工作；第三节为Netlogo概述；第四节为本文对于改进的贪心算法进行描述、实验、结果分析；第五节为结束语。20-1背包问题的数学模型及相关工作2.10-1背包问题的数学模型假设有n个物品，假定所有物品的重量和价格都是非负的,其重量用wj表示，价格为pj（i=1,2,….,n）。背包所能承受的最大重量为c，按一定的要求从余下物品中选择物品i选入背包时，则定义变量xi=1，否则nnxi=0。现在考虑n个物品的选择与否，则背包内n个物品总重量为?wixi，物件的总价值为?pixi，由变量xi(i=1,2,…,n)的取值来确定物品的组合，实现在不超过背包所能承受的最大重量的时背包内物件总价值最大，其数学模型表示如下:i=1i=1nMaxinize?pixii=1n?wixi≤0i=1Subjectto,式中xi取0或1，i=1,2,…,n,c为正值2.2基于求解0-1背包问题传统贪心算法不足分析众所周知，因为传统贪心算法中最好的贪心选择策略需要提前依次计算所有物品单位重量的价值vi/wi，，但是并不是所有物品都装载在背包里，因此当物品数量巨大时，会耗费大量时间和内存，也由此在现实生活实现的可能性较小；而且此算法也因此没有真正实现随机性、并行性，更极有可能过早出现早熟现象。3Netlogo概述3.1Netlogo简介NetLogo是一个用来对自然和社会现象进行仿真的可编程建模环境。它是由UriWilensky在1999年发起的，由连接学习和计算机建模中心（CCL）负责持续开发。Netlogo的虚拟世界由主体构成，主体能够接收命令、进行活动，所有的主体的行为并行发生，Netlogo中共有三类主体，分别称为turtles(海龟)，patches(瓦片)和obsever(观察者)，turtles是在世界中瓦片上移动的主体，即模型中的Agent；patch则为由二维网格组成的世界；而obsever是一个全局主体，它观察着turtles和patches构成的世界，能够执行指令获取世界全部或部分的状态，或实现对世界的控制。3.2Netlogo特性NetLogo在建模中控制成千上万的个体。因此NetLogo建模能很好地模拟微观个体的行为和宏观模式的涌现及其两者之间的联系。该环境中，大量的可移动主体在二维空间中交互作用，随着时间推荐，微观个体的位置不断发生变化，系统的宏观特征也因此而变化。NetLogo是用于模拟自然和社会现象的编程语言和建模平台，特别适合于模拟随时间发展的复杂系统。真正具有随机性、并行性，符合自然生态规律。Netlogo可视化功能，能够真正观察到物品们的各自和整体移动过程。能让研究者们更好的理解和探寻个体行为和集体涌现之间的关系。4基于Netlogo平台求解0-1背包问题一种改进贪心算法4.1改进贪心算法原理与算法描述本文基于Netlogo平台对贪心算法进行了改进，所有物品同时等概率随机分布在、运动到世界的某一位置，则算法具有并行性、随机性；再将世界分割成同等大小的几部分，依据贪心选择策略将每一部分的中单位重量的价值最高的物品选中，因为每个物品都有可能被选中，则算法具有随机性，之后计算所有选中物品的总重量和价值，与目前最优的进行比较，留下更好的结果，然后重新刷新再开始运行，运行一定次数后，将世界再次分割更小或者更大的同等大小的几部分，再重复之前的操作，这样也避免出现早熟现象。因为不需要提前计算所有的物品的单位单位重量的价值，所以具有高度仿真性。下面是改进后贪心算法基本步骤:NetLogo世界是由静止的“瓦片”构成的二维网格，瓦片是网格中的一个方格。移动主体（海龟）在由静态主体