Ramsey重数研究

对于图G_1,G_2,2色广义Ramsey数R(G_1,G_2)表示满足下列条件的最小正整数p:如果用2种颜色中的一种对K_p的每一条边染色,总有K_p的一个子图同构于G_i,它的边都染有第i种颜色,1≤i≤2.对K_(R(G))的所有可能的边2-着色中,含有单色子图G的最少的个数称为图G的重数.利用计算机计算了若干不小于5阶图的Ramsey重数精确值:M(C_6)=10,M(P_6)=300,M(P_7)=720;当计算量很大时,利用模拟退火算法得到了若干Ramsey重数的上界:M(B_4)≤51,M(K_(2,4))≤24,M(K_(3,3))≤150,M(K_(2,5))≤47,M(W_6)≤34,M(B_5)≤48.     

AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

Membrane algorithms （MAs）, which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The em-pirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural net-work and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.