An efficient memory-based electromagnetism-like mechanism for the redundancy allocation problem

Meta-heuristic algorithms have been successfully applied to solve the redundancy allocation problem in recent years. Among these algorithms, the electromagnetism-like mechanism (EM) is a powerful population-based algorithm designed for continuous decision spaces. This paper presents an efficient memory-based electromagnetism-like mechanism called MBEM to solve the redundancy allocation problem. The proposed algorithm employs a memory matrix in local search to save the features of good solutions and feed it back to the algorithm. This would make the search process more efficient. To verify the good performance of MBEM, various test problems, especially the 33 well-known benchmark instances in the literature, are examined. The experimental results show that not only optimal solutions of all benchmark instances are obtained within a reasonable computer execution time, but also MBEM outperforms EM in terms of the quality of the solutions obtained, even for large-size problems.     

A hybrid particle swarm optimization algorithm for the vehicle routing problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for successfully solving one of the most popular supply chain management problems, the vehicle routing problem. The vehicle routing problem is considered one of the most well studied problems in operations research. The proposed algorithm for the solution of the vehicle routing problem, the hybrid particle swarm optimization (HybPSO), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search–greedy randomized adaptive search procedure (MPNS–GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is suitable for solving very large-scale vehicle routing problems as well as other, more difficult combinatorial optimization problems, within short computational time. It is tested on a set of benchmark instances and produced very satisfactory results. The algorithm is ranked in the fifth place among the 39 most known and effective algorithms in the literature and in the first place among all nature inspired methods that have ever been used for this set of instances.     

A Probabilistic Memetic Framework

Memetic algorithms (MAs) represent one of the recent growing areas in evolutionary algorithm (EA) research. The term MAs is now widely used as a synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search. Quite often, MAs are also referred to in the literature as Baldwinian EAs, Lamarckian EAs, cultural algorithms, or genetic local searches. In the last decade, MAs have been demonstrated to converge to high-quality solutions more efficiently than their conventional counterparts on a wide range of real-world problems. Despite the success and surge in interests on MAs, many of the successful MAs reported have been crafted to suit problems in very specific domains. Given the restricted theoretical knowledge available in the field of MAs and the limited progress made on formal MA frameworks, we present a novel probabilistic memetic framework that models MAs as a process involving the decision of embracing the separate actions of evolution or individual learning and analyzing the probability of each process in locating the global optimum. Further, the framework balances evolution and individual learning by governing the learning intensity of each individual according to the theoretical upper bound derived while the search progresses. Theoretical and empirical studies on representative benchmark problems commonly used in the literature are presented to demonstrate the characteristics and efficacies of the probabilistic memetic framework. Further, comparisons to recent state-of-the-art evolutionary algorithms, memetic algorithms, and hybrid evolutionary-local search demonstrate that the proposed framework yields robust and improved search performance.      

基于关联度函数的决策树分类算法

为了克服决策树算法中普遍存在的多值偏向问题,提出了一种新的基于关联度函数的决策树算法--AF算法,并从理论上分析了它克服多值偏向的原理。通过实验发现,与ID3算法比较,AF算法不仅克服了多值偏向问题,而且保持了较高的分类正确率。     

Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups

This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16–17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems.     

Improving GASAT by replacing tabu search by DLM and enhancing the best members

The satisfiability problem (SAT), as one of the six basic core NP-complete problems, has been the deserving object of many studies in the last two decades (Lardeux et al. 2005, 2006). GASAT (Lardeux et al. 2005, 2006; Hao et al. 2002) is one of the current state-of-the-art genetic algorithms for solving SATs. Besides, the discrete lagrange-multiplier (DLM) (Wu and Wah 1999a, b) is one of the current state-of-the-art local search algorithms for solving SATs. GASAT is a hybrid algorithm of the genetic and tabu search techniques. GASAT uses tabu search to avoid restarting the search once it converges. In this paper, we improve GASAT by replacing the tabu search by the DLM algorithm. We show that the performance of the new algorithm, DGASAT, is far better than the performance of GASAT in solving most of the benchmark instances. We further improve DGASAT by introducing the notion of improving one of the best members in the current population at a time. We show through experimentation that DGASAT + is far better than DGASAT in solving nearly all the benchmark instances.     

Ensemble of multi-objective metaheuristic algorithms for multi-objective unconstrained binary quadratic programming problem

Metaheuristics have been widely utilized for solving NP-hard optimization problems. However, these algorithms usually perform differently from one problem to another, i.e., one may be effective on a problem but performs badly on another problem. Therefore, it is difficult to choose the best algorithm in advance for a given problem. In contrast to selecting the best algorithm for a problem, selection hyper-heuristics aim at performing well on a set of problems (instances). This paper proposes a selection hyper-heuristic based algorithm for multi-objective optimization problems. In the proposed algorithm, multiple metaheuristics exhibiting different search behaviors are managed and controlled as low-level metaheuristics in an algorithm pool, and the most appropriate metaheuristic is selected by means of a performance indicator at each search stage. To assess the performance of the proposed algorithm, an implementation of the algorithm containing four metaheuristics is proposed and tested for solving multi-objective unconstrained binary quadratic programming problem. Experimental results on 50 benchmark instances show that the proposed algorithm can provide better overall performance than single metaheuristics, which demonstrates the effectiveness of the proposed algorithm.     

A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems

This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms and heuristics in the literature.     

A tabu search based hybrid evolutionary algorithm for the max-cut problem

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.     

Minimum common string partition: on solving large‐scale problem instances

Minimum common string partition is an NP‐hard combinatorial optimization problem from the bioinformatics field. The current state‐of‐the‐art algorithm is a hybrid technique known as construct, merge, solve, and adapt (CMSA). This algorithm combines two main algorithmic components: generating solutions in a probabilistic way and solving reduced subinstances obtained from the tackled problem instances, if possible, to optimality. However, the CMSA algorithm was not intended for application to very large problem instances. Therefore, in this paper we present a technique that makes CMSA, and other available algorithms for this problem, applicable to problem instances that are about one order of magnitude larger than the largest problem instances considered so far. Moreover, a reduced variable neighborhood search (RVNS) for solving the tackled problem, based on integer programming, is introduced. The experimental results show that the modified CMSA algorithm is very strong for problem instances based on rather small alphabets. With growing alphabet size, it turns out that RVNS has a growing advantage over CMSA.     

Hybrid whale optimization algorithm enhanced with Lévy flight and differential evolution for job shop scheduling problems

The job shop scheduling problem (JSSP) has been a hot issue in manufacturing. For the past few decades, scholars have been attracted to research JSSP and proposed many novel meta-heuristic algorithms to solve it. Whale optimization algorithm (WOA) is such a novel meta-heuristic algorithm and has been proven to be efficient in solving real-world optimization problems in the literature. This paper proposes a hybrid WOA enhanced with Lévy flight and differential evolution (WOA-LFDE) to solve JSSP. By changing the expression of Lévy flight and DE search strategy, Lévy flight enhances the abilities of global search and convergence of WOA in iteration, while DE algorithm improves the exploitation and local search capabilities of WOA and keeps the diversity of solutions to escape local optima. It is then applied to solve 88 JSSP benchmark instances and compared with other state-of-art algorithms. The experimental results and statistical analysis show that the proposed algorithm has superior performance over contesting algorithms.     

A parallel local search framework for the Fixed-Charge Multicommodity Network Flow problem

We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multicommodity Network Flow problem (FCMNF). The approach proceeds by improving a given feasible solution by solving restricted instances of the problem where flows of certain commodities are fixed to those in the solution while the other commodities are locally optimized. We derive multiple independent local search neighborhoods from an arc-based mixed integer programming (MIP) formulation of the problem which are explored in parallel. Our scalable parallel implementation takes advantage of the hybrid memory architecture in modern platforms and the effectiveness of MIP solvers in solving small problems instances. Computational experiments on FCMNF instances from the literature demonstrate the competitiveness of our approach against state of the art MIP solvers and other heuristic methods.     

Cooperative group optimization with ants (CGO-AS): Leverage optimization with mixed individual and social learning

We present CGO-AS, a generalized ant system (AS) implemented in the framework of cooperative group optimization (CGO), to show the leveraged optimization with a mixed individual and social learning. Ant colony is a simple yet efficient natural system for understanding the effects of primary intelligence on optimization. However, existing AS algorithms are mostly focusing on their capability of using social heuristic cues while ignoring their individual learning. CGO can integrate the advantages of a cooperative group and a low-level algorithm portfolio design, and the agents of CGO can explore both individual and social search. In CGO-AS, each ant (agent) is added with an individual memory, and is implemented with a novel search strategy to use individual and social cues in a controlled proportion. The presented CGO-AS is therefore especially useful in exposing the power of the mixed individual and social learning for improving optimization. The optimization performance is tested with instances of the traveling salesman problem (TSP). The results prove that a cooperative ant group using both individual and social learning obtains a better performance than the systems solely using either individual or social learning. The best performance is achieved under the condition when agents use individual memory as their primary information source, and simultaneously use social memory as their searching guidance. In comparison with existing AS systems, CGO-AS retains a faster learning speed toward those higher-quality solutions, especially in the later learning cycles. The leverage in optimization by CGO-AS is highly possible due to its inherent feature of adaptively maintaining the population diversity in the individual memory of agents, and of accelerating the learning process with accumulated knowledge in the social memory.     

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。     

On the hybridization of memetic algorithms with branch-and-bound techniques.

Branch-and-bound (BnB) and memetic algorithms represent two very different approaches for tackling combinatorial optimization problems. However, these approaches are compatible. In this correspondence, a hybrid model that combines these two techniques is considered. To be precise, it is based on the interleaved execution of both approaches. Since the requirements of time and memory in BnB techniques are generally conflicting, a truncated exact search, namely, beam search, has opted to be carried out. Therefore, the resulting hybrid algorithm has a heuristic nature. The multidimensional 0-1 knapsack problem and the shortest common supersequence problem have been chosen as benchmarks. As will be shown, the hybrid algorithm can produce better results in both problems at the same computational cost, especially for large problem instances.     

优化简单表缩减算法求解因子分解编码实例

表约束在约束程序（constraint programming,简称CP）中被广泛研究.目前,求解表约束问题效率最高的算法是CT （compact-table）和STRbit （simple tabular reduction bit）.它们在搜索过程中维持广义弧相容（generalized arc consistency,简称GAC）.完全成对相容（full pairwise consistency,简称fPWC）是一种强于GAC的相容性关系,目前,实现fPWC效率最高的算法是PW-CT,但是它无法直接在通用的求解器上实现.因子分解编码（factor-decomposition encoding,简称FDE）是实现fPWC的一种编码方式,通常和简单表缩减（STR）算法一起来使用.当前效率最高的STR算法使用了bitset的数据结构,用这些算法来求解FDE实例可能会造成内存溢出.提出了STRFDE算法——一种使用bitset结构来求解FDE实例的方法.它结合了CT和STRbit的优势,在保证求解效率的同时,使占用的内存尽可能小.实验结果表明,在许多存在非平凡相交的实例上,该算法是有竞争力的.     

Multi-operator based evolutionary algorithms for solving constrained optimization problems

Over the last two decades, many sophisticated evolutionary algorithms have been introduced for solving constrained optimization problems. Due to the variability of characteristics in different COPs, no single algorithm performs consistently over a range of problems. In this paper, for a better coverage of the problem characteristics, we introduce an algorithm framework that uses multiple search operators in each generation. The appropriate mix of the search operators, for any given problem, is determined adaptively. The framework is tested by implementing two different algorithms. The performance of the algorithms is judged by solving 60 test instances taken from two constrained optimization benchmark sets from specialized literature. The first algorithm, which is a multi-operator based genetic algorithm (GA), shows a significant improvement over different versions of GA (each with a single one of these operators). The second algorithm, using differential evolution (DE), also confirms the benefit of the multi-operator algorithm by providing better and consistent solutions. The overall results demonstrated that both GA and DE based algorithms show competitive, if not better, performance as compared to the state of the art algorithms.     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

求解作业车间调度问题的改进混合灰狼优化算法*

灰狼优化算法(GWO)是目前一种比较新颖的群智能优化算法,具有收敛速度快,寻优能力强等优点。本文将灰狼优化算法用于求解复杂的作业车间调度问题,与布谷鸟搜索算法进行比较研究,验证了标准GWO算法求解经典作业车间调度问题的可行性和有效性。在此基础上,针对复杂作业车间调度问题难以求解的特点,对标准GWO算法进行改进,通过进化种群动态、反向学习初始化种群,以及最优个体变异等三个方面的改进操作,测试结果表明改进后的混合灰狼优化算法能够有效跳出局部最优值,找到更好的解,并且结果鲁棒性更强。