ACA And Its Application On Flow Shop Problem And Clustering Problem

Swarm intelligence were applied to solve most optimization problems, or problems that could be transformed as optimization problems. The theoretical basis and application of ant colony algorithm were developed continuously in recent years, and its application regime has been expanded to various kinds of engineering optimization problems. Ant colony algorithm discussed in this paper is one of optimal algorithms based on swarm intelligence. Dorigo designed ant colony algorithm in 1995, which was inspired from the swarm intelligence behavior of real ant searching food, and first developed to solve the classical computational algorithm of "traveling salesman problem"with quite computational effectiveness. Artificial ants were designed to simulate real ants scouting food activities when solving "traveling salesman problem", and the amount of pheromone left on the food searching trails by ant would evaporate with time updating. Each ant select the route according to the following random rules, that is the searching distance is shorter and pheromone information on trail is denser. So the optimal rout can be selected by the rule "the denser the pheromone on trail, the shorter the route will be". For artificial ant colony is specified by positive feedback mechanism, the shorter searching route can be selected with more chance with random-proportional rule, which is governed by probability formula, and so global optimal solution can be obtained without trapping into local optimal solution. Ant colony algorithm and its development history were retrospect, and comparison was done on the effectiveness of ant colony algorithm with different parameters. The effectiveness of ant colony algorithm was analyzed with properly selected parameters, and then an improved ant colony algorithm was developed for solving permutation Flow Shop problem. In the improved ant colony algorithm, random parameters and pheromone self-adaptation mechanism were applied in order to promote the convergence of the algorithm. Furthermore, mutation operation and noise interference operation were all employed in the algorithm with the aim to help artificial ant escaping local optimal solution by taking the best use of eigenvalue information. The result indicated that improved ant colony algorithm could play better in performance than that with traditional genetic algorithms when trying to solve the permutation Flow Shop problem. Minor improvement was done on the improved algorithm on the basis of ant colony algorithm's independence feature. And then, the algorithm was applied to solve general Flow Shop problem, the performance showed that minor change on the parameters of improved ant colony algorithm can be adapted easily to solve the general Flow Shop problem, and indicated that improved algorithm design is very reasonable. By selecting proper subjection function—triangle subjection function, new ant colony algorithm was designed to solve fuzzy Flow Shop problem, and the simulation result showed that the algorithm is proper and practicable. While the algorithm only testified by small scale fuzzy Flow Shop problem, the performance and effectiveness of this algorithm still need be testified by large scale fuzzy Flow Shop problem, and furthermore, improvement on the refinement of the algorithm need to be done in the future. An ant colony algorithm depending on amount of pheromone was designed to solve clustering problem, which is the second focus problem in this paper. The main aim of clustering is to classify collected samples to specified groups, and there exist great similarity with inner group, but great difference exist amount various groups. Artificial ants iterate each node, and separate each sample to proper groups according to its distance from temporary class center, and at same time, pheromone will be left on the trail between sample nodes to temporary class center. When artificial ant iterates all the sample nodes, target function will be recomputed, and new group center will be reallocated. In this way, ant will allocate each sample to certain group according to whether the amount of pheromone from one sample to a group is greater than that to other groups, and finally the clustering process is convergent to optimal classification result. This ant...