显然,本书构建的基于成本和时间的优化模型是典型的多目标优化问题,此类问题的各个子目标之间往往存在一定的冲突,改善其中任意一个子目标,往往意味着其他子目标的牺牲,因此,找到满足所有目标函数的最优解是不现实的。
可行的做法为通过对子目标之间进行均衡,以获得帕累托最优解。多目标的帕累托最优解是由多目标问题合理构成的集合,在实际应用中,决策者可根据实际情况及偏好,从上述合理解的集合中挑选一个或多个合理解作为多目标问题的最优解。在本书所有构建的基于成本和时间的优化模型中,成本和时间显然存在着互斥关系,要降低成本,往往就需要牺牲运输时间,要兼顾这两项指标,只能选择折中方案的合理解,形成费用尽可能少、时间尽可能短的一组同等优化级别的非劣解集合。
在具体算法上,考虑到传统算法通常只进行一次运行来获取一个帕累托最优解的局限性,本书采用具有智能性、自适应性、能够在单次优化过程中求解出多个均衡解的遗传算法来求解多目标优化问题。在多目标进化算法的研究中,不少学者取得了较好成果。NSGA(非支配排序遗传算法)和NSGA-II(带精英策略的非支配排序的遗传算法)都是基于帕累托最优解和遗传算法的多目标优化算法。
图5-18 NSGA-II算法流程(www.daowen.com)
传统多目标遗传算法(NSGA)采用的非支配分层方法,可以使好的个体有更大的机会遗传到下一代;适应度共享策略则使得准Pareto面上的个体均匀分布,保持了群体多样性,克服了超级个体的过度繁殖,防止了早熟收敛。
针对NSGA的不足之处,Deb等人于2002年提出NSGA-II算法。相较于NSGA,NSGA-II的改进体现在计算复杂度的降低、用拥挤距离比较算子替代适值度和引入精英保留机制。NSGA-II算法的主流程如图5-18所示。
在具体算法设计上面,首先明确将运输方式以自然数(1,2,3,4)来表示,并以此作为染色体基因。其次,确定初始种群,包括种群规模和构成种群的个体,按照通常经验,将种群规模确定为50~100,种群个体为每一个运输组织方案。在个体适应度评估中,以总运输时间和总运输费用两个约束条件作为评价标准。模型运算的选择操作则是依据快速非支配排序结果、拥挤度算子大小两项指标,采用拥挤联赛算子来选择。具体改进算法流程如图5-18所示。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。