A Study On A Schema-based ANT Algorithm And Its Application On QAP

Ant colony algorithms have got good result when solving the Quadratic Assign-ment Problem (QAP). Many researches recently concentrate on how to improve thee?ciency of the algorithms, which is also the di?culty while resolving the other com-binational optimization problems by meta-heuristics. As long as we try to improve thealgorithms'performances, it is important to make a balance between exploitation andexploration. Exploitation makes the search move to the convergent areas so as to findthe best solutions as soon as possible . Exploration tends to find the feasible solutionswith di?erent structures.Fitness analysis of the landscape can help to balance between exploitation andexploration. Precisely speaking, it will help the search to decide when and how toexploit and explore the landscape.We propose a new concept called solution schema on the basis of analyzing thelandscape of QAP and apply the concept into ant colony algorithms and design aschema-based algorithm called SchemaANT. We analyze four parameters of this ap-proach which are bp, Ps, W and D. bp stands for the number of better permutationsthat construct the solution schema, Ps stands for the probability of selecting the ele-ment, W stands for the weight of each permutation and D stands for the distance oftwo di?erent solutions. We make a comprehensive analysis for the first two parameterson how they in?uence the solution schema. The algorithm is implemented on all fourtypes of the QAP beachmark. Experimental results show that the performances arewidely improved while using the solution schema but may be only worse for the secondtype.