| Author | Barman, Shashwata Roy |
| Call Number | AIT Thesis no. CS-93-06 |
| Subject(s) | Traveling-salesman problem
|
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of
Engineering |
| Publisher | Asian Institute of Technology |
| Abstract | While non-adaptive neural nets was first used to solve the TSP, it had problems of
ascertaining weights and feasibility of solutions. ANGENIOL et al(1988) was first to use self-organization
for TSP. BURKE et al (1992) uses biased competition and a neural ring structure
where number of neurons equals number of cities. However her algorithm is prone to come
close to solution and stagnate asymptotically. Our proposed algorithm retains the engine of self-organization
and the neural ring structure. We introduce new concepts of redistribution of neurons
to guarantee convergence and freezing of neurons to quench the net towards convergence. We
explicitly take care to reduce self-intersection of edges by interchanging the guilty neurons during
the process of self-organization. We use a new biased competition scheme to make the net robust
to variations of bias but retaining the better node separation effect. We then benchmark our
algorithm vis-a-vis simulated annealing, Elastic net with the data sets of DURBIN et al (1987).
We find our algorithm's performance compares appreciably with those. It is better than Elastic
net in most cases and the objective function value is less then 1 % more than obtained by
simulated annealing. It has been successfully tested for 500 city and 1500 city problems. We also
adapt our algorithm to the shortest hamiltonian path problem with a fixed starting and a fixed
finishing city using an analogous neural thread approach. |
| Year | 1993 |
| Type | Thesis |
| School | School of Engineering and Technology (SET) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Sadananda, Ramakoti; |
| Examination Committee(s) | Murai, Shunji;Yulu, Qi; |
| Scholarship Donor(s) | Government of Japan; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, c1993 |
