旅行商问题的人工免疫算法

1 引言旅行商问题(TSP)是一个典型的有序组合优化问题,可以看成是许多领域内复杂工程优化问题的抽象形式。研究TSP问题的求解方法对解决复杂工程优化问题具有重要的参考价值。对于TSP问题,目前还没有完全有效的求解方法,但是,多年来人们一直在不停地探索。近年来,模拟自然界生物进化过程的求解TSP问题的方法不断见诸文献,但以基于

An Artificial Immune Algorithm for Travelling Salesman Problem

This paper presents an Artificial Immune Algorithm (AIA)simulating the biological immune systems, and offers its basic principle and approach. Comparing AIA with Genetic Algorithm (GAs)simulating the biological evolution process, the paper points out that the method producing new antibodies in AIA is more versatile than the one producing new individuals in GAs. AIA reflects mechanism of natural selection better than GAs does, as AIA selects effective antibodies from all antibodies by the appetency between an antibody and an antigen and by the repulsion between an antibody and another, while GAs selects new individuals of next colony by the proportion of individual fitness. For Travel Salesman Problem (TSP), this paper brings forward how to describe antibodies artificially, how to produce original antibodies, how to compute the appetency between an antibody and an antigen and the repulsion between an antibody and another, and works out several artificial immune operators producing new antibodies. Simulating examples show that AIA is a very effective method for TSP.