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

遗传算法在解装箱问题中的应用 摘要：组合优化是一种离散最优化问题，在规划、调度、资源分配、决策等问题中有着非常广泛的应用，典型的组合优化问题有旅行商问题、加工调度问题、背包问题、装箱问题、图着色问题、类聚问题等。这类问题都有非常精确的数学描述，计算复杂度高，属于NP难类问题。遗传算法通过编码技术，运用繁殖、杂交和突变等遗传算子，对染色体组成的初始种群，进行适应度分析，构成优胜劣汰、适者生存的自然环境，产生出新的更加优良的种群经过若干代的进化，最终求得适合问题的最优解.因此，遗传算法在解决组合优化问题上体现了相当的优越性。 关键词：组合优化；遗传算法1遗传算法的产生与发展 遗传算法就是根据自然界这个“物竞天择，适者生存”现象而提出来的一种随机搜索算法。遗传算法起源于对生物系统所进行的计算机模拟研究。遗传算法最早是由美国密执安大学著名学者J.H.Holland教授在1962年提出的，当时并未受到普遍重视，1975年，Holland教授出版了一本颇有影响的专著--《自然和人工系统的适配》(AdaptationinNaturalandArtificialSystems)，GA这个名称才逐渐为人所知。标志着遗传算法的创立。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论(schematheory)。 进入20世纪80年代，人们越来越清楚地意识到传统人工智能方法的局限性，并且由于计算机速度的提高以及并行机的普及，使进化计算对机器速度的要求不再是制约其发展的因素。遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。各种遗传算法国际会议的顺利召开，以及针对遗传算法研究的主要成果发布，使遗传算法在工程技术和社会生活中成功地解决了许多应用实例问题。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。 2遗传算法概述 遗传算法(GeneticAlgorithm，GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其本质是以汇总高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。 Holland遗传算法又被称为简单遗传算法(SGA)。该算法的操作对象是一群被称为种群的二进制位串（称为染色体、个体）。这里的每个染色体都对应求解问题的一个解。SGA的基本思想是：从初始种群出发，采用基于适应度比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此一代代演化下去，直至满足期望的终止条件为止。该算法的构成要素分为：编码机制，适应度函数，遗传算子和控制参数。遗传算法的主要过程如下： （1）对研究的变量或对象进行编码形成染色体，并随机地建立一个初始群体。 （2）计算群体中诸染色体的适应度。 （3）执行遗传算子操作。包括:繁殖，将适应度高的染色体进行繁殖，添入到群体中，删除适应度低的染色体；杂交，随机选出染色体对，对基因进行片段交叉换位，产生新的染色体对；突变，随机改变某染色体的某个基因，得到新染色体。 （4）根据某种条件判断计算过程是否可以结束，如果不满足结束条件，则返回到步2，直到满足结束条件为止。 3遗传算法实例分析（解装箱问题） 装箱问题也称背包问题，它可以表述为一个单约束的纯整数规划问题。设有一个箱子的总容积为w，另有n个不同的物品，其体积分别w「w2…，wn，其价值分别为P]，P2，…，Pn，问题是在不超过箱子总容积条件下，如何使装入箱子物体的总价值最大。这里w「、？「和w都是正整数，i=1，2，…，n。下面我们通过一个经济活动中常见的实际问题，介绍如何利用遗传算法解决装箱问题，这是遗传算法最简单、最基本的应用模式。 现有100万元资金打算在5个不同的地方修建某种工厂，由于条件不同，所需投资分别为:wj56，w2=20，w3=54，w4=42，w5=15（单位:万元），工厂建成后，每年能得到的利润分别为:Pj7，p2=5，p3=9，p4=6，p5=3（单元:万元）。问如何确定投资地点，使总投资不超过100万元，且使建成后每年所获总利润最多？ 此问题可以看成是一种装箱问题。其中装箱数学模型中的参数分别为:Xj表示在第i个地方是否修建工厂（i=1，2，…，5），w=100，n=5，wj56，w2=20，w3=54，w4=42，w5=15，p=7，p=5，p=9，p=6，p=3，目标函数:maxf（X）=7x+5x+9x+6x+3x，约束条件： 1234512345g（X）=56x+20x+54x+42x+42x+15xW100。编码是应用遗传算法首先要解决的问题，