Evolutionary algorithms for production planning problems with setup decisions

Production planning problems with setup decisions, which were formulated as mixed integer programmes (MIP), are solved in this study. The integer component of the MIP solution is determined by three evolution algorithms used in this study. Firstly, a traditional genetic algorithm (GA) uses conventional crossover and mutation operators for generating new chromosomes (solutions). Secondly, a modified GA uses not only the conventional operators but also a sibling operator, which stochastically produces new chromosomes from old ones using the sensitivity information of an associated linear programme. Thirdly, a sibling evolution algorithm uses only the sibling operator to reproduce. Based on the experiments done in this study, the sibling evolution algorithm performs the best among all the algorithms used in this study.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

Single row facility layout problem using a permutation-based genetic algorithm

In this paper, a permutation-based genetic algorithm (GA) is applied to the NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP). The GA individuals are obtained by using some rule-based as well as random permutations of the facilities, which are then improved towards the optimum by means of specially designed crossover and mutation operators. Such schemes led the GA to handle the SRFLP as an unconstrained optimization problem. In the computational experiments carried out with large-size instances of sizes from 60 to 80, available in the literature, the proposed GA improved several previously known best solutions.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

A Genetic Algorithm for Solving a Capacitated p-Median Problem

Facility-location problems have several applications, such as telecommunications, industrial transportation and distribution. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated p-median problem. The proposed GA uses not only conventional genetic operators, but also a new heuristic “hypermutation” operator suggested in this work. The proposed GA is compared with a tabu search algorithm.     

Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation

The Biogeography-Based Optimization algorithm and its variants have been used widely for optimization problems. To get better performance, a novel Biogeography-Based Optimization algorithm with Hybrid migration and global-best Gaussian mutation is proposed in this paper. Firstly, a linearly dynamic random heuristic crossover strategy and an exponentially dynamic random differential mutation one are presented to form a hybrid migration operator, and the former is used to get stronger local search ability and the latter strengthen the global search ability. Secondly, a new global-best Gaussian mutation operator is put forward to balance exploration and exploitation better. Finally, a random opposition learning strategy is merged to avoid getting stuck in local optima. The experiments on the classical benchmark functions and the complexity functions from CEC-2013 and CEC-2017 test sets, and the Wilcoxon, Bonferroni-Holm and Friedman statistical tests are used to evaluate our algorithm. The results show that our algorithm obtains better performance and faster running speed compared with quite a few state-of-the-art competitive algorithms. In addition, experimental results on Minimum Spanning Tree and K-means clustering optimization show that our algorithm can cope with these two problems better than the comparison algorithms.     

A modified DNA genetic algorithm for parameter estimation of the 2-Chlorophenol oxidation in supercritical water

Based on the mechanism of biological DNA genetic information and evolution, a modified DNA genetic algorithm (MDNA-GA) is proposed to estimate the kinetic parameters of the 2-Chlorophenol oxidation in supercritical water. In this approach, DNA encoding method, choose crossover operator and frame-shift mutation operator inspired by the biological DNA are developed for improving the global searching ability. Besides, an adaptive mutation probability which can be adjusted automatically according to the diversity of population is also adopted. A local search method is used to explore the search space to accelerate the convergence towards global optimum. The performance of MDNA-GA in typical benchmark functions and kinetic parameter estimation is studied and compared with RNA-GA. The experimental results demonstrate that the proposed algorithm can overcome premature convergence and yield the global optimum with high efficiency.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

Advanced particle swarm assisted genetic algorithm for constrained optimization problems

A novel hybrid evolutionary algorithm is developed based on the particle swarm optimization (PSO) and genetic algorithms (GAs). The PSO phase involves the enhancement of worst solutions by using the global-local best inertia weight and acceleration coefficients to increase the efficiency. In the genetic algorithm phase, a new rank-based multi-parent crossover is used by modifying the crossover and mutation operators which favors both the local and global exploration simultaneously. In addition, the Euclidean distance-based niching is implemented in the replacement phase of the GA to maintain the population diversity. To avoid the local optimum solutions, the stagnation check is performed and the solution is randomized when needed. The constraints are handled using an effective feasible population based approach. The parameters are self-adaptive requiring no tuning based on the type of problems. Numerical simulations are performed first to evaluate the current algorithm for a set of 24 benchmark constrained nonlinear optimization problems. The results demonstrate reasonable correlation and high quality optimum solutions with significantly less function evaluations against other state-of-the-art heuristic-based optimization algorithms. The algorithm is also applied to various nonlinear engineering optimization problems and shown to be excellent in searching for the global optimal solutions.     

A novel hybrid genetic algorithm for solving Sudoku puzzles

In this article, a novel hybrid genetic algorithm is proposed. The selection operator, crossover operator and mutation operator of the genetic algorithm have effectively been improved according to features of Sudoku puzzles. The improved selection operator has impaired the similarity of the selected chromosome and optimal chromosome in the current population such that the chromosome with more abundant genes is more likely to participate in crossover; such a designed crossover operator has possessed dual effects of self-experience and population experience based on the concept of tactfully combining PSO, thereby making the whole iterative process highly directional; crossover probability is a random number and mutation probability changes along with the fitness value of the optimal solution in the current population such that more possibilities of crossover and mutation could then be considered during the algorithm iteration. The simulation results show that the convergence rate and stability of the novel algorithm has significantly been improved.     

The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem

In this paper, we present an efficient genetic algorithm (GA) for solving the travelling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that does not break as some good subtours as possible, because the good subtours are worth preserving for descendants. Generally speaking, global search GA is considered to be better approaches than local searches. However, it is necessary to strengthen the ability of local search as well as global ones in order to increase a GA total efficiency. In this study, our GA applies a stochastic hill climbing procedure in the mutation process of the GA. Experimental results showed that the GA leads good convergence as high as 99 percent even for 500 cities TSP.     

广义优先关系约束下Max-npv项目调度问题及其遗传算法

以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。     

改进遗传算法求解旅行商问题

针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中.     

A hybrid evolutionary learning algorithm for TSK-type fuzzy model design

In this paper, a TSK-type fuzzy model (TFM) with a hybrid evolutionary learning algorithm (HELA) is proposed. The proposed HELA method combines the compact genetic algorithm (CGA) and the modified variable-length genetic algorithm (MVGA). Both the number of fuzzy rules and the adjustable parameters in the TFM are designed concurrently by the HELA method. In the proposed HELA method, individuals of the same length constitute the same group, and there are multiple groups in a population. Moreover, the proposed HELA adopts the compact genetic algorithm (CGA) to carry out the elite-based reproduction strategy. The CGA represents a population as a probability distribution over the set of solutions and is operationally equivalent to the order-one behavior of the simple GA. The evolution processes of a population consist of three major operations: group reproduction using the compact genetic algorithm, variable two-part individual crossover, and variable two-part mutation. Computer simulations have demonstrated that the proposed HELA method gives a better performance than some existing methods.     

Mean Convergence Time of Inhomogeneous Genetic Algorithm with Elitism

The theoretical study of a genetic algorithm (GA) has focused mainly on establishing its convergence in probability and almost always to the global optimum. In this article, we establishsufficient conditions for the finiteness of convergence mean time of the genetic algorithm with elitism. We obtain bounds for the probability of convergence to the global optimum in the first n iterations as a by-product.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

Evaluation of the genetic algorithm parameters on the optimization performance: a case study on pump-and-treat remediation design

In this study, the impacts of different crossover and encoding schemes on the performance of a genetic algorithm (GA) in finding optimal pump-and-treat (P&T) remediation designs are investigated. For this purpose, binary and Gray encodings of the decision variables are tested. Uniform and two-point crossover schemes are evaluated for two different crossover probabilities. Analysis is performed for two P&T system optimization scenarios. Results show that uniform crossover operator with Gray encoding outperforms the other alternatives for the complex problem with higher number of decision variables. On the other hand, when a simpler problem, which had a lower number of decision variables, is solved, the efficiency of GA is independent of the encoding and crossover schemes.     

A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions

Genetic algorithms are stochastic search approaches based on randomized operators, such as selection, crossover and mutation, inspired by the natural reproduction and evolution of the living creatures. However, few published works deal with their application to the global optimization of functions depending on continuous variables.A new algorithm called Continuous Genetic Algorithm (CGA) is proposed for the global optimization of multiminima functions. In order to cover a wide domain of possible solutions, our algorithm first takes care over the choice of the initial population. Then it locates the most promising area of the solution space, and continues the search through an intensification inside this area. The selection, the crossover and the mutation are performed by using the decimal code. The efficiency of CGA is tested in detail through a set of benchmark multimodal functions, of which global and local minima are known. CGA is compared to Tabu Search and Simulated Annealing, as alternative algorithms.     

Two warehouse inventory models for single vendor multiple retailers with price and stock dependent demand

Here a single vendor multiple retailer inventory model of an item is developed where demand of the item at every retailer is linearly dependent on stock and inversely on some powers of selling price. Item is produced by the vendor and is distributed to the retailers following basic period policy. According to this policy item is replenished to the retailers at a regular time interval (T₁) called basic period (BP) and replenishment quantity is sufficient to last for the period T₁. Due to the scarcity of storage space at market places, every retailer uses a showroom at the market place and a warehouse to store the item, little away from the market place. Item is sold from the showroom and is filled up from the warehouse in a bulk release pattern. Some of the inventory parameters are considered as fuzzy in nature and model is formulated to maximize the average profit from the whole system. Imprecise objective is transformed to equivalent deterministic ones using possibility/necessity measure of fuzzy events with some degree of optimism/pessimism. A genetic algorithm (GA) is developed with roulette wheel selection, arithmetic crossover and random mutation and is used to solve the model. In some complex cases, with the help of above GA, fuzzy simulation process is used to derive the optimal decision. The model is illustrated through numerical examples and some sensitivity analyses are presented.     

蚁群遗传混合算法

将蚁群遗传混合算法分别求解离散空间的和连续空间优化问题.求解旅行商问题的混合算法是以遗传算法为整个算法的框架,利用了蚁群算法中的信息素特性的进行交叉操作;根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-0pt方法对问题求解进行了局部优化.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.求解连续空间优化问题是以蚁群算法为整个算法的框架,加入遗传算法的交叉操作和变异操作,用测试函数验证了混合蚁群算法的正确性.