基于遗传算法的装卸货任务分配问题的研究

基于遗传算法的装卸货任务分配问题的研究

姓名 梁晶

（哈尔滨理工大学电气与电子工程学院，黑龙江 哈尔滨 150080）

摘 要：介绍了遗传算法（GA）的基本思想，并利用MATLAB实现了遗传算法在装卸货任务问题上的运用，仿真的结果验

证了该算法求解装卸货任务问题的有效性。

关键词：遗传算法；车间调度问题；仿真；MATLAB语言

中图分类号：TP183 文献标识码：A 文章编号：

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数(评估由数)的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程，遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体。

1 遗传算法的基本原理

1.1 遗传算法及其求解方法

[1]

遗传算法将问题的解表示成字符串, 并把这样的字符串当作人工染色体或称为个体, 多个个体构成一个种群, 随机产生若干个个体构成初始种群, 通过对种群的不断进化, 利用“优胜劣汰”的自然选择机制,使种群中的个体不断朝着最优解的方向移动, 最终搜索到问题的最优解。算法的主要运算过程如下:?

1)编码 在用遗传算法求解问题时, 首先遇到的是编码问题。将问题的解以适合于遗传算法求解的形式进行编码, 称为遗传算法的表示。而交叉、变异等操作与编码的形式有关, 因此在进行编码时要考虑到交叉和变异问题。最简单的编码方式是二进制编码。

2)初始种群的生成 产生初始种群是在求解之前, 在解的备选空间中选择若干个体组成初始种群,通常产生初始种群采用的是随机法。

3)适应度评价 根据生物进化“适者生存”的原则, 需要对每个个体适应环境的能力进行刻画, 从而引入适应度。适应度是遗传算法在群体进化过程中用到的唯一的信息, 它为字符串如何进行复制给出了定量的描述。适应度函数通过计算个体的适应值, 来比较个体的适应度。适应度函数分为无约束条件的适应度函数和有约束条件的适应度函数。

4)选择 种群中的个体在进行交叉之前, 要进行选择。选择的目的是获得较优的个体作为父代, 进行下一步的交叉。选择的依据是个体的适应度, 适应度值高的个体被选中的可能性大, 适应度低的个体被选中的概率小。适应度高的个体可能被多次复制, 而适应度低的个体可能一次也未被选中。

5)交叉 交叉也称为交配, 即将两个父代个体的编码串的部分基因进行交换, 产生新的个体。交叉算子是种群遗传算法中的重要算子, 是种群产生新个体的主要手段。对于二进制编码, 具体实施交叉的方法有单点交叉、两点交叉、多点交叉、一致交叉等。对于实数编码, 交叉的方法有离散重组、中间重组、线性重组等。

6)变异 变异操作首先在种群中随机选择一个个体, 对于选中的个体按照一定的概率随机改变串结构中的某个值, 即对种群中的每一个个体, 以某一概率改变某一个或某一些基因座上的值为其他的基因。同生物界一样, 遗传算法中发生变异的概率很低。变异操作为新个体的产生提供了机会。

7)终止条件判断 终止条件判断是指在什么情况下认为算法找到了最优解, 从而可以终止算法。由于通常使用遗传算法解决具体问题时, 并不知道问题的最优解是什么, 也不知道其最优解的目标函数值, 因而需要通过算法终止, 并获得最优解。

2 装卸货任务分配问题描述

假设在同一时间，有m台带装卸的货车且每台货车待装卸的货物量为装卸货的能力为

wi，

有n支装卸队且每支装卸对

Qk，我们要把这台带装卸的货车

分配给支装卸队，使得总装卸时间最短。 定义变量

wi为第i车货物装载量 (单位为t， i表

1

示第i车)；

Qk第k支装卸队的装卸能力(单位为

开始 计算个体适应度值 初始化种群 编码 t/h，k表示第k支装卸队)；定义决策变量

X?(x1,x2,???,xm)表示将m台待装卸货车分给n支装卸队装卸的分配情况，若第i列车的卸货任务

x?k，

分配给第k支装卸队，则i即表示编号为i的货车所被分配的装卸队的编号。k的取值为1到

遗传操作：选择、交叉、 f变异 n之间的整数；定义变量k为第k支装卸队的装卸 k?1,2,3???n作业时间, 。 产生新一代种群 根据决策变量X?(x1,x2,???,xm)，确定第k 队装卸队所对应的待装卸货车的编号i及其待装卸

N 货物量wi，即xi?k时对应的wik。 满足停止规则 第k队装卸队装卸货总量为：

Y wik （2.1） ?i 解码 可得第k支装卸队的装卸作业时间为 k?1,2,3???n：

结束 wik ? f?X??i,?x?kKi （2.2） Qk 遗传算法流程图

则任务分配问题的数学模型可表示为：

3.1 基于遗传算法的装卸任务问题算法过程

1) 初始化参数：族群30，最大遗传代数2000，代沟

（2.3） 0.9，交叉率0.8，变异率0.01。

2）初始化群：按照编码方式的特点以及问题的要

至此，货运站装卸货的数学模型建立完毕。根据此数学模型，可以对装卸货任务分配问题进行算法设计和计算求解

求随机的生成一个包含一定数量个体的矩阵。 3）计算适应值：解码成工序序列，计算时间。 4）选择：在原族群中，按轮盘法选择出30*0.9（代沟）=27个个体组成新族群。 5) 交叉：对选择出来的新族群进行交叉，在新族群中，随机选择2个个体（选择过的个体将不再选择，保证所有个体都有选择），随机生成有一个数，如果大于交叉概率，就进行2点交叉。2点交叉位置每

3 基于遗传算法的装卸任务分配问题

2

次都是随机的。

6）变异：对交叉出来的新族群进行变异，在新族群中，对每个个体随机生成一个数，如果大于变异概率，随机生成两个位置数据，将两个位置的数据进行交换。

7）替换：新的族群个体是27个，原族群为30，保留3个适应性好的，替代其他27个。

3.2 基于遗传算法的装卸任务问题主程序。 1)基本参数和初始化： clc;clear %清空环境

load scheduleData Jm T JmNumber %% 下载数据

NIND=30; %个体数目

MAXGEN=2000; %最大遗传代数 GGAP=0.9; %代沟 XOVR=0.8; %交叉率 MUTR=0.01; %变异率 gen=0; %代计数器

[PNumber MNumber]=size(Jm);

Chrom(j,i+WNumber)=unidrnd(SizeTemp); end end

% 计算目标函数值 [PVal ObjV P S]

=cal(Chrom,JmNumber,T,Jm);

3.2 仿真并显示结果

figure(1)

plot(trace(1,:)); hold on;

plot(trace(2,:),'-.');grid;

legend('解的变化','种群均值的变化'); %% 显示最优解 figure(2);

MP=S(1,PNumber*MNumber+1:PNumber*MNumber*2);

for i=1:WNumber val= P(1,i);

a=(mod(val,100)); %工序

%Pnumber 工件个数 Mnumber 工序个数 b=((val-a)/100); %工件

Temp=Jm{b,a}; trace=zeros(2, MAXGEN); %寻优结果的初始值

mText=Temp(MP(1,i)); WNumber=PNumber*MNumber; %工序总个数

x1=PVal(1,i); %%初始化

Number=zeros(1,PNumber); x2=PVal(2,i); for i=1:PNumber y1=mText-1; Number(i)=MNumber; y2=mText; end PlotRec(x1,x2,mText);

2）计算目标函数值

PlotRec(PVal(1,i),PVal(2,i),mText); % 代码2层，第一层工序，第二层机器

Chrom=zeros(NIND,2*WNumber); hold on; for j=1:NIND fill([x1,x2,x2,x1],[y1,y1,y2,y2],[1-1/ WPNumberTemp=Number; b,1/b,b/PNumber]); for i=1:WNumber text((x1+x2)/2,mText-0.25,num2str(P(i)

)); %随机产生工序

val=unidrnd(PNumber); end while WPNumberTemp(val)==0 仿真结果见图1，图2。 val=unidrnd(PNumber); end

%第一层代码表示工序 Chrom(j,i)= val;

WPNumberTemp(val)=WPNumberTemp(val)-1; %第二层代表表示机器

Temp=Jm{val,MNumber-WPNumberTemp(val)};

SizeTemp=length(Temp); %随机产生工序机器

3

图1 种群均值和最优解的变化

图2 最优装卸货任务分配

4 结论

本文将遗传算法用于解决装卸货任务分配的问题，从仿真的结果来看，具有很好的实用性。通过选择、交叉、变异和替换等方法，使得其具有不确定性，避免了人为的干扰，也证实了用遗传算法解决车间调度问题是很有可行性的。

5 体会与收获

6

通过完成这次作业我有了一些体会,那就是遗传算法有很强的快速随机搜索能力，搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较。由于他有选择、交叉和变异等特点，使得使用概率机制进行迭代时更具有随机性，并且具有扩展性，容易与其他算法结合。但是编程实现比较复杂，而且精确度不是很高。所以在应用上要取其精华去其糟粕。

参考文献:

[1] 罗勇； 陈治亚. 基于改进遗传算法的物流配送路径优

化[J] 118-122 系统工程 2012-8第30卷

[2] 谢胜利,黄强,董金祥等.求解JSP的遗传算法中不可行调

度的方案[J].西安:计算机集成制造系统,2002(11)：902-906.

[3] 方红雨,崔逊学, 基于遗传算法的调度问题研究[J].电脑

与信息技术,2001(2）：1-5.

4