当前位置： IC37首页 > 技术资料 > 电子综合 > 集装箱装载问题的模拟退火遗传算法
集装箱装载问题的模拟退火遗传算法
类别：电子综合
集装箱装载问题的模拟退火遗传算法 [日期：2005-12-19] 来源：电子技术应用 作者：江 娜 丁香乾 刘同义 张红兰 [字体：大 中 小] 摘要：将模拟退火的思想引入遗传算法中，将两者结合起来，探讨了模拟退火遗传算法在复杂集装箱装载中的应用，以此达到缩小搜索区域，增强算法的收敛性的目的。该算法充分发挥了遗传操作中交叉算子的作用，并通过实验仿真表明该算法优于传统的计算方法。 关键词：集装箱装载 模拟退火遗传算法 启发式算法 目前，物流业正处在快速发展的时期，集装箱运输将会有大幅度的增长。集装箱装载作为物流配送过程中的一个关键性环节，可提高配送业务的自动化水平、提高货物装载的优化程度、提高配送业务的工作效率和规范业务流程等。 从二十世纪70年代初正式开始，集装箱装载问题就引起了应用的研究和探讨。装箱问题就是将不同尺寸的物品摆放入有一定容易的容器中，以获得某种最佳的效益。从计算复杂性理论来讲，装箱问题属于np完全问题，求解极为困难。 遗传算法采用了生物进化论的思想，通过自然选择和适者生存的竞争策略来解优化问题；模拟退火起源于统计物理方法，并首先被kirkpatrick等引入组合优化领域。遗传算法的全局搜索性能较强，便是其容易过早收敛，而且在进化后期搜索效率较低，种群的进化缓慢；需模拟退火算法具有较强的局部搜索能力，并且能使搜索过程避免陷入局部最优解，但是把握搜索过程的能力不强，运行效率不高。本文通过将模拟退火的思想引入遗传算法，使两者有效地结合，缓解了遗传算法的选择压力，增强了遗传算法的全局收敛性，避免在搜索过程中陷入局部最优。 1 遗传算法 遗传算法最早由美国michigan大学的j.holland教授提出，起源于上世纪60年代人们自然和人工自适应系统的研究，是基于darwin进化论和mendel的遗传学说的一种全局优化概率搜索算法，它模拟了生物界中的生命进化机制，在人工系统中实现特定目标的优化。对于复杂的优化问题，遗传算法无需建模和进行复杂的运算。与传统的搜索算法不同，遗传算法把优化问题的解的搜索空间转化为遗传空间，从代表问题可能潜在问题的解的搜索空间转化为遗传空间，从代表问题可能潜在解集的一个种群开始，其中种群中的每一个体对应问题的一个解，称为染色体。初代种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，按预先根据目标函数确定的适应度函数计算各个体对问题环境的适应值，再根据个体的适应值对个体对应的染色体进行选择，使适应性好的梁色体比适应性差的染色体有更多的繁殖机会；然后进行交叉、变异等遗传操作产生新一代群体。如此循环，逐步向优化的种群进化。 遗传算法的主要特点是：遗传算法的处理对象不是参数本身，而是对参数集进行编码的个体；遗传算法采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估；遗传算法仅使用问题的目标函数进行工作，不需要其他的先决条件或辅助信息；遗传算法不是采用确定性规则进行工作，而是采用概率的变化迁规则来指导其搜索方法；遗传算法具有隐形并行性，可以在较大的解空间迅速寻优。
标准的遗传算法求解过程如下： （1）初始化遗传算法的控制参数，如群体规模n、变异概率pm、交叉概率pc； (2)随机产生初始解群p(t)={p0p1p2…pn}，个体的数目一定，每个个体表示为染色体的基因编码； （3）计算群体中每个个体的适应函数值； 遗传算法在搜索过程中基本不利于外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值进行搜索。因此适应度函数的选取至关重要，将直接影响遗传算法的收敛速度以及能否找到最优解。解的好坏用适宜度函数值的大小评估，适应度的函数值越大，解的质量越好。 （4）根据个体的适应度选择复制再生个体，适应函数值大的个体的复制概率大； 选择是指以一定的概率从种群中选择优胜个体，淘汰质个体的操作。选择的过程是一种基于适应的优胜劣汰的过程，是用来确定得组或交叉个体，以及被选个体将产生多少个子代个体。 （5）按照一定的交叉概率和交叉方法，对现有解群中的个体体交叉操作,生成新个体。 交叉是指对两个相互配对的染色体以某种方式相互交换部分基因，从而形成两个新的个体，交叉是遗传算法的核心。 （6）按照一定的变异概率和变异方法，对交叉后的个体进行变异操作； 变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因替换，从而形成一个新的个体。 （7）由交叉和变异产生了一新一代种群，若满足收敛条件，遗传进化过程结束；否则转（3）。 2 模拟退火算法 模拟退火算法是基于monte carlo迭代求解法后种启发式随机搜索算法，它模拟固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性来达到寻找全局最优或近似全局最优的目的。在搜索最优解的过程中，模拟退火法除了可以接受优化解外，还有一个随机接受准则（metropolis准则）有限度地接受恶化解，并且接受恶化解的概率慢慢趋向于0，这使得算法有可能从局部极值区域中跳出，即可能找到全局最优解，并保证了算法的收敛性。 模拟退火算法的求解过程如下： （1）随机产生初始解x0； （2）初始化退火温度t0； （3）在温度tk下执行如下操作： ·产生新的可行解x,x为x的邻解； ·计算评价函数f(x)和f(x)的差值δf=f(x)-f(x); ·以min{1,exp(-δf/tk)}>random[0,1]的概率接收新解，其中random[0,1]是[0，1]之间的随机数。若达到温度tk的平衡状态转（4），否则转（3）； （4）按一定方式降低温度，可定义下降函数为tk+1=αtk,k+1→,其中α∈[0，1]； （5）若满足收敛判据，退火过程结束；否则转（3）。 通过以上分析可知，在模拟退火过程中，其退火温度控制着求解过程向最小值的优化方向进行，同时它又以概率exp(-δf/tk)接收劣质解，因此算法可以跳出局部极值点。只要初始温度足够高，退火过程足够慢，算法能够收敛到全局最优解。 3 模拟退火遗传算法 虽然遗传算法使用简单、鲁棒性强、应用范围甚广，但是它本身也存在着许多不足，尤其是容易过早收敛，使搜索陷入局部最优解，因此本文把模拟退火引入到遗传算法中。本文的模拟退火遗传算法如下： （1）初始化控制参数： n为群体规模；pm为变异概率；t0为退火初始温度；α为温度冷却参数； （2）随机产生初始解群； （3）对现有解群实施如下操作，直至产生出下一代新的群体： ·评价群体中每个个体的适应函数值f(xi)，i=1,2,…,n,本文中以空间利用率作为适应度函数； ·采用轮盘赌选择法对个体进行选择； 轮盘赌选择法的基本思想是：生成一个随机数γ∈[0，1]，并且计算个体的相对适应度值pi=fi/∑fi，如果p0+p1+…+pi-1<γ≤p0+p1+…+pi,则第i个个体被选择到下一代。可见，个体的适应度值越大被选择到下一代的机会也越多。 ·对选择复制后的个体实话交叉操作，随机选择两个个体xi和xj进行交叉操作，并且计算两个新个数xi和xj的适应函数值f(xi)和f(xj)；生成一个[0，1]之间的随机数random，以min{1,exp(-δf/tk)}>random[0,1]的概率接受新的解，即接受新个体。 ·对交叉后的个体进行变异操作，按第三步中的方法决定是否接收变异后的解； （4）若满足收敛条件，进化过程结束；否则tk+1=αtk,转（3）。 模拟退火遗传算法首先利用轮盘赌选择方法，淘汰了适应度较低的个体。而交叉操作是遗传算法中的核心，寻优过程主要通过它实现，模拟退火遗传算法吸取了这一思想，对选择后个体均实话交叉操作，并且把交叉和变异后的子代与父代竞争，通过boltzmann机制来接收子代，不但有利于优良个体的保留，同时防止了早熟收敛的问题。随着进化过程的进行，温度逐渐下降，接收劣质解的概率也逐渐减小，有效地利用了模拟退火算法的爬山特性，提高了算法的收敛速度。 4 集装箱装载实例与算法分析 在实际应用中，为了求解的快速性和实用性，人们通常采用一引起启发式算法来求解装箱问题。为了评价模拟退火遗传算法的性能，将模拟退火算法和启发式算法进行比较，分别用来求解装箱问题。 本文使用delphi程序进行模拟装箱，所使用的模拟退火遗传算法的控制参数选取如下：群体规模n=100,变异概率pm=0.01，初始温度t0=1000，冷却参数α=0.9；待装物品为洗衣机散件，单位为毫米，其体积以及数量如表1所示；布局空间采用规格为11.96×2.35×2.69的集装箱，单位为米。物口装箱过程中，充分考虑到物品的摆放方式，以及是否可以置底，分别利用启发式算法以及本文的模拟退火遗传算法进行装箱，得到的结果如表2、表3所示，装载效果如图1、图2所示。其中x0,y0,z0表示物品在集装箱中的位置。
表1 待装物品数据名称数量深宽高体积10# 8004753351273008#4440330330479164# 15004204202646002#139360360220285123#10550430170402057# 6604403501016409#62852302301507611#4577054044518503117#186049050021070021# 2913642752912927# 58058058019511228# 5193105008044530#7800475580220400电机 56536523548463定时器 55043017040205主体机500430390660110682 表2 启发式算法的装箱结果序号产品数量深向宽向高向x0y0z01主体机486276300058#4141116100063#1015200198072#13823615500198072#111188300198089#2121116101760089#4141116100330 表3 模拟退火遗传算法的装箱结果序号产品数量深向宽向高向x0y0z01主体机48627630001主体机122610019801主体机212186001980230#4411129001980230#313112908001980317#111120908001980411#45153131900198058#4141116100063#6123860780198063#211220901660198063#21122580800198072#21128601880198072#212125801350198072#41412580800232072#126216131900242572#5151107500242589#2121116101760089#4141116100330 本例中的待特物品共有712件，其中需要装载500台主机，7台30#，1台17#，45台11#，6台9#，10台3#，139台2#，4台8#。 启发式算法使用知识规则，搜索速度快，搜索方向相对明确，但是知识规则的使用使得搜索空间的范围急剧缩小，因此求解结果通常会有很大的局限。利用文献中的启发式算法装载物品，共布入645件物品，空间利用率为88.3%。装箱结果如表2、图1所示。 模拟退火遗传算法把模拟退火和遗传算法有效地结合起来，既加速了算法的收敛速度又避免陷入局部是优解。利用模拟退火遗传算法装载物品，物品全部布入，空间利用率为92.6%。装箱结果如表3、图2所示。 从表2和表3的数据以及装箱效果图可以看出：模拟退火遗传算法的空间利用率比较高而且布入物口的个数和种类较多；启发式算法空间利用率比较低，布入的物品也较少。利用模拟退火遗传算法解决装箱问题还是行之有效的。 本文针对集装箱货物装载问题提出了一种模拟退火遗传算法，将模拟退火 和遗传算法有效地结合。通过具体试验可以看出，该算法充分发挥了交叉算子的作用，不仅缩小了可行域的搜索范围，而且避免搜索陷入局部最优解。采用该算法进行求解，不仅提高了集装箱的利用率，而且提高了工人的装载效率，从而提高了企业的竞争力。
