摘要：堆垛机是自动化立体仓库主要设备，本文分析了自动化仓库堆垛机拣选作业的运行特点，通过计算货位点所在坐标位置产生拣选点,运用遗传算法在MATLAB软件上编制并运行了堆垛机的访问路径优化程序，仿真实验和工程实际应用表明,该算法能有效提高系统的工作效率。

　　关键词： 堆垛机;路径优化;遗传算法;MATLAB

　　Abstract:The transport machine is the most important equipment in Automated Warehous,this paper analyzes the operating characteristics of the transporter .By calculating the location of the cargos can generated the choosen points, then writen and operated the program of transporter path in MATLAB ,the simulation experiments and engineering applications show that this method can visibly improve the efficiency of the systerm.

　　Key words:Transpoporter;Path optimization; Genetic Algorithm; MATLAB

　　1 引言

　　在全球新经济形势的挑战下，市场范围和竞争压力都不断扩大，很多企业将其发展的重点转移到企业供应链的物流管理上，自动化物流的快速发展离不开高效的供应链。立体仓库作为链接生产者和消费者的的桥梁，是物流系统的一个中心环节，自动化仓库以其较高的空间利用率、方便快捷的管理模式、货物破损率低及周转速度快等特点,是现代物流的重要组成部分, 因此对自动化运行情况进行分析，并根据外界环境对各子系统进行调度来提高自动化立体仓库的运行效率就显得格外重要[1]，其中堆垛机的作业周期由出库台和入库台的管理时间、处理时间和堆垛机的行驶时间3部分组成，其中堆垛机的行驶时问约占堆垛机作业周期的50%左右，它是行驶距离的单调增函数.所以，合理解决自动化立体仓库堆垛机的拣选作业路径，是提高其运行效益的有效手段。本文以拣选路径作为目标函数，通过使用遗传算法来优化其路径，并通过MATLAB编程验证了算法的有效性。

　　2 堆垛机工作流程

　　对于那些具有单机自动功能并且能批量输入

　　投稿日期：200911-27

作者简介：万欣欣(1984—)，女，汉，硕士研究生，研究方向：优化设计;E-mail：wanxinxin@163.com;

　　任务位置的堆垛机来说，操作人员在开始正式执行

　　拣选操作之前，将表单上所有任务的位置点首先通过操作面板输入到堆垛机控制系统中，然后每当一个拣选任务操作完成，就按一下面板上的指定控制按钮，堆垛机就自动地运行到下一个拣选位置处进行新的拣选操作，直到所有的任务完成，堆垛机行驶到出库端口处[2]。拣选作业流程可以把堆垛机的拣选作业调度问题归纳成如下问题:设有n个拣选任务，即有n个货位点等待堆垛机到达，堆垛机从出/人库站台处出发，依次到达n个货位点，且每个货位点只去l次，上述问题与旅行商问题相似，旅行商问题(TSP)是一个典型的优化组合问题,可具体描述如下:已知n个城市之间的相互距离,现有一个推销员从某一城市出发,必须遍访这n个城市,并且每个城市只能访问一次,最后又必须返回到出发城市.如何安排他对这些城市的访问次序,可使其旅行路线的总长度最短。可以用遗传算法来解决旅行商问题。

　　3 遗传算法优化原理

　　遗传算法(Genetic Algorithm)，起源于对生物系统所进行的计算机模拟研究，它是由美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发而创造的一种基于生物遗传和进化机制的自适应概率优化技术—遗传算法。基于对自然界中生物遗传与进化机理的模仿，可以用不同的编码方法来表示不同问题的可行解遗传算法的三个基本操作是：选择，交叉和变异。

　　3.1 选择

选择的目的是从当前群体中选择出优良个体并使其有机会作为父代为下一代繁殖子孙，进行选择的原则是适应性强的个体为夏代贡献一个或多个后代的概率大，这就体现了达尔文的适者生存的原则。选择操作建立在对个体的适应度进行了评价的基础上，通过选择算子进行SGA。人们提出了各种选择算子的操作方法，比例选择方法最常用。比例选择因子是利用比例于各个适应度的概率决定其子孙的遗传可能性[4]，比例选择算子是一种有随机选择也叫赌盘选择。若设种群数为M，个体i的适应度为，则个体i被选择的概率为

　　当个体选择的概率给定后就产生一个(0，1)之间的随机数来决定那个个体参加交配。

　　3.2 交叉

　　交叉是遗传算法中最主要的遗传操作，交叉可以获得新一代的个体，新个体遗传并组合了父辈的特征，交叉体现的是信息交换的思想，是将群体内的全部个体随机搭配成对，交叉有单点交叉，多点交叉，均匀交叉等。其中单点交叉是最常用的交叉方法。单点交叉的方法示意如下：

原始串： A 0 1 0 0 1 00 1 1

B 0 1 1 1 1 00 0 0

交叉后的串： A 0 1 0 0 1 00 0 0

B 0 1 1 1 1 00 1 1

　　3.3 变异

　　在自然进化中，变异是一随机的过程，是基因上的一个等位基因被另一个代替而产生的新的遗传结构，遗传算法中经常采用很小的概率来表示变异率，典型值是在0.001~0.01之间，变异的作用被认为是搜索任意给定的串的可能性永不为零 ，图3.1说明了一个二进制串上的变异效果。其中二进制串中的变异位是第四位。

　　原始串 0 0 0 1 1 1 0 0 1 1 0

　　变异后的串 0 0 0 0 1 1 0 0 1 1 0

　　4 MATLAB程序仿真实现

　　4.1 Grefenstette编码

　　基本遗传算法使用固定长度的二进制符号串来表示中种群中的个体，其等位基因由{0，1}所组成， 组成编码就是把一个问题的可行解从其解空间转换到GA所能处理的搜索空间的转换方法。针对一个具体的应用问题，如何设计一种完美的编码方案，一直是遗传算法应用的难题之一，也是其重要研究方向。编码方法有二进制编码、格雷码编码等其中格雷码可以克服传统的二进制表示方法的不足。由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码,所谓的grefenstette编码就是用所选队员在未选(不含淘汰)队员中的位置，)在求解TSP问题时，1985年，Grefenstette等提出了基于顺序表示的遗传基因编码方法[5]。顺序表示是指所有要访问的城市依次排列构成一个顺序表，对于一条旅程，可以依旅行经过顺序处理每个城市，每个城市在顺序表中的顺序就是一个遗传因子的表示，每处理完一个城市，从顺序表中去掉该城市。处理完所有城市以后，将每个城市的遗传因子表示连接起来，就是一条旅程的基因表示。例如，顺序表C = (1，2，3，4，5，6，7，8，9，10)，一条旅程为2-6-8-4-5-7-9-1-10-3。则这条旅程的编码表为(2 5 7 3 3 3 3 1 2 1)

 1/2    1 2 下一页 尾页