求解装箱问题的一种变长度染色体遗传算法(2)

54长春工程学院学报(自然科学版)2004,5(2)

C———箱子的重量限制,k是常数(k>0)表

示对装满箱子的重视程度,k越大,装

得满的箱子比一般填充的箱子受到的重视就越大,这里取k=2。

2.2　染色体编码设计

在遗传算法中如何描述问题的可行解,即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转化方法,就称为编码。

由于装箱问题的适应值函数依赖于箱子中物体的群体,因此此问题中好的编码应该包含2个部分:一部分提供关于哪个物品属于哪个箱子(群体)的信息,另一部分对使用的箱子编码。

基于此考虑,中各基因座位置(表示箱子)(的物品),排列起来,。

举例说,6对物品进行编码,染色体物品部分可写成142352,这表示:第1个物品放入箱子1,第2个物品放入箱子4,第3个和第6个物品放入箱子2,第4个物品放入箱子3,第5个物品放入箱子5;而染色体的群体部分仅表示箱子,用字母来表示箱子(这样,上面染色体就可以表示为ADBCEB)。

通过查询物品部分,可以清楚群体名称所代表的含义,即:

B={3,6},E={5},C={4},D={2},A={1}

因此,包括2个部分的染色体的集成可由下图来表示:

作称为选择,其目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体遗传到下一代,它是建立在群体中个体的适应值评估基础上的。

这里采用联赛选择算子。其基本方法是,从群体中随机选择k个个体,其中适应值最高的个体保存到下一代,这一过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。其中,参数k称为竞赛规模,常取k=2。2.3.2　交叉算子

,把,,是产生新。

由于染色体编码包含2部分:箱子和物品的群体,因此交叉需处理可变长度的染色体,具体步骤如下:

第1步:随机选择2个交叉位置,对每个父代选定交叉部分。

第2步:将第1个父代交叉部分的内容插入到第2个父代第1个交叉位置之前。由于交叉对染色体的部分群体进行操作,这就意味着从第1个父代插入一些群体

(箱子)到第2个父代中。

第3步:从产生的后代中原有的箱子中去掉所有重复出现的物品,使得这些物品原先的从属关系让位于“新”插入的箱子。

因此产生的后代中的某些群体发生了改变,他们不再包含与原先相同的物品。

第4步:如果必要,根据问题和适应值函数来调整新产生的箱子。在此步骤,可采用如FFD等局部搜索算法。

第5步:改变2个父代的角色并重新应用第2步到第4步生成第2个子代。

示例如下:

图1　染色体集成图

这种表示的原理是:对于装箱问题来说,群体是有意义的积木块,也就是最小的解片断,这些片断可以按照对其所属的解所期望的质量来转运信息。

而这种表示的关键之处就是遗传算子对于染色体的群体部分进行操作,其物品部分仅用于判定由哪些物品形成该群体。2.3　遗传操作设计

遗传操作包括以下3个基本遗传算子:选择、交叉、变异。选择和交叉基本完成了遗传算法的大部分搜索功能,变异增加了遗传算法找到接近最优解的能力。

2.3.1　选择算子

从群体中选择优胜的个体,淘汰劣质个体的操

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技求解装箱问题的一种变长度染色体遗传算法(2)全文阅读和word下载服务。