Solving bus terminal location problems using evolutionary algorithms

Bus terminal assignment with the objective of maximizing public transportation service is known as bus terminal location problem (BTLP). We formulate the BTLP, a problem of concern in transportation industry, as a p-uncapacitated facility location problem (p-UFLP) with distance constraint. The p-UFLP being NP-hard (Krarup and Pruzan, 1990), we propose evolutionary algorithms for its solution. According to the No Free Lunch theorem and the good efficiency of the distinctive preserve recombination (DPX) operator, we design a new recombination operator for solving a BTLP by new evolutionary and memetic algorithms namely, genetic local search algorithms (GLS). We also define the potential objective function (POF) for the nodes and design a new mutation operator based on POF. To make the memetic algorithm faster, we estimate the variation of the objective function based on POF in the local search as part of an operator in memetic algorithms. Finally, we explore numerically the performance of nine proposed algorithms on over a thousand randomly generated problems and select the best two algorithms for further testing. The comparative studies show that our new hybrid algorithm composing the evolutionary algorithm with the GLS outperforms the multistart simulated annealing algorithm.     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

Memetic algorithm using multi-surrogates for computationally expensive optimization problems

In this paper, we present a multi-surrogates assisted memetic algorithm for solving optimization problems with computationally expensive fitness functions. The essential backbone of our framework is an evolutionary algorithm coupled with a local search solver that employs multi-surrogate in the spirit of Lamarckian learning. Inspired by the notion of ‘blessing and curse of uncertainty’ in approximation models, we combine regression and exact interpolating surrogate models in the evolutionary search. Empirical results are presented for a series of commonly used benchmark problems to demonstrate that the proposed framework converges to good solution quality more efficiently than the standard genetic algorithm, memetic algorithm and surrogate-assisted memetic algorithms.     

Real-coded memetic algorithms with crossover hill-climbing

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.     

A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines

This paper presents a hybrid memetic algorithm for the problem of scheduling n jobs on m unrelated parallel machines with the objective of maximizing the weighted number of jobs that are completed exactly at their due dates. For each job, due date, weight, and the processing times on different machines are given. It has been shown that when the numbers of machines are a part of input, this problem is NP-hard in the strong sense. At first, the problem is formulated as an integer linear programming model. This model is practical to solve small-size problems. Afterward, a hybrid memetic algorithm is implemented which uses two heuristic algorithms as constructive algorithms, making initial population set. A data oriented mutation operator is implemented so as to facilitate memetic algorithm search process. Performance of all algorithms including heuristics (H1 and H2), hybrid genetic algorithm and hybrid memetic algorithm are evaluated through computational experiments which showed the capabilities of the proposed hybrid algorithm.     

Assignment of cells to switches in cellular mobile network: a learning automata-based memetic algorithm

Handoff and cabling costs management plays an important role in the design of cellular mobile networks. Efficient assigning of cells to switches can have a significant impact on handoff and cabling cost. Assignment of cells to switches problem (ACTSP) in cellular mobile network is NP-hard problem and consequently cannot be solved by exact methods. In this paper a new memetic algorithm which is obtained from the combination of learning automata (LA) and local search is proposed for solving the ACTSP in which the learning automata keeps the history of the local search process and manages the problem’s constraints. The proposed algorithm represents chromosome as object migration automata (OMAs), whose states represent the history of the local search process. Each state in an OMA has two attributes: the value of the gene (allele), and the degree of association with those values. The local search changes the degree of association between genes and their values. To show the superiority of the proposed algorithm several computer experiments have been conducted. The obtained results confirm the efficiency of proposed algorithm in comparison with the existing algorithms such as genetic algorithm, memetic algorithm, and a hybrid Hopfield network-genetic algorithm.     

Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.     

Balancing exploration and exploitation in memetic algorithms: A learning automata approach

One of the problems with traditional genetic algorithms (GAs) is premature convergence, which makes them incapable of finding good solutions to the problem. The memetic algorithm (MA) is an extension of the GA. It uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, we introduce a new algorithm based on learning automata (LAs) and an MA, and we refer to it as LA‐MA. This algorithm is composed of 2 parts: a genetic section and a memetic section. Evolution is performed in the genetic section, and local search is performed in the memetic section. The basic idea of LA‐MA is to use LAs during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. For this purpose, we present a criterion for the estimation of success of the local search at each generation. This criterion is used to calculate the probability of applying the local search to each chromosome. We show that in practice, the proposed probabilistic measure can be estimated reliably. On the basis of the relationship between the genetic section and the memetic section, 3 versions of LA‐MA are introduced. LLA‐MA behaves according to the Lamarckian learning model, BLA‐MA behaves according to the Baldwinian learning model, and HLA‐MA behaves according to both the Baldwinian and Lamarckian learning models. To evaluate the efficiency of these algorithms, they have been used to solve the graph isomorphism problem. The results of computer experimentations have shown that all the proposed algorithms outperform the existing algorithms in terms of quality of solution and rate of convergence.     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

In previous work, we developed three deadlock removal strategies for the job shop scheduling problem (JSSP) and proposed a hybridized genetic algorithm for it. While the genetic algorithm (GA) gave promising results, its performance depended greatly on the choice of deadlock removal strategies employed. This paper introduces a genetic algorithm based scheduling scheme that is deadlock free. This is achieved through the choice of chromosome representation and genetic operators. We propose an efficient solution representation for the JSSP in which the job task ordering constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided, thus resulting in increased efficiency. A mutation-like operator geared towards local search is also proposed which further improves the solution quality. Lastly, a hybrid strategy using the genetic algorithm reinforced with a tabu search is developed. An empirical study is carried out to test the proposed strategies.     

移动群智感知系统中基于离散布谷鸟搜索算法的任务分配

针对移动群智感知系统中工人积极性低以及任务过期的问题,提出了基于初始成本和软时间窗的任务分配算法。对应的任务分配问题为NP-hard问题,不存在计算有效的最优算法,因此,基于离散布谷鸟搜索算法（DCSA）进行求解。首先,根据问题特征,分别设计了对应的全局搜索过程以及局部搜索过程。其次,根据任务与工人起始位置的距离以及时间窗大小,分析其优先级以便得到更好的解。最后,执行可行化操作,使各次任务分配均满足相关约束。仿真结果表明,与遗传算法和贪婪算法相比,基于DCSA的任务分配算法能够提升工人的参与积极性,解决任务过期的问题,并最终降低系统的总成本。     

Artificial immune systems for assembly sequence planning exploration

Assembly sequence planning (ASP) needs to take relevant constraint factors such as the geometric characteristics and tool factors into consideration so as to work out a particular assembly sequence. At last, a product will come into being through the assembly of each part according to the assembly sequence. A problem encountered in ASP is that a larger number of components will cause more constraints to assembly a product, thus increasing the complexity of assembly problem. Therefore, it has been an objective for researchers to look for suitable methods for the solution space of feasible solutions.Among them, traditional genetic algorithms (GAs) belong to a random searching method. When the constraints are complicated in ASP, GAs often come out with a large number of solutions not feasible. Consequently, previous research results have proposed some approaches such as Guided genetic algorithms (Guided-GAs) or memetic algorithms (MAs) to enhance the structure of GAs to cope with the complexity of constraints in ASP problems. In this study, artificial immune systems (AIS) were proposed to help solve the assembly sequence problem. In AIS algorithm, the antibody (Ab) in the immune system is simulated to encounter one or more unknown antigens (Ags). Moreover, the clonal selection concept is employed in the immune system in which a better antibody will be selected in each generation of revolution and different antibodies will be cloned to protect the infection of the original antigen. With this mechanism, the shortcoming such as the traditional GAs to converge in local optimal solution will be overcome. Practical examples have demonstrated that AIS can solve the ASP problem with complicated constraints. Compared with guided genetic algorithms and memetic algorithms, AIS can generate the same or better solutions in terms of quality and searching time.     

多中心联合配送模式下集货需求随机的VRPSDP问题

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.     

A differential memetic algorithm

Memetic algorithms have been devised to rectify the absence of a local search mechanism in evolutionary algorithms. This paper proposes a differential memetic algorithm (DMA). To this end, first we propose a differential bidirectional random search as a local search algorithm. Then, a randomized blending crossover (RBleX) is proposed which aimed to scatter the new born offspring more diversely in the whole search space. We devise our proposed DMA, by using the RBleX crossover in the GA, and including the DBRS local search algorithm. A comparison of the performance of the DMA and those of seven other evolutionary/memetic or hybrid algorithms reported in two different papers on numerous bechmark functions demonstrates better performance of proposed DMA algorithm in most of the cases.     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

Improving fuzzy cognitive maps learning through memetic particle swarm optimization

Fuzzy cognitive maps constitute a neuro-fuzzy modeling methodology that can simulate complex systems accurately. Although their configuration is defined by experts, learning schemes based on evolutionary and swarm intelligence algorithms have been employed for improving their efficiency and effectiveness. This paper comprises an extensive study of the recently proposed swarm intelligence memetic algorithm that combines particle swarm optimization with both deterministic and stochastic local search schemes, for fuzzy cognitive maps learning tasks. Also, a new technique for the adaptation of the memetic schemes, with respect to the available number of function evaluations per application of the local search, is proposed. The memetic learning schemes are applied on four real-life problems and compared with established learning methods based on the standard particle swarm optimization, differential evolution, and genetic algorithms, justifying their superiority.     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

城市轨道车辆阻力公式经验参数文化基因优化算法的研究

为了解决城市轨道车辆阻力公式经验参数不易精确求解的问题,提出了一种改进的文化基因优化算法。首先,基于城市轨道车辆运行阻力经验公式和实际的运行数据,建立了城市轨道车辆运行阻力经验参数最优化问题的数学模型。为提升算法性能以提高求解精度,结合了遗传算法全局搜索能力强与粒子群算法收敛速度快的特点,进行优势互补,构造了的一种混合算法以便于全局搜索。其次,结合方程组求解法求解速度快和爬山法局部搜索能力强的特点,构造了一种混合算法以便于局部搜索。最后,在Matlab2010a GUI平台下采用几种不同的经验参数辨识算法和优化算法进行仿真试验。仿真结果表明,在相同条件下改进的文化基因优化算法能够寻到更精确的阻力公式经验参数。     

Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.