APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimummakespan in the job-shop scheduling problem. The new algorithm is based on the principles ofparticle swarm optimization (PSO). PSO employs a collaborative population-based search, which isinspired by the social behavior of bird flocking. It combines local search (by self experience) andglobal search (by neighboring experience), possessing high search efficiency. Simulated annealing(SA) employs certain probability to avoid becoming trapped in a local optimum and the search processcan be controlled by the cooling schedule. By reasonably combining these two different searchalgorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, isdeveloped. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated byapplying it to some benchmark job-shop scheduling problems and comparing results with otheralgorithms in literature. Comparing results indicate that PSO-based algorithm is a viable andeffective approach for the job-shop scheduling problem.

Solving Job-Shop Scheduling Problem Based on Improved Adaptive Particle Swarm Optimization Algorithm

An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.

Traveling Salesman Problem Using an Enhanced Hybrid Swarm Optimization Algorithm

The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.

Dynamic Weapon Target Assignment Based on Intuitionistic Fuzzy Entropy of Discrete Particle Swarm

Aiming at the problems of convergence-slow and convergence-free of Discrete Particle Swarm Optimization Algorithm(DPSO) in solving large scale or complicated discrete problem, this article proposes Intuitionistic Fuzzy Entropy of Discrete Particle Swarm Optimization(IFDPSO) and makes it applied to Dynamic Weapon Target Assignment(WTA). First, the strategy of choosing intuitionistic fuzzy parameters of particle swarm is defined, making intuitionistic fuzzy entropy as a basic parameter for measure and velocity mutation. Second, through analyzing the defects of DPSO, an adjusting parameter for balancing two cognition, velocity mutation mechanism and position mutation strategy are designed, and then two sets of improved and derivative algorithms for IFDPSO are put forward, which ensures the IFDPSO possibly search as much as possible sub-optimal positions and its neighborhood and the algorithm ability of searching global optimal value in solving large scale 0-1 knapsack problem is intensified. Third, focusing on the problem of WTA, some parameters including dynamic parameter for shifting firepower and constraints are designed to solve the problems of weapon target assignment. In addition, WTA Optimization Model with time and resource constraints is finally set up, which also intensifies the algorithm ability of searching global and local best value in the solution of WTA problem. Finally, the superiority of IFDPSO is proved by several simulation experiments. Particularly, IFDPSO, IFDPSO1~IFDPSO3 are respectively effective in solving large scale, medium scale or strict constraint problems such as 0-1 knapsack problem and WTA problem.

Optimization of Operational Route in AS/RS Based on Particle Swarm Algorithm

Optimization of the operational route in the automated storage/retrieval system （AS/RS） is transformed into the traveling salesman problem, To make the moving distance of the storage/retrieval machine shortest, we carry out a group of tests where 20 goods locations are chosed. Using PSO for operational route of AS/RS, the operation time can be shortened by about 11%. The experiments indicate that under the same conditions, the more the goods locations are, the higher the operation efficiency of the storage/retrieval machine is.

Development of Hybrid Algorithm Based on PSO and NN to Solve Economic Emission Dispatch Problem

The electric power generation system has always the significant location in the power system, and it should have an efficient and economic operation. This consists of the generating unit’s allocation with minimum fuel cost and also considers the emission cost. In this paper we have intended to propose a hybrid technique to optimize the economic and emission dispatch problem in power system. The hybrid technique is used to minimize the cost function of generating units and emission cost by balancing the total load demand and to decrease the power loss. This proposed technique employs Particle Swarm Optimization (PSO) and Neural Network (NN). PSO is one of the computational techniques that use a searching process to obtain an optimal solution and neural network is used to predict the load demand. Prior to performing this, the neural network training method is used to train all the generating power with respect to the load demand. The economic and emission dispatch problem will be solved by the optimized generating power and predicted load demand. The proposed hybrid intelligent technique is implemented in MATLAB platform and its performance is evaluated.

具有紧时、高能耗特征的混合流水车间多目标调度优化问题

针对具有紧时、高能耗工序特征的混合流水车间调度问题,以优化产品暴露时间、最大完工时间和能源消耗为目标,建立混合流水车间调度模型,并提出一种改进的多目标粒子群算法进行有效求解。首先构建了基于ISDE指标的档案维护策略及局部邻域搜索策略,辅助算法跃出局部极值及减少生产阻塞。之后,提出一种基于模糊理论的决策分析方法选取最优调度方案。最后,通过仿真实验验证提出的多目标调度模型与算法的可行性和优越性。

基于改进粒子群算法的木材板材下料方法

木材板材在家具行业应用广泛,以绿色环保、节约能源为目的的木材板材优化下料已经成为研究的热点。木材板材下料优化问题属于二维矩形下料问题,是一种具有高度计算复杂性的问题。本研究主要针对单规格木材板材进行矩形零件下料问题,在木材板材长和宽都大于零件长和宽的情况下,通过建立二维下料的数学模型,采用标准粒子群算法、变邻域搜索算法、粒子群混合变邻域搜索算法分别进行求解,并以某企业的下料实例进行分析计算。首先,利用标准粒子群算法求解单规格板材下料问题;其次,利用变邻域搜索算法求解单规格板材下料问题。在获得局部最优解的基础上改变其邻域结构再进行局部搜索,找到另一个局部最优解,如此不断迭代,直到满足算法的终止条件,获得全局最优解;最后,利用粒子群变邻域搜索混合算法求解单规格板材下料问题。针对粒子群算法局部搜索能力较差、容易过早收敛的问题和具有较好包容性的特点,将变邻域搜索的思想融入粒子群算法中,使结果更加趋向全局最优。结果表明:粒子群变邻域搜索混合算法相比粒子群算法和变邻域算法效率都有显著提升,能显著提高该木材板材的利用率,增加企业经济效益。

基于离散粒子群算法的管道保温结构优化研究

针对目前管道保温结构优化算法不稳定、结果优化程度不高的问题,建立以经济效益为目标函数,以满足国家散热损失标准等条件为约束函数的离散型数学模型。以BPSO算法为基础改变其位置更新规则,防止种群进化失效;采用自适应权重增加粒子的全局和局部搜索能力;充分利用模拟退火算法的思想避免出现早熟现象。应用改进的算法分别对普通蒸汽管道和核电站的蒸汽管道进行系统仿真实验。结果表明,该算法能够在满足国家散热损失标准等条件下取得最优解,可以为管道保温结构提供合理的优化方案。

基于遗传算法特性的混合粒子群算法求解TSP问题

为解决粒子群算法在旅行商问题上的收敛速度慢和路径最优化选择的问题,提出了一种新型的基于遗传算法特性的混合粒子群算法,对旅行商问题的最优路径进行规划.根据种群比例原则与迭代前的路径进行交叉、变异、复制等操作,建立了具有遗传算法特性的混合粒子群算法,并用于求解burma14问题.结果表明:相比传统的粒子群算法和模拟退火-禁忌搜索算法,混合粒子群算法在求解burma14问题中收敛时间与最优路径等指标上都有明显的优势,且随着迭代次数与种群个数的增大,算法的最优解逐渐减小;当最佳参数为种群个数150,迭代次数300时,最优解为30.179 424.

Binary Particle Swarm Optimization Based Hyper-Heuristic for Solving the Set-Union Knapsack Problem

The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computationally expensive.Therefore,several swarm intelligent algorithms have been proposed in order to solve the SUKP.Hyper-heuristics have received notable attention by researchers in recent years,and they are successfully applied to solve the combinatorial optimization problems.In this article,we propose a binary particle swarm optimization(BPSO)based hyper-heuristic for solving the SUKP,in which the BPSO is employed as a search methodology.The proposed approach has been evaluated on three sets of SUKP instances.The results are compared with 6 approaches:BABC,EMS,gPSO,DHJaya,b WSA,and HBPSO/TS,and demonstrate that the proposed approach for the SUKP outperforms other approaches.

面向动态公交的离散分层记忆粒子群优化算法

随着智慧城市、智慧交通的发展,移动互联网和公交智能基础设施以及相关数据的不断完善,通过用户手机预约公交服务的新型公交运营方式——动态公交,已经成为许多城市公交发展的重要探索方向。但目前,对动态公交问题的建模、算法研究不足。基于这一研究现状,提出动态公交问题模型和面向动态公交的离散分层记忆粒子群优化(PSO)算法。首先给出动态公交问题的目标函数和约束条件,给出动态公交问题的解的形式,并定义解的编辑距离;其次提出使用数据驱动的预计算路径集生成PSO算法的优质初始解的方法,给出基于解的编辑距离的PSO算法中粒子的变异概率和自适应收敛系数的计算方式;最后提出将粒子群分层求解的方法,其中低层粒子群可复用、可继承,从而减少单时间片内、时间片间复制和重初始化带来的性能损耗。基于重庆市北碚区蔡家岗街道的真实场景和亿级历史数据建立仿真环境进行实验,实验结果表明:相对于不分层PSO算法,分层PSO算法通过复用和继承能缩短超80%计算用时;自适应参数和变异机制能帮助算法更稳定地收敛到更优解;相对于传统公交系统,动态公交能在同等运力限制下,提高22%的乘客接单率,节省39.1%的乘客出行时间,所提算法能满足公交运营商在片区内进行动态公交调度的需求;相对于对比算法,所提算法平均缩短了85.3%的计算用时,并且在仅耗用80%里程的情况下提高了至少12%的接单率。

基于粒子群优化算法的柔性生产线排产方法

大力推进信息化和工业化的融合,要在航空航天装备上实现重点领域的技术突破。在未来十年,我国对飞机的需求将会持续加大,这就要求飞机零件的制造效率要高、响应速度要快。但实际生产中,对生产线排产算法的研究与应用还比较少,这就导致实际生产不能发挥出生产线的最大效能。针对上述问题,对实际柔性生产线进行了研究,建立符合现场生产实际的排产调度模型,采用优化的粒子群算法对模型进行求解,得到满足实际排产要求的最优解,使其发挥最大生产效能。

粒子群自进化算法求解物流装箱问题

为了解决当今物流行业中装载货物类型为强异构的情况,提高装载填充率和效率,提出了一种求解三维装箱问题的元启发式算法——粒子群自进化算法。算法包含两部分:极限点构造启发式算法和粒子群自进化规则。极限点构造启发式算法引入了极限点的概念,利用新的极值点思想推导出了三维装箱问题的启发式算法。粒子群自进化规则提出了在货物装载序列中表示粒子的方法,推导了粒子间交叉、变异算子,在极限点构造启发式算法的基础上不断迭代进化完成货物的装载。通过不同结果的比对,证明该算法显著提高了物流装载的空间利用率,强异构货物的平均装载率达到了85%,验证了算法在强异构货物下的有效性与优越性,并给出了货物装载的三维模型。由于实际测试集的缺少,分别为机腹仓装载类和集装板类模型提出了实例生成器,通过生成器的测试集验证了算法在实际应用中的紧凑性、实用性和快捷性。

基于正则化参数优化和边界聚类的电阻抗成像研究

电阻抗成像是一种无损伤的功能成像技术,由于逆问题具有不适定性、不稳定性等特点,往往存在重构图像的分辨率不高、伪影较大等问题。将Tikhonov和全变量(TV)两种正则化算法的罚函数进行组合应用,提出将粒子群算法用于组合罚函数的正则化参数优化,把图像质量指标(artifact level, AL)作为粒子群算法的适应度值,从而确定最优正则化参数,通过牛顿迭代法获得电导率,为了进一步去除伪影,将Niblack算法与边界聚类算法相结合,对求得的电导率进行处理,得到最终的电导率分布。仿真和实测结果均表明,该方法重建的图像能够更加准确地反映电场内目标物体的位置信息,有效的抑制伪影,提高了重建效果。

屋型拓扑粒子群优化算法与工程优化问题求解

针对粒子群优化算法在优化复杂工程问题时存在搜索效率低和易陷入局部最优的问题,提出一种屋型拓扑粒子群优化算法.该算法通过提出屋型拓扑和设计适应其特性的位置更新策略,改善粒子群优化算法信息传递和交流方式,提升算法的收敛速率和全局优化能力.在基准函数上的对比实验结果表明,屋型拓扑粒子群算法的寻优精度、收敛速度和稳定性均优于其他4种改进算法.在3个实际工程优化问题上的仿真实验结果进一步验证了该算法的有效性和实用性.

全渠道电商库存路径及定价问题优化研究

针对全渠道模式下电商库存路径及定价问题,考虑各前置仓需求不确定因素,本文提出一种按照不同售卖渠道的商品差异化定价策略,通过设置电商关于需求不确定风险态度的保守系数,构建以总利润最大化为目标的混合整数非线性鲁棒优化模型,并设计自适应模拟退火粒子群算法进行求解。选取含有10个和20个前置仓的两组算例,验证本文模型算法的适用性和有效性。实验分析结果显示,相比于统一定价,差异化定价可以提高电商总利润分别约5%和6%。敏感性分析结果表明,提升线上客户的线下购物体验以增加线上自提渠道客户数量,并组织线上营销活动以提高线上客户对电商促销努力的敏感度,能给电商带来更高的利润;掌控未来市场波动风险并准确预测需求信息以降低电商保守系数和需求最大偏离系数,亦可提高电商总利润。研究结论可为电商制定前置仓库存配送路径策略与各渠道商品定价方案提供参考。

带时间窗的车辆路径问题的混合粒子群优化算法

针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW),提出了一种混合粒子群优化算法(Hybrid Particle Swarm Optimization,HPSO)进行求解。所提出的算法设计了一种高效的编解码策略,以此搭建HPSO算法解空间到VRPTW解空间的桥梁。同时为了提高算法的寻优能力,设计了由单点插入策略以及双点交换策略组成的局部搜索策略。通过solomon-50标准数据集中的九个算例进行仿真实验,实验结果证明了所提出算法的寻优能力和稳定性均优于对比算法,最优解误差相较于对比算法最多降低了38.32%。

考虑参考价格效应的库存路径与定价问题

针对客户有价格策略型行为下的供应商库存路径与定价问题(inventory routing and pricing problem,IRPP),通过将参考价格效应嵌入产品需求价格函数中,以供应商总利润最大化为目标,构建考虑参考价格效应的IRPP优化模型,设计改进的粒子群算法进行求解。通过3组不同规模的算例验证本文模型与算法的适用性和有效性。计算结果显示,考虑参考价格效应不仅有助于降低产品定价(约9%)和提升客户感知收益,而且能够降低零售商的产品总库存(约22%)、仓储资源占用成本和库存持有成本,从而提高供应商总利润(约5%)。敏感性分析结果显示:受客户记忆参数减小和增益系数增大的共同影响,供应商总利润会明显增加;受客户记忆参数和损失系数增大的共同影响,供应商总利润会迅速下降。研究结论可为电商环境下客户有价格策略型行为下的供应商IRPP优化提供决策支撑。

多目标优化问题的进化计算方法

多目标优化问题在实际应用中广泛存在,涵盖了工程设计、资源分配、机器学习等领域。由于其具有问题空间复杂、决策变量众多及目标之间存在相互矛盾的特性,传统优化方法难以在解空间中找到全局的、非支配的解集。为解决多目标优化问题,文章探究了基于进化计算的方法。