Home Download Help Resources Extensions FAQ References Contact Us Donate Models: Library Community Modeling Commons User Manuals: Web Printable Chinese Czech Japanese |
## NetLogo User Community Models(back to the NetLogo User Community Models) ## Improved Clonal Selection Algorithm for Solving Travelling Salesman Problem (v_4_1_3)by Adil Baykasoglu, Alper Saltabas, A. Serdar Tasan, Kemal Subulan (Submitted: 03/04/2012)
This model demonstrates the first application of an improved clonal selection algorithm to a traveling salesman problem (Eil51). Clonal selection algorithm is one of the most famous biologically-inspired artificial immune system algorithm. Traditional clonal selection algorithm works by generating a random antibody population of solutions for a problem, evaluating those solutions and then using cloning and hypermutation to create new solutions to the problem. But experiments showed that this traditional method has low performance to solve the traveling salesman problems. Thus, in the present model crossover mechanism [1] and receptor-editing process [2] are integrated into traditional clonal selection algorithm.
In the present model "real valued vectors shape space" is used to represent solutions.
"1 / travel tour distance" metric is used as the affinity measure.
The improved clonal selection algorithm is composed of the following steps.
Step 1: Create an antibody population of random solutions (parameter:
Step 2: Calculate affinity for each antibody.
Step 3: According the affinity, select n antibodies and sort in descending order.
Step 4: Clone the selected antibodies. (parameter: clone-size)
Step 5: Hypermutate and receptor-editing process. Update affinities.
Step 6: Crossover process. Update affinities.
Step 7: According the affinity of antibodies that are created in step 5 and step 6,
Step 8: Update antibodies by comparing the affinity of antibodies that are selected in
Step 9: In each "replacement-frequency" generation, select k antibodies according to
Step 10: If the iteration number reaches maximum generation number, stop. Else, go to
Press the SETUP button to create a random initial antibody population.
Press the GO button to run improved clonal selection algorithm to solve the traveling salesman problem. "Eil51" problem from the literature is programmed as an example.
For running the model number-of-city slider is adjusted correctly. This parameter is used as a variable in the procedure of the model.
In each "replacement-frequency" generation the best solution tour can be seen in the VIEW.
Parameters:
Initial-population-size: This slider controls the initial population size. For example, if initial-population-size is 400, algorithm will create 400 random antibody at zeroth generation.
Number-of-generation: This slider controls maximum number of generation that limits the running time of the algorithm.
Selection-size: This slider controls selection size that is used in step 3 and step 5 of algorithm.
Clone-size: This slider controls clone size that is used in step 4 of the algorithm. Clone size parameter is not enough to determine real clone size in the algorithm. Real clone size is determined by using a function that contains clone-size parameter. Through this function, antibody which has better affinity clones more and antibody which has worse affinity clones less.
Replacement-frequency: This slider is used to determine replacement generation. For example, if replacement-frequency parameter is 20, algorithm will achieve replacement process in 20th, 40th, 60th, ... generation.
Replacement-rate: This slider controls replacement size as percentage. This parameter is used in step 9 of the proposed algorithm. For example, if antibody population size is 100 and replacement-rate is 20(%), the algorithm will kill 20 antibody that have worst affinity and then insert 20 random antibody into the population.
The "Tour Length Plot" is used to show the best, average, and worst tour length values of the solutions at each generation.
You can make many different experiments by changing the parameters.
[1] Dai, H.; Yang, Y.; Li, C., “Distance Maintaining Compact Quantum Crossover Based Clonal Selection Algorithm”, Journal of Convergence Information Technology, Volume 5, No 10, 2010.
If you mention this model in an academic publication, we ask that you include these citations:
For the model itself:
-2) Baykasoglu, A.; Saltabas, A.; Tasan, A.S.; Subulan, K. (2012). Improved Clonal Selection Algorithm for Travelling Salesmen Problem in NetLogo. Dokuz Eylul University, Faculty of Engineering, Department of Industrial Engineering, Tinaztepe Campus, 35160 Izmir, Turkey.
For the NetLogo software:
In other publications, please use:
Copyright: Baykasoglu, A.; Saltabas, A.; Tasan, A.S.; Subulan, K. (2012). |

(back to the NetLogo User Community Models)