论文部分内容阅读
摘 要:现如今,我国的电能计量装置管理模式普遍采用的是“集中检验、统一配送”模式,在这一模式的推动下,我国很多的省级电力公司都依据自身的特点成立了计量检定中心。与此同时,更加注重电力需求侧管理以及电能计量设备管理。正是在这一背景下,电力公司逐步开始对电能计量设备自动检定流水线调度进行优化。本文主要通过对问题的描述,详细的介绍了GATS算法的自动检定流水线调度优化过程,希望能够为电力公司提供帮助。
关键词:电能计量设备;自动检定流水线;调度优化
电能计量设备自动检定流水线是现阶段比较先进的电能检定装置之一,在检定的过程中,能够完全进行自动化操作。但是电能计量设备自动检定流水线调度还有可以优化的空间,如果优化成功,检定效率会更高,所以计量检定中心都十分关注调度优化的问题。
1 电能计量设备自动检定流水线调度问题描述
为了提高智能计量设备自动检定流水线的效率,生产调度中心会依据用户需求、智能立库存储量及检定周期等因素,将不同批次的同类型计量器具(单相电能表)或相同电压等级的不同类型器具(单相电能表和终端)放在一条流水线上进行检定。同时,在至少一个检定环节(如:多功能检定环节)中存在多条独立的并行检定单元,且每个检定单元含有多个检定工位,可实现多批次、多计量设备的同时检测。因此需要将待检器具进行分批组处理,每个批组的大小也可不同。根据上述分析,本文将此类自动检定流水线定义为带批组的并行混合流水线。带批组并行混合流水线调度问题可描述为,N个计量器具分为B个批组在流水线上进行S个环节的检测,各环节至少有一台检定设备且至少有一个环节存在并行的检定设备,同一环节中各检定设备检测同一计量器具的检测时间均相同,每个批组在同一环节的检测时间不完全相同,在每一环节各待检器具均要完成一道工序,但各待检器具的每道工序可在相应环节中的任意并行检定设备上检定,已知待检器具各道工序的检定时间,要求确定所有待检批组的排序以及每一环节中并行检定设备的任务分配情况,从而使得总检定完成时间最小,即最小化最大检定时间,图1为自动检定流水线流程图。
2 基于GATS算法的自动检定流水线调度优化
2.1 遗传禁忌混合算法
遗传禁忌混合算法组由遗传算法与禁忌搜索TS算法组成。这两种算法各具优势,有效结合能够发挥出两者的最大优势。所谓遗传算法简单的说就是将求解的具体问题,转换成生物“染色体”种群,之后一步一步进行进化,最为重要的操作有选择、交叉与变异等。通过各项操作,寻求能够适应环境的最理想个体,进而实现最优解自适应搜索。遗传算法比较适合应用在范围比较大的搜索中,但是局部搜索能力却不强。而所谓禁忌搜索TS算法最突出的优势就是记忆功能强。搜索期间能够接受劣解,跳出局部最优解,因此此种算法的局部搜索能力非常强,但是禁忌搜索TS算法对初始解具有非常强的依赖性。两种算法相结合,既使得禁忌算法搜索效率明显提升,也避免了GA爬坡能力过慢的问题。为了能够让遗传算法与禁忌搜索TS算法结合之后,发挥出最大的优势,研究对遗传禁忌算法进行了改进优化,同时使用精英策略,换言之,找到适应度最前面的精英解,然后将其与非精英解交叉。遗传操作之后,会获得相应的解集,将这些解集适应度进行排位,排位最前的解集就可以成为禁忌算法中的初始解,之后再使用禁忌搜索算法进行相应操作获得最优解,以此代替初始解,待到完全满足条件之后,跳出算法,获得最优解。
2.2 交叉与变异
研究者首先要找到适应度最佳的精英解,将其与非精英解,按照随机方法进行交叉操作,同时对交叉解进行验证,以此查看交叉解是否达到各个约束条件的要求。具体算法步骤如下:首先,选择一个非精英解。该解的随机概率一定要超过预设交叉概率,将其与随机精英解展开交叉操作,再对交叉解展开验证,最为重要的验证内容就是交叉是否符合约束条件要求;其次,交叉后获得子代,将其与非精英父代值进行有效的对比,如果子代解的适应度更佳,则直接代替父代值,自动进入下一种群,而如果对比结果正好相反,则应该由父代值直接保留。此次研究使用的是混合变异算子,如果现阶段的种群目标函数中取得的最大值与取得的最小值之差,并没有超过某一正数,此时就选择使用高斯变异法,如果两者之差超过了某一正数,则就选择使用边界变异法。所以,通常情况下,进化初期选择使用边界变异,换言之,就是选择种类差异大的批租,将其相对应的基因位看作是变异点,之后再使用两者相对的边界基因来取代最初的基因值,后阶段运用高斯变异,来使得算法搜索能力更强。
2.3 禁忌搜索
2.3.1 领域结构及候选集。本文首先采用交换邻域结构:任意选择同一检定设备上的两个批组,交换其检定顺序。其次,采用“高”候选集策略产生候选集。即:将总检定完成时间最大的并行机上任意批组插入到总检定时间最小的并行机上任一批组前。
2.3.2 禁忌表的设计。禁忌表采用先进先出的队列来实现。在禁忌搜索过程中,会出现当前解的领域全部被禁忌,或是某一解被禁忌后当前最优值将下降的情况,为了避免搜索算法丢失优化状态实现全局最优,本文基于特赦规则%根据解的适应度值,若出现某个候选解的适应度值优于当前最优解时,虽然从当前最优解到该解的变化被禁忌,但可以解禁该候选解作为当前最优解。
2.3.3 关于精英解的禁忌算法。禁忌算法的终止规则选用目标控制原则:当前已存在的最优解的适应度值连续n1次大于之后搜索到的解适应度值,则停止搜索。禁忌搜索算法流程如图2所示。
结束语
综上所述,可知运用遗传禁忌混合算法来进行电能计量设备自动检定流水线调度优化具有非常好的效果。使用遗传禁忌混合算法不仅具有非常快的收敛速度,还具有非常高的优化率,通过各种操作,能够获得很多最优解。总体上讲,此种算法具有非常强的有效性,也具有非常强的鲁棒性。当然电能计量设备自动检定流水线调度优化方法还有很多,有待其他学者进行进一步的研究,也希望技术人员在工作中加以总结。
参考文献
[1]王圣尧,王凌,许烨.求解相同并行机混合流水线车间调度问题的分布估计算法[J].计算机集成制造系统,2013(6).
[2]陈铁梅,罗家祥,杜娟,胡跃明.带扰动和变异因子的改进禁忌搜索算法求解贴片机贴装过程优化[J].控制与决策,2013(3).
[3]吕潇,孙跃,王智慧,赵志斌.复合谐振型感应电能传输系统分析及参数优化[J].电力系统自动化,2013(4).
[4]王凌,周刚,许烨,王圣尧.求解不相关并行机混合流水线调度问题的人工蜂群算法[J].控制理论与应用,2012(12).
关键词:电能计量设备;自动检定流水线;调度优化
电能计量设备自动检定流水线是现阶段比较先进的电能检定装置之一,在检定的过程中,能够完全进行自动化操作。但是电能计量设备自动检定流水线调度还有可以优化的空间,如果优化成功,检定效率会更高,所以计量检定中心都十分关注调度优化的问题。
1 电能计量设备自动检定流水线调度问题描述
为了提高智能计量设备自动检定流水线的效率,生产调度中心会依据用户需求、智能立库存储量及检定周期等因素,将不同批次的同类型计量器具(单相电能表)或相同电压等级的不同类型器具(单相电能表和终端)放在一条流水线上进行检定。同时,在至少一个检定环节(如:多功能检定环节)中存在多条独立的并行检定单元,且每个检定单元含有多个检定工位,可实现多批次、多计量设备的同时检测。因此需要将待检器具进行分批组处理,每个批组的大小也可不同。根据上述分析,本文将此类自动检定流水线定义为带批组的并行混合流水线。带批组并行混合流水线调度问题可描述为,N个计量器具分为B个批组在流水线上进行S个环节的检测,各环节至少有一台检定设备且至少有一个环节存在并行的检定设备,同一环节中各检定设备检测同一计量器具的检测时间均相同,每个批组在同一环节的检测时间不完全相同,在每一环节各待检器具均要完成一道工序,但各待检器具的每道工序可在相应环节中的任意并行检定设备上检定,已知待检器具各道工序的检定时间,要求确定所有待检批组的排序以及每一环节中并行检定设备的任务分配情况,从而使得总检定完成时间最小,即最小化最大检定时间,图1为自动检定流水线流程图。
2 基于GATS算法的自动检定流水线调度优化
2.1 遗传禁忌混合算法
遗传禁忌混合算法组由遗传算法与禁忌搜索TS算法组成。这两种算法各具优势,有效结合能够发挥出两者的最大优势。所谓遗传算法简单的说就是将求解的具体问题,转换成生物“染色体”种群,之后一步一步进行进化,最为重要的操作有选择、交叉与变异等。通过各项操作,寻求能够适应环境的最理想个体,进而实现最优解自适应搜索。遗传算法比较适合应用在范围比较大的搜索中,但是局部搜索能力却不强。而所谓禁忌搜索TS算法最突出的优势就是记忆功能强。搜索期间能够接受劣解,跳出局部最优解,因此此种算法的局部搜索能力非常强,但是禁忌搜索TS算法对初始解具有非常强的依赖性。两种算法相结合,既使得禁忌算法搜索效率明显提升,也避免了GA爬坡能力过慢的问题。为了能够让遗传算法与禁忌搜索TS算法结合之后,发挥出最大的优势,研究对遗传禁忌算法进行了改进优化,同时使用精英策略,换言之,找到适应度最前面的精英解,然后将其与非精英解交叉。遗传操作之后,会获得相应的解集,将这些解集适应度进行排位,排位最前的解集就可以成为禁忌算法中的初始解,之后再使用禁忌搜索算法进行相应操作获得最优解,以此代替初始解,待到完全满足条件之后,跳出算法,获得最优解。
2.2 交叉与变异
研究者首先要找到适应度最佳的精英解,将其与非精英解,按照随机方法进行交叉操作,同时对交叉解进行验证,以此查看交叉解是否达到各个约束条件的要求。具体算法步骤如下:首先,选择一个非精英解。该解的随机概率一定要超过预设交叉概率,将其与随机精英解展开交叉操作,再对交叉解展开验证,最为重要的验证内容就是交叉是否符合约束条件要求;其次,交叉后获得子代,将其与非精英父代值进行有效的对比,如果子代解的适应度更佳,则直接代替父代值,自动进入下一种群,而如果对比结果正好相反,则应该由父代值直接保留。此次研究使用的是混合变异算子,如果现阶段的种群目标函数中取得的最大值与取得的最小值之差,并没有超过某一正数,此时就选择使用高斯变异法,如果两者之差超过了某一正数,则就选择使用边界变异法。所以,通常情况下,进化初期选择使用边界变异,换言之,就是选择种类差异大的批租,将其相对应的基因位看作是变异点,之后再使用两者相对的边界基因来取代最初的基因值,后阶段运用高斯变异,来使得算法搜索能力更强。
2.3 禁忌搜索
2.3.1 领域结构及候选集。本文首先采用交换邻域结构:任意选择同一检定设备上的两个批组,交换其检定顺序。其次,采用“高”候选集策略产生候选集。即:将总检定完成时间最大的并行机上任意批组插入到总检定时间最小的并行机上任一批组前。
2.3.2 禁忌表的设计。禁忌表采用先进先出的队列来实现。在禁忌搜索过程中,会出现当前解的领域全部被禁忌,或是某一解被禁忌后当前最优值将下降的情况,为了避免搜索算法丢失优化状态实现全局最优,本文基于特赦规则%根据解的适应度值,若出现某个候选解的适应度值优于当前最优解时,虽然从当前最优解到该解的变化被禁忌,但可以解禁该候选解作为当前最优解。
2.3.3 关于精英解的禁忌算法。禁忌算法的终止规则选用目标控制原则:当前已存在的最优解的适应度值连续n1次大于之后搜索到的解适应度值,则停止搜索。禁忌搜索算法流程如图2所示。
结束语
综上所述,可知运用遗传禁忌混合算法来进行电能计量设备自动检定流水线调度优化具有非常好的效果。使用遗传禁忌混合算法不仅具有非常快的收敛速度,还具有非常高的优化率,通过各种操作,能够获得很多最优解。总体上讲,此种算法具有非常强的有效性,也具有非常强的鲁棒性。当然电能计量设备自动检定流水线调度优化方法还有很多,有待其他学者进行进一步的研究,也希望技术人员在工作中加以总结。
参考文献
[1]王圣尧,王凌,许烨.求解相同并行机混合流水线车间调度问题的分布估计算法[J].计算机集成制造系统,2013(6).
[2]陈铁梅,罗家祥,杜娟,胡跃明.带扰动和变异因子的改进禁忌搜索算法求解贴片机贴装过程优化[J].控制与决策,2013(3).
[3]吕潇,孙跃,王智慧,赵志斌.复合谐振型感应电能传输系统分析及参数优化[J].电力系统自动化,2013(4).
[4]王凌,周刚,许烨,王圣尧.求解不相关并行机混合流水线调度问题的人工蜂群算法[J].控制理论与应用,2012(12).