使用遗传算法改进R_时刻表算法

Improving Algorithms of R_ Time Table by Using Genetic Algorithm

给出了对于多成分R_时间表的解决办法。利用集合的性质把它看成是几个单成分时间关系约束的并集,采用算法I将多成分分解成单成分。使用遗传算法把问题的多成分的时间关系作为染色体的基因位,问题的所有的多成分的时间关系就构成了算法的染色体,以求解关系矩阵中求到的相容子集的个数作为染色体的适应度。算法的终止条件是根据关系矩阵求得的相容子集数等于事件的个数,利用算法II使用遗传算法求解多成分时间规划问题。对实际的问题进行了讨论,使用该算法在有穷次迭代后可得到可行解。

Gives the solution of R- time table under the multi - ingredient time relations. It can be looked on as the union of several simple - ingredient time relation constraints using the set property. Adopting the algorithm, can resolve the multi - ingredient as several simple - ingredients. Using genetic algorithm multi - ingredient time relations of the problems act as loci. The chromosomes of the algorithm are composed by all multi - ingredient time relations in the problem. The fitness in genetic algorithm is the amount of consistent subsets resulted from resolution of the relation matrix. And if the amount of events equals amount of consistent subsets, the algorithm is finished. The multi - ingredient temporal planning using the algorithm II can be resolved. It gives a discussion on the actual problem. The feasible solution is received after the finite iteration.