基于混合蚁群算法的多目标优化产品配置方法

摘要

本发明提供一种基于混合蚁群算法的多目标优化产品配置方法，包括如下步骤：（1）根据客户产品订单的不同情况，把各订单分成多个生产阶段；（2）得到各订单的生产结点，确定各订单的生产时刻，计算该订单产品在该订单的生产时刻的生产成本；（3）确定各订单是否安排生产；（4）确定需要生产的订单的调度方案；（5）输出调度方案，安排生产。通过此方法，可以优化生产调度，合理分配生产时间。

说明书

技术领域

本发明涉及一种基于混合蚁群算法的多目标优化产品配置方法，属于大规 模定制模式下生产计划柔性规划调度领域，主要针对多目标优化问题。

背景技术

目前，对产品配置的研究方向主要是针对模型的表示以及算法的求解展 开，其常用算法主要采用智能优化算法求解，其中的代表有人工鱼群算法、遗 传算法、人工免疫算法、运用判定树和最小冲突修改算法等。

以上方法在一般配置问题上可以较为满意地快速求解，但是仍存在部分不 足：

广义：从多目标优化的产品配置的特点来定义

1、仅仅是针对产品的结构模型和功能模块，以模型的相似度为分类依 据，大都只以最小生产成本为目标的算法。然而在大规模定制模式下，企业的 产品配置应涉及到整个产品的生命周期，应将库存成本、客户满意度、动态空 余生产能力、动态生产质量等一系列新的优化目的和约束纳入考量范围。

2、传统的产品配置方案并未引入按时间基准调度的机制，只是在遇到紧 急订单时，一味地将紧急订单作为作为最优先目标进行完成，而不对其合理性 进行分析。

3、现阶段的产品配置方案主要针对是单一产品在企业内的生产过程的配 置方式，没有体现生产阶段的衔接问题。

狭义：从算法本身结构组成进行讨论

1、现有的一般智能优化算法主要采用单种寻找方式或是单种信息素算 法，功能较为单一，主要模拟了实际信息搜索系统的一部分。而事实上，在真 实的生活中任何复杂系统都是有组织的、有分工的，不同的搜索路径都有不同 的信息素调控机制。

2、将产品配置算法作为一个系统来研究其重要的一个特性是自组织，这 是所有的智能优化算法的一个共同特征。反馈在系统学上的定义为影响系统将 来行为的现在行为。最优路径上信息素的堆积，作为正反馈使算法朝最优方向 前进，然而实际自然界中的路径结点都有其固有的饱和度，容易造成结点的生 产拥塞。

3、当搜索空间加大时，由于搜索结点呈数量级上升，系统搜索的重复性 大大提高，搜索效率明显下降。

4、在多目标优化问题的前提下，依靠结构模型和功能模块的特点，虽然 限制了一定的无效配置的产生，然而系统的收敛性仍然较差，产品容易产生大 量的可行配置，需要人工进行再次优化。

本发明专利在基于以上研究的基础上，对于大规模定制生产模式下求解多 目标优化问题(multi objective optimization problem，MOP)，研究了一种 含多蚁群、多信息素的混合多态蚁群算法(polymorphic ant colony  algorithm，PACA)。并提出网格划分策略，研究了时序约束条件下的混合蚁群 算法。建立了相关的多目标矩阵和多目标约束，并提出了合适的混合蚁群算法 步骤。

发明内容

本发明的目的是为了解决上述技术问题，提供一种基于混合蚁群算法的多 目标优化产品配置方法，以期实现对订单产品的更优化的处置方式，更大地利 用现有资源。

本发明采取的技术方案是：

一种基于混合蚁群算法的多目标优化产品配置方法，包括如下步骤：

(1)根据客户产品订单的不同情况，把各订单分成多个生产阶段；

(2)得到各订单的生产结点，确定各订单的生产时刻，计算该订单产品 在该订单的生产时刻的生产成本；

(3)确定各订单是否安排生产；

(4)确定需要生产的订单的调度方案；

(5)输出调度方案，安排生产。

进一步，所述第(2)步是通过以下算法来确定参数的：

通过量化订单的数学模型，提供：

目标函数：

$\underset{C}{{\min Z}_1}=\underset{k=1}{\overset{K}{\Sigma }}\underset{r=1}{\overset{N_k}{\Sigma }}\underset{h=1}{\overset{G}{\Sigma }}\underset{j=1}{\overset{N_m}{\Sigma }}\{C_{\mathrm{abc}}^{\mathrm{xy}}\left(t_k\right)+k_{\mathrm{abc}}^{\mathrm{xy}}{T}_{\mathrm{abc}2}^{\mathrm{xy}}\}$

$\underset{t}{{\min Z}_2}=\left|T_{\mathrm{abcexp}}^{\mathrm{xy}}\left(t_k\right)\right[T_{\mathrm{abc}1}^{\mathrm{xy}}\left(t_k\right)+T_{\mathrm{abc}2}^{\mathrm{xy}}\left(t_k\right)\left]\right|+\Pi$

模型约束：

$\underset{h=1}{\overset{G}{\Sigma }}\underset{j=1}{\overset{N_m}{\Sigma }}{S}_{\mathrm{abc}.\exp }^k\left(t_k\right)\le \underset{r=1}{\overset{N_k}{\Sigma }}{S}_{\mathrm{abc}.\mathrm{all}}^k\left(t_k\right)$

式中，K为订单产品的生产阶段总数；k为K个生产阶段中的索引；N_k为 第k个生产阶段中所拥有的生产结点数量；r为第k个生产阶段中的生产 单元索引；G为t_k时刻所包含的产品订单种类；h为集合G中订单种类的索 引；N_m为每类订单的产品总数；j为集合N_m中的索引；t_k为订单i的第k 个生产阶段的起始时间；为t_k时刻第(a，b，c)个产品在生产结点 (x，y)的生产成本；为第(a，b，c)个产品在生产结点(x，y)的单位库存成 本；为客户对第(a，b，c)个产品在生产结点(x，y)的期望生产时 间；为第(a，b，c)个产品在生产结点(x，y)的实际生产时间；为第(a，b，c)个产品在生产结点(x，y)的额外库存时间；Π设为企业的不可 逆延期因素，引入作为延期交货容忍参数，可设为定值；为tk时 刻集合N_k所能提供的生产能力总和；为t_k时刻产品所需要的生产 能力。

本发明的有益效果是：

对于大规模定制生产模式下求解多目标优化问题(multi objective  optimization problem，MOP)，通过一种含多蚁群、多信息素的混合多态蚁群 算法(polymorphic ant colony algorithm，PACA)。并提出网格划分策略， 研究了时序约束条件下的混合蚁群算法。建立了相关的多目标矩阵和多目标约 束，并提出了合适的混合蚁群算法步骤，对订单的生产进行了优化。

附图说明

附图1是本发明在MC模式下产品配置结构示意图；

附图2是本发明生产结点网格划分示意图；

附图3是本发明时序约束下的产品配置有向图；

附图4是本发明各类订单的多目标权重决策程序框图；

附图5是本发明多目标优化中产品配置的程序框图。

具体实施方式

下面结合附图对本发明基于混合蚁群算法的多目标优化产品配置方法的具 体实施方式作详细说明。

1、参见附图1，建立产品订单的量化数学模型，为蚁群寻优算法提供目标 函数和约束条件。

目标函数：

$\underset{C}{{\min >}_1}=\underset{k=1}{\overset{K}{\Sigma }}\underset{r=1}{\overset{N_k}{\Sigma }}\underset{h=1}{\overset{G}{\Sigma }}\underset{j=1}{\overset{N_m}{\Sigma }}\{C_{\mathrm{abc}}^{\mathrm{xy}}\left(t_k\right)+k_{\mathrm{abc}}^{\mathrm{xy}}{T}_{\mathrm{abc}2}^{\mathrm{xy}}\}---\left(1\right)$

模型约束：

$\underset{h=1}{\overset{G}{\Sigma }}\underset{j=1}{\overset{N_m}{\Sigma }}{S}_{\mathrm{abc}.\exp }^k\left(t_k\right)\le \underset{r=1}{\overset{N_k}{\Sigma }}{S}_{\mathrm{abc}.\mathrm{all}}^k\left(t_k\right)---\left(3\right)$

式中，K为MC模式下对定制产品的生产阶段总数；k为K个生产阶段中的 索引；N_k为第k个生产阶段中所拥有的生产结点数量；r为第k个生产阶段中 的生产单元索引；G为t_k时刻，所包含的产品订单种类；h为集合G中订单种类 的索引；N_m为每类订单的产品总数；j为集合N_m中的索引；t_k为订单i的第k 个生产阶段的起始时间；为t_k时刻第(a，b，c)个产品在生产结点(x，y)的 生产成本；为第(a，b，c)个产品在生产结点(x，y)的单位库存成本；为客户对第(a，b，c)个产品在生产结点(x，y)的期望生产时间；为第 (a，b，c)个产品在生产结点(x，y)的实际生产时间；为第(a，b，c)个产品 在生产结点(x，y)的额外库存时间；Π设为企业的不可逆延期因素，引入作为 延期交货容忍参数，可设为定值不作讨论；为tk时刻集合N_k所能提供 的生产能力总和；为t_k时刻产品所需要的生产能力。

在多目标优化问题中，产品的配置过程往往涉及到n个因素，其权重关系 主要由客户定夺。本发明专利通过改进的层次分析法，对于任意两因素之间的 定性语言进行量化，从而为众多因素建立层次化结构，为系统建立产品模型提 供依据。

引入函数g(x，y)表示在系统综合评价下因素x对比因素y的重要性标度。

设K个顾客订单的属性集为W＝[w₁，w₂，w₃，…w_n]，W_nm订单属性集W的具体要 求，建立产品配置的评语集Q＝[L₁，L₂，L₃，L₄]，定义α：W→L使评判函数，则可获 得客户对于W的综合评判集W_nm。

W_nm＝f(α(α₁)，α，α₂)，…，αα(_n))

式中，i＝1，2，…，N；L₁、L₂、L₃、L₄为不同的比例参数，且L₁＜L₂＜_L，《L₄。定 义L₁＝1、L₂＝2、L₃＝3、L₄＝6。(此处所设参数为举例所用，并不一定是本发明专 利的规定参数，可由客户确定该系数)

定义订单需求集的权重集合为R＝[r₁，r₂，r₃，…r_n]，采用归一化权向量： 为实现产品配置总体最优建立加权平均型目标函数：

$f\left(W\right)=\underset{n=1}{\overset{K}{\Sigma }}{R}_n{W}_{\mathrm{nm}}---\left(6\right)$

构造评价指标的判断比率矩阵

$Q=\stackrel{\left(\begin{array}{cccc}{q}_1& q_2& ···& q_n\end{array}\right)}{\left(\begin{array}{cccc}{q}_{11}& q_{12}& ···& q_{1n}\\ & & & ·\\ q_{21}& q_{22}& ···& ·\\ & & & ·\\ ·& ·& & ·\\ ·& ·& & ·\\ ·& ·& & ·\\ q_{n1}& ···& ···& q_{\mathrm{nn}}\end{array}\right)}\left(\begin{array}{c}{q}_1\\ q_2\\ q_3\\ q_4\end{array}\right),Q\to R---\left(7\right)$

设a_ij＝f(q_i，q_j)，求解判断比率矩阵特征向量，构造模糊关系矩阵：

${W_{\mathrm{nm}}}^{*}={\left(\frac{r_i}{r_j}\right)}_{n\times n}={\left(a_{\mathrm{ij}}^{*}\right)}_{n\times n}---\left(8\right)$

$\left(\begin{array}{cccc}\frac{r_1}{r_1}& \frac{r_1}{r_2}& ···& \frac{r_1}{r_n}\\ & & & ·\\ \frac{r_2}{r_1}& \frac{r_2}{r_2}& ···& ·\\ & & & ·\\ ·& ·& & ·\\ ·& ·& ···& ·\\ ·& ·& & ·\\ \frac{r_n}{r_1}& ···& ···& \frac{r_n}{r_n}\end{array}\right)\left(\begin{array}{c}{r}_1\\ r_2\\ ·\\ ·\\ ·\\ r_n\end{array}\right)=n\left(\begin{array}{c}{r}_1\\ r_2\\ ·\\ ·\\ ·\\ r_n\end{array}\right)---\left(9\right)$

根据图1的调整流程，针对紧急订单和非紧急订单的优化运做主线，将公 式(5)带入目标函数和模型约束，建立判断矩阵。以此为依据分别建立非紧 急订单和紧急订单的优化目标函数。

设综合成本Z₁、综合生产时间Z₂分别与q₁、q₂呈映射关系，顾客订单在t_k时刻、第k个生产阶段中的其余生产参数分别和q₃…q_n呈映射关系。

综上所述，第一类产品订单(非紧急订单)，设n＝5，且q₃代表产品额外库 存、q₄代表产品综合质量、q₅代表生产能力饱和度，由公式(6)-(9)计算 可得。

$W_{\mathrm{nm}11}=\left(\begin{array}{ccccc}1& 6& 6& 2& 2\\ \frac{1}{6}& 1& \frac{1}{2}& \frac{1}{3}& \frac{1}{2}\\ \frac{1}{6}& 2& 1& \frac{1}{3}& 1\\ \frac{1}{2}& 3& 3& 1& 2\\ \frac{1}{2}& 2& 1& \frac{1}{2}& 1\end{array}\right)$

采用和法对其进行求解，得到归一化后的权向量为

B₁₁＝(0.4333，0.0687，0.1070，0.2474，0.1436)

故建立一下目标优化总函数。

minf(W)₁₁＝0.4333w₁+0.0687w₂+0.1070w₃+0.2474w₄+0.1436w₅(10)

第二类产品订单(紧急订单)

首先，采用公式(10)建立数学模型：

minf(W)₂₁＝0.4333w₁+0.0687w₂+0.1070w₃+0.2474w₄+0.1436w₅(11)

判断此时是否满足约束条件公式(4)。

满足输出，如不满足调整目标参数集，建立以下矩阵：

$W_{\mathrm{nm}22}=\left(\begin{array}{ccccc}1& \frac{1}{6}& \frac{1}{2}& 2& 1\\ 6& 1& 6& 3& 2\\ 2& \frac{1}{6}& 1& \frac{1}{2}& 1\\ \frac{1}{2}& \frac{1}{3}& 2& 1& 2\\ 1& \frac{1}{2}& 1& \frac{1}{2}& 1\end{array}\right)$

采用和法对其进行求解，得到归一化后的权向量为

B₂₂＝(0.1297，0.4637，0.1154，0.1641，0.1271)

minf(W)₂₂＝0.1297w₁+0.4637w₂+0.1154w₃+0.1641w₄+0.1271w₅(12)

3、本发明采用网格划分策略，设结点数变量为n，并将其等分为K等份， 从而将n个变量的决策转变为K级决策问题。将其导入实际生产结点集合后， 采用生产阶段为依据对实际生产结点集合进行初级网格划分。在不能等分的前 提下引入虚拟生产结点概念，并将其设为绝对禁入结点，从而可以将蚁群算法 的空间复杂度降低一个数量级。网格划分方式如图2所示。

4、以产品订单时序为约束条件，对生产结点集合进行第二次分类。针对 复杂产品订单，在第一次划分得到各阶段生产关系的基础上，以客户要求的产 品生产阶段起始和截止时间为约束条件，完成各类产品协同制造链的有向图定 制划分。其制造任务的结构可采用图3所示方式表示。

综上所述，根据第一次和第二次划分的结果，可以确定在tk时刻蚁群算法 中每一类蚂蚁所对应的生产结点，从而确定算法的可行域，进一步降低该算法 的空间复杂度。

6、本发明专利采用混合蚁群算法进行产品配置

在本次算法中，在t时刻蚂蚁k由元素i转移到元素j的状态转移概率 为：

其中，α为信息启发式因子，表示轨迹的相对重要性，其值越大，蚂蚁间 协作越强；β为期望启发式因子，表示能见度的相对重要性，其值越大，转移 概率越接近贪心规则。η_ij(t)为启发函数，其表达式定义为：τ_ij(t)为信 息量函数根据信息素更新策略不同，采用模型：

信息素更新规则如下：

${\tau }_{\mathrm{ij}}(t+n)=(1-\rho )\times {\tau }_{\mathrm{ij}}\left(t\right)+{\mathrm{\Delta \tau }}_{\mathrm{ij}}\left(t\right),{\mathrm{\Delta \tau }}_{\mathrm{ij}}\left(t\right)=\underset{k=1}{\overset{m}{\Sigma }}{\mathrm{\Delta \tau }}_{\mathrm{ij}}^k\left(t\right),$挥发系数$\rho ⋐\left[\mathrm{0,1}\right).$

混合蚁群算法作为一种求解多目标优化问题，此时各个目标之间往往是相 互制约或是冲突的。可以说，在多目标优化的前提下，解的优劣具有一定的相 对性，而蚁群的信息素也应具有一定的差异性。当蚂蚁i在寻优时，同伴所释 放的信息量θ_i应有相应的差异。根据2.2节所建立的多目标模糊产品模型，且 定义B→θ_i，设定蚂蚁X_ij在生产结点(x，y)进行生产的概率为：

$P_{\left(\begin{array}{ccc}B& \mathrm{ij}& \mathrm{xy}\end{array}\right)}^A=B·P_{\left(\begin{array}{cc}\mathrm{ij}& \mathrm{xy}\end{array}\right)}^{\left(A\right)}---\left(15\right)$

默认参数设置为α＝1，β＝1，ρ＝0.2，最大循环次数为200。按照2.2节中 的描述确定多目标参数同各类蚁群遗留信息素量的关系，确定其概率公式为：

a、第一类订单

$P_{\left(\begin{array}{ccc}B& \mathrm{ij}& \mathrm{xy}\end{array}\right)}^{A1}=0.4333P_1+0.0687P_2+0.1070P_3+0.2474P_4+0.1436\left(\begin{array}{cc}1& P_5\end{array}\right)---\left(16\right)$

b、第二类订单

式中，(x，y)生产结点中第k类要素对蚂蚁A_ij的吸引概率为 $P_n=\frac{{\delta }_{\left(\begin{array}{cc}\mathrm{ij}& \mathrm{xy}\end{array}\right)}^n}{\underset{j=1}{\overset{m}{\Sigma }}{\delta }_{\left(\begin{array}{cc}\mathrm{ij}& \mathrm{xy}\end{array}\right)}^n},$i≠j，i，j＝1，2，…，N；为信息素量。

7、简单描述本发明专利的设计过程，参见附图4、5所示：

步骤1、根据客户产品订单的不同情况，企业由图二所示流程确定动态调 度调整时刻。

步骤2、算法开始，根据产品订单的信息类型，形成不同的生产任务类 别，构造相应的蚂蚁类别与之对应。

步骤3、通过模糊决策方案对于不同类型的蚁群构造其判断比率矩阵，从 而确定多目标问题的优化函数，确定各项权重指数。

步骤4、为每类蚂蚁设定相应的禁入结点，确定可行域。

步骤5、通过网格划分和时序约束条件缩小搜索空间，并确定各订单的起 始时刻和计划生产时间。

步骤6、根据订单类型，按照2.2节中的描述确定多目标参数同各类蚁群 遗留信息素量的关系，以确定选择不同生产结点的概率。

步骤7、将时间t和循环次数N设置为零，设置最大循环次数。令每条边 (i，j)上的初始化信息量为τ_ij(t)＝const(const为常数)，且设置初始初始时刻 Δτ_ij＝0。

步骤8、在源点生成第N_c批次的蚂蚁，每批次包含包含该批次中各类蚂 蚁，设各类蚂蚁的数量均为100。所有蚂蚁根据步骤六所确定的概率公式采用 赌轮法选择路径，并更新信息素。

步骤9、记录该批次中通过各结点的蚂蚁数量，并记录相对应的优化目标 值。

步骤10、更新最优路线信息值，循环次数N_c←N_c+1，同时转回步骤八。

步骤11、达到最大循环次数结束，输出。计算此时的优化目标。判断是否 满足模型的约束条件。如符合转步骤十二，否则转步骤三。

步骤12、根据记录各类蚂蚁在生产结点上的分配情况，进行产品配置的调 度工作。

综上所述，在大规模定制生产模式下，企业对于生产系统的柔性作业效率 要求将不断提高。基于此种前景，本发明针对客户对于订单的综合评判集，建 立了多目标优化模型；并提出了一种混合蚁群算法。在本发明专利中，算法对 于生产阶段的每一时刻均具有通用性，增强了算法的退化机制，引入生产能力 饱和度，消除了结点的拥塞问题；并采用模糊层次分析法量化了多目标优化问 题的权重向量；最后，依靠网格划分和时序约束进一步缩小了求解空间，是解 决多任务复杂设备产品配置过程求解的较好手段。

在大规模定制生产模式下，客户对定制产品的复杂性不断提高，庞大复杂 配置数据的无序处理成为了制约企业良性发展的主要约束。本发明以客户需求 为驱动，提高了柔性产品配置调度规划的有效性。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通 技术人员，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些 改进和润饰也应视为本发明的保护范围。