基于迷宫问题遗传算法的复合材料铺层数量优化

李世春，杨世文

（中北大学机械与动力工程学院，山西 太原 030051）

基于迷宫问题遗传算法的复合材料铺层数量优化

李世春，杨世文

（中北大学机械与动力工程学院，山西 太原 030051）

研究使用最少铺层数量，使产品达到性能指标的复合材料铺层优化问题。使用遗传算法，参考迷宫问题的解决方法，保留普通遗传算法的框架，改变求染色体的适应度值的计算过程，找出满足要求的最少铺层数量的解。在求适应度值过程中增加逐位解释环节，以得不同铺层数量的解。在求适应度值过程中增加解码、剔除无效项、对称环节，以满足复合材料铺层角角度离散、铺层角要少于4层连续相同、对称这些常见要求。结合示例，指出将逐位解释范围分段，可以提高计算效率。该方法实现了对复合材料产品的铺层数量和角度的同时优化，可以实现产品的经济性和轻量化。

铺层数量优化；迷宫问题；遗传算法

CLC NO.:TB332Document Code:AArticle ID:1671-7988(2014)02-17-06

前言

以力学性能为主要目标的复合材料产品，通常使用层合结构。其原材料通常为单向带预浸料。预

浸料的刚度和强度在平行纤维方向很高，而垂直纤维方向很差。因此在层合结构中，预浸料铺放的角度顺序，将极大地影响产品最终的性能。

鉴于铺层的角度顺序非常重要，目前研究者主要优化每个角度值的取值，以得到产品最好的力学性能。而很多工程问题则是要求产品性能达到一个指标即可，优化目标为产品的重量的优化问题。若产品宏观尺寸不变，产品重量将直接由所用铺层的数量决定。因此对于这类工程问题，优化目标应当涵盖铺层数量。

目前针对铺层数量的优化，常用的有两种方法。第一种方法[1]为，视角度数量固定，而每层铺层的厚度可变，得到最优解后，再将一层拆分为若干层。这种方法的缺点是无法满足铺层角要少于4层连续相同，否则将导致基体开裂。第二种方法[2]为，将角度序列作为染色体，使用遗传算法。将一个角度顺序表示前后两个向量。第一个向量中，每一项为0或1，表示该层角度值不存在或存在。第二个向量中，每一项为角度值或角度值代号。由于第一个向量中0的存在，角度序列中有效角度个数是不确定的，以此实现了铺层数量的变化。这种方法的缺点是，表示一个角度顺序需要一个两倍长度的向量，一个最优解需要前后两个模式（pattern)共同匹配，得到最优解的难度较大。

观察一个角度序列，首先可以看到各层的角度值，然后可以数出角度值的个数，即序列的长度。后者便是铺层的数量，这个由角度序列可以得到的信息常常被忽略。去除一个原始的较长的角度序列中的一些项，会得到一个新的铺层数量和角度顺序的角度序列。本文正是基于这个基本思想，借鉴迷宫问题的遗传算法解决方法，实现了对铺层数量和角度顺序同时优化。

1、迷宫问题与复合材料铺层优化介绍

1.1 迷宫问题

迷宫问题[3,4]即，为小人B寻找一条，从起点到出口，能够走出迷宫，且路程尽量短的路径,见图1。迷宫问题有三个特点。第一，在任意一个位置，小人的每一步有上下左右4种方向可选。第二，当选定的方向遇到障碍物时，该方向会被认为无效，将跳过该步进行下一步。第三，每走一步，就需要判断当前位置与出口的距离，一旦到达出口，就停止。将有效的方向记录在一个序列中。可行解为能够到达出口的序列。解的长度作为解的评价指标。最优解则为长度最短的可行解。最优解的长度未知。

1.2 复合材料铺层优化

由单向带预浸料构成的复合材料产品的性能，除材料本身的性能和产品尺寸外，主要由铺层组合决定。

铺层组合指铺层的数量和每一层的角度值所构成的角度序列。在工程实际中，角度值并不是连续变量，而是一些离散的值，通常为[-45°，0°，45°，90°]，也有以15°为间隔的角度系列。这些角度即可以认为是小人的每一步的上下左右方向。产品的最终性能即由这些角度的序列决定。这一点与迷宫问题的第一个特点相同。

复合材料铺层中，若连续4层方向均相同，则容易造成基体开裂而失效。即不能出现例如[45/ 45/45/45]的情况，第4个45°即被认为是无效的方向。这个角度值的无效可以认为是小人选定的方向有障碍物，自动跳过该角度值，读取下一个角度值。这一点与迷宫问题的第二个特点相同。

最终得到的最优的角度序列，其长度在优化之初完全未知。角度序列的长度小，即铺层数量少，则在同样的尺寸下可以减轻产品质量，优化目标即为铺层的数量。这一点与迷宫问题的第三个特点相同，也是两者本质上的相同之处。

2、遗传算法实现

2.1 算法流程

解决迷宫问题和铺层数量优化的遗传算法，与一般的遗传算法并没有基本框架的变化，仍然是随机生成若干染色体组成种群，计算每个染色体的适

应度值。染色体根据适应度值，通过复制、交叉、变异得到下一代种群，再次计算每个种群的适应度值。如此循环迭代，直到满足停止条件。有最好适应度值的染色体即为最优解。

迷宫问题遗传算法，与普通遗传算法的区别，仅在于对染色体的理解，和计算染色体的适应度值的过程。迷宫问题遗传算法，不认为种群中的染色体可以直接作为解。染色体中的每个变量不都是有效的。真实染色体包含在染色体中，它的长度比染色体短。它的每一项才都是有效的。染色体使用真实染色体的适应度值参与遗传算法计算，这样对普通遗传算法改动较小。

普通遗传算法得到适应度值的流程图，如图2所示。

迷宫问题遗传算法，得到染色体的适应度值的流程图，如图3所示。

2.2 关键步骤

2.2.1 角度值的变换

遗传算法所处理的染色体，并不是直接由角度值构成的。因为角度为离散值，所以使用一些整数来代表角度。染色体由整数值构成。在将染色体解释完成后，才将整数还原为角度值，带入产品计算函数计算该角度序列的适应度值。

在铺层设计中，有时要求平衡性。即+θ°与-θ°的数量相等。为解决这个问题，可将角度系列编为对应变量向量为[1,2,3]。其中1代表0°，2代表±45°共两层，3代表90°。这样把问题进一步简化了。

2.2.2 染色体的对称

复合材料铺层设计中，通常要求对称。所以将序列对称后作为实际的铺层顺序。即变量(x1,x2…,xn)，实际代表的铺层顺序是（xn,…,x2,x1,x1,x2…,xn)。这样的对称，对称后层数为偶数。

奇数层的对称，如（xn，…，x2,x1,x2…xn)，也满足对称性要求。但只减少一层，在实际中影响不明显。如有需要，可将偶数层的最中间层x1去掉一层，进行验算，或是在优化得到的层数的基础上，减去一层，按固定层数问题，进行优化并比较。

2.2.3 染色体的逐位解释

在迷宫问题中，开始时并不知道走到出口所需的步数，所以先估计一个较大的步数数量，然后随机生成各种方向，形成一个方向序列，即一个染色体。按这种方法，随机生成若干个染色体，构成种群。这些染色体的长度是相等的，而且在进化过程中也不会变化。

若将方向序列的每一步都执行完，小人可能到达出口后又折回迷宫。将最后停止的位置距离出口的距离作为适应度值评价，则该解的适应度值会非常差。但是真正的解实际上已经蕴含在方向序列中了。所以需要小人每走一步就进行一次评价。发现到达出口后，染色体中后续的方向就不再有意义。对染色体截取从第1位到某一位的片段，以这个片段作为一个可能的解，进行评价，再分析从第1位到下一位的片段，再进行评价，这个过程称为逐位解释。

到达出口后，若继续让小人运动，其适应度值将不会变好，通常是变差。将逐位解释得到的适应

度值组成适应度值向量，该向量中的适应度值将会逐渐变好，然后逐渐变差。假设最好的适应度值对应于从第1位到第k位的片段，（若有多个相同的最好适应度值，则取最先出现的），则该染色体的有意义部分为从第1位到第k位的这一部分。这一部分，经过剔除无效项后，即为真实染色体。

在复合材料铺层数量优化时，事先也不知道所需的最小层数。因此将层数数量取一较大的值，随机生成各种方向，形成一个较长的染色体。从第一位开始，直到最后一位，依次计算适应度值。例如染色体为（x1,x2，x3，x4）。其对应的真实铺层可能为(x1，x1)，(x2，x1，x1，x2)，(x3，x2，x1，x1，x2，x3)和(x4，x3，x2，x1，x1，x2，x3，x4)。其适应度值分别为fitness1，fitness2，fitness3，fitness4。假设fitness3为最好的值，则该染色体的有意义部分为（x1,x2，x3），对应的真实铺层顺序为(x3，x2，x1，x1，x2，x3)。

2.2.4 剔除无效方向

复合材料铺层中，不允许出现连续4层方向相同的情况。

由于在此文章中，是偶数对称铺层，因此x2和x1不可以相同。若相同，则剔除x2，得到新的序列，再次判断x2，直到得到一个x2不等于x1。然后从x1开始，判断是否有连续4层方向相同。若存在，则剔除第4个方向，依次判断并剔除。直到序列中不包含4个连续相同的值。

例如，假设在染色体逐位解释到第6位时，得到的染色体片段为(4,4,3,3,3,3)。可看出应该剔除第2位和第6位。剔除后得到的有效片段为(4,3,3,3)。对称并解码后，角度序列是[903/45]S。应注意到这与逐位解释到第5位时，得到的有效片段是相同的。也就是经过逐位解释和剔除过程后，有效片段可能会是重复的。

2.2.5 得到染色体的适应度值和真实染色体

这样，经过逐位解释、剔除无效项、对称和角度变换后，一条染色体就解释成为一系列长度不同的角度序列。用这些角度序列，分别计算适应度值，其最好的适应度值即为该染色体的适应度值，进行遗传算法计算。最好的适应度值所对应的有效片段，即为真实染色体。

这样一个变换的过程，可以单独写为一个函数。而用解释出的角度序列求适应度值的过程，写为一个产品计算函数，被前者调用。

3、算法效果分析

使用一个简单的算例，分析这种算法的效果。

算例1。已知单向碳纤维预浸料LT-02/T300B材料性能，E1=136GPa，E2=8.1GPa，G12=4.9GPa，V21=0.31，Xt=1560MPa，Xc=1380MPa，Yt=43.7MPa，Yc=215MPa，S=83.7MPa，预浸料厚度为0.127mm，密度为ρ=1800kg/m3。一矩形板长为a=0.5m，宽b=0.25m。在长度方向受拉力Fx=100kN。要求不能发生破坏，且长度方向变形量不得大于2mm。求满足要求的最少的铺层数量及其铺层角度。暂不考虑连续4层方向不可以相同。

若不考虑连续4层方向不可以相同，因为只受x方向的拉力，则该问题的最优解明显是由若干层0°构成。由于该算法得到的铺层顺序是偶数层的。因此只计算偶数层情况。经计算得，4层0°的变形量为2.9mm，6层0°的变形量为1.9mm，8层0°的变形量为1.4mm，且都不发生破坏。所以这个算例的最优解为6层0°。

使用Matlab自带GADS工具箱，结合整数规划。将铺层数量作为优化目标和适应度值。将变形量和Hoffman准则值作为约束，并使用罚函数将其集成到适应度值函数中。将变量个数设定为10，也就是铺层数量最大为20。设定种群个体数为20。将终止条件中，停滞代数（Stall generations）设置为

10，最大代数（generations）设置为20。进行计算。

GADS返回的最优染色体为[2,2,2,3,3,1,2,2,1,2]，最好的适应度值为6。也就是说最优解对应的角度序列有6位，铺层数量为6。染色体前6/2=3项有意义的值，组成这个染色体的真实染色体，为[2,2,2]（不考虑连续4层方向不可以相同）。解码并对称后，得到的角度序列为[06]。与之前计算的最优解相同。

算例1的运行过程显示在图4中。从图4和GADS的运行输出中，都可以发现，在第一代中，最优解已经得到了。进化是因为满足了停滞代数才终止的。

使用迷宫问题遗传算法，最优解在染色体中，作为一个模式（pattern）而存在，如此例中[2,2,2,*,*,*,*,*,*,*]，*表示任意取值。任何包含这种模式的染色体，都是最优解。前言中所述优化铺层数量的第二种方法，其最优解需要在两倍长度的染色体上，生成前后两个模式，两个模式匹配后，才能得到最优解。相比较，迷宫问题遗传算法，得到最优解的难度明显较低。

在此例中，在第一代，随机生成一个染色体时，生成这种模式的概率为1/43=1/64。对于种群数为20的初代种群，直接生成最优解的概率相当大。真正的最优解的长度越短，则在初代中出现最优解的概率越大，后续所需要的迭代次数也就越小。因此可以将停滞代数设置的少一些。而若真正的最优解的长度较长，则在优化时一定时间后得到的可行解长度也会较长，与真正的最优解也较接近。因此若计算时间过长，则可以选择一个较好的可行解，作为次优解在工程中使用。故使用这种遗传算法，停滞代数和最大代数都可以设置地比普通遗传算法稍少一些，至少可以得到一个较好的次优解以便工程使用。

4、算法改进

若严格按照上述步骤进行，则一个染色体要进行n次逐位解释，也即运行n次适应度值计算，（n为染色体长度）。若能估计出最优解的大致长度，就没必要从第1位到第n位全部逐位解释，只需要在其附近逐位解释，这样将显著减少计算量。若最优解的大致长度完全未知，则可以将逐位解释范围分段，分阶段进行遗传算法计算。

首先预估一个较大的范围，比如染色体有20位，需要逐位解释的范围定在12到20位，然后进行计算。若得到的最优解在12到20之间，则可以认为该解即为最优解。若得到的最优解为下界或更少，即12，则再缩减范围为15到4，并将刚才得到的最优解带入初始种群中，进行第二次遗传算法计算，直到找到最优解。第二次的范围上界比第一次的下界稍大。这是因为从染色体到铺层顺序的过程中，有剔除过程，所以应将边界范围放松一些。边界的变化顺序，也可以是从小向大变化。

算例2。同算例1，但是这次计算考虑连续4层不能相同的约束，并分阶段进行遗传算法计算。

首先，使用[0/+45/-45/90]准各向同性铺层方式，连续铺层，并对称。发现选用[90/45/-45/0/90/45/-45/0]S时，x方向变形量为1.9mm，小于2mm，最大Hoffman准则值为0.6157，小于1，不破坏。将该解作为一个参考。该层数为16层。因此设置染色体长度为8。

分阶段进行遗传算法计算。设置第一次遗传算法计算中，染色体逐位解释的范围为5到8。

计算得到的最优解为[2,2,2,4,2,2,1,4]。适应度值为8。也就是说，前4个有效项组成真实染色体。前4个有效项为[2,4,2,2]，即铺层顺序为[0/0/90/0]S。由于存在剔除过程，得到的解并不完全在限定的染色体范围内。比如此次限定的下限虽然为5，就得到了长度为4的解。

将这个第一次计算得到的有效染色体片段[2,4,2,2]，作为一种模式，生成一个染色体，比如[2,4,2,2,0,0,0,0]，放入第二次遗传算法计算的初始种群中。设定此次逐位解释范围为1到5。

这次得到的最优解为[1,2,2,2,1,2,3,1]，适应度值为8。即真实最优解的铺层顺序为[03/-45]S，层数为8层。计算得x方向变形量为1.86mm，最大Hoffman准则值为0.3981，满足约束条件。

至此可以认为[03/-45]S是最优解。也可以尝试将中间一层去掉，使用一个奇数层对称结构并对比。

将中间一层去掉，得[03/-45]S。计算这组解，得x方向变形量为1.89mm，最大Hoffman准则值为0.3864，满足约束条件。因此减去中间一层后的解，可以视为最优解。即最优解为7层，铺层顺序为相比较优化前使用准各向同性铺层方式，层数由16层减为7层，也就是减重56.25%。效果非常明显。

在算例2中，可以发现前后两阶段中，两个最优解虽然不同，但其适应度值是相同的，故也以认为第一阶段的最优解是最终要得到的最优解。所以这种分阶段的方法，对于求一个满意解或工程可以接受的次优解，是非常有效的。

5、结论

本文通过找出迷宫问题和复合材料铺层数量优化问题的本质相同之处，利用迷宫问题的遗传算法解决方法，实现了对铺层数量和铺层角度的同时优化。该方法保留普通遗传算法的框架，只改造求染色体的适应度值的计算过程，通用性好。

相较于常用的铺层数量优化方法，该方法可以处理铺层角少于4层连续相同的要求。通过将逐位解释范围分段，改进该方法后，可以快速得到最优解或工程可用的次优解。该方法计算后期主要为停滞，根据这个特点，可以引入自适应措施继续改进。

[1] 刘昊, 杨和振. 基于多岛遗传算法的深海复合材料悬链线立管优化设计[J]. 哈尔滨工程大学学报, 2013(07).

[2] 李伟国. 复合材料层合结构可靠性优化方法研究[D].南京航空航天大学, 2005.

[3] 巴克兰. 游戏编程中的人工智能技术[M]. 清华大学出版社, 2006.

[4] 王斌, 李元香. 用遗传算法解迷宫问题[J]. 微型机与应用, 2002(10):58-60.

Stacking number optimization of composite product by genetic algorithm based on maze problem

Li Shichun，Yang Shiwen

(North University of China School of Mechanical and Power Engineering ,ShanxiTaiyuan 030051)

This composite stacking optimization aims at the product meeting the target with least layers.Using genetic algorithm, referring to the solution to the maze problem, retaining the framework of the common genetic algorithm, changing the chromosome fitness value calculation process, the solution which has the minimum number of layers and meet the requirements was found.In the fitness value calculation process,the bit by bit explanation was added, to get solutions with various numbers of layers.In the fitness value calculation process, the encoding,removing invalid entries, symmetrization was added to meet the common requirements such as ply angles discrete, less than four contiguous plies in same direction, and symmetric.It pointed out with an example, that sectioning the range of the bit by bit explanation will improve efficiency. This method optimizes the stacking layer number and angles at the same time, which will achieve economical and lightweight.

stacking layers number optimization；maze problem；genetic algorithm

TB332

A

1671-7988(2014)02-17-06

李世春，硕士研究生，就读于中北大学，主要研究方向：复合材料产品设计及结构优化设计。