Membrane Algorithm with Brownian Subalgorithm and Genetic Subalgorithm
Membrane Algorithm with Brownian Subalgorithm and Genetic Subalgorithm
复制标题
DOI：
10.1142/s012905410700539x
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
T. Nishida
中科院分区：
文献类型：
--
作者：
T. Nishida
本文讨论了受模拟退火启发的带子算法的膜算法。模拟退火本质上是一种局部搜索，但它以“温度”确定的概率将解修改为更差的解。模拟退火的温度根据“冷却时间表”改变。另一方面，这里引入的子算法具有由子算法所在区域确定的恒定温度。它被称为布朗子算法，因为该子算法在搜索空间中引入了解的“热运动”，但不模拟“退火”。计算机模拟表明，对于旅行商问题的几个基准问题，具有三个区域并在每个区域中具有布朗子算法的膜算法可以获得很好的近似解.然而，该算法偶尔会得到相当糟糕的解决方案（是最优解的两倍）。一个膜算法，它有布朗和遗传子算法从来没有得到这样一个坏的解决方案（只有8%比最佳）的所有问题的检查，虽然，平均而言，它是不如布朗算法。结果表明，采用不同近似机制的子算法的膜算法在广泛的问题下都具有较好的鲁棒性。
Membrane algorithms with subalgorithms inspired by simulated annealing are treated in this paper. Simulated annealing is inherently a kind of local search but it modifies a solution to a worse one with a probability determined by "temperature". The temperature of simulated annealing is changed according to "cooling schedule". On the other hand, the subalgorithm introduced here has constant temperature which is determined by the region where the subalgorithm is. It is called Brownian subalgorithm since the subalgorithm incorporates "thermal movement" of a solution in the search space but does not simulate "annealing". Computer simulations show that a membrane algorithm which has three regions and has a Brownian subalgorithm in each region can obtain very good approximate solutions for several benchmark problems of the traveling salesman problem. However, the algorithm, occasionally, gets quite bad solutions (twice as large as the optimum) for a problem. A membrane algorithm which has both Brownian and genetic subalgorithms never gets such a bad solution (only 8% worse than the optimum) for all problems examined, although, in average, it is not as good as the algorithm with Brownian only. The result indicates that membrane algorithm with subalgorithms under different approximate mechanisms may be robust under a wide range of problems.