An Improved Bionic Optimization based on MAX-MIN Ant System

Abstract. This paper analyzes the characteristics of MMAS and Artificial fish algorithm; find their similarity optimization mechanism, combining with the advantages of two methods, and this paper puts forward a new hybrid bionic optimization algorithm; it can improve the efficiency of optimization algorithm. How to choose the most appropriate parameters or mainly based on low parameter requirements algorithm to combination of more efficient intelligent algorithm is the research work we want to continue, and design some more efficient adaptive algorithm to solving practical problems.

Key words:MAX-MIN Ant System; artificial fish algorithm; visual

1.Introduction

Ant colony algorithm is put forward algorithm in 1991 by Italian scholars dorigo meters, Maniezzo V, Colorni, has the characteristics of the foundation, on the groupment, robustness, and interoperability, fast and so on [1] and [2]. Because ants are random initial movement, it is difficult to find a short time optimal path or can't find, then easy to fall into the local extremum, lack of the global optimal, when the population size too big [3] [4].

Search time long (mini max ant system is German researcher put the Stuetzle T, Hoos H improved ant colony algorithm with the traditional. The difference ant colony algorithm is improved algorithm, the proposed algorithm only allow the ant path when had better update each iteration calculation, a pheromone help prevent premature convergence.

The convergence of the algorithm is faster and AFSA came early, but slow convergence speed convergence sometimes even stagnation in a later period, so it is difficult to obtain the precise optimal solution, only to find the optimal solution of the field [6] [7].

2.Basic algorithm

2.1. Mmas algorithm

Assuming the quantity of ant colony is m, the distance between the arbitrary paths is， express the quantity of ant colony located at pointiin the time of t , when， Express the residue pheromone at the moment ofton the route ofij .The value of is zero. Antdecide Movement direction according to pheromone on each route when movement.express the probability of ant select the routeijat the moment of t. Parameter express the coefficient of residue pheromone, express the Volatile coefficient of pheromone(the degree of information vanish).Each ant’s behavior meet:

1)According to corresponding probability and pheromone concentration select the next route.

2) Using a data structure named taboo list to control the ant select the route which had passed no longer. The taboo list store all routes until at tpoint, and taboo the ant visit again before seek out the optimal value by N iterations.

3) According to the whole route length release the pheromone of corresponding concentration when finished once iteration.

The updated rules and restrictions of pheromone:

1) Update the pheromone on the path of the best performance ant only,

(1)

Among.

2) The restrictions of pheromone: Set a top and bottom limitationand , and.This can avoid premature convergence. If , then; If, then.And to sure the .Set the maximum value to the estimate of maximum limit in the search process, and S is the global optimal solution:

(2)

Updateafter get the optimal solution, get dynamic change values

(3)

(4)

The average lengths of route decide the selection of maximum and minimum pheromone. Make the pheromone on some route will not be too high by setting, and avoid premature stagnation. Make it not less possibility to find new path due to pheromone too low.

The probability of ant k select route ij at the point tis:

(5)

if

Amongexpress

2.2.Artificial Fish Algorithm

The main behaviours for artificial fish algorithm are prey, swarm and follow.

Prey: suppose that current state is , random selection a statewithin the scope of the perception, step forward toward the direction of it when, random selection a stateestimate whether meet forward conditions; If don’t meet forward condition, random moving step after try number again and again.

Swarm: suppose that current state is, explore the partner numberand central positionof the current neighbourhood ( ). There are lots of foods in the partner central and not too crowed when. The fish move forward toward the direction of the central position, otherwise do prey behaviour.

Follow: suppose that current state is , explore the maximum partnerin the partners ofin the current neighbourhood (). There are lots of foods and not too crowed around partnerwhen, the fish move forward toward the direction of partner , otherwise do prey behavior.

Bulletin: records of the individual artificial fish state. Every artificial fish inspection its own state and bulletin boards states when finished every time optimization in the optimization process. It will change the bulletin state to its own state if its state was better. In that case the bulletin can record the best states.

The artificial fish’s behaviour principle is making each behaviour move to optimal direction. If don’t make the next state optimal compared against current state, take random behaviour.

3.ALGORITHM COMBINED WITH MMAS AND ARTIFICIAL FISH

3.1.Algorithm thought

MMAS and artificial fish algorithm are all belong to swarm optimization algorithm. The whole population exhibited some intelligent behavior when the number of individual to a certain extent. The aims of the ants are looking for optimal path, and the artificial fish is looking for foods. Their similarities are:

(1) Everywhere in the prime of ant colony algorithm at the point of are equal and all the ants chosen path randomly. The artificial fish select a state to try number within in view at the prime of the algorithm.

(2) Algorithm convergence of the ant colony algorithm via the update of the pheromone concentration() Pheromone is more, ants more. Artificial fish algorithm via the behaviours of follows and swarms to convergence. Generally speaking, if the area of the fish at most, the foods must be at most in this water area, and must be the optimal solution. The more artificial fish population could attract more fish.The behaviour of ants producing pheromones is similar to the action of swarm and follow of artificial fish.

(3) Many ants behaviour are random when the ants have a large number. This paper introduces the concept of visual before the iteration of every time. The ant k looks around the vision scope of the path after prepare to move from i to j until select the maximum path ij of and update the pheromone. If the paths cover in the vision have a better path than the current one ij , that is, then the ant again to choose the path. On the contrary, the ants select the path ij.

Ant colony algorithm is very easy to fall into local convergence at the prime of the algorithm. This paper introduced the concept of congestion degree (δ ) of artificial fish, can avoid individual gathered to the higher path of the pheromone prematurely at the prime time. Thus avoid premature convergence phenomenon of the ant colony, and improve global optimization ability of the algorithm.

3.2.Algorithm principles and steps

Take travelling salesman problem for example to describe the step of the algorithm:

Step1: Put m quantity ants into n quantity cities in time of t=0 randomly. The initial information of pheromone concentration in each path is =0

Step2: Let S =1 (S is the subscript of taboo table), Put the initial city number of the ant K into.

Signify that the ant K wander in the city S currently.

Step3: The probability of ant K transfer form position i to j:

(6)

if

Among signify the city which ant K was allowed to select next step. Parameter

and μ express the difference between accumulations of pheromone and heuristic factor (expectation) in the choice of the path in athletic process respectively, and

Step4: Calculating the path crowed degrees () when ants are expected to follow the above path to transfer.

, If , Signify that the path not

too crowed, and ants transfer form position i to j on this path. On the contrary, ants choose a suboptimal in the feasible neighbourhood again.is crowed degree threshold in time of t, and according to theto update.

Step6: update the concentration of pheromone .when finished iteration for n times. The formula is:

(7)

Among . Each iterations just updates the pheromone of the best ant’s to avoid search is too centralized. This paper main adopt pheromones smooth mechanism and adjust pheromone concentration by the way in proportion update. Make its added value is proportional to the D-value between and the side of (ij) of pheromone concentration

Step7: Update the bulletin boards after a circular, and show the optimal path value of this circular.Update bulletin board again until have the better path length next circular. Step8: Repeat step2 to step7, until convergence for a path only or at the designated iterations.

Step9: Algorithm terminates, and output optimalsolution.

4.EXAMPLE SIMULATION OF TSP

In order to detect the efficiency of the algorithm, we use the TSP problem Oliver30 as practical calculation example. Parameter selection of the algorithm: n=100, Visual=5, try number=10,, ,NC_max=200, Q=100,We use matlab9.0 to implement algorithm and the computer configuration for: Pentium(R) Dual-core E5400@2.7GH.2.69GH, 250G hard disk, 2G RAM.

Optimal curve and the shortest path as shown:

Fig.1 Optimal graph of the improved algorithm

Standard optimal solution is 423.7406. Integer distance is 420. The optimal distance of the paper reach is 423.2071. Slightly better than optimal solution, and algorithm precision improved, and achieve improvement purpose.

Compared with other algorithms

In order to further detect the efficiency of the algorithm, we use the TSP problem eil76 as practical calculation example.

5.CONCLUSION

Bionic optimization algorithm based on the MMAS and the artificial fish introduced visual concepts in MMAS form artificial fish algorithm for ants can more quickly find optimal path, and introduced crowded degree concepts of artificial fish algorithm to set strong crowded degree limit. The algorithm can global optimization better and avoid the local extreme value, and also accelerate the speed and improve the accuracy of the algorithm. However, MMAS has more demanding of parameter compared with AFSA, and this algorithm’s improvement is mainly based on ant colony algorithm, so the selection of algorithm parameter impact on the result directly.

6.References

[1]Dorigo M,Maniezzo V,Colorni A.Positive feedback as a search strategy. Technical Report, Dipartimento di Electronica, Politecnico di Milano,IT,1998, 91-116

[2]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies. Proceedings of the First European Conference on Artificial Life.Elsevier1999:134-142

[3]Stutzle T,Hoos H. Improvements on the ant system: Introducing MAX-MIN ant system. Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms. Wien: Springer Verlag,1997,115-128

[4]Stutzle T.MAX-MIN ant system for Quadratic Assignment Problems. Technical Report AIDA-97-04,Intellect Group, Department of Computer Science, Darmstadt University of Technology, Germany, July 1997,25-42

[5]Li Xiaolei,Qian Jixing. Artificial fish algorithm: Top-down optimization model. Process system engineering y-tzp powders,2010,76~82

[6]Li Xiaolei,Qian Jixing,Shao Zhijiang A method based on animal commune optimum model: Artificial fish algorithm, Systems Engineering-theory & Practice,2010,32-38

[7]Zhou Yongquan,Xie Zucheng. Solving TSP improvement artificially shoals algorithm, Systems Engineering and Electronics 2009,11(12): 44-47