您的位置:js12345金沙官网登入 > 网络编程 > 遗传算法求解混合流水车间调度问题(HFSP)二:

遗传算法求解混合流水车间调度问题(HFSP)二:

2019-10-06 19:43
  • 编码:对工件进行优先级编码,编码越小,优先级越高。
  • 解码:按照工件优先级进行生产,求出整体完工时间。
  • 目标函数值:整体完工时间。
  • 适应度值:目标函数越小,适应度值越大。
  • 选择:按照轮盘赌方法进行选择。
  • 交叉:按照交叉概率,选择两个父代个体,交叉生成两个子代个体。生成一个随机的交换空间,交换空间内,子1基因来自于父2,子2基因来自于父1;交换空间外,子1基因来自于父1,子2基因来自于父2。注意任意两个零件优先级不能相等。
  • 变异:按照变异概率,随机交换两个基因。
  • 终止条件:迭代固定次数。

简述

  遗传算法(GA)是一种模拟生物进化自然选择过程的非确定性搜索方法,源于达尔文的进化论和孟德尔的遗传定律,由美国 Michigan 大学的 Holland教授在 20 世纪 70 年代首先提出。生物理论指出, 生物个体的各种生命表征是由许多基因共同决定的。同一种群的不同生物个体通常拥有不同的基因,因此对外在环境的适应能力也是不同的。 在自然选择的作用下,一部分环境适应能力较差的个体会死亡被淘汰,而环境适应能力较强的个体则更多地存活下来并繁衍后代, 因此比较适应环境的基因会有较大的概率流传到下一代。 一般情况下子代的平均适应力普遍强于父代。 在基因从父代传递到子代的过程中,一部分基因会因为变异而在子代中产生新的基因,这种变异是随机的,有可能增强子代个体的环境适应力,也有可能会降低子代个体的适应力。
  遗传算法正是仿照上述理论,将一个问题的解空间编码,每一个编码代表一个个体,建立一个包含潜在的解的群体作为种群,在环境作用下通过选择(selection)、交叉(crossover)和变异(mutation)一代代繁衍,由于子代的环境适应力一般优于父代,因此算法最终能够得到问题的较优解。其中,编码中的每一位代表一个基因,环境作用由适应度函数模拟,适应度函数是判断某个解的优劣程度的函数,通常是目标函数本身或其修改形式。选择又称为选择算子,是指参照适应值函数,按照预先选定的策略随机从父代中挑选一些个体生存下来,剩下的个体则被淘汰。交叉是指仿照自然界基因传递的过程交配,对存活下来的父代个体的某些基因进行优化组合,办法是将两个父代个体某些对应位置的基因互换,以产生新的个体。变异是指对编码的某些位置上的基因按一定概率进行的改变。

在本例中,有6个工件,有3道工序,每道工序有2台机器,下面是执行结果:

2.选择策略

最优序列:3 4 6 2 1 5

2.1轮盘赌选择法

轮盘赌选择法是依据个体的适应度值计算每个个体在子代中出现的概率,并按照此概率随机选择个体构成子代种群。轮盘赌选择策略的出发点是适应度值越好的个体被选择的概率越大。因此,在求解最大化问题的时候,我们可以直接采用适应度值来进行选择。但是在求解最小化问题的时候,我们必须首先将问题的适应度函数进行转换,以将问题转化为最大化问题。下面给出最大化问题求解中遗传算法轮盘赌选择策略的一般步骤:

(1)  将种群中个体的适应度值叠加,得到总适应度值==1 ,其中 为种群中个体个数。

(2)  每个个体的适应度值除以总适应度值得到个体被选择的概率

(3)  计算个体的累积概率以构造一个轮盘。

(4)  轮盘选择:产生一个[0,1]区间内的随机数,若该随机数小于或等于个体的累积概率且大于个体1的累积概率,选择个体进入子代种群。

重复步骤(4)次,得到的个体构成新一代种群。

图片 1加工流程图

2.2 随机遍历抽样法

像轮盘赌一样计算选择概率,只是在随机遍历选择法中等距离的选择体,设npoint为需要选择的个体数目,等距离的选择个体,选择指针的距离是1/npoint,第一个指针的位置由[0,1/npoint]的均匀随机数决定。

上图中,第1、2行是第1工序的2台设备,第3、4行是第2工序的2台设备,第5、6行是第3工序的两台设备,纵轴代表时间。按照最优序列3 4 6 2 1 5赋予每个零件优先级,一共用时25.

2.3 锦标赛选择法

锦标赛方法选择策略每次从种群中取出一定数量个体,然后选择其中最好的一个进入子代种群。重复该操作,直到新的种群规模达到原来的种群规模。具体的操作步骤如下:

(1) 确定每次选择的个体数量(本文以占种群中个体个数的百分比表示)。

(2) 从种群中随机选择个个体(每个个体入选概率相同) 构成组,根据每个个体的适应度值,选择其中适应度值最好的个体进入子代种群。

(3) 重复步骤(2)次,得到的个体构成新一代种群。

需要注意的是,锦标赛选择策略每次是从个个体中选择最好的个体进入子代种群,因此可以通用于最大化问题和最小化问题,不像轮盘赌选择策略那样,在求解最小化问题的时候还需要将适应度值进行转换。

首先定义问题的参数:

参考资料

  [1]遗传算法:理论、应用及软件实现/王小平, 曹立明著 西安交通大学出版社,2002

  [2]张琛,詹志辉. 遗传算法选择策略比较[J]. 计算机工程与设计,2009,23:5471-5474+5478

 

 

piecetime = [2 4 6; ... % 设备加工时间 4 9 2; 4 2 8; 9 5 6; 5 2 7; 9 4 3];equsize = [2 2 2]; % 每个工序设备数目piecesize = size(piecetime, 1); % 工件数目prosize = size(piecetime, 2); % 工序数目

在本例中,一共有6个设备,3道工序,设备必须按照1-2-3的工序进行加工,每个工序有2台机器。一共有6个工件。piecetime中行代表工件,列代表工序,内容是加工时间,比如第1行第1列,表示工件1在工序1加工时间为2.

定义遗传算法的参数:

popsize = 20; % 种群规模cr = 0.6; % 交叉概率mr = 0.05; % 变异概率maxgen = 100; % 迭代次数

进行迭代:

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:遗传算法求解混合流水车间调度问题(HFSP)二:

关键词: