一类模糊环境下的单机排序模型

摘要：本文基于近年来对工件加工时间同时具有恶化和学习效应的排序问题的研究，引入可信性空间的模糊变量，建立了模糊排序模型。通过改进遗传算法，设计基于改进遗传算法的混合智能算法求解模型。最后以具体算例验证了该算法的可行性和有效性。关键词：可信性理论；排序；遗传算法；混合智能算法中图分类号：g642.4文标志码a文章号：1674-93242012）04-0058-02一、研究背景排序问scheduling调度问题筹学和组合优化的一个重要分支。近年来，工件加工时间依赖开工时间的排序问题受到广泛关注，其中工件加工时间具有恶化和学习效应的排序问题受到了广泛的关注和研究lee2004[1]最早考虑了两种效应共同作用的单机模型。现实模型中的参数不一定是确定的，这些不确定性包括随机性和模糊性。模糊集概念由zadeh（1965）出，已经很好地应用于解决各种实际问题方面。为测度模糊事件zadeh（1978）提出了可性测度的概念。但这一理论不满足自对偶性，而自对偶性在理论和应用中是非常重要的概念和liu2002）[2]出了自对偶的可信性测度概念，并于2004年建立了可信性理论已成为研究模糊现象的一个数学分支。二、理论基础设为非空集合为的幂集p中一元素称为一个事件对每一个事件a分一个数cr{a}用表示事件发生的信性义若集数cr满以四公理称之为可信性测度。公理1?摇（定性cr{}=1.理摇（单调性）若a?奂b，则cr{a}≤公理3?摇（自对偶性）对任意件，cr{a}+cr{ac}=1.理4?摇（极性原理）对任意满足supicr{ai}＜0.5的件ai}cr{uiai}=supicr{ai}.义设θ为空集合p为θ的幂集，cr为信性测度。则称三元组θp，）为可信性空间。定义3将信性空间（θpcr到实数集的可测函数定义为模糊变量义4设为可信性空θcr上的模糊变量，则它的隶属函数由可信性测度表示为μ（）=2cr{∧，x∈。义5?摇设ξ为糊变量它期望值为e[ξ]=■cr{ξ≥r}dr-cr{ξ≤r}dr等式右边的两个积分至少有一个有限。三、模型描述记n个工件为j={1，2，l，。模糊环境下，考虑这一组工件在一台机器上加工的排序问题。首先作如下基本假设：①一组工件在初始时刻同时准备加工，工件加工不可中断；②在同一时刻，机器只能加工一个工件；③在一组工件加工结束期间机器不能空闲。记工件j的际加工位置记为则π│jr1=1│rn│为实际加工序列，也就是j重排序的结果。假设每个工件的基本加工时间相同，记为模糊变p，隶属函数为μ，的实际加工时间表示为（p0+（（jj。其中是j开加工时间；αt）为随t加而递增的恶化变量，在模糊环境中t为模糊变量，故恶化效应函数α（）模糊变量；为习指数，其中a=log2x模糊参数∈（，100%于有学习效应，排在后面加工的工件的实际加工时间会减少；同时，在恶化效应的作用下，实际加工时间会随着等待时间变长。单机排序的优化目标，是要找到一种最优的排序方法，使最大完工时间、完工时间之和、加权完工时间之和、最大延时等目标值最小化。在给定排π下，记工件i的工时间为ci=ci（π最大完工时间为cmax=max{ci|i=1，，，n}，完工时间之和为ci，权完工时间和为ωici最大延时为lmax=max{ci-di|i=1，2，，n}其中di为工的i交期但由于加工时间为模糊变量大工时间等优化目标值不能直接进行比较，而要借助于期望值、可信度等特征值来进行比较。即将模糊优化问题转化为等价的确定性优化问题求解。建立模糊单机排序期望值模型，建立如下：假设我们选取期

望值评价准则。期望最大完工时间，期望完工时间之和，期望加权完工时间之和，以及期望最大延时分别记为e[cmax]=max{e[ci│i=1ωicie[lmax]=max{e[ci-di]│i=12ln}。期望值最小化的目标代替模糊变量最小化的问题，将排序问题转化为确定性的问题解决。四、基于改进遗传算法的混合智能算法的模型求解相对于确定性模型，模糊模型中含有不确定的变量使求解难度更大，需要借助于计算机对函数进行编程模拟，并设计基于进化算法的混合智能算法来求出最优解。遗传算法原理简单，实现便捷，求解的过程与实际的目标问题无关，具备良好的并行能力和潜在的全局搜索可能性。考虑到由于遗传算法本身选择压力和种群多样性保持之间的矛盾带来的缺陷，并依据模型的特点，改进遗传算法，更新基于改进遗传算法的混合智能算法用于求解论文提出的排序模型。1.编码设计。排序模型的优化，实际上就是为了找到工件的一个最佳的加工次序，使目标函数值最小化。为了方便问题的在遗传算法中能够被准确地描述，每一个染色体使用一个满足工件优先顺序的正整数序列作为基因位，来描述一个可行的工件加工顺序。例如个工件，，在1台器上加工，工件需要满足如下的优先顺序2→3，即工件2要先于工件3加，那么，可以构可行的工件加工顺序为{1，2，3}，{2，，1}，，，3}。2.种群初始化。已知工件数是n首先要设定遗传算法的种群规模为，代进化的上限为iteration，叉率pc和变异概率pm每一代的种群对应npopsize个染色体v，在满足工件加工优先顺序前提下，每个染色体基因位对应着实际的工件编号c1，c2…cn（×rand染色体内的基因c1……互不重复。然后把这个步骤执行npopsize次，到一组整数排列构成的初始群体：{v1，v2，…vnpopsize}。3.评估适应度函数。适应度函数的构造一般都是直接选取目标函数f（文的目标函数需要通过模糊模拟或不确定模拟，求出模糊的或不确定的目标函数值，将不确定的函数值转化为确定值比较任意的两个染色体的目标函数值，较小的那个作为较优的染色体。然后对这npopsize个个体，按照适应度函数大小进行排列，构成一个新的有序种群v={v1，v2……vnpopsize}。根据文献3]设置评价序函数e（vi）=■，方便对群体中的个体进行评价。4.遗传算子的实施。遗传算法的进化过程中，主要包括以下3个遗传算子：选择算子，交叉算子，变异算子。这些算子对种群实施相应的操作，主要的目的就是在维持种群多样性的同时，能够确保种群在迭代的过程中，适应度较高的个体能够有更多的机会遗传进入子代个体中去。①为了能够更好地对种群进行进化，选择一个合适的选择策略是非常关键的。在实施遗传选择算子的时候，不同的选择策略会给种群带来不同的选择压力，一般，选择压力太大的（轮盘赌选择低种群的多样性并引起种群陷入早熟不收敛到全局最优选压力不足的（如锦标选这造成种群的搜索随机性变强算的收敛速度慢了变这种状况文使用一个自适应的轮盘赌选择策略而平衡种群的选择压力。②在进行交叉操作之前要预定义一个交叉概率pc父代个体在进行交叉操作时要照下述步骤重复npopsize次据pc从父代个体中随机选取两个个体vi和vjj=1…，npopsize进下述的配对，vj1…，后机产生一个系数e，（1如的交叉操作得到两个新的父代个体×（vj2vj1=（1-e）×vi1+e×vj2，然后检查vi1的可行性。如果不可行，不断重复上述步骤，直至得到两个可行解③进行变操作之前要预定义一个变异概率pm父个体在进行变异操作时，在基因窜上随机选取两个变异点，然后进行交换，并进行约束判断，从而得到一个

新的可行的候选子代个体。④对于父代的最优个体，采取精英保留策略，无条件遗传至子代个体中，从而在维持种群多样性的同时，增大种群的选择压力。5.混合智能算法的求解步骤经了选择交叉变异操作后新生的种群就准备进入下轮的迭代进化。整个混合遗传算法将会在一个给定的循环迭代次数下，按照上述的步骤实施进化，本文把上述的遗传算法描述如下：步骤1：随机初始化，产生可行的npopsize个体；步骤2：通过模糊模拟或不确定模拟，计算目标函数值；步骤3：对上述的种群根据目标函数值，进行评价，得到评价适应度函数；步骤4：依照种群约束，对整个种群内的个体进行遗传操作；步骤5依照给定的循环数，重复实施步骤2步4之的过程；步骤6：得到最优解。五、数值算例下面以一个模糊环境下的单机模型为例，目标函数为最大完工时间最小化，具体问题如下：考虑10个工件j={1，，，10}记工件j的实际加工位置记为jj，则{r1│jr1=1，r2││jr1=n}为际加工序列就是j新排序的结果体说果j1：j10分别取值为2，，，，，，，10，，对应π={6，，，，，，，，，8}。设每个工件的基本加工时间p0为角模糊变量101214是j开始加工时间；学习效应函数α（=0.25t学习指数，x~（0.250.30.35每个工件的实际加工时间为（p0+0.25tj始加工时间记为0最大完工时间为cmax=max{ci│i=1，，，10}=cπ（10求解算例，本文使用了仿真编译工具matlab7.0，遗算法的参数设定如下：群体规模npopsize=50，叉概率pc=0.3，变异概率pm=0.1，迭代次数500次应用上面的数据，通运行本文设计的程序，得到了如下的最优结果：最优的实际加工顺序为86273510应大完工时间的最小值为：。六、小结本文在可信性理论的基础上，关注了近年来对工件加工时间同时具有恶化和学习效应的排序问题的研究，对排序理论这一经典的组合优化问题展开研究，在可信性空间建立了模糊排序模型。对排序问题的求解通常具有一定难度，模型中引入的模糊变量更增加了求解模型的难度，本文中设计了基于改进遗传算法的