《Algorithms》：The New Mushroom–Weed Hybrid Reproduction Optimization Algorithm and Its Application to Tourist Route Planning
Domagoj Palinic,
Rea Aladrovic,
Marina Ivasic-Kos and
Jonatan Lerga
编辑推荐：
受自然启发的元启发式算法（Metaheuristic Algorithms）常被应用于复杂组合优化（Combinatorial Optimization）问题，Activate Stop此处精确方法在计算上不可行。旅游路线优化是一个典型的多目标（Multi-o
受自然启发的元启发式算法（Metaheuristic Algorithms）常被应用于复杂组合优化（Combinatorial Optimization）问题，Activate Stop此处精确方法在计算上不可行。旅游路线优化是一个典型的多目标（Multi-objective）问题，其特征在于存在诸如旅行时间、成本、开放时间和交通方式等现实约束。尽管蘑菇繁殖优化（Mushroom Reproduction Optimization, MRO）在计算上具有效率优势，但在复杂搜索空间中常出现早熟收敛（Premature Convergence）现象。本研究提出了一种新型混合算法——蘑菇–杂草混合繁殖优化（Mushroom–Weed Hybrid Reproduction Optimization, MWHRO），该算法将MRO的基于菌落局部搜索与入侵杂草优化（Invasive Weed Optimization, IWO）的适应度比例繁殖及竞争淘汰机制相结合。混合化策略增强了种群多样性（Population Diversity）和全局探索能力，同时保持了快速收敛特性。所提算法基于克罗地亚萨格勒布市的真实数据，在多种交通方式和目标权重场景下对现实旅游路线优化问题进行了评估。在相同评估预算下，与蚁群优化（Ant Colony Optimization, ACO）、IWO、粒子群优化（Particle Swarm Optimization, PSO）及标准MRO进行了性能比较。实验结果表明，所提出的MWHRO算法能够持续获得高质量解，且具有显著更低的执行时间，尤其在约束和多模态场景中表现突出。统计分析证实了该方法的鲁棒性和对现实路线优化问题的实际适用性。
本研究旨在解决旅游路线优化这一受限组合优化问题，该问题涉及多个往往相互冲突的目标，包括最小化旅行距离、时间和成本，或最大化游客满意度，同时受到景点开放时间、用户偏好、交通方式、交通状况和时间预算等现实约束的影响。由于问题规模随决策变量增加呈指数级增长，属于NP-hard或NP-complete问题，传统精确方法在大规模实例中难以适用，因此需要借助元启发式算法在合理计算时间内寻找接近全局最优的高质量解。
研究人员开发了蘑菇–杂草混合繁殖优化（MWHRO）算法，该算法选择性整合MRO的计算效率与IWO的多样性增强繁殖策略，通过算子层面的混合化设计，在保持MRO框架计算效率的同时，克服标准MRO的停滞问题，提升全局解搜索能力和鲁棒性。算法评估基于克罗地亚萨格勒布市的真实地理数据，涵盖步行、驾车和公共交通三种交通 ICCV（交通）模式，以及均衡权重和距离优先两种目标函数权重场景。
研究采用的关键技术方法包括：（1）基于Google Routes API获取的真实距离矩阵和时间矩阵，参考数据采集时间为2026年3月6日上午9:20；（2）多目标函数设计，整合距离、时间、成本及违反开放时间约束的惩罚项，并采用基于随机路线5th和95th百分位数的归一化处理；（3）五元对比评估框架，将MWHRO与ACO、IWO、PSO及标准MRO在相同评估预算（10,000次目标函数评估）下进行系统比较；（4）非参数统计检验，采用Wilcoxon符号秩检验和Cliff's δ效应量评估差异显著性，以及Spearman秩相关系数评估路线排序相似性；（5）种群规模敏感性分析，测试5至30个代理的初始种群规模；（6）问题规模扩展性测试，比较15个和29个景点的场景。
**执行时间比较**：在均衡权重场景下，MWHRO在所有交通模式中实现最低执行时间（驾车0.379秒、公共交通0.368秒、步行0.321秒），显著优于IWO（约1.3秒）和ACO（约3.9秒）。MRO和PSO表现相近但略慢于MWHRO。距离优先场景下呈现一致趋势，表明MWHRO在不同优化目标下均保持稳定的计算效率，适用于实时或交互式路由应用。
**解质量比较**：在公共交通距离优先场景中，MRO获得最佳平均得分（6.5926），MWHRO次之（6.6430），但MWHRO取得最佳最小得分（6.0819）且执行时间最短。收敛曲线显示ACO和MRO更快达到平台期，而MWHRO持续改进并获得最低最终得分；分散图表明MWHRO和ACO的最终得分更为一致，PSO的收敛结果和分散性最差。在驾车距离优先场景中，MRO实现最佳平均得分，但MWHRO仍获得最佳最小解和最短执行时间，体现了在解质量与效率之间的强平衡能力。
**统计显著性评估**：在公共交通均衡场景下，MWHRO显著优于所有竞争算法，与ACO、IWO、PSO比较均具有大效应量（|δ| > 0.6）；与MRO的差异无统计显著性（p = 0 family 0.5978，小效应量）。在驾车距离优先场景下，MWHRO显著优于IWO和PSO（大效应量），对ACO具有中等效应量显著优势，与MRO无显著差异。这些结果表明MWHRO在约束和多模态情况下的统计鲁棒性。
**种群规模敏感性比较**：MRO和MWHRO在较小初始种群时表现更佳，平均得分随种群规模从5增至30而上升（MWHRO从6.7896升至7.1605）。ACO和IWO对种群规模相对不敏感。PSO表现出高度敏感性，较大种群显著改善其性能。运行时间方面，除IWO随种群规模增加而显著下降（从5到30代理时从3.9秒降至0.71秒）外，其余算法受种群规模影响较小。
**景点数量对算法性能的影响**：在15景点场景中，MWHRO获得最低平均目标值（-0.7009）和最短执行时间（0.7185秒）。在29景点更复杂场景中，MWHRO仍保持最佳平均得分（6.5016）和最佳最小得分（6.0247），同时执行时间最短（0.3569秒），证明其良好的可扩展性。ACO和IWO在处理大规模问题时需要显著更长的计算时间。
**惩罚机制对结果的影响**：在无惩罚、无归一化的24景点多日程扩展实验中，ACO取得最佳平均和最小得分，MWHRO和MRO获得相近的竞争力次优结果，而IWO和PSO表现明显较差。执行时间方面，PSO最快（0.28秒），MWHRO低于0.5秒，ACO显著最慢（11.65秒）。该配置下ACO的优势与其基于图结构的特性及精英信息素更新策略有关，但MWHRO仍保持计算效率优势。
**输出路线比较**：在公共交通均衡场景下，各算法生成的最优路线具有高度相似的全局结构，均从Ban Jela?i? Square出发，先游览历史中心城区主要景点，再延伸至Mirogoj公墓、Maksimir公园、Jarun湖和The Garden Brewery等较远处景点。MWHRO获得最佳目标值（6.4804），MRO次之（6.6535）。路线差异主要体现在局部邻近景点的排序变化，如Upper Town区域的St. Mark's Church、Lotr??ak?
? Tower、失恋博物馆和Klovi?evi Dvori画廊的访问顺序，以及Zagreb大教堂和Dolac市场的细微序列差异。PSO得分最高（7.3831），表明其路线效率相对较低，但总体空间组织逻辑仍与其他算法一致。Spearman分析显示各算法输出路线的景点排序具有高度相关性。
**讨论部分总结**：研究人员指出，混合MRO的局部搜索效率与IWO的全局探索机制对提升算法性能具有积极效果。MWHRO通过允许多个高适应度菌落个体参与繁殖，并按适应度比例分配后代数量，有效增加了种群多样性；同时引入的竞争淘汰机制控制了种群规模，防止计算资源过度消耗。这种算子层面的混合设计不同于简单的算法串联或嵌套，而是实现了机制互补。实验表明，在静态环境下的个体旅游路线优化中，MWHRO在多数场景下实现了最佳或接近最佳的解质量与执行时间的平衡，尤其对于需要实时响应的旅游规划系统具有实际价值。研究人员也指出，现实世界旅游场景包含大规模人群动态、多智能体交互和共享资源竞争等宏观动态 behaviors，这些问题可通过平均场博弈（MFG）框架建模，是未来值得探索的方向。未来工作将扩展至更大数据集、动态交通条件，以及时间优先或成本优先等更多优化场景，并进一步优化参数以提升鲁棒性和可扩展性。
**研究结论翻译**：本研究提出了蘑菇–杂草混合繁殖优化算法。该方法结合了蘑菇繁殖优化的局部搜索优势与入侵杂草优化的基于适应度繁殖及淘汰机制。主要目标是减少MRO的早熟收敛现象，并提升其在具有约束的复杂组合问题中的性能。该算法基于现实旅游路线优化问题进行了评估，使用了真实地理数据，以及通过Google Maps API获取的不同交通方式下各位置间的距离信息，还有可用的交通价格信息和旅游景点开放时间信息。所采用的实例为克罗地亚首都萨格勒布，该城拥有位于近市中心和远市中心、可通过步行、公共交通或汽车到达的各类旅游景点。结果表明，MWHRO能持续产生高质量解，且在多数场景下比对比算法需要更少的执行Passes执行时间。统计分析证实，在受限和多模态情况下，尤其是公共交通路线规划中，MWHRO显著优于MRO、IWO和PSO。在许多情况下，它也优于ACO。ACO在某些距离优先的驾车场景中取得了强劲结果，但与MWHRO相比需要相当更多的计算时间。相比之下，MWHRO提供了更优的解质量与效率平衡，使其适用于实际旅游路线规划系统。未来工作将包括更大规模数据集（景点）的问题以及动态交通条件，还将探索参数调优的进一步改进以增强鲁棒性和可扩展性，以及探索优先考虑时间或成本的其他优化场景。
