A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems

The job-shop scheduling problem is one of the most difficult production planning problems. Since it is in the NP-hard class, a recent trend in solving the job-shop scheduling problem is shifting towards the use of heuristic and metaheuristic algorithms. This paper proposes a novel metaheuristic algorithm, which is a modification of the genetic algorithm. This proposed algorithm introduces two new concepts to the standard genetic algorithm: (1) fuzzy roulette wheel selection and (2) the mutation operation with tabu list. The proposed algorithm has been evaluated and compared with several state-of-the-art algorithms in the literature. The experimental results on 53 JSSPs show that the proposed algorithm is very effective in solving the combinatorial optimization problems. It outperforms all state-of-the-art algorithms on all benchmark problems in terms of the ability to achieve the optimal solution and the computational time.     

Design of water distribution networks using accelerated momentum particle swarm optimisation technique

Optimisation of looped water distribution networks (WDNs) has been recognised as an NP-hard combinatorial problem which cannot be easily solved using traditional mathematical optimisation techniques. This article proposes the use of a new version of heuristic particle swarm optimisation (PSO) for solving this problem. In order to increase the convergence speed of the original PSO algorithm, some accelerated parameters are introduced to the velocity update equation. Furthermore, momentum parts are added to the PSO position updating formula to get away from trapping in local optimums. The new version of the PSO algorithm is called accelerated momentum particle swarm optimisation (AMPSO). The proposed AMPSO is then applied to solve WDN design problems. Some illustrative and comparative illustrative examples are presented to show the efficiency of the introduced AMPSO compared with some other heuristic algorithms.     

离散萤火虫优化算法求解概率旅行商问题

对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解.其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能.实验中用TSPLIB中的经典实例进行测试来验证其可行性.考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较.实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值.     

Non-parametric particle swarm optimization for global optimization

In recent years, particle swarm optimization (PSO) has extensively applied in various optimization problems because of its simple structure. Although the PSO may find local optima or exhibit slow convergence speed when solving complex multimodal problems. Also, the algorithm requires setting several parameters, and tuning the parameters is a challenging for some optimization problems. To address these issues, an improved PSO scheme is proposed in this study. The algorithm, called non-parametric particle swarm optimization (NP-PSO) enhances the global exploration and the local exploitation in PSO without tuning any algorithmic parameter. NP-PSO combines local and global topologies with two quadratic interpolation operations to increase the search ability. Nineteen (19) unimodal and multimodal nonlinear benchmark functions are selected to compare the performance of NP-PSO with several well-known PSO algorithms. The experimental results showed that the proposed method considerably enhances the efficiency of PSO algorithm in terms of solution accuracy, convergence speed, global optimality, and algorithm reliability.     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.     

多策略并行学习的异构粒子群优化算法

针对标准粒子群优化(PSO)算法在复杂问题上收敛速度慢和早熟收敛的缺点,提出了一种多策略并行学习的异构PSO算法(MHPSO).该算法首先从种群多样性和跳出局部极值的角度提出了两种新学习策略(局部扰动学习策略和高斯子空间学习策略),并将这两种策略与MBB-PSO策略融合组成高效稳定的策略池.其次提出了一种简单有效的策略更换机制,指导粒子迭代寻优中何时更换学习策略.基准测试函数的实验结果表明,改进的粒子群优化算法在求解精度和收敛速度上得到极大的提高.与一些改进PSO算法(如自适应的粒子群优化(APSO)算法等)相比,所提算法具有更优良的寻优性能.     

Discrete symbiotic organisms search algorithm for travelling salesman problem

A Discrete Symbiotic Organisms Search (DSOS) algorithm for finding a near optimal solution for the Travelling Salesman Problem (TSP) is proposed. The SOS is a metaheuristic search optimization algorithm, inspired by the symbiotic interaction strategies often adopted by organisms in the ecosystem for survival and propagation. This new optimization algorithm has been proven to be very effective and robust in solving numerical optimization and engineering design problems. In this paper, the SOS is improved and extended by using three mutation-based local search operators to reconstruct its population, improve its exploration and exploitation capability, and accelerate the convergence speed. To prove that the proposed solution approach of the DSOS is a promising technique for solving combinatorial problems like the TSPs, a set of benchmarks of symmetric TSP instances selected from the TSPLIB library are used to evaluate its performance against other heuristic algorithms. Numerical results obtained show that the proposed optimization method can achieve results close to the theoretical best known solutions within a reasonable time frame.     

Immigrant Population Search Algorithm for Solving Constrained Optimization Problems

This article introduces the Immigrant Population Search Algorithm (IPSA) inspired by the pattern of human population migration to find better habitats. The algorithm is viewed as a new optimization method for solving constrained optimization problems, and it belongs to the set of population-based algorithms that are proposed for combinatorial optimization. In this algorithm, the life environment is the solution space of the problem. Every point of this space is a solution for the problem, which may be feasible or infeasible, and the quality of life at that point is the value of fitness function for that solution. Each population group tries to investigate feasible and better habitats. In other words, it tries to optimize the problem. After the algorithm steps are described, the efficiency of the algorithm is compared to that of three other metaheuristic algorithms that are used to optimize some mathematic problems. The results show that the proposed algorithm performs better than the other three methods.     

Central force optimization on a GPU: a case study in high performance metaheuristics

Central Force Optimization (CFO) is a new and deterministic population based metaheuristic algorithm that has been demonstrated to be competitive with other metaheuristic algorithms such as Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Group Search Optimization (GSO). While CFO often shows superiority in terms of functional evaluations and solution quality, the algorithm is complex and typically requires increased computational time. In order to decrease the computational time required for convergence when using CFO, this study presents the first parallel implementation of CFO on a Graphics Processing Unit (GPU) using the NVIDIA Compute Unified Device Architecture (CUDA). Two versions of the CFO algorithm, Parameter-Free CFO (PF-CFO) and Pseudo-Random CFO (PR-CFO), are implemented using CUDA on a NVIDIA Quadro 1000M and examined using four test problems ranging from 10 to 50 dimensions. Discussion is made concerning the implementation of the CFO algorithms in terms of problem decomposition, memory access, scalability, and divergent code. Results demonstrate substantial speedups ranging from roughly 1 to 28 depending on problem size and complexity.     

基于自适应Tent混沌搜索的粒子群优化算法

为解决粒子群优化算法易于陷入局部最优问题,提出基于自适应Tent混沌搜索的粒子群优化算法。应用Tent 映射初始化均匀分布的粒群,并以当前整个粒子群迄今为止搜索到的最优位置为基础产生Tent混沌序列,混沌序列的搜索范围采用自适应调整方法。该方法可以有效避免计算的盲目性,还能够快速搜寻到最优解。实验表明该算法在多个标准测试函数下都超越了同类改进算法。     

Two-stage updating pheromone for invariant ant colony optimization algorithm

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO algorithm.     

Quantum-inspired evolutionary algorithms with a new termination criterion, H/sub /spl epsi// gate, and two-phase scheme

From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.     

Hierarchical heterogeneous particle swarm optimization: algorithms and evaluations

Particle swarm optimization (PSO) has recently been extended in several directions. Heterogeneous PSO (HPSO) is one of such recent extensions, which implements behavioural heterogeneity of particles. In this paper, we propose a further extended version, Hierarchcial Heterogeenous PSO (HHPSO), in which heterogeneous behaviors of particles are enforced through interactions among hierarchically structured particles. Two algorithms have been developed and studied: multi-layer HHPSO (ml-HHPSO) and multi-group HHPSO (mg-HHPSO). In each HHPSO algorithm, stagnancy and overcrowding detection mechanisms were implemented to avoid premature convergence. The algorithm performance was measured on a set of benchmark functions and compared with performances of standard PSO (SPSO) and HPSO. The results demonstrated that both ml-HHPSO and mg-HHPSO performed well on all testing problems and significantly outperformed SPSO and HPSO in terms of solution accuracy, convergence speed and diversity maintenance. Further computational experiments revealed the optimal frequencies of stagnation and overcrowding detection for each HHPSO algorithm.     

Nonlinear continuous multi-response problems: a novel two-phase hybrid genetic based metaheuristic

Generally the most real world production systems are tackling several different responses and the problem is optimizing these responses concurrently. This study strives to present a new two-phase hybrid genetic based metaheuristic for optimizing nonlinear continuous multi-response problems. Premature convergence and getting stuck in local optima, which makes the algorithm time consuming, are common problems dealing with genetic algorithms (GAs). So we hybridize GA with a clustering approach and particle swarm optimization algorithm (PSO) to make a balanced relationship between time consuming and premature termination. The proposed algorithm also tries to find Ideal Points (IPs) for response functions. IPs are considered as improvement measures that determine when PSO should start. PSO based local search exploit Pareto archive solutions to enhance performance of the algorithm by expanding the search space. Since there is no standard benchmark in this field, we use two case studies from distinguished paper in multi-response optimization and compare the results with some of the mentioned algorithms in the literature. Results show the outperformance of the proposed algorithm than all of them.     

一种改进的求解TSP混合粒子群优化算法

为解决粒子群算法在求解组合优化问题中存在的早熟性收敛和收敛速度慢等问题,将粒子群算法与局部搜索优化算法结合,可抑制粒子群算法早熟收敛问题,提高粒子群算法的收敛速度。通过建立有效的局部搜索优化算法所需借助的参照优化边集,提高了局部搜索优化算法的求解质量和求解效率。新的混合粒子群算法高效收敛于中小规模旅行商问题的全局最优解,实验表明改进的混合粒子群算法是有效的。     

基于模拟退火的自适应粒子群优化算法的改进策略

针对PSO算法在求解问题的优化问题中易陷入局部收敛且收敛速度较慢等缺陷,引入一种初始化改进策略,并将模拟退火算法与PSO算法相结合,提出了一种全新的算法。该算法将寻优过程分为两个阶段:为了提高算法的执行速度,前期使用标准PSO算法进行寻优,后期运用模拟退火思想对PSO中的参数进行优化搜索最优解。最后将该算法应用于八个经典的单峰/多峰函数中。模拟结果表明,该算法有效地避免了早熟收敛现象,并提高了收敛速度,从而提高了PSO算法解决全局优化的性能。     

基于PSO信息传递模式的混合算法

粒子群优化算法（Particle Swarm Optimization,PSO）是一种基于群智能（Swarm Intelligence）的随机优化计算技术。PSO和遗传算法这两种算法相比较,PSO收敛快速准确,但编码形式单一,局限于解决实优化问题,而遗传算法编码形式灵活,解决问题广泛,但执行效率低于PS00。将粒子群算法的信息传递模式与遗传算法的编码和遗传操作相结合,提出一种混合算法。并推导了两个算法之间的密切联系。并通过组合优化和函数优化的基准测试集对算法进行测试,试验结果表明,该算法在收敛精度和速度优于传统遗传算法。同时,也观察到该算法取得了与粒子群算法一致的收敛现象。     

求解0-1背包问题的交叉熵方法

交叉熵方法是近几年发展起来的一种优化方法,被应用到许多组合优化问题的求解中并显示出很好的性能.文中使用交叉熵方法来求解一种经典的组合优化问题-0-1背包问题.具体方法是:首先按Bernoulli分布生成变量的随机样本,并根据约束条件修正样本,求出目标函数值样本,然后按照交叉熵最小原理建立分布参数的更新规则.建立了基于交叉熵方法的背包问题求解算法.数值实验表明,与目前常用方法相比,该方法在收敛速度和稳定性上都有较大的优势.     

基于随机惯性权重的简化粒子群优化算法

针对标准粒子群优化算法易出现早熟收敛、搜索速度慢及寻优精度低等缺陷, 提出一种基于随机惯性权重的简化粒子群优化算法。算法采用去除速度项的粒子群简化结构, 通过随机分布的方式获取惯性权重提高新算法的局部搜索和全局搜索能力, 并且学习因子采用异步变化的策略来改善粒子的学习能力。考虑到个体之间的相互影响关系, 每个粒子的个体极值用所有粒子个体极值的平均值代替。通过几个典型测试函数仿真及F-检验结果表明, 提出的算法在搜索速度、收敛精度、鲁棒性方面较已有改进算法有了显著提高, 并且具有摆脱陷入局部最优解的能力。     

基于二次搜索的改进粒子群算法

针对标准粒子群优化（PSO）算法在求解复杂优化问题中出现的早熟收敛问题,提出一种结合梯度下降法的二次搜索粒子群算法。首先,当全局极值超过预设的最大不变迭代次数时,判断全局极值点处于极值陷阱中;然后,采用梯度下降法进行二次搜索,并以最优极值点为中心、某一具体半径设定禁忌区域,防止粒子重复搜索该区域;最后,依据种群多样性准则生成新粒子,替代被淘汰的粒子。将二次搜索粒子群算法及其他四种典型的改进粒子群算法分别应用于四种典型测试函数的优化,仿真结果表明,二次搜索粒子群算法收敛精度最高提升了10个数量级,并且收敛速度较快更容易寻找全局最优解。