用遗传算法求解多维背包问题.pdf

智能所“暑期学校”科研实习告

题目：用遗传算法求解多维背包问题

姓名：吴逊专业：智能科学与技术

指导老师姓名、职务：尚荣华副教授

日期：二零一一年八月

摘要

首先简单介绍了基本的遗传算法。然后将贪婪算法与简单遗传法相结合构成

一种混合遗传算法,用该混合遗传算法求解背包问题。通过对标准测试集中的27

个问题进行测试，发现用这种方法求解大规模背包问题,其解的质量和求解性能

较简单遗传算法和贪婪算法都有所改善。

关键词：遗传算法，多维背包问题

2/22/2

绪论

遗传算法是模拟生物界自然进化过程的一种计算模型，其思想主要来源于达

尔文进化论、孟德尔遗传学说及现代生物学对生命遗传过程的研究。对它的研究

起源于20世纪70年代，由美国Michigan大学的J.Holland教授于1975年正式

提出。GA的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依

赖于梯度信息。尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可

广泛用于组合优化、机器学习、自适应控制等领域。

本文将先就遗传算法介绍其思想来源及基本思路，并提出GA应用的5个关

键点。接着对一类典型的组合优化问题——0-1背包问题分别进行简单遗传算法

混合遗传算法的求解，并将结果与贪婪算法进行对比。

第一章遗传算法概述

2.1达尔文进化论与孟德尔学说

19世纪中叶，达尔文创立了科学的生物进化学说，它第一次对整个生物界的

发生、发展，作出了唯物的、规律性的解释，使生物学发生了一次革命性的变革。

达尔文进化论认为生物不是静止的，而是进化的。物种不断变异，旧物种消

失，新物种产生。而且生物的进化是连续和逐渐，不会发生突变。生物之间存在

一定的亲缘关系，他具有共同的祖先；而另一方面，由于生物过渡繁殖，但是

它的生存空间和食物有限，从而面临生存斗争，包括:种内、种间以及生物

环境的斗争。总结起来为两部分内容：遗传变异自然选择。其中自然选择是达

尔文进化论的核心。

1857年，孟德尔通过对植物进行一系列仔细的实验。揭示了遗传学的两条基

本定律：分离定律和独立分配定律，统称为孟德尔遗传定律。

分离定律是指基因作为独特的独立单位而代代相传。细胞中有成对的基本遗

传单位，在杂交的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本.独立分

配定律则指出在一对染色体上的基因对中的等位基因能够独立遗传。

孟德尔的这两条遗传基本定律就是新遗传学的起点，孟德尔也因此被后人称

为现代遗传学的奠基人。

将达尔文进化论和孟德尔-摩根基因相结合，成为现被广泛接受的新达尔文主

2/22/2

义。

新达尔文主义认为，只用种群上和物种内的少量统计过程就可以充分地解释

大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共

同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有

限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。

2.2生物学中的遗传概念

在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。

染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同

的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基

因），即可改变人体的身高。

细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了

上一代细胞的基因。有性生殖生物在繁殖下一代时，两个同元染色体之间通过交

叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交

叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，

从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后

代）的新的性状。

在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适

应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机

会相对较少，即所谓自然选择。而生存下来的