Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems

In this paper, a modified particle swarm optimization (PSO) algorithm is developed for solving multimodal function optimization problems. The difference between the proposed method and the general PSO is to split up the original single population into several subpopulations according to the order of particles. The best particle within each subpopulation is recorded and then applied into the velocity updating formula to replace the original global best particle in the whole population. To update all particles in each subpopulation, the modified velocity formula is utilized. Based on the idea of multiple subpopulations, for the multimodal function optimization the several optima including the global and local solutions may probably be found by these best particles separately. To show the efficiency of the proposed method, two kinds of function optimizations are provided, including a single modal function optimization and a complex multimodal function optimization. Simulation results will demonstrate the convergence behavior of particles by the number of iterations, and the global and local system solutions are solved by these best particles of subpopulations.     

改进型粒子群算法及其在选址问题中的应用

为了解决基本粒子群算法不易跳出局部最优的问题,提出了一种协同粒子群优化算法。在算法中通过加入权值递减的惯性因子和变异算子以克服基本PSO易早熟、不易收敛以及缺乏多样性的不足。将算法应用于极小极大选址问题的实验结果表明,算法能够有效地求解极小极大选址问题,具有较好的应用价值。     

定位-运输路线安排问题的改进离散粒子群优化算法

定位-运输路线安排问题(LRP)是集成物流中的一个NP-hard难题,为求解一类特殊的LRP问题,提出改进的离散粒子群优化算法.该方法采用整体优化的思想,将LAP和VRP集成在一起.通过合适的粒子编码方式,并改进粒子的运动方程,引入相应的变异算子和趋同扰动算子等,使得算法的适用性和性能获得了改善.通过仿真实验及与另2个典型算法的比较分析,证明了该算法的有效性.     

一种群体智能融合算法及其在应急设施选址的应用

针对粒子群优化算法早熟及细菌觅食算法收敛慢的问题,提出了将量子粒子群优化与细菌觅食算法融合的一种群体智能融合算法。该算法将细菌觅食、量子计算理论及粒子群优化的优点进行融合,以细菌觅食算法为主体,将量子进化算法及粒子群优化算法嵌入其中,从而极大地提高了算法的性能。通过对三个标准函数求解和验证,结果表明该算法提高了收敛精度及速度。最后用该算法求解公共卫生应急服务设施点选址问题,取得了较好的效果,说明了该算法的有效性。     

随机权值平面选址的粒子群优化算法

将引入粒子群优化算法来解决带随机权值、服从独立均匀概率分布的极小化极大（1-中心）平面选址问题,对其进行实验模拟并得出了乐观的结果。     

Simplified swarm optimization in disassembly sequencing problems with learning effects

In classical disassembly sequencing problems (DSPs), the disassembly time of each item is assumed fixed and sequence-independent. From a practical perspective, the actual processing time of a component could depend on its position in the sequence. In this paper, a novel DSP called the learning-effect DSP (LDSP) is proposed by considering the general effects of learning in DSP. A modified simplified swarm optimization (SSO) method developed by revising the most recently published variants of SSO is proposed to solve this new problem. The presented SSO scheme improves the update mechanism, which is the core of any soft computing based methods, and revises the self-adaptive parameter control procedure. The conducted computational experiment with up to 500 components reflects the effectiveness of the modified SSO method in terms of final accuracy, convergence speed, and robustness.     

协同混合粒子群算法求解车间作业调度问题

针对如何有效解决车间作业优化调度问题,提出一种协同粒子群和引力搜索的混合算法。新算法在粒子群算法进化停滞时引入引力搜索算法,利用引力搜索算法进化后期快速寻优的能力,及时跳出局部最优,保证全局最优。同时采用协同原理简化算法结构,提高算法收敛速度。将提出算法对车间作业调度典型测试用例进行仿真,仿真结果表明该算法较PSO和GA等算法在求解车间作业调度问题上更具优越性。     

Adaptive swarm optimization for locating and tracking multiple targets

Locating and tracking multiple targets in the dynamic and uncertain environment is a crucial and challenging problem in many practical applications. The main task of this paper is to investigate three fundamental problems, which are composed of the identification of irregular target, locating multiple targets and tracking multiple targets. Firstly, the proposed objective function successfully gets the target's shape to discern eccentric target in the specific environment. Secondly, for the sake of locating multiple targets, the adaptive PSO algorithm divides the swarm into many subgroups, and adaptively adjusts the number of particles in each subgroup by the competition and cooperation technology. Thirdly, in order to track multiple targets in the dynamic environment, the proposed swarm optimization has the characteristic of the adaptively covered radius of the subgroup according to the minimum distance among other subgroups. To show the efficiency and high performance of the proposed algorithms, several algorithms chiefly concentrate on locating and tracking three ants in the practical systems.     

A simple and effective genetic algorithm for the two-stage capacitated facility location problem

This paper presents a simple and effective Genetic Algorithm (GA) for the two-stage capacitated facility location problem (TSCFLP). The TSCFLP is a typical location problem which arises in freight transportation. In this problem, a single product must be transported from a set of plants to meet customers demands, passing out by intermediate depots. The objective is to minimize the operation costs of the underlying two-stage transportation system thereby satisfying demand and capacity constraints of its agents. For this purpose, a GA is proposed and computational results are reported comparing the heuristic results with those obtained by two state-of-the-art Lagrangian heuristics proposed in the literature for the problem.     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

Solving uncapacitated multilevel lot-sizing problems using a particle swarm optimization with flexible inertial weight

The multilevel lot-sizing (MLLS) problem is a key production planning problem in materials requirements planning (MRP) system. The MLLS problem deals with determining the production lot-sizes of various items appearing in the product structure over a given finite planning horizon to minimize the production cost, the inventory carrying cost, the back ordering cost and etc. This paper proposed a particle swarm optimization (PSO) algorithm for solving the uncapacitated MLLS problem with assembly structure. All the mathematical operators in our algorithm are redefined and the inertial weight parameter can be either a negative real number or a positive one. The feasibility and effectiveness of our algorithm are investigated by comparing the experimental results with those of a genetic algorithm (GA).     

A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems

The Travelling Salesman Problem (TSP) is one of the most well-known combinatorial optimization problems and has attracted a lot of interests from researchers. Many studies have proposed various methods for solving the two-dimensional TSP. In this study, we extend the two-dimensional TSP to the three-dimensional TSP, namely the spherical TSP in which all points (cities) and paths (solutions) are on the surface of a sphere. A hybrid algorithm based on the glowworm swarm optimization (GSO) and the complete 2-opt algorithm is proposed, in which the carriers of the luciferin are transformed from glowworms to edges between cities, and the probabilistic formula and the luciferin updating formula are modified. In addition, the complete 2-opt algorithm is performed to optimize the selected optimal routes every few iterations. Numerical experimental results show that the proposed algorithm has a better performance than the basic GSO in solving the spherical TSP. Meanwhile, the complete 2-opt algorithm can speed up the convergence rate.     

A hybrid particle swarm optimization based algorithm for high school timetabling problems

In this contribution a hybrid particle swarm optimization (PSO) based algorithm is applied to high school timetabling problems. The proposed PSO based algorithm is used for creating feasible and efficient high school timetables. In order to demonstrate the efficiency of the proposed PSO based algorithm, experiments with real-world input data coming from many different Greek high schools have been conducted. Computational results show that the proposed hybrid PSO based algorithm performs better than existing approaches applied to the same school timetabling input instances using the same evaluation criteria.     

A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem

This paper proposes a novel multi-objective model for an unrelated parallel machine scheduling problem considering inherent uncertainty in processing times and due dates. The problem is characterized by non-zero ready times, sequence and machine-dependent setup times, and secondary resource constraints for jobs. Each job can be processed only if its required machine and secondary resource (if any) are available at the same time. Finding optimal solution for this complex problem in a reasonable time using exact optimization tools is prohibitive. This paper presents an effective multi-objective particle swarm optimization (MOPSO) algorithm to find a good approximation of Pareto frontier where total weighted flow time, total weighted tardiness, and total machine load variation are to be minimized simultaneously. The proposed MOPSO exploits new selection regimes for preserving global as well as personal best solutions. Moreover, a generalized dominance concept in a fuzzy environment is employed to find locally Pareto-optimal frontier. Performance of the proposed MOPSO is compared against a conventional multi-objective particle swarm optimization (CMOPSO) algorithm over a number of randomly generated test problems. Statistical analyses based on the effect of each algorithm on each objective space show that the proposed MOPSO outperforms the CMOPSO in terms of quality, diversity and spacing metrics.     

Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows

This study presents a new variant of the team orienteering problem with time windows (TOPTW), called the multi-modal team orienteering problem with time windows (MM-TOPTW). The problem is motivated by the development of a tourist trip design application when there are several transportation modes available for tourists to choose during their trip. We develop a mixed integer programming model for MM-TOPTW based on the standard TOPTW model with additional considerations of transportation mode choices, including transportation cost and transportation time. Because MM-TOPTW is NP-hard, we design a two-level particle swarm optimization with multiple social learning terms (2L-GLNPSO) to solve the problem. To demonstrate the applicability and effectiveness of the proposed model and algorithm, we employ the proposed 2L-GLNPSO to solve 56 MM-TOPTW instances that are generated based on VRPTW benchmark instances. The computational results demonstrate that the proposed 2L-GLNPSO can obtain optimal solutions to small and medium-scale instances. For large-scale instances, 2L-GLNPSO is capable of producing high-quality solutions. Moreover, we test the proposed algorithm on standard TOPTW benchmark instances and obtains competitive results with the state-of-art algorithms.     

A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery

Vehicle routing problem (VRP) is an important and well-known combinatorial optimization problem encountered in many transport logistics and distribution systems. The VRP has several variants depending on tasks performed and on some restrictions, such as time windows, multiple vehicles, backhauls, simultaneous delivery and pick-up, etc. In this paper, we consider vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The VRPSPD deals with optimally integrating goods distribution and collection when there are no precedence restrictions on the order in which the operations must be performed. Since the VRPSPD is an NP-hard problem, we present a heuristic solution approach based on particle swarm optimization (PSO) in which a local search is performed by variable neighborhood descent algorithm (VND). Moreover, it implements an annealing-like strategy to preserve the swarm diversity. The effectiveness of the proposed PSO is investigated by an experiment conducted on benchmark problem instances available in the literature. The computational results indicate that the proposed algorithm competes with the heuristic approaches in the literature and improves several best known solutions.     

A novel discrete particle swarm optimization algorithm for solving bayesian network structures learning problem

ABSTRACT

Bayesian network is an effective representation tool to describe the uncertainty of the knowledge in artificial intelligence. One important method to learning Bayesian network from data is to employ a search procedure to explore the space of networks and a scoring metric to evaluate each candidate structure. In this paper, a novel discrete particle swarm optimization algorithm has been designed to solve the problem of Bayesian network structures learning. The proposed algorithm not only maintains the search advantages of the classical particle swarm optimization but also matches the characteristics of Bayesian networks. Meanwhile, mutation and neighbor searching operators have been used to overcome the drawback of premature convergence and balance the exploration and exploitation abilities of the particle swarm optimization. The experimental results on benchmark networks illustrate the feasibility and effectiveness of the proposed algorithm, and the comparative experiments indicate that our algorithm is highly competitive compared to other algorithms.