计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 215-221.doi: 10.11896/jsjkx.190600101
李远锋, 李章维, 秦子豪, 胡俊, 张贵军
LI Yuan-feng, LI Zhang-wei, QIN Zi-hao, HU Jun, ZHANG Gui-jun
摘要： 针对平衡运输问题,文中提出了一种基于蒙特卡洛相似度遗传算法的求解算法。首先,利用矩阵元素对种群个体进行初始化,增加了种群的多样性;其次,设计了动态变异率算子和随机变异策略,以增强算法的搜索能力,加快收敛速度;最后,采用蒙特卡洛相似度接收的方式,避免算法陷入局部最优解问题。通过收敛速度、最优解偏差率、相对标准差等参数对基本遗传算法GA和改进遗传算法IGA进行比较,验证了所提算法的有效性。针对杭州地理数据,设计开发了基于ArcGIS平台的运输配送系统,实现了平衡运输问题的求解功能,系统测试表明了所提算法的有效性。
中图分类号:
| [1]HITCHCOCK F L.The distribution of a product from several sources to numerous localities[J].Journal of Mathematics and Physics,1941,20(1/2/3/4):224-230. [2]KOOPMANS T C.Optimum utilization of the transportationsystem[J].Econometrica:Journal of the Econometric Society,1949,17:136-146. [3]ORLIN J B.A faster strongly polynomial minimum cost flow algorithm[J].Operations research,1993,41(2):338-350. [4]KLOSE A.Algorithms for solving the single-sink fixed-chargetransportation problem[J].Computers & Operations Research,2008,35(6):2079-2092. [5]ZHU L L.Inteligent Optimization Algorithm for Upper Minimal Total Cost Bound of Transportation Problem with Varying Demands and Supplies[D].Nanchang:Nanchang University,2015. [6]SHARMA R R K,PRASAD S.Obtaining a good primal solution to the uncapacitated transportation problem[J].European Journal of Operational Research,2003,144(3):560-564. [7]PAPAMANTHOU C,PAPARRIZOS K,SAMARAS N.Computational experience with exterior point algorithms for the transportation problem[J].Applied Mathematics and Computation,2004,158(2):459-475. [8]ADLAKHA V,KOWALSKI K,VEMUGANTI R R.Heuristic algorithms for the fixed-charge transportation problem[J].OPSEARCH,2006,43(2):132-151. [9]KANNAN G,KUMAR P S,VINAY V P.Comments on nonli-near fixed charge transportation problem by spanning tree-based genetic algorithm by Jung-Bok Jo,Yinzhen Li,Mitsuo Gen,Computers & Industrial Engineering (2007)[J].Computers & Industrial Engineering,2008,55(2):533-534. [10]KIRALY Z,KOVACS P.Efficient implementations of mini-mum-cost flow algorithms[J].Acta Universitatis Sapientiae,Informatica,2012,4(1):67-118. [11]LOTFI M M,TAVAKKOLI-MOGHADDAM R.A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems[J].Applied Soft Computing,2013,13(5):2711-2726. [12]MOLLA-ALIZADEH-ZAVARDEHI S,NEZHAD S S,TAVAK-KOLI-MOGHADDAM R,et al.Solving a fuzzy fixed charge so-lid transportation problem by metaheuristics[J].Mathematical &Computer Modelling,2013,57(5/6):1543-1558. [13]SABBAGH M S,GHAFARI H,MOUSAVI S R.A new hybrid algorithm for the balanced transportation problem[M]//Pergamon Press,2015. [14]XIE F,BUTT M M,LI Z,et al.An upper bound on the minimal total cost of the transportation problem with varying demands and supplies[J].Omega,2017,68:105-118. [15]KARAGUL K,SAHIN Y.A Novel Approximation Method to Obtain Initial Basic Feasible Solution of Transportation Problem[J].Journal of King Saud University-Engineering Sciences,2020(32):211-218. [16]LIU Y M,WEI O,HUANG M Y,et al.Feature Selection Optimization Based on Atomic Set and Genetic Algorithm in Software Product Line [J].Journal of Chinese Computer Systems,2017,38(1):35-39. [17]YANG X W,YANG L J.An Improved Genetic Algorithm Based on Crossover Model [J].Control and Decision,2016,31(10):1837-1844. [18]HAN K K,XIE Z P,LV X.Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm [J].Computer Science,2018,45(4):137-142. [19]WU X L,XIAO X,ZHAO N.Flexible Job Shop Dual Resource Scheduling Problem Considering Loading and Unloading [J].Control and Decision,2020,35(10):2475-2485. [20]SHI T F.Research on Path Planning for Mobile Robot Based on Improved Genetic Algorithm [J].Computer Simulation,2011,28(4):193-195. [21]WEN Y,PAN D Z.Improved Genetic Algorithm for Traveling Salesman Problem[J].Computer Science,2016,43(S1):90-92. |
| [1] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005 |
| [2] | 李丹丹, 吴宇翔, 朱聪聪, 李仲康. 基于多种改进策略的改进麻雀搜索算法 Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies 计算机科学, 2022, 49(6A): 217-222. https://doi.org/10.11896/jsjkx.210700032 |
| [3] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
| [4] | 吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110 |
| [5] | 王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239 |
| [6] | 郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131 |
| [7] | 左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053 |
| [8] | 高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057 |
| [9] | 姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191 |
| [10] | 高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088 |
| [11] | 吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021 |
| [12] | 董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089 |
| [13] | 梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009 |
| [14] | 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184 |
| [15] | 冯炳超, 吴璟莉. 求解自行车共享系统静态再平衡问题的单亲遗传算法 Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System 计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120 |
|
||
首页