Scatter Search and Genetic Algorithms for MAX-SAT Problems

In this paper, both scatter search (SS) and genetic algorithms (GAs) are studied for the NP-Hard optimization variant of the satisfiability problem, namely MAX-SAT. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of a genetic algorithm. The resulting algorithm is enhanced in two ways leading to two genetic algorithm variants: the first one uses a uniform crossover. The second one uses a specific crossover operator (to MAX-SAT). The crossover operator is combined with an improved stochastic local search (SLS). The crossover operator is used to identify promising regions while the stochastic local search performs an intensified search of solutions around these regions. Secondly, we propose a scatter search variant for MAX-SAT. Both the SS and the GAs implementations share the solution selection strategy, the improved SLS method and the combination operator. Experiments on several instances from MAX-SAT libraries are performed to show and compare the effectiveness of our approaches. The computational experiments show that both (SS) and (GAs) with a stochastic local search (SLS) improvement technique outperform a classical genetic algorithm (without SLS). The two metaheuristics are able of balancing search diversification and intensification which leads to good results. In general, the specific genetic algorithm with a (SLS) improvement technique and a specific combination method provides competitive results and finds solutions of a higher quality than a scatter search.     

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.     

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

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

基于种群分类排序的约束优化遗传算法

针对约束优化问题,提出了一类将种群中的个体分类排序的思想.算法的特点在于:先将种群中的解分为可行解和不可行解两类,然后分别按照不同的标准排序.由于很多约束优化问题的最优解位于可行域的边界上或附近,所以排序时并不认为可行解一定优于不可行解.基于此分类排队思想,特别设计了只允许同等级个体进行交叉的新的交叉算子,称之为同等级交叉算子,以及基于一维搜索的变异算子.算法同时采用了保证固定比例不可行解的自适应策略.4个标准测试函数的数值仿真结果验证了算法的有效性.     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

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.     

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.     

Improving crossover operator for real-coded genetic algorithms using virtual parents

The crossover operator is the most innovative and relevant operator in real-coded genetic algorithms. In this work we propose a new strategy to improve the performance of this operator by the creation of virtual parents obtained from the population parameters of localisation and dispersion of the best individuals. The idea consists of mating these virtual parents with individuals of the population. In this way, the offspring are created in the most promising regions. This strategy has been incorporated into several crossover operators. After analysing the results we can conclude that this strategy significantly improves the performance of the algorithm in most problems analysed.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Genetic algorithms and traveling salesman problems

A genetic algorithm (GA) with an asexual reproduction plan through a generalized mutation for an evolutionary operator is developed that can be directly applied to a permutation of n numbers for an approximate global optimal solution of a traveling salesman problem (TSP). Schema analysis of the algorithm shows that a sexual reproduction with the generalized mutation operator preserves the global convergence property of a genetic algorithm thus establishing the fundamental theorem of the GA for the algorithm. Avoiding an intermediate step of encoding through random keys to preserve crossover or permuting n and using “fixing” states for legal crossover are the chief benefits of the innovations reported in this paper. The algorithm has been applied to a number of natural and artificial problems and the results are encouraging.     

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

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

Grey prediction evolution algorithm for global optimization

This article uses the grey prediction theory to structure a new metaheuristic: grey prediction evolution algorithm based on the even grey model. The proposed algorithm considers the population series of evolutionary algorithms as a time series, and uses the even grey model as a reproduction operator to forecast the next population (without employing any mutation and crossover operators). It is theoretically proven that the reproduction operator based on the even grey model is adaptive. Additionally, the algorithmic search mechanism and its differences with other evolutionary algorithms are analyzed. The performance of the proposed algorithm is validated on CEC2005 benchmark functions and a test suite composed of six engineering constrained design problems. The comparison experiments show the effectiveness and superiority of the proposed algorithm.The proposed algorithm can be regarded as the first case of structuring metaheuristics by using the prediction theory. The novel algorithm is anticipated to influence two future works. The first is to propose more metaheuristics inspired by prediction theories (including some statistical algorithms). Another is that the theoretical results of these prediction systems can be used for this novel type of metaheuristics.     

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.     

蚁群遗传混合算法

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

An effective multiagent evolutionary algorithm integrating a novel roulette inversion operator for engineering optimization

Multiagent systems have been studied and widely used in the field of artificial intelligence and computer science to catalyze computation intelligence. In this paper, a multiagent evolutionary algorithm called RAER based on the ERA multiagent modeling pattern is proposed, where ERA has the same architecture as Swarm including three parts of Environment, Reactive rules and Agents. RAER integrates a novel roulette inversion operator (RIO) proposed in this paper and theoretically proved to conquer the irrationality of the inversion operator (IO) designed by John Holland when used for real code stochastic optimization algorithms. Experiments for numerical optimization of 4 benchmark functions show that the RIO operator bears better functioning than IO operator. And experiments for numerical optimization of 12 benchmark functions are used to examine the performance and scalability of RAER along the problem dimensions ranging 20-10 000, results indicate that RAER outperforms other comparative algorithms significantly. Also, two engineering optimization problems of a stable linear system approximation and a welded beam design are used to examine the applicability of RAER. Results show that RAER has better search ability and faster convergence speed. Especially for the approximation problem, REAR can find the proper optima belonging to different fixed search areas, which is significantly better than other algorithms and shows that RAER can search the problem domains more thoroughly than other algorithms. Hence, RAER is efficient and practical.     

改进遗传算法优化非线性规划问题

针对遗传算法在处理优化问题上的独特优势,主要研究遗传算法的改进,并将其应用于优化非线性规划问题.在进化策略上,采用群体精英保留方式,将适应度值低的个体进行变异;交叉算子采用按决策变量分段交叉方式,提高进化速度;在优化有约束非线性规划问题时,引入算子修正法,对非可行个体进行改善.MATLAB仿真实验表明,方法是一种有效的、可靠的、方便的方法.     

改进遗传算法求解TSP问题

提出了一种改进遗传算法求解 TSP.该方法在迭代初期引入不适应度函数作为评价标准 ,结合启发式交叉和边重组交叉算子设计了一种新的交叉算子 ,并对变异后个体进行免疫操作 .此外对操作后群体进行整理 ,删除群体中相同个体 ,得到规模为 N1的中间群体 ,对较优的 N -N 1个个体进行启发式变异 ,并将变异后个体补充进中间群体 ,生成规模为 N的新群体 ,这样保证群体中没有相同个体 ,从而保证群体多样性 .数值结果表明这种改进遗传算法是有效的 .     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

This paper proposes a new crossover operator called two-part chromosome crossover (TCX) for solving the multiple travelling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. We adopt the two-part chromosome representation technique which has been proven to minimise the size of the problem search space. Nevertheless, the existing crossover method for the two-part chromosome representation has two limitations. Firstly, it has extremely limited diversity in the second part of the chromosome, which greatly restricts the search ability of the GA. Secondly, the existing crossover approach tends to break useful building blocks in the first part of the chromosome, which reduces the GA’s effectiveness and solution quality. Therefore, in order to improve the GA search performance with the two-part chromosome representation, we propose TCX to overcome these two limitations and improve solution quality. Moreover, we evaluate and compare the proposed TCX with three different crossover methods for two MTSP objective functions, namely, minimising total travel distance and minimising longest tour. The experimental results show that TCX can improve the solution quality of the GA compared to three existing crossover approaches.     

Bacterial memetic algorithm for offline path planning of mobile robots

The goal of the path planning problem is to determine an optimal collision-free path between a start and a target point for a mobile robot in an environment surrounded by obstacles. This problem belongs to the group of combinatorial optimization problems which are approached by modern optimization techniques such as evolutionary algorithms. In this paper the bacterial memetic algorithm is proposed for path planning of a mobile robot. The objective is to minimize the path length and the number of turns without colliding with an obstacle. The representation used in the paper fits well to the algorithm. Memetic algorithms combine evolutionary algorithms with local search heuristics in order to speed up the evolutionary process. The bacterial memetic algorithm applies the bacterial operators instead of the genetic algorithm??s crossover and mutation operator. One advantage of these operators is that they easily can handle individuals with different length. The method is able to generate a collision-free path for the robot even in complicated search spaces. The proposed algorithm is tested in real environment.