(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201810803005.6(22)申请日 2018.07.20
(71)申请人 九江学院
地址 332000 江西省九江市前进东路551号(72)发明人 张含叶 梁伟杰
(74)专利代理机构 南昌新天下专利商标代理有
限公司 36115
代理人 谢德珍(51)Int.Cl.
G06Q 10/04(2012.01)G06N 3/12(2006.01)G06Q 50/04(2012.01)
(54)发明名称
一种基于免疫遗传算法求解第一类装配线平衡问题的方法(57)摘要 平衡问题的方法，
该方法定义了一个函数ψ(∙)使种中的个体满足装配优先关系约束，并给出了第一类装配线平衡问题的约束条件和目标函数，最后构建了免疫遗传算法求解第一类装配线平衡问题，该方法包括函数ψ(∙)的定义，约束条件，目标函数，免疫遗传算法；其中免疫遗传算法包括：设定参数、初始化、更新种、更新记忆库、终止条件验证和结果输出。本发明将人工免疫算法和遗传算法结合起来，建立一种综合性能更好的混合算法，可用于解决第一类装配线平衡问题，例如用于求解APXV9R20B天线装配线平衡问 题。
权利要求书4页 说明书10页 附图2页
CN 109146136 A 2019.01.04
C N 109146136
A
1.一种基于免疫遗传算法求解第一类装配线平衡问题的方法，其特征在于，该方法包括以下步骤：
1）函数ψ(∙)的定义：
A*， 满足：
(1) 如果 则交换矩阵A中 和
的位置；
(2) 如果 则矩阵A中 和
位置保持不变；
其中，
n 代表装配任务的总数目；矩阵A中的任意列均代表n的一个全排列；
2） 约束条件包括：
一个装配作业元素只能分配到一个工作站中
其中，k表示装配工作站的序号，M表示装配工作站的总数，i表示装配作业元素的序号； 装配优先约束关系约束
其中，j表示装配作业元素的序号；
装配节拍约束（即，任一工作站的装配时间不得大于装配节拍）
其中，N表示装配作业元素的集合，t i表示第i个作业元素的装配时间，C表示装配节拍；
变量的取值范围
3）目标函数：
其中，f1表示最小化工作站数，f2表示最小化平滑指数，w1和w2均表示权重系数；
所述最小化工作站数为
其中， m表示装配工作站的序号；
所述最小化平滑指数为
其中， ST k表示第k个装配工作站的装配时间；
因此，目标函数的计算公式为：
（1）
4）免疫遗传算法：
步骤一：设定参数
(1) PS：种规模；
(2)P c：交叉概率；
(3) P m：变异概率；
(4) P i：免疫接种概率；
(5) ：相似度阈值， ；
步骤二: 初始化：
随机生成PS个初始个体，把这PS个初始个体记为矩阵A，且对其进行操作，使满足
A*；
步骤三: 更新种：
(1)交叉操作：
令，其中 表示大于或等于x的最小正整数；如果M1为奇数，则M1←M1-1；
首先，从第t代种A(t)中随机选取M1个个体构建矩阵；接着，从 中随机
选取两个个体执行交叉操作，原理如图1所示，经过交叉操作后的矩阵记为；最后，
对 执行 操作，并令 ；
(2) 变异操作 ：
令 ；首先，从第t代种A(t)中随机选取M2个个体构建
矩阵；接着，对 中的所有个体进行变异操作，原理如图2所示，经过变异操
作后的的矩阵记为；最后，对执行 操作，并令
；
(3) 免疫接种操作：
令，P g代表记忆库中的接种疫苗；首先，从第t代种A(t)
中随机选取M3个个体构建矩阵；接着，对中的所有个体和P g进行交叉操作，
原理如图1所示，经过交叉操作后的的矩阵记为；最后，对执行
操作，并令 ；
(4) 抗体生存期望选择：
令 ，中所有
个个体的生存期望根据公式进行计算，并对结果进行升序排列，选择前PS个个体构成下一代种A(t+1)；
其中，
其中，表示抗体u和抗体v在第j位基因上的基因值相等，即抗体u 和抗体v具有等位基因j；
表示抗体u和抗体v具有等位基因的总个数；
步骤四: 更新记忆库：
矩阵A(t+1)中所有M个个体的目标函数根据公式(1)进行计算，并把具有最小目标函数的
个体记为；如果 ，则
；否则，；
步骤五: 终止条件验证：
一般而言，算法只要满足下面三个条件中的任意一个，则终止迭代；
（1）最优个体的适应度达到给定的阈值；
（2）最优个体的适应度和体的适应度不再上升；
（3）迭代次数达到预设的代数；
其中，选择条件（2）作为算法的停止条件，即在算法的迭代过程中，一旦最优个体的适应度和体适应度不再上升，则停止迭代，进入步骤六；否则，转入步骤三；
步骤六: 结果输出：
输出最佳装配线平衡结果。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议