一种改进的多目标混合差分进化算法

第２８卷第５期　２０１０年１０月　轻工机糖　Ｌｉｇｈｔ　ＩｎｄｕｓｔｒｙＭａｅ／￣ｅｒｙ　Ｖ０１．２８　Ｎｏ．５　０ｃｔ．２０１０　

［经营・管理］　ＤＯＩ．１０．３９６９／ｊ．ｉｓｓｎ．１００５－２８９５．２０１０．０５．０３３　

决作　车间调度问　晌　

混合　分进　法　

周萧，王万良，徐新黎　

（浙江工业大学信息学院，浙江杭州３１００２３）　

摘要：文章提出了一种改进的差分进化算法一混合差分进化算法（Ｈｙｂｒｉｄ　Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ）来解决作业　车间调度问题。为了防止基本差分进化算法陷入早熟收敛和局部最优，从２个方面对算法进行了改进。首先为了在进　化初期能够保持种群多样性，后期减少缩放因子对最优解的破坏，提出了自适应的缩放因子Ｆ。其次交叉操作时采用分　组交叉思想。通过对作业车间调度问题的研究，改进后的算法全局寻优能力和鲁棒性有了明显改进。图１表３参９　关键词：生产管理；混合差分进化算法；自适应缩放因子；分组交叉；作业车间调度问题　中图分类号：Ｆ２７３　文献标志码：Ａ　文章编号：１００５－２８９５（２０１０）０５－０１２１－０４　

Ｈｙｂｒｉｄ　Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ｓｏｌｖｉｎｇ　Ｊｏｂ　Ｓｈｏｐ　Ｓｃｈｅｄｕｌｉｎｇ　Ｐｒｏｂｌｅｍｓ　

ｚＨ０Ｕ　Ｘｉａｏ．ＷＡＮＧ　Ｗａｎ—ｌｉａｎｇ。ＸＵ　Ｘｉｎ．１ｉ　

（ＣｏＵｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　３１００２３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ＤＥ　ａｌｇｏｒｉｔｈｍ，ｎａｍｅｄ　ＨＤＥ　ｔｏ　ｓｏｌｖｅ　ｊｏｂ　ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　

ａｖｏｉｄ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｆａｌｌｉｎｇ　ｉｎｔｏ　ａ　ｌｏｃａｌ　ｏｐｔｉｍｕｍ　ａｎｄ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ．Ｈｙｂｒｉｄ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　

基于分解的多目标优化算法

多目标优化问题（MOP）的目标函数有两个或两个以上，其解通常是一组Pareto最优解。采用传统的优化算法处理多目标优化问题时不能达到令人满意的效果。文字研究基于分解的多目标进化算法（MOEA/D），该算法将一个多目标优化问题分解为一组单目标优化问题并对它们同时优化，通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，比其他同类的优化算法具有更低的计算复杂度。在0—1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现得更加出色或者表现相近，未来该算法具有较大的发展空间。

一、多目标优化问题溯源

多目标优化问题首先由法国经济学家V.Pareto在研究经济平衡时提出，并且引进和推广了Pareto最优解。多目标优化问题中的每个目标称为子目标。各个子目标之间的相互影响和作用，使得对多目标优化时不仅仅是满足每个子目标的最优化条件，而且要满足子目标间相互关系的约束条件。因为子目标间的关系也就是子目标约束条件往往是复杂的，有时甚至是相互矛盾的，所以多目标优化问题实质上是处理这种不确定的子目标约束条件。Pareto最优解，也就是说找不到比这个更好的解了，使得至少有一个目标函数有提升。也即找不到一个解使得每一个目标函数都比它更不糟糕的解。而弱Pareto最优解是指不存在一个点使得每一个目标函数相对于现在这个点都有提升，即找不到一个解使得每个目标函数值都比它好。

所谓的目标优化问题，一般就是指通过一定的优化算法获得目标函数的最优化解。当优化的目标函数为一个时称之为单目标优化，当优化的目标函数有两个或两个以上时称为多目标优化。不同于单目标优化的解为有限解，多目标优化的解通常是一组均衡解。显而易见，多目标优化问题比单目标优化问题更接近工程实践，同时更加复杂。很多工程实践中的优化问题最后都可以转化为多目标优化问题，因此，对多目标优化问题的深入研究对于实践应用更具价值。通常，多目标优化问题都是通过一定的算法实现求解的。

第３０卷第１期　计算机仿真　２０１３年１月　

文章编号：１００６—９３４８（２０１３）０１一Ｏ３８９一刚ｌ　

改进的组合差分进化优化算法　

董明刚　，王宁　，程小辉　

（１．桂林理工大学信息科学与：工程学院，广西桂林５４１００４；２．浙江大学工业控制技术国家重点实验室，浙江杭州３１００２７）　

摘要：组合差分进化算法ＣｏＤＥ是一新的具有竞争力的算法，但收敛速度和寻优性能仍有待改进。为解决上述问题，提出对　组合差分进化算法ＣｏＤＥ从生成策略和控制参数两个方面进行改进，提出了两种改进的ＣｏＤＥ版本ＭＣｏＤＥ和ＭＣｏＤＥ—Ｐ，并　利用６个典型的测试函数对改进性能进行检验。结果表明结合了最好个体信息的ＭＣｏＤＥ方法能够改善ＣｏＤＥ的寻优性能，　

而采用控制参数扩展的ＭＣｏＤＥ—Ｐ方法却难以达到期望的效果。　关键词：组合差分进化；改进；优化算法；生成策略；控制参数　中图分类号：ＴＰ２０２．７　文献标识码：Ａ　

Ｉｍｐｒｏｖｅｄ　Ｃｏｍｐｏｓｉｔｅ　Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ　

ＤＯＮＧ　Ｍｉｎｇ－ｇａｎｇ　一，ＷＡＮＧ　Ｎｉｎｇ　，ＣＨＥＮＧ　Ｘｉａｏ＿ｈｕｉ　

（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ　Ｇａｎｇｘｉ　５４１００４，Ｃｈｉｎａ；　

２．Ｎａｔｉｏｎａｌ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｄｕｓｔｒｉａｌ　Ｃｏｎｔｒｏｌ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ　Ｚｈｅｊｉａｎｇ　３１００２７，Ｃｈｉｎａ）　

ＡＢＳＴＲＡＣＴ：ＣｏＤＥ，ｔｈｅ　ｃｏｍｐｏｓｉｔｅ　ｄｉｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ｉｓ　ａ　ｎｅｗ　ｃｏｍｐｅｔｉｔｉｖｅ　ａｌｇｏｒｉｔｈｍ，ｂｕｔ　ｔｈｅ　ｃｏｎｖｅｒ－　

差分进化算法原理

差分进化算法是一种基于群体智能的优化算法，由Storn和Price于1995年提出。该算法通过模拟生物遗传进化的过程，在群体中引入变异、交叉、选择等操作，从而优化目标函数。相对于传统优化算法，差分进化算法具有收敛速度快、全局搜索能力强等优点，因此在实际工程优化中得到广泛应用。

差分进化算法的基本原理是通过不断改进目标函数来优化群体中的个体。算法的基本流程如下：

1. 初始化：随机生成足够多的初始个体，构成初始群体。

2. 变异：对于每个个体，根据固定的变异策略生成一个变异个体。

3. 交叉：将原个体和变异个体进行交叉，得到一个新的个体。

4. 选择：从原个体和交叉个体中选择更优的一个作为下一代的个体。

5. 更新群体：将新个体代替原个体，同时保留所有代的最优解。

变异策略和交叉方法是差分进化算法的核心部分。

1. 变异策略：

变异策略是指在进化过程中，对每个个体进行的变异操作。常用的变异策略有DE/rand/1、DE/rand/2和DE/best/1等。“DE”表示差分进化， “rand”表示随机选择其他个体进行变异，“best”表示选择当前代的最优解。

以DE/rand/1为例，其变异操作步骤如下：

（1）从群体中随机选择两个个体（除当前个体之外）；

（2）根据固定的变异因子F，生成一个变异向量v；

（3）计算原个体与变异向量v的差分，得到新的个体。

变异因子F的值通常取0.5-1.0，表示变异向量中各项的取值在变量取值范围内随机变化的程度。

2. 交叉方法：

交叉方法是指在变异个体和原个体之间进行的交叉操作。常用的交叉方法有“二项式交叉”和“指数交叉”等。 以二项式交叉为例，其交叉操作步骤如下：

（1）对于变异向量v中的每一维，以一定的概率Cr选择变异向量中的该维，否则选择原个体中的该维；