A hybrid evolutionary algorithm for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) is an NP-hard optimization problem. RCPSP is one of the most important and challenging problems in the project management field. In the past few years, many researches have been proposed for solving the RCPSP. The objective of this problem is to schedule the activities under limited resources so that the project makespan is minimized. This paper proposes a new algorithm for solving RCPSP that combines the concepts of negative selection mechanism of the biologic immune system, simulated annealing algorithm (SA), tabu search algorithm (TS) and genetic algorithm (GA) together. The performance of the proposed algorithm is evaluated and compared to current state-of-the-art metaheuristic algorithms. In this study, the benchmark data sets used in testing the performance of the proposed algorithm are obtained from the project scheduling problem library. The performance is measured in terms of the average percentage deviation from the critical path lower bound. The experimental results show that the proposed algorithm outperforms the state-of-the-art metaheuristic algorithms on all standard benchmark data sets.     

Iterative improvement to solve the parcel hub scheduling problem

This paper presents iterative improvement algorithms to solve the parcel hub scheduling problem (PHSP). The PHSP is combinatorial optimization problem that consists of scheduling a set of inbound trailers to a small number of unload docks. At the unload docks, the inbound trailers must be unloaded and the parcel sorted and loaded onto outbound trailers. Because the transfer operation is labor intensive, the transfer of parcels must be done in such a way as to minimize the timespan of the transfer operation. Local search (LS) and simulated annealing (SA) algorithms are developed and evaluated to solve the problem. The performances of the algorithms are compared to the performance of an existing genetic algorithm (GA). The computational results show that the LS and SA algorithms offer solutions that are superior to those offered by the GA.     

An Electromagnetism-like algorithm for cell formation and layout problem

Implementation of cellular manufacturing systems (CMS) is thriving among manufacturing companies due to many advantages that are attained by applying this system. In this study CMS formation and layout problems are considered. An Electromagnetism like (EM-like) algorithm is developed to solve the mentioned problems. In addition the required modifications to make EM-like algorithm applicable in these problems are mentioned. A heuristic approach is developed as a local search method to improve the quality of solution of EM-like. Beside in order to examine its performance, it is compared with two other methods. The performance of EM-like algorithm with proposed heuristic and GA are compared and it is demonstrated that implementing EM-like algorithm in this problem can improve the results significantly in comparison with GA. In addition some statistical tests are conducted to find the best performance of EM-like algorithm and GA due to their parameters. The convergence diagrams are plotted for two problems to compare the convergence process of the algorithms. For small size problems the performances of the algorithms are compared with an exact algorithm (Branch & Bound).     

一种新的求解0-1背包问题的混合算法

该文汲取了蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种求解0-1背包问题的混合型算法,该算法充分利用了前者的搜索能力和后者的种群多样性。仿真实验对算法的部分参数进行了分析,并与其他文献的算法进行比较,结果表明,该算法是一种具有较高性能的混合优化算法。     

Ant colony optimization algorithm for the Euclidean location-allocation problem with unknown number of facilities

This paper addresses the Euclidean location-allocation problem with an unknown number of facilities, and an objective of minimizing the fixed and transportation costs. This is a NP-hard problem and in this paper, a three-stage ant colony optimization (ACO) algorithm is introduced and its performance is evaluated by comparing its solutions to the solutions of genetic algorithms (GA). The results show that ACO outperformed GA and reached better solutions in a faster computational time. Furthermore, ACO was tested on the relaxed version of the problem where the number of facilities is known, and compared to existing methods in the literature. The results again confirmed the superiority of the proposed algorithm.     

Application of metaheuristics-based clustering algorithm to item assignment in a synchronized zone order picking system

Warehousing management policy is a crucial issue in logistic management. It must be managed effectively and efficiently to reduce the production cost as well as the customer satisfaction. Synchronized zoning system is a warehousing management policy which aims to increase the warehouse utilization and customer satisfaction by reducing the customer waiting time. This policy divides a warehouse into several zones where each zone has its own picker who can work simultaneously. Herein, item assignment plays an important role since it influences the order processing performance. This study proposes an application of metaheuristic algorithms, namely particle swarm optimization (PSO) and genetic algorithm (GA), for item assignment in synchronized zoning system. The original PSO and GA algorithms are modified so that it is suitable for solving item assignment problem. The datasets with different sizes are used for method validation. Results obtained by PSO and GA are then compared with the result of an existing algorithm. The experimental results showed that PSO and GA can perform better than the existing algorithm. These results also show that PSO has better performance than GA, especially for bigger problems. It proves that item assignment policy obtained by PSO and GA has higher utilization rates than the existing algorithm.     

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 novel ACO–GA hybrid algorithm for feature selection in protein function prediction

Protein function prediction is an important problem in functional genomics. Typically, protein sequences are represented by feature vectors. A major problem of protein datasets that increase the complexity of classification models is their large number of features. Feature selection (FS) techniques are used to deal with this high dimensional space of features. In this paper, we propose a novel feature selection algorithm that combines genetic algorithms (GA) and ant colony optimization (ACO) for faster and better search capability. The hybrid algorithm makes use of advantages of both ACO and GA methods. Proposed algorithm is easily implemented and because of use of a simple classifier in that, its computational complexity is very low. The performance of proposed algorithm is compared to the performance of two prominent population-based algorithms, ACO and genetic algorithms. Experimentation is carried out using two challenging biological datasets, involving the hierarchical functional classification of GPCRs and enzymes. The criteria used for comparison are maximizing predictive accuracy, and finding the smallest subset of features. The results of experiments indicate the superiority of proposed algorithm.     

A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems

This article addresses the problem of hybrid flexible flow line where some constraints are considered to alleviate the chasm between the real-world industries scheduling and the production scheduling theories. Sequence-dependent setup times, machine release date and time lags are three constraints deemed to project the circumstances commonly found in real-world industries. To tackle the complexity of the problem at hand, we propose an approach base on genetic algorithm (GA). However, the performance of most evolutionary algorithms is significantly impressed by the values determined for the miscellaneous parameters which these algorithms possess. Hence, response surface methodology is applied to set the parameters of GA and to estimate the proper values of GA parameters in continually intervals. Finally, problems of various sizes are utilized to test the performance of the proposed algorithm and to compare it with some existing heuristic in the literature such as SPT, LPT and NEH.     

Multi-objective optimization of stochastic disassembly line balancing with station paralleling

One of the major activities performed in product recovery is disassembly. Disassembly line is the most suitable setting to disassemble a product. Therefore, designing and balancing efficient disassembly systems are important to optimize the product recovery process. In this study, we deal with multi-objective optimization of a stochastic disassembly line balancing problem (DLBP) with station paralleling and propose a new genetic algorithm (GA) for solving this multi-objective optimization problem. The line balance and design costs objectives are simultaneously optimized by using an AND/OR Graph (AOG) of the product. The proposed GA is designed to generate Pareto-optimal solutions considering two different fitness evaluation approaches, repair algorithms and a diversification strategy. It is tested on 96 test problems that were generated using the benchmark problem generation scheme for problems defined on AOG as developed in literature. In addition, to validate the performance of the algorithm, a goal programming approach and a heuristic approach are presented and their results are compared with those obtained by using GA. Computational results show that GA can be considered as an effective and efficient solution algorithm for solving stochastic DLBP with station paralleling in terms of the solution quality and CPU time.     

Data Generation for Path Testing

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms with each other and with a hill-climbing algorithm, Korel's algorithm (KA), for integer-value-input subject programs and compare SA and GA with each other on real-value subject programs. Our empirical work uses several subject programs with a number of paths. The results show that: (a) SA and GA are superior to KA in the number of executed paths, (b) SA tends to perform slightly better than GA in terms of the number of executed paths, and (c) GA is faster than SA; however, KA, when it succeeds in finding the solution, is the fastest.     

A Genetic Algorithm Based on Relaxation Induced Neighborhood Search in a Local Branching Framework for Capacitated Multicommodity Network Design

The fixed-charge Capacitated Multicommodity Network Design (CMND) is a well-known problem of both practical and theoretical significance. This article proposes the Genetic Algorithm (GA) cooperative Relaxation Induced Neighborhood Search (RINS) in a Local Branching (LB) framework for CMND problem. GA algorithm is started by initial population which is made by two parents obtain from hybrid LB and RINS algorithms. The basic idea of the proposed solution method is to use the GA algorithm to explore the search space and the hybrid LB and RINS methods to move from current solution to neighbor solution. Adapting the metaheuristic algorithm with RINS method to fit within an LB framework represents an interesting challenge. To evaluate the proposed algorithm, the standard problems with different sizes are used. The parameters of the algorithm are tuned by design of experiments. In order to prove the efficiency and effectiveness of the proposed algorithm, the results are compared with the best results available in the literature. The statistical analysis shows high performance of the proposed algorithm.     

Matrix-Based Genetic Algorithm for Computing the Minimum Volume Ellipsoid

The minimum volume ellipsoid (MVE) is a useful tool in multivariate statistics and data mining. It is used for computing robust multivariate outlier diagnostics and for calculating robust covariance matrix estimates. Various search algorithms for finding or approximating the MVE have been developed, but due to the combinatorial nature of the problem, exact computation of the MVE is impractical for all but the smallest datasets. Since large datasets are increasingly common, alternative algorithms are desired. Even among small datasets, performance of the existing algorithms varies considerably—no single algorithm dominates in performance. This paper presents a unique matrix-structured genetic algorithm (GA) that directly searches the ellipsoid space for the MVE. By directly searching the space of ellipsoids, the impact of the combinatorial nature of the problem is minimized. The matrix-structured GA is described in detail, and evidence is provided to illustrate the performance of the new algorithm in detecting multivariate outliers.      

Block transportation scheduling under delivery restriction in shipyard using meta-heuristic algorithms

Special vehicles called transporters are used to deliver heavy blocks from one plant to another in shipyards. Because of the limitation on the number of transporters, the scheduling of transporters is important for maintaining the overall production schedule of the blocks. This paper considers a scheduling problem of block transportation under a delivery restriction to determine when and by which transporter each block is delivered from its source plant to its destination plant. The objective of the problem is to minimize the penalty times that can cause delays in the overall block production schedule. A mathematical model for the optimal solution is derived, and two meta-heuristic algorithms based on a genetic algorithm (GA) and a self-evolution algorithm (SEA) are proposed. The performance of the algorithms is evaluated with several randomly generated experimental examples.     

Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem

Finding a Pareto-optimal frontier is widely favorable among researchers to model existing conflict objectives in an optimization problem. Project scheduling is a well-known problem in which investigating a combination of goals eventuate in a more real situation. Although there are many different types of objectives based on the situation on hand, three basic objectives are the most common in the literature of the project scheduling problem. These objectives are: (i) the minimization of the makespan, (ii) the minimization of the total cost associated with the resources, and (iii) the minimization of the variability in resources usage. In this paper, three genetic-based algorithms are proposed for approximating the Pareto-optimal frontier in project scheduling problem where the above three objectives are simultaneously considered. For the above problem, three self-adaptive genetic algorithms, namely (i) A two-stage multi-population genetic algorithm (MPGA), (ii) a two-phase subpopulation genetic algorithm (TPSPGA), and (iii) a non-dominated ranked genetic algorithm (NRGA) are developed. The algorithms are tested using a set of instances built from benchmark instances existing in the literature. The performances of the algorithms are evaluated using five performance metrics proposed in the literature. Finally according to the technique for order preference by similarity to ideal solution (TOPSIS) the self-adaptive NRGA gained the highest preference rank, followed by the self-adaptive TPSPGA and MPGA, respectively.     

Self-adaptive Bat Algorithm With Genetic Operations

Swarm intelligence in a bat algorithm (BA) provides social learning. Genetic operations for reproducing individuals in a genetic algorithm (GA) offer global search ability in solving complex optimization problems. Their integration provides an opportunity for improved search performance. However, existing studies adopt only one genetic operation of GA, or design hybrid algorithms that divide the overall population into multiple subpopulations that evolve in parallel with limited interactions only. Differing from them, this work proposes an improved self-adaptive bat algorithm with genetic operations (SBAGO) where GA and BA are combined in a highly integrated way. Specifically, SBAGO performs their genetic operations of GA on previous search information of BA solutions to produce new exemplars that are of high-diversity and high-quality. Guided by these exemplars, SBAGO improves both BA’s efficiency and global search capability. We evaluate this approach by using 29 widely-adopted problems from four test suites. SBAGO is also evaluated by a real-life optimization problem in mobile edge computing systems. Experimental results show that SBAGO outperforms its widely-used and recently proposed peers in terms of effectiveness, search accuracy, local optima avoidance, and robustness.      

定位—运输路线安排问题的遗传算法研究

定位—运输路线安排问题(LRP)是分销网络设计和物流管理决策中的难题。由于LRP是NP-complete问题,对它的求解方法大多局限于将其分解为定位—分配问题和车辆运输路线安排问题,或者是基于这种分解思想。文章通过对遗传算法(GA)中树编码、免疫遗传算法以及GA阶段进化策略深入地分析和研究,构建了定位—运输路线安排问题的遗传算法,它与以往算法最大的不同点就是并没有基于两阶段求解的思路,而是将LRP的解看作一个整体,从而减小了在进化过程中停滞于局部最优解的概率,提高了GA的计算效率和计算速度。文中详细叙述了针对LRP问题的树编码、交叉、变异、爬山、免疫、合并小路线等各种算子设计过程,并利用一实例来验证算法的可行性。该算法为LRP问题以及相关大规模组合优化问题的求解开辟了一个新的思路,同时也为GA中树编码在实际中应用做了有益的尝试。     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.     

一种解决TSP的改进遗传算法

旅行推销员问题TSP(Traveling Salesman Problem)问题是组合优化中的经典NP难题,一些典型的遗传算法(GA)在求解TSP问题时的性能并不理想.提出基于"最小邻域接入法"CBMC(Connecting Based on Minimum Circle)思想的改进的遗传算法,并在算法中增加一些控制策略,与其他算法相比,获得了更好的性能和收敛速度.通过用中国33个省会的TSP问题对提出算法进行实验验证,结果证明了改进后的算法在收敛速度和收敛到最优解的概率都优于其他遗传算法.