基于遗传算法的作业单位的确定

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于遗传算法的作业单位的确定范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：遗传算法是模仿生物的进化过程,运用达尔文进化论“适者生存”原理的现代启发式算法[5~7]，通过模拟遗传操作（交叉运算和变异运算） 在解空间搜索，通过选择操作在解空间寻优。本文在SPL方法获得作业单位的综合关系表的基础上，采用遗传算法求得最佳的或满意的布局方案。

关键词：遗传算法;最优解

中图分类号：O1文献标识码：A文章编号：1673-0992（2011）01-0396-01

引言

ヒ糯算法的基本原理[6~8]如下：

ゼ俣考虑全局优化问题（P）：max{F(x):x∈Rn}，F:ΩRnR1,则求解问题（P）的一个不变规模（假设为N）的模拟进化计算抽象描述如下：

Step1：随即初始化种群X(0)={X1(0),X2(0),…,XN(0)}，置k=0；

Step2：计算当前种群的每一个体Xi(k)的适应度值（i=1,2,…，N）；

Step3：依据适应性指定其相应个体的复制概率；

Step4：依据所指定的复制概率，通过交叉、变异等遗传机制产生适量的新一代种群的侯选种群；

Step5：依据某种选择规则，从侯选种群中确定新一代种群X（k+1）；

Step6：检验当前种群是否产生满意解或者己经达到预设的进化时限，如已满足，停止，否则，令k=k+1，转Step2。

1.遗传编码

ビ靡糯算法求解布局问题，首先将布局问题的解空间映射成一定的代码串，以便各种选择操作。为简化模型需要，将作业单位均假定按纵向排列，并且以从左到右，自上而下的顺序。任意作业单位上下保留间隔空间各Δi/2，作为预留空间。这里采用遗传编码形式为:[m1,m2,m3,…,mn]，其中mi表示i位置的作业单位的序号。

2.适值函数

ナ手岛数[6]就是评价进化过程中各代种群各个染色体的优劣，它是遗传算法操作进行“优胜劣汰”的依据。

ケ疚慕问题的目标函数设定为各作业单位间可行布局中的实际关系密切度与理想布局中的关系密切度之间的方差。遗传算法应用逆向思维，随机产生合法的布局方案，利用遗传选择，优胜劣汰解方案，在数代的种群更替后，逐步收敛到非劣解。

ナ手岛数的具体设定如下:

zij=0,gij=-1且dijd＞5

5-dijd-gij2(else)

テ渲gij=1,2,3,4,5,-1，表示SLP法得出的作业单位间的理论关系密切度，其值分别代表A、E、I、O、U、X(如表6-1)，dij表示作业单位与作业单位j之间的实际距离，d设定为相邻作业单位间的单位距离，5-dijd-gij为作业单位i与j之间实际的关系密切度，如实际距离相距为d时，则实际关系密切度为4 (A 等级)，因此5-dijd-gij2表示作业单位i与j间实际密切度与理论密切度之间的方差。当关系密切度为-1 (即X) 时，表示不可靠近，即要求作业单位间的距离必须大于5d，故此

时z=0。所有作业单位理论与实际密切度的方差之和的最小值，即为最佳的初步布置方案。

ヒ糯操作是遗传算法模拟生物进化，通过交叉和变异改变个体基因，形成对解的改进[7~8]。交叉作用于两个染色体，结合这两个个体的不同基因片断产生两个新的子代；变异运算作用于单个染色体，改变个体的一个或若干个基因产生新的子代.。

a)目标函数的建立

ネü对遗传算法与布置问题的特点的分析，所有作业单位理论与实际密切度的方差之和的最小值，即为最佳的初步布置方案，因此，我们建立如下目标函数：

minz=∑10i=1∑11j=i+1zij

ザ杂dij，假定该厂的物料搬运系统是通过井字形道路运输,故作业单位的实际距离为dij=|xi-xj|+|yi-yj|，作业单位间的单位距离d，按照两作业单位可能的最远距离与相邻距离的差值的6等分(每等分为d，按实际需要Δij=8m。

ピ际条件的挖掘

ビ捎诟髯饕档ピ在厂址中均需占有一定的面积，单元间还需为人员留有一定的活动空间。因此在布局设计中还需考虑一些约束条件。

ナ迪植季值挠呕设计，所需要的约束条件包括：

(1) 间距约束：设备间应保持一定距离，满足，

|xi-xj|≥si+sj2+Δij

|yi-yj|≥li+lj2+Δij

ナ街校(xi,yi)，(xj,yj)分别表示单位i和j的坐标，Δij表示两单位应该流的距离，因为作业单元可以错开布置，因此以上两式至少满足一个即可。

(2) 边界约束：

ザ杂诟髯饕档ピ，布置的范围不能超过厂址的面积，因此，对于各单元均有一定的边界约束。

b) 作业单位位置的确定

ネü目标函数与约束条件的建立，得到布局问题的模型：

minz=∑10i=1 ∑11j=i+1zij

st.zij=0 gij=-1 and dijd＞5

5-dijd-gij2 else

|xi-xj|≥si+sj2+Δij or |yi-yj|≥li+lj2+Δij

xi∈si2,80-si2

yi∈li2,200-li2

ネü运行结果，我们可以得到11个作业单位的中心坐标，如下表：

け6-3 作业单位的中心坐标

根据以上坐标，就可确定11个作业单位的位置，在进行位置分析以及根据实际需要进行微调。

结束语

ビ靡糯算法求解布局问题，首先将布局问题的解空间映射成一定的代码串，以便各种选择操作。为简化模型需要，将作业单位均假定按纵向排列，并且以从左到右，自上而下的顺序。通过模拟遗传操作（交叉运算和变异运算） 在解空间搜索，通过选择操作在解空间寻优。

参考文献：

[1]程国全，物流设施规划与设计[M].中国物资出版社，2003.

[2]叶慕静, 周根贵.基于遗传算法的系统布置设计及初步应用[J].工业工程，2005,5.

[3]玄光男, 承润伟. 遗传算法与工程设计[M]. 北京:科学出版社,2000.

[4]叶慕静, 周根贵.混合遗传算法在带走道的双目标布局问题中的应用[J]. 系统工程理论与实践,2005,10.