遗传算法在解装箱问题中的应用

《遗传算法在解装箱问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法在解装箱问题中的应用摘要：组合优化是一种离散最优化问题，在规划、调度、资源分配、决策等问题屮有着非常广泛的应用，典型的组合优化问题有旅行商问题、加工调度问题、背包问题、装箱问题、图着色问题、类聚问题等。这类问题都有非常精确的数学描述，计算复杂度高，属于NP难类问题。遗传算法通过编码技术，运用繁殖、杂交和突变等遗传算子，对染色体组成的初始种群，进行适应度分析，构成优胜劣汰、适者生存的自然环境，产生出新的更加优良的种群.经过若干代的进化，最终求得适合问题的最优解.因此，遗传算法在解决组合优化问题上体现了相当的优越性。

2、关键词：组合优化；遗传算法1遗传算法的产生与发展遗传算法就是根据自然界这个“物竞天择，适者生存”现象而提出来的一种随机搜索算法。遗传算法起源于对生物系统所进行的计算机模拟研究。遗传算法最早是由美国密执安大学著名学者J.H.Holland教授在1962年提出的,当时并未受到普遍重视,1975年，Holland教授出版了一本颇有影响的专著一《自然和人工系统的适配》(AdaptationinNaturalandArtificialSystems),GA这个名称才逐渐为人所知。标志着遗传算法的创立。Holland在该书中系统地阐

3、述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论(schematheory)o进入20

4、比纪80年代，人们越来越清楚地意识到传统人工智能方法的局限性，并且由于计算机速度的提高以及并行机的普及，使进化计算对机器速度的要求不再是制约其发展的因素。遗传算法迎来了兴盛发展吋期，无论是理论研究还是应用研究都成了十分热门的课题。各种遗传算法国际会议的顺利召开，以及针对遗传算法研究的主要成果发布，使遗传算法在工程技术和社会生活中成功地解决了许多应用实例问题。目前，关于遗传算法研究的热潮仍在持续，越来越

5、多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。2遗传算法概述遗传算法(GeneticAlgorithm,GA)是模拟达尔文生物进化论的口然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟口然进化过程搜索最优解的方法。其本质是以汇总高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并口适应地控制搜索过程以求得最优解。Holland遗传算法又被称为简单遗传算法(SGA)o该算法的操作对彖是一群被称为种群的二进制位串（称为染色体、个体）。这里的每个染色体都对应求解问

6、题的一个解。SGA的基本思想是：从初始种群出发，采用基于适应度比例的选择策略在当前种群屮选择个体，使用杂交和变异来产生下一代种群。如此一代代演化下去，直至满足期望的终止条件为止。该算法的构成要素分为：编码机制，适应度函数，遗传算子和控制参数。遗传算法的主要过程如下：（1）对研究的变量或对彖进行编码形成染色体，并随机地建立一个初始群体。（2）计算群体中诸染色体的适应度。（3）执行遗传算子操作。包括:繁殖，将适应度高的染色体进行繁殖，添入到群体中,删除适应度低的染色体；杂交，随机选出染色体对，对基因进行片段交叉换位，产生新的

7、染色体对；突变，随机改变某染色体的某个基因，得到新染色体。（4）根据某种条件判断计算过程是否可以结束，如杲不满足结束条件，则返回到步2,直到满足结束条件为止。3遗传算法实例分析（解装箱问题）装箱问题也称背包问题，它可以表述为一个单约束的纯整数规划问题。设有一个箱子的总容积为W,另有n个不同的物品，其体积分别W1,W2,…，W”其价值分别为Pl,P2,…,Pn，问题是在不超过箱子总容积条件下，如何使装入箱子物体的总价值最大。这里Wi、P：和W都是正整数，i=l,2,…，no下面我们通过一个经济活动中常见的实际问题，介绍如何

8、利用遗传算法解决装箱问题，这是遗传算法最简单、最基本的应用模式。现有100万元资金打算在5个不同的地方修建某种工厂，由于条件不同，所需投资分别为:wi=56,w2=20,w3=54,w尸42,眺二15（单位:万元）,工厂建成后，每年能得到的利润分别为:PL7,p2=5,P3二9,p4=6,P5=3（单元:万元）。问如何确定投资地点,使总投资不超过100万元，且使建成后每年所获总利润最多？此问题可以看成是一种装箱问题。其中装箱数学模型中的参数分别为:Xi表示在第i个地方是否修建工厂（i=l,2,…，5）,w=100,n=5

9、,wi=56,w2=20,w3=54,w4=42,ws=15,Pi=7,p2=5,p：尸9,p.i=6,ps=3,目标函数：maxf（X）二7xi+5x2+9xs+6x4+3x3,约束条件：g（X）=56x1+20x，+54x3+42x.1+42x.1+15x5<100o编码是应用遗传算法首先要解决的问题，在遗传算法