A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

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

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

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

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

遗传算法的一种改进进化策略

在现有文献研究的基础上,对传统遗传算法的进化策略又作了进一步研究,提出了一种改进的进化策略.进化策略克服了传统遗传算法中交又得到的优秀个体有可能在变异过程中遭到破坏而不能生存的不足.另外取消了遗传算法中难以确定的交叉、变异概率,使交叉产生的新个体数增多,这样可增大产生更优秀个体的可能性,因而可使遗传算法的性能得到更好的改善.通过4个测试函数的测试计算,结果表明,给出的改进进化策略比传统遗传算法进化策略的运算速度明显提高,迭代次数明显减少,从而验证了提出的改进进化策略的有效性.     

Performance replication of the Spot Energy Index with optimal equity portfolio selection: Evidence from the UK,US and Brazilian markets

This paper reproduces the performance of a geometric average Spot Energy Index by investing only in a subset of stocks from the Dow Jones Composite Average, the FTSE 100 and Bovespa Composite indexes, and in two pools that include only energy-sector stocks from the US and the UK respectively. Daily data are used and the index-tracking problem for passive investment is addressed with two evolutionary algorithms – the differential evolution algorithm and the genetic algorithm. The performance of the suggested investment strategy is tested under three different scenarios: buy-and-hold, quarterly and monthly rebalancing, accounting for transaction costs where necessary.     

A hybrid optimization approach to index tracking

Index tracking consists in reproducing the performance of a stock-market index by investing in a subset of the stocks included in the index. A hybrid strategy that combines an evolutionary algorithm with quadratic programming is designed to solve this NP-hard problem: Given a subset of assets, quadratic programming yields the optimal tracking portfolio that invests only in the selected assets. The combinatorial problem of identifying the appropriate assets is solved by a genetic algorithm that uses the output of the quadratic optimization as fitness function. This hybrid approach allows the identification of quasi-optimal tracking portfolios at a reduced computational cost.     

Genetic algorithms with noisy fitness

The convergence properties of genetic algorithms with noisy fitness information are studied here. In the proposed scheme, hypothesis testing methods are used to compare sample fitness values. The “best” individual of each generation is kept and a greater-than-zero mutation rate is used so that every individual will be generated with positive probability in each generation. The convergence criterion is different from the frequently-used uniform population criterion; instead, the sequence of the “best” individual in each generation is considered, and the algorithm is regarded as convergent if the sequence of the “best” individuals converges with probability one to a point with optimal average fitness.     

Efficient tree traversal to reduce code growth in tree-based genetic programming

Genetic programming is an evolutionary optimization method following the principle of program induction. Genetic programming often uses variable-length tree structures for representing candidate solutions. A serious problem with variable-length representations is code growth: during evolution these tree structures tend to grow in size without a corresponding increase in fitness. Many anti-bloat methods focus solely on size reduction and forget about fitness improvement, which is rather strange when using an “optimization” method. This paper reports the application of a semantically driven local search operator to control code growth and improve best fitness. Five examples, two theoretical benchmark applications and three real-life test problems are used to illustrate the obtained size reduction and fitness improvement. Performance of the local search operator is also compared with various other anti-bloat methods such as size and depth delimiters, an expression simplifier, linear and adaptive parsimony pressure, automatically defined functions and Tarpeian bloat control.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

Differential Evolution with Wavelet Mutation in Digital Finite Impulse Response Filter Design

This paper proposes one novel algorithm called differential evolution with wavelet mutation for the optimal design of linear phase finite impulse response filters. For comparative performance study, the Parks–McClellan algorithm and some evolutionary algorithms like the real coded genetic algorithm, conventional particle swarm optimization, and conventional differential evolution have also been applied.     

A hybrid evolutionary algorithm for the two-dimensional packing problem

This paper presents a hybrid evolutionary algorithm for the two-dimensional non-guillotine packing problem. The problem consists of packing many rectangular pieces into a single rectangular sheet in order to maximize the total area of the pieces packed. Moreover, there is a constraint on the maximum number of times that a piece may be used in a packing pattern. The set of packing patterns is processed by an evolutionary algorithm. Three mutation operators and two types of quality functions are used in the algorithm. The best solution obtained by the evolutionary algorithm is used as the initial solution in a tree search improvement procedure. This approach is tested on a set of benchmark problems taken from the literature and compared with the results published by other authors.     

油田注水系统拓扑布局优化的混合遗传算法

以投资最小为目标函数,建立了注水系统拓扑布局优化数学模型.根据模型特点,将优化问题分为两层,分别采用遗传算法和非线性优化方法进行求解.并对遗传算法的操作过程进行了改进,调整了适应函数,改进了交叉和变异操作,结合了模拟退火算法,在操作过程中使约束条件得到满足,减少了不可行解的产生,使遗传算法的优化性能得到了提高.优化算例说明了该方法的有效性.     

Solving the Graphical Steiner Tree Problem Using Genetic Algorithms

We develop a genetic algorithm (GA) to solve the Steiner Minimal Tree problem in graphs. To apply the GA paradigm, a simple bit string representation is used, where a 1 or 0 corresponds to whether or not a node is included in the solution tree. The standard genetic operators — selection, crossover and mutation — are applied to both random and seeded initial populations of representations. Various parameters within the algorithm have to be set and we discuss how and why we have selected the values used. A standard set of graph problems used extensively in the comparison of Steiner tree algorithms has been solved using our resulting algorithm. We report our results (which are encouragingly good) and draw conclusions.     

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.     

A new multiobjective evolutionary algorithm

The Pareto-based approaches have shown some success in designing multiobjective evolutionary algorithms (MEAs). Their methods of fitness assignment are mainly from the information of dominated and nondominated individuals. On the top of the hierarchy of MEAs, the strength Pareto evolutionary algorithm (SPEA) has been elaborately designed with this principle in mind. In this paper, we propose a (μ+λ) multiobjective evolutionary algorithm ((μ+λ) MEA), which discards the dominated individuals in each generation. The comparisons of the experimental results demonstrate that the (μ+λ) MEA outperforms SPEA on five benchmark functions with less computational efforts.     

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.     

A few logs suffice to build (almost) all trees (I)

A phylogenetic tree, also called an “evolutionary tree,” is a leaf‐labeled tree which represents the evolutionary history for a set of species, and the construction of such trees is a fundamental problem in biology. Here we address the issue of how many sequence sites are required in order to recover the tree with high probability when the sites evolve under standard Markov‐style i.i.d. mutation models. We provide analytic upper and lower bounds for the required sequence length, by developing a new polynomial time algorithm. In particular, we show when the mutation probabilities are bounded the required sequence length can grow surprisingly slowly (a power of log n) in the number n of sequences, for almost all trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 153–184, 1999     

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.     

煤炭码头卸车调度问题多目标优化模型及算法

本文针对煤炭码头卸车调度问题,提出了相应的多约束多目标优化模型,并设计了采用仿真推演策略解码的遗传算法求解。首先,本文考虑列车、煤种、场存、设备、翻堆线和卸车作业过程等约束条件,以卸车效率最大和列车在港时间最短为目标,构建了煤炭码头卸车调度问题多目标数学模型。然后,综合运筹学、遗传算法以及仿真技术,给出了煤炭码头卸车调度问题遗传算法详细设计,包括组合式编码和仿真推演解码方法,染色体生成算法,适应度函数设计,以及采用多种策略的遗传操作及修正等,并列出了算法步骤。实例测试表明,本算法的执行效率高而且优化效果好,结果适用。