哈喽，小伙伴们好~

今天我们继续优化算法的学习，在之前的文章中我们讲解了——优化算法学习|布谷鸟算法原理及Python实现，这次我们就来学习一下布谷鸟算法的应用——混合布谷鸟算法求解绿色流水线调度问题。

问题描述

近些年来，随着社会各界对环境问题的重视，绿色调度成为研究的热点。在传统的车间调度问题中，我们的优化目标通常与时间、成本等因素有关。但是随着可持续与环境问题的日益严重，越来越多的企业开始在制造过程中平衡经济成本与绿色成本。

在计算复杂度上，２台机器以上的置换流水车间调度问题（Permutation Flow Shop Scheduling Problem,PFSP）是车间调度问题中特殊的一种，更加符合实际生产。这个问题也早已被证明是NP-hard问题[1]，因此，更为复杂的带绿色指标的多目标置换流水线生产调度问题（Multi-object Permutation Flow Shop Scheduling Problem，MOPFSP）也属于NP-hard问题。

对于MOPFSP问题，可以描述如下：

数学模型

混合布谷鸟算法设计

对于标准布谷鸟算法的流程，在优化算法学习|布谷鸟算法原理及Python实现一文中已有讲解，在此就不做赘述。

01 自适应步长因子

CS算法虽然在诸多领域得到应用研究，但其本身存在固有不足：莱维飞行是一种马尔科夫链，只与当前情况有关，随机性较大，所以标准CS算法缺乏有效机制来加强搜索深度，算法收敛精度不高。CS算法在式（11）中定义了步长控制因子，该因子在标准算法中一般设定为固定的常数（譬如常取值为0.01）。若步长控制因子取值过大，易导致算法后期的搜索偏离优质解，使其收敛速度变慢；反之，若步长控制因子取值过小，则算法可能过早地陷入局部最优解，从而导致算法性能较弱。因此，对步长控制因子的改进有利于算法性能的提升。如果在算法搜索前期使用一个较大的步长控制因子，有利于在全局范围内迅速发现优质解所在区域；同时，随着算法搜索的推进，应逐渐减小步长控制因子，加强对局部优质解区域的细致搜索，这有利于提高算法的收敛速度和性能。

从步长控制因子方面对标准CS算法进行改进：用动态步长控制因子替换原有固定的步长控制因子。寻优过程中，随着个体质量逐步提高，适当缩小搜索范围，以加强搜索深度，有利于搜寻到更优的解。合理的步长控制因子应该是随着进化代数的增加而逐渐减小，使得算法在进化后期容易发现优质个体。

根据以下方面自适应调整步长控制因子α：将α 取值范围设置为[0.01, 0.2]；另外，引入余弦函数使α 随着进化代数的增加而减小。综上所述，提出α 的改进公式：

02 多邻域局部搜索

为进一步提高布谷鸟算法的局部搜索能力，引入多邻域局部搜索策略，对种群中的优质个体执行基于不同邻域的细致搜索。具体来说，就是对算法当前的非劣解集中的个体执行基于三种邻域的局部搜索。这三种邻域搜索分别为：Interchange local search、Insert local search[3]、2-opt local search，具体定义如下：

Interchange local search：对每个个体的工件排序，随机选择其中两个不同的位置，交换位置上的工件。例如10工件排序为[4, 2, 7, 1, 3, 5, 9, 8, 10, 6]，随机产生了两个位置P1＝３，P2＝９，则将位置3的工件7和位置9的工件10交换位置，得到一个新排序[4, 2, 10, 1, 9, 5, 9, 8, 10, 6]。

Insert local search: 该步骤可分为前插入和后插入。对每个个体的工件排序进行操作，随机选择其中2个不同的位置P1和P2，假设P1＞P2。后插入是指将位置P1的工件插入位置P2，位置P1+1～P2的工件均往前挪一个位置；前插入是指将P2的工件插入位置P1，位置P1～P2-1的工件均往后挪一个位置。例如10工件排序为[4, 2, 7, 1, 3, 5, 9, 8, 10, 6]，随机产生了两个位置P1＝3，P2＝9，按照上文，后插入得到的新排序为[4, 2, 1, 3, 5, 9, 8, 10, 7, 6]，前插入得到的新排序为[4, 2, 10, 7, 1, 3, 5, 9, 8, 10, 6]。

2-opt local search:对每个个体的工件排序，随机选择其中两个不同的位置P1和P2，将P1～P2的工件排序逆序排列，其他位置工件排序不变。例如10工件排序为[4, 2, 7, 1, 3, 5, 9, 8, 10, 6]，随机产生了两个位置P1＝3，P2＝9，按照上文，得到的新排序为[4, 2, 10, 8, 9, 5, 3, 1, 7, 6]。

算法流程

参考文献

[1] Garey M R , Sethi J R . The Complexity of Flowshop and Jobshop Scheduling[J]. Mathematics of Operations Research, 1976, 1(2):117-129.

[2] Yang X S , Deb S . Multiobjective cuckoo search for design optimization[J]. Computers & Operations Research, 2013, 40(6):1616-1624.

[3] Lei Deming , Guo Xiuping. A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents[J]. Expert Systems with Applications, 2015, 42( 23):9333-9339.

[4]钟祾充, 钱斌, 胡蓉,等. 混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程, 2018, 29(22):2674-2681.

好啦，今天的学习就到这里啦，关注公众号“土博在路上”获取更多精彩内容。

祝各位小伙伴：