Selecting survivors in genetic algorithm using tabu search strategies

Genetic algorithm (GA) is well-known for its effectiveness in global search and optimization. To balance selection pressure and population diversity is an important issue of designing GA. This paper proposes a novel hybridization of GA and tabu search (TS) to address this issue. The proposed method embeds the key elements of TS—tabu restriction and aspiration criterion—into the survival selection operator of GA. More specifically, the tabu restriction is used to prevent inbreeding for diversity maintenance, and the aspiration criterion is activated to provide moderate selection pressure under the tabu restriction. The interaction of tabu restriction and aspiration criterion enables survivor selection to balance selection pressure and population diversity. The experimental results on numerical and combinatorial optimization problems show that this hybridization can significantly improve GAs in terms of solution quality as well as convergence speed. An empirical analysis further identifies the influences of the TS strategies on the performance of this hybrid GA.     

基于TSP问题的一种改进遗传算法

针对传统遗传算法(GA)在解决旅行商问题(TSP)时存在的不足,对初始种群的选取方式和算子的选取进行了改进,设计出了一种能够较好的求解出TSP问题的最优解的算法.计算机仿真实验验证了该算法的有效性.     

实数遗传算法进化策略的改进研究

在现有文献研究的基础上,对传统实数遗传算法的进化策略又作了进一步研究,提出了一种改进的进化策略.进化策略克服了传统实数遗传算法中交叉得到的优秀个体有可能在变异过程中遭到破坏而不能生存的不足,并取消了交叉概率,使交叉产生的个体数增多,这样可增大产生更优秀个体的可能性,因而可使实数遗传算法的性能得到更好的改善.另外,给出了一种计算种群中个体适应度的计算公式和计算方法.该方法不但使得遗传算法具有较强的局部搜索能力,而且具有较强的广域搜索能力和较好的种群多样性,不易陷入局部最优解,从而可快速收敛到全局最优解.5个测试函数的计算结果表明,给出的实数遗传算法的改进进化策略比传统实数遗传算法进化策略的运算速度明显提高,迭代次数明显减少,从而验证了提出的实数遗传算法改进进化策略的有效性.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

用遗传算法求解分组旅行推销员问题

在遗传算法能够有效解决TSP问题的基础上，根据遗传算法——通过搜索大规模，多样化的种群，在种群间交换个体所携带的遗传信息，保留种群中个体的优越遗传信息——的思想，设计了求解分组TSP问题的遗传算法。算法中染色体表示、评价函数的构造、杂交变异算子的设计经过实例计算的检验被证明较为可靠；算法运算速度快，容易获得有效解。     

改进GA机制融合的二进制蜂群算法研究

为了克服人工蜂群算法蜜源更新过程中的随机性并保留蜜源中个体序列合理的组合形式,通过分析基本蜂群算法更新公式的机理,提出一种改进GA(Genetic A1gorithm)机制融合的二进制蜂群算法.算法以二进制编码,首先依概率对任意两蜜源进行"去同存异"操作后随机排列,将排列结果放入到其中某个体中形成新个体.然后依概率进行二进制个体的"翻转"操作,上述两种操作从其本质上相当于GA的类交叉和类变异操作;其次利用GA机制收敛性的证明方式在理论上证明算法是收敛的.最后通过应用不同特性的多维基准函数和算法之间的比较验证改进蜂群算法具有良好的收敛能力和鲁棒性.     

Reliability based assignment in stochastic-flow freight network

Based on the reliability of transportation time, a transportation assignment model of stochastic-flow freight network is designed in this paper. This transportation assignment model is built by mean of stochastic chance-constraint programming and solved with a hybrid intelligent algorithm (HIA) which integrates genetic algorithm (GA), stochastic simulation (SS) and neural network (NN). GA is employed to report the optimal solution as well as the optimal objective function values of the proposed model. SS is used to simulate the value of uncertain system reliability function. The uncertain function approximated via NN is embedded into GA to check the feasibility and to compute the fitness of the chromosomes. These conclusions have been drawn after a test of numerical case using the proposed formulations. System reliability, total system cost and flow on each path would finally reach at their own convergence points. Increase of the system reliability causes increase of the total time cost. The system reliability and the total time cost converge at a possible Nash Equilibrium point.     

求解旅行商问题的基于类Kruskal的混合粒子群算法

本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题,提出一种基于Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法(SKHPSO)。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段,产生一个较优的初始可行解,作为粒子群中的一员,然后再用改进的混合粒子群算法进行启发式搜索。SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索,而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析,结果表明:SKHPSO可明显提高求解的质量和效率。     

Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study

The potential of Genetic Algorithmic (GA) approaches for solving order-based problems including the Traveling Salesman Problem (TSP) is recognized in a number of recent studies. By applying various GAs, these studies developed a set of unresolved GA design and configuration issues. The purpose of this study is to resolve the conflicting GA design and configuration issues by (1) concentrating on the classical TSP; and (2) developing, implementing, and testing a complete set of alternative GA configurations, 144 GAs are developed and evaluated by solvinh 5000 TSPs. A carefully designed statistical experimental plan accompanied by rigorous statistical analysis isolate the most promising configurations and identify their effect on solution time and quality. Although, the emphasis is on the TSP, the final results are applicable to other order-based problems that use sequence encoding.     

基于在线评论的新产品定向市场播种最优策略研究

定向市场播种,即选择特定的消费群体对其免费发放新产品,由此获得的在线评论对其他潜在消费者的购买决策有较大的影响作用,但还没有 相关研究。以在线销售的新产品为研究对象,基于Hoteling模型,加入在线评论对消费者预期值的影响作用来构建企业最优收益模型,研究垄断厂商最优的定向播种策略。研究结果揭示了(1)最优播种目标与消费者对产品的初始预期值相关:预期值较高时,可不播种;预期值处于中等水平,可选择均匀播种;预期值较低时,应选择高匹配用户播种;(2)三种播种方式下各自的最优播种比例及其定价策略;(3)当消费者初始预期值与产品不匹配成本发生变化时,三种播种策略下最优的播种比例和定价策略的调整方案。研究结果为探究在线评论对播种策略的影响提供了新的研究方向和理论依据。     

On simulated annealing with temperature-dependent energy and temperature-dependent communication

Simulated annealing (SA) is a generic optimization method that is quite popular because of its ease of implementation and its optimal convergence properties. Still, SA is widely reported to converge very slowly and it is common practice to allow extra freedom in its design at the expense of losing global convergence guarantees.In this paper, we derive simple sufficient conditions for the global convergence of SA when the cost function and the candidate solution generation mechanism are temperature-dependent. These conditions are surprisingly weak-they do not involve the variations of the cost function with temperature-and exponential cooling makes it possible to be arbitrarily close to the best possible convergence exponent of standard SA.     

Convergence of monotone iterations to initial value problems of functional differential equations

The method of quasilinearization is a well-known technique for obtaining approximate solutions of nonlinear differential equations. We use this technique to initial value problems of functional differential equations showing that corresponding linear iterations converge to the unique solution of our problem and this convergence is superlinear     

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.     

Annealing a Genetic Algorithm for Constrained Optimization

In this paper, we adapt a genetic algorithm for constrained optimization problems. We use a dynamic penalty approach along with some form of annealing, thus forcing the search to concentrate on feasible solutions as the algorithm progresses. We suggest two different general-purpose methods for guaranteeing convergence to a globally optimal (feasible) solution, neither of which makes any assumptions on the structure of the optimization problem. The former involves modifying the GA evolution operators to yield a Boltzmann-type distribution on populations. The latter incorporates a dynamic penalty along with a slow annealing of acceptance probabilities. We prove that, with probability one, both of these methods will converge to a globally optimal feasible state.     

改进鲸鱼优化算法在电力负荷调度中的应用

为了提高鲸鱼优化算法(WOA)的全局优化性能, 提出了一种基于黄金分割搜索的改进鲸鱼优化算法(GWOA)。首先利用黄金分割搜索对WOA的初始种群进行初始化, 使得初始种群能够尽可能的靠近全局最优解, 然后利用黄金分割搜索所形成的变区间, 进行变区间黄金分割非均匀变异操作, 以增加WOA的粒子多样性和提高粒子跳出局部最优陷阱的能力, 从而改善WOA的寻优性能。选取了15个大规模测试函数进行数值仿真测试, 仿真结果和统计分析表明GWOA的寻优性能要优于对比文献的改进鲸鱼优化算法(IWOA)。此外, 将GWOA用于对工程实际应用领域中的电力负荷优化调度问题进行实例分析, 实例应用结果表明, GWOA能有效对电力负荷优化调度问题进行寻优求解。     

父代种群参与竞争遗传算法几乎必然收敛

熟知,标准遗传算法如不采用“杰出者记录策略”则必不收敛。本文发现：允许父代种群参与竞争是标准遗传算法几乎必然收敛的条件。特别地,我们运用鞅收敛定理证明：允许父代种群参与竞争型遗传算法能以概率1确保在限步内达到全局最优解,且收敛与种群规模无关。所获结果对该类遗传算法的应用奠定了可靠基础。     

An accelerated differential evolution algorithm with new operators for multi-damage detection in plate-like structures

This paper proposes an Accelerated Differential Evolution (ADE) algorithm for damage localization and quantification in plate-like structures. In this study, the inverse damage detection problem is formulated as a nonlinear optimization problem. The objective function is established through the alterations of the structure flexibility matrix weighted with a penalty-function, used specifically to prevent the detection of false alarms. The ADE algorithm is designed via the introduction of three modifications in the standard differential evolution algorithm. Firstly, the initial population is created using knowledge we usually have about the damage scenario of a structure. Such initialization technique assists the algorithm to converge promptly. Secondly, in the mutation phase, a new difference vector, created based on the dispersion of individuals through the search space, is used to ensure the automatic balance between global and local searching abilities. Thirdly, a new exchange operator is designed and used to avoid the untimely convergence to local optima. Finite-element models of isotropic and laminated composite plates are considered as numerical examples to test the efficiency of the proposed approach. Numerical results validate the performance of the ADE method, in terms of both solution accuracy and computational cost and highlight its ability to locate and assess damage, even for large-scale problems and noise-contaminated data.     

阶梯状黄土边坡稳定性分析的改进遗传算法及应用

阶梯状黄土边坡稳定性分析的关键是估算其稳定系数的最小值.稳定系数的求解涉及诸多因素且计算过程繁杂,传统优化算法往往不能有效地搜索到其全局最小解.为此,提出一种改进的自适应遗传算法.算法对基因变量空间进行网格状划分,采用迭代选优法建立均匀分布的初始种群,运用优质个体保留遗传策略,并按照特定的准则自适应地调整交叉概率和变异概率,提高算法的全局搜索能力和收敛速度.实例应用表明算法能够快速有效地收敛于土坡稳定系数的全局最小解,且计算结果与实际情况更加吻合.     

Kantorovich distance in the martingale CLT and quantitative homogenization of parabolic equations with random coefficients

The article begins with a quantitative version of the martingale central limit theorem, in terms of the Kantorovich distance. This result is then used in the study of the homogenization of discrete parabolic equations with random i.i.d. coefficients. For smooth initial condition, the rescaled solution of such an equation, once averaged over the randomness, is shown to converge polynomially fast to the solution of the homogenized equation, with an explicit exponent depending only on the dimension. Polynomial rate of homogenization for the averaged heat kernel, with an explicit exponent, is then derived. Similar results for elliptic equations are also presented.