Optimization strategies gleaned from biological evolution
Optimization strategies gleaned from biological evolution
复制标题
从生物进化中收集的优化策略
作者：
R. Brady
几个问题，特别是“旅行推销员”问题1，其中一个寻求最短的路线，包括随机分布的城市群，已被优化的反复随机改变（突变）的试验解决方案，然后选择更便宜（更适合）的解决方案。大多数非平凡问题具有复杂的适应度函数，并且优化往往会陷入局部适应度最大值。最近推出的策略逃避（模拟退火）包括接受不利的突变有限的概率1 -3。独立地，人们对克服生物进化中适应性最大值问题的遗传策略感兴趣4 -6，并且一些作者已经将生物元素应用于优化7，8。在这里，我们使用计算机算法来研究64个城市的旅行推销员问题的新策略，该问题将联合收割机传统的优化或“淬火”与生物元素相结合，即具有试验解决方案的群体，帮助较弱的个体生存，以及基因的有性交换的模拟。新的策略比模拟退火更快，得到更好的结果。
Several problems, in particular the ‘travelling salesman’ problem1 wherein one seeks the shortest route encompassing a randomly distributed group of cities, have been optimized by repeated random alteration (mutation) of a trial solution followed by selection of the cheaper (fitter) solution. Most non-trivial problems have complicated fitness functions, and optimization tends to become stuck in local fitness maxima. A recently introduced strategy to escape (simulated annealing) involves accepting unfavourable mutations with finite probability1–3. Independently, there has been interest in genetic strategies which overcome the problem of fitness maxima in biological evolution4–6, and several authors have applied biological elements to optimization7,8. Here we use computer algorithms to investigate new strategies for the 64-city travelling salesman problem, which combine conventional optimization or ‘quenching’ with biological elements, namely having a population of trial solutions, helping weaker individuals to survive, and an analogue of sexual crossing-over of genes. The new strategies were faster and gave better results than simulated annealing.