CEGA浅谈
No-wait job-shop scheduling (NWJSS)问题是许多带有无等待约束的行业中存在的经典调度问题，例如金属加工、塑料、化工和食品行业。交叉熵（CE）作为一种新的元启发式方法，可以成为解决NWJSS问题的替代方法。这种方法已经被用于组合优化、多元优化和稀有事件模拟。在这些问题上，CE的实现平均需要较少的计算时间就能得到最优值。然而，使用原始的CE来解决大规模的NWJSS需要高计算时间。而CEGA即交叉熵与遗传算法的混合算法能够很好解决这一问题。
本文还将CEGA与模拟退火遗传算法、混合禁忌搜索进行了比较，最终发现CEGA在计算时间上要远远优于这两种算法。传统的模拟退火遗传算法具有以下缺点：
参数敏感性：模拟退火遗传算法涉及到许多参数的设定，如初始温度、冷却率、交叉率、变异率等。这些参数的选择对算法的性能和结果有重要影响，但确定合适的参数值通常是一项具有挑战性的任务。
收敛速度：模拟退火遗传算法在初始阶段可能需要大量的迭代和搜索才能找到一个较优的解。算法的收敛速度可能相对较慢，特别是在处理复杂问题或大规模问题时。
局部最优解问题：由于模拟退火遗传算法使用了随机性操作，例如交叉和变异，存在一定的风险陷入局部最优解。这可能导致算法无法达到全局最优解，而只能找到局部较优解。
资源消耗：由于模拟退火遗传算法需要进行大量的迭代和搜索，因此它可能需要较长的计算时间和更多的计算资源。特别是在处理复杂问题和大规模问题时，算法的计算成本可能会显著增加。
参数调优困难：确定合适的参数值对于模拟退火遗传算法的性能至关重要。然而，找到最佳参数组合通常需要大量的实验和经验，并且可能需要针对不同的问题进行调优。
而混合禁忌算法同样存在明显的弊端：
参数选择困难：混合禁忌算法涉及到多个参数的设定，如禁忌列表长度、禁忌迭代次数、邻域搜索策略等。确定合适的参数值并进行参数调优可能是一项具有挑战性的任务。
局部最优解问题：混合禁忌算法使用了禁忌搜索和邻域搜索策略来避免陷入局部最优解。然而，由于算法的随机性和启发式策略的局限性，仍然存在一定的风险陷入局部最优解。
计算复杂度高：混合禁忌算法在每个迭代中需要进行禁忌列表的更新、邻域搜索和禁忌策略的应用等操作。这些操作可能导致算法的计算复杂度较高，尤其在处理复杂问题和大规模问题时。
调优过程漫长：由于混合禁忌算法的参数较多且相互关联，进行参数调优可能需要大量的实验和经验。寻找最佳参数组合可能需要漫长的试错过程，增加了调优的难度和时间成本。
邻域搜索受限：混合禁忌算法的性能很大程度上依赖于邻域搜索策略。如果邻域搜索策略不够全面或无法有效地跳出局部最优解，算法的性能可能会受到限制。
而CEGA能够很好克服上述缺点，并提供以下的优势：
组合优势：CEGA结合了交叉熵和遗传算法的优点，充分发挥了它们在解决问题时的不同特点和搜索策略。通过结合两种算法，CEGA能够更全面地探索解空间并找到更优的解决方案。
具备全局搜索能力：遗传算法作为CEGA的一部分，具有较好的全局搜索能力。它能够通过选择、交叉和变异等操作，不断探索解空间，并逐步优化解决方案。
适应性强：CEGA的交叉熵部分可以根据问题的特性和搜索过程中的情况，动态地调整概率分布模型，使其适应不同的问题和搜索空间。这种适应性使得CEGA在解决不同类型的NWJSS问题时更加灵活和有效。
改进性能：通过引入遗传算法的组件，CEGA能够在大规模NWJSS实例中显著改善计算性能。遗传算法通过并行搜索和自适应性操作，加速了解的收敛和优化过程。
综合效果优良：通过与其他元启发式方法进行比较，CEGA在NWJSS问题中提供了更好或至少相等的完成时间。这表明CEGA在解决实际行业中的NWJSS问题时具有竞争力和有效性。
总体而言，CEGA的性能优于模拟退火遗传算法和混合禁忌搜索（HTS），尤其是对于小规模实例而言。在未来的研究中，需要修改CEGA以获得更好的性能，尤其是针对大规模实例。使用较低级别的编程语言实现可能会提高CEGA的性能。另外，建议将该算法应用于其他问题上。
