Solving TSP Problem in Cloud Computing using Improved Cultural Algorithm

摘要

Traveling Salesman Problem (TSP), despite its simple appearance, is one of the classic and complex problems in Combinatorial Optimization and it is difficult to find an accurate answer for large samples. This problem is so important that many real-world problems can be turned into a TSP and solved. Optimization methods for solving difficult problems, such as TSP, mainly involve a large number of variables and constraints that reduce their practical efficiency in solving large-scale problems. An optimization algorithm includes factors that increase the speed of convergence, which can be inherited as a culture to the next generation. The basic idea of cultural algorithms is based on the theory that in advanced societies, in addition to the knowledge that parsons have in their genetic code and inherited from their ancestors, there is another element called culture for evolution. Culture is a set of accepted beliefs of community leaders. Of course, one of the disadvantages of this type of algorithm is the formation of a false culture and the adherence of all people to the same culture, which occasionally leads to local optimizations during the evolution process. The solution proposed in this paper to overcome this shortcoming is to select diverse leaders and consequently produce different subpopulations. This increases the diversity of people in the population and thus distributes the search throughout the problem space, and breaks the problem into smaller problems, and reduces the complexity of problem-solving temporality. In the meantime, cloud computing, given scalability and accessibility, provides us with good facilities. Using the capabilities of cloud computing, one problem can be divided into smaller sub-problems and solved in several virtual machines. Each of the virtual machines uses the improved culture algorithm technique proposed to solve their dedicated sub-problem. In the meantime, the nodes assigned to each machine are hidden from the other machine. Finally, the result is obtained by combining the results of all virtual machines, according to the proposed algorithm.