摘要
运输问题自提出后,人们因其在各个领域的广泛应用进行了大量研究。尤其是线型运输问题,已经设计出了多种有效解法,但它们均不能直接处理非线性运输问题。本文在经典粒子群算法PSO的基础上设计了新算法PSO-NLTP,它通过改进PSO的粒子飞行速度和飞行位置更新方程,及设计出负修复算子,既满足TP的约束条件,又扩大了搜索空间。针对经典PSO算法容易在局部最优解过早停止搜索的不足,我们添加了自适应的变异算子,以防止PSO-NLTP过早停止搜索。通过仿真实例证明,与遗传算法GA-NLTP和带惩罚策略的EP进行比较,PSO-NLTP能在较短的时间内找到更优解,结果验证了新算法的有效性。
The transportation problem （TP） is well known as a combinatorial optimization problem for it could be extensively applied in many fields. There are several mathematical and computational methods for linear transportation problem （LTP）. However, the approaches cannot be used in solving non-linear transportation problems （NLTP） directly. In the present paper, a new algorithm （PSO-NLTP） is proposed for the solution to NLTP on the PSO algorithm. Taking use of the function of the new position updating rule and negative repair operator, it can satisfy the constrained conditions of TP. PSO-mutation as another extra operator is introduced to enlarge the search space. The nature of PSO can accelerate the convergence of the novel algorithm, which would also make PSO-TP get the local best solution. However, the PSO mutation as an extra operator can help PSO-TP to avoid mature convergence. The numerical experiments of solving the NLTP instances based on open problems show the effectiveness and efficiency of PSO- NLTP through the comparison with EP with penalty strategy and GA in the literature.
出处
《计算机科学》
CSCD
北大核心
2008年第6期206-209,共4页
Computer Science
基金
国家自然科学基金(10471045,60433020)
国家新世纪优秀人才基金(NCET-05-0734)
广东省自然科学基金(04020079)
霍英东基金(91005)
教育人文社科基金(2005-241)
广东省科技攻关项目(2005B10101010)
关键词
非线性运输问题
粒子群算法
负修复
自适应变异
Non-linear transportation problem, Particle swarm optimization, Negative repair, Mutation
