Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows may be imposed.
Published in Chapter:
Studies of Computational Intelligence Based on the Behaviour of Cockroaches
Amartya Neogi (Dr. B. C. Roy Engineering College, India)
Copyright: © 2015
|Pages: 48
DOI: 10.4018/978-1-4666-8291-7.ch004
Abstract
In this chapter, the author expands the notion of computational intelligence using the behavior of cockroaches. An introduction to cockroach as swarm intelligence emerging research area and literature review of its growing concept is explained in the beginning. The chapter also covers the ideas of hybrid cockroach optimization system. Next, the author studies the applicability of cockroach swarm optimization. Thereafter, the author presents the details of theoretical algorithm and an experimental result of integration of robot to some cockroaches to make collective decisions. Then, the author proposes his algorithm for traversing the shortest distance of city warehouses. Then, a few comparative statistical results of the progress of the present work on cockroach intelligence are shown. Finally, conclusive remarks are given. At last, the author hopes that even researchers with little experience in swarm intelligence will be enabled to apply the proposed algorithm in their own application areas.